APM 381, Theory of Computation, 4 credits—Winter 2007

• Detailed syllabus for the course.
• Place and Time: Tue, Thu at 3:30–5:17 PM in DHE 237.
• Office hours: Mon, Wed 3–4 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 would like a one-to-one meeting, 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 can be found at Amazon.com for the second or the third edition. I expect you to have a copy of this textbook.

• 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). If you get a failing grade on an assignment, you will need to resubmit the assignment, make an appointment with me, and explain the solution for the problems of my choice to my satisfaction. 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 WebCT.
  • Homework Assignment #4. Due date: Thursday, Apr 12, 2007
  • Homework Assignment #3. Due date: Tuesday, Mar 27, 2007
  • Homework Assignment #2. Due date: Tuesday, Feb 13, 2007
  • Homework Assignment #1. Due date: Tuesday, Jan 30, 2007

• Midterm Exam:
  First draft due date: Tuesday, Feb 20, 2007
  Final version due date: Tuesday, Mar 6, 2007
  This is a take-home midterm exam worth 50% of the final grade. You can use any written material, and you may consult me and your classmates about the exam. After submitting, you will need to make an appointment with me in which you explain your solutions for some of the problems of my choice. Your grade on the exam will be based on your written solutions and your oral explanations.
  Grades will be available on WebCT.
  

• Final Exam:
  The Final Examination is comprehensive. It will be given on Friday, April 20, 2007, 3:30–6:30 PM and will be worth 50% of the final grade. Calculators or notes will not be allowed.
  Grades will be available on WebCT.
  Review of topics for the Final Exam.

• Grading Policy:
  Your course grade will depend on the Midterm and the Final Exam as indicated in the syllabus.

• Material covered: (section and page numbers are from the third edition):

  Week	Dates	Material covered	Section
  1	Jan 1–5	Discussion of syllabus Proof techniques	Sections 1.1–1.4, pages 3–28 Sections 2.1–2.5, pages 43–72
  2	Jan 8–12	Languages Regular Languages and Finite Automata (FA)	Section 1.5, pages 28–32 Sections 3.1–3.3, pages 85–105
  3	Jan 15–19	Distinguishing one string from another Nondeterministic FA, HW #1	Sections 3.4–3.5, pages 105–112 Section 4.1, pages 123–133
  4	Jan 22–26	Nondeterministic FA with Lambda-transitions Kleene's Theorem	Sections 4.2–4.3, pages 133–154
  5	Jan 29–Feb 2	Minimal FA Pumping Lemma for regular languages, HW #2	Sections 5.1–5.2, pages 168–179 Sections 5.3–5.5, pages 180–191
  6	Feb 5–9	Context-free grammars Regular grammars	Sections 6.1–6.2, pages 203–217 Section 6.3, pages 217–220
  7	Feb 12–16	Derivation trees and ambiguity Pushdown Automata, DPDA, Midterm Exam	Sections 6.4–6.5, pages 220–237 Sections 7.1–7.3, pages 251–263
  8	Feb 19–23	pal is not DCFL PDA = CFG	Section 7.3, pages 264–265 Sections 7.4–7.5, pages 265–280
  9	Feb 26–Mar 2	Winter Break	-
  10	Mar 5–9	Pumping lemma for CFL's	Section 8.1, pages 297–304
  11	Mar 12–16	Instersections, complements, and decision problems of CFL's Turing Machines, HW #3	Sections 8.2–8.3, pages 306–312 Section 9.1, pages 319–327
  12	Mar 19–23	Combining TM's, Multitape TM's Nondeterministic TM's, Universal TM's	Sections 9.3–9.4, pages 332–341 Sections 9.5–9.6, pages 341–352
  13	Mar 26–30	Recursive and recursively enumerable languages Unrestricted grammars A nonrecursive language, HW #4	Sections 10.1–10.3, pages 365–380 Section 10.5, pages 387–397 Section 11.1, pages 407–410
  14	Apr 2–6	Unsolvable problems Growth rates of functions Time and Space complexity of TM's	Sections 11.1–11.4, pages 410–422 Sections 13.1–13.2, pages 481–492
  15	Apr 9–13	P and NP Polynomial-time reductions and NP-completeness Cook's Theorem, Review	Sections 14.1–14.3, pages 500–517
  16	Apr 16–20	NP-complete Problems	Section 14.4, pages 517–522

• Recommended exercises:
  Note: these are a lot. It is not necessary to solve all of them. Pick some until you feel confident you know what is going on.
  • Section 1, Pages 32–42: 1, 4, 5, 7, 8, 11, 13, 17, 19, 22, 23, 29, 30, 33, 39, 41, 45–47, 51, 53, 55, 57, 68, 71.
  • Section 2, Pages 72–81: 1, 3, 8, 13–14, 17–18, 22, 24, 25, 27, 36, 39, 43, 46, 53, 55, 58–59, 61–62, 65, 67–68.
  • Section 3, Pages 112–122: 1, 3–4, 6–7, 9, 11–12, 17–19, 21–22, 24, 26, 29–30, 33, 36, 41, 44.
  • Section 4, Pages 156–167: 1–2, 4, 8, 10–13, 16, 19–20, 24–25, 28, 38–42.
  • Section 5, Pages 191–200: 2, 4, 6, 8, 13, 16, 19–20, 24, 26–28, 34, 40, 47.
  • Section 6, Pages 240–250: 1, 4–6, 9–10, 13–14, 21, 23, 36–38, 41, 43, 45, 51, 58.
  • Section 7, Pages 290–296: 1, 5–7, 9–10, 13–14, 19, 38, 42.
  • Section 8, Pages 312–315: 1, 5, 8, 10–11, 14.
  • Section 9, Pages 354–364: 2, 3, 6, 11, 13, 16–17, 24, 29–30, 39–40.
  • Section 10, Pages 397–404: 3, 7, 9, 11, 13, 25, 27, 31, 34, 41, 48.
  • Section 11, Pages 436–441: 3, 6, 8, 12, 14, 21, 31, 34.
  • Section 13, Pages 497–499: 1, 2, 4–6, 20.
  • Section 14, Pages 522–526: 4, 7, 11, 15–16, 18, 22, 25.

• 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 proofs of 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.
  • 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.