| Announcements | | Course information | | Assignments and tests | | Labs | | Lecture outline |
08/12/2009 Please check the marks file and let me know before the final exam if there are any mistakes in it. If you made special arrangements with me because of being sick, the entry for which there is a special arrangement is marked green.
03/12/2009 Study guide for the final exam is now posted.
02/12/2009 The office hours before the final exam will be Friday, Dec 11th, 2pm-5pm. The final exam itself is Dec 14th, 3-5pm, usual classroom.
01/12/2009 There was a mistake in the solutions for assignment 4 (the fuzzy sorting problem.) Please download the updated solutions.
30/11/2009 It is OK to use a Java built-in priority queue for this assignment.
27/11/2009 Solutions to assignment 5, written part, are posted below.
26/11/2009 Solutions to assignment 4 are posted below.
25/11/2009 By popular demand ;-), there will be Lab 11 next Thursday (Dec 3rd). The marks for the best 10 lab out of 11 will be taken.
20/11/2009 Assignment 5 is now posted. Written part due Friday Nov 27th, programming part due Wed Dec 2nd.
13/11/2009 Assignment 4 due date is posponed till Wednesday Nov 18. There will be office hours on Monday 2-3.
06/11/2009 Study guide for the midterm is now posted.
05/11/2009 Solutions to assignment 3 are now posted .
2/11/2009 Assignment 4 is now posted. Due Nov 16th.
02/11/2009 The midterm test will be on Monday, Nov 9th. The class before that,
Friday Nov 6th, is a review for the midterm.
19/10/2009 Assignment 3 is now posted. Due Friday Oct 30th.
15/10/2009 For assignment 2, do not use Java builtin hash table class! The point of the exercise is to develop your own hash table which handles things differently from the default Java class.
14/10/2009 Try your assignment 2 program on the following files: a short file, "Hamlet", a file containing a list of words from "Hamlet". Experiment with a=5,11,37. For n, take 17,47,109 for the short file and 601, 1021, 1823 and 2851 for the large files. Make sure you check for duplicates and don't hash them twice.
07/10/2009 If you would like to read more about the primality testing without randomness, a recent great result in computer science by an indian scientist Manindra Agrawal and its two then-undergraduate students Neeraj Kayal and Nitin Saxena, one good place to start would be the Wikipedia page . A write-up by Scott Aaronson is another good place: it is an easy reading and talks about all sorts of things related to prime numbers, including the primality testing algorithm, cryptography and factoring numbers on quantum computers (which is about the only area where a quantum computer beats a normal one, by the way).
07/10/2009 Assignment 2 is now online. Due Oct 16th.
02/10/2009 Submit is down. So if you haven't submitted electronically, please email the files to me to antonina.kolokolova@gmail.com.
02/10/2009 Due to the problems with submit, you have extra two hours (until 1pm) to submit your assignment electronically. See the next line for updated instructions. Email me if you have any problems!
01/10/2009 To submit the assignment: create a directory comp2711-a1, and in it a subdirectory a1 with your assignment files. Then, from comp2711-a1, run the command:
01/10/2009 Friday Oct 9th classed is canceled. Make-up class on Wednesday Oct 14th at 5pm in EN-1052 (our usual classroom).
28/9/2009 Make sure your program takes input files of this form .
23/9/2009 The office hours will be on Wednesday 2-3pm.
20/9/2009 Assignment 1 is now posted. Due Oct 2nd.
8/9/2009 The labs will start on Sep 17th.
Lectures: 10:00-10:50 Monday, Wednesday and Friday in EN-1052
Instructor: Antonina
Kolokolova , email: [Your browser cannot view this email address] , office ER-6033.
Instructor office hours: W 14:00-15:00
Labs: Thursday morning 900 - 1200 in CS-1019. The lab webpage is here
Textbook: Data Structures and Algorithms in Java (4th Edition) by Michael T. Goodrich and Roberto Tamassia, 2006.
Reference books: Algorithm design. Kleinberg and Tardos,
Introduction to Algorithms
(Second Edition). Cormen, Leiserson, Rivest, and Stein.
Important Information on Account Access, Printing and Java Version
Help Centre Schedule
Marking scheme:
| Assigments | Quizzes | Midterm | Final exam |
|---|---|---|---|
| 5 x 6% = 30% | 10 x 2% = 20% | 1 x 18%= 15% | 1 x 38% = 35% |
Submission Details for All Assignments
| Assignment 1. Due Oct 2nd, 2009. | Assignment 2. Due Oct 16, 2009. | Assignment 3. Due Oct 30, 2009. |
| Assignment 4. Due Nov 16, 2009. | Assignment 5. Due Nov 27th and Dec 2nd, 2009. |
| Week | Topics | Readings (chapters) |
|---|---|---|
| Week 1: | Overview, review, recursion, analysis | 1,2,3,4 |
| Week 2: | Stacks and queues, lists and iterators, Trees | 5,6,7 |
| Week 3: | trees, heaps,priority queues | 7,8 |
| Week 4: | Hash tables | 9 |
| Week 5: | Review of induction | 4.3 |
| Week 6: | Skip lists, binary search trees, AVL trees | 9.4, 10 |
| Week 7: | (2,4) trees, red-black trees, splay trees | 10 |
| Week 8: | Sorting, graphs | 11,13 |
| Week 9: | DFS, BFS, shortest paths, midterm review | 13 |
| Week 10: | Midterm (Nov 9th), minimal spanning trees | 12, 13 |
| Week 11: | Text processing, algorithm design paradigms: greedy algorithms | 13 |
| Week 12: | Text processing and dynamic programming , all-pairs-shortest path. | 12 |
| Week 13: | algorithm case study, review for the final exam. | 3-13 |