APM 581, Theory of Computation, 4 credits—Winter 2008

• Detailed syllabus for the course.
• Place and Time: Tue, Thu at 7:30–9:17 PM in DHE 204.
• Office hours: Wed 1–2 PM, or by appointment (SEB 347).
  During office hours I let everyone who showed up into my office and discuss questions in a round-robin manner. If you need to see me outside regular office hours, ask or e-mail me to set up an appointment.
• Textbook: Introduction to Languages and the Theory of Computation, by John C. Martin (second or third edition, WCB/McGraw-Hill, 1997). (Used copies of the second edition can be found at Amazon.com.)
  
  
• Final Grade: Your course grade will be based on the presentation of your project and on the scores you achieve on the homework assignments. For details see the syllabus.
  Results will be available on Moodle.
  
  
• Project: There will be a term project instead of a final exam. You will choose among the hundreds of research papers in Complexity Theory proving that a given problem is NP-complete, read the paper, digest the material, and present the main result in class, on slides, during the last couple of weeks of the term. You will have to choose the paper by the end of February and I must approve it.
  Your presentation must:
  • Have a handout (1–2 pages) with the main definitions and concepts (So we can more easily follow the proof)
  • Present the problem with examples (So everyone in the class understands the problem)
  • Present the context of the problem (Why do we care? Any applications?)
  • Present the proof of NP-completeness
  • Answer all questions from the audience
  
  To find papers, go to MathSciNet (use an OU machine to have access) and search for entries with ``np-complete" in the titles. (There are more than 250 of them.) Then read the abstracts, select a few that seem interesting to you, and bring me a copy of one (or more) paper you are considering.
  After the presentations are all done, everyone will be required to submit evaluation of everybody else's presentation, and I will have a discussion with everyone individually.
  
  
• Tests and Final Exam: There will be no tests or final exam in this course.
  
  
• Homework assignments:
  Your solutions should be nicely presented. Write as clearly and cleanly as you can, use sentences, and explain the steps of the solution. I encourage you to work in groups and discuss the problems and their solutions with each other. However, the actual solutions you submit should be your own work (see Academic honesty for more info). In most cases I will allow you to resubmit problems of the homework assignments to improve your score (when you do that, attach the already graded version of the assignment to your new solutions). Solutions for homework assignment problems will rarely be discussed in class. If you have questions about the homework, ask me. Results will be available on Moodle.
  • Homework Assignment #5. Due date: Thursday, Apr 3, 2008
  • Homework Assignment #4. Due date: Tuesday, Mar 18, 2008
  • Homework Assignment #3. Due date: Thursday, Mar 6, 2008
  • Homework Assignment #2. Due date: Thursday, Feb 14, 2008
  • Homework Assignment #1. Due date: Tuesday, Jan 29, 2008
  
  
• Recommended exercises: (from the second edition; if given, the corresponding third edition problems are in parentheses)
  • Section 1, Pages 30–35: 1, 3, 5, 6, 8–12, 14, 17–19, 23, 42, 43, 46, 48–51. (most of these are just to refresh the basics)
  • Section 2, Pages 63–67: 1, 2, 4–6, 8, 13, 14, 26, 29, 41, 44, 45.
  • Section 3, Pages 92–97: 1, 4, 6–8, 13, 16, 23, 25–27, 31, 37.
  • Section 4, Pages 126–133: 1, 4, 5, 8, 9, 11–14, 16, 21, 31, 41.
  • Section 5, Pages 154–158: 1, 4–6, 10, 17, 24, 27, 31, 34.
  • Section 6, Pages 191–196: 1, 4–7, 10, 13, 14, 17, 22, 23, 29, 35, 36.
  • Section 7, Pages 232–236: 1, 5–7, 9, 12, 14, 19, 35, 39.
  • Section 8, Pages 251–253: 1, 5, 6, 10, 14, 16, 20*.
  • Section 9, Pages 285–293: 2, 3, 5, 6, 13, 16, 19, 25, 33, 50 (2, 3, 7, 13, 16, 19, 24, 29, 52).
  • Section 10, Pages 306–309: 3, 5, 9, 15, 25, 26 (4, 27, 34, 37, 39, 49).
  • Section 14, Pages 410–411: 1, 2, 4, 5, 7, 14 (Section 13: 1, 2, 4, 6, 20, 25).
  • Section 15, Pages 433–434: 6, 10, 12, 15, 20, 22, 23, 25 (Section 14: 4, 7, 11, 15, 16, 18, 22, 25).
  
  
• Material covered: (section and page numbers are from the third edition):
  Week 15: (Apr 14–18)
  • Presentations of project by Hesiri and Philip (Tue)
    Presentations of project by Priya and Tom (Thu)
  Week 14: (Apr 7–11)
  • Presentation of project by Scott (Tue)
    Presentations of project by Yung-Hsuan and Joe (Thu)
  Week 13: (Mar 31–Apr 4)
  • Cook's Theorem: Sections 14.3, pages 510–517
    More NP-complete Problems: Section 14.4, pages 517–522
  Week 12: (Mar 24–28)
  • Complexity classes of TM's: Section 13.3, pages 492–497
    P and NP, Polynomial-time reductions and NP-completeness: Sections 14.1–14.2, pages 500–510
    Suggestions for your presentation
    
  Week 11: (Mar 17–21)
  • Unsolvable problems: Sections 11.1–11.4, pages 407–422
    Homework Assignment #5
    Growth rates of functions, Time and Space complexity of TM's: Sections 13.1–13.2, pages 481–492
  Week 10: (Mar 10–14)
  • Unrestricted grammars: Section 10.3, pages 371–380
    Recursive and recursively enumerable languages: Section 10.1, pages 365–368
    Enumerating Languages, Not all languages are recursively enumerable: Sections 10.2 and 10.5, pages 368–371 and 387–397
  Week 9: (Mar 3–7)
  • Computing partial functions: Section 9.2, pages 328–332
    Nondeterministic TM's, Universal TM's: Sections 9.5–9.6, pages 341–352
    Homework Assignment #4
  Week 8: (Feb 25–29)
  • Winter Break: No classes
  Week 7: (Feb 18–22)
  • Turing Machines: Section 9.1, pages 319–327
    Summary of P, NP, NP-completeness for the project
    Combining TM's, Multitape TM's: Sections 9.3–9.4, pages 332–341
  Week 6: (Feb 11–15)
  • PDA = CFG: Sections 7.4–7.5, pages 265–280
    Parsing: Section 7.6, pages 280–290 (self-study)
    Pumping lemma for PDA: Sections 8.1–8.2, pages 297–306
    Instersections and Complements of CFL's: Section 8.2, pages 306–311
    Homework Assignment #3
  Week 5: (Feb 4–8)
  • Pushdown Automata, DPDA: Sections 7.1–7.3, pages 251–265.
  Week 4: (Jan 28–Feb 1)
  • Homework Assignment #2
    Context-free grammars: Sections 6.1–6.2, pages 203–217
    Regular grammars, Ambiguity: Sections 6.3–6.6, pages 217–239
  Week 3: (Jan 21–25)
  • Kleene's Theorem: Section 4.3, pages 145–154
    Minimal FA's: Sections 5.1–5.2, pages 168–179
    Pumping Lemma for regular languages: Sections 5.3–5.5, pages 180–191
  Week 2: (Jan 14–18)
  • Distinguishing one string from another: Sections 3.4–3.5, pages 105–112
    Nondeterministic finite automata: Section 4.1, pages 123–133
    Nondeterministic finite automata with lambda-transitions: Section 4.2, pages 133–145
  Week 1: (Jan 7–11)
  • Basic Mathematical Objects: Sections 1.1–1.4, pages 3–28 (self-study)
    Mathematical Induction and Recursive Definitions: Sections 2.1–2.5, pages 43–72
    Languages: Section 1.5, pages 28–32
    Regular Languages and Finite Automata: Sections 3.1–3.3, pages 85–105
    Homework Assignment #1
  
  
• Academic honesty:
  Cheating is a serious academic crime. Oakland University policy requires that all suspected instances of cheating be reported to the Academic Conduct Committee for adjudication. Anyone found guilty of cheating in this course will receive a course grade of 0.0 in addition to any penalty assigned by the Academic Conduct Committee. Working with others on a homework assignment does not constitute cheating; handing in an assignment that has essentially been copied from someone else or from a solutions manual does. Receiving help from someone else (except possibly me) or from unauthorized written material during a quiz, test, or final exam is also cheating.
  
  
• Study habits:
  I can only guide and help you by providing the framework for the course: you are responsible to learn the material. Most of this learning must take place outside the classroom. This will usually take two to three hours outside of class for each hour in class, but may take longer in some cases. Our aim is to be able to apply the material to new situations, hence the focus is on understanding rather than memorizing. How can you achieve that?
  
  • Read the textbook: this must be done carefully and slowly. You may need to re-read and analyze sentences, since the text is very dense, unlike a novel. You should have pencil and paper ready to work with while reading to draw pictures and fill in omitted steps. Understand and learn the definitions and the important theorems. Whenever possible, read the relevant sections before we discuss them.
  • Ask questions: in class, during office hours or an appointment. If you have difficulties, get it clarified as soon as possible. If you make a mistake, rework the problem with the idea that you will not make similar mistakes later.
  • Do the homework assignments: after you get feedback on any assignments, clarify any questions, and resubmit incorrect solutions when allowed.
  • Review the material regularly: It will take time and practice to digest and really understand the new concepts and theorems.
  • Study with others: if you can, discuss solutions to problems with your classmates, e.g. in study groups.