Discrete Structures


Lecture hours: Mon 10:30am -- 11:25am,
Tue 11:30am -- 12:25pm,
Thu 08:30am -- 09:25am
Office hours: Wed 11:00am -- 12:30pm
Location: KReSIT SIC 301
Instructor: Nutan Limaye (firstname[AT]cse[DOT]iitb[DOT]ac[DOT]in)
Teaching Assistants:       Hemant Kumar Adil (hemant[DOT]adil[AT]gmail)
Khushraj Madnani (khush250[AT]gmail)
Naman Mishra (firsnamelastname[AT]gmail)
Pratik Patre (pblastname[AT]gmail)

Assignments

Assignment 1 [pdf] [Due: Fri, Aug 17]

Assignment 2 [pdf] [Due: Fri, Aug 24]


Lectures and tutorials

Week 1

Lecture 1 (Mon, Jul 30): [slides]

What is a proof? What are propositions? Proof methods

Lecture 2 (Tue, Jul 31): [slides]

The principle of induction

Lecture 3 (Thu, Aug 01): [slides]

What are sets? Finites sets and infinite sets. What are functions?

Tutorial 1[pdf]

Week 2

Lecture 4 (Mon, Aug 06): [slides]

There is a bijection from N x N to N. There is no bijection between N and all subsets of N [Cantor, 1891].

Lecture 5 (Tue, Aug 07): [slides]

Let A, B be two sets. If there is an injective map from A to B and another injective map from B to A then there is a bijection from A to B. [Schröder-Bernstein]

Lecture 6 (Thu, Aug 09): [slides]

Relations and types of relations.

Tutorial 2[pdf]

Week 3

Lecture 7 (Mon, Aug 13): [slides]

Properties of equivalence classes and partial orders.

Lecture 8 (Tue, Aug 14): [slides]

Basics of counting: count one object in order to count the other, double counting.

Lecture 9 (Thu, Aug 16): [slides]

Approximating n! -- Striling's approximation, Counting the numner of labelled trees.

Tutorial 3[pdf]

Week 4

Lecture 10 (Mon, Aug 27): [slides]

Computing the n-th Fibonacci number using generating functions

Lecture 11 (Tue, Aug 28): [slides]

Computing the n-th catalan number using generating functions.

Lecture 12 (Thu, Aug 30): [slides]

Recurrence for triagulating a convex polygon, the number of derrangement.

Tutorial 4[pdf]