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

Upcoming Office Hours:

• Apr 5, 3:00-4:00
• Apr 8, 3:00-4:00
• Apr 11, 2:00-3:00
• Apr 13, 2:00-3:00
• Apr 15, 3:00-5:00

Regular Announcements:

• Apr 13: I have finished marking assignment 3. Grades are available through courseInfo. You can pick up the assignments in my office hours. Here is the marking scheme: Q1(a) 1 mark, Q1(b) 4 marks, Q1(c) 3 marks, Q2(a) 1 mark, Q2(b) 2 marks, Q2(c) 3 marks, Q2(d) 1 mark, Q3(a) 1 mark, Q3(b) 5 marks (+ 2 bonus if you solved the original question rather than the simplified one).
• Apr 11: There was a typo in the solution to question 3 for problem set 3. The number of rows in A and in b are m+2k+2, not m+2n+2. (This has been corrected in the copy posted below.)
• Apr 6: Solutions to assignment 3 are posted below.
• Apr 4: For the exam, you are allowed to bring one 8.5x11 inch sheet of handwritten notes (both sides of page).
• Apr 4: Marking scheme for assignment 2:
  Q1: 2 marks, Q2(a): 1 mark, Q2(b): 2 marks, Q2(c): 3 marks, Q2(d): 2 marks, Q3(a): 4 marks, Q3(b): 7 marks (about half for algorithm and half for explanation), Q4: 4 marks. Total 25. I'll post solutions for Assignment 3 here soon.
• Apr 1: For question 3(b) of problem set 3, you will get full credit if you can show that the problem is NP-complete when the elements of b are natural numbers. Those who show that the problem is still NP-complete even when each element of b is -1, 0 or 1 will get a small bonus.
• Mar 30: I will be having office hours between now and the exam, but they probably won't be at the usual time. The times will be posted here. (They partly depend on whether there is a TTC strike.)
• Mar 30: You can bring your 3rd problem set to my office on Monday. If I'm not there, you can slide it under the door.
• Mar 10: Hint for Q2(c) on Assignment 2: You can do query operations on a data structures in between the operations that build it.
• Mar 9: Someone asked for a clarification of Q3a on assignment 2. Abstractly, the deque is just a sequence of elements. You can add/remove elements only at the left and right ends (not the middle). The way it is represented on disk is that there is a series of pages that contain the elements in the order they appear in the deque. The two pages in main memory are used to store a copy of the leftmost disk page and the rightmost disk page. If a page in main memory has become full and you want to add another element at that end of the deque, then you write the page to disk and empty the page in main memory so that you will have space to write the new element. Whenever a page in main memory has become empty and you want to dequeue an element from that end, you read in the leftmost/rightmost page from disk into main memory and dequeue from it.
• Mar 9: For the second test (and the exam), you will be allowed to use one 8.5 x 11 inch sheet of notes, handwritten on both sides.
• Mar 9: Marking scheme for assignment 1. Q1:6, Q2a:3, Q2b:1, Q2c:3, Q3a:1, Q3b:2, Q3c:2, Q3d:3, Q3e:3, Q3f:1, Q4a: 4, Q4b: 4. Total 33.
• Mar 9: Clarification of assignment 2, question 2(c). "the problem" refers to the problem described above part (a): i.e. in (c), you must give an algorithm that finds how many pairs of line segments (out of the n(n-1)/2 pairs of given segments) intersect.
• Mar 5: There was a typo on the solutions to assignment 1. In the induction step of question 4(a), the 4th and 5th sentences should refer to keys, not priorities.
• Mar 5: Clarification of assignment 2, question 1: You don't have to give a formal proof of this. I just want you to explain why you cannot maintain a depth field in the nodes of a red-black tree without affecting the asymptotic running times of DELETES. Your answer can be quite brief.
• Mar 3: Next Wednesday (Mar 9), Ian Munro of the University of Waterloo will be giving a talk, Succinct Data Structures for Trees and Full Text Search, as part of the department's distinguished lecture series. It will be from 1:30 to 2:30pm in CSE3033. I strongly recommend it.
• Mar 3: Course evaluations will be done in class on March 23.
• Feb 22: If, during the term, you want to check my record of your marks, you can use the command "courseInfo 4101" when you are logged into your cs account.
• Feb 14: My office hour on Feb 16 is cancelled.
• Feb 8: Come to the York Programming Contest on Friday, February 11! All students are eligible. The contest will be in CSEB1004 from 14:00 to 16:00, with refreshments afterwards. See this link for further details.
• Feb 1: In the handout containing last year's tests, there is an error in a solution. Replace "number" by "sum" in the solution to question 3(a) of the first test.
• Feb 1: The due date for the first assignment has been moved to February 9.
• Jan 24: Come to the computer science student-faculty forum in lecture hall B of the Computer Science Building on Fri, Feb 4 at 4:30p.m. Key topics include study abroad opportunities, NSERC summer research awards, Women in CSE, ACM programming contest, internship programme, curriculum, CRA Award. You can also contribute thoughts or concerns about the department.
• Jan 17: If you're interested in working at York on a research project next summer, see this link. However, students who will be graduating before Sep 2005 are not eligible.
• Jan 17: The dates for the first test & assignment have been posted below. For the test, you will be allowed to use one 8.5 x 11 inch sheet of notes, handwritten on both sides.

Important Dates

January 3	First class
February 2	Test 1
February 9	Assignment 1 due
February 14-18	Reading week (no classes)
March 4	Last date to drop course without receiving a grade
March 14	Assignment 2 due
March 21	Test 2
March 30	Last class
April 4	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
• Assignment 3 solutions

Updated April 11, 2005