## 6.046J/18.410J Design and Analysis of Algorithms

**Fall 2009**

**Professors:**Erik D Demaine, Shafrira Goldwasser

**TAs:**Ammar Ammar, I-Ting Angelina Lee, Huy Ngoc Nguyen, Tao B Schardl

**Lecture**: TR11-12.30 (26-100)

**Information:**

This is the second undergraduate algorithms class after 6.006. The textbook is Introduction to Algorithms, Third Edition by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Electronic versions of the

*second edition*are available from Google Book Search (limited viewing but searchable) and from books24x7 (author search for Cormen, or follow the direct link after logging in with the link above).#### General (5)

09.09.09

**Recitation Assignment Form**

Deadline: 6pm, Thursday September 10

**Last modified by:**Erik Demaine

#### Lecture Notes (23)

09.10.09

**Lecture 1: Overview of class. Interval scheduling.**

Thursday, September 10, 2009

**Last modified by:**Erik Demaine

09.18.09

**Lecture 2: Divide-and-conquer, integer multiplication, recursive powering**

Tuesday, September 15, 2009

**Last modified by:**Erik Demaine

09.18.09

**Lecture 3: Randomized algorithms, primality testing**

Thursday, September 17, 2009

**Last modified by:**Erik Demaine

10.07.09

**Lecture 9: Greedy algorithms: Minimum spanning tree, Prim, Kruskal**

**Last modified by:**Erik Demaine

10.23.09

**Lecture 11: All-pairs shortest paths: Floyd-Warshall, Johnson, difference constraints**

**Last modified by:**Erik Demaine

11.17.09

**Lecture 17: RP, polynomial identity, PSPACE, interactive proofs**

**Last modified by:**Erik Demaine

## No comments:

## Post a Comment