CS 601 Spring 2020: Final Exam.
Solve any 5 of the following problems. You will get extra credit for solving additional problems. All
problems are worth 20 points.
Please work on these problems individually, and do not discuss them, verbally or otherwise, with anyone
else. You may email me with any questions you have. You may also consult textbooks, but you must
acknowledge and reference any material you use to solve these problems. You are not allowed to
search for solutions on the Web and you may not post these problems on any Web forum asking for
answers.
Problem 1. Consider the language = {< >: ℎ ℎ ∈ () ⟹ ∈ ()}.
For example, if (1) = 0
∗ then 1 ∈ , but if (2) is the set of all binary strings without two
consecutive 1’s then 2 ∉ because 101 ∈ (2) 101101 ∉ (2). Describe a high-level
algorithm to decide and give an intuitive argument why your algorithm is correct.
One way to approach this problem is to construct, from the DFA a DFA that is the product of with
several similar automata that differ from only in having a different initial state. In the DFA that is the
product of these automata, it is possible to determine whether the input to A has the property that, if
followed by another , the string would be accepted by A. That lets you choose the final states of
the product automaton so that it accepts if and only if is accepted by A but is not.
Problem 2. Prove that ≠ (). (Hint: Consider TQBF)
Problem 3. An undirected graph is bipartite if its vertices can be divided into two sets so that all edges
go from a vertex in one set to a vertex in the other set. Show that a graph is bipartite if and only if the
graph has no odd cycles. Let = {< >: ℎ}. Prove that
∈ .
Problem 4. Before you head home for vacation, you decide to purchase gifts for family and friends. You
must fit these gifts inside the limited number of suitcases you have. All suitcases are the same size, and
every gift fits inside a suitcase. Your problem is to determine if all the gifts can be packed inside the
suitcases you have. The size of each gift and of the suitcases can be modeled as integers.
A. Formulate the problem as a language decision problem. There is no a priori bound on the
number of gifts or the number of suitcases.
B. What is the computational complexity of solving your problem? Prove your answer.
Problem 5. Define the language
3 = {: 3 ℎ
ℎℎ ℎ . }
In this problem you will prove that NOTALL3SAT is NP-Complete. If any truth assignment that satisfies
has the property that at least one literal in every clause is FALSE, then we say that the truth assignment
is a NOTALL3-satisfying assignment.
A. Show that if all the variables in a NOTALL3-satisfying assignment are negated, then the result is
also a NOTALL3-satisfying assignment for .
B. Suppose that has clauses. Now, transform (1, … , ) into another 3CNF formula
(1, … , , 0, 1, … , ) as follows:
Convert the th clause (1 ∨ 2 ∨ 3) of into (1 ∨ 2 ∨ ) ∧ (̅ ∨ 3 ∨ 0)
Note that has 2 clauses, and that 0 appears in of them.
Show that if has a NOTALL3-satisfying assignment, then is satisfiable.
C. Show that if is satisfiable then has a NOTALL3-satisfying assignment.
D. Prove that NOTALL3SAT is NP-Complete.
Problem 6. Consider the following checkerboard game played by one person. You are given an ×
board where each of the 2 positions may be empty or occupied by either a red stone or a blue stone.
Initially, some configuration of stones is placed on the board. Then, for each column you must remove
either all the red stones in that column or all the blue stones in that column. Of course, if a column has
only blue stones, or only red stones, you do not have to remove any stones in that column. The
objective is to leave at least one stone in each row after you have processed every column.
It is possible, depending on the initial configuration of the checkerboard, that the objective cannot be
met. Given an initial checkerboard configuration, what is the complexity of determining if the objective
can be met? Give a formal proof of your answer.
Problem 7. A quadratic system is a set of equalities and inequalities, each involving polynomials of
degree at most 2 (with integer coefficients) in real variables 1, . . . , . The problem is to decide
whether there exists an assignment of real values to the variables that satisfies all the constraints
simultaneously.
As an example, the system
1 + 2 ≤ 1
1 ≥ 0
2 ≥ 0
412 ≥ 1
can be satisfied by setting 1 = 2 =
1
2
, but if we replaced the last inequality by 12 ≥ 1, then the
system becomes unsatisfiable.
Define QUADSAT to be the set of satisfiable quadratic systems. Show that 3 ≤ .
(Hint: construct a variable for each vertex in the graph, and construct inequalities that are satisfied if
and only if (i) each variable is assigned either -1, 0 or 1 and (ii) variables corresponding to adjacent
vertices are assigned different values.)
How would you show that QUADSAT is in ? What is the technical reason this seems difficult?
Problem 8. A language ⊆ Σ∗ is said to cover ℕ if, for every ≥ 0, there is a string of length in . In
this problem we consider regular languages that cover ℕ.
A. For any language over an alphabet Σ, define () = {1|| ∶ ∈ }.
Prove that if is regular then () is regular.
(Hint: start with a DFA for .)
B. Describe an algorithm to decide if the language of a given DFA over a 1-letter alphabet covers ℕ.
Prove the correctness of your algorithm.
C. Describe a decision algorithm for testing whether the language of a DFA over any alphabet
covers ℕ or not. Prove the correctness of your algorithm.