1. (8 POINTS) For each question below, compare the given pairs of functions f(n) and g(n). In each case, determine how the two functions compare to one another using O(), ⌦(), or ⇥() as n grows very large.
For each, clearly circle the best answer. (No partial credit will be awarded.) (a) f(n) = n! and g(n) = 2n
i. f = O(g) ii. f = ⌦(g) iii. f = ⇥(g)
iv. None of the above
(b) f(n) = 2n+1 and g(n) = 2n
i. f = O(g) ii. f = ⌦(g) iii. f = ⇥(g)
iv. None of the above
(c) f(n) = 5log2 n and g(n) = n1/2
i. f = O(g) ii. f = ⌦(g) iii. f = ⇥(g)
iv. None of the above
(d) f(n) = n2n and g(n) = 3n
i. f = O(g) ii. f = ⌦(g) iii. f = ⇥(g)
iv. None of the above
2
2. (6 POINTS) We want to describe how many times an exclamation mark (!) is printed by the pseudocode below.
function f(n)
{
if n > 1 then {
print “!”
f(n/2)
f(n/2)
} }
(a) Define a recurrence relation T(n) for the given pseudocode that represents the number of times an exclamation mark is printed out.
T(n) =
(b) Solve the recurrence relation from part (a). In other words, remove any and all recur- sive T () terms from the right-hand side.
T(n) =
(c) If f(n/4) replaced each f(n/2) call in the given pseudocode, again define relation T (n) for the number of times an exclamation mark is printed out. As with part (b) above, remove any and all recursive T () terms from the right-hand side.
T(n) =
3
3. (6 POINTS) Draw a directed graph with two strongly connected components and at least six vertices for which it is impossible to add one edge and make the graph strongly connected.
For all graph-related questions, no self-loops or multi-edges are allowed. In other words, all edges have distinct endpoint vertices.
4. (10 POINTS) Given an undirected graph G = (V, E), let Vodd ✓ V contain all vertices with odd degree. Show that we can always find a way to pair up all vertices of Vodd so that the paths between each such pair of vertices have no edges in common. Note that these paths may share vertices (but not edges).
For all graph-related questions, no self-loops or multi-edges are allowed. In other words, all edges have distinct endpoint vertices.
4
5. (8 POINTS) Professor F. Lake claims that if {u, v} is an edge in an undirected graph and during a DFS post(u) < post(v), then vertex v is an ancestor of vertex u in the DFS tree. Either prove this claim to be true or show that this claim is not possible. For all graph-related questions, no self-loops or multi-edges are allowed. In other words, all edges have distinct endpoint vertices. 6. (8 POINTS) What is the maximum number of colors needed to color an undirected graph with exactly one odd-length cycle? Remember that to color a graph is to assign colors to its vertices such that adjacent vertices do not have the same color. In your answer, also describe how you would color such a graph. For all graph-related questions, no self-loops or multi-edges are allowed. In other words, all edges have distinct endpoint vertices. Maximum number of colors needed: Describe how to achieve this solution for any graph G = (V, E): 5 7. (8 POINTS) When multiple shortest paths exist in a given graph, Dijkstra’s shortest path algorithm arbitrarily finds one of these shortest paths. In such cases, the most convenient of these paths is often the path with the fewest number of edges (e.g., fewest number of layovers for a series of flights). In this problem, you are asked to extend Dijkstra’s algorithm to also calculate the fewest number of edges in each shortest path from a start vertex s. More specifically, for each vertex u in a given graph, define: best[u] = minimum number of edges in a shortest path from s to u Rewrite Dijkstra’s algorithm (e.g., from Figure 4.8 of DPV) with the above addition. Be sure to define the inputs, the outputs, the modified pseudocode, and the runtime of your algorithm. Assume that makequeue(), deletemin(), and decreasekey() operations are already given. For all graph-related questions, no self-loops or multi-edges are allowed. In other words, all edges have distinct endpoint vertices. 6 8. (8 POINTS) Given a connected undirected graph G = (V,E) as input, describe a linear- time O(|V |) algorithm to determine if there is an edge that can be removed from G that still leaves G connected. Your algorithm merely needs to output either true or false (so do not attempt to identify the specific edge). In your answer, be sure to show the input, the output, and the runtime of your algorithm, as well as a brief description of the algorithm itself. For all graph-related questions, no self-loops or multi-edges are allowed. In other words, all edges have distinct endpoint vertices. 7 9. (12 POINTS) Professor F. Lake has two new claims, shown below. For each claim, either prove the claim to be true or disprove the claim by describing a simple counterexample or contradiction. For all graph-related questions, no self-loops or multi-edges are allowed. In other words, all edges have distinct endpoint vertices. (a) The shortest path between two vertices u and v is always part of a minimum spanning tree. (b) First, for any m > 0, define an m-path to be a lightweight path with edge weights wi < m. The claim is that if graph G = (V, E) contains an m-path from vertex s to vertex t, then every minimum spanning tree of G must also contain an m-path from vertex s to vertex t. 8 10. (18 POINTS) Given a rectangular sheet of metal with dimensions H ⇥ V , where H and V are both positive integers, we are also given a list of n products that can be made from the sheet metal. For each product i = 1, 2, . . . , n, we know that an hi ⇥ vi rectangle is required to make the product and that the selling price for the product is ci. For all i, note that hi, vi, and ci are all positive integers with hi H and vi V . The machine used to cut the sheet metal is limited in that it can only cut a rectangular piece into two smaller pieces by cutting either horizontally or vertically. Use dynamic programming to develop an algorithm that determines the set of products we can make that will maximize the sum of the costs ci. Note that we can make as many copies of the same product as we would like. And we do not need to make all n possible products. Be sure to describe the subproblems, the recurrence relation, the order in which subproblems must be solved, how a solution is determined, and the runtime of your algorithm. 9 11. (8 POINTS) We define a new problem called the Intersect Every Set (IES) Problem as follows. Given a family of n sets {S1,S2,...,Sn} and a budget b, we wish to find a set I of size s b that intersects every set Si, if such an I exists. More specifically, we wish to find a setI suchthatI\Si 6=;foralli. Show that the IES Problem is in class NP-complete. As a hint, consider modeling this problem using a graph and remember that to show a problem is in class NP-complete, we must show a polynomial-time reduction from a known NP-complete problem to the new problem. 10