欢迎来到在线教学平台
问题答疑
精品课程
全部课程
公开课
云课直播
新闻公告
数图资源
智汇大讲堂
更多
精品课程
全部课程
公开课
云课直播
新闻公告
数图资源
智汇大讲堂
教师登录
学生登录
精品课程
全部课程
公开课
云课直播
新闻公告
数图资源
智汇大讲堂
首页 - 课程列表 - 课程详情
返回
算法设计与分析
课程类型：
选修课
主讲教师：
王振波
课程来源：
清华大学
建议学分：
3.00分
课程编码：
xtzx0557
课程介绍
课程目录
教师团队
1 Introduction of Algorithm
s
1.1 Introduction
（5分钟）
s
1.2 A First Problem: Stable Matching
（5分钟）
s
1.3 Gale-Shapley Algorithm
（6分钟）
s
1.4 Understanding Gale-Shapley Algorithm
（7分钟）
2 Basics of Algorithm Analysis
s
2.1 Computational Tractability
（4分钟）
s
2.2 Asymptotic Order of Growth
（5分钟）
s
2.3 A Survey of Common Running Times
（6分钟）
3 Graph
s
3.1 Basic Definitions and Applications
（8分钟）
s
3.2 Graph Traversal
（5分钟）
s
3.3 Testing Bipartiteness
（4分钟）
s
3.4 Connectivity in Directed Graphs
（4分钟）
s
3.5 DAG and Topological Ordering
（8分钟）
4 Greedy Algorithms
s
4.1 Coin Changing
（6分钟）
s
4.2 Interval Scheduling
（6分钟）
s
4.3 Interval Partitioning
（3分钟）
s
4.4 Scheduling to Minimize Lateness
（6分钟）
s
4.5 Optimal Caching
（9分钟）
s
4.6 Shortest Paths in a Graph
（7分钟）
s
4.7 Minimum Spanning Tree
（5分钟）
s
4.8 Correctness of Algorithms
（5分钟）
s
4.9 Clustering
（5分钟）
5 Divide and Conquer
s
5.1 Mergesort
（10分钟）
s
5.2 Counting Inversions
（7分钟）
s
5.3 Closest Pair of Points
（8分钟）
s
5.4 Integer Multiplication
（4分钟）
s
5.5 Matrix Multiplication
（6分钟）
s
5.6 Convolution and FFT
（8分钟）
s
5.7 FFT
（5分钟）
s
5.8 Inverse DFT
（5分钟）
6 Dynamic Programming
s
6.1 Weighted Interval Scheduling
（11分钟）
s
6.2 Segmented Least Squares
（5分钟）
s
6.3 Knapsack Problem
（7分钟）
s
6.4 RNA Secondary Structure
（9分钟）
s
6.5 Sequence Alignment
（6分钟）
s
6.6 Shortest Paths
（6分钟）
7 Network Flow
s
7.1 Flows and Cuts
（6分钟）
s
7.2 Minimum Cut and Maximum Flow
（5分钟）
s
7.3 Ford-Fulkerson Algorithm
（9分钟）
s
7.4 Choosing Good Augmenting Paths
（8分钟）
s
7.5 Bipartite Matching
（6分钟）
8 NP and Computational Intractability
s
8.1 Polynomial-Time Reductions
（6分钟）
s
8.2 Basic Reduction Strategies I
（6分钟）
s
8.3 Basic Reduction Strategies II
（8分钟）
s
8.4 Definition of NP
（6分钟）
s
8.5 Problems in NP
（7分钟）
s
8.6 NP-Completeness
（6分钟）
s
8.7 Sequencing Problems
（10分钟）
s
8.8 Numerical Problems
（8分钟）
s
8.9 co-NP and the Asymmetry of NP
（3分钟）
9 Approximation Algorithms
s
9.1 Load Balancing
（12分钟）
s
9.2 Center Selection
（8分钟）
s
9.3 The Pricing Method: Vertex Cover
（6分钟）
s
9.4 LP Rounding: Vertex Cover
（7分钟）
s
9.5 Knapsack Problem
（12分钟）
10 Local Search
s
10.1 Landscape of an Optimization Problem
（4分钟）
s
10.2 Maximum Cut
（7分钟）
s
10.3 Nash Equilibria
（6分钟）
s
10.4 Price of Stability
（8分钟）
11 Randomized Algorithms
s
11.1 Contention Resolution
（7分钟）
s
11.2 Linearity of Expectation
（5分钟）
s
11.3 MAX 3-SAT
（7分钟）
s
11.4 Chernoff Bounds
（5分钟）
京公网安备 11011502004263