COT5405/CIS4930: ANALYSIS OF ALGORITHMS
Exam III
Date: April 18, 2017, Tuesday
Time: 8:20pm { 10:10pm (110 minutes) Professor: Alper Ungor (Oce CSE 534)
This is a closed book exam. No collaborations are allowed. Your solutions should be concise, but complete, and handwritten clearly. Use only the space provided in this booklet, including the even numbered pages. Feel free to refer to algorithms, denitions and concepts discussed in class rather than describing them in detail unless of course you are asked for it specically.
(: GOOD LUCK and HAVE A GREAT SUMMER 🙂
First Name:
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
Last Name:
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
UF ID:
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
Credit
Max
Problem 1
20
Problem 2
30
Problem 3
30
Problem 4
30
TOTAL
110
1. [20 points] Pick One No justication is needed for this problem.
(a) Which one of the following is incorrect for Two Dimensional Range Trees? i. Counting range queries take O(log2(n)) time.
ii. Reporting range queries take O(log2(n) + k) time. iii. Construction time is Θ(n log n).
iv. Space complexity is Θ(n2 log n).
(b) Clique-Degree-4 problem: Given a graph G = (V, E) where all vertices have degree at most 4, and an integer k, determine whether V has a subset S of size at least k that forms a clique in G. Which of the following statement(s) is/are correct?
(a) Clique-Degree-4 is NP-Hard; (b) Clique-Degree-4 is in P; (c) Approximating Clique-Degree-4 is NP-Hard; (d) There exists a polynomial time reduction from Clique-Degree-4 to VertexCover problem.
i. (a) and (d) ii. (b) and (d)
iii. (a) and (c) iv. (b) and (c) v. All of them
(c) Majority-Check problem: Given a set S of n real numbers, determine whether more than half the numbers in S are exactly the same. Assuming two numbers can be com- pared in constant time, which of the following statement(s) is/are correct?
(a) Majority-Check is in NP; (b) There exists no comparison-based algorithm solv- ing MajorityCheck in Θ(n) time; (c) Majority-Check is proven to be NP-hard via a reduction from SubsetSum problem.
i. only (a)
ii. (a) and (b) iii. (a) and (c)
iv. All of them v. None of them
(d) MAX-SAT: Given a CNF (Conjunctive Normal Form) Boolean formula and a positive integer k, does there exist a truth assignment that satises at least k clauses.
Which one of the following is correct about this problem?
i. This problem can be solved in polynomial time since k is a small number.
ii. This problem is NP-hard since it is a special case of the SAT problem.
iii. This problem is NP-hard since it is a generalization of the SAT problem.
iv. This problem can be shown to be NP-hard by giving a reduction from MAX-SAT
to CLIQUE problem.
v. None of the above
3
4
2. [30 points] Geometric Algorithms – Co-Circularity Check
Following procedures each with planar input points and constant running time are provided: CCW(p, q, r) decides if r is leftOf, on, or rightOf the oriented line going through p, q. InCircle(p,q,r,s) decides whether s is inside, on, or outside the unique circle going through p, q, r.
(a) Draw ve points a,b,c,d,e such that the radii of the circles going through triples of points (a,b,c), (a,b,d), and (a,b,e) are all the same, a,b,c,d are co-circular, and yet a, b, c, e are not co-circular, i.e., circumradius(a, b, c) = circumradius(a, b, d) = circumradius(a, b, e), InCircle (a, b, c, d) = on, and InCircle (a, b, c, e) ̸= on.
(b) Given n points in the plane (no three of which are co-linear) we want to determine whether any four of them are co-circular. Naive algorithm would take O(n4) time. Design and analyze an algorithm that solves this problem in O(n3 log n) time. (Hints: Sorting takes O(nlogn) time. Recall the co-linearity checking algorithm.)
5
6
3. [30 points] NP-Completeness – Strongly Independent Sets
Consider a simple graph G = (V, E). A subset S1 ⊆ V is called an independent set, if no two vertices in S1 have an edge (path of length one) between them. A subset S2 ⊆ V is called a strongly independent set, if no two vertices in S2 have a path of length one or two between them,i.e.,∀u,v∈S2,wehave(u,v)∈/E,andw∈V suchthat(u,w)∈Eand(w,v)∈E. IndependentSet Problem: Given a simple graph G and an integer k, determine if G contains an independent set of size at least k.
StronglyIndependentSet Problem: Given a simple graph G and an integer k, determine if G contains a strongly independent set of size at least k.
(a) Draw a connected graph that has an independent set of size 4. Draw another connected graph that has a strongly independent set of size 4.
(b) Prove that StronglyIndependentSet Problem is NP-Complete. (Hints: Indepen- dentSet Problem is NP-hard. For your reduction, consider additional vertices positioned strategically and forming a clique among themselves.)
7
8
4. [30 points] Approximation – Pack your Books, You Got a Job at Google
Imagine that you just graduated UF and got a job at Google. For your move to California, you need to pack all your books to boxes each of which has capacity a real number between 1 and 2. For simplicity, assume that each book has weight a real number between 0 and 1. You want to minimize the number of boxes that you use. More formally:
PackBooks Problem: Given n books with weights w1,…,wn where ∀ i, 0 < wi < 1, m boxes with capacities c1,...,cm where ∀ j, 1 < cj < 2, and an integer k, is it possible to pack all books in at most k boxes such that total weight in each box is within its capacity.
(a) Prove that PackBooks Problem is NP-hard. (Hints: Consider a special case of this problem that you are familiar with. No reduction necessary.)
(b) Design and analyze an approximation algorithm for the minimization version of the PackBooks Problem with an approximation ratio at most 4.
9
10