# Amitabha Bagchi

Pre-Major Totals. Includes all evaluations apart from Major and Reminor. Posted 18 Nov 2019.

### Timings and Venues

#### Lecture

Mon Thu 9:30AM to 10:50AM, LH 310.

#### Tutorial

• Group 1. Thu 2-3PM. Supervised by: Sudeep Agarwal (cs5150295@iitd.ac.in)
• Group 2. Fri 2-3PM. Supervised by: Shubhani (anz168046@iitd.ac.in)
• Group 3. Mon 2-3PM. Supervised by: Raj Kamal (csz188013@iitd.ac.in)
• Group 4. Tue 2-3PM. Supervised by: Mehreen Jabbeen (csz187551@iitd.ac.in)
All tutorials will be conducted in Room LH 604.

### Topics

• Basic logic: Propositional logic: logical connectives; truth tables; normal forms (conjunctive and disjunctive); validity; predicate logic; limitations of predicate logic, universal and existential quantification; modus ponens and modus tollens. Proof techniques: Notions of implication, converse, inverse, contrapositive, negation, and contradiction; the structure of formal proofs; direct proofs; proof by counterexample; proof by contraposition; proof by contradiction; mathematical induction; strong induction; recursive mathematical definitions; well orderings.
• Basics of counting: Counting arguments; pigeonhole principle; permutations and combinations; inclusion-exclusion, recurrence relations, generating functions.
• Fundamental structures; Functions (surjections, injections, inverses, composition); relations (reflexivity, symmetry, transitivity, equivalence relations); sets (Venn diagrams, complements, Cartesian products, power sets); pigeonhole principle; cardinality and countability.
• Introduction to probability: Events, probability, probability of unions and intersections of events, independence and conditional probabilities, random variables, expectations, variances, basic tail inequalities.
• Intro to graph theory.

### Texts

The primary text book for this class will be:
[LLM10] E. Lehman, F. T. Leighton, and A. R. Meyer. Mathematics for Computer Science, Lecture notes from Fall 2010, MIT Open Courseware.

### Course calendar

• All the material given in the portions of the texts mentioned under "Source" may not have been covered in lecture. Nevertheless it is all in the syllabus.
• Tutorial sheets will generally be based on the material covered in the previous week.

### Tutorials

#### Tutorial sheets

• Tut 12. Posted 7 November 2019.
• Tut 11. Posted 31 October 2019.
• Tut 10. Posted 24 October 2019.
• Tut 9. Posted 17 October 2019.
• Tut 8. Posted 10 October 2019.
• Tut 7. Posted 18 September 2019.
• Tut 6. Posted 12 September 2019.
• Tut 5. Posted 4 September 2019.
• Tut 4. Posted 29 August 2019.
• Tut 3. Posted 8 August 2019.
• Tut 2. Posted 2 August 2019.
• Tut 1. Posted 25 July 2019.

#### Tutorial guidelines

• Tutorial sheets will be posted in the week before the tutorial is scheduled.
• One or two problems will be marked as for submission. You have to solve this problem and bring it to the tutorial. Write your solution on a plain piece of paper and put your name, entry number and the Tutorial number on top of the page.
• Your tutorial submission will be graded for effort and clarity (not necessarily correctness). You will get marked out of 3 based on the grader's subjective judgment on whether you have put in effort or not and on the level of clarity in what you have written.
• Your tutorial submission will not be accepted if you don't attend the tutorial, i.e. you cannot send your submission with a friend. Your tutorial submission will be graded only if you attend the relevant tutorial.
• The tutorial schedule and the sheets associated with each tutorial are given in the course calendar above.

### Evaluation

• 8%: Quizzes. 4% per quiz. Only the best two will be counted.
• 12%: Tutorial exercises. 1.5% per tutorial exercise. Only the best eight will be counted.
• 22%: I Minor Exam.
• 22%: II Minor Exam.
• 36%: Major Exam.

### Policies

• Attendance. 75% attendance is an institute requirement for getting an I grade or for being allowed to take a remajor in case of getting an E. There is no other attendance-based restriction in this course. Attendance will be through Timble and Timble issues will not be discussed (take them up with Timble admin).
• Missed minors. For missed minors there will be a single reminor held after the major at an announced time. The syllabus will be the entire course.
• Missing other evaluations. There will be no re-quizzes or make-up tutorials for any reason even illness. We will have enough of both to ensure that you will not suffer for missing up to 2 of each.
• Re-grading policy for quizzes and exams.