NPTEL : NOC:Discrete Mathematics (Computer Science and Engineering)

Co-ordinators : Prof. Sudarshan Iyengar


Lecture 1 - Motivation for Counting

Lecture 2 - Paper Folding Example

Lecture 3 - Rubik's Cube Example

Lecture 4 - Factorial Example

Lecture 5 - Counting in Computer Science

Lecture 6 - Motivation for Catalan numbers

Lecture 7 - Rule of Sum and Rule of Product

Lecture 8 - Problems on Rule of Sum and Rule of Product

Lecture 9 - Factorial Explained

Lecture 10 - Proof of n! - Part 1

Lecture 11 - Proof of n! - Part 2

Lecture 12 - Astronomical Numbers

Lecture 13 - Permutations - Part 1

Lecture 14 - Permutations - Part 2

Lecture 15 - Permutations - Part 3

Lecture 16 - Permutations - Part 4

Lecture 17 - Problems on Permutations

Lecture 18 - Combinations - Part 1

Lecture 19 - Combinations - Part 2

Lecture 20 - Combinations - Part 3

Lecture 21 - Combinations - Part 4

Lecture 22 - Problems on Combinations

Lecture 23 - Difference between Permuations and Combinations

Lecture 24 - Combination with Repetition - Part 1

Lecture 25 - Combination with Repetition - Part 2

Lecture 26 - Combination with Repetition - Problems

Lecture 27 - Binomial theorem

Lecture 28 - Applications of Binomial theorem

Lecture 29 - Properties of Binomial theorem

Lecture 30 - Multinomial theorem

Lecture 31 - Problems on Binomial theorem

Lecture 32 - Pascal's Triangle

Lecture 33 - Fun facts on Pascal's Triangle

Lecture 34 - Catalan Numbers - Part 1

Lecture 35 - Catalan Numbers - Part 2

Lecture 36 - Catalan Numbers - Part 3

Lecture 37 - Catalan Numbers - Part 4

Lecture 38 - Examples of Catalan numbers

Lecture 39 - Chapter Summary

Lecture 40 - Introduction to Set Theory

Lecture 41 - Example, definiton and notation

Lecture 42 - Sets - Problems Part 1

Lecture 43 - Subsets - Part 1

Lecture 44 - Subsets - Part 2

Lecture 45 - Subsets - Part 3

Lecture 46 - Union and intersections of sets

Lecture 47 - Union and intersections of sets - Part 1

Lecture 48 - Union and intersections of sets - Part 2

Lecture 49 - Union and intersections of sets - Part 3

Lecture 50 - Cardinality of Union of two sets - Part 1

Lecture 51 - Cardinality of Union of two sets - Part 2

Lecture 52 - Cardinality of Union of three sets

Lecture 53 - Power Set - Part 1

Lecture 54 - Power set - Part 2

Lecture 55 - Power set - Part 3

Lecture 56 - Connection betwenn Binomial Theorem and Power Sets

Lecture 57 - Power set - Problems

Lecture 58 - Complement of a set

Lecture 59 - De Morgan's Laws - Part 1

Lecture 60 - De Morgan's Laws - Part 2

Lecture 61 - A proof technique

Lecture 62 - De Morgan's Laws - Part 3

Lecture 63 - De Morgan's Laws - Part 4

Lecture 64 - Set difference - Part 1

Lecture 65 - Set difference - Part 2

Lecture 66 - Symmetric difference

Lecture 67 - History

Lecture 68 - Summary

Lecture 69 - Motivational example

Lecture 70 - Introduction to Statements

Lecture 71 - Examples and Non-examples of Statements

Lecture 72 - Introduction to Negation

Lecture 73 - Negation - Explanation

Lecture 74 - Negation - Truthtable

Lecture 75 - Examples for Negation

Lecture 76 - Motivation for OR operator

Lecture 77 - Introduction to OR operator

Lecture 78 - Truthtable for OR operator

Lecture 79 - OR operator for 3 Variables

Lecture 80 - Truthtable for AND operator

Lecture 81 - AND operator for 3 Variables

Lecture 82 - Primitive and Compound statements - Part 1

Lecture 83 - Primitive and Compound statements - Part 2

Lecture 84 - Problems involoving NOT, OR and AND operators

Lecture 85 - Introduction to implication

Lecture 86 - Examples and Non-examples of Implication - Part 1

Lecture 87 - Examples and Non-examples of Implication - Part 2

Lecture 88 - Explanation of Implication

Lecture 89 - Introduction to Double Implication

Lecture 90 - Explanation of Double Implication

Lecture 91 - Converse, Inverse and Contrapositive

Lecture 92 - XOR operator - Part 1

Lecture 93 - XOR operator - Part 2

Lecture 94 - XOR operator - Part 3

Lecture 95 - Problems

Lecture 96 - Tautology, Contradiction - Part 1

Lecture 97 - Tautology, Contradiction - Part 2

Lecture 98 - Tautology, Contradiction - Part 3

Lecture 99 - SAT Problem - Part 1

Lecture 100 - SAT Problem - Part 2

Lecture 101 - Logical Equivalence - Part 1

Lecture 102 - Logical Equivalence - Part 2

Lecture 103 - Logical Equivalence - Part 3

Lecture 104 - Logical Equivalence - Part 4

Lecture 105 - Motivation for laws of logic

Lecture 106 - Double negation - Part 1

Lecture 107 - Double negation - Part 2

Lecture 108 - Laws of Logic

Lecture 109 - De Morgan's Law - Part 1

Lecture 110 - De Morgan's Law - Part 2

Lecture 111 - Rules of Inferences - Part 1

Lecture 112 - Rules of Inferences - Part 2

Lecture 113 - Rules of Inferences - Part 3

Lecture 114 - Rules of Inferences - Part 4

Lecture 115 - Rules of Inferences - Part 5

Lecture 116 - Rules of Inferences - Part 6

Lecture 117 - Rules of Inferences - Part 7

Lecture 118 - Conclusion

Lecture 119 - Introduction to Relation

Lecture 120 - Graphical Representation of a Relation

Lecture 121 - Various sets

Lecture 122 - Matrix Representation of a Relation

Lecture 123 - Relation - An Example

Lecture 124 - Cartesian Product

Lecture 125 - Set Representation of a Relation

Lecture 126 - Revisiting Representations of a Relation

Lecture 127 - Examples of Relations

Lecture 128 - Number of relations - Part 1

Lecture 129 - Number of relations - Part 2

Lecture 130 - Reflexive relation - Introduction

Lecture 131 - Example of a Reflexive relation

Lecture 132 - Reflexive relation - Matrix representation

Lecture 133 - Number of Reflexive relations

Lecture 134 - Symmetric Relation - Introduction

Lecture 135 - Symmetric Relation - Matrix representation

Lecture 136 - Symmetric Relation - Examples and non examples

Lecture 137 - Parallel lines revisited

Lecture 138 - Number of symmetric relations - Part 1

Lecture 139 - Number of symmetric relations - Part 2

Lecture 140 - Examples of Reflexive and Symmetric Relations

Lecture 141 - Pattern

Lecture 142 - Transitive relation - Examples and non examples

Lecture 143 - Antisymmetric relation

Lecture 144 - Examples of Transitive and Antisymmetric Relation

Lecture 145 - Antisymmetric - Graphical representation

Lecture 146 - Antisymmetric - Matrix representation

Lecture 147 - Number of Antisymmetric relations

Lecture 148 - Condition for relation to be reflexive

Lecture 149 - Few notations

Lecture 150 - Condition for relation to be reflexive

Lecture 151 - Condition for relation to be reflexive

Lecture 152 - Condition for relation to be symmetric

Lecture 153 - Condition for relation to be symmetric

Lecture 154 - Condition for relation to be antisymmetric

Lecture 155 - Equivalence relation

Lecture 156 - Equivalence relation - Example 4

Lecture 157 - Partition - Part 1

Lecture 158 - Partition - Part 2

Lecture 159 - Partition - Part 3

Lecture 160 - Partition - Part 4

Lecture 161 - Partition - Part 5

Lecture 162 - Partition - Part 6

Lecture 163 - Motivational Example - 1

Lecture 164 - Motivational Example - 2

Lecture 165 - Commonality in examples

Lecture 166 - Motivational Example - 3

Lecture 167 - Example - 4 Explanation

Lecture 168 - Introduction to functions

Lecture 169 - Defintion of a function - Part 1

Lecture 170 - Defintion of a function - Part 2

Lecture 171 - Defintion of a function - Part 3

Lecture 172 - Relations vs Functions - Part 1

Lecture 173 - Relations vs Functions - Part 2

Lecture 174 - Introduction to One-One Function

Lecture 175 - One-One Function - Example 1

Lecture 176 - One-One Function - Example 2

Lecture 177 - One-One Function - Example 3

Lecture 178 - Proving a Function is One-One

Lecture 179 - Examples and Non- examples of One-One function

Lecture 180 - Cardinality condition in One-One function - Part 1

Lecture 181 - Cardinality condition in One-One function - Part 2

Lecture 182 - Introduction to Onto Function - Part 1

Lecture 183 - Introduction to Onto Function - Part 2

Lecture 184 - Definition of Onto Function

Lecture 185 - Examples of Onto Function

Lecture 186 - Cardinality condition in Onto function - Part 1

Lecture 187 - Cardinality condition in Onto function - Part 2

Lecture 188 - Introduction to Bijection

Lecture 189 - Examples of Bijection

Lecture 190 - Cardinality condition in Bijection - Part 1

Lecture 191 - Cardinality condition in Bijection - Part 2

Lecture 192 - Counting number of functions

Lecture 193 - Number of functions

Lecture 194 - Number of One-One functions - Part 1

Lecture 195 - Number of One-One functions - Part 2

Lecture 196 - Number of One-One functions - Part 3

Lecture 197 - Number of Onto functions

Lecture 198 - Number of Bijections

Lecture 199 - Counting number of functions.

Lecture 200 - Motivation for Composition of functions - Part 1

Lecture 201 - Motivation for Composition of functions - Part 2

Lecture 202 - Definition of Composition of functions

Lecture 203 - Why study Composition of functions

Lecture 204 - Example of Composition of functions - Part 1

Lecture 205 - Example of Composition of functions - Part 2

Lecture 206 - Motivation for Inverse functions

Lecture 207 - Inverse functions

Lecture 208 - Examples of Inverse functions

Lecture 209 - Application of inverse functions - Part 1

Lecture 210 - Three stories

Lecture 211 - Three stories - Connecting the dots

Lecture 212 - Mathematical induction - An illustration

Lecture 213 - Mathematical Induction - Its essence

Lecture 214 - Mathematical Induction - The formal way

Lecture 215 - MI - Sum of odd numbers

Lecture 216 - MI - Sum of powers of 2

Lecture 217 - MI - Inequality 1

Lecture 218 - MI - Inequality 1 (solution)

Lecture 219 - MI - To prove divisibility

Lecture 220 - MI - To prove divisibility (solution)

Lecture 221 - MI - Problem on satisfying inequalities

Lecture 222 - MI - Problem on satisfying inequalities (solutions)

Lecture 223 - MI - Inequality 2

Lecture 224 - MI - Inequality 2 solution

Lecture 225 - Mathematical Induction - Example 9

Lecture 226 - Mathematical Induction - Example 10 solution

Lecture 227 - Binomial Coeffecients - Proof by induction

Lecture 228 - Checker board and Triomioes - A puzzle

Lecture 229 - Checker board and triominoes - Solution

Lecture 230 - Mathematical induction - An important note

Lecture 231 - Mathematical Induction - A false proof

Lecture 232 - A false proof - Solution

Lecture 233 - Motivation for Pegionhole Principle

Lecture 234 - Group of n people

Lecture 235 - Set of n integgers

Lecture 236 - 10 points on an equilateral triangle

Lecture 237 - Pegionhole Principle - A result

Lecture 238 - Consecutive integers

Lecture 239 - Consecutive integers solution

Lecture 240 - Matching initials

Lecture 241 - Matching initials - Solution

Lecture 242 - Numbers adding to 9

Lecture 243 - Numbers adding to 9 - Solution

Lecture 244 - Deck of cards

Lecture 245 - Deck of cards - Solution

Lecture 246 - Number of errors

Lecture 247 - Number of errors - Solution

Lecture 248 - Puzzle - Challenge for you

Lecture 249 - Friendship - an interesting property

Lecture 250 - Connectedness through Connecting people

Lecture 251 - Traversing the bridges

Lecture 252 - Three utilities problem

Lecture 253 - Coloring the India map

Lecture 254 - Defintion of a Graph

Lecture 255 - Degree and degree sequence

Lecture 256 - Relation between number of edges and degrees

Lecture 257 - Relation between number of edges and degrees - Proof

Lecture 258 - Hand shaking lemma - Corollary

Lecture 259 - Problems based on Hand shaking lemma

Lecture 260 - Havel Hakimi theorem - Part 1

Lecture 261 - Havel Hakimi theorem - Part 2

Lecture 262 - Havel Hakimi theorem - Part 3

Lecture 263 - Havel Hakimi theorem - Part 4

Lecture 264 - Havel Hakimi theorem - Part 5

Lecture 265 - Regular graph and irregular graph

Lecture 266 - Walk

Lecture 267 - Trail

Lecture 268 - Path and closed path

Lecture 269 - Definitions revisited

Lecture 270 - Examples of walk, trail and path

Lecture 271 - Cycle and circuit

Lecture 272 - Example of cycle and circuit

Lecture 273 - Relation between walk and path

Lecture 274 - Relation between walk and path - An induction proof

Lecture 275 - Subgraph

Lecture 276 - Spanning and induced subgraph

Lecture 277 - Spanning and induced subgraph - A result

Lecture 278 - Introduction to Tree

Lecture 279 - Connected and Disconnected graphs

Lecture 280 - Property of a cycle

Lecture 281 - Edge condition for connectivity

Lecture 282 - Connecting connectedness and path

Lecture 283 - Connecting connectedness and path - An illustration

Lecture 284 - Cut vertex

Lecture 285 - Cut edge

Lecture 286 - Illustration of cut vertices and cut edges

Lecture 287 - NetworkX - Need of the hour

Lecture 288 - Introduction to Python - Installation

Lecture 289 - Introduction to Python - Basics

Lecture 290 - Introduction to NetworkX

Lecture 291 - Story so far - Using NetworkX

Lecture 292 - Directed, weighted and multi graphs

Lecture 293 - Illustration of Directed, weighted and multi graphs

Lecture 294 - Graph representations - Introduction

Lecture 295 - Adjacency matrix representation

Lecture 296 - Incidence matrix representation

Lecture 297 - Isomorphism - Introduction

Lecture 298 - Isomorphic graphs - An illustration

Lecture 299 - Isomorphic graphs - A challenge

Lecture 300 - Non-isomorphic graphs

Lecture 301 - Isomorphism - A question

Lecture 302 - Complement of a Graph - Introduction

Lecture 303 - Complement of a Graph - Illiustration

Lecture 304 - Self complement

Lecture 305 - Complement of a disconnected graph is connected

Lecture 306 - Complement of a disconnected graph is connected - Solution

Lecture 307 - Which is more? Connected graphs or disconnected graphs?

Lecture 308 - Bipartite graphs.

Lecture 309 - Bipartite graphs - A puzzle

Lecture 310 - Bipartite graphs - Converse part of the puzzle

Lecture 311 - Definition of Eulerian Graph

Lecture 312 - Illustration of eulerian graph

Lecture 313 - Non- example of Eulerian graph

Lecture 314 - Litmus test for an Eulerian graph

Lecture 315 - Why even degree?

Lecture 316 - Proof for even degree implies graph is eulerian

Lecture 317 - A condition for Eulerian trail

Lecture 318 - Why the name Eulerian

Lecture 319 - Can you traverse all location?

Lecture 320 - Defintion of Hamiltonian graphs

Lecture 321 - Examples of Hamiltonian graphs

Lecture 322 - Hamiltonian graph - A result

Lecture 323 - A result on connectedness

Lecture 324 - A result on Path

Lecture 325 - Dirac's Theorem

Lecture 326 - Dirac's theorem - A note

Lecture 327 - Ore's Theorem

Lecture 328 - Dirac's Theorem v/s Ore's Theorem

Lecture 329 - Eulerian and Hamiltonian Are they related

Lecture 330 - Importance of Hamiltonian graphs in Computer science

Lecture 331 - Constructing non intersecting roads

Lecture 332 - Definition of a Planar graph

Lecture 333 - Examples of Planar graphs

Lecture 334 - V - E + R = 2

Lecture 335 - Illustration of V - E + R =2

Lecture 336 - V - E + R = 2; Use induction

Lecture 337 - Proof of V - E + R = 2

Lecture 338 - Famous non-planar graphs

Lecture 339 - Litmus test for planarity

Lecture 340 - Planar graphs - Inequality 1

Lecture 341 - 3 Utilities problem - Revisited

Lecture 342 - Complete graph on 5 vertices is non-planar - Proof

Lecture 343 - Prisoners and cells

Lecture 344 - Prisoners example and Proper coloring

Lecture 345 - Chromatic number of a graph

Lecture 346 - Examples on Proper coloring

Lecture 347 - Recalling the India map problem

Lecture 348 - Recalling the India map problem - Solution

Lecture 349 - NetworkX - Digraphs

Lecture 350 - NetworkX - Adjacency matrix

Lecture 351 - NetworkX - Random graphs

Lecture 352 - NetworkX - Subgarph

Lecture 353 - NetworkX - Isomorphic graphs Part 1

Lecture 354 - NetworkX - Isomorphic graphs Part 2

Lecture 355 - NetworkX - Isomorphic graphs: A game to play

Lecture 356 - NetworkX - Graph complement

Lecture 357 - NetworkX - Eulerian graphs

Lecture 358 - NetworkX - Bipaprtite graphs

Lecture 359 - NetworkX - Coloring

Lecture 360 - Counting in a creative way

Lecture 361 - Example 1 - Fun with words

Lecture 362 - Words and the polynomial

Lecture 363 - Words and the polynomial - Explained

Lecture 364 - Example 2 - Picking five balls

Lecture 365 - Picking five balls - Solution

Lecture 366 - Picking five balls - Another version

Lecture 367 - Defintion of Generating function

Lecture 368 - Generating function examples - Part 1

Lecture 369 - Generating function examples - Part 2

Lecture 370 - Generating function examples - Part 3

Lecture 371 - Binomial expansion - A generating function

Lecture 372 - Binomial expansion - Explained

Lecture 373 - Picking 7 balls - The naive way

Lecture 374 - Picking 7 balls - The creative way

Lecture 375 - Generating functions - Problem 1

Lecture 376 - Generating functions - Problem 2

Lecture 377 - Generating functions - Problem 3

Lecture 378 - Why Generating function?

Lecture 379 - Introduction to Advanced Counting

Lecture 380 - Example 1 : Dogs and Cats

Lecture 381 - Inclusion-Exclusion Formula

Lecture 382 - Proof of Inclusion - Exlusion formula

Lecture 383 - Example 2 : Integer solutions of an equation

Lecture 384 - Example 3 : Words not containing some strings

Lecture 385 - Example 4 : Arranging 3 x's, 3 y's and 3 z's

Lecture 386 - Example 5 : Non-multiples of 2 or 3

Lecture 387 - Example 6 : Integers not divisible by 5, 7 or 11

Lecture 388 - A tip in solving problems

Lecture 389 - Example 7 : A dog nor a cat

Lecture 390 - Example 8 : Brownies, Muffins and Cookies

Lecture 391 - Example 10 : Integer solutions of an equation

Lecture 392 - Example 11 : Seating Arrangement - Part 1

Lecture 393 - Example 11 : Seating Arrangement - Part 2

Lecture 394 - Example 12 : Integer solutions of an equation

Lecture 395 - Number of Onto Functions.

Lecture 396 - Formula for Number of Onto Functions

Lecture 397 - Example 13 : Onto Functions

Lecture 398 - Example 14 : No one in their own house

Lecture 399 - Derangements

Lecture 400 - Derangements of 4 numbers

Lecture 401 - Example 15 : Bottles and caps

Lecture 402 - Example 16 : Self grading

Lecture 403 - Example 17 : Even integers and their places

Lecture 404 - Example 18 : Finding total number of items

Lecture 405 - Example 19 : Devising a secret code

Lecture 406 - Placing rooks on the chessboard

Lecture 407 - Rook Polynomial

Lecture 408 - Rook Polynomial

Lecture 409 - Motivation for recurrence relation

Lecture 410 - Getting started with recurrence relations

Lecture 411 - What is a recurrence relation?

Lecture 412 - Compound Interest as a recurrence relation

Lecture 413 - Examples of recurrence relations

Lecture 414 - Example - Number of ways of climbing steps

Lecture 415 - Number of ways of climbing steps: Recurrence relation

Lecture 416 - Example - Rabbits on an island

Lecture 417 - Example - n-bit string

Lecture 418 - Example - n-bit string without consecutive zero

Lecture 419 - Solving Linear Recurrence Relations - A theorem

Lecture 420 - A note on the proof

Lecture 421 - Soving recurrence relation - Example 1

Lecture 422 - Soving recurrence relation - Example 2

Lecture 423 - Fibonacci Sequence

Lecture 424 - Introduction to Fibonacci sequence

Lecture 425 - Solution of Fibbonacci sequence

Lecture 426 - A basic introduction to 'complexity'

Lecture 427 - Intuition for 'complexity'

Lecture 428 - Visualizing complexity order as a graph

Lecture 429 - Tower of Hanoi

Lecture 430 - Reccurence relation of Tower of Hanoi

Lecture 431 - Solution for the recurrence relation of Tower of Hanoi

Lecture 432 - A searching technique

Lecture 433 - Recurrence relation for Binary search

Lecture 434 - Solution for the recurrence relation of Binary search

Lecture 435 - Example: Door knocks example

Lecture 436 - Example: Door knocks example solution

Lecture 437 - Door knock example and Merge sort

Lecture 438 - Introduction to Merge sort - 1

Lecture 439 - Introduction to Merge sort - 2

Lecture 440 - Intoduction to advanced topics

Lecture 441 - Introduction to Chromatic polynomial

Lecture 442 - Chromatic polynomial of complete graphs

Lecture 443 - Chromatic polynomial of cycle on 4 vertices - Part 1

Lecture 444 - Chromatic polynomial of cycle on 4 vertices - Part 2

Lecture 445 - Correspondence between partition and generating functions

Lecture 446 - Correspondence between partition and generating functions: In general

Lecture 447 - Distinct partitions and odd partitions

Lecture 448 - Distinct partitions and generating functions

Lecture 449 - Odd partitions and generating functions

Lecture 450 - Distinct partitions equals odd partitions: Observation

Lecture 451 - Distinct partitions equals odd partitions: Proof

Lecture 452 - Why 'partitions' to 'polynomial'?

Lecture 453 - Example: Picking 4 letters from the word 'INDIAN'

Lecture 454 - Motivation for exponential generating function

Lecture 455 - Recurrrence relation: The theorem and its proof

Lecture 456 - Introduction to Group Theory

Lecture 457 - Uniqueness of the identity element

Lecture 458 - Formal definition of a Group

Lecture 459 - Groups: Examples and non-examples

Lecture 460 - Groups: Special Examples - Part 1

Lecture 461 - Groups: Special Examples - Part 2

Lecture 462 - Subgroup: Defintion and examples

Lecture 463 - Lagrange's theorem

Lecture 464 - Summary

Lecture 465 - Conclusion