CS 373: Theory of Computation

Syllabus

Click here to view the syllabus: [PDF]

Problem Sets
Problem Set Corrections/Hints Due on Solutions Points
Problem Set 0 [PDF] Minor corrections Wednesday, June 20
[PDF]
100
Problem Set 1 [PDF] English description of L in problem 4 Wednesday, June 27
[PDF]
100
Problem Set 2 [PDF] Corrected alphabet for 3b and language for 4a Thursday, July 5th
[PDF]
100
Problem Set 3 [PDF] Corrected language for 3 Wednesday, July 18th
[PDF]
100
Problem Set 4 [PDF] Wednesday, July 25th
[PDF]
100
Problem Set 5 [PDF] Wednesday, August 1st
[PDF]
100

Insurance Point Challenges (Exam 1)

Here are a list of options for earning insurance points. They must be completed before Friday, June 29th.
  1. Biographical essays: write a one page (single spaced) essay summarizing the life and accomplishments of Kurt Godel, Bertrand Russel, or Georg Cantor. Please include citations for the sources you use. Email your essay to the instructor for 50 points per essay.
  2. Review sheet: If you have written good notes for the class, type them up in Latex and submit them by email. 100 points per weekly summary. If your review sheet is particularly good, the instructor may request to share it with the class. If you do so, you will recieve 50 more points.
  3. Review session: If you would like to run a weekly review session for other students, email the instructor. He will set up a conference room. You will gain 100 points for conducting the review session, and an additional 10 points per student that attends.
  4. Programming: in Python, write a DFA simulator. A user must be able to specify a DFA on an alphabet and supply strings to their DFA. Your program will let them know whether each string is accepted or rejected by the DFA. The interface for the program is entirely up to you. Present your program to the instructor during office hours for a possible 350 points.
  5. Problems from textbook: Each of the following problems from the textbook will be worth 10 points each: 1.1-1.21, 1.32-1.39.
  6. FSTs: Completing problems 1.24-1.28 together will be worth 100 points.
  7. A list of challenging proof problems can be found here.
  8. Write a Python script that will take an input string representing a regular expression in Sipser's notation (since the union symbol isn't standard ASCII, you can replace it with the + symbol) and a file. Your program should then convert the input regular expression into a Python regular expression and read the input file line by line. Each line matching the regular expression should be printed to the screen. This is worth 250 insurance points.

Insurance Point Challenges (Exam 2)

Here are a list of tasks for earning insurance points for exam 2. They must be completed before Friday, July 20th.
  1. Biographical essays: write a one page (single spaced) essay summarizing the life and accomplishments of Alan Turing, Noam Chomsky, Alonzo Church, David Hilbert, or Stephen Kleene. Please include citations for the sources you use. Email your essay to the instructor for 50 points per essay.
  2. A list of programming challenges can be found here. They may be completed in the language of your choice.
  3. The following problems from the textbook are worth 10 points each: 2.4b, 2.4c, 2.4e, 2.4f, 2.5b, 2.5c, 2.5e, 2.5f, 2.6b, 2.6d, 2.7b, 2.7d
  4. The following problems from the textbook are worth 20 points each: 2.11, 2.12, 2.14
  5. The following problems from the textbook are worth 50 points each: 2.19, 2.21, 2.22, 2.24, 2.33, 2.45
  6. For 200 points, design a context sensitive grammar for the language described in problem 2.42 in the textbook (note: this is tough!)
  7. For 50-500 points, write a 1-2 page essay relating Stanislaw Lem's short story "How the World was Saved" to ideas from this course. The points rewarded will be at the instructor's discretion, but the most points will be rewarded for creative essays that link many ideas from the course and use formal notation whenever possible.
  8. The following problems from the textbook are worth 10 points each: 3.1a, 3.1c, 3.1d, 3.2b, 3.2c,3.2d,3.2e
  9. The following problems from the textbook are worth 20 points each: 3.8b, 3.8c
  10. The following problems from the textbook are worth 30 points each: 3.11, 3.12, 3.13, 3.14.

Insurance Point Challenges (After Exam 2)

  1. The following problems from the textbook are worth 20 points each: 4.10, 4.12, 4.15, 4.19, 4.27, 5.9, 5.33, and 5.34
  2. Solve the following problems using mapping reduction for 20 points each: 5.30a, and 5.30b