Probability & Computing

Organizational Details

Instructor: John Augustine (Email: augustine at iitm)

Co-Instructor (IIT-PKD): Deepak Rajendraprasad

Teaching Assistants:

IIT-M
- Vikram Bhat (cs16m057 at smail)
- ~~Mohit Daga~~ ~~(cs15s041 at smail)~~ Off to KTH!
- Ananya Sai (cs16m037 at smail)
IIT-Palakkad
- Archana (archana at iitpkd.ac.in)

Location: MSB 359 @ IITM

Slot: "F" (Tue 4.50-5.40 PM, Wed 11-11.50 AM, Thu 9 - 9.50 AM, Fri 8 - 8.50 AM)

Textbook: Probability and Computing: Randomized Algorithms and Probabilistic Analysis, by Mitzenmacher and Upfal.

References:

Randomized Algorithms, by Motwani and Raghavan.
Concentration of Measure for the Analysis of Randomized Algorithms, by Dubhashi and Panconesi.

Class Forum: https://groups.google.com/d/forum/17-pac

Video Recording: This course is going to be live telecast to IIT Palakkad and also recorded by NPTEL. However, I do not foresee any restrictions on classroom interaction.

Lectures

Module 01: S01, S02, S03, S04, S05, S06

Module 02: S01, S02, S03, S04, S05, S06

Module 03: S01, S02, S03, S04, S05

Module 04: S01, S02, S03, S04, S05

Module 05: S01, S02, S03

Module 06: S01, S02, S03, S04

Module 07: S01, S02, S03, S04, S05

Module 08: S01, S02, S03

Module 09: S01, S02, S03

Tutorials

In-class handout
In-class handout
Problems 3.9, 3.20, 3.14, 3.15, 3.22, 4.1, 4.2, 4.7, 4.11, 4.12
Problems: 4.17, 4.20, 4.21, 4.25
Problems: 5.3, 5.11, 5.21, 5.22, 5.24, 13.11

Assignments

Done.
Due: Sunday Sept 24, 6PM. Problems: 4.25 and 5.21 (2 marks each. Must be written on your own as usual. The writing should be formal and complete. A template will be posted shortly)
Problems 7.4, 7.10, 7.22, and 7.26 from the textbook. Due Wednesday Oct 11, 6 PM.
Problems 10.5 and 10.6 due Friday Oct 20, 6 PM.
Problems 11.7 and 11.16 due Friday Nov 10, 6PM.

Grading Scheme

Five (Latexed) Assignments: 5*4=20 (Questions will be discussed during tutorial sessions. Submissions will be checked for plagiarism.)

Three Programming Assignments: 3*5=15 (Submission will be through an online tool that will check for plagiarism.)

Two Quizzes: 2*15=30 (No cheatsheets allowed.)

Final Exam: 1*35=35 (Policy on cheatsheets will be informed later. Update: No Cheatsheets!)

Update: Since we had fewer programming assignments than planned, the final marks distribution will be slightly updated.

Please read my academic honesty policy. Institute's 85% attendance policy will be strictly followed.

Google Sites

Report abuse