Approximation Algorithms Spring 2018
|Lecture timings||Tuesday 05:30PM – 07:00PM in LT2 Level 4||Wednesday 07:00PM – 08:30PM LT2 Level 4|
|Required text||Williamson & Shmoys, The Design of Approximation Algorithms||Vijay Vazirani, Approximation Algorithms|
|Prerequisite||Advance Algorithm Analysis|
— Bulletin Board —
||Here is the Latex Template .|
|Lecture 1||Here is the Lecture#1 Notes .|
|Lecture 2||Here is the Lecture#2 Notes .|
|HW 2||Here is the Homework 2 . Deadline is 20th Feb 2018.|
|HW 3||Here is the Homework 3 . Deadline is 28th Feb 2018.|
|There will be homeworks, in-class quizzes, presentations, some lecture notes and two exams. The grade break down will be as follows:
– Homeworks and Quizzes (30%)
– Participation(Class + Blog) (10%)
– Lecture Notes(LaTeX + Blog) (15%)
– Project (40%)
Note : Final grades will be curved.
|The homework assignments will be related to topics which we will discuss in class.|
|Students have to submit homework individually.|
|NO LATE HOMEWORKS WILL BE ACCEPTED.|
|To fairly account for natural disasters and emergencies, everyone is allowed to skip one homework and one quiz. If you choose to solve all homeworks(quizzes), your homework(quiz) with the least score will be discarded while computing your final grade.|
|25% credit will be given for any question for clearly marking the question with “I DON’T KNOW”. Questions with an entirely wrong answer will get 0% credit, but a partially correct answer will get partial credit. So if u don’t have any idea about a problem, it’s better for you to admit that you don’t know something, rather than trying to fake it. But, if you have some idea, but its not entirely correct but is partially correct, you should show your partial solution|
|Under the Honor Code, each of you is expected to submit your own work in this course. However, as outlined above, for the homework submissions, you are allowed to work in groups or to ask for general advice from the course staff or other experts. Such activity is both acceptable and encouraged, but you must indicate any collaboration or assistance on your solution sets.|
|Any collaboration or assistance that is not given proper citation may be considered a violation of the Honor Code.|
|You are responsible for understanding and being able to explain the solutions you submit.|
|In case of plagiarism you may receive an ‘F’ grade in this course along with penalties dictated by university policy. The course staff will actively pursue any suspected cases of Honor Code violations.|
- 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.
- Knapsack and Rounding: This module shows the power of rounding by using it todesign a near-optimal solution to another basic problem: the Knapsack problem.
- 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.)
- 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.
- Multiway Cut and Randomized Rounding: This module deepens the understanding of randomized rounding by developing a sophisticated variant and applying it to another basic problem, the Multiway Cut problem.