Introduction to Algorithms (MIT 6.006) [Playlist + Textbooks]

0
9981

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

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

Textbook (PDF)

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

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

Textbook (PDF)

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.)

Course Materials (ZIP)

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:

Buy at Amazon 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.

ASSN # TOPICS PROBLEM SETS SOLUTIONS
1 Asymptotic complexity, recurrence relations, peak finding Problem Set 1 (PDF)Problem Set 1 Code (ZIP) Problem Set 1 Solutions (PDF)
2 Fractal rendering, digital circuit simulation Problem Set 2 (PDF)Problem Set 2 Code (ZIP) Problem Set 2 Solutions (PDF)Problem Set 2 Code Solutions (ZIP – 7.7MB)
3 Range queries, digital circuit layout Problem Set 3 (PDF)Problem Set 3 Code (ZIP – 3.2MB) Problem Set 3 Solutions (PDF)Problem Set 3 Code Solutions(ZIP – 15.7MB)
4 Hash functions, Python dictionaries, matching DNA sequences Problem Set 4 (PDF)Problem Set 4 Code (GZ – 12.4MB) (kfasta.py courtesy of Kevin Kelley, and used with permission.) Problem Set 4 Solutions (PDF)Problem Set 4 Code Solutions (ZIP)
5 The Knight’s Shield, RSA public key encryption, image decryption Problem Set 5 (PDF)Problem Set 5 Code (ZIP)Problem Set 5 Grading Explanation (PDF) Problem Set 5 Solutions (PDF)Problem Set 5 Code Solutions (ZIP)
6 Social networks, Rubik’s Cube, Dijkstra Problem Set 6 (PDF)Problem Set 6 Code (ZIP – 2.9MB) (nhpn.py courtesy of Punyashloka Biswal and Michael Lieberman; Pocket Cube Solver courtesy of Huan Liu and Anh Nguyen. Used with permission.) Problem Set 6 Solutions (PDF)Problem Set 6 Code Solutions (ZIP)
7 Seam carving, stock purchasing and knapsack Problem Set 7 (PDF)Seam Carving for Content-Aware Image ResizingProblem Set 7 Code (ZIP) (Sunset image © source unknown. All rights reserved. This content is excluded from our Creative Commons license. For more information, see http://ocw.mit.edu/fairuse.)Problem Set 7 Answer Template (ZIP)

Problem Set 7 Grading Explanation (PDF)

Problem Set 7 Solutions (PDF)Problem Set 7 Code Solutions (ZIP)

 

(Source: MIT )

Leave a Reply