This is a closed book exam, but you may use one page of prepared notes. Answer all of the questions.
Describe the main ideas behind greedy algorithms.
What problem does Dijkstra's algorithm solve?
What problem does Prim's algorithm solve?
A vertex cover of an undirected graph G is a set S of vertices such every edge in G has at least one of its endpoints in S. The vertex cover problem is: Given an undirected graph G, find a vertex cover of G that has the smallest possible size. That is, find a set of as few vertices as possible such that every edge hits at least one of the vertices in this set. The following is a proposed algorithm for the vertex cover problem. It uses the notion of the degree of a vertex, which is the number of edges that hit this vertex.
A vertex cover needs to cover all of the edges, where an edge is covered by choosing a vertex from that edge. This algorithm is based on the principle that, by choosing a vertex with the most edges hitting it, we get cover the most edges.
What kind of algorithm is this? Is it guaranteed to find the smallest vertex cover? If so, why? If not, give a counterexample.
What are the main principles of dynamic programming algorithms? That is, what characteristics do they share?
Dynamic programming algorithms are usually based on recursive equations. Why don't dynamic programming algorithms simply use recursion to implement those equations directly?
Consider the definition
h(0) = 1
h(n) = h(n-1) + h(floor(n/2)) + 1
For example, h(2) = h(1) + h(1) + 1 = 3, h(3) = h(2) + h(1) + 1 = 5, etc.
An obvious algorithm to compute h is a recursive one, based directly on
the defining equations. Is that algorithm efficient? Why or why not?
If not, how can the algorithm be improved?
Justify your answer.
There are several variants of a problem called the Knapsack Problem. One variant is as follows. The input is a list of positive integers x1, ..., xn, and another positive integer K. You would like to select some of the numbers x1, ..., xn so that their sum is as large as possible, without exceeding K. For example, if the list is 3,10,4,6,8, and K = 19, you can select 3, 10 and 6, for a sum of exactly 19. Think of these as the weights of items that you want to put into a knapsack, where the knapsack can only hold a total weight of K. You want to put as much into the knapsack as possible without overfilling it.
A convenient way of indicating which numbers to choose it to give an index set I, telling the indices of the values in the list to take. For example, if you want to take the first, third and fourth numbers, the index set is {1,3,4}. If I is an index set, define S(I) to be the sum of all xi for i in I. For example, if I is {1,3,4}, then S(I) is x1 + x3 + x4. The Knapsack Problem is to find an index set I that is a subset of {1, ..., n} such that S(I) is as large as possible, subject to the constraint that S(I) is no larger than K.
For w = 0, ..., K and j = 0, ..., n, let Wj, w be 1 if there is an index set I that is a subset of {1, ..., j} such that S(I) = w, and let Wj, w be 0 otherwise. In the case where j = 0, I is required to be empty. Put another way, Wj, w tells you whether it is possible to get a sum of exactly w if you are only allowed to choose from among the first j numbers in the list x1, ..., xn.
Write recursive equations that define Wj, w for j = 0, ..., n and w = 0, ..., K. You can use operators and and or, which take the logical and an logical or of values, treating 0 as false and 1 as true. Your algorithm will need to use the values x1, ..., xn.
The Weak Knapsack Problem does not ask for the subset I itself, but just for S(I), the largest amount that can be put into the knapsack without overfilling it. Describe an algorithm that solves the Weak Knapsack Problem in time O(nK). Assume that arithmetic and logical operations take constant time.