News
- 7 May: Final Exam Comments (including drawing!)
- 29 April: Class 26 (Computing Genomes, Genomes Computing): [PPT] [PDF]
- 29 April: Where to Go From Here; Final Exam Preview
- 29 April: PS6 Comments
- 24 April: Class 25 (Security through Complexity?): [PPT] [PDF] (Karsten Nohl)
- 23 April: Thursday's class will be a guest lecture by Karsten Nohl, a Computer Engineering PhD student, about complexity classes and cryptography. As a preview, you can read some of the media accounts of his cryptanalysis work here (for example, RFID hack could crack open 2 billion smart cards, ComputerWorld, 14 March 2008).
- 23 April: This comic may provide some much-needed inspiration for
PS6:
(Thanks to Rachel Kammerer for finding the comic.) - 22 April: Class 24 (P = NP?): [PPT] [PDF]
- 22 April: Exam 2 Remaining Comments
- 17 April: Class 23 (NP-Completeness): [PPT] [PDF] (Isabelle Stanton)
- 17 April: Here are links to the papers that will be distributed in
class today:
- March Madness is (NP-)Hard by David Liben-Nowell, Moses Liskov, Chris Peikert, Abhi Shelat, Adam Smith, and Grant Wang.
- Pancakes, Puzzles, and Polynomials: Cracking the Cracker Barrel by Christopher Frost, Michael Peck, and David Evans. ACM SIGACT News, March 2004. (Chris and Mike did this as an independent study project while they were UVa 3rd-year students.) [Website]
- Some Minesweeper Configurations by Richard Kaye. [Website]
- The Complexity of Songs, Donald E. Knuth, Communications of the ACM, April 1984.
- 15 April: Class 22 (Complexity Classes): [PPT] [PDF]
- 15 April: Problem Set 6 (due April 24)
- 11 April: From now on, my Wednesday morning "coffee" hours will be held in my office, Olsson 236A (9:30-10:30am Wednesdays). This Wednesday (16 April), my office hours will be 10-11am (instead of the usual time).
- 10 April: Class 21 (Introducing Complexity): [PPT] [PDF]
- 8 April: Exam 2
- 5 April: Class 20 (Yan Huang) (Lambda Calculus and Computability): [PPT] [PDF] [Notes]
- 5 April: A draft of the PS5 comments is now available: PS5 Comments (an updated version will be posted after we finish grading them, but this is being made available now to help you prepare for Exam 2)
- 2 April: Exam 2 Study Guide
- 1 April: Class 19 (Undecidability in Theory and Practice) [PPT] [PDF]
- 25 March: Class 18 (Important Undecidable Problems) [PPT] [PDF]
- 25 March: PS4 Comments
- 25 March: Class 17 (Proving Undecidability) [PPT] [PDF]
- 24 March: Some people have still not picked up Exam 1! As mentioned in class last week, I am now charging storage fees for holding them. In addition to these fees, I assume that that anyone who does not bother to pick up Exam 1 before Exam 2 must not care at all about their grade in this course or the feedback we provide in grading exams and problem sets, so we will not bother to grade your Exam 2.
- 22 March: Problem Set 5 is now available
- 20 March: Class 16 (Universality and Undecidability) [PPT] [PDF]
- 18 March: Class 15 (Robustness of TM Model) (Qi Mi) [PPT] [PDF]
- 16 March: Problem Set 4 will be accepted without penalty at the beginning of Thursday's (20 March) class.
- 13 March: Class 14 (Church-Turing Thesis) [PPT] [PDF] (corrected: 15 March)
- 12 March: Corrected Exam 1 Comments
- 11 March: Class 13 (Turing Machines) [PPT] [PDF]
- 11 March: Exam 1 Comments, Problem Set 4 (due 18 March)
- 7 March: Here are the slides from Pieter Hooimeijer's class on Indexed Grammars (26 February) slides: [PDF]
- 7 March: We have four winning solutions to the Lww complement challenge problem! They all prove the same property, but in interestingly different ways: Ian Davey's Proof, Raghavendra Rajkumar's Proof, Ruixin Yang's Proof, and Liuyi Zhang's Proof.
- 29 February: The reading for Spring Break is Scott Aaronson's article, The Limits of Quantum Computers from the March 2008 Scientific American (not available freely electronically). You may also want to read Scott Aaronson's blog post about the article.
- 22 February: Exam 1 Study Guide
- 22 February: PS3 Comments
- 21 February: Class 11 (Parsimonious Parsing) [PPT] [PDF]
- 20 February: Next week's office hours will be in Olsson 226D (back corner conference room) at the usual times (Monday, 2-3pm; Wednesday 9:30-10:30am). I am away Monday-Wednesday, but Qi Mi will be holding the office hours at my usual office hour times.
- 19 February: Class 10 [PPT] [PDF]
- 19 February: The drawing of the state machine in the PS2 comments for question 2c is wrong - the start state is marked as accepting, but it should not be an accepting state (note that the empty string is not in the language, so start can definitely not be accepting!)
- 18 February: Wednesday's TA session will be in Olsson 226D (instead of 228E)
- 16 February: There is a bad mistake in the DPDA for Problem 7. The
DPDA we meant to use is:
- 16 February: There is a typo in question 6c. Instead of "still value expressions" it should read, "still valid expressions". After the change you make for question 6c, the grammar should generate the same exact language as before, but because of the changes you make expressions should be parsed differently to change the value of the given expression.
- 14 February: Class 9: CFL Notes
- 12 February: Class 8: PDF
- 12 February: Problem Set 3; PS2 Comments
- 12 February:
Rich First-Grader Buys Whole Sheet Of Gold Stars, from The Onion:
BREMERTON, WA — Lakeside Elementary first-grader Max Carr, son of Boeing CEO Robert Carr, used a small portion of his $100 weekly allowance Monday to buy himself a sheet of the gold stars used to reward academic achievement. "I don't get why all the kids work so hard to get good grades just for a sticker," Carr said. "I only got a C-minus on my phonics homework, but Mommy took me to the mall, and now I have 10 gold stars — more than anybody in the whole class." Carr said his "dumb classmates have no idea" that students can simply purchase a sheet of "Great Job!" Mickey Mouse stickers at a store.
- 8 February: There's an interesting article in American Scientist on
the limits of computation including the P = NP? question which we will
encounter later in the class: Accidental
Algorithms: A strange new family of algorithms probes the boundary
between easy and hard problems.
Suggesting that P might be equal to NP is deeply unfashionable. A few years ago William Gasarch of the University of Maryland took a poll on the question. Of 100 respondents, only nine stood on the side of P = NP, and Gasarch reported that some of them took the position "just to be contrary". The idea that all NP problems have easy solutions seems too good to be true, an exercise in wishful thinking; it would be miraculous if we lived in a universe where computing is so effortless. But the miracle argument cuts both ways: For NP to remain aloof from P, we have to believe that not even one out of all those thousands of NP-complete problems has an efficient solution.
(Note that a poll is not a proof, even if 91% of respondents agree.) - 7 February: Class 7: Nondeterministic Pushdown Automata Notes
- 5 February: Class 6: Deterministic Pushdown Automata Notes. Here is a link to the video with the challenge question in it: http://www.youtube.com/watch?v=1nnj7r1wCD4 (the question appears after 6:30 in the video). Although Senator Obama's answer is better than good enough for a presidential candidate, to win the challenge question your answer must be a satisfactory solution to the problem. See the email for more details. This article describes the question: Obama Passes His Google Interview, Wired Blog, November 14, 2007.
- 5 February: The solution in the PS1 comments for Problem 6 is wrong! Liuyi Zhang cleverly noticed that the question does not require the cuts be perpendicular to the bottom of the pie, and that you can obtain more pieces by angling the cuts. He proved that in fact, you can produce (n3+5n+6)/6 pieces using n cuts! Here is his proof (including some 3D drawing of the slides): 3D Pie Slicing
- 31 January: Class 5: Pumping Lemma (and Proofs) Notes; PS1 Comments
- 30 January: Starting next week, the problem-solving sessions will move to Olson 228E (which is a larger conference room). This evenings problem-solving session will still be held in Olsson 226D.
- 29 January: Class 4: NFA Notes; Problem Set 2
- 24 January: Class 3: DFA Notes
- 24 January: There was some concern raised in Tuesday's class that there might not be enough gold stars available to support a class this big. Fear not: Bush Earmarks 1.5 Billion Gold Stars For Education (The Onion)
- 22 January: Problem Set 1; Slides [PDF, PPT]
- 21 January: The TAs' problem solving sessions will be held Mondays (5:30-6:30pm) and Wednesday (6-7pm) in Olsson 226D (the back corner conference room).
- 17 January: Class 1 (abhi shelat): Slides [PDF]
- 16 January: There is a Google calendar for cs302. To subscribe, click cs302 Google calendar.
- 16 January: Course Syllabus [PDF]
- 16 January: Please submit a registration survey before 5pm Sunday, 20 January.
- Spring semester courses start January 16.
- The textbook for the course is:
Michael Sipser, Introduction to the
Theory of Computation (Second Edition). [Amazon
($102.13)]
Other recommended books include:
Thomas Sudkamp. Languages and Machines: An Introduction to the Theory of Computer Science.
John Hopcroft, Rajeev Motowani, and Jeffrey Ullman. Automata Theory, Languages, and Computation.
- 25 October: This 2-state, 3-symbol Turing machine:
is universal! This is a very amazing result, that was proven by an undergraduate student in England to win the Wolfram Research Prize. We'll talk about what this means and what the implications of it are in later in the course. Some articles about this:- A New Kind of Science Author Pays Brainy Undergrad $25,000 for Identifying Simplest Computer, Scientific American, October 25, 2007.
- Simplicity sought for complex computing, Chicago Tribune, November 19, 2007.
- iPod Mathematical Riddle Solved, NPR (podcast), November 10, 2007.
Past Schedule
- Sunday, 20 January (5pm): Registration Survey Due
- before 29 January: Read Sipser, Chapter 0 and Section 1.1
- Tuesday, 29 January (2:02pm): Problem Set 1
- Thursday, 7 February (2:02pm): Problem Set 2
- Before Tuesday, 12 February: Finish reading Sipser, Chapter 2
- Tuesday, 19 February (2:02pm): Problem Set 3
- Thursday, 28 February: Exam 1 (in class). For exam 1, you may bring one page (one side) of notes, but may not use any other materials.
- Tuesday, 11 March: Finish Spring Break reading.
- Week of March 11: Read Sipser, Chapter 3.
- Monday, 17 March: I will not be able to hold my normal office hours Monday (I am out of town). The TAs normally scheduled Problem Solving Session will be held, 5:30-6:30 in Olsson 228E.
-
Tuesday, 18 MarchThursday, 20 March (2:02pm): Problem Set 4 - Monday, 31 April: The normally scheduled office hours will be held by Qi Mi in Olsson 226D, 2-3pm Monday. The TA help sessions will be held as normal Monday evening Monday (5:30-6:30pm) and Wednesday (6-7pm) in Olsson 228E. My office hours for Wednesday morning are cancelled as I will be out of town.
- Tuesday, 1 April (2:02pm): Problem Set 5
- Tuesday, 8 April: Exam 2
- Tuesday, 15 April: Exam 2 Revisions (due at beginning of class)
- Week of April 14: Read Sipser, Chapter 7 (through 7.3)
- Thursday, 24 April: Problem Set 6
- Wednesday, 30 April (6pm, Olsson 228E): Group review session (run by students, no staff will be there)
- Monday, 5:30-6:30pm (Olsson 228E): Last ACs help session
- Wednesday, 9:30-10:30am (Olsson 236A): Last scheduled office hours
- Thursday, 1 May (5-6pm, Olsson 236D): Assistant Coaches' review session
- Saturday, 3 May (9am-noon): Final Exam