IIT Ropar · Computer Science

Discrete Mathematics

Prof. Sudarshan Iyengar · 466 free video lectures

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…

▶ Play on Open Lecture HallCourse page ↗

Lectures

  1. Motivation for Counting
  2. Paper Folding Example
  3. Rubik's Cube Example
  4. Factorial Example
  5. Counting in Computer Science
  6. Motivation for Catalan numbers
  7. Rule of Sum and Rule of Product
  8. Problems on Rule of Sum and Rule of Product
  9. Factorial Explained
  10. Proof of n! - Part 1
  11. Proof of n! - Part 2
  12. Astronomical Numbers
  13. Permutations - Part 1
  14. Permutations - Part 2
  15. Permutations - Part 3
  16. Permutations - Part 4
  17. Problems on Permutations
  18. Combinations - Part 1
  19. Combinations - Part 2
  20. Combinations - Part 3
  21. Combinations - Part 4
  22. Problems on Combinations
  23. Difference between Permutations and Combinations
  24. Combinations with Repetition - Part 1
  25. Combinations with Repetition - Part 2
  26. Combination with Repetition - Problems
  27. Binomial Theorem
  28. Applications of Binomial Theorem
  29. Properties of Binomial Thoerem
  30. Multinomial Theorem
  31. Problems on Binomial and Multinomial Theorem
  32. Pascal's Triangle
  33. Fun facts on Pascal's Triangle
  34. Catalan Numbers - Part 1
  35. Catalan numbers - Part 2
  36. Catalan Numbers - Part 3
  37. Catalan Numbers - Part 4
  38. Examples of Catalan Numbers
  39. Chapter Summary
  40. Introduction to Set Theory
  41. Example, definiton and notation
  42. Sets - Problems Part 1
  43. Subsets - Part 1
  44. Subsets - Part 2
  45. Subsets - Part 3
  46. Union and intersections of sets
  47. Union and intersections of sets - Part 1
  48. Union and intersections of sets - Part 2
  49. Union and intersections of sets - Part 3
  50. Cardinality of Union of two sets - Part 1
  51. Cardinality of Union of sets - Part 2
  52. Cardinality of Union of three sets
  53. Power Set - Part 1
  54. Power set - Part 2
  55. Power set - Part 3
  56. Connection betwenn Binomial Theorem and Power Sets
  57. Power set - Problems
  58. Complement of a set
  59. De Morgan's Laws - Part 1
  60. De Morgan's Laws - Part 2
  61. A proof technique
  62. De Morgan's Laws - Part 3
  63. De Morgan's Laws - Part 4
  64. Set difference - Part 1
  65. Set difference - Part 2
  66. Symmetric difference
  67. History
  68. Summary
  69. Motivational example
  70. Introduction to Statements
  71. Examples and Non-examples of Statements
  72. Introduction to Negation
  73. Negation - Explanation
  74. Negation - Truthtable
  75. Examples for Negation
  76. Motivation for OR operator
  77. Introduction to OR operator
  78. Truthtable for OR operator
  79. OR operator for 3 Variables
  80. Truthtable for AND operator
  81. AND operator for 3 Variables
  82. Primitive and Compound statements - Part 1
  83. Primitive and Compound statements - Part 2
  84. Problems involoving NOT, OR and AND operators
  85. Introduction to implication
  86. Examples and Non-examples of Implication - Part 1
  87. Examples and Non-examples of Implication - Part 2
  88. Explanation of Implication
  89. Introduction to Double Implication
  90. Explanation of Double Implication
  91. Converse, Inverse and Contrapositive
  92. XOR operator - Part 1
  93. XOR operator - Part 2
  94. XOR operator - Part 3
  95. Problems
  96. Tautology, Contradiction - Part 1
  97. Tautology, Contradiction - Part 2
  98. Tautology, Contradiction - Part 3
  99. SAT Problem - Part 1
  100. SAT Problem - Part 2
  101. Logical Equivalence - Part 1
  102. Logical Equivalence - Part 2
  103. Logical Equivalence - Part 3
  104. Logical Equivalence - Part 4
  105. Motivation for laws of logic
  106. Double negation - Part 1
  107. Double negation - Part 2
  108. Laws of Logic
  109. De Morgan's Law - Part 1
  110. De Morgan's Law - Part 2
  111. Rules of Inferences - Part 1
  112. Rules of Inferences - Part 2
  113. Rules of Inferences - Part 3
  114. Rules of Inferences - Part 4
  115. Rules of Inferences - Part 5
  116. Rules of Inferences - Part 6
  117. Rules of Inferences - Part 7
  118. Conclusion
  119. Introduction to Relation
  120. Graphical Representation of a Relation
  121. Various sets
  122. Matrix Representation of a Relation
  123. Relation - An Example
  124. Cartesian Product
  125. Set Representation of a Relation
  126. Revisiting Representations of a Relation
  127. Examples of Relations
  128. Number of relations - Part 1
  129. Number of relations - Part 2
  130. Reflexive relation - Introduction
  131. Example of a Reflexive relation
  132. Reflexive relation - Matrix representation
  133. Number of Reflexive relations
  134. Symmetric Relation - Introduction
  135. Symmetric Relation - Matrix representation
  136. Symmetric Relation - Examples and non examples
  137. Parallel lines revisited
  138. Number of symmetric relations - Part 1
  139. Number of symmetric relations - Part 2
  140. Examples of Reflexive and Symmetric Relations
  141. Pattern
  142. Transitive relation - Examples and non examples
  143. Antisymmetric relation
  144. Examples of Transitive and Antisymmetric Relation
  145. Antisymmetric - Graphical representation
  146. Antisymmetric - Matrix representation
  147. Number of Antisymmetric relations
  148. Condition for relation to be reflexive
  149. Few notations
  150. Condition for relation to be reflexive
  151. Condition for relation to be reflexive
  152. Condition for relation to be symmetric
  153. Condition for relation to be symmetric
  154. Condition for relation to be antisymmetric
  155. Equivalence relation
  156. Equivalence relation - Example 4
  157. Partition - Part 1
  158. Partition - Part 2
  159. Partition - Part 3
  160. Partition - Part 4
  161. Partition - Part 5
  162. Partition - Part 5
  163. Motivational Example - 1
  164. Motivational Example - 2
  165. Commonality in examples
  166. Motivational Example - 3
  167. Example - 4 Explanation
  168. Introduction to functions
  169. Defintion of a function - Part 1
  170. Defintion of a function - Part 2
  171. Defintion of a function - Part 3
  172. Relations vs Functions - Part 1
  173. Relations vs Functions - Part 2
  174. Introduction to One-One Function
  175. One-One Function - Example 1
  176. One-One Function - Example 2
  177. One-One Function - Example 3
  178. Proving a Function is One-One
  179. Examples and Non- examples of One-One function
  180. Cardinality condition in One-One function - Part 1
  181. Cardinality condition in One-One function - Part 2
  182. Introduction to Onto Function - Part 1
  183. Introduction to Onto Function - Part 2
  184. Definition of Onto Function
  185. Examples of Onto Function
  186. Cardinality condition in Onto function - Part 1
  187. Cardinality condition in Onto function - Part 2
  188. Introduction to Bijection
  189. Examples of Bijection
  190. Cardinality condition in Bijection - Part 1
  191. Cardinality condition in Bijection - Part 2
  192. Counting number of functions
  193. Number of functions
  194. Number of One-One functions - Part 1
  195. Number of One-One functions - Part 2
  196. Number of One-One functions - Part 3
  197. Number of Onto functions
  198. Number of Bijections
  199. Counting number of functions
  200. Motivation for Composition of functions - Part 1
  201. Motivation for Composition of functions - Part 2
  202. Definition of Composition of functions
  203. Why study Composition of functions
  204. Example of Composition of functions - Part 1
  205. Example of Composition of functions - Part 2
  206. Motivation for Inverse functions
  207. Inverse functions
  208. Examples of Inverse functions
  209. Application of inverse functions - Part 1
  210. Three stories
  211. Three stories - Connecting the dots
  212. Mathematical induction - An illustration
  213. Mathematical Induction - Its essence
  214. Mathematical Induction - The formal way
  215. MI - Sum of odd numbers
  216. MI - Sum of powers of 2
  217. MI - Inequality 1
  218. MI - Inequality 1 (solution)
  219. MI - To prove divisibility
  220. MI - To prove divisibility (solution)
  221. MI - Problem on satisfying inequalities
  222. MI - Problem on satisfying inequalities (solutions)
  223. MI - Inequality 2
  224. MI - Inequality 2 solution
  225. Mathematical Induction - Example 9
  226. Mathematical Induction - Example 10 solution
  227. Binomial Coeffecients - Proof by induction
  228. Checker board and Triomioes - A puzzle
  229. Checker board and triominoes - Solution
  230. Mathematical induction - An important note
  231. Mathematical Induction - A false proof
  232. A false proof - Solution
  233. Motivation for Pegionhole Principle
  234. Group of n people
  235. Set of n integgers
  236. 10 points on an equilateral triangle
  237. Pegionhole Principle - A result
  238. Consecutive integers
  239. Consecutive integers solution
  240. Matching initials
  241. Matching initials - Solution
  242. Numbers adding to 9
  243. Numbers adding to 9 - Solution
  244. Deck of cards
  245. Deck of cards - Solution
  246. Number of errors
  247. Number of errors - Solution
  248. Puzzle - Challenge for you
  249. Friendship - an interesting property
  250. Connectedness through Connecting people
  251. Traversing the bridges
  252. Three utilities problem
  253. Coloring the India map
  254. Defintion of a Graph
  255. Degree and degree sequence
  256. Relation between number of edges and degrees
  257. Relation between number of edges and degrees - Proof
  258. Hand shaking lemma - Corollary
  259. Problems based on Hand shaking lemma
  260. Havel Hakimi theorem - Part 1
  261. Havel Hakimi theorem - Part 2
  262. Havel Hakimi theorem - Part 3
  263. Havel Hakimi theorem - Part 4
  264. Havel Hakimi theorem - Part 5
  265. Regular graph and irregular graph
  266. Walk
  267. Trail
  268. Path and closed path
  269. Definitions revisited
  270. Examples of walk, trail and path
  271. Cycle and circuit
  272. Example of cycle and circuit
  273. Relation between walk and path
  274. Relation between walk and path - An induction proof
  275. Subgraph
  276. Spanning and induced subgraph
  277. Spanning and induced subgraph - A result
  278. Introduction to Tree
  279. Connected and Disconnected graphs
  280. Property of a cycle
  281. Edge condition for connectivity
  282. Connecting connectedness and path
  283. Connecting connectedness and path - An illustration
  284. Cut vertex
  285. Cut edge
  286. Illustration of cut vertices and cut edges
  287. NetworkX - Need of the hour
  288. Introduction to Python - Installation
  289. Introduction to Python - Basics
  290. Introduction to NetworkX
  291. Story so far - Using NetworkX
  292. Directed, weighted and multi graphs
  293. Illustration of Directed, weighted and multi graphs
  294. Graph representations - Introduction
  295. Adjacency matrix representation
  296. Incidence matrix representation
  297. Isomorphism - Introduction
  298. Isomorphic graphs - An illustration
  299. Isomorphic graphs - A challenge
  300. Non - isomorphic graphs
  301. Isomorphism - A question
  302. Complement of a Graph - Introduction
  303. Complement of a Graph - Illiustration
  304. Self complement
  305. Complement of a disconnected graph is connected
  306. Complement of a disconnected graph is connected - Solution
  307. Which is more? Connected graphs or disconnected graphs?
  308. Bipartite graphs
  309. Bipartite graphs - A puzzle
  310. Bipartite graphs - Converse part of the puzzle
  311. Definition of Eulerian Graph
  312. Illustration of eulerian graph
  313. Non- example of Eulerian graph
  314. Litmus test for an Eulerian graph
  315. Why even degree?
  316. Proof for even degree implies graph is eulerian
  317. A condition for Eulerian trail
  318. Why the name Eulerian
  319. Can you traverse all location?
  320. Defintion of Hamiltonian graphs
  321. Examples of Hamiltonian graphs
  322. Hamiltonian graph - A result
  323. A result on connectedness
  324. A result on Path
  325. Dirac's Theorem
  326. Dirac's theorem - A note
  327. Ore's Theorem
  328. Dirac's Theorem v/s Ore's Theorem
  329. Eulerian and Hamiltonian Are they related
  330. Importance of Hamiltonian graphs in Computer science
  331. Constructing non intersecting roads
  332. Definition of a Planar graph
  333. Examples of Planar graphs
  334. V - E + R = 2
  335. Illustration of V - E + R =2
  336. V - E + R = 2; Use induction
  337. Proof of V - E + R = 2
  338. Famous non-planar graphs
  339. Litmus test for planarity
  340. Planar graphs - Inequality 1
  341. 3 Utilities problem - Revisited
  342. Complete graph on 5 vertices is non-planar - Proof
  343. Prisoners and cells
  344. Prisoners example and Proper coloring
  345. Chromatic number of a graph
  346. Examples on Proper coloring
  347. Recalling the India map problem
  348. Recalling the India map problem - Solution
  349. NetworkX - Digraphs
  350. NetworkX - Adjacency matrix
  351. NetworkX- Random graphs
  352. NetworkX - Subgarph
  353. NetworkX - Isomorphic graphs Part 1
  354. NetworkX - Isomorphic graphs Part 2
  355. NetworkX - Isomorphic graphs: A game to play
  356. NetworkX - Graph complement
  357. NetworkX - Eulerian graphs
  358. NetworkX - Bipaprtite graphs
  359. NetworkX - Coloring
  360. Counting in a creative way
  361. Example 1 - Fun with words
  362. Words and the polynomial
  363. Words and the polynomial - Explained
  364. Example 2 - Picking five balls
  365. Picking five balls - Solution
  366. Picking five balls - Another version
  367. Defintion of Generating function
  368. Generating function examples - Part 1
  369. Generating function examples - Part 2
  370. Generating function examples - Part 3
  371. Binomial expansion - A generating function
  372. Binomial expansion - Explained
  373. Picking 7 balls - The naive way
  374. Picking 7 balls - The creative way
  375. Generating functions - Problem 1
  376. Generating functions - Problem 2
  377. Generating functions - Problem 3
  378. Why Generating function?
  379. Introduction to Advanced Counting
  380. Example 1 : Dogs and Cats
  381. Inclusion-Exclusion Formula
  382. Proof of Inclusion - Exlusion formula
  383. Example 2 : Integer solutions of an equation
  384. Example 3 : Words not containing some strings
  385. Example 4 : Arranging 3 x's, 3 y's and 3 z's
  386. Example 5 : Non-multiples of 2 or 3
  387. Example 6 : Integers not divisible by 5, 7 or 11
  388. A tip in solving problems
  389. Example 7 : A dog nor a cat
  390. Example 8 : Brownies, Muffins and Cookies
  391. Example 10 : Integer solutions of an equation
  392. Example 11 : Seating Arrangement - Part 1
  393. Example 11 : Seating Arrangement - Part 2
  394. Example 12 : Integer solutions of an equation
  395. Number of Onto Functions
  396. Formula for Number of Onto Functions
  397. Example 13 : Onto Functions
  398. Example 14 : No one in their own house
  399. Derangements
  400. Derangements of 4 numbers
  401. Example 15 : Bottles and caps
  402. Example 16 : Self grading
  403. Example 17 : Even integers and their places
  404. Example 18 : Finding total number of items
  405. Example 19 : Devising a secret code
  406. Placing rooks on the chessboard
  407. Rook Polynomial
  408. Rook Polynomial
  409. Motivation for recurrence relation
  410. Getting started with recurrence relations
  411. What is a recurrence relation?
  412. Compound Interest as a recurrence relation
  413. Examples of recurrence relations
  414. Example - Number of ways of climbing steps
  415. Number of ways of climbing steps: Recurrence relation
  416. Example - Rabbits on an island
  417. Example - n-bit string
  418. Example - n-bit string without consecutive zero
  419. Solving Linear Recurrence Relations - A theorem
  420. A note on the proof
  421. Soving recurrence relation - Example 1
  422. Soving recurrence relation - Example 2
  423. Fibonacci Sequence
  424. Introduction to Fibonacci sequence
  425. Solution of Fibbonacci sequence
  426. A basic introduction to 'complexity'
  427. Intuition for 'complexity'
  428. Visualizing complexity order as a graph
  429. Tower of Hanoi
  430. Reccurence relation of Tower of Hanoi
  431. Solution for the recurrence relation of Tower of Hanoi
  432. A searching technique
  433. Recurrence relation for Binary search
  434. Solution for the recurrence relation of Binary search
  435. Example: Door knocks example
  436. Example: Door knocks example solution
  437. Door knock example and Merge sort
  438. Introduction to Merge sort - 1
  439. Introduction to Merge sort - 2
  440. Recurrence relation for Merge sort
  441. Intoduction to advanced topics
  442. Introduction to Chromatic polynomial
  443. Chromatic polynomial of complete graphs
  444. Chromatic polynomial of cycle on 4 vertices - Part 1
  445. Chromatic polynomial of cycle on 4 vertices - Part 2
  446. Correspondence between partition and generating functions
  447. Correspondence between partition and generating functions: In general
  448. Distinct partitions and odd partitions
  449. Distinct partitions and generating functions
  450. Odd partitions and generating functions
  451. Distinct partitions equals odd partitions: Observation
  452. Distinct partitions equals odd partitions: Proof
  453. Why 'partitions' to 'polynomial'?
  454. Example: Picking 4 letters from the word 'INDIAN'
  455. Motivation for exponential generating function
  456. Recurrrence relation: The theorem and its proof
  457. Introduction to Group Theory
  458. Uniqueness of the identity element
  459. Formal definition of a Group
  460. Groups: Examples and non-examples
  461. Groups: Special Examples Part 1
  462. Groups: Special Examples Part 2
  463. Subgroup: Defintion and examples
  464. Lagrange's theorem
  465. Summary
  466. Conclusion

From NPTEL (IITs and IISc) · CC BY-NC-SA. More from IIT Ropar.

Open Lecture Hall is free, with no ads and no sign-up. It is not run by or connected to any university; the lectures are the universities' own free recordings, played from where they host them. About & rights