CSL 105 - Discrete Mathematical Structures (Spring 2015)

CSL 105 - Discrete Mathematical Structures

(Spring 2015)

IIT Ropar

Prof. S. R. S. Iyengar

Mon 0955-1045, Tue 1050-1140, Wed 0800-0850 and 1145-1235

(Optional Extra Class: Sat 0900 hrs to 1230 hrs)

Venue: Main Building, L4

Course Overview

Description

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.

Textbook

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.

Syllabus

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.

Course Details

Teaching Assistant

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.

Office Hours of the instructor

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

E-mail Policy

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.

Grading

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%).

Grading Criteria

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

Distribution of Marks

Problem Sets15%
Surprise Quizzes20%
Activity10%
Attendance05%
Minor20%
Major30%

Problem Sets

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.

Surprise Quiz

We will have a few surprise quiz sessions to test your understanding of the concepts taught in the previous classes. If you are attentive in the class, make notes and read them once before the class, you will do very well and will most certainly secure full marks. The number of quizzes isn't pre-decided, your marks will be normalized and will comprise of 20% of the course weightage.

Activity

Activity will comprise of two parts:
  • 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.

Attendance

Attendance for the course is compulsory. If you secure less than 75% attendance, you will be given an F grade, which is as per the institute rule. Attendance carries 0-5 marks, details of which is given in the table below:
[95,100]5
[90,95)4
[85,90)3
[80,85)2
[75,80)1
[0,75)F
I assume you all have undergone a course in real analysis and know what one means by a closed[] and open interval() :-)

Minor and Major

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.

Academic Integrity

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

Schedule

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:

Anonymous Feedback/Sugestion

Click here to submit an anonymous feedback/suggestion to the instructor/TA. Please be constructive in your crticism. Do it with the objective of helping us give our best to you. If you are highlighting on any course related problem/issue, be it teaching, evaluation, grading, etc., try proposing how would you want us to handle it otherwise.