This is a pre-requisite course for almost all topics of computer science that you will study in the forthcoming semester. The word discrete in discrete mathematics has dual meaning: one being an antonym of the word continuous, which signifies, we are going to deal with the number line comprising of integers. The second being a discrete bunch of pre-requisite topics for computer science, stitched together and offered as a subject. Most of the topics that will be covered in the course do not assume any pre-requisites and our discussions will resemble puzzle solving sessions. The subject is very fascinating and it has been my observation that many graduating students regard this as one of their favourite subjects. Apart from aiding as a pre-requisite to other courses, discrete mathematics helps in heightening the mathematical aptitude of a student. If you ever enjoyed puzzle solving, you will like the ride through this subject. The treatment of the subject is excellent in the prescribed text book (mentioned below). The text book gets to the level of a college fresher without assuming any preliminary knowledge. The motivation of concepts is through several worked examples which makes learning easy and fun. The textbook has a historical account that appears at the end of every chapter, which I recommend you all to read without fail. There are several nice books and popular science articles on this subject which I can pass on to you people if you are interested. You are encouraged to read up extra material and discuss the same with the course instructor and TA beyond the class and office hours. We sincerely hope that you enjoy this course at its fullest.

The textbook for the course is * Discrete and Combinatorial Mathematics, 5th Ediction *
by Ralph P. Grimaldi. We will cover the first 13 chapters from this
text book. This book is available on flipkart and amazon. I personally
liked the e-version of the book which is available for a nominal price
on amazon (click here).
This e-version opens on your desktop/tablet. I strongly suggest that
you buy an e-version instead of a hardcopy as it helps you annotate the
text and search through the text easily. There is a third version of
this book available as a pdf document online (if you google), although I
am not sure if this is legal or pirated version.

The syllabus for the course will be the first 13 chapters from the above book which will make 90% of the syllabus. The rest 10% will be a bunch of miscellaneous topics, covered at the end of the course. We will provide you with references for these topics, as and when they are covered.

This course has one formal and an informal (volunteered) teaching assistant :

- Varsha Bhat (varsha.bhat@iitrpr.ac.in)
*Office hours:*0800 to 0900 hrs, Research Scholar's lab, Room #120- Jaspal Singh (jaspal.singh@iitrpr.ac.in)
*Office hours:*He is forever energetic, knowledgeable, ready to help you all out - anytime (that's what he claims :-) ). Although, I suggest you Write to him, fix an appointment and meet him.

The instructor and the TA will be available from 0800 to 0900 hrs on every Monday at the same place (Research Scholar's lab #120).

I request that you talk to me and the instructor during the above
mentioned office hours or immediately before/after the class. The
mailing list for the course is csl105@iitrpr.ac.in, you must ensure that
you are subscribed to this mailing list. In case of any questions, you
are requested to post them on the group and not email us personally,
(unless there is something personal for you to discuss). __Under no circumstances should you call/message the TA/instructor over phone __.
Contacting us over phone/email, requesting for the post poning of the
class or extension of deadline or any similar requests will lead to a
penalty of -5 marks (we are strict about this). In case there is any
request, you may please post it on the mailing list :
csl105@iitrpr.ac.in.

The course comprises of 3 lecture hours and 1 tutorial hour. Grading will be based on : weekly problem sets (15%), surprise quiz (20%), Activity (10%), minor(20%), major(30%),attendance (5%).

The grading will be absolute, based on the following criteria

[85,100] | A |

[80,85) | A- |

[75,80) | B |

[70-75) | B- |

[65-70) | C |

[60-65) | C- |

[50-60) | D |

[0-50) | F |

Problem Sets | 15% |

Surprise Quizzes | 20% |

Activity | 10% |

Attendance | 05% |

Minor | 20% |

Major | 30% |

You are requested to note the following:

- You must work
**alone**on problem sets. You are**not allowed**to collaborate or discuss with anyone (including the course instructor and TA). The questions that will be posed to you will be self contained or will be a direct exercise problem from the text book. - You should
**not google**for a solution. The only companion to you during your solving of the given assignment will be the course text book, we suggest that you don't stay online when you are solving the exercise problems. - Just in case we observe that you are copying from the internet (even partially) or collaborating with someone, you will get a
**straight F grade**. - You are not allowed to show your assignments to anyone,
even if your friend sees your written script or discusses and borrows
ideas from you and tries using the same method, we will regard that as
**plagiarism**(straight F grade to both of you!). Even soliciting help for assignments is against the honor code, in case someone requests you, please report the name of that student to us and we will keep your identity anonymous and initiate action against him/her. - Problem sets will be posted every week and you will be given sufficient time to solve it. Submissions are accepted in
**written format**only, on an A4 sized sheet which should be__punched and tagged and not pinned__. - You must submit your assignment in the class sharpt at 0955 hrs every Monday. Late submissions of assignment will
**fetch a 0**. In case you are unable to attempt a question, you should describe in detail your partial analysis /understanding/approach which, if observed to be good, can at times fetch you full marks. Take note that you are not allowed to submit your assignment before or after the above specified time, you may however submit it through a friend, just in case you are absent. - The total number of problem sets isn't preset. We will normalize your marks and this will carry 15% of the overall course weightage.
- Minor and Major question paper should be considered as two additional problem sets and must be submitted before the deadline, which will be announced immediately after your exams.

- Written assignment that is due by the first week of March.
- Two Collaborating Learning Activities, one in the last week of January and the other one in the first week of March.

[95,100] | 5 |

[90,95) | 4 |

[85,90) | 3 |

[80,85) | 2 |

[75,80) | 1 |

[0,75) | F |

There will be two exams in the course, minor and major. The portions for major exam will be the entire syllabus.

Minor will be of 2 hours duration and will comprise of 5 questions with three degrees of difficulty: easy (1 quesiton), medium (2 questions) and hard (2 questions). Major will be of 3 hours duration and will comprise of 6 questions with three degrees of difficulty: easy (2 quesitons), medium (2 questions) and hard (2 questions). Degree of difficulty is a very subjective term which is left to the instructor to decide. A student who has consistently practiced solving exercise problems from the text book and has solved all problem sets should be able to solve all the quesitons easily. We are overly and overtly serious when it comes to academic
integrity. We have 0 tolerance towards students who cheat. Action
against those who cheat will involve not less than assigning them an F
grade followed by immediate expulsion from the course. Over and above
this, the case will be reported to the disciplinary committee which may
decide to suspend the student for a semester or two. To repeat, __you
must work alone on homework problems and not discuss them with anyone.
The only materials you can refer when working on your problem sets are
your course notes and the assigned text book. You may not refer to
online sources or talk to others. When you are in doubt, ask the
instructor or TA what is allowed and what isn't. Just in case you have
overseen/suspect someone copying in the quiz/exam/problemsets, dutifully
report it to us, we will scrutinize their scripts and will initiate
action against them if they are found guilty. We assure that your
identity wll be kept anonymous. We request that you report immediately
(even if you are partially suspicious of any such malpractice amongst
your classmates.)__

I will update below the course coverage and the text book units that you all should read after the class.

**Class 1** (Wednesday, 7th Jan 2015, 0800-0850)

Introduction to the course and briefing on the grading scheme.

__Textbook Chapter:__ None

**Class 2** (Wednesday, 7th Jan 2015, 1145-1235)

Induction and the Cursed Monks problem

__Textbook chapters:__ None

**Class 3** (Saturday, 10th Jan 2015, 0900-0950)

We starte with the question of finding the cardinality of the power set of a set with n elements. We came out with many ways of showing that the answer is 2^n. We then saw different interpretations of nC2, many of you came out with nearly 10 different questions for which nC2 is the answer :-)

__Textbook chapters:__ None

**Class 4** (Saturday, 10th Jan 2015, 1000-1050)

We solved a graph degree problem using pigeon hole principle. We observed that a sequence of length 10 has a monotone subsequence of length 4. We constructed a table and saw that the proof follows from Pigeon Hole Principle. We then stated the general result "Given any sequence of length (n^2)+1 there is always a monotone subsequence of length n+1"

__Textbook chapters:__ None

**Class 5** (Saturday, 10th Jan 2015, 1100-1150)

We stated and tried solving the Catalan Number sequence. We noted that the number of ways to reach (5,5) from (0,0) without tresspassing the diagonal is a non-trivial question. We solved this using a simple bijection trick

__Textbook chapters:__ 1.6

**Class 6** (Saturday, 10th Jan 2015, 1200-1250)

We continued our discusison on Catalan numbers and discussed several other questions that lead to catalan sequence. I ended the class discussing the Towers of Hanoi problem.

__Textbook chapters:__ 1.6

**Class 7** (Monday, 12th Jan 2015, 0955-1045)

We discussed a recurrence relation for Catalan numbers. Note that this isn't part of the text book, but is an interesting concept that you all should know. We discussed the binomial theorem and spoke a bit about pascal's triangle, followed by a combinatorial problem based on the pascal's triangle. We briefly discussed the rule of sums and the rule of products. We ended our class by posing the question: "In how many ways can the entire class have 5 different flavours of ice-cream."

__Textbook chapters:__ 1.1,1.2,1.3,1.6

**Class 8** (Tuesday, 13th Jan 2015, 1050-1150)

Introduction to Logic: We took a quick conceptual tour on p-->q and constructed the truth table. We saw several important graph theory problems and ended our class with a problem on graph isomorphism

__Textbook chapters:__ 2.1, 11.1

**Class 9** (Wednesday, 14th Jan 2015, 0800-0850)

We started with the topic "Combinations with repetitions" and showed how the formula works. We defined a few standard terminologies in Graphs and discussed the Konigsberg bridge problem and stated the theorem "A connected graph has an Eularian Circuit iff all the vertices are of even degree"."

__Textbook chapters:__ 1.4, 11.1, 11.2

**Class 10** (Wednesday 14th Jan 2015, 1145-1235)

We defined what is a circuit, trail, path, walk, Eulerian Circuit and then proved the theorem that we stated in our previous class. We did a recapitulation of the concept of induction and saw a stronger version of it. We then applied induction to solve the theorem. We ended our class by posing a question on graph isomorphism.

__Textbook chapters:__ 11.3

**Class 11** (Saturday 17th Jan 2015, 0900-1000)

Annotation Assignment, Lab Activity

__Textbook chapters:__N/A

**Class 12** (Saturday 17th Jan 2015, 1000-1100)

Annotation Assignment, Lab Activity

__Textbook chapters:__N/A

**Class 13** (Saturday 17th Jan 2015, 1100-1200)

Annotation Assignment, Lab Activity

__Textbook chapters:__N/A

**Class 14** (Monday 19th Jan 2015, 0955-1045)

Problem solving session in graph theory (13th Chapter) and Counting (1st Chapter)

__Textbook chapters:__ Chapter 1 and 13

**Class 15** (Tuesday 20th Jan 2015, 1050-1140)

Random Assignment Check (Oral Test)

__Textbook chapters:__ N/A

**Class 16** (Wednesday 21st Jan 2015 0800-0850)

Surprise Quiz

**Class 17** (Wednesday 21st Jan 2015 1145-1235)

Recitation Class by Apoorva on Mathematical Logic

__Textbook chapters:__ Whole of 2nd Chapter

**Class 18** (Saturday 24th Jan 2015)

Graph Isomorphism, Exercise problems on graph theory

__Textbook chapters:__11

**Class 19** (Saturday 24th Jan 2015 09:15-10:15)

Planar Graphs (Proof of v-e+r=2)

__Textbook chapters:__11

**Class 20** (Saturday 24th Jan 2015 10:35-12:35)

Introduction to Hamilton Paths and Cycles

__Textbook chapters:__11

**Class 21** (Saturday 24th Jan 2015 12:35-1300)

Hamilton Paths (contd), Applications of Graph theory

__Textbook chapters:__11

**Class 22** (Tuesday 27th Jan 2015 1050-1140)

Chromatic Polynomials, Proper Coloring

__Textbook chapters:__11

**Class 23** (Wednesday 28th Jan 2015 0800-0850)

Hamilton Cycles (2 theorems), Introduction to Set theory

__Textbook chapters:__11 and 3

**Class 24** (Wednesday 28th Jan 2015 1145-1235)

Countable and Uncountable sets, Power set is uncountable

__Textbook chapters:__ Appendix (this is a standard topic and one may refer to any of the online resources).

**Class 25** (Saturday 31st Jan 2015 0900-1000)

Countable and Uncountable sets,

__Textbook chapters:__ Appendix (this is a standard topic and one may refer to any of the online resources).

**Class 26** (Saturday 31st Jan 2015 1005-1100)

Decidability (not all problems are solvable). Introduction to Probability.

__Textbook chapters:__ 3 (for probability), for Decidability you may just want to revise whatever was taught in class.

**Class 27** (Saturday 31st Jan 2015 1130-1230)

Birthday Paradox, Balls and Bins. We ended our class with the 'empty containers' question.

__Textbook chapters:__ Revise whatever was taught in class, (this topic is not present in the textbook).

**Class 28** (Monday 2nd Feb 2015 0955-1045)

Introduction to Number theory, divisibility

__Textbook chapters:__ 4

**Class 29** (Monday 2nd Feb 2015 1845-1940)

Divisibility (contd), GCD(a,b) can be expressed as a lineary combination of a and b.

__Textbook chapters:__ 4

**Class 30** (Monday 2nd Feb 2015 1945-2050)

Problems in Number Theory, Euclid's Algorithm, Introduction to Modulo n Arithmetic (we did not talk about congruences)

__Textbook chapters:__4.3,4.4,4.5

**Class 31** (Tuesday 3rd Feb 2015 1050-1140)

Recapitulation of Induction, The proof for Konigsberg Problem, Eulerian Circuits, Quiz

__Textbook chapters:__ N/A

**Class 32** (Wednesday 4th Feb 2015 0800-0850)

Recap of Logic, Rules of Inference and Quantifiers

__Textbook chapters:__2.3, 2.4

**Class 33** (Wednesday 11th Feb 2015 0800-0850)

Quiz 3

__Textbook chapters:__2.4 and 2.5

**Class 34** (Wednesday 18th Feb 2015 0800-0850)

Quiz 4

__Textbook chapters:__2.4 and 2.5

**Class 35** (Tuesday 3rd March 2015 0955-1045)

3/march/2015 We discussed functions and relations and introduced how one can count the total number of onto functions and introduced stirlings number.

__Textbook chapters:__

**Class 36** (Wednesday 4th March 2015 0800-0850)
We solved a few exercise problems on stirling numbers and bell numbers.

__Textbook chapters:__

**Class 37** (Wednesday 4th March 2015 1145-1235)
We discussed bell numbers and stirling number of the second kind. We discussed equivalence relations and saw how composition of relations can be computed using matrix multiplication.

__Textbook chapters:__

**Class 38** (Monday 9th March 2015 0955-1045)
Quiz paper discussion.
We stated and proved the recurrence relation for S(m)

__Textbook chapters:__

**Class 39** (Tuesday 10 March 2015 1050-1140)
We counted the total number of reflexive, symmetric and antisymmetric relations. We introduced what is a poset and a toast and discussed a few examples. We discussed Hasse Diagrams and Topological Sorting with examples.

__Textbook chapters:__

**Class 39** (Wednesday 11th March 2015 0800-0850)
We continued our discussion on relations and solved a few problems.

__Textbook chapters:__

**Class 40** (Wednesday 11th March 2015 1145-1235)
We started off with the principle of inclusion and exclusion. We showed how counting can be made easy by the formula. We discussed how to compute a closed form for Euler’s totient function and discussed a few of it’s properties.

__Textbook chapters:__

**Class 41** (Saturday 14th March 2015 0930-1030)
We continued our discussion with the principle of inclusion and exclusion. We discussed how to count the derrangements of n items and derived a formula for the same. We discussed a few problems.

__Textbook chapters:__

**Class 42** (Saturday 14th March 2015 1040-1140)

We introduced Rook polynomials and discussed a few problems.

__Textbook chapters:__

**Class 43** (Saturday 14th March 2015 1140-1235)

We discussed a recursive method to compute the Rook polynomial and solved a problem.

__Textbook chapters:__

**Class 44** (Monday 16th March 2015 0955-1045)

We introduced generating functions and discussed a few example applications.

__Textbook chapters:__

**Class 45** (Tuesday 17th March 2015 1050-1140)

We discussed the maclaurin's series and its application in counting. We discussed an important problem of finding the total possible 4 element subsets of {1,2,...,15} without consecutive elements in it.

__Textbook chapters:__

**Class 46** (Wednesday 18th March 2015 1145-1235)

We defined partition of a number and discussed the generating function method to enumerate them. We also discussed the proof of p_o(n)=p_d(n)

__Textbook chapters:__