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.
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.