Introduction to Analysis of Algorithms - Graph and DP algorithms. 

please provide step-by-step instructions I believe graph algo would help with the question.
 

 

Transcribed Image Text:

Problem 1 (Snakes and Ladders, ). Snakes and Ladders is a classic board game, originating in India no later than the 16th century. The board consists of an n x n grid of squares, numbered consecutively from 1 to n, starting in the bottom left corner and proceeding row by row from bottom to top, with rows alternating to the left and right. Certain pairs of squares, always in different rows, are connected by either "snakes" (leading down) or "ladders" (leading up). Each square can be an endpoint of at most one snake or ladder. An example board is shown in figure 1. 100 99 97 96 94 93 92 91 81 82 8 80 84 85 86 87 89 90 78 77 76 75 74 73 71 61 62 63 64 65 66 68 6 70 58 555 545 52 51 60 41 443 5 46 4 48 49 40 39 38 37 36 35 34 33 32 31 21 22 23 25 6 28 29 30 20 19 8 1 16 514 3 2 11 4 5 5 7 9 10 Figure 1: A typical Snakes and Ladders board. Upward straight arrows are ladders; downward wavy arrows are snakes. You start with a token in cell 1, in the bottom left corner. In each move, you advance your token up to k positions (i.e. from your current square s to any square from s +1 to s+ k), for some fixed constant k (typically 6). If the token ends the move at the top end of a snake, you must slide the token down to the bottom of that snake. If the token ends the move at the bottom end of a ladder, you may move the token up to the top of that ladder. (a) Describe an algorithm to compute the smallest number of moves required for the token to reach the last square of the grid. Don't forget to take into consideration when the last square (b) (c) can not be reached. Analyze the runtime of your algorithm if the board is given explicitly as an n x n grid of squares, each with fields indicating whether they are the start of a snake or ladder and giving the destination if so. Analyze the runtime of your algorithm (in terms of the input size) if instead the input is just the number n (written in binary), together with lists of snakes and ladders represented as pairs (i, j) giving the numbers of their start and end squares. If it helps, you can let m be the number of ladders plus the number of snakes. Problem 1 (Snakes and Ladders, ). Snakes and Ladders is a classic board game, originating in India no later than the 16th century. The board consists of an n x n grid of squares, numbered consecutively from 1 to n, starting in the bottom left corner and proceeding row by row from bottom to top, with rows alternating to the left and right. Certain pairs of squares, always in different rows, are connected by either "snakes" (leading down) or "ladders" (leading up). Each square can be an endpoint of at most one snake or ladder. An example board is shown in figure 1. 100 99 97 96 94 93 92 91 81 82 8 80 84 85 86 87 89 90 78 77 76 75 74 73 71 61 62 63 64 65 66 68 6 70 58 555 545 52 51 60 41 443 5 46 4 48 49 40 39 38 37 36 35 34 33 32 31 21 22 23 25 6 28 29 30 20 19 8 1 16 514 3 2 11 4 5 5 7 9 10 Figure 1: A typical Snakes and Ladders board. Upward straight arrows are ladders; downward wavy arrows are snakes. You start with a token in cell 1, in the bottom left corner. In each move, you advance your token up to k positions (i.e. from your current square s to any square from s +1 to s+ k), for some fixed constant k (typically 6). If the token ends the move at the top end of a snake, you must slide the token down to the bottom of that snake. If the token ends the move at the bottom end of a ladder, you may move the token up to the top of that ladder. (a) Describe an algorithm to compute the smallest number of moves required for the token to reach the last square of the grid. Don't forget to take into consideration when the last square (b) (c) can not be reached. Analyze the runtime of your algorithm if the board is given explicitly as an n x n grid of squares, each with fields indicating whether they are the start of a snake or ladder and giving the destination if so. Analyze the runtime of your algorithm (in terms of the input size) if instead the input is just the number n (written in binary), together with lists of snakes and ladders represented as pairs (i, j) giving the numbers of their start and end squares. If it helps, you can let m be the number of ladders plus the number of snakes.