COURSE INTRODUCTION
The course is lined towards understanding probability ideas in computer science. Apart from developing the subject the theoretical way, we address some of the most interesting real life questions and provide solutions to it. Following are some of the most interesting questions we address in the course:
- What is the ideal and optimal “dating” strategy? Of what interest is this to computer scientists?
- Can you convince a person that you know a secret without telling him/her the secret? This is doable and is one of the path breaking ideas in computer security!
- Is it practical and advisable to claim “you’re feeling lucky” and gamble? Why should one never visit Las Vegas? What has this to do with the mechanism with which internet search engines work?
- Can ideas from probability theory help one design algorithms that can make your android phone beat the world’s fastest supercomputer?
- Do we all have a common biological “ancestral mother” from whom everyone descended? Answer: YES and we need both - ideas from probability theory and computer science to answer this!
The course is mainly geared towards making students understand and appreciate the idea of probability and randomization in the field of computing. At the end of the course, the student will be:
- confident of reading and understanding any probability related idea in computer science.
- able to think on the lines of solving a problem with randomization techniques, which are otherwise hard to solve the deterministic way.
- able to appreciate the basic ideas in probability such as distributions, bounds, inequalities and their applications.
- to a good extent able to independently read and understand the technical details in a research paper that uses probability ideas to solve questions related to computer science.
SYLLABUS
In this course we will cover the following topics:
Puzzles and Activities, More Puzzles and Activities (Gich Game, Online Hiring, German Tank Problem, Cryptology: Vigenere Cipher, One time pad, Random Number Generation), Application: Polynomial Identities, Application: Matrix Multiplication Verification, Application: Zero knowledge proofs, Gambler’s Ruin, Introduction to Random Variables and Distributions, Contention Resolution, Finding the Global min cut, Randomized Approximation Algorithm for Max 3-sat, Median Finding and Quick Sort, Randomized Closest Pair Solution, Randomized Caching, Introduction to Chernoff Bounds, Load Balancing, Packet Routing, Balls, Bins and Random Graphs : Poisson Distributions and other topics, Balls, Bins and Random Graphs : Other topics, Balls, Bins and Random Graphs : Birthday Paradox, Balls, Bins and Random Graphs: Hashing bit strings, Balls, Bins and Random Graphs: Bloom filters, Balls, Bins and Random Graphs: Finding Hamilton Cycles in a Graph, Markov Chains : Introduction with applications, Markov Chains : More applications, Markov Chains and Random Walks : 2-SAT randomized solution., Markov Chains and Random Walks : 3-SAT randomized solution, Markov Chains and Random Walks : Random Walks on undirected Graphs, Markov Chains and Random Walks : An s-t connectivity algorithm, Spectral Analysis, Random Walks and Web Search, Random Number Generation, Probabilistic Primes: The Miller Rabin Test, Branching and Coalescent process, Species accumulation problem (Enumeration Queries)
The course will also contain some invited lectures.
MARKS DISTRIBUTION
Midterm will be for 2 hours as per the timetable
Finals will be for 3 hours as per the timetable
Minimum Passing Marks : 30 (Absolute)
The course will comprise of several quizzes, you can expect 1 to 2 short duration quizzes every week. Quizzes will be announced (at least 1 day in advance).
| Track 1 | Track 2 |
|---|---|
| 20% Quiz | 20% Quiz |
| 10% Oral | 10% Oral |
| 20% Midterm | 35% Midterm |
| 50% Final | 35% Final |
Total marks = Maximum of marks secured in track 1 and track 2.
Let us illustrate this with an example:
Assume a student A secured the following marks
30 out of 100 in mid term
90 out of 100 in final
And student B secured:
90 out of 100 in mid term
30 out of 100 in final
Student A will secure:
0.20(30) + 0.50(90) = 51 in track 1
0.35(30) + 0.35(90) = 42 in track 2
Hence the final marks of Student A in midterm + final = max (51,42) = 51 marks
Student B will secure:
0.20(90) + 0.50(30) = 33 in track 1
0.35(90) + 0.35(30) = 42 in track 2
The final marks of Student B in midterm + final = max (33,42) =42 marks
LEARNERS ARMOUR
With the intention of protecting the interest of students and fostering a dynamic learning experience, the instructor plans to set up the following mechanisms/protocols to ensure that the students get the best from this course:
1. In case the student finds it difficult to understand any of the concepts covered in the class, s/he is requested to email the instructor asking for help within 5 working days from the day of the class. The instructor along with the TA will make sincere attempts to ensure that a time is scheduled within the next 1 week to clarify the doubt or redo that part of teaching, if required.
2. Irrespective of the official/personal commitments of the instructor, the instructor will stick to the scheduled date/time of the class and will never prepone or postpone the class’ date/time under any circumstance. The instructor will never schedule an extra class beyond the scheduled class hours. If there is a need for one, the instructor will record a few video lectures and pass it on to everyone well in advance, which will serve as a replacement for the extra classes.
3. Irrespective of any academic/official/personal engagements, the instructor will ensure that he is present in the class before the commencement time of the class. In no case will the instructor be late by even a minute. Also, under no circumstance will the instructor continue to engage the class a minute beyond the scheduled 50 minutes.
4. The instructor will strictly stick to the list of topics presented in the table in the same order to the best possible extent.
5. The instructor maintains an anonymous feedback form at the following link: Click Here. You are requested to post your concerns/complaints/feedback here. Every feedback we receive will be discussed in the class and solved.
6.The instructor will, under no cost, change the marks distribution, syllabus or introduce any perk/point not listed in this document.
7. The instructor guarantees that the tutorial sheets will serve as a model for the kind of questions that will appear in the tests and exams. The student should never be in the state of not knowing how to prepare and what to prepare. You are guaranteed to do very well if you are attending the classes, reading all the topics from the references provided and solving all the tutorial problems.
8. The course assumes that the student is spending about 4 to 5 hours per week outside the class hours in understanding the subject material. In case the student is struggling beyond these many hours, it can be detrimental to his/her overall progress in the semester. In such a situation, you are requested to meet the instructor at the earliest possible time by fixing an appointment. The instructor will evaluate your preparedness for the topics covered in the course and will advise you on ways to improve your understanding of the course content.
FREQUENTLY ASKED QUESTIONS
Q1. The marks distribution looks strangely different. Why?
It is observed that there are two categories of students, ones who perform consistently well and the ones who are slow bloomers. Respecting this, the instructor has decided to evaluate a student in two different ways and take the maximum of the two distributions. For instance, if you end up securing less marks in the minor exam, you will still have hopes to perform well in the major exam and compensate for it because we will consider track 1 distribution. If you are a consistent student and have done well in the minor but not so well in the major, you are well protected by the track 2 distribution. Please note that the marks distribution is final and there will be no changes to it.
Q2. Why are there no assignments in this course?
While the instructor understands that the homework assignments give the students a different kind of learning advantage in comparison to the time bound tests/exams, it was noted in the past that the plagiarism/copying related strategies which a few students resort to, give them unwarranted edge over the faithful and sincere ones. To protect the interests of sincere students, the instructor has decided to not have a homework component in the course.
Q3. I learn the best when I am given homeworks/assignments. How else will a student get to achieve depth if one does not solve assignment or homework problems at one’s own pace?
The instructor completely understands this point and strongly believes that the students should spend quality time in solving problem sets with varying difficulty levels. In this connection, we will ensure that problem sets are given in the form of tutorial-sheets well in advance to students so that they spend time solving them independently/collaboratively. After about a week, these questions will be discussed and solved in the Tutorial sessions by the TA/instructor. It is important for the student to be self motivated enough to attempt the questions provided in the tutorial-sheet. The questions in the tutorial-sheet are indicative of the difficulty level of the questions that will be asked in the tests and exams. In fact, a few questions in the minor/major will be directly picked from these tutorial-sheets.
Q4. How do I ensure that I perform well in this course?
You are more likely to get a very good grade if you do the following:
Attend the lectures, follow up with the instructor and TA if you don’t understand a concept.
Solve the problem sets given in the form of tutorial sheets before coming to the tutorial classes.
Ensure that you understand the topics by reading the material from the references provided.
Take the quizzes seriously, which will help you stay with the pace of the classes.
Q5. I am not sure what is the actual course load. What if it gets heavy and affects my overall semester’s progress.
This is very unlikely, given that the instructor has made every attempt to keep the course organized with deviations minimized. Beyond this, at any point of time, if you think you are struggling with the course, you should talk to the instructor/TA immediately, we can take a closer look at your problem and with a “high probability” solve it for you. The course is all about probabilistic solutions to problems which the instructor and TA seem to be a little versed with :-)
Q6. If I have a serious complaint with the way the course is conducted or if there is any other issue which I cannot directly convey, fearing that it can be mistaken for insubordination, how do I go about it?
Despite our best efforts, if there is something that you don’t like about the way the course is conducted (by the instructor or by the TA), be it teaching/evaluation/partiality, you may please use the anonymous link to post your grievance: Anonymous Feedback Form . We will immediately act on it with the benefit of doubt, always given to the students.
Q7. I am into extra curricular activities and cannot give a whole lot of time for studies, do you think i will be risking it by taking up this elective?
Extra curricular activities are as important as academics. We encourage you to participate and suggest that you strike a good balance between the two. In order to encourage the students to spend good amount of time in their holistic development outside academics, the CSL471 course is structured in a way that we don’t expect beyond 4 to 5 hours of your study time per week, which amounts to 56 hrs to 70 hrs in the semester.
Q8. What will be asked in the quizzes? Will it be surprise or announced?
Quizzes will test your understanding of the concepts, it will be of short duration and straightforward questions. Anyone who has sat through the lectures can easily answer them. Every quiz will be pre-announced by at least a day’s time in advance (over email). There will be 1 to 2 quizzes every week each of 5 to 10 mins duration. More details about the quiz will be shared on the first day of the class.
Q9. Is the grading in the exams boolean or do we get marks for partial attempts?
The valuation (/marking) scheme and solution to the exam questions will be shared with everyone. The marking will not be boolean, you will get marks for partial attempts as described in the scheme of valuation.
Q10. I love programming! I don’t see any programming component in this elective. Why?
We feel the course is already heavy for 4 credits, including a programming component will tax the student a bit too much. We will be giving you interesting programming questions and exploratory assignments to try by yourself, these will not be graded.
Q11. How are the grade letters assigned in this course?
It has been our sincere observation from our experience so far that it is tough to decide the grading mechanism a priori and do justice to students. The instructor will decide on the grade letter breakups after observing the final performance of the students. The grading will be fair, in the sense that, it will distinguish students on the basis of their understanding and efforts. Every attempt will be made in ensuring that the evaluation is such that the “naturally talented”, “high IQ-ed” and “intelligent” students will not have an undue advantage over a “hardworking” and “sincere” student.
CLASS COVERAGE
| S. No. | Date-Time | Summary of Topics Covered | Lecture notes/References | Comments |
|---|---|---|---|---|
| 1 | 9 Aug (16:45-17:35) | This lecture introduced the structure and a brief introduction of the course along with the introduction of the grading scheme. | ||
| 2 | 10 Aug (14:00-14:50) | This was an introductory lecture where the upcoming topics were discussed like The German Tank Problem, The Dating Problem, The Las Vegas Paradox, Zero knowledge proof, Mitochondrial Eve, Monty Hall problem. | ||
| 3 | 11 Aug (14:55-15:45) | In this lecture, the proof of monty hall problem was covered. It was followed by the basic probability questions to introduce sample space, event space, dependent and independent events. | Lecture 1 | |
| 4 | 16 Aug (16:45-17:35) | In this lecture, the simple gambling problem, some puzzles, and prerequisites for dating problem were covered. | Lecture 2 | |
| 5 | 17 Aug (14:00-14:50) | In this lecture, the detailed explanation of the dating problem was covered. | Lecture 3 | |
| 6 | 18 Aug (8:00-8:50) | In this lecture, first we had the quiz, after that the detailed proof of dating problem was covered. The session was concluded with the interesting questions on this problem. | ||
| 7 | 18 Aug (14:55-15:45) | In this lecture, the detailed explanation of the German Tank problem was covered. | Lecture 4 | |
| 8 | 30 Aug (16:45-17:35) | In this lecture, the cryptanalysis techniques were discussed. The main techniques covered in this lecture includes Ceaser, Substitution, Vigenere Cipher, and one time pad. | Lecture 5Lecture 5 A (One Time Pad) | |
| 9 | 31 Aug (14:00-14:50) | In this lecture, the detailed explanation of the Vigenere cipher was covered. | Lecture 6 | |
| 10 | 1 Sep (8:00-8:50) | In this lecture, the Zero Knowledge proof, and its analysis were discussed. | Lecture 7 | |
| 11 | 1 Sep (14:55-15:45) | In this lecture, the detailed explanation of zero knowledge proof using Graph Isomorphism was covered. | Lecture 8 | |
| 12 | 6 Sep (16:45-17:35) | In this lecture, we discussed Matrix Multiplication Verification problem using gamble and computing approach. | Lecture 9 | |
| 13 | 7 Sep (14:00-14:55) | In this lecture, we discussed the detailed proof of Matrix Multiplication Verification problem. | Lecture 10 | |
| 14 | 8 Sep (8:00-8:50) | In this lecture, first, we discussed some basics followed by the introduction of polynomial verification problem. | Lecture 11 | |
| 15 | 8 Sep (14:55-15:45) | In this lecture, we discussed the detail proof of polynomial verification problem, followed by the introduction of Min-cut algorithm. | Lecture 12 | |
| 16 | 13 Sep (16:45-17:35) | In this lecture, we discussed the observations based on Min-cut problem followed by the Karger's algorithm to get the min-cut in the given graph. | Refer Lecture Note 12 | |
| 17 | 14 Sep (14:00-14:55) | In this lecture, we discussed the detailed proof of Karger's Algorithm, analysis of Quick Sort, and the algorithm to find Kth Maximum element in the given array. | Lecture 13 (A) , Lecture 13 (B) | |
| 18 | 15 Sep (8:00-8:50) | In this lecture, the closest pair problem in 1-Dimension was covered. | Refer Lecture 14 | |
| 19 | 15 Sep (14:55-15:45) | In this lecture, the detailed explanation of the closest pair problem in 1-Dimension was covered that was followed by the introduction of the closest pair problem in 2-Dimension. | Lecture 14 | |
| 20 | 20 Sep (16:45-17:35) | In this lecture, we discussed the randomized algorithm to find the closest pair in 1-D and 2-D dimensions. | Refer Lecture Note 14 | |
| 21 | 21 Sep (14:00-14:55) | In this lecture, we discussed the detailed proof of randomized algorithm for 2 dimension, followed by the contention resolution problem and its analysis. | Lecture 15 | |
| 22 | 22 Sep (8:00-8:50) | In this lecture, First we had a quiz and then discussed Tutorial 1. | ||
| 23 | 22 Sep (14:55-15:45) | In this lecture, We finished the tutorial 1 and discussed some more questions based on the tutorial 1. | ||
| 24 | 27 Sep (16:45-17:35) | In this lecture, we discussed Tutorial 2 and 3. | ||
| 25 | 28 Sep (14:00-14:55) | In this lecture, we had a quiz and discussed Tutorial 3. | ||
| 26 | 29 Sep (8:00-8:50) | In this lecture, we covered tutorial 4,5, and 6. | ||
| 27 | 11 Oct (16:45-17:35) | In this lecture, we discussed Coupon Collector Problem. | Lecture 16 | |
| 28 | 12 Oct (14:00-14:50) | In this lecture, the linearity of the expectation and indroduction of 3 SAT problem was covered. | Refer notes of Lecture 29 | |
| 29 | 13 Oct (8:00-8:50) | In this lecture, we covered the detailed analysis of 3 SAT Problem. | Lecture 17 | |
| 30 | 13 Oct (14:55-15:45) | In this lecture, we discussed one probabilistic question based on 3 SAT problem. The question is, what is the probability that more than 7k/8 clauses are satisfied if the value is assigned randomly to the literals. | Refer Lecture note 17 | |
| 31 | 14 Oct (14:00-14:55) | In this lecture, Chernoff bounds were covered. | Lecture 18 | |
| 32 | 25 Oct (16:45-17:35) | In this lecture, we discussed PageRank and solved some questions based on that. | Refer shared videos | |
| 33 | 26 Oct (14:00-14:50) | In this lecture, We covered the convergence proof of PageRank. | Refer shared videos | |
| 34 | 27 Oct (8:00-8:50) | In this lecture, Pagerank computation using matrix multiplication was covered. | Refer shared videos | |
| 35 | 27 Oct (14:55-15:45) | In this lecture, Markov chains was covered. | Refer shared videos | |
| 36 | 28 Oct (14:55-15:45) | In this lecture, Primality test was covered. | Lecture 19 | |
| 37 | 28 Oct (14:55-15:45) | In this lecture, the detailed proof of Primality test was covered. | Refer Lecture Note 19 | |
| 38 | 1 Nov (16:45-17:35) | In this lecture, the extended analysis of Primality test was covered. | Refer Lecture Note 19 | |
| 39 | 2 Nov (14:00-14:50) | In this lecture, the final analysis of Primality test and the introduction of balls and bins was covered. | Refer Lecture Note 19 | |
| 40 | 3 Nov (8:00-8:50) | In this lecture, the probablity questions based on balls and bin were covered like what is the probability to fall k balls in a given bin, what is the probability to fall k balls in any bin, and so on. | ||
| 41 | 3 Nov (14:55-15:45) | In this lecture, the detailed analysis of balls and bins problems and chernoff bounds were covered. | Lecture Note 20 | |
| 42 | 8 Nov (16:45-17:35) | In this lecture, balls and bins questions and load balancing questions based on chernoff bound were covered. | Lecture Note 21 | |
| 43 | 9 Nov (14:00-14:50) | In this lecture, birthday paradox is covered. | Lecture Note 22 Refer these notes for birthday Paradox and Bucket Sort | |
| 44 | 10 Nov (8:00-8:50) | In this lecture, we discussed hashing and its analysis. | Lecture Note 23 | |
| 45 | 15 Nov (16:45-17:35) | In this lecture, we discussed bloom filetrs and its analysis. | Lecture Note 24 (Refer attached notes for bloom filters) | |
| 46 | 16 Nov (14:00-14:50) | In this lecture, the analysis of bloom filters was finished. | Refer Lecture Notes 24 | |
| 47 | 17 Nov (14:55-15:45) | In this lecture, some PNC problems were discussed. | ||
| 48 | 22 Nov (16:45-17:35) | In this lecture, we discussed Tutorial 7. | ||
| 49 | 23 Nov (14:00-14:50) | In this lecture, we discussed Tutorial 8. | ||
| 50 | 24 Nov (14:55-15:45) | Final Test Conducted. |
Balls and Bins additional notes are here
TUTORIALS
Tutorials will be conducted regularly, you will be provided with tutorial sheets to practice. The difficulty level in the examination will be equivalent to the difficulty level of the tutorial questions. You are advised to solve the questions without referring to any material online/offline, except for the textbook.
Tutorial 1 The solution is here
Tutorial 2 The solution is here
Tutorial 3 The solution is here
Tutorial 4 The solution is here
Tutorial 5 The solution is here
Tutorial 6 The solution is here
Quizzes
| Quizzes | Date-Time | Comments |
|---|---|---|
| Quiz 1 | 18 Aug (8:00-8:50) | Quiz was based on monty hall problem and dating problem. |
| Quiz 2 | 7 Sep (14:00-14:50) | Quiz is based on Tutorial 1. |
| Quiz 3 | 8 Sep (8:00-8:50) | Quiz is based on Matrix Multiplication Verification Problem. |
| Quiz 4 | 20 Sep (16:45-17:35) | Quiz is based on the topics covered in the classes held on 13, 14, and 15 Sep 2017. |
| Quiz 5 | 22 Sep (8:00-8:50) | Quiz is based on Tutorial 2. |
| Quiz 6 | 28 Sep (14:00-14:50) | Quiz is based on Tutorial 3,4,5. |
| Quiz 7 | 13 Oct (8:00-8:50) | Quiz is based on the topics covered in this week. |
| Quiz 8 | 26 Oct (14:00-14:50) | Quiz is based on PageRank. |
| Quiz 9 | 27 Oct (8:00-8:50) | Quiz is based on PageRank convergence. |
| Quiz 10 | 27 Oct (14:55-15:45) | Quiz is based on PageRank computation using matrix multiplication. |
| Quiz 11 | 3 Nov (8:00-8:50) | Quiz is based on the syllabus covered in this week. |
| Quiz 12 | 10 Nov (8:00-8:50) | Quiz was based on chernoff bound. |
Videos
Videos related to the course will be posted here.
QUESTION PAPERS
Question papers and the solutions will be posted here.