# Amitabha Bagchi

Registration note: COL202 in this semester is only open for CS1 and CS5 students. All others please register in the 2nd semester 2022-23 when it will be offered again. No exceptions will be made under any circumstances so please do not request it. Even if the ERP system allows you to add the course and you are not from CS1 or CS5 you will eventually be deregistered.

### Timings and Venues

#### Lecture

Mon Thu 9:30AM to 10:50AM. Venue: LH 111.

#### Tutorial

• Group 1. Thu 1-2PM. Venue: LH 611.
• Group 2. Fri 1-2PM. Venue: LH 611.
• Group 3. Mon 1-2PM. Venue: LH 611.
• Group 4. Tue 1-2PM. Venue: LH 611.

### 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.
• Intro to graph theory.

### Texts

The primary textbooks 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.
[LLM18] E. Lehman, F. T. Leighton, and A. R. Meyer. Mathematics for Computer Science, June 2018, MIT Open Courseware.

### Tutorials

#### Tutorial sheets

• Tut 1. Posted 18 August 2022.
• Tut 2. Posted 25 August 2022.
• Tut 3. Posted 1 September 2022.
• Tut 4. Posted 8 September 2022.
• Tut 5. Posted 15 September 2022.
• Tut 6. Posted 6 October 2022. Updated 10 October 2022.
• Tut 7. Posted 13 October 2022.
• Tut 8. Posted 20 October 2022.
• Tut 9. Posted 27 October 2022.
• Tut 10. Posted 3 November 2022.

#### Tutorial guidelines

• Each tutorial is numbered. The numbers run from 1 to 10. In the course calendar above the date for each tutorial for each group is clearly marked. For example, T2 for G4 is on 30 August 2022.
• Each tutorial sheet corresponds to a tutorial session, i.e., the tutorial sheets will be numbered from 1 to 10.
• In each tutorial sheet one question will be marked for submission. You must solve this problem at home on a sheet of paper with your name and entry number on it and bring it to the scheduled tutorial session and submit it at the beginning of the class, no later than 1:10PM. For example, students of grooup 4 will solve the submission question of tutorial sheet T2 and bring it to class on 30.08.2022.
• You can only submit the tutorial submission if you come to class. You cannot send it with someone else. You cannot submit it late. No exceptions.
• Plagiarism penalties for the tutorial submission will be extremely harsh. Please see the section on plagiarism below.
• Tutorial solutions will be graded for clarity and completeness along with correctness. The 4 points in bold in "Guidelines for writing a good proof" will be considered mandatory and marks will be deducted if any of them are missing.

### Evaluation

• 15%: Quizzes. 5% per quiz. Only the best three out of five will be counted.
• 16%: Tutorial exercises. 2% per tutorial exercise. Only the best eight will be counted.
• 29%: Minor Exam.
• 40%: 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).
• Tutorial submissions. Tutorial submissions will only be accepted during the tutorial session. If you miss the session you are not allowed to submit later or even send it along with a friend. This is a way of enforcing attendance in the tutorial sessions.
• 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.