Course106106183400 lectures
Discrete Mathematics
Prof. Sudarshan Iyengar · IIT Ropar
About
The course will be an introduction to Discrete Mathematics which comprises of the essentials for a computer science student to go ahead and study any other topics in the subject. The emphasis will be on problem solving as well as proofs. We will be providing motivational illustrations and applications through out the course. The course doesn't assume any pre-requisites except for high school level arithmetic and algebra.
Intended audience: Any Interested Learners
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 Permutations and Combinations
- Combinations with Repetition - Part 1
- Combinations with Repetition - Part 2
- Combination with Repetition - Problems
- Binomial Theorem
- Applications of Binomial Theorem
- Properties of Binomial Thoerem
- Multinomial Theorem
- Problems on Binomial and Multinomial 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
- 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
Syllabus and materials
At NPTEL, as the course publishes them.
Credits and licence
- Institution
- IIT Ropar
- Department
- Computer Science and Engineering
- Teacher
- Prof. Sudarshan Iyengar
- Level
- Undergraduate
- Language
- English
- Subjects
- Computer science, Engineering
- Source
- NPTEL
- Licence
- CC BY-NC-SA, as NPTEL states it. Non-commercial use only. NPTEL's terms
- Attribution
- NPTEL states: "Distributed under Creative Commons Attribution-ShareAlike / CC BY - NC - SA", beside a BY-NC-SA badge. Coordinated by IIT Madras.
- Who can watch
- NPTEL gives no rating. Invisible Network shows it to Teens profiles and older, judged from what the source says about it. How courses are placed
More like this
NPTEL103106570
Course
Interfacial Engineering
40 lectures · Video
NPTEL106106169
Course
Social Networks
166 lectures · Source's player
NPTEL106106184
Course
Deep Learning - IIT Ropar
117 lectures · Source's player
NPTEL108106177
Course
Digital System Design
68 lectures · Video
NPTEL106106182
Course
The Joy of Computing using Python
225 lectures · Source's player
TED
Talk
The future we're building -- and boring
Source's player
TED
Talk
The thrilling potential of SixthSense technology
Source's player
TED
Talk
Why don't perpetual motion machines ever work?
Source's player
Course
History 7b Spring 2006 UC Berkeley (History 7B US History: from Civil War to Present)
39 lectures · Audio
Course
Science Events Video
84 lectures · Video
Course
Nuclear Engineering 101 001 Fall 2009 UC Berkeley Nuclear Reactions and Radiation (Nuclear Engineering 101, 001|Fall 2009|UC Berkeley (Nuclear Reactions and Radiation))
29 lectures · Audio
Course
Matrix Methods in Data Analysis, Signal Processing, and Machine Learning
34 lectures · Video
Course
Matrix Methods in Data Analysis, Signal Processing, and Machine Learning
34 lectures · Video