This Course at MIT

This Course at MIT pages are part of the OCW Educator initiative, which seeks to enhance the value of OCW for educators.

Course Overview

This page focuses on the course 6.046 Design and Analysis of Algorithms as taught by Professors Erik Demaine, Srini Devadas, and Nancy Lynch in Spring 2015.

This course is an intermediate class covering the design of computer algorithms and the analysis of sophisticated algorithms. Students learn how to analyze the asymptotic performance of algorithms, and gain familiarity with major algorithms and data structures. They also apply important algorithmic design paradigms and methods of analysis, in addition to synthesizing efficient algorithms in common engineering design situations. Course materials are designed to help students understand the difference between tractable and intractable problems and to become familiar with strategies to deal with intractability. Students attend lectures and recitation sessions, and complete 10 problem sets throughout the semester.

Curriculum Information

Prerequisites

Requirements Satisfied

6.046 can be applied toward a Bachelor of Science in Computer Science and Engineering.

Offered

Every fall and spring semester

 

Course Outcomes

Course Goals for Students

Students who complete this course will have demonstrated the ability to do the following:

  • Argue the correctness of algorithms using inductive proofs and loop invariants.
  • Analyze worst-case running times of algorithms using asymptotic analysis. Compare the asymptotic behaviors of functions obtained by elementary compositions of polynomials, exponentials, and logarithmic functions. Describe the relative merits of worst-, average-, and best-case analysis.
  • Analyze average-case running times of algorithms whose running time is probabilistic. Employ indicator random variables and linearity of expectation to perform the analyses. Recite analyses of algorithms that employ this method of analysis.

› Read More

Meet the Educator

Man with glasses sits in front of geometric paper sculptures.

Erik Demaine, Professor in the Department of Electrical Engineering & Computer Science

In the following video, Erik Domaine discusses his role in the course, his interest in algorithms, and how teaching 6.046 Design and Analysis of Algorithms helps him understand algorithms at a deeper level.

 

Instructor Insights

This is me living the dream, teaching the topic I love.

—Erik Demaine

In the following videos, Professor Erik Demaine describes various aspects of how he teaches 6.046 Design and Analysis of Algorithms.

 

Assessment

The students' grades were based on the following activities:

The color used on the preceding chart which represents the percentage of the total grade contributed by problem sets. 30% Problem sets
The color used on the preceding chart which represents the percentage of the total grade contributed by quiz 1. 20% Quiz 1 (2 hours)
The color used on the preceding chart which represents the percentage of the total grade contributed by quiz 2. 20% Quiz 2 (2 hours)
The color used on the preceding chart which represents the percentage of the total grade contributed by the final exam. 30% Final exam (3 hours)

Instructor Insights on Assessment

Professor Erik Demaine shares his insights about assessment in his video, “On the Challenge of Assessing Students’ Abilities to Apply Algorithms in New and Creative Ways.”

 

Student Information

Approximately 250 students take this course each time it is offered.

Breakdown by Year

Mostly juniors and seniors

Breakdown by Major

Mostly computer science majors

Typical Student Background

Students tends to be interested in exploring algorithms at a more sophisticated level than what is typically offered in introductory level courses.