1.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) (4.0 Points)
Answer:
Greedy Algorithms
Are used to make a locally optimal choice at each stage with the hope of finding a global optimum.In many problems, a greedy strategy does not, in general, produce an optimal solution, but nonetheless, a greedy heuristic may yield locally optimal solutions that approximate a global optimal solution in a reasonable time.We can make whatever choice seems best at the moment and then solve the subproblems that arise later. The choice made by a greedy algorithm may depend on choices made so far but not on future choices or all the solutions to the subproblem. It iteratively makes one greedy choice after another, reducing each given problem into a smaller one.
Dynamic Programming:
It is a bottom-up approach where the subproblems are solved first, then combining the outputs of the subproblems generate solution to the overall problem. The dynamic approach focusses on solving the subproblems once and storing the solution to the subproblem in an array so that if in case the same subproblems come up in the future, there won't be a need to solve it again. It is called memoization.After every stage, dynamic programming makes decisions based on all the decisions made in the previous stage, and may reconsider the previous stage's algorithmic path to solution. Two main properties of a problem suggest that the given problem can be solved using Dynamic Programming. These properties are overlapping sub-problems and optimal substructure
Examples:
Greedy Algorithm:
A problem statement where you are given a certain amount of dollars to spend and you have to buy the maximum number of pens with that amount. Consider a problem which consists of 7 types of pens with the costs: 20, 10, 30, 15, 25, 5, 12 and the amount you are being given to spend is 50$. Here the greedy approach will be to sort the prices of pens and then choose amongst them.
Step 1: Sort the costs
Sorted Costs: 5, 10, 12, 15, 20, 25, 30
Step 2: Start picking pens till you run out of money
After choosing 5, the amount left is 50-5 = 45
After choosing 10, the amount left is 45-10 = 35
After choosing 12, the amount left is 35-12 = 23
After choosing 15, the amount left is 23-15 = 8
The next pen has a cost of 20 but cannot be chosen as there are only 8$ left.
So the maximum number of pens that I can buy with 50$ is 4.
Dynamic Programming:
Modified Fibonacci is an example of Dynamic Programming. In Fibonacci , to calculate fibo(n) we have to calculate fibo(n-1) and fibo(n-2). Here the overlapping sub-problems property comes into picture as we have to calculate subproblems multiple times which are overlapping also optimal substructure property is used as we need to find optimal answers for all the sub-fibo's. Consider calculating fibo(5) where we will first need to find fibo(4) and fibo(3). Now to calculate fibo(4) we have to calculate fibo(3) and fibo(2) and to calculate fibo(3) we have to calculate fibo(2) and fibo(1). Here as we see, we are calculating fibo(3), fibo(2) and fibo(1) multiple times. So using memoiztion, we can create an array where we store all the fibo values as we come across so that there is no need to calculate the fibo of any number multiple times.
2.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 }? (2.0 Points)
- 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
3.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
4.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
5.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 straight-forward recursive approach.
A. True
B. False
6.In dynamic programming, the technique of storing the previously calculated values is called ___________
- A.Saving value property
- B.Hashing
- C.Memoization
- D.Mapping
7.Modify MEMOIZED-CUT-ROD from the textbook to return not only the value but the actual solution too.
Answer:
def cut_rod_bottom(price, n, revenue, rod_length):
if revenue[n] >= 0: #base case
return revenue[n]
revenue[n] = 0
for i in range(1, n + 1):
q = price[i] + cut_rod_sub(price, n - i, revenue, rod_length)
if q>revenue[n]:
rod_length[n] = i
revenue[n] = q
return revenue[n]
def cut_rod(price, n):
rod_length = [i for i in xrange(n + 1)] #This stores the different lengths of rod in which it can be cut
revenue = [-1 for _ in xrange(n + 1)] #It will act as a cache so that there is no need to calculate the same value multiple times
cut_rod_bottom(price, n, revenue, rod_length) #Returns the maximized price
revenue = revenue[n] #Revenue variable is now allocated the maximized price value
cuts = [] #Keeps a track of the cuts which maximizes the value
while n > 0:
cuts.append(s[n])
n -= rod_length[n]
return cuts,revenue
price = [2,5,7,8]
n = 5
print(cut_rod(price,n))
Output:
([1,2,2],12)
Here the output will be a tuple where the first value will be a list containing the lengths in which the rod needs to be cut and second value will be the maximized price for the specified length of the rod.
8.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)
The basic idea behind Huffman coding algorithm is to use fewer bits for more frequently occurringcharacters. Huffman coding algorithm compresses the storage of data using variable length codes. Each character takes 8 bits for representation. When reading a file, generally system reads 8 bits at a time to read a single character. But this coding schemeis inefficient. The reason for this is that some characters are more frequently used than other characters. Let's say that the letter 'e' is used 10 times more frequently than letter 'q'. It would then be advantageousfor us to use a 7-bit code for 'e' and a 9-bit code for 'q' instead because that could reduce our overall message length.
Note: I have explained the example in the following images.
So the Huffmancodes for the letters are:
G: 0110
D: 0111
F: 110
B: 111
C: 010
E: 11
A: 00
9.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.
10.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
11.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?
Answer:
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))
12.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.)
def lucas(n, temp):
if n == 0:
temp[n] = 2
if n == 1:
temp[n] = 1
if temp[n] == None:
temp[n] = fibo(n-1,temp) + fibo(n-2,temp)
return temp[n]
n = raw_input("Enter the number whose lucas series is to be calculated").split()
temp = [None]*n #Temporary array to cache all the fibo's calculated
answer = lucas(n,temp)
print('Lucas Series is : ',answer)
13.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 .... 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:
We can use Greedy Algorithm by going to as farthest gas station as we can before the gas runs out. As soon as we reach that gas station, we can refill the gas and continue the process again till we reach our destination.
Pseudocode:
current position = source;
while (current_position < destination)
continue till the position on which car will run out of gas.
if (that position < destination) then
find closest gas station before reaching that position.
fill up gas at that station.
current position = that gas station
else
current position = end position;
Time Complexity: O(n)
14.An example of set of coin denominations for which the greedy algorithm does not yield an optimal solution is {_________________}.
Answer:
Consider a setof denominations : [7,5,1]
If we need the sum to be 10$ with minimum coins used, our greedy algorithm will give us the answer to be 4 coins(1 coin of 7 and 3 coins of 1) but the efficient solution will be 2 coins (2 coins of 5)
15.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:
In Huffman coding, we need to maintain a min heap to retrieve minimum values which will take the time complexity of O(log n) for build_heap. Also, it takes O(n) to traverse all the nodes at least once hence the time complexity of Huffman coding is O(nlogn). Also, for choosing the two minimum nodes with the least frequencies we use heap data structure. This is done N-1 times. Total work for this part is O(n log n). Addition of each parent node and connecting it with the children node will take constant time per node. Work for this part is O(n). Hence the total time complexity is O(n log n)