# Amitabha Bagchi

### Timings and Venues

#### Lecture

Mon Thu 9:30AM to 10:50AM, on Microsoft Teams.

A weekly help session will be conducted from 3PM-4PM on Wednesdays on Teams.

#### Tutorial

• Group 1. Thu 2-3PM.
• Group 2. Fri 2-3PM.
• Group 3. Mon 2-3PM.
• Group 4. Tue 2-3PM.
All tutorials will be conducted on Microsoft Teams. Here are the instructions:
• Check your allotted TA from the link above. Note: Some groups have multiple TAs. Make sure to check the TA allotted to you and not your group.
• At the time allotted to your Group, go to the team 2001-COL202 DISCRETE MATHEMATICAL STRUCTUR on Teams.
• In the list of channels look for the channel with your TA's name, e.g., if your TA's name is Arindam then there will be a channel "TA-Arindam." Note: You will be asked to leave if you join the wrong TA's meeting without prior permission. We have made the channels public for your convenience so the occasional rescheduling is easy. Do not abuse the convenience.
• Your TA will set up a meeting within the channel for the scheduled time. Join this meeting at the given time.
• After the tutorial, you are expected to submit the solution on the same day on Gradescope. Even if Gradescope accepts solution after the deadline, no late submissions will be evaluated.
Note: In case you have issues with Teams or Gradescope please message Head TA Arindam Bhattacharya (csz168114) on Teams.

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

• Each lecture has text sections mentioned in parantheses after the topics. These sections may not have been covered in their entirety in the lecture. Nevertheless each section is in the syllabus in its entirety.
• Tutorial sheets will generally be based on the material covered in the previous week.

### Tutorials

#### Tutorial sheets

• Tut 10. Posted 24 December 2020.
• Tut 9. Posted 17 December 2020.
• Tut 8. Posted 28` November 2020.
• Tut 7. Posted 20 November 2020.
• Tut 6. Posted 12 November 2020.
• Tut 5. Posted 1 November 2020.
• Tut 4. Posted 23 October 2020.
• Tut 3. Posted 16 October 2020.
• Tut 2. Posted 8 October 2020.
• Tut 1. Posted 2 October 2020.

#### Tutorial guidelines

• There will be 10 tutorial sessions. Each tutorial session has a number from T1 to T10. Please check the calendar to see which day which tutorial number is scheduled for your group.
• There will be 10 tutorial sheets, one for each session. You are expected to work on sheet number i in tutorial number i, i.e., in T1 you will work on Tut1, T2 on Tut2 etc. The sheets will be posted at least one day before the scheduled session.
• One or two problems in each tutorial sheet will be marked as for submission. You have to solve this problem and submit it via Gradescope by 11:59PM on the day of your 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. Then upload it to Gradescope.
• Your tutorial submission will be graded for effort and clarity (not necessarily correctness). You will get marked out of 4 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 late under any circumstances.

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

• Lecture delivery. There will be 24 live 80 min lectures delivered via MS Teams at the scheduled times per the time table. These lectures will be archived on Impartus within a day or two of being delivered. There will be 4 pre-recorded 80 min lectures posted on Impartus. The dates for posting these will be announced.
• Tutorial sessions. Tutorials will be conducted on MS Teams at the scheduled times. You are expected to read the tutorial sheet beforehand and be available on Teams with pen and paper handy.
• Quizzes. Five scheduled quizzes will be held during class timings in the first 15 minutes of class. The quiz will be emailed to you and you will have to upload your work to Gradescope. Please see the calendar for the schedule of quizzes. You will be given some extra time to upload the quiz.
• Plagiarism. Since this is an online semester with a lot of scope for cheating, we will have a very strict plagiarism policy. If you copy or allow anyone to copy in any tutorial submission, quiz or exam then you will get -25% for the entire course. Both the person who has copied and the person whose work has been copied will get the same penalty. The penalty will be same for weekly tutorial submissions and for the quizzes and exams. Copying includes: copying from each other, copying from a textbook or any internet source. For tutorial submissions you are allowed to discuss but you have to write in your own words.
• Attendance. Since this is an online semester, as per the decision of the Senate there will be no attendance requirement. However, for this class attending lectures is highly recommended and attending tutorials should be considered mandatory. If you miss a tutorial due to internet issues you can take my permission and join the same tutorial with another group.
• Missed minor. If you miss a minor there will be a 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.