Instructor

Muddasir Shabbir
Email: mudassir.shabbir@itu.edu.pk Office Hours:
Tue 04:00-06:00 PM and/or By appointment.

Approximation Algorithms Spring 2018

Course Information

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 —

 
























Topic News
Latex Template
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.
Lecture 4 Here is the Lecture#4 Notes .
Lecture 5 Here is the Lecture#5 Notes .
Lecture 6 Here is the Lecture#6 Notes .
HW 4 Here is the Homework 4 . Deadline is 7th March 2018.
HW 5 Here is the Homework 5. Deadline is 14th March 2018.
Lecture 7 Here is the Lecture#7 Notes.
Lecture 8 Here is the Lecture#8 Notes.
Lecture 9 Here is the Lecture#9 Notes
Lecture 10 Here is the Lecture#10 Notes.
HW 6 Here is the Homework 6. Deadline is 26th March 2018.
HW 7 Here is the Homework 7. Deadline is 18th April 2018.
HW 8 Here is the Homework 8. Deadline is 25th April 2018.
Lecture 11 Here is the Lecture#11 Notes.
Lecture 12 Here is the Lecture#12 Notes.
Lecture 13 Here is the Lecture#13 Notes.
Lecture 18 Here is the Lecture#18 Notes.
Lecture 19 Here is the Lecture#19 Notes.
Lecture 20-21 Here is the Lecture#20-21 Notes.
Lecture 22 Here is the Lecture#22 Notes.

 


Policies

Grading

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

Academic dishonesty

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.

———
Details regarding the course will be added to this as they become available. Feel free to send your queries to: mudassir@rutgers.edu
———
Intended Audience:
This course is intended towards a potential research body in the theory of computer science. So if you are committed to pursue a PhD in CS, or are a faculty member who regularly teaches theory course at your institute, this course is an ideal window towards more they for you. This course is NOT aimed at software engineers; this course will NOT help you write more efficient or better software, and this course will certainly NOT help get you a better job.
This is an advanced course in theory so you must already be versed with discrete math, graphs, algorithms, and probability theory.
%For example you should be quite comfortable solving our algorithms course Midterm Exam available at the following link:
How to Register:
To register please send an email to mudassir@rutgers.edu with title: REGISTER FOR AA. Please write a paragraph about you and why you should be registered for this course. You will be called for a short interview and if we find that you can benefit from this course, we will approve your registration. Admission/Registrar office will help you with documentation afterwards. There are a total about 20 seats and a majority of those seats are reserved for ITU students. Remaining seats are on first come basis so it is suggested to have your interview scheduled at earliest.

Course Contents:
The goal of this course is to learn the tools and technique to design approximation algorithms. As Linear Programming is probably the most effective candidate, we will spend a considerable time studying examples of NP-Hard problems that can be approximately solved by LP. After that we will study the Semidefinite Programming and its applications. We will study the analysis of general greedy techniques and see it has an effect on sub modular objectives. If we get time we will do a little bit of Fixed Parameter Tractability. Program for the first 3-4 weeks of the course may look like the following list from Claire Mathieu course on the same topic.
  • 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.
Schedule:
We will start our classes in early Feb and will remain engage for next 16 weeks. Each week we will meet twice on WEEKDAYS. The timing of the class is not final yet but our graduate level classes are usually scheduled in the time window of 4PM to 8:30PM.
Class Participation:
As a participant in the class, you will be required to attend the lecture and contribute towards the discussion. Moreover you will be asked to read research papers from time to time and present them in the class. You will also have to complete homeworks, and scribe lecture notes on your turn.
About Instructor:
Mudassir Shabbir has been associated with Information Technology as an Assistant Professor since he received his PhD from  Rutgers University, NJ USA in 2014. He enjoys working in theoretical computer science while his main area of research is Algorithmic and Discrete Geometry. He has developed new methods for the characterization and computation of succinct representations of large data sets with applications in nonparametric statistical analysis. He also works in Approximation Algorithms, Combinatorics, and Extremal Graph Theory.
Previously, Mudassir has worked at LUMS, Lahore, Los Alamos National Labs, NM, Bloomberg L.P. New York, NY and at Rutgers University. He was Rutgers Honors Fellow for 2011-12.