Search This Blog

Sunday, September 14, 2014

Design and Analysis of Algorithms

Prof. Tim Roughgarden

COURSE DESCRIPTION

Overview course:   Introduction to fundamental techniques for designing and analyzing algorithms, including asymptotic analysis; divide-and-conquer algorithms and recurrences; greedy algorithms; data structures; dynamic programming; graph algorithms; and randomized algorithms.
Required textbook:   Kleinberg and Tardos, Algorithm Design, Covering Most of Chapters 4-6 will be 2005. We, some Parts of Chapter 13, and in The Book of Not A couple topics.
Prerequisites:   Introduction to proofs, and with with discrete Mathematics and Probability (eg, CS 103 and Stat116). If you have not taken a probability course, you should expect to do some independent reading during the course on topics including random variables, expectation, conditioning, and basic combinatorics.

1. INTRODUCTION (1/4/2011)



2. BASIC DIVIDE & CONQUER (1/6/2011)



3. THE MASTER METHOD (1/11/2011)



4. LINEAR-TIME MEDIAN (1/13/2011)
We apologize for the poor audio quality in this video.



5. GRAPH SEARCH & DIJKSTRA'S ALGORITHM (1/18/2011)



6. CONNECTIVITY IN DIRECTED GRAPHS (1/20/2011)



7. INTRODUCTION TO GREEDY ALGORITHMS (1/25/2011)



8. MINIMUM SPANNING TREES (1/27/2011)



9. KRUSKAL'S ALGORITHM AND UNION-FIND (2/1/2011)



10. PATH COMPRESSION AND CLUSTERING (2/3/2011)



11. INTRODUCTION TO RANDOMIZED ALGORITHMS (2/8/2011)



12. QUICKSORT (2/10/2011)



13. HASHING (2/15/2011)



14. BALANCED SEARCH TREES AND SKIP LISTS (2/17/2011)



15. INTRODUCTION TO DYNAMIC PROGRAMMING (2/22/2011)



16. SEQUENCE ALIGNMENT (2/24/2011)



17. SHORTEST PATHS: BELLMAN-FORD AND FLOYD-WARSHALL (3/1/2011)



18. NP-COMPLETE PROBLEMS (3/3/2011)



19. APPROXIMATION ALGORITHMS (3/8/2011)



20. THE WIDER WORLD OF ALGORITHMS (3/10/2011)


http://openclassroom.stanford.edu/