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 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 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 1-1 | 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 tutorial-sheets 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 tutorial-sheet. The questions in the tutorial-sheet 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 tutorial-sheets.
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 pre-announced 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 IQ-ed” and “intelligent” students will not have an undue advantage over a “hardworking” and “sincere” student.
CLASS COVERAGE
| S. No. | Date-Time | Summary of Topics Covered | Lecture notes/References | Comments |
|---|---|---|---|---|
| 1 | 4 Jan (16:15-17: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:30-14: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 Erdos-Szekeres 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:15-17:05) |
In this lecture, we revisited the Erdos-Szekeres 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:30-14:20) |
We looked at the different instances where we would come across nC2 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 ice-cream 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+r-1Cr-1. 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:25-15:15) |
The main focus of this lecture was to understand mathematical induction. We solved a few example problems such as Euler's formula (v-e+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:15-17: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 non-trivial 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, one-one function, and onto functions. | Chapter 4 Grimaldi |
|
| 9 | 19 Jan (13:30-14:20) |
We had a few warm up exercises of different functions that qualify as either one-one or onto, or both or neither. We saw how establishing one-one 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:00-08:50) |
We solved a few problems that involved counting the different kind of functions given a finite domain and co-domain. | Chapter 5 Grimaldi |
|
| 11 | 20 Jan (14:25-15: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:30-14: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:15-17: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:00-08:50) |
We discussed the solutions to the second half of the problems given in the assignment 1. | Assignment 1 |
|
| 15 | 27 Jan (14:25-15:15) |
We discussed the solutions to the remaining questions given in the assignment 1. | Assignment 1 |
|
| 16 | 1 Feb (16:15-17: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 one-one, is their composition also one-one? Similarly, if two functions are known to be onto, what can we say about their composition? | Chapter 5 Grimaldi |
|
| 17 | 2 Feb (13:30-14: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:00-8:55) |
Test 1 | - |
|
| 19 | 3 Feb (14:25-15: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:15-17: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:30-14: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:00-8: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:25-15: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:15-17: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:30-14: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:00-08: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:25-15: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:30-17: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:30-14: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:00-08:50) |
It was majorly a tutorial/assignment solving session. | Assignment 2,3 |
|
| 31 | 24 Feb (14:25-15: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:30-14: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 non-planarity 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 n-1 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 n-1. | 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 one-to-one 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 co-efficients 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 1-12 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