辅导案例-CS 601
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.