Homework 5 Theory of Computation

Homework 5
ECE 345 Algorithms and Data Structures

• All page numbers are from 2009 edition of Cormen, Leiserson, Rivest and Stein.
• For each algorithm you asked to design you should give a detailed description of the idea,
proof of algorithm correctness, termination, analysis of time and space complexity. If not,
your answer will be incomplete and you will miss credit. You are allowed to refer to pages in
the textbook.
• Do not write C code! When asked to describe an algorithm give analytical pseudocode.
• Staple your homework properly. Use a stapler; do not use glue or other weird material to put
it together. If you are missing pages, we are not responsible for it but you are!
• Write clearly, if we cannot understand what you write you may not get credit for the question.
Be as formal as possible in your answers. Don’t forget to include your name(s) and student
number(s) on the front page!
1. [Theory of Computation, 3+6+6 points]
For each of the following languages over the alphabet Σ = {a, b, c}, draw a corresponding DFA
for the language.
(a) a
∗
· b
(b) ((a | b)
∗
| (c · c
∗
))
(c) a · (a | (b | c))∗
2. [NP-completeness, 5+5 points]
For a graph G = (V, E), an independent set is a set of vertices I ⊆ V such that for all (u, v) ∈ E,
at most one of u or v is in I. In other words, every edge has at most one end in I. A vertex
cover is a set of vertices S ⊆ V if for every edge (u, v) ∈ E, at least one of u or v is in S. In
other words, every edge has at least one end in S. Consider the following two problems:
Problem Vertex-Cover
Input: G = (V, E), k
Question: Does G contain a vertex cover S of size |S| ≤ k?
Problem: Independent-Set
Input: G = (V, E), k
Question: Does G contain an independent set I of size |I| ≥ k?
UofToronto–ECE 345–Fall, 2017 2 Homework 5
(a) Show that Independent-Set ≤P Vertex-Cover.
(b) Show that Vertex-Cover ≤P Independent-Set.
3. [NP-completeness, 5+15 points]
Consider the following problems A and B:
A = Vertex-Cover.
B = {hGi | G is an undirected graph with an even number of vertices, and there exists a vertex
cover with exactly half the vertices}.
Show that B is NP-complete by showing that:
(a) B ∈ NP. That is, show that given a solution, this solution can be verified in polynomial
time.
(b) B is NP-hard, by showing that A ≤P B. Hint: Remember that an instance for A (the
Vertex-Cover problem) is given as hG, ki. For the mapping to B, consider three cases
for k with respect to |V |
2
.
4. [NP-completeness, 25 points]
Prove that the following problem is NP-Complete. Longest-Simple-Cycle: Given graph
G = (V, E) and an integer k, determine whether G contains a simple cycle (no repeated
vertices) with at least k vertices. You may assume that the Ham-Cycle is NP-Complete in
your proof.