Homework 3: Dynamic and Greedy Programming

Note: ^ means “raise to the power”.

1.(4 points) Use your own words to illustrate in what scenarios we should use greedy algorithm or dynamic programming. Please give examples of when each paradigm works. (For example, we can apply dynamic programming on rod cutting, greedy algorithm cannot work here because rod cutting needs to use sub-rob-cutting cases to calculate final result. Use example outside course material or try to illustrate in general way)

Sample Answer: For example, we can apply dynamic programming on rod cutting, greedy algorithm cannot work here because rod cutting in one place can prevent us from taking the optimal solution in another place. For instance, if we cut an 8-foot rod in half, we can't make a 5-foot cut if that turns out to be better.

2. (2 points) Greedy algorithms are also used widely in memory management. Given a list of blocks, in which the sizes are { 100, 150, 180, 200, 300 }, how would a greedy algorithm (grab the smallest block that works first) fit processes with sizes {10, 222, 198, 147, 178 }?

a. process 1: block 1, process 2: block 2, process 3: block 4, process 4: block 3, process 5: block 5

b. process 1: block 1, process 2: block 5, process 3: block 4, process 4: block 3, process 5: block 2

c. process 1: block 5, process 2: block 2, process 3: block 4, process 4: block 3, process 5: block 1

d. process 1: block 1, process 2: block 5, process 3: block 4, process 4: block 2, process 5: block 3

Answer: d. process 1: block 1, process 2: block 5, process 3: block 4, process 4: block 2, process 5: block 3

3.(2 points) Which of the following is/are property/properties of a dynamic programming problem?

a. Optimal substructure

b. Overlapping subproblems

c. Greedy approach

d. Both optimal substructure and overlapping subproblems

Answer: d. Both optimal substructure and overlapping subproblems

4. (2 points) If a problem can be broken into subproblems which are solved several times, the problem possesses ____________ property.

a. Overlapping subproblems

b. Optimal substructure

c. Memoization

d. Greedy

Answer: a. Overlapping subproblems

Reason: In computer science, a problem is said to have overlapping subproblems if the problem can be broken down into subproblems which are reused several times or a recursive algorithm for the problem solves the same subproblem over and over rather than always generating new subproblems

5. (1 point) When dynamic programming is applied to a problem with overlapping subproblems, the time complexity of the resulting program typically will be significantly less than a straightforward recursive approach.

Answer: True

Reason: The overlapping subproblems are not solve again and again. We follow a memozied approach which result in a memory-time trade-off. It results in reducing the complexity of the algorithm to a very large extent

6. (2 points) In dynamic programming, the technique of storing the previously calculated values is called ___________

a. Saving value property

b. Hashing

c. Memoization

d. Mapping

Answer: c. Memoization

Reason: It memorizes or stores the results for subproblems.

7. (4 points) Modify MEMOIZED-CUT-ROD from the textbook to return not only the value but the actual solution too.

Answer:

EXTENDED-BOTTOM-UP-CUT-ROD(p,n)

1.  let r[0..n] and s[0..n] be new arrays

2.  r[0] = 0

3.  for j = 1 to n

4.     q = -INF

5.     for i = 1 to j

6.        if q < p[i] + r[j-i]

7.           q = p[i] + r[j-i]

8.           s[j] = i

9.     r[j] = q

10. // Print optimal cuts

11. i = n

12. while i > 0

13.    print s[i]

14.    i = i - s[i]

15. return r and s

8. (4 points) Describe the Huffman encoding that will deal with the following letters and their corresponding frequencies.

(g, 6), (d,13), (f,17), (b,18), (c, 29), (e, 30), (a, 37)

Answer:

IMG_20171018_144946325.jpg

(It’s not necessary to draw a tree although it is preferable)

a        -> 10

b         -> 011

c         -> 111

d         -> 1101

e         -> 00

f         -> 010

g         -> 1100

9. (2 points) Huffman’s algorithm is a greedy algorithm because:

a. The frequencies are combined at each step

b. The two smallest probability nodes are chosen at each step

c. It involves drawing a Huffman tree

d. Both a and c.

Answer: b. The two smallest probability nodes are chosen at each step

Explanation: Satisfies greedy property.

10. (2 points) A thief enters a store and sees the following items: Bag A worth $100 weighing 2 pounds, Bag B worth $10 weighing 2 pounds and Bag C worth $120 weighing 3 pounds. His Knapsack holds 4 pounds. What is his maximum profit according to the Fractional Knapsack Problem?

a. 120

b. 195

c. 180

d. None of the above

Answer: c. 180

Explanation: In the Fractional Knapsack problem, the item with the maximum ‘by weight’ profit is chosen first. In this case the maximum ‘by weight’ profit is obtained by choosing Bag A (100/2 is equal to 50).

Current Profit: 100

Bag A weighs 2 pounds so there are 2 more pounds remaining in the Knapsack. The next maximum ‘by weight’ profit is Bag C (120/3 is equal to 40). So we take 2 pounds of Bag C.

Final profit: 100+(2*40) = 180

11. (2 points) You are building up a new housing subdivision (community / neighborhood). You have picked out a series of good house sites 1 kilometer apart from each other. However, zoning regulations in this very rural area require that each house be 4 kilometers from any other house. Given you have a list, r, of the revenue you expect from each site (they differ because of the view!), what is the recurrence relation you should use to pick out the maximum revenue you can expect from the entire development?

a. T(n) = r-sub-n + T(n - 4)

b. T(n) = max(r-sub-n, T(n - 4))

c. T(n) = max(r-sub-n + T(n - 4), T(n - 1))

d. T(n) = max(r-sub-n + T(n - 1), T(n - 4))

Answer: c. T(n) = max(r[n] + T(n - 4), T(n - 1))

Reason: Because it accurately captures the problem!

12. (4 points) The Lucas series is similar to the Fibonacci series, except that its base cases are L(0) = 2 and L(1) = 1. Please write memoized code for computing the n-th Lucas number. (Pseudo-code is fine here, but you can also write code in any common language like C, Java, Python, Ruby, etc.)

Answer:

Just like memo_fib, except for 0 we return 2, and 1 we return 1.

def memo_fib(n, first_call=True):

   """

       A memo-ized version of naive fib, that runs much faster.

       Args:

           n: the fibonacci number to return

           first_call: Is this the top-level call to this function?

       Returns:

           The n-th fibonacci number.

   """

   global ops

   global results

   if first_call:

       ops = 0  # make sure we don't count some other call's operations!

       results = [-1 for x in range(1000)]


   if n < 0:

       print("n must be >= 0!")

       return -1

   elif n == 0:

       ops += 1

       return 0

   elif n == 1:

       ops += 1

       return 1

   else:

       # Here we check and see if we have calculated the results

       # we need earlier. If so, use them. If not, calculate and

       # then store ("memo-ize") them.

       n_minus_one = 0

       n_minus_two = 0

       if results[n - 1] >= 0:

           ops += 3  # if, assignment, and subtraction

           n_minus_one = results[n - 1]

       else:

           ops += 5  # two assignments, two subtractions, function call

           n_minus_one = memo_fib(n - 1, False)

           results[n - 1] = n_minus_one

       if results[n - 2] >= 0:

           ops += 3  # if, assignment, and subtraction

           n_minus_two = results[n - 2]

       else:

           ops += 5  # two assignments, two subtractions, function call

           n_minus_two = memo_fib(n - 2, False)

           results[n - 2] = n_minus_two


       ops += 1

       return n_minus_one + n_minus_two

13. (4 points) Suppose you were to drive from St. Louis to Denver along I-70. Your gas tank, when full, holds enough gas to travel m miles, and you have a map that gives distances between gas stations along the route. Let d1 < d2 <...  < dn be the locations of all the gas stations along the route where d-sub-i is the distance from St. Louis to the gas station. You can assume that the distance between neighboring gas stations is at most m miles. Your goal is to make as few gas stops as possible along the way.

Give the most efficient algorithm you can find to determine at which gas stations you should stop and prove that your strategy yields an optimal solution. Be sure to give the time complexity of your algorithm as a function of n.

(Pseudo code expected.)

Answer:         

Screen Shot 2017-10-19 at 11.55.20 PM.png

                                

14. (2 points) An example of set of coin denominations for which the greedy algorithm does not yield an optimal solution is {_________________}.

Answer: { 1, 3, 4 } for 6 as change amount with minimum number of coins

It will give the answer 4 + 1 + 1

Whereas the correct answer is 3 + 3

Note: The answer for this question may differ from person to person.

15. (3 points) Explain why the time complexity of Huffman coding is O(n lg n) (this could be a full formal proof, but a good intuitive explanation is sufficient)?

Answer: For each of n items we do at most lg n operations to get it at the right place in the tree.