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