Design and Analysis of Algorithms

"The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct." -- Donald Knuth

I. Foundations


1. The Role Of Algorithms

2. Getting Started

3. Growth Of Functions

4. Divide And Conquer

5. Randomized Algorithms

II. Sorting And Order Statistics


6. Heapsort

7. Quicksort

8. Sorting In Linear Time

9. Medians And Order Statistics

III. Data Structures


10. Elementary Data Structures

11. Hash Tables

12. Binary Search Trees

13. Red Black Trees

14. Augmenting Data Structures

IV. Advanced Design And Analysis Techniques


15. Dynamic Programming

16. Greedy Algorithms

17. Amortized Analysis

V. Advanced Data Structures


18. B Trees

19. Fibonacci Heaps

20. van Emde Boas Trees

21. Data Structures For Disjoint Sets

VI. Graph Algorithms


22. Graph Algorithms

23. Minimum Spanning Trees

24. Single Source Shortest Paths

25. All Pairs Shortest Paths

26. Maximum Flow

VII. Selected Topics


27. Multithreaded Algorithms

28. Matrix Operations

29. Linear Programming

30. Polynomials And The F F T

31. Number Theoretic Algorithms

32. String Matching

33. Computational Geometry

34. N P Completeness

35. Approximation Algorithms

Other Material

Course Outline Fall 2017

TA Hours Fall 2017

Homework with answers, Fall 2017

Past Tests

The Algorithm Museum

Greedy Versus Dynamic Programming


GitHub Repository