CS140 Home Page

# CS140: Algorithms

## Fall 2001

### Lecture:

  M&W, 2:45-4:00, Galileo McAlister

### Professor:

  Z Sweedyk
  e-mail: z@cs.hmc.edu
  Web page: www.cs.hmc.edu/~z
  Office hours: See my schedule

  ### Course contact:

  Mailing list: cs-140-l@hmc.edu
  Web page: www.cs.hmc.edu/courses/2001/fall/cs140/

### Tutor/Grader:

- Ethan Drucker edrucker@cs.hmc.edu
- Star Roth kroth@odin.ac.hmc.edu
- Don Wang dwang@cs.hmc.edu

### Text:

  Introduction to Algorithms by Thomas Cormen, Charles Leiserson, and Ronald Rivest.

### What Is CS140?

In CS140 we study algorithms . More specifically, we study well-known algorithms for classical problems in computer science such as finding the median of a set of numbers and finding a minimum spanning tree in a graph. In the process we also cover some advanced data structures like red/black trees and fibonnaci heaps. A primary objective of the course is to learn to design algorithms . To a large extent you'll learn by doing, but in addition we look at various design paradigms like divide and conquer, dynamic programming, and reductions. Another objective of the course is to learn to analyze algorithms; by this we mean answering the following questions.

- Is the algorithm correct?
- Is the algorithm efficient?

Finally we study a classification scheme for computational problems based on the efficiency of their algorithms; i.e. the classes P and NP . We may also touch on more advanced topics like approximation algorithms and the polynomial-time hierarchy.

### Grades

Your grade will be based on class participation, homework, three midterms exams, and a comprehensive final. A total of 110 points are possible. Class participation is worth 10 points. Homework, each midterm, and the final are worth 25 points but the lowest of these four scores will be dropped. Homework assignments will be posted to the course web page before class on Tuesdays and Thursdays. Assignments are due at the start of the next class period. Homework solutions will be posted on the web at the due-time, so no late homework will be accepted. Your three lowest homework scores will be dropped in computing your homework grade. You may collaborate in small groups (<5) on the homework but you must reference your collaborators. Homework should be prepared in LaTex. For help getting started see my LaTex tutorial. Exams will be take-home, timed, closed-book/notes. The tentative exam due dates are Oct. 8, Nov. 12, Dec. 3, and Dec. 18.

### Course Schedule:

Date | Lecture | Reading | Homework
Sept 5 | Introduction | Ch 1, 5, 11 | HW0: ps , tex , solutions
Sept 10 | Big-O, series and summations, loop-counting | Ch 2, 3 | HW1: ps , tex , solutions
Sept 12 | Recurrence relations, divide and conquer, Mergesort, Quicksort | Ch 4 | HW2: ps , tex , solutions
Sept 17 | Data structures, Heaps, binary search trees, treaps | Ch 7, 13 | HW3: ps , tex , solutions
Sept 19 | Linear time selection | Ch 6, 8, 9.4, 10.2 | HW4: ps , tex
Sept 24 | Lower bounds | Ch 9.1 |
Sept 26 | Lower bounds cont. |  | HW5: ps , tex , solutions , Review
Oct 1 | Review |  | EXAM 1: ps , tex
Oct 3 | Inductive Design |  |
Oct 8 | Inductive Design cont. |  | HW 6: ps , tex , solutions
Oct 10 | Class cancelled |  |
Oct 15 | Reductions, Network Flow | Ch 27 |
Oct 17 | Network Flow cont. and Divide and Conquer | Ch 27, 31.2 | HW 7: ps , tex , solutions
Oct 22 | Fall break |  |
Oct 24 | Greedy | Ch 16 | HW 8: ps , tex , solutions
Oct 29 | Dynamic Programming |  |
Oct 31 | Dynamic Programming cont. |  | HW 9: ps , tex , solutions
Nov 5 | Graph algorithms | Ch 25, 26 |
Nov 7 | Graph algorithms cont. |  |
Nov 8 | Review 7PM-8:30PM |  | Exam 2
Nov 12 | Intro to Complexity Theory | Ch 36 |
Nov 14 | NP-completeness |  | HW 10: ps , tex , solutions
Nov 19 | Simple Reductions |  |
Nov 21 | Thanksgiving break |  |
Nov 26 | Harder Reductions |  |
Nov 28 | Killer Reductions |  | HW 11: ps , tex , solutions
Dec 3 | Misc. Topics |  |
Dec 5 | Misc. Topics |  |
Dec 7 |  |  | Exam 3 (ps)
Dec 10 | Misc. Topics |  |
Dec 12 | Misc. Topics |  | Final Exam