算法导论公开课对应章节（来自MIT）_self organizing list mtf danny sleator bob tarjan

作者：小桥流水78 | 2024-07-05 14:59:33

踩

self organizing list mtf danny sleator bob tarjan

SES #	TOPICS	READINGS
L1	Administrivia Introduction Analysis of Algorithms, Insertion Sort, Mergesort	Chapters 1-2
R1	Correctness of Algorithms Horner's rule
L2	Asymptotic Notation Recurrences Substitution, Master Method	Chapters 3-4, excluding section 4.6
L3	Divide-and-Conquer: Strassen, Fibonacci, Polynomial Multiplication	Sections 4.2 and 30.1
R2	Recurrences, Sloppiness
L4	Quicksort, Randomized Algorithms	Sections 5.1-5.3 Chapter 7
R3	Heapsort, Dynamic Sets, Priority Queues	Chapter 6
L5	Linear-time Sorting: Lower Bounds, Counting Sort, Radix Sort	Sections 8.1-8.3
L6	Order Statistics, Median	Chapter 9
R4	Applications of Median Bucketsort	Section 8.4
L7	Hashing, Hash Functions	Sections 11.1-11.3
L8	Universal Hashing, Perfect Hashing	Section 11.5
R5	Quiz 1 Review
Q1	Quiz 1, In-class
R6	Binary Search Trees, Tree Walks	Sections 12.1-12.3
L9	Relation of BSTs to Quicksort Analysis of Random BST	Section 12.4
L10	Red-black Trees, Rotations, Insertions, Deletions	Chapter 13
R7	2-3 Trees, B-trees
L11	Augmenting Data Structures, Dynamic Order Statistics, Interval Trees	Chapter 14
L12	Skip Lists	Skip Lists handout (PDF)
R8	Range Trees
L13	Amortized Algorithms, Table Doubling, Potential Method	Chapter 17
L14	Competitive Analysis: Self-organizing Lists	Sleator, 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.
R9	Competitive Analysis: Ski Rental, Randomized Competitive Algorithm
L15	Dynamic Programming, Longest Common Subsequence	Chapter 15
L16	Greedy Algorithms, Minimum Spanning Trees	Sections 16.1-16.3 and 22.1 Chapter 23
L17	Shortest Paths I: Properties, Dijkstra's Algorithm, Breadth-first Search	Section 22.2 Chapter 24
L18	Shortest Paths II: Bellman-Ford, Linear Programming, Difference Constraints
R10	Graph Searching: Depth-first Search, Topological Sort, DAG Shortest Paths	Sections 22.3-22.4
L19	Shortest Paths III: All-pairs Shortest Paths, Matrix Multiplication, Floyd-Warshall, Johnson	Chapter 25
L20	Quiz 2 Review
L21	Ethics, Problem Solving (Mandatory Attendance)
Q2	Quiz 2, In-class
L22	Advanced Topics	Dynamic Multithreaded Algorithms handout (PDF)
L23	Advanced Topics (cont.)
R11	Advanced Topics
L24	Advanced 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 ofLecture Notes in Computer Science. Berlin, Germany: Springer-Verlag.
L25	Advanced Topics (cont.) Discussion of Follow-on Classes

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小桥流水78/article/detail/790365