Media Storage Type : 64 GB USB Stick
NPTEL Subject Matter Expert : Prof. Sudarshan Iyengar
NPTEL Co-ordinating Institute : IIT Madras
NPTEL Lecture Count : 465
NPTEL Course Size : 31 GB
NPTEL PDF Text Transcription : Available and Included
NPTEL Subtitle Transcription : Available and Included (SRT)
Lecture Titles:
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 - Recurrence relation for Merge sort
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