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.890 Algorithmic Lower Bounds: Fun with Hardness Proofs as it was taught by Professor Erik Demaine in Fall 2014.

This course addressed algorithmic reductions and techniques for proving problems are computationally hard for a variety of complexity classes. Students created interesting gadgets, learned many hardness proof styles, explored the connection between games and computation, surveyed several important problems and complexity classes, and crushed hopes and dreams (for fast optimal solutions).

Students met twice a week for lectures and had the opportunity to meet once a week for optional problem-solving sessions focused on jointly solving open problems.

Course Outcomes

Course Goals for Students

  • Learn when to give up the search for efficient algorithms
  • See connections between computational problems
  • Solve puzzles to prove theorems
  • Solve open problems

Possibilities for Further Study/Careers

Many students who took this course in Fall 2014 met after the course was over to continue their work on open problems.

Other possibilities for further study included courses in complexity theory or advanced algorithms.

Curriculum Information

Prerequisites

  • 6.046 Design and Analysis of Algorithms or equivalent background in discrete mathematics and algorithms
  • Alternatively, permission from the instructor
  • No background in computational complexity required; all needed notations defined in class

Requirements Satisfied

None

Offered

6.890 was offered for the first time in Fall 2014.

 

Instructor Insights

Professor Eric Demaine sits in front of the bookshelves.

In the following videos, Professor Erik Demaine describes various aspects of how he taught 6.890 Algorithmic Lower Bounds: Fun with Hardness Proofs.

Silence is the worst thing for solving problems.

— Erik Demaine

 

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. 20% Problem sets
The color used on the preceding chart which represents the percentage of the total grade contributed by scribe notes. 10% Scribed notes
The color used on the preceding chart which represents the percentage of the total grade contributed by final project. 50% Final project
The color used on the preceding chart which represents the percentage of the total grade contributed by final presentation. 20% Final presentation
 

Student Information

37 students took this course when it was taught in Fall 2014.

Breakdown by Year

Both graduate and undergraduate students

Breakdown by Major

Mostly computer science majors

Typical Student Background

Although many students were computer science majors, few were theoretical computer scientists. Most had strong backgrounds in algorithms.

The course was designed for people working on challenging problems (by using heuristics or relatively slow algorithms, for example) and who needed to learn how to prove that their approaches were the best choices for solving the problems. 6.890 provided these students with a practical approach for proving hardness.