| 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.
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% |
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. |
| 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 | |