University of the West Indies

Dept. Mathematics and Computer Science

CS20R: Analysis of Algorithms

[Announcements] [Course Information] [Assignments] [Recitations] [Resources]

Welcome to the CS20R home page! This page is intended to be a distribution site for any electronic information relevant to the course. At the moment, it contains little more than links to the content handed out in class. Suggestions for other useful information are welcome.

Note: Most documents have been provided in both HTML, Postscript as well as PDF. The Postscript and PDF files are better suited for printing than the HTML, and for viewing formatted Mathematical expressions.

Announcements

(Apr. 20, 2007) Project 2 has now been posted below.
(Apr. 17, 2007) Recitation 7 has now been posted below.
(Apr. 11, 2007) Project 1 has now been posted. It is due next week Tuesday. Please look at it for tutorial.
(Mar. 22, 2007) Assignment 2 has now been posted.
(Mar. 9, 2007) Recitation 6 is now available. See the links below.
(Mar. 9, 2007) Midterms have been marked. As soon as the grades are recorded they will be made available in the lab.
(Mar. 2, 2007) Assignment 1 Solutions have been posted. Please ignore the HTML version, as it seems to be completely broken (all the answers are missing). Use the PDF or Postscript versions instead. Don't forget about your in-course test later today.
(Feb. 27, 2007) Recitation 5 has now been posted.
(Feb. 16, 2007) Recitation 4 has now been posted. See it below to prepare for next week.
(Feb. 16, 2007) The mid-term test has been set for Friday, March 2, 2007 at 3pm in the Old Dramatic Theatre. Its duration is 1 hour.
(Feb. 13, 2007) Assignment 1 has now been posted below. Note that it is due next week Friday.
(Feb. 12, 2007) Recitation 3 has now been posted below.
(Jan. 30, 2007) Recitation 2 has now been posted below. The greater part of it is the same as one of the questions in Rectitation 1. This is to give those of you who missed your recitation an opportunity to catch up. There are also a few practise problems on the Master Theorem.
(Jan. 23, 2007) Recitation 1 has now been posted. The recitation signup sheets are also now available. Please sign up for only one slot. For this week, you may attend any one of them, but as of next week, please attend the one that you have signed up for.
(Jan. 15, 2007) Please be sure to read the course description and guidelines posted below. It contains very important information about the course.

Course Information

Course Description HTML | PDF | Postscript

Assignments

Assignment 1 HTML | PDF | Postscript
Assignment 1 Solutions HTML | PDF | Postscript
Assignment 2 HTML | PDF | Postscript
Project 1 HTML | PDF | Postscript
Download the starting code.
Project 2 HTML | PDF | Postscript
Download the starting code.
In case you need the cup.jar file, download it here.
I originally forgot to include two sample graph files in the samples directory of the zip file that I distributed. They are called graph1.txt and graph2.txt. These are text files describing two simple graphs, that make it easy for you to test your implementations. You can load them by clicking the LOAD button and then using the file browser that pops up to navigate to the file of your choice.
A number of persons have been asking for the GraphTraversal.java source, so you can now get it here. I do not recommend that you try to read this unless you cannot find another way to solve the problem. Instead, you should be consulting the graph-docs/TraversalStrategy.java documentation, provided in the zip file for the project, for an explanation of when each method that you have to implement in your TraversalStrategy instantiations gets called. You can also view the source for the Forest.java file, in case it can help you to debug. (Again, you shouldn't need it, but it's provided in case you prefer to read source code to documentation.)

Recitations

Recitation 1. An example worked from problem specification through to time complexity analysis. HTML | PDF | Postscript
Recitation 2. The harder part of Recitation 1 and some Master Theorem practice. HTML | PDF | Postscript
Recitation 3. Master Theorem and ADTs. HTML | PDF | Postscript
Recitation 4. Binary Heaps and Binary Search Trees. HTML | PDF | Postscript
Recitation 5. Red-Black Trees and Hashing. HTML | PDF | Postscript
Recitation 6. Sorting. HTML | PDF | Postscript
Recitation 7. Graphs. HTML | PDF | Postscript

Lecture Notes

Transcript of *scheme* buffer that was developed in lecture while demonstrating basic sheme expressions.

The notes included below are somewhat weak, and your mileage may vary.

Notes on Scheme evaluation.
Notes on Properties of Orders of Growth
Notes on Recurrence Relations

Exams

2006 Exams coming soon!
CS20A 2005 midterm (PDF)
CS20A 2005 Final exam (PDF)
CS20A 2005 Summer exam (PDF)

Resources

Quick and dirty instructions for using Emacs with Scheme. You should note that many of the key strokes described will also work with other programming languages as well, so these are pretty useful if you plan to use Emacs as a general purpose editor (and not just one for Scheme).
HTML | Postscript | PDF Notes on using Scheme in the lab (originally written for CS20A, but still mostly relevant)
(Incomplete) Manual for CS20A. This manual covers everything needed for CS20R, except the latter part of graphs and complexity theory. Be careful though, there are a few known bugs that still need fixing.