**CSC 4170: Homework Assignments **

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

**Homework 1
**

**Next quiz **on September 11.

**Material covered:
**Slides 0.a - 1.2.m

**Assignment: **(New questions will be added to this list until the Friday before the quiz)

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 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)

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

Exercise 1.16

**Homework 2
**

**Next quiz **on September 25.

**Material covered:
**Slides 1.3.a - 1.4.e

**Assignment: **(New questions will be added to this list until the Friday before the quiz)

- Exercise 1.18 (a,b,c,d,e,g,k,l,m,n)
- Exercise 1.20
- Exercise 1.19
- Exercise 1.21
- Exercise 1.27
- Make
sure you understand the formulation (statement) of the pumping lemma and
can accurately reproduce it. No proof of this lemma is required though.

- Using
the pumping lemma, prove that the language
**{0**≥^{n}1^{n}| 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**is not regular.^{m}1^{n}| 0<m<n} - Using
the pumping lemma, prove that the language
**{0**is not regular (hint: think of^{m}1^{n}| 0<n<m}*pumping out*instead of pumping in).

**Homework 3
**

**Next quiz **on October 9.

**Material covered:
**Slides 2.1.a-2.3.d

**Assignment: **(New questions will be added to this list until the Friday before the quiz)

- Exercise 2.1
- Exercise 2.3 (a-n)
- When do we say that a context-free grammar is ambiguous? (definition)
- Exercise 2.4
- Exercise 2.9
- Using the
procedure of Slide 2.1.j, convert the DFA
*M*from Exercise 1.1 to an equivalent context-free grammar_{1} - Construct
a PDA for the language
**{w#w**∈^{R}^{ }| w**{0,1}*}**. Here and below,**w**means^{R}**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).

**Homework 4
**

**Next quiz **on October 30.

**Material covered:
**Slides 3.1.a-3.1.i

**Assignment: **(New questions will be added to this list until the Friday before the quiz)

- 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
The input alphabet here is*#0*=0*.**{#,0,=}**.* - Construct
a Turing machine (provide a full diagram) for the language
The input alphabet here is*{#0*.^{n}>0^{m }| n>m}*{#,0,>}**.*(Note: this is similar to but NOT the same as the example on slide 3.1.f). - Design
a fragment of a TM that, from a state “
”, goes to a state “*Beg?*” or “*Yes*”, depending on whether you are at the beginning of the tape or not, without corrupting the contents of the tape (Slide 3.1.i).*No*

**Homework 5
**

**Next quiz **on November 13.

**Material covered:
**Slides 3.1.j-3.3.c

**Assignment: **(New questions will be added to this list until the Friday before the quiz)

- Design
a fragment of a TM that, from a state “
”, goes to the beginning of the tape and state “*Go to the beginning*” (Slide 3.1.j).*Done* - 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
(Slide 3.1.k). Assume the tape alphabet is*0*, and that neither*{0,1,-}*nor*0*ever occurs after the leftmost blank on the tape.*1* - 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 (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. - Exercise
3.6.

- Prove that a language is enumerable iff it is recognizable (Slide 3.2.h).
- 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**. - The definitions of computing, computability and graph of a function (Slide 3.2.j).
- Prove that a function is computable iff its graph is decidable (Slide 3.2.k).
- What is encoding? Give examples.

**Homework 6
**

**Next quiz **on November 27.

**Material covered:
**Slides 3.1.j-4.2.d

**Assignment: **(New questions will be added to this list until the Friday before the quiz)

- 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).
- Exercises
3.7, 4.1(a,b,c)

- Prove that if
a language is decidable, then so is its complement.

- Prove that if
two languages are decidable, then so is their intersection.

- 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).
- Proof of Theorem 4.23.
- Prove
that if a language
**L**and its complementare both recognizable, then__L__**L**is decidable (Hint: the idea is, in fact, already given in the proof of Theorem 4.23).

- What is encoding? Give examples.

**Homework 7
**

**Final Examination **Section
1: Dec.17, 2:30-5:00; Section 2: Dec.21, 8:30-11:00.
COMPREHENSIVE! (any topic covered throughout the semester may appear)

**Material covered:
**Slides 5.1.a-5.3.e, 7.1.a-8.3.c (Chapter 6 omitted, proofs of Theorems 7.8, 7.11 also omitted)

**Assignment: **(New questions will be added to this list until December 14)

- 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).
- The definitions of mapping reduction and mapping reducibility.
- Prove that if a language
is mapping reducible to a language*A*and*B*is decidable, then*B*is decidable (Theorem 5.22).*A* - rove that if a language
is mapping reducible to a language*A*and*B*is recognizable, then*B*is recognizable (hint: very similar to the proof of Theorem 5.22).*A* - 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}**

- Describe a function which is a mapping reduction of the acceptance problem to the halting problem (Slide 5.3.d).
- Definitions 7.1, 7.7, 7.9, 7.12.
- Describe a
**O(n**time TM which decides the language^{2})**{0**≥^{n}1^{n}| n**0}**(Slide 7.1.b). - Answer the questions of Slide 7.1.j.
- Describe a
**O(n**time TM which decides the language^{2})**{0**≥^{n}1^{n}| n**0}**(Slide 7.1.b). - Show
that {
**0**≥^{n}1^{n}| n**0**} is in**TIME(****n log n)**(describe a TM and give an asymptotic analysis). - Theorems 7.8, 7.11 withOUT proofs.
- 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
- Define the class NP (Slide 7.3.d).
- Show that the CLIQUE problem is in NP (Slide 7.3.e).
- The definitions of coNP and EXPTIME (given on slide 7.3.i).
- The intuitive characterizations of P, NP, coNP and EXPTIME (given on slide 7.3.i).
- What
do we know and what do we not know about the relationships (equal? subset?)
between P, NP, coNP, EXPTIME?
(again, given on slide 7.3.g).

- Define the space complexity of a machine (Slide 8.0.a).
- Define the class PSPACE (Slide 8.2.a).
- Give a linear space algorithm for SAT (Slide 8.0.c).
- What does Savitch’s theorem say? (Slide 8.1.a).
- What
do we know and what do we not know about the relationships (equal? subset?)
between P, PSPACE, NPSPACE, EXPTIME? (Slide 8.2.a).