Approximation Algorithms Part I
- Offered byCoursera
Approximation Algorithms Part I at Coursera Overview
Duration | 36 hours |
Start from | Start Now |
Total fee | Free |
Mode of learning | Online |
Schedule type | Self paced |
Official Website | Explore Free Course  |
Credential | Certificate |
Approximation Algorithms Part I at Coursera Highlights
- 100% online Start instantly and learn at your own schedule.
- Flexible deadlines Reset deadlines in accordance to your schedule.
- Approx. 36 hours to complete
- English Subtitles: French, Portuguese (European), Russian, English, Spanish
Approximation Algorithms Part I at Coursera Course details
- Approximation algorithms, Part I
- How efficiently can you pack objects into a minimum number of boxes? How well can you cluster nodes so as to cheaply separate a network into components around a few centers? These are examples of NP-hard combinatorial optimization problems. It is most likely impossible to solve such problems efficiently, so our aim is to give an approximate solution that can be computed in polynomial time and that at the same time has provable guarantees on its cost relative to the optimum.
- This course assumes knowledge of a standard undergraduate Algorithms course, and particularly emphasizes algorithms that can be designed using linear programming, a favorite and amazingly successful technique in this area. By taking this course, you will be exposed to a range of problems at the foundations of theoretical computer science, and to powerful design and analysis techniques. Upon completion, you will be able to recognize, when faced with a new combinatorial optimization problem, whether it is close to one of a few known basic problems, and will be able to design linear programming relaxations and use randomized rounding to attempt to solve your own problem. The course content and in particular the homework is of a theoretical nature without any programming assignments.
- This is the first of a two-part course on Approximation Algorithms.
Approximation Algorithms Part I at Coursera Curriculum
Vertex cover and Linear Programming
Lecture: Introduction
Lecture: Definition
Lecture: Integer program
Lecture: A linear programming relaxation
Lecture: Approximation algorithm
Lecture: Analysis
Lecture: General facts
Half integrality (7:35 bug, fixed in pdf slides)
Slides
All slides for all chapters of Approx Algs part 1
Attempt to upload slides in Keynote format
Slides
Slides
Slides
Slides
Slides
Slides
Practice Exercises
PDF version of the peer-graded assignment
Half-integrality slides
All slides together in one file
Quiz 1: P vs. NP review
Quiz 2
Quiz 3
Quiz 4
Quiz 5
Quiz 6
Quiz 7
Knapsack and Rounding
Lecture: Definition
Lecture: Greedy algorithm
Lecture: Special dynamic program
Lecture: General dynamic program
Lecture: algorithm
Lecture: analysis
Lecture: approximation scheme
Slides
Slides
Slides
Slides
Slides
Slides
Slides
Practise Exercises
All slides together in one file
Quiz 1
Quiz 2
Quiz 3
Quiz 4
Quiz 5
Quiz 6
Quiz 7
Bin Packing, Linear Programming and Rounding
Lecture: Next Fit
Lecture: a linear program
Lecture: small items
Lecture: large items, few sizes
Large items, many sizes
Lecture: large items analysis
Lecture: general algorithm
Lecture: conclusion
Slides (with typo corrected)
Slides
Slides
Slides
Slides
Slides
Slides
Slides
Practice Exercises
All slides together in one file
Quiz 1
Quiz 2
Quiz 3
Quiz 4
Quiz 5
Quiz 6
Quiz 7
Set Cover and Randomized Rounding
Lecture: definition
Lecture: randomized rounding
Lecture: cost analysis
Lecture: coverage analysis
Lecture: iterated algorithm
Lecture: stopping time algorithm
Lecture: stopping time analysis
Lecture:final remarks
Slides
Slides
Slides
Slides
Slides
Slides
Slides
Slides
A reference on this stopping time analysis
Practise Exercise
All slides together in one file
Quiz 1
Quiz 2
Quiz 3
Quiz 4
Quiz 5
Quiz 6
Quiz 7
Quiz 8
Multiway Cut and Randomized Rounding
Lecture: definition
Lecture: linear programming relaxation
Lecture: randomized rounding
Lecture: analysis
Lecture: conclusion
Slides
Slides
Slides
Slides
Slides
Practice exercise
All Chapter Slides together in one file
Slides for all chapters of Approx Algs Part 1 together in one file
Quiz 1 : Some context on cuts
Quiz 2
Quiz 3
Quiz 4
Quiz 5
Approximation Algorithms Part I at Coursera Admission Process
Important Dates
Other courses offered by Coursera
Student Forum
Anything you would want to ask experts?