CS140:  Algorithms

Spring  2001


Lecture:

Section 1: T&Th 9:40-11, Beckman 126
Section 2: T&Th 2:45-4:00, Pryne

 

Professor:

Z Sweedyk
e-mail z@cs.hmc.edu
Office Hours: M&W 3-5

 

Course mailing list:

cs-140-l@hmc.edu

 

Tutor/Grader:


 

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. 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 will be assigned at class 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. 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 Feb. 13, Mar. 27, and April 26.
 

Course Schedule:
Last updated: April 2001