CSC 280 Calendar and Problem Sets

Schedule of topics and homework problem problems. Solutions to the problem sets will be discussed in the workshops. Problem sets are not turned in. See Reading Assignments for homework that will be turned in.

date topic
Thu Jan 19 Introduction. Mathematical notation.
Tue Jan 24 Proofs. Problem Set 1.
Thu Jan 26 Proofs. About "getting the direction right" in proofs.
Tue Jan 31

Regular languages.

Problem set 2:

Construct the following NFA that accepts strings that end in 00.

Use the proof of the reduction of a NFA to a DFA to construct the DFA for this language.

Sipser 1.31, 1.36, 1.37, 1.38, 1.40, and 1.45.

Thu Feb 2 Regular languages
Tue Feb 7

Regular expressions. Do these problems and bring your solutions to the workshop:

Exercises 1.18, 1.28, 1.21 (b), 1.24 (a-d), 1.25, 1.26 (for T1 only), 1.27.

Thu Feb 9

(Andrew Reinders teaches)

See new readings to outline, listed on readings page.

Work on these problems over the weekend and bring your solutions to class Tuesday: 1.49, 1.54.

Optional makeup Quiz 2: complete and bring to class Tuesday.

For workshop Wednesday, work on these exercises and bring your solutions to workshop: 2.4bcef, 2.5bcef, 2.6b, 2.9, 2.11, 2.27.

Tue Feb 14 Finished regular languages and began context-free languages.
Thu Feb 16 Quiz 3. Enjoy your weekend.
Tue Feb 21

More on context free languages. Work on these exercises and bring your solutions to workshop Wednesday:

  • Extend the grammar in exercise 2.1 to include unary - (negation) and binary - (minus).
  • Convert that grammar to a PDA using the procedure given in Theorem 2.20.
  • Convert the following PDA to a grammar using the procedure given in Theorem 2.20:

  • Problem 2.22. Hint: Create a PDA that "guesses" the position of the first mismatch.
Thu Feb 23

Finished context free languages.

Make-up Quiz 3. Turn this in on class on Tuesday 28 Feb. You may use textbook and other academic sources, but you should not search for solutions to the specific problems or collaborate.

Readings on Chapter 3 are due Sunday midnight.

Study and/or solve following problems to prepare for class Tuesday and for the workshop Wednesday:

  • Example 2.36
  • Example 2.38
  • We saw that regular languages are closed under intersection. Use the result from Example 2.36 to prove that context-free languages are not closed under intersection. Explain why together with the fact that context-free languages are closed under union means that context-free languages are not closed under complement.
  • We showed the solution to problem 2.22 in the last class. Study your notes so that you understand how and why this solution works:
  • 0. Push $ on the stack.
    1. Read next input symbol and push 1 on the stack.
    2. Nondeterministically jump to either 1 or 3.
    3. Record the current input symbol in the finite control (i.e. by going to a particular state).
    4. Read input symbols until # is read.
    5. Read the next symbol, and pop the stack.
    6. If stack is empty ($ is not on top), then go to 7, else go to 5.
    7. Accept if the current input symbol isn’t a, (i.e., go to accept state, where the accept state loops reading y until input is all gone), otherwise reject.

    Next, come up a PDA that shows the following language is context-free: L = { x#y | x,yt in {a,b,c}* such that some pair of letters "a" and "b" (in that order) in x are separated by the same distance as are a pair of letters "a" and "b" in y }. For example, L contains the string cabccbac#ccacabb because the first half contains and "a" and "b" separated by 3 characters, as does the second half. However, L does not contain the string caccbcb#bacbccacb.

Tue Feb 28

Finish Pumping Lemma for CFL.

In class: Problem 2.31.

Workshop this week:

  • Finish any of the problems listed above that we did not complete in class.
  • Problem 2.18.
  • Problem 2.31.
  • If time: Problem 2.43
Thu Mar 1

Ch 3: Church-Turing Thesis

For class Tuesday Mar 6 class and workshop Wed Mar 7:

  • Modify Example 3.11 so that the TM computes i / j = k using integer arithmetic (rounding down, so 3 / 2 = 1).
  • Modify the example again so it computes i mod j = k.
  • Problems 3.15 and 3.16.

For class Thursday Mar 8, prepare by outlining Chapter 4 section 1 (pages 165 - 172). You will not turn in the outlines yet, but you should have them done.

Tue Mar 6

Quiz 4: Pumping Lemma and PDAs. The questions will be similar to the problems listed for Feb 23 and Feb 28 (excluding 2.43).

Ch 3: Church-Turing Thesis

Thu Mar 8

Ch 4: Decidability (Sec 4.1)

Read and outline rest of Chapter 4. The turn-in deadline (this time only) is NOON TUESDAY (March 20) rather than Sunday night. See also the problems for this week.

Tue Mar 20

Ch 4: Decidability (Sec 4.2)

Class today: Proof that the Halting Problem is undecidable

Problems for workshop Wednesday: 4.3, 4.5, 4.9 (answer in book), 4.10, 4.6, 4.7, 4.28.

Special reading assignment: read Section 5.1 to the end of Theorem 5.4 (pages 187-192). Do not turn in yet.

Thu Mar 22

Ch 5: Reducibility

Class today: Theorems 5.1, 5.2, 5.3, 5.4

Reading assignment due Sunday night: outline of Section 5.1 and 5.3 (skip section 5.2).

Tue Mar 27

Ch 5: Reducibility

Class today: Sec. 5.3. and problems 5.28 (Rice's Theorem). We will start working on the following problems and finish them in workshop: 5.9, 5.13, 5.16 (busy beaver), 5.25, 5.30.

Make-up Quiz 4 handed out. Due at start of class Tuesday April 3.

Weds Mar 28 Workshop and Review Session: special 90+ minute session, beginning with Reducibility problems, followed by discussion of all material to date for review for midterm.
Thu Mar 29

Midterm (Automata and Decidability)

There will be six problems covering the following topics:

  • Converting a NFA to a DFA.
  • Using the pumping lemma for regular languages to show a language is not regular.
  • Proving that a language is regular by constructing a PDA or a CFG.
  • Using the pumping lemma for context free languages to prove that a language is not context free.
  • Showing that a language is decidable by constructing a Turing machine that always halts that decides it.
  • Using a mapping reduction to show that a language is undecidable by reducing the decision problem to the halting problem.

Reading assignment due *Monday* night at midnight: Outline Chapter 7.1 - 7.4. Although this is fairly long, you already know much of your material, so your notes can be brief. The details of the proof of the Cook-Levin are complicated, so at this point just try to grasp the high-level idea: you can revise your notes on this proof for the next set of outlines.

Tue Apr 3

Ch 7: Time Complexity

Make-up Quiz 4 due.

Wed April 4 Workshop and following class: 7.9, 7.11, 7.17
Thu Apr 5 Ch 7: Time Complexity - problems 7.27
Tue Apr 10

Ch 7: Time Complexity - problems 7.24, 7.26, 7.29, 7.36, 7.42

(Andrew Reinders runs class)

Make-up Quiz 4 returned.

Wed Apr 11 Workshop: problems 7.26, 7.29, 7.36, 7.42
Thu Apr 12

Class Cancelled

Reading outlines due Sunday: Chapter 8, Sections 8.1-8.3

Tue Apr 17

Quiz 5 (Time Complexity)

Space Complexity (Sec 8.1-8.3: outlines due midnight Monday April 16)

Space complexity classes; Savitch's theorem; Quantified Boolean Formulas

Wed April 18 Workshop - Problems 8.8, 8.9, 8.11, 8.16
Thu Apr 19

Space Complexity

PSPACE-completeness; Games

Make-up Quiz 5. Due in class Tuesday Apr 24.

Solution to Quiz 5.

My notes on Savitch's Theorem, PSPACE-Completeness, and Games.

Tue Apr 24

Space Complexity (Definition of an oracle, Sec 9.2 up to page 349, and Section 10.3 Alternating Machines, pages 380-386: outline due midnight Sunday April 22)

Alternating machines; Polynomial Hierarchy

Wed April 25 Workshop - Exercise 8.3, 8.13, 10.12, 10.13, 10.14.
Thu Apr 26

Space Complexity & the Polynomial TIme Hieararchy

My notes on the polynomial time hierarchy.

Problem set on polynomial hierarchy. You will complete and turn in for a grade in class on Tue May 6. (This replaces a quiz.)

Tue May 1 Conclusion of Time and Space Complexity
Wed May 2 No workshop!
Fri May 11 Final Exam (Complexity) 4:00pm-5:30pm. You may bring your outlines and textbook.