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

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

Assignments

    1. Done.
    2. 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)
    3. Problems 7.4, 7.10, 7.22, and 7.26 from the textbook. Due Wednesday Oct 11, 6 PM.
    4. Problems 10.5 and 10.6 due Friday Oct 20, 6 PM.
    5. 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.