Computer Science 2711 -- Introduction to Algorithms and Data Structures, Winter 2009

Announcements | Course information | Assignments and tests | Labs | Lecture outline


11/4/2009 The term marks are now available. Please check that all your marks were recorded and calculated correctly! If you notice a mistake, please bring the assignments/quizzes that are missing/wrong to the final, and email me about that. If there is a mistake in calculations, please email me. If you missed an assignment/quiz due to sickness or some such, and talked to me about it, the assignment/quiz mark is moved to the final and the corresponding field in the table is coloured green. If you talked to me about a missed assignment/quiz, but it is not marked on this sheet, please email me immediately.
01/4/2009 Corrected sample files are now available. Please download the new ones.
01/4/2009 Sample files for the assignment 6: a6-1.txt , a6-2.txt and a6-3.txt . For the first, n=4, for the second, n=9 and for the third, n=6. Try clustering them into two and three clusters, and for the second and third file, into 4 clusters.
30/3/2009 Solutions to assignment 5 are now posted. You can use either this algorithm or your own for assignment 6. Your output for the program should consists of lines of the form "Cluster 1: 5,6,8,11" for each cluster.
24/3/2009 The last lab will be next week, April 2nd . The topic of the last lab will be dynamic programming, and the mark for the last quiz replaces your lowest quiz mark. This week lab is on shortest paths and min. spanning trees.
20/3/2009 Assignments 5 and 6 are now posted (one file). Due March 30th and April 6th, respectively.
16/3/2009 If you did not submit a written page with an analysis of performance of your algorithm (part 2 of the assignment), please email it to me right away!
14/3/2009 You don't need to submit printouts of all runs, just say whether polynomial or MAD give you better performance, and if it is for all values of n and both files, and which set of parameters for MAD / polynomial codes give you the best results. Also say if you could get better collision rate for the same n with different parameters.
Type this up as a plain text file (it does not need to be long or pretty), and submit it both printed and with submit-assignment.
11/3/2009 Try your assignment 4 program on the following files: a short file, "Hamlet", a file containing a list of words from "Hamlet". . For polynomial code, experiment with a=5, 11,37. For the MAD, try a=5,37,373 and b=7, 509. As for the values of n, take 17, 47 and 109 for the short file, and 601, 1021, 1823 and 3851 for the large files. Make sure you check for duplicates and don't hash them twice.
09/3/2009 Assignment 4 is changed again (to avoid some java limitations). Please download the latest version. Suggestion: implement polynomial code first. Then, implement MAD as an additional operation after computing polynomial code with a=256 (that is, 2 to the 8th power). To avoid overflows, use modular arithmetic: every time you multiply or add, do these operations mod n.
28/2/2009 Assignment 4 is changed (to make it more interesting). Please download the latest version (with "bag of words" in the title and three parts). 27/2/2009 Assignment 4 is now posted (parameters and test files to be posted later).
27/2/2009 Solutions to assignment 3 are now posted.
26/2/2009 A study guide for the midterm is now available.
Please email me if you notice any mistakes/omissions in it.
26/2/2009 Reminder: midterm next Monday (March 2nd), midterm review this Friday (Feb 27). I will have extra office hours before and after the lecture on Friday. The rest of the lectures next week taught by Tina Yu.
17/2/2009 Assignment 3 is now posted. Due Feb 27th.
02/2/2009 Solutions to assignment 1 are now posted.
26/01/2009 Assignment 2 is now available here . Due Feb 16th. This is a programming assignment, to be submitted both electronically and on paper (at the lecture).
21/1/2009 Correction to assignment 1, question 1b: use BubbleSort instead of MergeSort. Make sure you specify which one you are using, to avoid misunderstandings.
19/1/2009 Assignment 1 is now available here . Due Jan 30th (next Friday). There no programming component in this assignment.
07/01/2009 There will be no lab on Thursday, Jan 8th.

Course information

Lectures: 14:00-14:50 Monday, Wednesday and Friday in EN-1051
Antonina Kolokolova , email: [Your browser cannot view this email address] , office ER-6033.
Instructor office hours: TBA
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 book: 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
6 x 5% = 30% 10 x 2% = 20% 1 x 15%= 15% 1 x 35% = 35%


Assignments and tests

Submission Details for All Assignments

Assignment 1. Due Jan 30, 2009. Assignment 2. Due Feb 16, 2009. Assignment 3. Due Feb 27, 2009.
Assignment 4. Due Mar 16, 2009. Assignments 5 and 6. Due Mar 30/Apr 6.
There may be an assignment due during the last week of classes to ensure that as much of the material as possible appears in the assignments before appearing in the final exam.


Tentative course outline

Some slides handouts

Study guide for the final

Week Topics Readings (chapters)
Week 1: Overview and review, pseudocode, complexity and correctness analysis
Week 2: Recursion, mathematical induction 3,4, appendix A.
Week 3: Stacks and queues, lists and iterators, trees. 4.3,5,6, 7
Week 4: Trees, heaps,priority queues, hash tables, skip lists 7,8,9
Week 5: binary search trees, AVL trees,(2,4) trees, red-black trees, splay trees 10
Week 8: Divide-and-conquer, Sorting 11
Week 7: Sorting, Graphs 11,12
Week 8: Semester break 23th-25th, midterm review 3 to 11
Week 9: Midterm , Text processing (KMP) 12
Week 10: Graphs, 13
Week 11: Greedy algorithms 12.4, 12.3, 13.6, 13.5, Greedy algorithm notes
Week 12: Dynamic programming 12.5, 13.4.2, dynamic programming notes
Week 13: Scheduling case study , Parallel algorithms