CSC 4170: Homework Assignments

CSC 4170: Homework Assignments

Policy: Homework will not be graded. Using somebody's help when doing homework is not forbidden. However, the quiz problems will usually come from the latest two homework assignments. Book or notes will not be allowed during the quiz. Some homework or quiz problems may also reappear on examinations. So, even if you use somebody's help, make sure ultimately you understand everything well and can solve the same or similar problems on your own.

August 28

Material covered: Slides 0.a - 0.h

Assignment:

Exercise 0.1 [Note: "N" stands for natural numbers. See page 4]
Exercise 0.2
Exercise 0.3
Exercise 0.4
Exercise 0.5

August 30

Material covered: Slides 1.1.a - 1.1.j

Assignment:

Exercise 1.1
Exercise 1.2
Exercise 1.3
Exercise 1.4
Exercise 1.5(a,b,c,g,h)
Exercise 1.6(a,b,d,e,g,i,k,m,n)

September 4

Material covered: Slides 1.2.a - 1.2.h

Assignment:

Exercise 1.7(a,b,c,d,g)
Exercise 1.24
Exercise 1.27

September 6

Material covered: Slides 1.2.h - 1.3.c

Assignment:

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

September 11

Material covered: Slides 1.3.d – 1.3.p

Assignment:

Exercise 1.19
Exercise 1.20
Exercise 1.22

September 13

Material covered: Slides 1.3.q – 1.4.c

Assignment:

Exercise 1.21
Make sure you understand the formulation (statement) of the pumping lemma and can accurately reproduce it. No proof of this lemma required tough.

September 18

Material covered: Slides 1.4.d – 2.1.b

Assignment:

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.
Exercise 2.1

September 20

Material covered: Slides 2.1.c – 2.1.g

Assignment:

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.3 (a-n).
When do we say that a context-free grammar is ambiguous? (definition)

September 25

Material covered: Slides 2.1.h – 2.2.b

Assignment:

Exercise 2.4.
Exercise 2.9.
Using the procedure of Slide 2.1.j, convert the DFA from Exercise 1.21(b) to an equivalent context-free grammar.

September 27

Material covered: Slides 2.2.c – 2.3.d

Assignment:

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 {w | w=w^R, i.e., w is a palindrome}. Assume the alphabet is {0,1}.
Construct a PDA for the language {w | the length of w is odd and its middle symbol is a 0}. Assume the alphabet is {0,1}.
The formulation (no proof) of the pumping lemma for context-free languages.
Proof given in Example 2.36 (Slide 2.3.c).

October 2

Material covered: Slides 3.1.a – 3.1.e4

Assignment:

NOTICE: Midterm on Thursday, October 11. There will be a quiz on Tuesday as usual.

The definitions of accepting, rejecting, recognizing, deciding (Slide 3.1.c1).
Exercise 3.2
Exercise 3.5
Construct a Turing machine (provide a full diagram) for the language {#·ⁿ>·^m| n>m} (note: this is similar to but NOT the same as the example on slide 3.1.f).

October 4

Material covered: Slides 3.1.f – 3.1.l

Assignment:

NOTICE: Midterm on Thursday, October 11. There will be a quiz on Tuesday as usual.

· 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.

October 9

Material covered: Nothing new

Assignment: Nothing new. NOTICE: Midterm on Thursday, October 11.

October 23

Material covered: Slides 3.2.a – 3.2.e

Assignment:

· 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,-}.

· State Theorem 3.13 and provide a very brief (half-page or so) yet meaningful and to-the-point explanation of its proof idea. Do not go into (m)any technical details.

· The same for Theorem 3.16.

October 25

Material covered: Slides 3.2.f – 3.2.k

Assignment:

Proof idea for Theorem 3.21.

· 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.

November 1

Material covered: Slides 3.3.a – 3.3.f

Assignment: [NOTE: the quiz questions this time will come from one of the latest THREE sets of problems – those posted on Oct. 23, Oct. 25 and Nov. 1]

Construct an enumerator for the language (expressed by) (00)*. Hint: Start with the one of Slide 3.2.g and think about how to (slightly) modify it.

· 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.6.

· Exercise 3.7.

November 6

Material covered: Slides 4.1.a – 4.1.f

Assignment:

Exercises 4.1, 4.2, 4.3.

November 8

Material covered: Slides 4.2.a – 4.2.d

Assignment:

What language does the universal Turing machine recognize and how does it work? (the description of the algorithm it follows). Answers to this question are 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).
Proof of Theorem 4.23.

November 13

Material covered: Slide 5.1.a

Assignment:

Prove that if a language L and its complement L are both recognizable, then L is decidable (Hint: the idea is, in fact, already given in the proof of Theorem 4.23).
Proof of Theorem 5.1.
Prove that the halting problem is recognizable (Hint: similar to the theorem on Slide 4.2.a).

November 15

Material covered: Slides 5.3.a – 5.3.d

Assignment:

The definitions of mapping reduction and mapping reducibility.
Proof of Theorem 5.22.
Prove that if a language A is mapping reducible to a language B and B is recognizable, then A is recognizable (hint: very similar to the proof of Theorem 5.22).
In each case below, find (precisely define) 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}

November 20

Material covered: Slides 6.3.a – 6.3.b

Assignment:

Describe a function which is a mapping reduction of the acceptance problem to the halting problem (Slide 5.3.d).
The definition of Turing reducibility.
Proof of Theorem 6.21.
Show that any language L is Turing reducible to its complement (Hint: A straightforward generalization of the example on Slide 6.3.a).
Show that A_TM is Turing reducible to HALT_TM (we talked about this at the end of class).

November 27

Material covered: Slides 6.2.a – 6.2.c

Assignment:

Which of the following sentences are true and which are false? Justify your answers:
   1. "x$y(x=y)
   2. $y"x(x=y)
   3. "x"y ($z(y=x+z) Ú $z(x=y+z))

Express, using the formal language of arithmetic (given on Slide 6.2.a), the following (it is OK if you use x,y,z,.. instead the official variables v, v', v'', ...; it is also OK to use A®B as an abbreviation of (ØA)ÚB and $xA(x) as an abbreviation of Ø"xØA(x)):
(1) "x is even''; (2) "x³y"; (3) "x>y"; (4) "x=y³"; (5) "x is composite" (meaning that x is the product of two other numbers, both different from x); (6) "x is prime"; (7) "x is a divisor of y"; (8) "x is a common divisor of y and z"; (9) "x is the greatest common divisor of y and z".

November 29

Material covered: Slides 6.2.d, 7.1.a – 7.1.b

Assignment:

Prove that Th(N,+,´) is unrecognizable, assuming that the undecidability of this problem is already known (the Corollary on slide 6.2.d).
Definirion 7.1.

December 4

Material covered: Slides 7.1.c – 7.1.p (Slides 7.1.d-f omitted)

Assignment:

Definirion 7.9.
Show that {0^k1^k | k³0}ÎTIME(n log n) (describe a TM and give an asymptotic analysis).
Theorems (with proof ideas) 7.8, 7.11.

December 6

Material covered: Slides 7.2.a – 7.3.f

Assignment:

Definition 7.12
The definition of NP (Slide 7.3.d)
Show that PATHÎP (Theorem 7.14)
Show that RELPRIMEÎP (Theorem 7.15)
Prove that CLIQUEÎNP (Slide 7.3.e)

December 13

Material covered: Slides 7.3.f – 7.3.g

Assignment:

Definitions of the classes coNP and EXPTIME. See Slide 7.3.g.
How do the classes P, NP, coNP and EXPTIME relate (what is known to be a subset of what, what containments or (un)equalities remain unknown)? Again, see Slide 7.3.g.

FINAL examination: Thursday, December 20, 11:30-2:00, usual place.