1.Coin Collection The Coin Collection problem is defined as follows: Several coins are placed on an n m board with at most one coin per cell of the board. A robot is initially located at the upper left cell of the board. The robot can only move to the right or down; it can not move up or left. When the robot visits a cell where a coin is located, it picks it up. At most, how many coins can the robot collect? This problem can be solved by the following method: void RobotCoin ( i n t n , i n t m, // s i z e of the board i n t C [ n ] [ m] // Is there a coin in ( i , j ) ) { i n t F [ n ] [ m ] ; //How many coins can be c o l l e c t e d while on ( i , j ) F [ 0 ] [ 0 ] = C [ 0 ] [ 0 ] ; f o r ( i n t k =1; k

2. Knapsack The Knapsack problem aims at finding the best set of objects to pack in a bag. Often the following dynamic programming algorithm is used to solve the problem. void k n a p s a c k ( i n t n , i n t W, i n t v a l u e [ ] , i n t w e i g h t [ ] , i n t v a l [ ] [ ] ) { f o r ( i n t a = 0 ; a<=W; ++a ) { v a l [ 0 ] [ a ] = 0 ; } f o r ( i n t i =1; i <=n ; ++i ) { f o r ( i n t j =0; j<=W; ++j ) { v a l [ i ] [ j ] = v a l [ i 1 ] [ j ] ; i f ( w e i g h t [ i 1] <= j ) { v a l [ i ] [ j ] = max ( v a l [ i 1 ] [ j ] , v a l u e [ i 1]+ v a l [ i 1 ] [ j w e i g h t [ i 1 ] ] ) ; } } } } (You can assume weight is positive.) Question: What is the complexity of this function? Question: Extract the dependencies. Question: What is the width? Question: What is the work? Question: What is the critical path? What is its length?

3.Bubble Sort The bubble sort algorithm can be written like this: void b u b b l e s o r t ( i n t A, i n t n ) { f o r ( i n t i =0; i