Design and Analysis of Algorithms PPT Slides

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

09.22.09

Handout 1: Course Information

Last modified by: Huy Nguyen

09.09.09

Handout 2: Course Objectives and Outcomes

Last modified by: Erik Demaine

09.09.09

Handout 3: References

Last modified by: Erik Demaine

11.11.09

Academic Honesty note for quiz 2

Last modified by: Huy Nguyen

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

09.20.09

Lecture 4: Quicksort, randomly built BSTs

Last modified by: Erik Demaine

09.24.09

Lecture 5: Universal hashing, perfect hashing

Last modified by: Erik Demaine

09.29.09

Lecture 6: Skip lists

Last modified by: Erik Demaine

10.05.09

Lecture 7: 2-3 trees, B-trees, red-black trees

Last modified by: Erik Demaine

10.05.09

Lecture 8: Amortized analysis

Last modified by: Erik Demaine

10.07.09

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

Last modified by: Erik Demaine

10.26.09

Lecture 10: Dynamic programming

Last modified by: Erik Demaine

10.23.09

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

Last modified by: Erik Demaine

10.27.09

Lecture 12: Max flow, min cut

Last modified by: Erik Demaine

10.29.09

Lecture 13: Matching

Last modified by: Erik Demaine

11.03.09

Lecture 14: Linear programming, low-dimensional algorithms

Last modified by: Erik Demaine

11.28.09

Lecture 15: NP, P, and NP-completeness

Last modified by: Erik Demaine

11.17.09

Lecture 16: NP-complete Problems

Last modified by: Erik Demaine

11.17.09

Lecture 16 slides

Last modified by: Erik Demaine

11.17.09

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

Last modified by: Erik Demaine

11.19.09

Lecture 17 slides

Last modified by: Huy Nguyen

12.02.09

Lecture 18: Approximation algorithms, inapproximability

Last modified by: Erik Demaine

12.01.09

Lecture 20: van Emde Boas

Last modified by: Erik Demaine

12.04.09

Lecture 21 slides

Last modified by: Huy Nguyen

12.08.09

Lecture 22: Compression Algorithms

Huffman, Lempel Ziv

Last modified by: Huy Nguyen

Problem Sets (6)

09.10.09

Problem set 1

Due: September 22 2009 11:00 a.m.

09.22.09

Problem set 2

Due: October 01 2009 11:00 a.m.

10.01.09

Problem set 3

Due: October 09 2009 3:00 p.m.

10.20.09

Problem set 4

Due: October 29 2009 11:00 a.m.

10.29.09

Problem set 5

Due: November 10 2009 11:00 a.m.

11.19.09

Problem set 6

Due: December 03 2009 11:00 a.m.

Quizzes (4)

10.06.09

Quiz 1 Practice

Pratice question for the quiz 1.

Last modified by: Huy Nguyen

10.11.09

Solution for quiz 1 practice questions

Last modified by: Huy Nguyen

10.20.09

Quiz 1 Solution

Last modified by: Huy Nguyen

11.30.09

Quiz 2 solution

Last modified by: Huy Nguyen