Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

Tsinghua University

算法设计与分析

Tsinghua University via XuetangX

Overview

     本课程系统介绍算法设计与分析的方法和理论,包括算法基础、图、贪婪算法、分治、动态规划、网络流、计算复杂性初步、近似算法及随机算法等。同时,本课程还包含算法领域的一些前沿课题和最新进展。本课程可以作为数学、计算机等相关专业的学生关于算法理论的基础课程。

      算法设计与分析是计算机科学及运筹学的一门基础性课程,在清华大学数学系已经开设了10几年的时间,一般在秋季学期开设,4学分64课时,有来自数学系,计算机系,工业工程,经管学院及一些工科院系的学生选课,选课学生比较踊跃,课容量多次扩大。学生普遍反映课程内容精彩、有用、有趣。在算法广泛应用和飞速发展的时代,学生通过对这门课程的学习,进入了算法领域,掌握其基本理论和方法,提升思维方式,为今后的学习、科研和工作打下坚实基础。 

Syllabus

  • 1 Introduction of Algorithm
    • 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 Basics of Algorithm Analysis
    • 2.1 Computational Tractability
    • 2.2 Asymptotic Order of Growth
    • 2.3 A Survey of Common Running Times
    • Homework2
    • Lecture note 2
  • 3 Graph
    • 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 Greedy Algorithms
    • 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 Divide and Conquer
    • 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 Dynamic Programming
    • 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 Network Flow
    • 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 NP and Computational Intractability
    • 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 Approximation Algorithms
    • 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 Local Search
    • 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 Randomized Algorithms
    • 11.1 Contention Resolution
    • 11.2 Linearity of Expectation
    • 11.3 MAX 3-SAT
    • 11.4 Chernoff Bounds
    • Homework11
    • Lecture note 11
  • Exam
    • Exam

Taught by

Zhenbo Wang

Tags

Reviews

Start your review of 算法设计与分析

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.