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

(Jun 8, 2006)Here is a (still unofficial) list of your final grades. You will know they have become official when you see them on your on-line records.
(May 26, 2006) CS20R is offered in Summer School, and some of you may be wondering whether you need to think about registering for it. You may check here for a Provisional Pass/Fail List based on your Exam Grade Only. Note that coursework marks have not yet been incorporated into these provisional results, therefore you can be sure you have failed only if you actually see an F beside your ID number. You cannot tell for certain whether you have passed the course from this list. NB: These grades have not yet been approved at an Examiner's meeting, therefore they are not official, and are still subject to change. It has been provided merely as an indicator for whether you are likely to have passed this course or not.
(May 15, 2006) Many of you have complained about your Project 1 grades that you believe they are lower than you deserve. In response, Ricardo Anderson has agreed to meet with those of you who have grievances about how Project 1 was assessed to discuss these issues. He is making himself available on Wednesday, May 17 at 12 - 3 pm and also on Thursday afternoon for those of you who can come only after working hours. (Specific times for Thursday to be announced). If you have issues with your Project 1 grade and Ricardo assessed it, please use this opportunity to clarify them. I will not be able to help you out if you come to me afterwards with this complaint, because I have no way of knowing how you performed in your checkoff session.
(May 9, 2006) I have created a class called DictGen that should make it a little easier for you to create dictionaries for doing Problem 3 of the project. You can download it from the link below (or just fetch it here).
(May 8, 2006) The marked Assignment 2 papers have (finally) been returned. You can pick them up from the usual place. You can also view the results I have for you so far here.
(May 8, 2006) Project 2 Submission Instructions: On the submission page there are three slots.
1. The first is for a plain text file (no Word or other formatted files please) containing the members of your group.
2. The second is for the code from Problems 1 and 2. Zip all of your Java files from your working directory in a flat zip file. You do not need to include the graph.jar file that I gave you, nor the dictionaries, although you should include any dictionaries that you created. Use esub2 to submit your zipped project.
3. The third slot is for Problem 3. Submit a file containing your time complexity analysis along with all the evidence you used to come to your conclusions. If you need to submit more than one file, zip all the relevant information together and submit that. This file will be manually read.
(May 3, 2006) Documentation for the graph package has now been posted on this page. You may browse it from this page, if you are unsure how to create your own version using javadoc.
(Apr 28, 2006) It turns out that the revised Problem 3 of Assignment 3, although clearer than the first version, was probably unreasonably difficult to do; so I have revised it. It is now quite reasonable, and should be within your grasp if you try hard enough (i.e. This time, I've actually done it myself, so I know that it can be done). Please make sure to download the newest version of Assignment 3.
(Apr 26, 2006) I have now updated the coursework marks with the results from Project 1. I expect that I will have the results for Assignment 2 up by Monday. You should view the grades I have for you and report any anomalies as soon as possible.
(Apr 21, 2006) As promised, I have modified Problem 3a of Assignment 3. Please refetch the assignment to get the updated version of the question.
(Apr 21, 2006) The due dates for Assignment 3 / Project 2 have been extended to May 8, 2006. When the time for submission draws near, you should pay very special attention to the instructions, because there may be very little room for errors in submission.
(Apr 21, 2006) You may now review the grades that I have recorded for you so far. Please bring any corrections to me as soon as possible.
(Apr 20, 2006) The graded Assignment 1 scripts have been returned in the lab. Please collect yours and review it for any corrections. If you have objections or corrections to be made, please think them through before bringing them to me. I don't mind correcting obvious errors, nor explaining why full marks were not given for a particular response, but please don't ask me to remark a question. If you believe something is unfairly marked, then be prepared to explain why you believe your response deserves more than it was given.
(Apr 18, 2006) You can now sign up for a checkoff slot.
(Apr 12, 2006) The long-awaited Project 2 is finally available. It has been divided into two portions: one, labeled Project 2, is the programming component and may be done in groups of up to three persons; the other, labeled Assignment 3, is the analytical component and must be done individually. The answers for Assignment 3 must be submitted in the usual manner in the drop box, but the programming component will be assessed by a checkoff process.
(Apr 7, 2006) A submission page has now been opened on esub. Please read the instructions below carefully before submitting your assignment.
(Apr 5, 2006) An updated version of the code for Project 1 has been posted. It is available below as version 1.2 of the code. The changes are minor, and confined to the utils.scm and system.scm files. See below for details. I have also posted a few tips for using Emacs with Scheme. They are available under the Resources section. These are the same tips that were posted to Rohan Smith's wiki at the start of the semester, so if you have already been using these tips, then you need not refer to these again.
(Apr 3, 2006) The due date for Project 1 has now been extended to Friday, April 7, 2006. A bug was found in the system.scm file, where a call to patient:treatment-difficulty should have been patient:treatment-handicap instead. A number of students have also been using some of the list functions that are provided as primitives in MIT Scheme. For this project, this is strongly discouraged because using these functions will call the system versions of the basic operations (such as cons, car, cdr) instead of the overridden definitions which cause the clock to tick.
For those of you who have already used some of these functions, I have written overriding definitions for the most common ones and provided them in the utils.scm file. You can get all these changes by downloading the latest version of the project, provided below. Please be cautious in unzipping it, and avoid overwriting your solution files (which should all be in the student directory)
(Mar 28, 2006) Recitation 7 has been posted below.
(Mar 23, 2006) Project 1, the Triage simulator has been posted below.
(Mar 21, 2006) Recitation 6 has been posted below.
(Mar 21, 2006) Your graded midterms have been returned, and are available for pickup in the lab, if you didn't already pick it up from lecture.
(Mar 16, 2006) The due date for Assignment 2 has been extended to Monday, March 20, 2006 at 3pm. No submissions will be accepted after this date and time.
(Mar 11, 2006) Solutions to Assignment 1 have been posted below.
(Mar 6, 2006) Recitation 5 has been posted below.
(Feb 24, 2006) Assignment 2 has been posted below. It is due on Thursday, Feb 16, 2006.
(Feb 24, 2006) The midterm exam will be on Monday, March 13, 2006 in the Old Dramatic Theatre at 4pm. Calculators will NOT be permitted.
(Feb 20, 2006)Recitation 4 has been posted below.
(Feb 15, 2006)Recitation 3 has been posted below.
(Feb 10, 2006)Assignment 1 has been posted below.
(Feb 7, 2006)Recitation 2 has been posted below.
(Jan 31, 2006)Recitation 1 has been posted below.
(Jan 31, 2006)Some rough notes related to the material covered in lectures has been posted below.
(Jan 31, 2006)Be sure to take a look at the wiki created for this course by one of your colleagues. If you all participate constructively, it could become a very useful tool to you at the end of the term. You can follow the link that has been placed below under Resources.

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: The triage simulator. HTML | PDF | Postscript
Download the starting code for the project.

Download version 1.1 of the project code.
Changes in v1.1
- The bug in system.scm where there was a call to patient:treatment-difficulty was fixed to be a call to patient:treatment-handicap.
- some additional list utility functions were implemented in utils.scm to override the system provided ones which would have circumvented the mechanisms to count the number of basic operations that you used.
Download version 1.2 of the project code.
Changes in v1.2
- Some additional functions have been defined in utils.scm and some of the basic operations defined within the run procedure in the system.scm file have been modified accordingly.
- Added implementations to utils.scm for: length, list-copy, list, vector, vector-grow
The upshot of these changes is that you may now call any one of them without (accidentally) bypassing the basic operations counter.

Instructions for Submission of Project 1
Please follow these instructions very carefully when submitting your assignment. Failure to do so could result in a loss of marks. Unfortunately, these instructions cannot be placed on the esub page directly (not yet anyway), otherwise I would have.
1. The first file you submit should be a list of your group members. There should not be more than 3. Only persons listed here will receive credit for the work submitted. Any person listed in more than one group will jeopardize the marks for all groups in which he/she is listed. In particular, each of the related fraudulent groups will receive a grade that is lower than the lowest original grade among them. (Think of the net resistance of resistors in parallel.)
2. The second file you submit should be a zip file of the student directory. Make sure that you zip from the project directory, so that student is a subdirectory, and preserve paths, so that when your file is unzipped, your solutions will be restored to the student directory. Please make sure that you are using zip, and not any of the other popular compression techniques. Marks will be deducted if there is trouble in decompressing your submission. Make sure that your submission works out of the box; you will be assessed a penalty for any changes that you need to make during the checkoff. There will be no second chances at checkoff -- except under extreme circumstances.
Go to the Project 1 submission page.

Sign up for a checkoff slot
Assignment3 and Project 2. The written portion of project 2 is referred to as Assignment 3. It is to be done individually, and submitted on hard copy.. The programming portion of the project is what is referred to as Project 2, and it may be done in groups of up to 3 persons. It is to be submitted through the esub tool, for subsequent checkoff by a tutor.
1. Assignment 3 HTML | PDF | Postscript (Individual Work)
2. Project 2 HTML | PDF | Postscript (Group Work)
  Download the starting code for Project 2. (You will need to uncompress it into a working directory dedicated to this project.)
  
  You may now browse the javadoc generated documentation for classes within the graph package.
  
  Some students pointed out to me that when using TestGen to generate a random dictionary there are a number of problems/issues. First, it is possible to produce duplicates, second, the number of words obtained is about twice the number asked for, and third, there is always the string "!!" at the end of it. These features are all OK when creating a file of random word ladder input pairs, which is what TestGen was designed for, but not so good for generating dictionaries.
  
  So, I have created DictGen, which you should now use instead of TestGen to generate your dictionaries. (Still use TestGen to generate your sample input for the test word ladder pairs). You should download the source for DictGen.java and compile it yourself, if you want to use it.

Recitations

Recitation 1. An example worked from problem specification through to time complexity analysis. HTML | PDF | Postscript
Recitation 2. Practice with Master Theorem and working with trees. HTML | PDF | Postscript
Recitation 3. Binary Heaps and Binary Search Trees. HTML | PDF | Postscript
Recitation 4. Red-Black Trees. HTML | PDF | Postscript
Recitation 5. Hashing and Union-Find. HTML | PDF | Postscript
Recitation 6. Sorting. HTML | PDF | Postscript
Recitation 7. Graphs: Representation, BFS and DFS. HTML | PDF | Postscript

Lecture Notes

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

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.

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

CS Home