Course10610822772 lectures
Discrete Mathematics - IIITB
Prof. Ashish Choudhury · IIIT Bangalore
About
Discrete mathematics is the study of mathematical structures that are discrete in the sense that they assume only distinct, separate values, rather than in a range of values. It deals with the mathematical objects that are widely used in all most all fields of computer science, such as programming languages, data structures and algorithms, cryptography, operating systems, compilers, computer networks, artificial intelligence, image processing, computer vision, natural language processing, etc. The subject enables the students to formulate problems precisely, solve the problems, apply formal proof techniques and explain their reasoning clearly.
Intended audience: The course is intended for any student from the computer science discipline
Lectures
Week 1 Propositional Logic
- Introduction to Mathematical Logic
- Logical Equivalence
- SAT Problem
- Rules of Inference
- Resolution
- Tutorial 1: Part I
- Tutorial 1: Part II
Week 2 Predicate Logic, Proof Strategies and Induction
- Predicate Logic
- Rules of Inferences in Predicate Logic
- Proof Strategies I
- Proof Strategies II
- Induction
- Tutorial 2: Part I
- Tutorial 2: Part II
Week 3 Sets and Relations
- Sets
- Relations
- Operations on Relations
- Transitive Closure of Relations
- Warshall’s Algorithm for Computing Transitive Closure
- Tutorial 3
Week 4 Equivalence Relations, Partitions, Partial Orderings and Functions
- Equivalence Relation
- Equivalence Relations and Partitions
- Partial Ordering
- Functions
- Tutorial 4: Part I
- Tutorial 4: Part II
Week 5 Theory of Countability
- Countable and Uncountable Sets
- Examples of Countably Infinite Sets
- Cantor’s Diagonalization Argument
- Uncomputable Functions
- Tutorial 5
Week 6 Combinatorics Part I
- Basic Rules of Counting
- Permutation and Combination
- Counting Using Recurrence Equations
- Solving Linear Homogeneous Recurrence Equations – Part I
- Solving Linear Homogeneous Recurrence Equations – Part II
- Tutorial 6: Part I
- Tutorial 6: Part II
Week 7 Combinatorics Part II
- Solving Linear Non-Homogeneous Recurrence Equations
- Catalan Numbers
- Catalan Numbers – Derivation of Closed Form Formula
- Counting Using Principle of Inclusion-Exclusion
- Tutorial 7
Week 8 Graph Theory Part I
- Graph Theory Basics
- Matching
- Proof of Hall’s Marriage Theorem
- Various Operations on Graphs
- Vertex and Edge Connectivity
- Tutorial 8
Week 9 Graph Theory Part II
- Euler Path and Euler Circuit
- Hamiltonian Circuit
- Vertex and Edge Coloring
- Tutorial 9: Part I
- Tutorial 9: Part II
Week 10 Number theory
- Modular Arithmetic
- Prime Numbers and GCD
- Properties of GCD and Bézout’s Theorem
- Linear Congruence Equations and Chinese Remainder Theorem
- Uniqueness Proof of the CRT
- Fermat’s Little Theorem, Primality Testing and Carmichael Numbers
Week 11 Abstract Algebra : Part I
- Group Theory
- Cyclic Groups
- Subgroups
- Discrete Logarithm and Cryptographic Applications
- More Applications of Groups
Week 12 Abstract Algebra : Part II
Syllabus and materials
At NPTEL, as the course publishes them.
Credits and licence
- Institution
- IIIT Bangalore
- Department
- Computer Science and Engineering
- Teacher
- Prof. Ashish Choudhury
- 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 IISc Bangalore.
- Who can watch
- NPTEL gives no rating. Invisible Network shows it to Tweens profiles and older, judged from what the source says about it. How courses are placed
More like this
NPTEL106101163
Course
Software Testing
57 lectures · Source's player
NPTEL106106221
Course
Foundations of Cryptography, IIIT Bangalore
66 lectures · Video
NPTEL117106149
Course
Design and Analysis of VLSI Subsystems
95 lectures · Video
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
Computational Science and Engineering I
50 lectures · Video
Course
Engineering Dynamics
223 lectures · Video
Course
Matrix Methods in Data Analysis, Signal Processing, and Machine Learning
34 lectures · Video
Course
Computational Science and Engineering I
50 lectures · Video
Course
Engineering Dynamics
223 lectures · Video