Dr. Ghys said Dr. Ratner replied: "Yes! Exactly! You understood why and how I write mathematics."

Excerpted from

K. Chang, Marina Ratner, Emigre Mathematician Who Found Midlife Acclaim, Dies at 78, New York Times, 25 July 2017.

End term instructions

Grading related:

• Regrade requests will be taken untill 5PM on 27 November 2017.
• The usual negative marking scheme will apply in case of thoughtless regrade requests.
• Negative marks will also be given to a question for which you have a 0 if it is felt that the regrade request is not valid.
• References for the exam solutions (not solutions, just references): Q1, for Q2 see Sec 7.9 of LLM10, Q3.

Grade related:

• Grading policy will be consistent with institute norms.
• Total scores will be made available once regrading is complete (probably by Tuesday afternoon).
• Do not email me or try to meet re your grade unless you are in danger of failing the class. There is always a person at every grade who misses the next higher grade by a small margin. While I wish that were not so (having been in that position myself more than once), it is a mathematical fact that such a person will exist (because every subset of the natural numbers is totally ordered) and there's not much I can do about it.

• Why should a CS student study this course? What should your learning goals be? Some rules for this class.
• How to write an email to your professor or TA

Timings and Venues

Lecture

Tutorial

• Group 1. Thu 1-2PM. Supervised by: Dishant Goyal (csz178060).
• Group 2. Fri 1-2PM. Supervised by: Anagh Prasad (cs5130277).
• Group 3. Mon 1-2PM. Supervised by: Gagan Madan (me1130015).
• Group 4. Tue 1-2PM. Supervised by: Shubhankar Suman Singh (csz168113).

Topics

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

Additional Material

• [Diestel16] Reinhard Diestel. Graph Theory, 5e, 2016. Posted 8 October 2017.
• [GKP94] R. L. Graham, D. E. Knuth, O. Patashnik. Concrete Mathematics: A foundation for computer science, 2nd ed. Pearson, 1994. (Available in the Central Library and in affordable Indian edition). Posted 23 September 2017.
• [Gallier08] Jean Gallier. Discrete Mathematics for Computer Science: Some Notes. arXiv:0805.0585, 2008. Posted 20 August 2017.
• [Arun-Kumar02] S. Arun-Kumar. Introduction to Logic for Computer Science (WWW draft), IIT Delhi, September 2002, retrieved 12 August 2017. Posted 14 August 2017.
• [Charikar02] Moses Charikar. Lecture slides for 7 Oct 2002, Handouts for Computer Science 341 (Discrete Mathematics) Fall 2002, Princeton University, 2002, retrieved 12 August 2017. Posted 14 August 2017.
• [Wilf94] Herbert S. Wilf. generatingfunctionology, Academic Press, 1994. Posted 7 August 2017.
• [LLM10] E. Lehman, F. T. Leighton, and A. R. Meyer. Mathematics for Computer Science, Lecture notes from Fall 2010, MIT Open Courseware. Posted 27 July 2017.
• [Bogart05] K. Bogart. Enumerative Combinatorics through Guided Discovery, 2005. Posted 23 July 2017.

Miscellaneous

• H. A. Priestley. Ordered Sets and Complete Lattices. In: Backhouse R., Crole R., Gibbons J. (eds) Algebraic and Coalgebraic Methods in the Mathematics of Program Construction. Lecture Notes in Computer Science, vol 2297, 2002. Springer, Berlin, Heidelberg. Posted 22 October 2017.
• A. Bagchi. Quiz 9 solution with grading notes (local access only). Posted 21 October 2017.
• A. Bagchi. Mutual independence, pairwise independence and $k$-wise independence: Events versus random variables. Posted 30 September 2017.
• A. Bagchi. Quiz 1 solution (local access only). Posted 28 July 2017.
• A. Bagchi. Why should a CS student study this course? What should your learning goals be? Some rules for this class. Posted 24 July 2017.

Course calendar

Update: All quizzes are now publicly available from outside IITD as well.
Click here to download as a single zip. Posted 26 February 2018.

Regarding this calendar please note

• The source material for topics covered in lecture in a given week are mentioned under the column titled "Source".
• 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 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 in a pass/fail mode, i.e. you will get either 1 or 0 marks based on the grader's subjective judgment on whether you have put in effort or not.
• 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

• 32%: Quizzes. 4% per quiz. Only the best eight will be counted.
• 8%: Tutorial exercises. 1% per tutorial exercise. Only the best eight will be counted.
• 15%: I Minor Exam.
• 15%: II Minor Exam.
• 30%: 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. This will be enforced at the institute level. There is no other attendance-based restriction in this course.
• 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 upto 4 of each.
• Quiz re-grading policy.
  • No regrading requests by email, only through gradescope.
  • Ask for regrading only if you think your solution is right but has been marked as wrong.
  • No regrading for partial marks, i.e., if you have been given marks for attempting, that is a subjective decision and will not be reviewed.
  • Frivolous regrading requests will get -0.5.
  • You need to describe in detail why you think your marks should be increased. Saying "Recheck Q2" will be considered a frivolous request and treated accordingly.