信息时代,算法为王,和我一起进入算法的世界。
播放:51361次,课程ID:4231227
信息时代,算法为王,和我一起进入算法的世界。
--1.1 Introduction
--1.2 A First Problem: Stable Matching
--1.3 Gale-Shapley Algorithm
--1.4 Understanding Gale-Shapley Algorithm
--Homework1
--Lecture note 1
--2.1 Computational Tractability
--2.2 Asymptotic Order of Growth
--2.3 A Survey of Common Running Times
--Homework2
--Lecture note 2
--3.1 Basic Definitions and Applications
--3.2 Graph Traversal
--3.3 Testing Bipartiteness
--3.4 Connectivity in Directed Graphs
--3.5 DAG and Topological Ordering
--Homework3
--Lecture note 3
--4.1 Coin Changing
--4.2 Interval Scheduling
--4.3 Interval Partitioning
--4.4 Scheduling to Minimize Lateness
--4.5 Optimal Caching
--4.6 Shortest Paths in a Graph
--4.7 Minimum Spanning Tree
--4.8 Correctness of Algorithms
--4.9 Clustering
--Homework4
--Lecture note 4
--5.1 Mergesort
--5.2 Counting Inversions
--5.3 Closest Pair of Points
--5.4 Integer Multiplication
--5.5 Matrix Multiplication
--5.6 Convolution and FFT
--5.7 FFT
--5.8 Inverse DFT
--Homework5
--Lecture note 5
--6.1 Weighted Interval Scheduling
--6.2 Segmented Least Squares
--6.3 Knapsack Problem
--6.4 RNA Secondary Structure
--6.5 Sequence Alignment
--6.6 Shortest Paths
--Homework6
--Lecture note 6
--7.1 Flows and Cuts
--7.2 Minimum Cut and Maximum Flow
--7.3 Ford-Fulkerson Algorithm
--7.4 Choosing Good Augmenting Paths
--7.5 Bipartite Matching
--Homework7
--Lecture note 7
--8.1 Polynomial-Time Reductions
--8.2 Basic Reduction Strategies I
--8.3 Basic Reduction Strategies II
--8.4 Definition of NP
--8.5 Problems in NP
--8.6 NP-Completeness
--8.7 Sequencing Problems
--8.8 Numerical Problems
--8.9 co-NP and the Asymmetry of NP
--Homework8
--Lecture note 8
--9.1 Load Balancing
--9.2 Center Selection
--9.3 The Pricing Method: Vertex Cover
--9.4 LP Rounding: Vertex Cover
--9.5 Knapsack Problem
--Homework9
--Lecture note 9
--10.1 Landscape of an Optimization Problem
--10.2 Maximum Cut
--10.3 Nash Equilibria
--10.4 Price of Stability
--Homework10
--Lecture note 10
--11.1 Contention Resolution
--11.2 Linearity of Expectation
--11.3 MAX 3-SAT
--11.4 Chernoff Bounds
--Homework11
--Lecture note 11
--Exam
王振波,清华大学数学科学系副教授,2006年在清华大学数学科学系获得博士学位。主要研究方向为算法设计与分析。曾获清华大学优秀博士后,清华大学研究生精品课课程负责人,清华大学教学成果一等奖,北京青年优秀科技论文奖等。讲授《高等数学》、《线性代数》、《数学实验》等本科生课程,及《算法设计与分析》、《计算复杂性理论》、《网络优化》等研究生课程。