Toggle navigation
About us
Courses
FAQ
Contact us
×
Login
Existing User
New User
Forgot Password
Email:
Password:
Submit
Register
Email:
Password:
Confirm Password:
Name:
User Type:
Select
Student
Faculty
Others
Institute:
Branch:
Enter the Captcha
Register
Forgot Password
Email:
Submit
Home
Syllabus
Lectures
Downloads
FAQ
Course Co-ordinated by :
IIT Madras
Course Available from :
25-April-2018
NPTEL
Computer Science and Engineering
NOC:Discrete Mathematics (Video)
Motivation for Counting
Modules / Lectures
Week 1
Motivation for Counting
Paper Folding Example
Rubik's Cube Example
Factorial Example
Counting in Computer Science
Motivation for Catalan numbers
Rule of Sum and Rule of Product
Problems on Rule of Sum and Rule of Product
Factorial Explained
Proof of n! - Part 1
Proof of n! - Part 2
Astronomical Numbers
Permutations - Part 1
Permutations - Part 2
Permutations - Part 3
Permutations - Part 4
Problems on Permutations
Combinations - Part 1
Combinations - Part 2
Combinations - Part 3
Combinations - Part 4
Problems on Combinations
Difference between Permuations and Combinations
Combination with Repetition - Part 1
Combination with Repetition - Part 2
Combination with Repetition - Problems
Binomial theorem
Applications of Binomial theorem
Properties of Binomial theorem
Multinomial theorem
Problems on Binomial theorem
Pascal's Triangle
Fun facts on Pascal's Triangle
Catalan Numbers - Part 1
Catalan Numbers - Part 2
Catalan Numbers - Part 3
Catalan Numbers - Part 4
Examples of Catalan numbers
Chapter Summary
Week 2
Introduction to Set Theory
Example, definiton and notation
Sets - Problems Part 1
Subsets - Part 1
Subsets - Part 2
Subsets - Part 3
Union and intersections of sets
Union and intersections of sets - Part 1
Union and intersections of sets - Part 2
Union and intersections of sets - Part 3
Cardinality of Union of two sets - Part 1
Cardinality of Union of sets - Part 2
Cardinality of Union of three sets
Power Set - Part 1
Power set - Part 2
Power set - Part 3
Connection betwenn Binomial Theorem and Power Sets
Power set - Problems
Complement of a set
De Morgan's Laws - Part 1
De Morgan's Laws - Part 2
A proof technique
De Morgan's Laws - Part 3
De Morgan's Laws - Part 4
Set difference - Part 1
Set difference - Part 2
Symmetric difference
History
Summary
Week 3
Motivational example
Introduction to Statements
Examples and Non-examples of Statements
Introduction to Negation
Negation - Explanation
Negation - Truthtable
Examples for Negation
Motivation for OR operator
Introduction to OR operator
Truthtable for OR operator
OR operator for 3 Variables
Truthtable for AND operator
AND operator for 3 Variables
Primitive and Compound statements - Part 1
Primitive and Compound statements - Part 2
Problems involoving NOT, OR and AND operators
Introduction to implication
Examples and Non-examples of Implication - Part 1
Examples and Non-examples of Implication - Part 2
Explanation of Implication
Introduction to Double Implication
Explanation of Double Implication
Converse, Inverse and Contrapositive
XOR operator - Part 1
XOR operator - Part 2
XOR operator - Part 3
Problems
Tautology, Contradiction - Part 1
Tautology, Contradiction - Part 2
Tautology, Contradiction - Part 3
SAT Problem - Part 1
SAT Problem - Part 2
Logical Equivalence - Part 1
Logical Equivalence - Part 2
Logical Equivalence - Part 3
Logical Equivalence - Part 4
Motivation for laws of logic
Double negation - Part 1
Double negation - Part 2
Laws of Logic
De Morgan's Law - Part 1
De Morgan's Law - Part 2
Rules of Inferences - Part 1
Rules of Inferences - Part 2
Rules of Inferences - Part 3
Rules of Inferences - Part 4
Rules of Inferences - Part 5
Rules of Inferences - Part 6
Rules of Inferences - Part 7
Conclusion
Week 4
Introduction to Relation
Graphical Representation of a Relation
Various sets
Matrix Representation of a Relation
Relation - An Example
Cartesian Product
Set Representation of a Relation
Revisiting Representations of a Relation
Examples of Relations
Number of relations - Part 1
Number of relations - Part 2
Reflexive relation - Introduction
Example of a Reflexive relation
Reflexive relation - Matrix representation
Number of Reflexive relations
Symmetric Relation - Introduction
Symmetric Relation - Matrix representation
Symmetric Relation - Examples and non examples
Parallel lines revisited
Number of symmetric relations - Part 1
Number of symmetric relations - Part 2
Examples of Reflexive and Symmetric Relations
Pattern
Transitive relation - Examples and non examples
Antisymmetric relation
Examples of Transitive and Antisymmetric Relation
Antisymmetric - Graphical representation
Antisymmetric - Matrix representation
Number of Antisymmetric relations
Condition for relation to be reflexive
Few notations
Condition for relation to be reflexive.
Condition for relation to be reflexive..
Condition for relation to be symmetric
Condition for relation to be symmetric.
Condition for relation to be antisymmetric
Equivalence relation
Equivalence relation - Example 4
Partition - Part 1
Partition - Part 2
Partition - Part 3
Partition - Part 4
Partition - Part 5
Partition - Part 5.
Week 5
Motivational Example - 1
Motivational Example - 2
Commonality in examples
Motivational Example - 3
Example - 4 Explanation
Introduction to functions
Defintion of a function - Part 1
Defintion of a function - Part 2
Defintion of a function - Part 3
Relations vs Functions - Part 1
Relations vs Functions - Part 2
Introduction to One-One Function
One-One Function - Example 1
One-One Function - Example 2
One-One Function - Example 3
Proving a Function is One-One
Examples and Non- examples of One-One function
Cardinality condition in One-One function - Part 1
Cardinality condition in One-One function - Part 2
Introduction to Onto Function - Part 1
Introduction to Onto Function - Part 2
Definition of Onto Function
Examples of Onto Function
Cardinality condition in Onto function - Part 1
Cardinality condition in Onto function - Part 2
Introduction to Bijection
Examples of Bijection
Cardinality condition in Bijection - Part 1
Cardinality condition in Bijection - Part 2
Counting number of functions
Number of functions
Number of One-One functions - Part 1
Number of One-One functions - Part 2
Number of One-One functions - Part 3
Number of Onto functions
Number of Bijections
Counting number of functions.
Motivation for Composition of functions - Part 1
Motivation for Composition of functions - Part 2
Definition of Composition of functions
Why study Composition of functions
Example of Composition of functions - Part 1
Example of Composition of functions - Part 2
Motivation for Inverse functions
Inverse functions
Examples of Inverse functions
Application of inverse functions - Part 1
Week 6
Three stories
Three stories - Connecting the dots
Mathematical induction - An illustration
Mathematical Induction - Its essence
Mathematical Induction - The formal way
MI - Sum of odd numbers
MI - Sum of powers of 2
MI - Inequality 1
MI - Inequality 1 (solution)
MI - To prove divisibility
MI - To prove divisibility (solution)
MI - Problem on satisfying inequalities
MI - Problem on satisfying inequalities (solutions)
MI - Inequality 2
MI - Inequality 2 solution
Mathematical Induction - Example 9
Mathematical Induction - Example 10 solution
Binomial Coeffecients - Proof by induction
Checker board and Triomioes - A puzzle
Checker board and triominoes - Solution
Mathematical induction - An important note
Mathematical Induction - A false proof
A false proof - Solution
Motivation for Pegionhole Principle
Group of n people
Set of n integgers
10 points on an equilateral triangle
Pegionhole Principle - A result
Consecutive integers
Consecutive integers solution
Matching initials
Matching initials - Solution
Numbers adding to 9
Numbers adding to 9 - Solution
Deck of cards
Deck of cards - Solution
Number of errors
Number of errors - Solution
Puzzle - Challenge for you
Week 7
Friendship - an interesting property
Connectedness through Connecting people
Traversing the bridges
Three utilities problem
Coloring the India map
Defintion of a Graph
Degree and degree sequence
Relation between number of edges and degrees
Relation between number of edges and degrees - Proof
Hand shaking lemma - Corollary
Problems based on Hand shaking lemma
Havel Hakimi theorem - Part 1
Havel Hakimi theorem - Part 2
Havel Hakimi theorem - Part 3
Havel Hakimi theorem - Part 4
Havel Hakimi theorem - Part 5
Regular graph and irregular graph
Walk
Trail
Path and closed path
Definitions revisited
Examples of walk, trail and path
Cycle and circuit
Example of cycle and circuit
Relation between walk and path
Relation between walk and path - An induction proof
Subgraph
Spanning and induced subgraph
Spanning and induced subgraph - A result
Introduction to Tree
Connected and Disconnected graphs
Property of a cycle
Edge condition for connectivity
Connecting connectedness and path
Connecting connectedness and path - An illustration
Cut vertex
Cut edge
Illustration of cut vertices and cut edges
NetworkX - Need of the hour
Introduction to Python - Installation
Introduction to Python - Basics
Introduction to NetworkX
Story so far - Using NetworkX
Week 8
Bipartite graphs.
Directed, weighted and multi graphs
Illustration of Directed, weighted and multi graphs
Graph representations - Introduction
Adjacency matrix representation
Incidence matrix representation
Isomorphism - Introduction
Isomorphic graphs - An illustration
Isomorphic graphs - A challenge
Non - isomorphic graphs
Isomorphism - A question
Complement of a Graph - Introduction
Complement of a Graph - Illiustration
Self complement
Complement of a disconnected graph is connected
Complement of a disconnected graph is connected - Solution
Which is more? Connected graphs or disconnected graphs?
Bipartite graphs
Bipartite graphs - A puzzle
Bipartite graphs - Converse part of the puzzle
Definition of Eulerian Graph
Illustration of eulerian graph
Non- example of Eulerian graph
Litmus test for an Eulerian graph
Why even degree?
Proof for even degree implies graph is eulerian
A condition for Eulerian trail
Why the name Eulerian
Can you traverse all location?
Defintion of Hamiltonian graphs
Examples of Hamiltonian graphs
Hamiltonian graph - A result
A result on connectedness
A result on Path
Dirac's Theorem
Dirac's theorem - A note
Ore's Theorem
Dirac's Theorem v/s Ore's Theorem
Eulerian and Hamiltonian Are they related
Importance of Hamiltonian graphs in Computer science
Constructing non intersecting roads
Definition of a Planar graph
Examples of Planar graphs
V - E + R = 2
Illustration of V - E + R =2
V - E + R = 2; Use induction
Proof of V - E + R = 2
Famous non-planar graphs
Litmus test for planarity
Planar graphs - Inequality 1
3 Utilities problem - Revisited
Complete graph on 5 vertices is non-planar - Proof
Prisoners and cells
Prisoners example and Proper coloring
Chromatic number of a graph
Examples on Proper coloring
Recalling the India map problem
Recalling the India map problem - Solution
Week 9
NetworkX - Digraphs
NetworkX - Adjacency matrix
NetworkX- Random graphs
NetworkX - Subgarph
NetworkX - Isomorphic graphs Part 1
NetworkX - Isomorphic graphs Part 2
NetworkX - Isomorphic graphs: A game to play
NetworkX - Graph complement
NetworkX - Eulerian graphs
NetworkX - Bipaprtite graphs
NetworkX - Coloring
Counting in a creative way
Example 1 - Fun with words
Words and the polynomial
Words and the polynomial - Explained
Example 2 - Picking five balls
Picking five balls - Solution
Picking five balls - Another version
Defintion of Generating function
Generating function examples - Part 1
Generating function examples - Part 2
Generating function examples - Part 3
Binomial expansion - A generating function
Binomial expansion - Explained
Picking 7 balls - The naive way
Picking 7 balls - The creative way
Generating functions - Problem 1
Generating functions - Problem 2
Generating functions - Problem 3
Why Generating function?
Week 10
Introduction to Advanced Counting
Example 1 : Dogs and Cats
Inclusion-Exclusion Formula
Proof of Inclusion - Exlusion formula
Example 2 : Integer solutions of an equation
Example 3 : Words not containing some strings
Example 4 : Arranging 3 x's, 3 y's and 3 z's
Example 5 : Non-multiples of 2 or 3
Example 6 : Integers not divisible by 5, 7 or 11
A tip in solving problems
Example 7 : A dog nor a cat
Example 8 : Brownies, Muffins and Cookies
Example 10 : Integer solutions of an equation
Example 11 : Seating Arrangement - Part 1
Example 11 : Seating Arrangement - Part 2
Example 12 : Integer solutions of an equation
Number of Onto Functions.
Formula for Number of Onto Functions
Example 13 : Onto Functions
Example 14 : No one in their own house
Derangements
Derangements of 4 numbers
Example 15 : Bottles and caps
Example 16 : Self grading
Example 17 : Even integers and their places
Example 18 : Finding total number of items
Example 19 : Devising a secret code
Placing rooks on the chessboard
Rook Polynomial
Rook Polynomial.
Week 11
Motivation for recurrence relation
Getting started with recurrence relations
What is a recurrence relation?
Compound Interest as a recurrence relation
Examples of recurrence relations
Example - Number of ways of climbing steps
Number of ways of climbing steps: Recurrence relation
Example - Rabbits on an island
Example - n-bit string
Example - n-bit string without consecutive zero
Solving Linear Recurrence Relations - A theorem
A note on the proof
Soving recurrence relation - Example 1
Soving recurrence relation - Example 2
Fibonacci Sequence
Introduction to Fibonacci sequence
Solution of Fibbonacci sequence
A basic introduction to 'complexity'
Intuition for 'complexity'
Visualizing complexity order as a graph
Tower of Hanoi
Reccurence relation of Tower of Hanoi
Solution for the recurrence relation of Tower of Hanoi
A searching technique
Recurrence relation for Binary search
Solution for the recurrence relation of Binary search
Example: Door knocks example
Example: Door knocks example solution
Door knock example and Merge sort
Introduction to Merge sort - 1
Recurrence relation for Merge sort
Week 12
Intoduction to advanced topics
Introduction to Chromatic polynomial
Chromatic polynomial of complete graphs
Chromatic polynomial of cycle on 4 vertices - Part 1
Chromatic polynomial of cycle on 4 vertices - Part 2
Correspondence between partition and generating functions
Correspondence between partition and generating functions: In general
Distinct partitions and odd partitions
Distinct partitions and generating functions
Odd partitions and generating functions
Distinct partitions equals odd partitions: Observation
Distinct partitions equals odd partitions: Proof
Why 'partitions' to 'polynomial'?
Example: Picking 4 letters from the word 'INDIAN'
Motivation for exponential generating function
Recurrrence relation: The theorem and its proof
Introduction to Group Theory
Uniqueness of the identity element
Formal definition of a Group
Groups: Examples and non-examples
Groups: Special Examples Part 1
Groups: Special Examples Part 2
Subgroup: Defintion and examples
Lagrange's theorem
Summary.
Conclusion.
Watch on YouTube
Video
Video Download
Full Video Download
FORMATS AVAILABLE FOR DOWNLOAD:
MP4 format(42 MB):
Mirror 1
Mirror 2
FLV format(4 MB):
Mirror 1
Mirror 2
3gp format(4 MB):
Mirror 1
Mirror 2
MP3 Format :
Download MP3
×
Get Alert for certification?
Would you like to know when this course is offered for certification?
Email ID*
×
Issue Reporting
Found an Issue: Report it!
Issue Description *
Email ID
Transcripts of video
Yet to be verified by subject matter expert(s)
loading...
Important: Please enable javascript in your browser and download
Adobe Flash player
to view this site
Site Maintained by Web Studio, IIT Madras. Contact Webmaster:
nptel@iitm.ac.in