Algorithms Ph.D Qualifier

You have 60 minutes to complete this exam.

Please use the test paper for your work.

Do not put your name anywhere on this paper. Enter your exam code number here: .

Answer all questions below. You must show all work!

I 1.(10) Let f(n) = n2 and g(n) = n lg n. Indicate by writing “yes” or “no” if f(n) is O, o, Ω, ω, Θ of g(n) by filling in the table below.

f(n) / g(n) / O / o / Ω / ω / Θ
n2 / n lg n
  1. (10) Solve the recurrence below for an exact solution.

T(n) = 3T(n-1) +4T(n-2), T(0) = 0, T(1) = 5

T(n) = ______

3. (10) Explain the difference between NP-completeness and NP-hardness. Can you give an example of a problem that is NP-hard but not believed to be in NP?

4. (10) Use the master theorem to give asymptotically tight upper bounds for T(n). Show your work.

T(n) = 6T(n/4) + n2

5. (5) Suppose that algorithms A1 and A2 have worst case time bounds of p and q, respectively. Suppose that algorithm A3 consists of applying A2 to the output of A1. (The input to A3 is the input to A1. Give a worst case time bound for A3.

6. (10) Write an algorithm to determine whether a graph G = (V,E) is 2-colorable. The algorithm should run in O(n + m) time where n = |V| and m = |E|.

II.(30) In this section, there are 10 TRUE/FALSE questions each worth 3points.

Please circle one of (T)rue or (F)alse.

T F 1.Let f(n) and g(n) be asymptotically nonnegative functions. Then min(f(n), g(n)) = Θ(f(n) + g(n))

T F 2.Θ(.), Ω(.), and O(.), all have symmetry property (e.g. f(n) = Θ(g(n)) if and only if g(n) = Θ(f(n)) ).

T F 3.P  NP is a known fact.

T F 4.If (L  NP) is a language such that L' ≤P L for some L'  NP-complete then L is NP-complete.

T F 5.If the CLIQUE problem can be solved in polynomial time, most of the problems in NP (but not all) can be solved in polynomial-time.

T F 6.NP-Completeness is defined over decision problems only.

T F 7.If a language L is accepted by a polynomial-time algorithm, it can also be decided in polynomial-time.

T F 8.If any problem in NP is not polynomial-time solvable, then no NP-complete problem is polynomial-time solvable.

T F 9.The problem of determining the satisfiability of boolean formulas in disjunctive normal form is polynomial-time solvable.

T F 10. Cook’s theorem proved the CNF-satisfiability problem is NP-complete.

III. (15) In this section, there are 3 questions each worth 5 points. Please circle only one choice for each question unless specified otherwise.

1. Which of the following problems (or languages) are not in P? (circle all that apply)

(a) 3-CNF Satisfiability

(b) 2-CNF Satisfiability

(c) Finding a Hamiltonian Path in an undirected graph

(d) Finding a clique in an undirected graph

(e) Finding an Euler Tour (which traverses each edge once) in a directed graph

(f) Finding the longest simple path (with no cycles) between two vertices in a directed graph

(g) Finding the shortest path between two vertices in a directed graph

2. Which of the following is the correct solution for T(n)= 3T(n/2) + nlgn ?

(a) Θ(n2lgn)

(b) Θ(nlgn)

(c) Θ(nlg2n)

(d) Θ(n2)

(e) Θ(nlg3)

3. Which of the following decision problems are NP-Complete? (circle all that apply)

(a) Given two graphs G1 and G2, are G1 and G2 isomorphic?

(b) Given an an undirected graph G, is there a vertex cover of size k in G?

(c) Given an an undirected graph G, is there a clique of size 5 in G?

(d) Is there an Euler Tour (which traverses each edge once) in a directed graph?

(e) 3-CNF Satisfiability

(f) 2-CNF Satisfiability

(g) Is there a path of size less than k between two vertices in a directed graph?

(h) Given a directed acyclic graph G, is there a hamiltonian path in G?