6.046J/18.410J Class Home

6.046J/18.410J Design and Analysis of Algorithms

Fall 2009

home page image

Professors: Erik D Demaine, Shafi Goldwasser

TAs: Ammar T Ammar, I-Ting Angelina Lee, Huy Ngoc Nguyen, Tao 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).

Announcements

6.046 Final Exam Scores

Hey everybody,

The 6.046 final exam scores are now up on Stellar.

Have a great holiday break,
-TB

Announced on 20 December 2009 11:26 a.m. by Tao Schardl

Dynamic Programming in the Final

Dear Class,

As we mentioned in the review session yesterday, Dynamic Programming IS included in the coverage for the final. It was omitted from the topic list by mistake.

Good Luck,
Ammar

Announced on 13 December 2009 8:37 p.m. by Ammar T Ammar

Final review

Hi all,

We will hold a review section for the final exam on this Saturday, December 12, 5:00pm - 7:00pm at 6-120.

Also, the topics that are covered in the final exam can be found at: http://stellar.mit.edu/S/course/6/fa09/6.046/courseMaterial/topics/topic4/resource/final_topic/final_topic.txt

Best,
Huy

Announced on 10 December 2009 9:14 p.m. by Huy Ngoc Nguyen

Final Exam Annoucement

What: 6.046 Final Exam.

When: Monday, December 14, 2009, 1:30pm-4:30pm.

Where: duPont Athletic Gymnasium (Building W31).

Cheat sheets: You may bring TWO double-sided cheat sheets on 8 1/2" x 11" or A4 papers. Calculators and programmable devices are not allowed for this quiz.

Good luck!

Announced on 10 December 2009 3:37 p.m. by Huy Ngoc Nguyen

Problem 6: Clarification

Hi all,

This is a clarification for the definition of IP* in problem 3(e):

IP* are those decision problems \Pi such that there exists a probabilistic polynomial time algorithm V that interacts with an all-powerful algorithm P in a protocol (P, V ) such that on input x:

- when \Pi(x) = YES, *then there exists a prover P*, such that
Pr[V (x, r) outputs YES at the end of interactive protocol with P] > 2/3
- when \Pi(x) = NO, *then for all provers P* ,
Pr[V (x, r) outputs YES at the end of interactive protocol with P] = 0

Thanks,
Huy

Announced on 01 December 2009 12:58 p.m. by Huy Ngoc Nguyen

View archived announcements