Sunday, January 16, 2011

Video Lectures on Introduction to Algorithms

Video Lectures

Audio/video for lectures 20 and 21 are not available.


Lecture 1: Administrivia; Introduction; Analysis of Algorithms, Insertion Sort, Mergesort
Go to this video


Lecture 2: Asymptotic Notation; Recurrences; Substitution, Master Method
Go to this video


Lecture 3: Divide-and-Conquer: Strassen, Fibonacci, Polynomial Multiplication
Go to this video


Lecture 4: Quicksort, Randomized Algorithms
Go to this video


Lecture 5: Linear-time Sorting: Lower Bounds, Counting Sort, Radix Sort
Go to this video


Lecture 6: Order Statistics, Median
Go to this video


Lecture 7: Hashing, Hash Functions
Go to this video


Lecture 8: Universal Hashing, Perfect Hashing
Go to this video


Lecture 9: Relation of BSTs to Quicksort - Analysis of Random BST
Go to this video


Lecture 10: Red-black Trees, Rotations, Insertions, Deletions
Go to this video


Lecture 11: Augmenting Data Structures, Dynamic Order Statistics, Interval Trees
Go to this video


Lecture 12: Skip Lists
Go to this video


Lecture 13: Amortized Algorithms, Table Doubling, Potential Method
Go to this video


Lecture 14: Competitive Analysis: Self-organizing Lists
Go to this video


Lecture 15: Dynamic Programming, Longest Common Subsequence
Go to this video


Lecture 16: Greedy Algorithms, Minimum Spanning Trees
Go to this video


Lecture 17: Shortest Paths I: Properties, Dijkstra's Algorithm, Breadth-first Search
Go to this video


Lecture 18: Shortest Paths II: Bellman-Ford, Linear Programming, Difference Constraints
Go to this video


Lecture 19: Shortest Paths III: All-pairs Shortest Paths, Matrix Multiplication, Floyd-Warshall, Johnson
Go to this video


Lecture 22: Advanced Topics
Go to this video


Lecture 23: Advanced Topics (cont.)
Go to this video


Lecture 24: Advanced Topics (cont.)
Go to this video


Lecture 25: Advanced Topics (cont.) - Discussion of Follow-on Classes
Go to this video

sorting

EXAMSSOLUTIONS
Practice Quiz 1 (PDF)(PDF)#
Practice Quiz 2 (PDF)
Practice Final Exam (PDF)(PDF)
Quiz 1 (PDF)(PDF)
Quiz 2 (PDF)(PDF)
Final Exam (PDF)(PDF)

Assignments

This section contains documents that are inaccessible to screen reader software. A "#" symbol is used to denote such documents.
Special software is required to use some of the files in this section: .c, .java.
The problem sets for the course included both exercises and problems that students were asked to solve. Students were required to turn in only the problems but were encouraged to solve the exercises to help master the course material. Many of the exercise questions were taken from the course textbook.
ASSIGNMENTSSOLUTIONS
Problem Set 1 (PDF)#(PDF)#
Problem Set 2 (PDF)(PDF)
Problem Set 3 (PDF)(PDF)
Problem Set 4 (PDF)(PDF)
Problem Set 5 (PDF)(PDF)#
Problem Set 6 (PDF)(PDF)#
Problem Set 7 (PDF)

Sample Input, sample.txt (TXT)
Sample Output, samplesol.txt (TXT)
Input 1, input1.txt (TXT)
Input 2, input2.txt (TXT)
Input 3, input3.txt (TXT)
(PDF)

Source Code, editDistance.java (JAVA)
Source Code, editDistance.c (C)
Problem Set 8 (PDF)(PDF)
Problem Set 9 (PDF)(PDF)
The table below provides information on the course's reading assignments, which are taken from the course textbook:
Amazon logo Cormen, Thomas H., Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. 2nd ed. Cambridge, MA: MIT Press. ISBN: 0262032937.
In addition to the assigned course readings, see the list of useful references for the course below.
SES #TOPICSREADINGS
L1Administrivia

Introduction

Analysis of Algorithms, Insertion Sort, Mergesort
Chapters 1-2
R1Correctness of Algorithms

Horner's rule
 
L2Asymptotic Notation

Recurrences

Substitution, Master Method
Chapters 3-4, excluding section 4.4
L3Divide-and-Conquer: Strassen, Fibonacci, Polynomial MultiplicationSections 28.2 and 30.1
R2Recurrences, Sloppiness 
L4Quicksort, Randomized AlgorithmsSections 5.1-5.3

Chapter 7
R3Heapsort, Dynamic Sets, Priority QueuesChapter 6
L5Linear-time Sorting: Lower Bounds, Counting Sort, Radix SortSections 8.1-8.3
L6Order Statistics, MedianChapter 9
R4Applications of Median

Bucketsort
Section 8.4
L7Hashing, Hash FunctionsSections 11.1-11.3
L8Universal Hashing, Perfect HashingSection 11.5
R5Quiz 1 Review 
Q1Quiz 1, In-class 
R6Binary Search Trees, Tree WalksSections 12.1-12.3
L9Relation of BSTs to Quicksort

Analysis of Random BST
Section 12.4
L10Red-black Trees, Rotations, Insertions, DeletionsChapter 13
R72-3 Trees, B-trees 
L11Augmenting Data Structures, Dynamic Order Statistics, Interval TreesChapter 14
L12Skip ListsSkip Lists handout (PDF)
R8Range Trees 
L13Amortized Algorithms, Table Doubling, Potential MethodChapter 17
L14Competitive Analysis: Self-organizing ListsSleator, Daniel D., and Robert E. Tarjan. "Amortized efficiency of list update and paging rules." Communications of the ACM 28, no. 2 (February 1985): 202-208.
R9Competitive Analysis: Ski Rental, Randomized Competitive Algorithm 
L15Dynamic Programming, Longest Common SubsequenceChapter 15
L16Greedy Algorithms, Minimum Spanning TreesSections 16.1-16.3 and 22.1

Chapter 23
L17Shortest Paths I: Properties, Dijkstra's Algorithm, Breadth-first SearchSection 22.2

Chapter 24
L18Shortest Paths II: Bellman-Ford, Linear Programming, Difference Constraints 
R10Graph Searching: Depth-first Search, Topological Sort, DAG Shortest PathsSections 22.3-22.4
L19Shortest Paths III: All-pairs Shortest Paths, Matrix Multiplication, Floyd-Warshall, JohnsonChapter 25
L20Quiz 2 Review 
L21Ethics, Problem Solving (Mandatory Attendance) 
Q2Quiz 2, In-class 
L22Advanced TopicsDynamic Multithreaded Algorithms handout (PDF)
L23Advanced Topics (cont.) 
R11Advanced Topics 
L24Advanced Topics (cont.)Demaine, Erik D. "Cache-Oblivious Algorithms and Data Structures." To appear in Lecture Notes from the EEF Summer School on Massive Data Sets, a volume of Lecture Notes in Computer Science. Berlin, Germany: Springer-Verlag.
L25Advanced Topics (cont.)

Discussion of Follow-on Classes
 
 Final Exam 

Useful References

Aho, Alfred V., John E. Hopcroft, and Jeffrey D. Ullman. The Design and Analysis of Computer Algorithms. Reading, MA: Addison-Wesley, 1974. ISBN: 0201000296.
The classic text, but it lacks topics in network flows and linear programming, as well as more recent algorithms.
———. Data Structures and Algorithms. Reading, MA: Addison-Wesley, 1983. ISBN: 0201000237.
Revised and more elementary version of the first six chapters of The Design and Analysis of Computer Algorithms.
Baase, Sara. Computer Algorithms: Introduction to Design and Analysis. 2nd ed. Reading, MA: Addison-Wesley, 1988. ISBN: 0201060353.
General reference, although the exposition is sometimes terse or sketchy.
Bentley, Jon Louis. Programming Pearls. Reading, MA: Addison-Wesley, 1986. ISBN: 0201103311.
Applications of algorithm design techniques to software engineering.
———. More Programming Pearls: Confessions of a Coder. Reading, MA: Addison-Wesley, 1988. ISBN: 0201118890.
More applications of algorithm design techniques to software engineering.
———. Writing Efficient Programs. Englewood Cliffs, NJ: Prentice-Hall, 1982. ISBN: 0139702512.
Performance hacking extraordinaire.
Brassard, Gilles, and Paul Bratley. Algorithmics: Theory and Practice. Englewood Cliffs, NJ: Prentice-Hall, 1988. ISBN: 0130232432.
Good examples and problems. Focus on methods rather than specific problems.
Chung, Kai Lai. Elementary Probability Theory with Stochastic Processes. New York, NY: Springer-Verlag, 1974. ISBN: 0387900969.
Intuitive introduction to probability.
Even, Shimon. Graph Algorithms. Rockville, MD: Computer Science Press, 1979. ISBN: 0914894218.
Broad treatment of graph algorithms, including network flow and planarity.
Feller, William. An Introduction to Probability Theory and Its Applications. 3rd ed. 2 vols. New York, NY: John Wiley & Sons, 1968, 1971. ISBN: 0471257087. ISBN: 0471257095.
Excellent reference for probability theory.
Garey, Michael R., and David S. Johnson. Computers and Intractibility: A Guide to the Theory of NP-Completeness. San Francisco, CA: W. H. Freeman & Co., 1979. ISBN: 0716710447.
Reference book devoted to NP-completeness. The second half contains an extensive list of NP-complete problems and references to algorithms in the literature for polynomial-time special cases.
Gonnet, Gaston H. Handbook of Algorithms and Data Structures. Reading, MA: Addison-Wesley, 1984. ISBN: 020114218X.
Code in Pascal and C, comparisons of actual running times, and pointers to analysis in research papers.
Gusfield, Dan. Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge, UK: Cambridge University Press, 1997. ISBN: 0521585198.
General treatment of algorithms that operate on character strings and sequences.
Horowitz, Ellis, and Sartaj Sahni. Fundamentals of Computer Algorithms. Potomac, MD: Computer Science Press, 1978. ISBN: 0914894226.
Good on data structures, dynamic programming, and branch-and-bound algorithms.
Kingston, Jeffrey H. Algorithms and Data Structures: Design, Correctness, Analysis. Reading, MA: Addison-Wesley Publishing Co., 1991. ISBN: 0201417057.
A nice introductory book on data structures, with a good chapter on algorithm correctness.
Knuth, Donald E. The Art of Computer Programming. 3rd ed. 3 vols. Reading, MA: Addison-Wesley, 1997. ISBN: 0201896834. ISBN: 0201896842. ISBN: 0201896850.
Encyclopedic work in three volumes: (1) Fundamental Algorithms, (2) Seminumerical Algorithms, and (3) Sorting and Searching.
Lawler, Eugene L. Combinatorial Optimization: Networks and Matroids. New York, NY: Holt, Rinehart, and Winston, 1976. ISBN: 0030848660.
Graph algorithms (dense graphs), network flows, and linear programming. First few chapters are excellent.
Liu, Chung L. Introduction to Combinatorial Mathematics. New York, NY: McGraw-Hill, 1968. ISBN: 0070381240.
Combinatorial mathematics relevant to computer science. Excellent problems.
Manber, Udi. Introduction to Algorithms: A Creative Approach. Reading, MA: Addison-Wesley, 1989. ISBN: 0201120372.
Elementary text with an emphasis on creativity.
Mehlhorn, Kurt. Data Structures and Algorithms. 3 vols. New York, NY: Springer-Verlag, 1984. ISBN: 038713302X. ISBN: 354013641X. ISBN: 0387136428.
Three volumes: (1) Sorting and Searching, (2) Graph Algorithms and NP-Completeness, and (3) Multidimensional Searching and Computational Geometry. Lecture notes on basic and advanced topics.
Niven, Ivan, and Herbert S. Zuckerman. An Introduction to the Theory of Numbers. 4th ed. New York, NY: John Wiley & Sons, 1980. ISBN: 0471028517.
Readable introduction to number theory.
Papadimitriou, Christos H., and Kenneth Steiglitz. Combinatorial Optimization: Algorithms and Complexity. Englewood Cliffs, NJ: Prentice-Hall, 1982. ISBN: 0131524623.
Linear programming and its variants.
Press, William P., Brian P. Flannery, Saul A. Teukolsky, and William T. Vetterling. Numerical Recipies in C: The Art of Scientific Computing. Cambridge, UK: Cambridge University Press, 1988. ISBN: 052135465X.
Code for numerical algorithms.
Reingold, Edwin M., Jurg Nievergelt, and Narsingh Deo. Combinatorial Algorithms: Theory and Practice. Englewood Cliffs, NJ: Prentice-Hall, 1977. ISBN: 013152447X.
Good on recurrence relations and binary search trees.
Sedgewick, Robert. Algorithms. 2nd ed. Reading, MA: Addison-Wesley, 1988. ISBN: 0201066734.
Elementary text with an excellent breadth of topics. Light on analysis, but lots of figures.
Sipser, Michael. Introduction to the Theory of Computation. Boston, MA: PWS Publishing Company, 1997. ISBN: 053494728X.
A good text on computability and complexity theory.
Tarjan, Robert Endre. Data Structures and Network Algorithms. Philadelphia, PA: Society for Industrial and Applied Mathematics, 1983. ISBN: 0898711878.
Advanced book with tons of good stuff.

No comments: