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)
- thanks
http://openclassroom.stanford.edu/
No comments:
Post a Comment