## Course Description

This course provides an introduction to mathematical modeling of computational problems. It covers the common algorithms, algorithmic paradigms, and data structures used to solve these problems. The course emphasizes the relationship between algorithms and programming, and introduces basic performance measures and analysis techniques for these problems.

1. Algorithmic Thinking, Peak Finding

2. Models of Computation, Document Distance

3. Insertion Sort, Merge Sort

4. Heaps and Heap Sort

5. Binary Search Trees, BST Sort

6. AVL Trees, AVL Sort

7. Counting Sort, Radix Sort, Lower Bounds for Sorting

8. Hashing with Chaining

9. Table Doubling, Karp-Rabin

10. Open Addressing, Cryptographic Hashing

11. Integer Arithmetic, Karatsuba Multiplication

12. Square Roots, Newton’s Method

13. Breadth-First Search (BFS)

14. Depth-First Search (DFS), Topological Sort

15. Single-Source Shortest Paths Problem

16. Dijkstra

17. Bellman-Ford

18. Speeding up Dijkstra

19. Dynamic Programming I: Fibonacci, Shortest Paths

20. Dynamic Programming II: Text Justification, Blackjack

21. DP III: Parenthesization, Edit Distance, Knapsack

22. DP IV: Guitar Fingering, Tetris, Super Mario Bros.

23. Computational Complexity

24. Topics in Algorithms Research

R1. Asymptotic Complexity, Peak Finding

R2. Python Cost Model, Document Distance

R3. Document Distance, Insertion and Merge Sort

R5. Recursion Trees, Binary Search Trees

R6. AVL Trees

R7. Comparison Sort, Counting and Radix Sort

R8. Simulation Algorithms

R9. Rolling Hashes, Amortized Analysis

Recitation 9b: DNA Sequence Matching

R10. Quiz 1 Review

R11. Principles of Algorithm Design

R12. Karatsuba Multiplication, Newton’s Method

R13. Breadth-First Search (BFS)

R14. Depth-First Search (DFS)

R15. Shortest Paths

R16. Rubik’s Cube, StarCraft Zero

R18. Quiz 2 Review

R19. Dynamic Programming: Crazy Eights, Shortest Path

R20. Dynamic Programming: Blackjack

R21. Dynamic Programming: Knapsack Problem

R22. Dynamic Programming: Dance Dance Revolution

R23. Computational Complexity

R24. Final Exam Review

## Prerequisites

A firm grasp of Python and a solid background in discrete mathematics are necessary prerequisites to this course. You are expected to have mastered the material presented in *6.01 Introduction to EECS I* and *6.042J Mathematics for Computer Science*.

If you have not taken and been successful in each of these subjects, please speak with a TA or professor before enrolling. We do allow students who have equivalent, other experience with the material described above to enroll, but with the firm understanding that mastery of this material is assumed and that course staff will not feel obligated to cover it or to help students who are struggling with it.

6.006 is a 12-unit (4-0-8) subject and serves as a Foundational Computer Science subject under the new curriculum. It is a direct prerequisite for *6.046 Design and Analysis of Algorithms, *the theory header.

## Textbooks

### Required

Cormen, Thomas, Charles Leiserson, Ronald Rivest, and Clifford Stein. *Introduction to Algorithms*. 3rd ed. MIT Press, 2009. ISBN: 9780262033848.

For the student who finds books helpful, we also suggest:

Miller, Bradley, and David Ranum. *Problem Solving with Algorithms and Data Structures Using Python*. 2nd ed. Franklin, Beedle & Associates, 2011. ISBN: 9781590282571.

## Software

6.006 programming environment setup

## Lectures and Recitations

One-hour lectures are held twice a week. You are responsible for material presented in lectures, including oral comments made by the lecturer (or other information that may not be present in the notes).

One-hour recitations are held twice a week, one day after the lectures. You are responsible for the material presented in recitation, which may include new material not presented in lectures. Recitation attendance has been well-correlated with quiz performance in past semesters. Recitations also give you a more intimate opportunity to ask questions of and to interact with the course staff. Your recitation instructor is responsible for determining your final grade.

## Problem Sets

We will assign seven problem sets during the course of the semester. Each problem set will consist of a programming assignment, to be completed in Python, and a theory assignment.

If you collaborate with others in any fashion, you must list their names as collaborators. For details, please see the section on our collaboration policy; we take this very seriously.

Late assignments will be severely penalized. (This penalty is currently a 1% deduction every six minutes or part thereof until the end of the tenth hour after the deadline, after which submissions will receive no credit.)

**Instructor(s)**

Prof. Erik Demaine

Prof. Srinivas Devadas

**MIT Course Number**

6.006

**Recorded
**Fall 2011

**Level
**Undergraduate

View the complete course: http://ocw.mit.edu/6-006F11

Readings refer to chapters and/or sections of the course textbook:

Cormen, Thomas, Charles Leiserson, Ronald Rivest, and Clifford Stein. *Introduction to Algorithms*. 3rd ed. MIT Press, 2009. ISBN: 9780262033848.

LEC # | TOPICS | READINGS |
---|---|---|

Unit 1: Introduction |
||

1 | Algorithmic thinking, peak finding | 1, 3, D.1 |

2 | Models of computation, Python cost model, document distance | 1, 3, Python Cost Model |

Unit 2: Sorting and Trees |
||

3 | Insertion sort, merge sort | 1.2, 2.1–2.3, 4.3–4.6 |

4 | Heaps and heap sort | 6.1–6.4 |

5 | Binary search trees, BST sort | 10.4, 12.1–12.3, Binary Search Trees |

6 | AVL trees, AVL sort | 13.2, 14 |

7 | Counting sort, radix sort, lower bounds for sorting and searching | 8.1–8.3 |

Unit 3: Hashing |
||

8 | Hashing with chaining | 11.1–11.3 |

9 | Table doubling, Karp-Rabin | 17 |

10 | Open addressing, cryptographic hashing | 11.4 |

Quiz 1 | ||

Unit 4: Numerics |
||

11 | Integer arithmetic, Karatsuba multiplication | |

12 | Square roots, Newton’s method | |

Unit 5: Graphs |
||

13 | Breadth-first search (BFS) | 22.1–22.2, B.4 |

14 | Depth-first search (DFS), topological sorting | 22.3–22.4 |

Unit 6: Shortest Paths |
||

15 | Single-source shortest paths problem | 24.0, 24.5 |

16 | Dijkstra | 24.3 |

17 | Bellman-Ford | 24.1–24.2 |

18 | Speeding up Dijkstra | |

Quiz 2 | ||

Unit 7: Dynamic Programming |
||

19 | Memoization, subproblems, guessing, bottom-up; Fibonacci, shortest paths | 15.1, 15.3 |

20 | Parent pointers; text justification, perfect-information blackjack | 15.3, Problem 15–4,Blackjack rules |

21 | String subproblems, psuedopolynomial time; parenthesization, edit distance, knapsack | 15.1, 15.2, 15.4 |

22 | Two kinds of guessing; piano/guitar fingering, Tetris training, Super Mario Bros. | |

Unit 8: Advanced Topics |
||

23 | Computational complexity | 34.1–34.3 |

24 | Algorithms research topics |

6.006 students submitted their solutions using Gradetacular, which is not available through MIT OpenCourseWare. The solutions below contain all of the test data used by 6.006 staff, so you can use these files to grade your own code.

In order to use the ZIP files, you will need the programs described in the Software section. Some problem sets also contain additional installation instructions in the README.txt files. LaTeX templates are also included; see the Related Resources for suggested editors.

(*Source: MIT* )

You must log in to post a comment.