CS 215 Homework 5

1. What is the idea of clustering? Explain how single-link clustering is similar to Kruskal's greedy MST algorithm. Describe one real-world application of clustering. Include citation(s) for any online reference(s) you use.

2. Mylar the robot has a simple life. Its sole purpose is to navigate from the top row of an NxN grid to the bottom row, while consuming as little fuel as possible. Mylar is able to choose its starting column. At each time step, it can select from one of three possible actions: move straight down, or move diagonally down left or right:

   

   If Mylar ever attempts to step off the left or right edge of the grid, it reappears in the appropriate location on the opposite side.

   Complicating Mylar's life is the fact that there may be a different fuel cost associated with traversing each cell in the grid. Here is an example grid along with the optimal sequence of decisions (with a total fuel cost of 5):

   

   Your goal is to develop a dynamic programming algorithm that Mylar can use to solve this problem. You should provide an English language description, clear pseudocode (or well-documented code), and a performance analysis. The input to the algorithm is the NxN grid of numbers. The output of the algorithm should be the total fuel usage; you do not need to return the path itself.

3. Describe a real-world application of the Knapsack problem. Include citations for any online source(s) you use.
4. Suppose we have a solution to the n-Queens problem instance in which n = 4. Can we extend this solution to find a solution to the problem instance in which n = 5? Can we then use the solution for n = 4 and n = 5 to construct a solution to the instance in which n = 6 and continue this dynamic programming approach to find a solution to any instance in which n > 4? Justify your answer.
5. Find at least two instances of the n-Queens problem that have no solutions.