Course Outline: CS 601, Algorithms and Complexity

CS 601, Algorithms and Complexity

Teaching Assistants:

Srinivas Karthik (skarthikv@cse), Sagar Kale (sag@cse), Jagadish M (jagadish@cse).

Office hours:

Monday 4-5

Eligibility:

Only for CSE PGs. It is recommended that you should have done a UG Algorithm design course; if not, you may want to take the UG algorithms course instead. PGs from other departments: talk to me. CSE/other UGs: not eligible.

Quiz 0 to help you get a sense of the skills required for the course. Also read the remarks there.

Topics:

Network flow. NP-completeness. Approximation Algorithms. Randomized Algorithms. Respectively chapters 7,8,11,13 of the text book.

Text book: (must have)

Algorithm Design. Jon Kleinberg and Eva Tardos. Addison Wesley. Indian Edition available.

Lecture notes, and additional reading

Consult the homepage frequently.

Evaluation:

All the tests are closed book and closed notes. Cooperation is OK on homeworks, but see below.

2 Quizzes (10 marks each)
Midterm (20 marks)
Homeworks (10 marks). There will be n (about 10) homeworks which will be graded. You will be deemed as having got the full marks on a homework if you get at least 50%. The score on the best n-2 out of the n will be scaled up to 10 marks. You are allowed to discuss homeworks with friends, but you must write answers on your own. Delayed submissions will not be accepted in general and there will be no make up homeworks.
Beware of relying too much on friends; you may get full marks on homeworks without learning how to really solve problems. Please discuss with me if you are unable to solve problems on your own.
Final examination (50 marks).

Quizzes will be held in the slots 7A and 7B. Please make sure that you do not schedule anything else in those slots. If some other quiz is scheduled in conflict with our quiz it is your responsibility to let me know as soon as I announce our quiz.

If you miss a quiz or a test for valid reasons (you need a "pink slip" from the IIT hospital for medical reasons), the marks from the other exams will be prorated to make up.

Requirements for audit:

Only homeworks and quizzes as above.