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:

1. What is the ideal and optimal “dating” strategy? Of what interest is this to computer scientists?
2. 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!
3. 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?
4. Can ideas from probability theory help one design algorithms that can make your android phone beat the world’s fastest supercomputer?
5. 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

Items 1 to 16 will be covered before midterm exams.

Items 17 to 31 will be covered after midterm exams.

Items 32, 33 and invited lectures are all independent sessions that will be covered if time permits. The instructor may cover these items any time during the semester.

Please note: Each item presented below doesn’t denote a 50 min class session. They are just the list of topics that we will be covering. While some items might take a meagre 20 mins (eg., item 3 takes less than 20 mins) some of them may take more than 2 to 3 classes (eg., item 31 takes 2 hours or more to cover).

MARKS DISTRIBUTION

Test 1 and Test 2 are of duration 1 hour.

Midterm is for 2 hours.

Final is for 3 hours.

Minimum Passing Marks : 30 (Absolute).

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.15(30) + 0.45(90) = 45 in track 1

0.30(30) + 0.30(90) = 36 in track 2

Hence the final marks of Student A in midterm + final = max (45,36) = 45 marks

Student B will secure:

0.15(90) + 0.45(30) = 27 in track 1

0.30(90) + 0.30(30) = 36 in track 2

The final marks of Student B in midterm + final = max (27,36) =36 marks

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 doesn’t 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 Tuit-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 tuit-sheet. The questions in the tuit-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 tuit-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 Tuit 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. What is the attendance policy?
For the sake of records, attendance will be taken, but is not compulsory.

Q6. 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 :-)

Q7. 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: http://goo.gl/forms/pPJKQvSLwJ9mFpNx2 . We will immediately act on it with the benefit of doubt, always given to the students.

Q8. 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 CSL 471 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.

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

Q10. Is the grading in the tests/exams boolean or do we get marks for partial attempts?
The valuation (/marking) scheme and solution to the test/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.

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

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

Tutorials

1. Tutorial 1 to be discussed on 11 August. Solutions
2. Tutorial 2 to be discussed on 1 September. Solutions
3. Tutorial 3
4. Tutorial 4
5. Tutorial 5
6. Tutorial 6

QUESTION PAPERS

1. Test1 organised on Sep 7.
2. Mid-semester exam organised on 24Sep.
3. Test2 organised on Nov 11.
4. Major exam organised on 26 Nov.