CSC 4170: Homework Assignments

CSC 4170: Homework Questions

Policy: Homework will not be graded, but the quiz and examination questions will mostly come from or be based on the homework assignments. Using somebody's help when doing homework is not forbidden. Books or notes will not be allowed during a quiz or examination.

[For the quiz of August 29]

Material covered: Slides 0.a – 0.h

Questions: (New questions will/may be added to this list on Thursday)

· Exercise 0.1 [Note: "N" stands for natural numbers. See page 4]

· Exercise 0.2

· Exercise 0.3

· Exercise 0.4

· Exercise 0.5

· Exercise 0.6

[For the quiz of September 5]

Material covered: Slides 1.1.a – 1.2.g

Questions: (New questions will/may be added to this list on Thursday)

· Exercise 1.1

· Exercise 1.2

· Exercise 1.3

· If a DFA (finite automaton) does not accept any strings, how many (if any) languages can it recognize?

· Exercise 1.4

· Exercise 1.5(a,b,c,g,h)

· Exercise 1.6(a,b,d,e,g,i,k,m,n)

· Exercise 1.7(a,b,c,d,g)

[For the quiz of September 12]

Material covered: Slides 1.2.h – 1.3.d

Questions: (New questions will/may be added to this list on Thursday)

· Exercise 1.16

· What is a regular expression over an alphabet S? (define – Slide 1.3.b)

· List all the elements of the set ({a,b}_°{0,1})È({a,b}_°Æ*)È({0,1}_°Æ).

· List five distinct elements of the set {01,10}*.

· Exercise 1.18 (a,b,c,d,e,g,k,l,m,n)

· Exercise 1.20

[For the quiz of September 19]

Material covered: Slides 1.3.e – 1.4.c

Questions: (New questions will/may be added to this list on Thursday)

· Exercise 1.19

· You should be able to perform the routines of ripping a state out (Slide 1.3.q) and eliminating parallel transitions (Slide 1.3.r).

· Exercise 1.21

· Make sure you understand the formulation (statement) of the pumping lemma and can accurately reproduce it. No proof of this lemma is required though.

[For the quiz of September 26]

Material covered: Slides 1.4.c – 2.1.i

Questions: (New questions will/may be added to this list on Thursday)

· Using the pumping lemma, prove that the language {0ⁿ1ⁿ | n≥0} is not regular.

· Using the pumping lemma, prove that the language {ww | w∈{0,1}^*} is not regular.

· Using the pumping lemma, prove that the language {0^m1ⁿ | 0<m<n} is not regular.

· Using the pumping lemma, prove that the language {0^m1ⁿ | 0<n<m} is not regular (hint: think of pumping out instead of pumping in).

· Exercise 2.1

· Exercise 2.3

· When do we say that a context-free grammar is ambiguous? (definition)

· Exercise 2.4

· Exercise 2.9

[For the quiz of October 3]

Material covered: Slides 2.2.a – 2.3.d

Questions: (New questions will/may be added to this list on Thursday)

· Using the procedure of Slide 2.1.j, convert the DFA M₁ from Exercise 1.1 to an equivalent context-free grammar.

· Construct a PDA for the language {w | the length of w is odd and its middle symbol is a 0} over the alphabet {0,1}.

· Construct a PDA for the language {w#w^R| w∈{0,1}*}. Here and below, w^R means w spelled right to left. So, the strings in this language are #, 0#0, 1#1, 00#00, 01#10, 10#01, 11#11, 000#000, 001#100, 111001#100111, etc.

· Construct a PDA for the language {ww^R| w∈{0,1}*}.

· Construct a PDA for the language {w | w=w^R, i.e., w is a palindrome} over the alphabet {0,1}.

· Construct a PDA for the language {w | the length of w is odd and its middle symbol is a 0} over the alphabet {0,1}.

· State the pumping lemma for context-free languages.

· Using the pumping lemma, prove that the language {aⁿbⁿcⁿ | n≥0} is not context-free.

[For the quiz of October 17]

Material covered: Slides 3.1.a – 3.1.g

Questions: (New questions will/may be added to this list on Thursday)

The definitions of “decider”, “recognize” and “decide” (Slide 3.1.c1).
Exercise 3.2
Exercise 3.5

· Construct a Turing machine (provide a full diagram) that decides the language represented by the regular expression #0*=0*. The input alphabet here is {#,0,=}.

Construct a Turing machine (provide a full diagram) for the language {#0ⁿ>0^m | n>m}. The input alphabet here is {#,0,>}. (Note: this is similar to but NOT the same as the example on slide 3.1.f).

[For the quiz of October 24]

Material covered: Slides 3.1.h – 3.2.c

Questions: (New questions will/may be added to this list on Thursday)

Design a fragment of a TM that, from a state “Beg?”, goes to a state “Yes” or “No”, depending on whether you are at the beginning of the tape or not, without corrupting the contents of the tape (Slide 3.1.i).
Design a fragment of a TM that, from a state “Go to the beginning”, goes to the beginning of the tape and state “Done” (Slide 3.1.j).
Design a fragment of a TM that, beginning from the current cell, shifts the contents of the tape right, typing in the current cell a 0 (Slide 3.1.k). Assume the tape alphabet is {0,1,-}, and that neither 0 nor 1 ever occurs after the leftmost blank on the tape.
Design a fragment of a 2-tape TM that swaps the contents of the tapes, from the position where the heads are at the beginning and there are no blanks followed by non-blank symbols (Slide 3.2.c). Tape alphabet: {0,1,-}.

[For the quiz of October 31]

Material covered: Slides 3.2.d – 3.2.j

Questions: (New questions will/may be added to this list on Thursday)

State Theorem 3.13 and provide a very brief (not more than half-page) yet meaningful and to-the-point explanation of its proof idea. Do not go into (m)any technical details.
State Theorem 3.16 and provide a very brief (couple of lines perhaps) of its proof idea. Do not go into (m)any technical details.
Design an enumerator for the language (00)*, i.e. {e,00,0000,000000,00000000,…}. Hint: Start with the one of Slide 3.2.g and think about how to (slightly) modify it.

Prove (with understanding!) that a language is enumerable iff it is recognizable (Slide 3.2.h).
Exercise 3.6.

The definitions of computing, computability and graph of a function (Slide 3.2.j).
For a bit string w, NOT(w) means w with all bits changed. For example, NOT(11010)=00101. Construct a Turing machine with an output that computes function NOT.

[For the quiz of November 7]

Material covered: Slides 3.2.h – 4.1.a

Questions: (New questions will/may be added to this list on Thursday)

Prove that a function is computable iff its graph is decidable (Slide 3.2.k).
What is encoding? Give examples.
What is the Church-Turing thesis all about? (don't just write something like "algorithms = TM"; write a couple of sentences showing that you understand what you are writing).
Exercise 3.7.
Prove that if a language is decidable, then so is its complement.
Prove that if two languages are decidable, then so is their intersection.

[For the quiz of November 14]

Material covered: Slides 4.1.b – 4.2.d

Questions: (New questions will/may be added to this list on Thursday)

Exercise 4.1(a,b,c,d)
Exercise 4.3. Hint: similar to Theorem 4.4.

· What language does the universal Turing machine recognize? (Do not just give its name, define the language.) The answer is found on Slide 4.2.a.

· How does the universal Turing machine work? (i.e. what algorithm does it follow?) The answer, again, is found on Slide 4.2.a.

· Proof of Theorem 4.11 (given on Slides 4.2.b.1-2, or page 207 of the textbook)

· Prove that if a language L and its complement L are both recognizable, then L is decidable (Theorem 4.22).

· Prove that the complement of A_TM is not recognizable (Theorem 4.23).

· Is the complement of A_TM decidable? Why or why not?

[For the quiz of November 21]

Material covered: Slides 5.1.a – 7.1.g (Section 6 is omitted. Slides 7.1.c-7.1.g are just to help you refresh your memory of asymptotic analysis, depending on your needs).

Questions: (New questions will/may be added to this list on Thursday)

Prove that the halting problem is undecidable (Theorem 5.1)
Prove that the halting problem is recognizable (Hint: Similar to the theorem on Slide 4.2.a).
Show that A_NFA is mapping reducible to A_DFA (Slide 5.3.b).

The definitions of mapping reduction and mapping reducibility.
In each case below, find (precisely define) a particular function that is a mapping reduction of A to B. Both A and B are languages over the alphabet {0,1}.

A is the language described by 1*0*, B is the language described by 01*0*
A={w | the length of w is even}, B={w | the length of w is odd}
A=B={w | the length of w is even}
A={0,1}*, B={00,1,101}

Your answers should start with “f(w) = ”

Describe a function which is a mapping reduction of the acceptance problem to the halting problem (Slide 5.3.d).
Prove that if a language A is mapping reducible to a language B and B is decidable, then so is A (theorem 5.22).
Definition 7.1.

[For the quiz of November 28]

Material covered: Slides 7.1.h – 7.1.p

Questions: (New questions will/may be added to this list on Thursday)

Describe a O(n²) time single-tape TM which decides the language {0ⁿ1ⁿ | n≥0} (Slide 7.1.b).
Answer the questions of Slide 7.1.j.
Show that {0ⁿ1ⁿ | n≥0} is in TIME(n log n) (describe a TM and give an asymptotic analysis – Slide 7.1.l).
Describe a O(n) time two-tape TM which decides the language {0ⁿ1ⁿ | n≥0} (Slide 7.1.m).
Definition 7.9.
Theorems 7.8, 7.11 withOUT proofs.

[For the quiz of December 5]

Material covered: Slides 7.2.a – 7.3.g

Questions: (New questions will/may be added to this list on Thursday)

What are the two main reasons making the class P important and appealing? (Slide 7.2.a)
Give a polynomial time algorithm for PATH (Slide 7.2.c). Explain why it indeed runs in polynomial time.
Exercises 7.3, 7.8, 7.9, 7.12
Define the class NP (Slide 7.3.d).
Write a nondeterministic polynomial time algorithm for CLIQUE (Slide 7.3.f)
Write a nondeterministic polynomial time algorithm for CLIQUE (Slide 7.3.g)
Write a nondeterministic polynomial time algorithm for COMPOSITES
Write a nondeterministic polynomial time algorithm for HAMPATH

Additional material covered since the previous posting: Slides 7.3.d – 8.3.e

Questions:

The definitions of polynomial time reducibility, NP-hardness and NP-completeness (Slide 7.3.d)
The definitions of coNP and EXPTIME (given on slide 7.3.j).
The intuitive characterizations of P, NP, coNP and EXPTIME (given on slide 7.3.j).
What do we know and what do we not know about the relationships (equal? subset?) between P, NP, coNP, PSPACE, NPSPACE, EXPTIME? (again, given on slides 7.3.j and 8.2.a).
Definition 8.1
Write a linear space algorithm for SAT (Slide 8.0.c)
State Savitch’s theorem (Slide 8.1.a)
Define the class PSPACE
Define the concept of PSPACE-completeness

FINAL EXAM: Wednesday December 13, 11:30-2:00, Mendel 213.