Exercise 1


a) What claim about dynamic programming is not correct? Dynamic programming... 
    ...combines solutions of subproblems to solve a problem.
    ...can solve problems with less work than a divide-and-conquer-algorithm.
    ...can not be used together with recursion.
    ...is often used on optimization problems.
 
b) Which of these problems is most suitable for dynamic programming?
    Find an element which occurs more than once in a list of n integers between 1 and n-1.
    Sort a list of n integers between 1 and n^2.
    Find the n'th Fibonacci-number.
    Find the element in a binary search tree which has value closest to a given value.
 
c) Is it so that for all optimization problems that the optimal solution of an instance of the problem is put together by optimal solutions of suminstances?
    Yes
    No




Exercise 2

In this exercise we are going to look at a rectangular grid given as follows:

(figure)

We are now going to find how many paths there are from the point Start (point [1, 1]) to the point Mål (point [m, n]) following some simple rules.
A legal path from Start to Mål is defined such that steps from point [i, j] on the path must either go to point [i+1, j] or to the point [i, j+1]. Two paths are different if they are not identical, step by step.
The function T(i, j) gives the number of paths from point [1, 1] to point [i, j]. E.g. T(1, 2) = 1 and T(3, 2) = 3.

a) What is T(1, 5)?
    1  2  3  4  5

b) What is T(5, 3)? (It is wise to find a system to answer this question)
    8  10  12  15  18

c) Find an expression which makes it possible to compute T(m, n). T(m, n) = ?
    T(m-1, n-1) + 2
    T(m-1, n) + T(m, n-1)
    MAX{ T(m-1, n), T(m, n-1)} + 1
    m^2 + n^2 - m*n
    T(m-1, n) + T(m, n-1) + T(m-1, n-1)




Exercise 3

The knapsack problem:
Given n elements with weights w1, ..., wn and values v1, ..., vn and a sack with capacity W, find the most valuable combination of elements which can be roomed by the sack. V is thus the total value of this
combination.

What is V given

a) W = 5
   v1 = 12, v2 = 10, v3 = 20, v4 = 15
   w1 = 2, w2 = 1, w3 = 3, w4 = 2
    32
    35
    37
    47

b) W = 740
   v1 = 18, v2 = 27, v3 = 51, v4 = 36, v5 = 24, v6 = 22, v7 = 29, v8 = 10, v9 = 24, v10 = 40
   w1 = 320, w2 = 301, w3 = 371, w4 = 296, w5 = 303, w6 = 359, w7 = 148, w8 = 275, w9 = 296, w10 = 395
    78
    87
    89
    93

c) Same as b), but with W = 720
    78
    87
    89
    93