COURSE INTRODUCTION
This is a prerequisite course for almost all subjects/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 prerequisite 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 prerequisites 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 prerequisite 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.
Primary Textbook
The textbook for the course is Discrete and Combinatorial Mathematics, 5th Edition by Ralph P. Grimaldi. We will cover most of the chapters from this text book. This book is available on Flipkart and Amazon. I personally liked the eversion of the book which is available for a nominal price on Amazon (click here,). This eversion opens on your desktop/tablet. I strongly suggest that you buy an eversion instead of a hard copy as it helps you annotate the text and helps you 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 whether this is a legal or a pirated one.
A few topics will be covered from the following text books:
Introduction to algorithms by Cormen et al.
Discrete Mathematics and its applications by Kenneth Rosen
SYLLABUS
Items 1 to 24 will be covered before midterm exams.
Items 25 to 50 will be covered after midterm exams.
Please note: Each item presented below does not denote a class session of 50 minutes duration. They are just the list of topics that will be covered.
Sl. No.  Topic  Reference Material 

1  Introduction to Counting  Grimaldi 
2  Permutations  Grimaldi 
3  Combinations: The binomial theorem  Grimaldi 
4  Combinations with repetition  Grimaldi 
5  The Catalan numbers  Grimaldi 
6  The well ordering principle  Grimaldi 
7  Mathematical Induction  Grimaldi 
8  Introduction to Functions and Relations  Grimaldi 
9  Cartesian Products and Relations  Grimaldi 
10  Functions: Plain and 11  Grimaldi 
11  Onto Functions: Stirling Numbers of the second kind  Grimaldi 
12  The pigeonhole principle  Grimaldi 
13  Function composition and inverse functions  Grimaldi 
14  Properties of relations  Grimaldi 
15  Partial Orders: Hasse Diagrams  Grimaldi 
16  Equivalence Relations and Partitions  Grimaldi 
17  Introduction to Set theory(excluded)  Grimaldi 
18  Countable and Uncountable sets(excluded)  Grimaldi 
19  Introduction to Graph Theory  Grimaldi 
20  Euler Trails and Circuits  Grimaldi 
21  Planar Graphs  Grimaldi 
22  Hamilton Paths and Cycles  Grimaldi 
23  Graph coloring and chromatic polynomials  Grimaldi 
24  Trees  Grimaldi 
25  Introduction to Logic  Grimaldi 
26  Basic Connectives and Truth Tables  Grimaldi 
27  The laws of logic  Grimaldi 
28  Rules of inference  Grimaldi 
29  Quantifiers  Grimaldi 
30  Quantifiers, Definitions and Proofs  Grimaldi 
31  Introduction : principle of inclusion and exclusion  Grimaldi 
32  Generalizations of the principle  Grimaldi 
33  Derangements: Nothing is in the right place  Grimaldi 
34  Rook Polynomials  Grimaldi 
35  Arrangements with forbidden positions  Grimaldi 
36  Introduction to Generating Functions  Grimaldi 
37  Partitions of integers  Grimaldi 
38  The exponential generating functions  Grimaldi 
39  Introduction to Recurrences  Cormen 
40  Recurrence relations and Computing  Cormen 
41  Substitution method for solving recurrences (excluded)  Cormen 
42  Recursion tree method (excluded)  Cormen 
43  The master method (excluded)  Cormen 
44  Introduction to Number theory (excluded)  Rosen 
45  Congruences(excluded)  Rosen 
46  Basic results (excluded)  Rosen 
47  Public Key Cryptography (excluded)  Rosen 
48  Introduction to Algorithms (excluded)  Rosen 
49  The Growth of functions (excluded)  Rosen 
50  Complexity of Algorithms (excluded)  Rosen 
 
MARKS DISTRIBUTION
Test 1 will be conducted in the class on 3rd February 2017, 8 am to 8:50 am
Test 2 will be conducted in the class on 12th April 2017, 4:15 pm to 5:05 pm
Midterm will be for 2 hours as per the timetable
Finals will be for 3 hours as per the timetable
Minimum Passing Marks : 30 (Absolute)
The course will comprise of several quizzes, you can expect 1 to 2 short duration quizzes every week. Quizzes will be announced (at least 1 day in advance). It will mostly be on the day of tutorials.
Track 1  Track 2 

20% Quiz  20% Quiz 
10% Test 1  10% Test 1 
15% Midterm  30% Midterm 
10% Test 2  10% Test 2 
45% Final  30% Final 
Total marks = Maximum of marks secured in track 1 and track 2.
Let us illustrate this with an example:
Assume a student A secured the following marks
30 out of 100 in mid term
90 out of 100 in final
And student B secured:
90 out of 100 in mid term
30 out of 100 in final
Student A will secure:
0.15(30) + 0.45(90) = 45 in track 1
0.30(30) + 0.30(90) = 36 in track 2
Hence the final marks of Student A in midterm + final = max (45,36) = 45 marks
Student B will secure:
0.15(90) + 0.45(30) = 27 in track 1
0.30(90) + 0.30(30) = 36 in track 2
The final marks of Student B in midterm + final = max (27,36) =36 marks
LEARNERS ARMOUR
With the intention of protecting the interest of students and fostering a dynamic learning experience, the instructor plans to set up the following mechanisms/protocols to ensure that the students get the best from this course:
1. In case the student finds it difficult to understand any of the concepts covered in the class, s/he is requested to email the instructor asking for help within 5 working days from the day of the class. The instructor along with the TA will make sincere attempts to ensure that a time is scheduled within the next 1 week to clarify the doubt or redo that part of teaching, if required.
2. Irrespective of the official/personal commitments of the instructor, the instructor will stick to the scheduled date/time of the class and will never prepone or postpone the class’ date/time under any circumstance. The instructor will never schedule an extra class beyond the scheduled class hours. If there is a need for one, the instructor will record a few video lectures and pass it on to everyone well in advance, which will serve as a replacement for the extra classes.
3. Irrespective of any academic/official/personal engagements, the instructor will ensure that he is present in the class before the commencement time of the class. In no case will the instructor be late by even a minute. Also, under no circumstance will the instructor continue to engage the class a minute beyond the scheduled 50 minutes.
4. The instructor will strictly stick to the list of topics presented in the table in the same order to the best possible extent.
5. The instructor maintains an anonymous feedback form at the following link: http://goo.gl/n6P27i. You are requested to post your concerns/complaints/feedback here. Every feedback we receive will be discussed in the class and solved.
6.The instructor will, under no cost, change the marks distribution, syllabus or introduce any perk/point not listed in this document. after 10th of January 2017.
7. The instructor guarantees that the tutorial sheets will serve as a model for the kind of questions that will appear in the tests and exams. The student should never be in the state of not knowing how to prepare and what to prepare. You are guaranteed to do very well if you are attending the classes, reading all the topics from the references provided and solving all the tutorial problems.
8. The course assumes that the student is spending about 4 to 5 hours per week outside the class hours in understanding the subject material. In case the student is struggling beyond these many hours, it can be detrimental to his/her overall progress in the semester. In such a situation, you are requested to meet the instructor at the earliest possible time by fixing an appointment. The instructor will evaluate your preparedness for the topics covered in the course and will advise you on ways to improve your understanding of the course content.
FREQUENTLY ASKED QUESTIONS
Q1. The marks distribution looks strangely different. Why?
It is observed that there are two categories of students, ones who perform consistently well and the ones who are slow bloomers. Respecting this, the instructor has decided to evaluate a student in two different ways and take the maximum of the two distributions. For instance, if you end up securing less marks in the minor exam, you will still have hopes to perform well in the major exam and compensate for it because we will consider track 1 distribution. If you are a consistent student and have done well in the minor but not so well in the major, you are well protected by the track 2 distribution. Please note that the marks distribution is final and there will be no changes to it.
Q2. Why are there no assignments in this course?
While the instructor understands that the homework assignments give the students a different kind of learning advantage in comparison to the time bound tests/exams, it was noted in the past that the plagiarism/copying related strategies which a few students resort to, give them unwarranted edge over the faithful and sincere ones. To protect the interests of sincere students, the instructor has decided to not have a homework component in the course.
Q3. I learn the best when I am given homeworks/assignments. How else will a student get to achieve depth if one does not solve assignment or homework problems at one’s own pace?
The instructor completely understands this point and strongly believes that the students should spend quality time in solving problem sets with varying difficulty levels. In this connection, we will ensure that problem sets are given in the form of tutorialsheets well in advance to students so that they spend time solving them independently/collaboratively. After about a week, these questions will be discussed and solved in the Tutorial sessions by the TA/instructor. It is important for the student to be self motivated enough to attempt the questions provided in the tutorialsheet. The questions in the tutorialsheet are indicative of the difficulty level of the questions that will be asked in the tests and exams. In fact, a few questions in the minor/major will be directly picked from these tutorialsheets.
Q4. How do I ensure that I perform well in this course?
You are more likely to get a very good grade if you do the following:
Attend the lectures, follow up with the instructor and TA if you don’t understand a concept.
Solve the problem sets given in the form of tutorial sheets before coming to the tutorial classes.
Ensure that you understand the topics by reading the material from the references provided.
Take the quizzes seriously, which will help you stay with the pace of the classes.
Q5. I am not sure what is the actual course load. What if it gets heavy and affects my overall semester’s progress.
This is very unlikely, given that the instructor has made every attempt to keep the course organized with deviations minimized. Beyond this, at any point of time, if you think you are struggling with the course, you should talk to the instructor/TA immediately, we can take a closer look at your problem and with a “high probability” solve it for you. The course is all about probabilistic solutions to problems which the instructor and TA seem to be a little versed with :)
Q6. If I have a serious complaint with the way the course is conducted or if there is any other issue which I cannot directly convey, fearing that it can be mistaken for insubordination, how do I go about it?
Despite our best efforts, if there is something that you don’t like about the way the course is conducted (by the instructor or by the TA), be it teaching/evaluation/partiality, you may please use the anonymous link to post your grievance: http://goo.gl/forms/pPJKQvSLwJ9mFpNx2 . We will immediately act on it with the benefit of doubt, always given to the students.
Q7. I am into extra curricular activities and cannot give a whole lot of time for studies, do you think i will be risking it by taking up this elective?
Extra curricular activities are as important as academics. We encourage you to participate and suggest that you strike a good balance between the two. In order to encourage the students to spend good amount of time in their holistic development outside academics, the CSL105 course is structured in a way that we don’t expect beyond 4 to 5 hours of your study time per week, which amounts to 56 hrs to 70 hrs in the semester.
Q8. What will be asked in the quizzes? Will it be surprise or announced?
Quizzes will test your understanding of the concepts, it will be of short duration and straightforward questions. Anyone who has sat through the lectures can easily answer them. Every quiz will be preannounced by at least a day’s time in advance (over email). There will be 1 to 2 quizzes every week each of 5 to 10 mins duration. More details about the quiz will be shared on the first day of the class.
Q9. Is the grading in the tests/exams boolean or do we get marks for partial attempts?
The valuation (/marking) scheme and solution to the test/exam questions will be shared with everyone. The marking will not be boolean, you will get marks for partial attempts as described in the scheme of valuation.
Q10. I love programming! I don’t see any programming component in this elective. Why?
We feel the course is already heavy for 4 credits, including a programming component will tax the student a bit too much. We will be giving you interesting programming questions and exploratory assignments to try by yourself, these will not be graded.
Q11. How are the grade letters assigned in this course?
It has been our sincere observation from our experience so far that it is tough to decide the grading mechanism a priori and do justice to students. The instructor will decide on the grade letter breakups after observing the final performance of the students. The grading will be fair, in the sense that, it will distinguish students on the basis of their understanding and efforts. Every attempt will be made in ensuring that the evaluation is such that the “naturally talented”, “high IQed” and “intelligent” students will not have an undue advantage over a “hardworking” and “sincere” student.
CLASS COVERAGE
S. No.  DateTime  Summary of Topics Covered  Lecture notes/References  Comments 

1  4 Jan (16:1517:05) 
This lecture introduced the structure and a brief introduction of the course along with an intersting puzzle on combinatorics.  Chapter 1 Grimaldi 

2  5 Jan (13:3014:20) 
This lecture covered two problems: finding the number of binary search trees and the number of valid parentheses. Catalan numbers were used to solve them.  Chapter 1 Grimaldi 

3  6 Jan (08:00 08:50) 
The concept of Catalan numbers was discussed in detail. Additionally, the concept of Pigeonhole principle was discussed and used in understanding ErdosSzekeres sequence.  Chapter 1 Grimaldi and class notes 

4  6 Jan (14:25 15:15) 
This lecture covered some problems covering basic topics like sum rule, product rule, permutations, combinations and binomial theorem along with combinations with repetitions.  Chapter 1 Grimaldi 

5  11 Jan (16:1517:05) 
In this lecture, we revisited the ErdosSzekeres sequence and saw the complete proof. We also saw how the claim does not hold for a smaller length integer sequence. We also took a look at Binomial theorem and supplied a combinatorial proof for the expansion. We saw that the proof can be easily extended to a multinomial expansion.  Chapter 1 Grimaldi and class notes 

6  12 Jan (13:3014:20) 
We looked at the different instances where we would come across ^{n}C_{2} and saw quite a few seemingly unrelated instances. We also observed how the same question when viewed from two differnt perspectives can have different answers and still have both the answers correct. This was the case with the icecream parlour problem. We supplied the proof of correctness for both the answers. We took a look at combinations with repetitions and proved why it would be ^{n+r1}C_{r1}. We proved this by establishing a bijection to a seemingly easier set of objects and gave a count of the number of objects in this new set.  Chapter 1 Grimaldi 

7  13 Jan (14:2515:15) 
The main focus of this lecture was to understand mathematical induction. We solved a few example problems such as Euler's formula (ve+r=2), edge node relationship in a tree (acyclic connected graph), the sum of the first n natural numbers, etc. It was left as an exercise to think about the induction that goes in the proof of the maximum contigious subarray problem.  Chapter 4 Grimaldi 

8  18 Jan (16:1517:10) 
We formalized the notion of mathematical induction, defined the statement and took a look at its proof. In its proof we defined and saw the use of the principle of well ordering. We discussed on the nontrivial examples where we encounter mathenatical induction: the monks; Konigsberg bridge; maximum contigious subarray; etc. We briefly discussed another problem of showing that every integer greater than equal to 14 can be written as the sum of 8s and 3s. We then began with the chapter on functions and relations. We defined a function, oneone function, and onto functions.  Chapter 4 Grimaldi 

9  19 Jan (13:3014:20) 
We had a few warm up exercises of different functions that qualify as either oneone or onto, or both or neither. We saw how establishing oneone and onto nature of functions help in making counting arguments. In this regard, we saw the example of Catalan numbers.  Chapter 5 Grimaldi 

10  20 Jan (08:0008:50) 
We solved a few problems that involved counting the different kind of functions given a finite domain and codomain.  Chapter 5 Grimaldi 

11  20 Jan (14:2515:15) 
We continued with the questions asked in the previous class. We saw a general form to count the number of onto functions. We proved a recurrence to find out the stirling's number and ended answering the question of finding the total number of ways one can factor the number 30030 into its factors.  Chapter 5 Grimaldi 

12  24 Jan (13:3014:20) 
Is it indeed possible to compress data and be able to retrieve the data? That is, is compression even possible, in the literal sense? This is the question we began with and saw how one can use Pigeonhole principle to state the answer. We saw a variety of problems whose proof involves the pigeonhole principle.  Chapter 5 Grimaldi 

13  25 Jan (16:1517:05) 
We were introduced to the concept of extended Pigeonhole principle and we looked at few interesting problems that used this concept. The list of problems that were discussed in the class is included in the tutorial section.  Chapter 5 Grimaldi 

14  27 Jan (08:0008:50) 
We discussed the solutions to the second half of the problems given in the assignment 1.  Assignment 1 

15  27 Jan (14:2515:15) 
We discussed the solutions to the remaining questions given in the assignment 1.  Assignment 1 

16  1 Feb (16:1517:05) 
In today's class we observed the need for having composition of functions. As an example, we took a look at Collatz conjecture and posed a couple of problems on the same. We also stated that the abstraction is important, although it may not have any direct impact, functions are an important concept used in computer science. With this, we began questioning the nature of functions and asked if two functions are oneone, is their composition also oneone? Similarly, if two functions are known to be onto, what can we say about their composition?  Chapter 5 Grimaldi 

17  2 Feb (13:3014:20) 
We revisited the Catalan numbers and saw that along with a closed form, the nth Catalan number can also be given in the form of a recurrence relation. We established the recurrence relation through the example of the balanced paranthesis problem. We also solved the polygon triangulation problem using this recurrence.  Chapter 1 Class notes 

18  3 Feb (8:008:55) 
Test 1   

19  3 Feb (14:2515:15) 
We took a look at function compositions in detail and showed how inverse of a function, if it exists, is always unique. We also took a look at the similarities in the behaviour of set of all bijective functions and integers. We showed that properties such as associativity, identity, inverses holds in both spaces.  Chapter 5 Grimaldi 

20  8 Feb (16:1517:05) 
We began by defining the notion of a relation. We saw that we can classify the differnt types of relations conditioned on whether the defined relation respects some properties. In this regard, we saw when we define a relation to be reflexive, symmetric and transitive. Through various examples, we saw how a given relation can exhibit all possible combinations of thes properties. We ended the class making the observation that when a relation is reflexive, symmetric and transitive at the same time, the set on which the relation is defined can be partitioned into equivalence classes.  Chapter 7 Grimaldi 

21  9 Feb (13:3014:20) 
We revised the concept of reflexive, transitive and symmetric relations through examples. We also counted the number of relexive relations, symmetric relations on a given set. As per the request of students, we took a look at a special kind of relation  one that is not reflexive but is symmetric and transitive. Despite the fact that, at first it seems impossible to construct such a relation, we showed the existence of many such relations. Through these examples, we were better able to appreciate the definition of symmetric and transitive relations.  Chapter 7 Grimaldi 

22  10 Feb (8:008:50) 
Revisiting the notion of function composition, we questioned the composition of relations. Noting that a relation is nothing but a subset of the cross products of sets, we saw that composition of relations also defines another relation. We saw how we can capture a relation in a matrix and saw how matrix multiplication translates to composition of relations.  Chapter 7 Grimaldi 

23  10 Feb (14:2515:15) 
We observed the operation of matrices in order to capture composition of relations. We also saw why this operation is true. We also questioned about the properties of a matrix that represents a reflexive relation, transitive relation. We also defined what an antisymmetric relation is and how the matrix of such a relation would look like.  Chapter 7 Grimaldi 

24  15 Feb (16:1517:05) 
We watched a video that discussed the notion of a Hasse diagram. We discussed the concept of a sink and a source and observed that a Poset always has a sink and a source. We learnt how to represent a poset using a Hasse diagram. We saw the importance to have different ways to represent a poset. We briefly saw the need for a technique like that of Topological sorting.  Chapter 7 Grimaldi 

25  16 Feb (13:3014:20) 
We had previously encountered Equivalence relations. Today we took a look at the detailed proof that shows that every equivalence relation partitions the set into disjoint equivalence classes and vice versa as well.  Chapter 7 Grimaldi 

26  17 Feb (08:0008:50) 
We began learning the concepts of a new chapter  Graph Theory. We undersood what a graph is and its constituents of vertces and edges. We also took a look at what one means by the compliment of a graph. We saw the notion of connected versus disconnected graphs. We asked whether the complement of a disconnected graph is always disconnected and vice versa.  Chapter 11 Grimaldi 

27  17 Feb (14:2515:15) 
We briefly discuused the different notions of a graph such as a walk, cycle, trail, path, circuit, etc. Then we were introduced to the notion of an Eulerian circuit and we took a look at the proof for the presence of an Eulerian circuit in a graph.  Chapter 11 Grimaldi 

28  22 Feb (16:3017:20) 
In today's class we saw the concept of Bell numbers and the notion of graph isomorphism. We also completed the proof for the condition for the relation matrix M(R) to hold in order for the relation R to be transitive.  Chapter 7,10,11 Grimaldi 

29  23 Feb (13:3014:20) 
We formally defined the notion of graph isomorphism and solved the puzzle of determining if two graphs are isomorphic or not, which was given in the previous class. We majorly solve the first 14 questions of Assignment 2.  Assignment 2 

30  24 Feb (08:0008:50) 
It was majorly a tutorial/assignment solving session.  Assignment 2,3 

31  24 Feb (14:2515:15) 
We solved more exercise problems and quickly took a recap of all the topics that have been covered so far and the portions for minor exams.  Assignment 3 

32  9 Mar (13:3014:20) 
We formally took a look at the Konigsberg problem and showed that there cannot be an eulerian circuit on it. We saw this with the example of a zoo problem and proved it using induction.  
33  10 Mar (8:00  8:50) 
We had a tutorial session where the main focus was on solving problems on graphs. The new concepts learnt was that of wheel graphs, subgraphs, induced subgraphs, spanning subgraphs.  Tutorial 5 

34  10 Mar (14:25  15:15) 
Today we discussed planarity of graphs and the condition required for a graph to be planar. We discussed the nonplanarity of K5, K(3,3) and the Peterson's graph.  Chapter 11 Grimaldi 

35  15 Mar (16:15  17:05) 
We studied a special kind of graph known as a tournament grpahs and we saw that proof for the fact that there is always a Hamilton path on such a graph. Additionally, we saw that any graph on n vertices that satisfies the property that sum of the degree of any two vertices is greater than n1 is alwaus connected.  Chapter 11 Grimaldi 

36  16 Mar (13:30  14:20) 
Borrowing ideas from the previous class, we completed the proof for the existence of a Hamiltonian path on any graph on n vertices that satisfies the property that sum of the degree of any two vertices is greater than n1.  Chapter 11 Grimaldi 

37  17 Mar (08:00  08:50) 
This class focused on introducing the concept of graph colouring (chromatic number of a graph). We took a look at the chromatic number of a complete graph and that of a cycle. We also took a look at the derivation of the chromatic polynomial.  Chapter 11 Grimaldi 

38  17 Mar (14:25  15:15) 
This was a tutorial session where we took a look at some more problems on hamiltonian paths, minimum cut of a graph, etc.  Tutorial 6 

39  29 Mar (16:15  17:05) 
We discussed the first three units from the text. We discussed the idea of truth tables, tautology, contradiction and satisfiability. We discussed the meanig of p>q in detail with its truth table. We also saw the proofs for well known statements such as "primes are infinite" and "square root of 2 is irrational". We observed the application of the laws of inference in the proofs. We ended the class by solving a few problems on inference rules.  Chapter 2 

40  30 Mar (13:30  14:20) 
Today we discussed dual of Boolean expression, absorption law, De Morgan's law, proof by contradiction, proof by contraposition and practised some examples.  Chapter 2 

41  31 Mar (08:00  08:50) 
We discussed qunatifiers, namely 'forall' and 'there exists'. We observed the way to create negation of a given expression. We noted that the definition of convergence of a sequence can be captured using quantifiers and thus one can obtain the negation of the statement.  Chapter 2 

42  31 Mar (02:25  03:15) 
Class Committee Meeting   

43  5 April (16:15  17:05) 
We began with a motivating example of counting the number of ways in which every letter is put inside a wrong envelope. With this in mind we took a look at the Principle of Inclusion and Exclusion. We also saw the proof of the same. As another application of the principle of inclusion and exclusion, we counted the number of possible graphs with no isolated vertex.  Chapter 8 

44  6 April (13:30  14:20) 
The main focus of today's class was to count the number of ways in which we can place rooks on a chess board so that none of them take each other. In this context, we studies the rook polynomial that captures the possible ways of achieving this. We further saw the benefit of representing it as a polynomial, when we can break the given chess board configuration into smaller independent subproblems. We ended the class by observing how one can recursively construct the rook polynomial of any chess board configuration.  Chapter 8 

45  7 April (08:00  08:50) 
In this class, we discussed an interesting problem of finding the number of onetoone functions from a set A to set B, given certain constraints such as some of the elements of the set A can not be associated with some of the elements of the set B. We saw how this problem can be converted into a problem that can be solved using the concept of Rook's Polynomial.  Chapter 8 

46  7 April (14:25  15:15) 
We solved the first 11 questoins from assignment 4 on graphs.  Assignment 4 

47  8 April (08:00  08:50) 
We solved the remaining questoins from assignment 4 on graphs.  Assignment 4 

48  8 April (14:25  15:15) 
We solved the questoins from assignment 5 on logic.  Assignment 5 

49  11 April (13:30  14:20) 
We solved the questoins from assignment 6 on principle of inclusion and exclusion.  Assignment 6 

50  12 April (16:15  17:05) 
Test 2  

51  19 April (16:15  17:05) 
In this class we began by revisiting the concept of counting with repetitions. Then we saw how one can construct polynomials such that the coefficients of the terms are answers to counting problems. With this we introduced the idea of generating functions. We also looked at the Maclaurin series expansion for few functions. We then saw how the infinite series representation of these functions help us in easily computing the the values of the coefficients. We solved the example of counting how many subsets of size 4 can be picked from the set S={1,2,3, ... 15} such that the subset does not have any consecutive integers.  Chapter 9 

52  20 April (13:30  14:20) 
We continued with the concept of generating functions and saw how they are useful in determining the number of partitions of a given integer. We also observed that the number of partitions of an integer with distinct summands is equal to the number of partitions with odd summands.  Chapter 9 

53  21 April (08:00  08:50) 
We had the compensatory Test/Quiz qustions given in class. We then discussed the notion of exponential generating functions and solved an example problem on the same.  Chapter 9 
TUTORIALS
Tutorials will be conducted regularly, you will be provided with tutorial sheets to practice. The difficulty level in the examination will be equivalent to the difficulty level of the tutorial questions. You are advised to solve the questions without referring to any material online/offline, except for the textbook.
Counting  Solved Exercises in the Class on 7th January 2017
Mathematical Induction  Solved Exercises in the Class on 14th and 19th January 2017
Relations and functions  Solved Exercises in the Class on 20th January 2017
Pigeonhole Principle  Solved Exercises in the Class on 24th and 25th January 2017
Graphs  Solved Exercises in the Class on 10th March 2017
Graphs  Problems solved on 17th March 2017
ASSIGNMENTS
Assignment 1  Questions from topics 112 in the syllabus
Assignment 2  Questions on Relations
Assignment 3  Questions on Graphs
Assignment 4  Questions on Graphs [Solution]
Assignment 5  Questions on Logic [Solution]
Assignment 6  Questions on Principle of Inclusion and Exclusion [Solution]
Assignment 7  Questions on Generating Functions [Solution]
Videos
2 Relations: More examples and Posets
Graph representation and POSETS