NOC:Discrete Mathematics


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