CS 301—Languages and Automata (Fall 2012)


  • (Wednesday, December 12, 2012) I've got a bad cold today and don't want to make anyone sick during exam week, so I think it would be best if we unfortunately cancel the review session and my office hours today. Please feel free to post any questions you have on Piazza, however, we can happily discuss there together.
  • (December 10, 2012) Please continue to check Piazza in order to see updates to the review session time and location!
  • (Friday, December 7, 2012) Solutions for A6 and A7 have been posted to Blackboard.
  • (Wednesday, December 5, 2012) The practice assignment for the CS301 final has been posted to the course webpage under "Homeworks". Any of the more difficult "prove" questions are just theorems we've seen in class which I wish to make sure you guys know the main tricks behind.
  • (Tuesday, December 4, 2012) As you know, we have reached the end of the official syllabus, and have been voting on Piazza as to what advanced topic to study in our final two lectures: The PCP theorem or quantum computing. Quantum computing won the vote by quite a large margin, so we'll begin discussing it tomorrow in class. Suggested reading is posted to the course website as usual.
  • (Thursday, November 22, 2012) An update to A7 has been posted on the course website - please download the latest version.
  • (Monday, November 19, 2012) The final assignment of the course, A7, has been posted, and is due Friday, November 30, 2012.
  • (Thursday, November 15, 2012) A hint has been added to A6Q5; please download the updated assignment. Note that question 5 is particularly nice, since the ideas behind the proof are very similar to (but much simpler than) those we'll see soon for the Cook-Levin theorem (and in fact even for the quantum version of the Cook-Levin theorem!). In other words, the ideas here will likely serve you well in the future.
  • (Thursday, November 8, 2012) An update to the course project has been posted. Please download this latest version.
  • (Tuesday, November 6, 2012) First, A6 has been posted, and is due Friday, November 16, 2012. It asks you primarily to practice reductions, so that you'll be ready to tackle the magnum opus of this course, Chapter 7 and the theory of NP-completeness, which uses reductions heavily. Second, the course project has been posted (also under Homeworks), and is due Friday, December 7, 2012.
  • (Thursday, October 25, 2012) A5 has been posted, and is due Friday, November 2, 2012.
  • (Tuesday, October 23, 2012) The solutions for A4 are now posted on Blackboard under "Assignments".
  • (Tuesday, October 9, 2012) A practice assignment for next week's midterm has been posted under "Homeworks".
  • (Sunday, September 30, 2012) Two announcements: First, A4 has been posted, and is due Friday, October 12, 2012. Second, A3 solutions have been posted to Blackboard under "Assignments".
  • (Wednesday, September 19, 2012) Two announcements: First, A3 has been posted, and is due Friday, September 28. Second, since there is no assignment due this Friday, September 21, there will be no problem discussion session that day.
  • (Friday, September 14, 2012) The solutions for A2 are now posted on Blackboard under "Assignments".
  • (Monday, September 10, 2012) There has been an update to A2, questions 2c and 2d. Please download the new version of the assignment! (If you have already done the old versions of these questions, you can hand that in, too. Otherwise, please attempt the new versions of the questions instead.)
  • (Monday, September 10, 2012) Starting Wednesday, September 12, my office will be in 1218 SEO.
  • (Sunday, September 9, 2012) Solutions for A1 are now posted on Blackboard under "Assignments".
  • (Thursday, September 6, 2012) Assignment 2 has been posted, and is due Friday, September 14.
  • (Wednesday, September 5, 2012) The problem discussion session this Friday, September 7 will be cancelled, since there is no assignment to discuss this week.
  • (Thursday, August 30, 2012) If you haven't managed to pick up a copy of the textbook yet, I've written up a pdf of the assignment questions. It can be found on Blackboard under Assignments. Blackboard is at blackboard.uic.edu.
  • (Thursday, August 30, 2012) I've received word that there's some interest among students about quantum computing, so for those who are interested, I'd be happy to help in any way I can. Please see my post in Piazza for some recommended reading on the topic. If there's interest, I'm also happy to hold ad-hoc or regular discussion group meetings in person, eg if students wish to read a bit, and then grill me with questions, I'd be happy to.

Course Info

Please see the Syllabus for initial course details, prerequisites, etc.

We are using Piazza for this course for Q&A, discussion, etc. I anticipate using UIC's Blackboard system generally for recording grades but for nothing else.

Remember: Class meets Monday, Wednesday, Friday 11:00 am to 11:50 am, and you are expected to also attend a weekly discussion devoted primarily to homework problems Fridays from 12:00 pm to 12:50 pm.

[Acknowledgement: The content of this course wiki is based on and adapted from that of Prof. Robert Sloan.]

Copyright 2016 The Board of Trustees
of the University of Illinois.webmaster@cs.uic.edu
Helping Women Faculty Advance
Funded by NSF