INTRODUCTION
Why Study Algorithms ? (4 min)
Integer Multiplication (9 min)
Karatsuba Multiplication (13 min)
Merge Sort: Motivation and Example (9 min)
Merge Sort: Pseudocode (13 min)
Guiding Principles for Analysis of Algorithms (15 min)
ASYMPTOTIC ANALYSIS
Additional Examples [Review - Optional] (8 min)
DIVIDE & CONQUER ALGORITHMS
O(n log n) Algorithm for Counting Inversions I (13 min)
O(n log n) Algorithm for Counting Inversions II (17 min)
Strassen's Subcubic Matrix Multiplication Algorithm (22 min)
O(n log n) Algorithm for Closest Pair I [Advanced - Optional] (32 min)
O(n log n) Algorithm for Closest Pair II [Advanced - Optional] (19 min)
Homework 1
Problem Set 该内容计入总分。
Programming Assignment 该内容计入总分。
THE MASTER METHOD
Interpretation of the 3 Cases (11 min)
QUICKSORT - ALGORITHM
Partitioning Around a Pivot (25 min)
Correctness of Quicksort [Review - Optional] (11 min)
QUICKSORT - ANALYSIS
Analysis I: A Decomposition Principle [Advanced - Optional] (22 min)
Analysis II: The Key Insight [Advanced - Optional] (12min)
Analysis III: Final Calculations [Advanced - Optional] (9min)
PROBABILITY REVIEW
Probability Review I [Review - Optional] (25 min)
Probability Review II [Review - Optional] (17 min)
Homework 2
Problem Set 该内容计入总分。
Programming Assignment 该内容计入总分。
LINEAR-TIME SELECTION
Randomized Selection - Algorithm (22 min)
Randomized Selection - Analysis (21 min)
Deterministic Selection - Algorithm [Advanced - Optional] (17 min)
Deterministic Selection - Analysis I [Advanced - Optional] (22 min)
Deterministic Selection - Analysis II [Advanced - Optional] (13 min)
Omega(n log n) Lower Bound for Comparison-Based Sorting [Advanced - Optional] (13 min)
GRAPHS AND THE CONTRACTION ALGORITHM
Graphs and Minimum Cuts (16 min)
Graph Representations (14 min)
Random Contraction Algorithm (9 min)
Analysis of Contraction Algorithm (30 min)
Homework 3
Problem Set 该内容计入总分。
Programming Assignment 该内容计入总分。
GRAPH SEARCH AND CONNECTIVITY
Graph Search - Overview (23 min)
Breadth-First Search (BFS): The Basics (14 min)
BFS and Shortest Paths (8 min)
BFS and Undirected Connectivity (13 min)
Depth-First Search (DFS): The Basics (7 min)
Computing Strong Components: The Algorithm (29 min)
Computing Strong Components: The Analysis (26 min)
Structure of the Web [Optional] (19 min)
Homework 4
Problem Set 该内容计入总分。
Programming Assignment 该内容计入总分。
DIJKSTRA'S SHORTEST-PATH ALGORITHM
Dijkstra's Shortest-Path Algorithm (21 min)
Dijkstra's Algorithm: Examples (13 min)
Correctness of Dijkstra's Algorithm [Advanced - Optional] (19 min)
Dijkstra's Algorithm: Implementation and Running Time (26 min)
HEAPS
Data Structures: Overview (5 min)
Heaps: Operations and Applications (18 min)
Heaps: Implementation Details [Advanced - Optional] (21 min)
BALANCED BINARY SEARCH TREES
Balanced Search Trees: Operations and Applications (11 min)
Binary Search Tree Basics I (13 min)
Binary Search Tree Basics, Part II (30 min)
Rotations [Advanced - Optional] (8 min)
Insertion in a Red-Black Tree [Advanced] (15 min)
Homework 5
Problem Set 该内容计入总分。
Programming Assignment 该内容计入总分。
HASHING: THE BASICS
Hash Tables: Operations and Applications (19 min)
Hash Tables: Implementation Details I (19 min)
Hash Tables: Implementation Details II (22 min)
UNIVERSAL HASHING
Pathological Data Sets and Universal Hashing Motivation (22 min)
Universal Hashing: Definition and Example [Advanced - Optional] (26 min)
Universal Hashing: Analysis of Chaining [Advanced - Optional] (19 min)
Hash Table Performance with Open Addressing [Advanced - Optional] (16 min)
BLOOM FILTERS
Bloom Filters: The Basics (16 min)
Bloom Filters: Heuristic Analysis (13 min)
Homework 6
Problem Set 该内容计入总分。
Programming Assignment 该内容计入总分。
Final Exam
Final Exam 该内容计入总分。
介绍
合并排序：分析（9分钟）Part1 Part2 Part3
渐近分析
要点（14分钟）Part1 Part2 Part3 Part4 Part5
大哦记法（4分钟）
基本范例（7分钟）
大欧米茄和西塔（7分钟）
附加示例[审阅-可选]（8分钟）
分而治之算法
O（n log n）个用于计算反转I的算法（13分钟）
O（n log n）的反演计数算法II（17分钟）
Strassen的亚三次矩阵乘法算法（22分钟）
最近对I的O（n log n）算法[高级-可选]（32分钟）
最接近对II的O（n log n）算法[高级-可选]（19分钟）
作业1
问题集1
可选理论问题
编程作业1
主方法
概观
动机（8分钟）
正式声明（10分钟）
范例（13分钟）
证明I（10分钟）
解读3例（11分钟）
证明II（16分钟）
快速排序-算法
快速排序：概述（12分钟）
围绕枢轴进行分区（25分钟）
快速排序的正确性[查看-可选]（11分钟）
选择一个好的支点（22分钟）
快速排序-分析
分析I：分解原理[高级-可选]（22分钟）
分析II：Key Insight [高级-可选]（12分钟）
分析III：最终计算[高级-可选]（9分钟）
概率审查
概率复习I [复习-可选]（25分钟）
概率复习II [复习-可选]（17分钟）
作业2
问题集2
可选理论问题
编程作业2
线性时间选择
概观
随机选择-算法（22分钟）
随机选择-分析（21分钟）
确定性选择-算法[高级-可选]（17分钟）
确定性选择-分析I [高级-可选]（22分钟）
确定性选择-分析II [高级-可选]（13分钟）
Omega（n log n）下界，用于基于比较的排序[高级-可选]（13分钟）
图和约束算法
图形和最小切割（16分钟）
图形表示（14分钟）
随机收缩算法（9分钟）
收缩算法分析（30分钟）
计算最小切割数（7分钟）
作业3
问题集3
可选理论问题
编程作业3
图形搜索和连接
概观
图形搜索-概述（23分钟）
广度优先搜索（BFS）：基础知识（14分钟）
BFS和最短路径（8分钟）
BFS和无定向连接（13分钟）
深度优先搜索（DFS）：基础知识（7分钟）
拓扑排序（22分钟）
计算强成分：算法（29分钟）
计算强成分：分析（26分钟）
网络结构[可选]（19分钟）
作业4
问题集4
可选理论问题
编程作业4
迪克斯特拉的最短路径算法
概观
Dijkstra的最短路径算法（21分钟）
Dijkstra的算法：示例（13分钟）
Dijkstra算法的正确性[高级-可选]（19分钟）
Dijkstra的算法：实现和运行时间（26分钟）
堆
数据结构：概述（5分钟）
堆：操作和应用程序（18分钟）
堆：实施细节[高级-可选]（21分钟）
平衡二叉树
平衡的搜索树：操作和应用程序（11分钟）
二叉搜索树基础I（13分钟）
二进制搜索树基础，第二部分（30分钟）
红黑树（21分钟）
旋转[高级-可选]（8分钟）
插入红黑树中[高级]（15分钟）
作业5
习题集5
可选理论问题
编程作业5
哈希：基础
概观
哈希表：操作和应用程序（19分钟）
哈希表：实现细节I（19分钟）
哈希表：实施细节II（22分钟）
通用哈希
病理数据集和通用哈希动机（22分钟）
通用哈希：定义和示例[高级-可选]（26分钟）
通用哈希：链接分析[高级-可选]（19分钟）
带有开放寻址的哈希表性能[高级-可选]（16分钟）
花朵滤镜
Bloom Filters：基础知识（16分钟）
布隆过滤器：启发式分析（13分钟）
作业6
习题集6
可选理论问题
编程作业6
期末考试
期末考试
网友评论