Web page contents:

General Information

There is a newsgroup, york.cs.course.4101, that you can use to discuss the course.

Take a look at the departmental guidelines on academic honesty.

Marking Scheme

Announcements

• Apr 26: I have finished marking exams. I will pretend that the exam was out of 40 instead of 44. You can check your UNOFFICIAL grades using courseInfo. If you didn't pick up your assignment, it's in a box outside my office door. In case you're curious: the simplest solution for augmenting the 2-3-4 tree was to add fields that store the min and max elt in the subtree and also the closest pair in the subtree. The subgraph isomorphism problem is NP-hard because the Clique problem is a special case of it. The first approximation algorithm on the exam was bad (approximation ratio infinity for some graphs, e.g. a graph containing 2 vertices and one edge), and the second approximation algorithm works because each iteration removes at most delta+1 vertices from the graph and adds one vertex to the independent set. The bonus question (which *nobody* attempted) actually wasn't very hard; it's easy to prove that any independent set will have size at most n/2 just by considering the edges that go from the vertices in the independent set to those outside the independent set. Putting that together with the hint in part (b) gives the required ratio of (delta+1)/2.
• Apr 20: Assignment 3 has been marked. You can see how you did by typing "courseInfo 4101". I'll bring the assignments to the exam.
• Apr 15: My office hours for next week will be on April 19 and 20 from 1:00 to 2:00.
• Apr 8: My office hours for next week will include April 12 and 13 from 1:00 to 2:00, and possibly other times, depending on demand. If you drop by my office some time and I'm there, you can also ask me questions then.
• Apr 6: Solutions to assignment 3 have been posted below.
• Apr 4: My office hours this week will be held a the usual times: April 5, 1:30-2:30 and Apr 8 11:30-12:30. Check back here for future office hours.
• Apr 1: It seems that question 5 on assignment 3 is a bit harder than I intended it to be. So here's a hint. You can solve the problem in three parts. Note that even if you don't figure out one of the parts, you can still do the others to get partial credit.
  (a) Let's start with a simple example. Suppose the formula you are given is (x implies y) (i.e. (not x or y)). Design a CNF formula F(x,y) involving variables x and y (and some new variable(s)) with the property that a truth value assignment to x and y satisfies (x implies y) iff that truth value assignment can be extended (assigning values to your new variable(s)) to give an assignment that satisfies exactly one literal in each clause of F(x,y).
  (b) Show that (v1 or v2 or v3) is satisfied by a truth value assignment iff it can be extended to give an assignment that satisfies exactly one literal in each clause of (u1 or u2 or u3) and F(u1,v1) and F(u2,v2) and F(u3,v3). (Here, u1, u2 and u3 are new variables.)
  (c) Answer the original question using (a) and (b).
• March 31: You may bring one 8.5 x 11 inch sheet of handwritten notes (written on both sides) into the final exam.
• March 14: My solutions to Assignment 2 have been posted below. I have also posted Assignment 3.
• March 10: Test 2 will focus on material that was discussed during lectures from February 2 to March 10 (inclusive). As with the first test, you can use one 8.5 by 11 sheet of handwritten notes (both sides).
• March 8: Due to popular demand, I have moved the deadline for assignment 2 to Friday, March 12 at 11:30 am. There should be a drop box set up for the course by Friday near the main CS office. Also, test 2 has been moved to March 17.
• March 5: I noticed that the deadline for assignment 2 was listed as Monday, March 10 below. It should have read Wednesday, March 10.
• March 5: Professor Ruppert's office hour on Monday, March 8 is moved to Tuesday March 9, from 11:30-12:30.
• March 4: For question 4(d) on assignment 2, assume you start from an empty tree.
• February 29: You can check my record of your marks from your cs account by typing "courseInfo 4101".
• February 25: The exam schedule has been posted.
• February 25: You will be asked to fill out course evaluation surveys on March 29.
• February 12: My office hour on Mon, Feb 16 is cancelled.
• February 11: In solution to 3(a) of test 1, replace "number" by "sum".
• February 4: Solutions to assignment 1 have been posted below.
• February 2: You can bring one 8.5 x 11 inch sheet of handwritten (not photocopied) notes into your tests.
• January 21: For Q4 on A1, assume m > n.
• January 20: There was a little bug in question 3 of the assignment I handed out yesterday. It's been corrected in the version posted below. Instead of storing the children of a node as a singly-linked list, they will be stored in a super-list (sorted by the keys of those children). The super-list ADT is like a singly-linked list except it also allows fast insertions.
• January 14: A message from the Associate Dean, Michael De Robertis, to senior female undergrads:
  The Dean's Office invites you to attend a presentation by Ms Rena Chenoy from IBM at 10:30-11:30am on Thursday January 22, 2004 in the Bethune Gallery (Room 320 Bethune College). Ms Chenoy will describe to our FPAS community IBM's Women in Technology Initiative. This initiative is an exciting educational program designed to encourage girls from K-12 to consider careers in technology, science and mathematics.
  Through this program, IBM women, as well as female science students (senior undergrad and grad), particularly Computer Science and Engineering students, join forces to reach out to schools at all levels; elementary, middle, and high schools.
  IBM would like to open a Chapter here at York University for this purpose, as it has at four other major universities in Ontario.
  The presentation will last about one hour, with ample time for questions.
  If you are a female student and have ever wanted to share your interest in science with girls and young women, please consider attending. If you have any questions, don't hesitate to contact me at mmdr@yorku.ca
  Thanks very much and hope to see you there,
  Michael
• January 7: I am a coach for York's ACM programming contest team. If you are still going to be a York student next fall (undergrad or grad), you should think about getting involved. Training for next fall's contest will begin soon, with an organizational meeting next week. See this link for details.

Important Dates

Monday, January 5	First class
Monday, January 19	Assignment 1 handed out
Wednesday, February 4	Assignment 1 due
Monday, February 9	Test 1
February 16-20	Reading week (no classes)
Monday, February 23	Assignment 2 handed out
Friday, March 5	Last date to drop course without receiving a grade
Friday, March 12 (at 11:30am)	Assignment 2 due
Wednesday, March 17	Test 2
Wednesday, March 31	Last class
Monday, April 5	Assignment 3 due

Resources

Textbook

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Introduction to Algorithms, 2nd edition, MIT Press & McGraw-Hill, 2001. For known errata, follow this link.

Other References

• Michael R. Garey, and David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Company, 1979.
• Dorit S. Hochbaum, Approximation Algorithms for NP-Hard Problems, PWS Publishing Company, 1997.
• Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Concrete Mathematics: A Foundation for Computer Science (2nd edition), Addison-Wesley, 1994.

Web Links

• Web page for this course the last time I taught it.
• Algorithmics Animation Workshop
• links to web pages on theoretical computer science

Reading

Course Handouts

• Assignment 1
• Dictionary data structures
• Assignment 2
• Assignment 3

Updated June 22, 2004