課程信息
6,606 次近期查看

100% 在線

立即開始,按照自己的計劃學習。

可靈活調整截止日期

根據您的日程表重置截止日期。

完成時間大約為21 小時

建議:4 hours/week...

英語(English)

字幕:英語(English)

100% 在線

立即開始,按照自己的計劃學習。

可靈活調整截止日期

根據您的日程表重置截止日期。

完成時間大約為21 小時

建議:4 hours/week...

英語(English)

字幕:英語(English)

教學大綱 - 您將從這門課程中學到什麼

1
完成時間為 6 小時

Vertex cover and Linear Programming

We introduce the course topic by a typical example of a basic problem, called Vertex Cover, for which we will design and analyze a state-of-the-art approximation algorithm using two basic techniques, called Linear Programming Relaxation and Rounding. It is a simple, elementary application of powerful techniques.

...
8 個視頻 (總計 54 分鐘), 13 個閱讀材料, 8 個測驗
8 個視頻
Lecture: Definition4分鐘
Lecture: Integer program6分鐘
Lecture: A linear programming relaxation6分鐘
Lecture: Approximation algorithm6分鐘
Lecture: Analysis6分鐘
Lecture: General facts5分鐘
Half integrality (7:35 bug, fixed in pdf slides)10分鐘
13 個閱讀材料
Slides10分鐘
All slides for all chapters of Approx Algs part 110分鐘
Attempt to upload slides in Keynote format10分鐘
Slides10分鐘
Slides10分鐘
Slides10分鐘
Slides10分鐘
Slides10分鐘
Slides10分鐘
Practice Exercises10分鐘
PDF version of the peer-graded assignment10分鐘
Half-integrality slides10分鐘
All slides together in one file10分鐘
7 個練習
Quiz 1: P vs. NP review6分鐘
Quiz 28分鐘
Quiz 34分鐘
Quiz 46分鐘
Quiz 54分鐘
Quiz 64分鐘
Quiz 74分鐘
2
完成時間為 5 小時

Knapsack and Rounding

This module shows the power of rounding by using it to design a near-optimal solution to another basic problem: the Knapsack problem.

...
7 個視頻 (總計 52 分鐘), 9 個閱讀材料, 8 個測驗
7 個視頻
Lecture: Greedy algorithm5分鐘
Lecture: Special dynamic program8分鐘
Lecture: General dynamic program8分鐘
Lecture: algorithm6分鐘
Lecture: analysis7分鐘
Lecture: approximation scheme4分鐘
9 個閱讀材料
Slides10分鐘
Slides10分鐘
Slides10分鐘
Slides10分鐘
Slides10分鐘
Slides10分鐘
Slides10分鐘
Practise Exercises10分鐘
All slides together in one file10分鐘
7 個練習
Quiz 12分鐘
Quiz 22分鐘
Quiz 34分鐘
Quiz 42分鐘
Quiz 52分鐘
Quiz 62分鐘
Quiz 72分鐘
3
完成時間為 5 小時

Bin Packing, Linear Programming and Rounding

This module shows the sophistication of rounding by using a clever variant for another basic problem: bin packing. (This is a more advanced module.)

...
8 個視頻 (總計 74 分鐘), 10 個閱讀材料, 8 個測驗
8 個視頻
Lecture: a linear program12分鐘
Lecture: small items6分鐘
Lecture: large items, few sizes11分鐘
Large items, many sizes8分鐘
Lecture: large items analysis8分鐘
Lecture: general algorithm7分鐘
Lecture: conclusion6分鐘
10 個閱讀材料
Slides (with typo corrected)10分鐘
Slides10分鐘
Slides10分鐘
Slides10分鐘
Slides10分鐘
Slides10分鐘
Slides10分鐘
Slides10分鐘
Practice Exercises10分鐘
All slides together in one file10分鐘
7 個練習
Quiz 14分鐘
Quiz 26分鐘
Quiz 32分鐘
Quiz 46分鐘
Quiz 54分鐘
Quiz 66分鐘
Quiz 76分鐘
4
完成時間為 5 小時

Set Cover and Randomized Rounding

This module introduces a simple and powerful variant of rounding, based on probability: randomized rounding. Its power is applied to another basic problem, the Set Cover problem.

...
8 個視頻 (總計 58 分鐘), 11 個閱讀材料, 9 個測驗
8 個視頻
Lecture: randomized rounding4分鐘
Lecture: cost analysis5分鐘
Lecture: coverage analysis8分鐘
Lecture: iterated algorithm4分鐘
Lecture: stopping time algorithm4分鐘
Lecture: stopping time analysis10分鐘
Lecture:final remarks6分鐘
11 個閱讀材料
Slides10分鐘
Slides10分鐘
Slides10分鐘
Slides10分鐘
Slides10分鐘
Slides10分鐘
Slides10分鐘
Slides10分鐘
A reference on this stopping time analysis10分鐘
Practise Exercise10分鐘
All slides together in one file10分鐘
8 個練習
Quiz 12分鐘
Quiz 22分鐘
Quiz 32分鐘
Quiz 44分鐘
Quiz 52分鐘
Quiz 62分鐘
Quiz 72分鐘
Quiz 84分鐘
4.7
34 個審閱Chevron Right

來自Approximation Algorithms Part I的熱門評論

創建者 DAJan 27th 2016

The course provides a high-level introduction to approximation algorithm. There is no programming assignments but it provides nice introduction to approximation algorithm.

創建者 ZWSep 17th 2017

This course is awesome. Prof. managed to elaborate the problem and analysis clearly and homework is properly assigned.

關於 法国巴黎高等师范学院

L’École normale supérieure (ENS) est un établissement d'enseignement supérieur pour les études prédoctorales et doctorales (graduate school) et un haut lieu de la recherche française. L'ENS offre à 300 nouveaux étudiants et 200 doctorants chaque année une formation de haut niveau, largement pluridisciplinaire, des humanités et sciences sociales aux sciences dures. Régulièrement distinguée au niveau international, l'ENS a formé 10 médailles Fields et 13 prix Nobel....

常見問題

  • 注册以便获得证书后,您将有权访问所有视频、测验和编程作业(如果适用)。只有在您的班次开课之后,才可以提交和审阅同学互评作业。如果您选择在不购买的情况下浏览课程,可能无法访问某些作业。

還有其他問題嗎?請訪問 學生幫助中心