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.
[/FALSE ]
If P = NP, then all NP-Hard problems can be solved in Polynomial time.
[/FALSE ]
Dynamic Programming approach only works when used on problems with non-overlapping sub problems.
[/FALSE ]
In a divide & conquer algorithm, the size of each sub-problem must be at most half the size of the original problem.
[/FALSE ]
In a 0-1 knapsack problem, a solution that uses up all of the capacity of the knapsack will be optimal.
[/FALSE ]
If a problem X can be reduced to a known NP-hard problem, then X must be NP-hard.
[ TRUE/]
If SAT ≤P A, then A is NP-hard.
[ TRUE/]
The recurrence
[/FALSE ]
, 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 .
[/FALSE ]
If an undirected graph G=(V,E) has a Hamiltonian Cycle, then any DFS tree in G has a depth |V| – 1.
[ TRUE/]
Linear programming is at least as hard as the 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 Executive 2
Office 1
Student 1
Available hours 16
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.
Solution:
Start by defining your variables:
x = number of executive desks made y = number of office desks made
z = number of student desks made
Maximize P=150x+125y+50z. Subject to:
2x + y + z ≤ 16 cabinet hours x + 2y + z ≤ 16 finishing hours x + y + .5z ≤ 10 crating hours x≥0, y≥ 0, z≥ 0
Finishing shop
1
2
1 .5 50 16 10
Crating shop Profit 1 150
1 125
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.
Solution:
Clearly this problem is in NP. The certificate will be a cycle of the graph, and the certifier will check whether the certificate is really a cycle of length k of the given graph.
We will reduce HAM-CYCLE to this problem. Given an instance of HAM-CYCLE with graph G=(V,E), construct a new graph G’=(V’, E) by adding one isolated vertex u to G. Now ask the longest-simple-cycle problem with k = |V| <|V’| for graph G’. If there is a HAM-CYCLE in G, it will be a cycle of length k = |V| in G’.
If there is no HAM-CYCLE in G’, there must not be no cycle of length |V| in G’. If there is, we know the cycle does not contain u, because it is isolated. So the cycle will contain all vertex in |V|, which is a HAM-CYCLE of the G.
The reduction is in polynomial time, so longest-simple-path 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.
Solution:
Let 𝑇(𝑛) denote the number of different ways for climbing up 𝑛 stairs.
There are three choices for each first step: either 1, 2, or 3. T(n)= T(n-1)+ T(n-2)+ T(n-3) The boundary conditions :
when there is only one step, 𝑇(1) = 1 . If only two steps, 𝑇(2) = 2 . T(3)= 4. ((1,1,1), (1,2), (2,1), (3))
Pseudo code as below:
if n is 1
return 1 else if n is 2
return 2 else
T[1] = 1
T[2] = 2
T[3]=4
for i = 4 to n do
T[i] = T[i-1]+T[i-2]+ T[i-3] return T[n]
The time complexity is Θ(𝑛) .
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|