Quantitative Finance

Computer Science Concepts

Recursive Backtracking

     

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 2020.

1
2
3
4
2
4 1
5 2 4
3 9 0 5

That is, 2+4+5+9=202 + 4 + 5 + 9 = 20.

Devise a backtracking solution to find the maximum total from top to bottom of the triangle below:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
9 
75 59 
57 51 32 
63 14 83 29 
67 93 35 21 87 
9 21 56 3 58 87 
10 86 100 15 27 68 46 
85 95 54 5 22 60 2 51 
33 7 9 62 29 13 3 24 2 
17 54 23 59 81 59 54 24 2 100 
19 29 63 37 25 75 31 17 2 81 78 
21 96 67 59 2 72 60 64 4 66 8 82 
51 67 52 30 64 80 14 85 89 98 82 70 9 
58 88 23 16 56 52 68 65 89 56 87 43 2 37 
61 64 59 56 28 25 63 93 91 43 85 41 99 83 81 

Suppose you are given an m×nm \times n matrix AA with 00's and 11's. The matrix represents a maze. The aim is to move from any starting position (x,y)(x,y) to the position (m1,n1)(m-1,n-1) following the path's of 11's, when you are only allowed to move to directly adjacent squares.

Write a program to determine the existence of such paths and apply it to the following text file. Which of the (row, column) pairs in our options are connected to position (m-1, n-1)?

Select one or more

You are given an N×NN \times N chess board, empty but for a single knight. Write a program that determines the existence of a series of a legal knight moves that result in the knight visiting every square on the chessboard exactly once. The program is given only the starting coordinate of the "tour" as input.

Suppose N=5N = 5. Which of the following starting points will not lead to a valid knight tour?

Details and assumptions

  • A coordinate is just a tuple of two numbers (x,y)(x,y). For example, (0,0)(0,0) and (0,4)(0,4) are the top left and top right cells in the board respectively.
×

Problem Loading...

Note Loading...

Set Loading...