Computer Science 231
Fundamental Algorithms
Spring 2009

Welcome to CS231
Computer Science 231 is an introduction to the design and analysis of fundamental algorithms. General techniques covered: Divide-and-conquer algorithms, dynamic programming, greediness, probabilistic algorithms. Topics include: sorting, searching, graph algorithms, file compression, and NP-completeness. Course requirements will be discussed on the first day.
Prerequisite: 230
Distribution: Mathematical Modeling
Semester: Fall, Unit: 1.0

Textbook
The text this semester is the second edition of Introduction to Algorithms, written by Thomas Cormen, Charles Leiserson, Ronald Rivest, and Clifford Stein published by MIT Press, Cambridge, Massachusetts. Several copies of the text, here after known as CLRS, are on reserve in the library.

Course Materials
CS231 course materials for each class will be handed out at the beginning of each lecture. Copies are available in .pdf format using the links on this page and require the Adobe Acrobat Reader program for on-screen viewing and printing. This program is installed on most public computers at Wellesley College. If your computer does not have a working copy of Acrobat Reader, it is available for free from Adobe on all major computer platforms. Click on the button to the left to download Acrobat Reader. Note that there are plug-ins that allow you to read .pdf files directly from your browser; again, these are installed on most public computers and are freely available from Adobe.

Transparencies
Copies of course transparencies will be available at the beginning of each lecture. Copies may be obtained using the following links.

  1. Introduction to Algorithms
    Tuesday, February 3
  2. Measuring Algorithms
    Friday, February 6
  3. Asymptotic Notation
    Tuesday, February 10
  4. Solving Recurrences
    Friday, February 13
  5. Heap Sort
    Tuesday, February 17
  6. Priority Queues
    Friday, February 20
  7. Quicksort
    Tuesday, February 24
  8. Average case analysis of Quicksort
    Friday, February 27
  9. Limits to comparison sorting
    Tuesday, March 3
  10. Linear sorting techniques
    Friday, March 6
  11. Order Statistics
    Tuesday, March 10
  12. Dynamic Sets
    Friday, March 13
  13. Red-Black Trees
    Tuesday, March 17
  14. Midterm Examination 1
    Friday, March 20
  15. Spring break
    March 21 -- 29
  16. Dynamic programming
    Tuesday, March 31
  17. Matrix-chain multiplication
    Friday, April 3
  18. Greedy algorithms
    Tuesday, April 7
  19. File compression and Huffman codes
    Friday, April 10
  20. Amortized Analysis
    Tuesday, April 14
  21. Dynamic tables
    Friday, April 17
  22. Monday's schedule (no class)
    Tuesday, April 21
  23. Midtermin Examination 2
    Friday, April 24
  24. B-trees
    Tuesday, April 28
  25. Elementary graph algorithms
    Friday, May 1
  26. Topological sort
    Tuesday, May 5
  27. Minimum spanning trees
    Friday, May 8
  28. When is a problem hard?
    Tuesday, May 12
Homework Sets
All assignments are due at the beginning of class on the due dates announced when distributed and given below. Once graded homework is returned and solutions posted (usually on the class following the day the assignment was due) no late work for that assignment will be accepted. Copies of assignments may be obtained using the following links.
  1. Assignment 1 due Tuesday, February 10
  2. Assignment 2 due Tuesday, February 17
  3. Assignment 3 due Tuesday, February 24
  4. Assignment 4 due Tuesday, March 3
  5. Assignment 5 due Friday, March 13
  6. Assignment 6 due Friday, April 3
  7. Assignment 7 due Friday, April 10
  8. Assignment 8 due Friday, April 17
  9. Assignment 9 due Tuesday, May 12

Randy Shull -- rshull@wellesley.edu
Computer Science 231, Spring 2009
Last Modified April 26, 2009
Page Expires May 31, 2009