Introduction to Algorithms, MIT 6.006
Course Description
- mathematical modeling of computational problems
- covers：
- common algorithms
- algorithmic paradigms
- data structures
- used to solve these problems
- emphasizes
- relationship between algorithms and programming
- basic performance measures and analysis techniques
Definition: Algorithm
-
https://en.wikipedia.org/wiki/Algorithm
In mathematics and computer science, an algorithm is an unambiguous specification of how to solve a class of problems. Algorithms can perform calculation, data processing and automated reasoning tasks.
An algorithm is an effective method that can be expressed within a finite amount of space and time and in a well-defined formal language for calculating a function. Starting from an initial state and initial input (perhaps empty), the instructions describe a computation that, when executed, proceeds through a finite number of well-defined successive states, eventually producing "output" and terminating at a final ending state.
Textbooks
- T.Cormen, C.Leiserson, R.Rivest, C.Stein, Introduction to Algorithms, 3rd ed, 2009
- B.Miller, D.Ranum, Problem Solving with Algorithms and Data Structures Using Python, 2nd ed, 2011
Syllabus and Readings
- Introduction
- Algorithmic thinking, peak finding - 1, 3, D.1
- Models of computation, Python cost model, document distance - 1, 3, Python Cost Model
- Sorting and Trees
- Insertion sort, merge sort - 1.2, 2.1–2.3, 4.3–4.6
- Heaps and heap sort - 6.1–6.4
- Binary search trees, BST sort - 10.4, 12.1–12.3, Binary Search Trees
- AVL trees, AVL sort - 13.2, 14
- Counting sort, radix sort, lower bounds for sorting and searching - 8.1–8.3
- Hashing
- Hashing with chaining - 11.1–11.3
- Table doubling, Karp-Rabin - 17
- Open addressing, cryptographic hashing - 11.4
- Numerics
- Integer arithmetic, Karatsuba multiplication
- Square roots, Newton's method
- Graphs
- Breadth-first search (BFS) - 22.1–22.2, B.4
- Depth-first search (DFS), topological sorting - 22.3–22.4
- Shortest Paths
- Single-source shortest paths problem - 24.0, 24.5
- Dijkstra - 24.3
- Bellman-Ford - 24.1–24.2
- Speeding up Dijkstra
- Dynamic Programming
- Memoization, subproblems, guessing, bottom-up; Fibonacci, shortest paths - 15.1, 15.3
- Parent pointers; text justification, perfect-information blackjack - 15.3, Problem 15–4, Blackjack rules
- String subproblems, psuedopolynomial time; parenthesization, edit distance, knapsack - 15.1, 15.2, 15.4
- Two kinds of guessing; piano/guitar fingering, Tetris training, Super Mario Bros.
- Advanced Topics
- Computational complexity - 34.1–34.3
- Algorithms research topics
