Microsoft Word – Fall15_Exam3_soln.doc
CS570
Analysis of Algorithms
Fall 2015
Exam III
Name: _____________________
Student ID: _________________
Email Address:________________
_____Check if DEN Student
Maximum Received
Problem 1 20
Problem 2 15
Problem 3 12
Problem 4 15
Problem 5 15
Problem 6 12
Problem 7 11
Total 100
Instructions:
1. This is a 2-hr exam. Closed book and notes
2. If a description to an algorithm or a proof is required please limit your description or
proof to within 150 words, preferably not exceeding the space allotted for that
question.
3. No space other than the pages in the exam booklet will be scanned for grading.
4. If you require an additional page for a question, you can use the extra page provided
within this booklet. However please indicate clearly that you are continuing the
solution on the additional page.
1) 20 pts
Mark the following statements as TRUE, FALSE. No need to provide any
justification.
If P = NP, then all NP-Hard problems can be solved in Polynomial time.
Dynamic Programming approach only works when used on problems with non-
overlapping sub problems.
In a divide & conquer algorithm, the size of each sub-problem must be at most half
the size of the original problem.
In a 0-1 knapsack problem, a solution that uses up all of the capacity of the knapsack
will be optimal.
If a problem X can be reduced to a known NP-hard problem, then X must be NP-
hard.
If SAT ≤P A, then A is NP-hard.
The recurrence , has solution
Consider two positively weighted graphs and with
the same vertices and edges such that, for any edge , we have
For any two vertices , any shortest path between u and
v in is also a shortest path in .
If an undirected graph G=(V,E) has a Hamiltonian Cycle, then any DFS tree in G has
a depth |V| – 1.
Linear programming is at least as hard as the Max Flow problem.
2) 15 pts
A company makes three models of desks, an executive model, an office model and a
student model. Building each desk takes time in the cabinet shop, the finishing shop
and the crating shop as shown in the table below:
Type of desk Cabinet shop Finishing shop Crating shop Profit
Executive 2 1 1 150
Office 1 2 1 125
Student 1 1 .5 50
Available hours 16 16 10
How many of each type should they make to maximize profit? Use linear programming
to formulate your solution. Assume that real numbers are acceptable in your solution.
3) 12 pts
Given a graph G=(V, E) and a positive integer k < |V|. The longest-simple-cycle
problem is the problem of determining whether a simple cycle (no repeated vertices)
of length k exists in a graph. Show that this problem is NP-complete.
4) 15 pts
Suppose there are n steps, and one can climb either 1, 2, or 3 steps at a time.
Determine how many different ways one can climb the n steps. E.g. if there are 5
steps, these are some possible ways to climb them: (1,1,1,1,1), (1,2,1,1), (3, 2), (2,3),
etc. Your algorithm should run in linear time with respect to n. You need to include
your complexity analysis.
5) 15 pts
We'd like to select frequencies for FM radio stations so that no two are too close in
frequency (creating interference). Suppose there are n candidate frequencies
{f1,…fn}. Our goal is to pick as many frequencies as possible such that no two
selected frequencies fi, fj have |fi-fj|