Randomized Algorithms

Organizational Details:

Term: Jan - May 2018

Location: CS26

Slot: "B" (Mon 9 - 9.50, Tue 8 - 8.50, Wed 12 - 12.50, Fri 11 - 11.50)

Instructor: John Augustine

Office Hours: Fridays 2.30 - 4.30. During this time, I will be available in my office to address any course related issues.

Textbook: There are several useful books, drafts, lecture notes, and research articles for this course, but for this offering, we will largely follow the book: Randomized Algorithms, by Motwani and Raghavan.

Quiz Dates: Feb 17 (FN) and March 24 (FN).

Teaching Assistants (tentative until dept confirmation);

• Barath Ashok
• Purnata Ghosal
• Jithin Vachery

Prerequisites: An algorithms course and a probability course. This course will be unsuitable for you if you are unfamiliar with basic algorithms and/or basic probability theory. Please take those introductory courses first.

What to Expect?

• This is a problem solving course. As the name indicates, we will be focussing on algorithm design when given the ability to toss coins along the way. Is this some esoteric notion that is applicable in rare situations? Not at all. On the contrary, almost all modern classes of algorithms (data mining, machine learning, cryptography, distributed algorithms, etc. comprise randomized algorithms at their very cores.)
• The general syllabus can be seen under the syllabus tab. The list of topics covered in this offering -- including references -- will be posted under the updates tab.
• You will be expected to own a copy of Motwani and Raghavan. The cost is < ₹600 < ₹650 at Amazon. Please procure a copy asap. There will be in class mini-tests where I plan to allow you to refer to the textbook.
• Please read my expectations on academic honesty thoroughly.

Grading Scheme

Problem Sets: 5 @ 4 marks each = 20

Surprise mini-tests: Best 5 out of at least 6 @ 2 marks each = 10

Quizzes: 2 @ 20 marks each = 40

Final Exam: 1 @ 30 marks = 30

I reserve the right to make minor adjustments with due notice.

Attendance policy: I try to keep my classes as interactive as possible. To get the best out of them, it is important that you attend and participate regularly. With this in mind, I will -- in spirit -- follow the institute policy of 85% attendance. Those who fail to maintain this attendance requirement will be awarded a "W" grade. Medical and other exceptions routed through the Dean of Academic Courses will, of course, be honoured.

Question and Answer Forum

Please join the fun at <https://groups.google.com/d/forum/18-cs6170>. Please click on the Forum tab above to participate once you have signed up and signed in.