Discrete Mathematics
|
Course Objectives
|
|
In this course, the mathematical foundations related to computer sciences like formal logic, set theory, mathematical induction, methods of counting, discrete probability, elementary graph theory are discussed.
|
|
Course materials
|
- Notes on Discrete Mathematics, M. A. Lerma, Northwestern University
- Discrete Mathematical Structures: Theory and Applications, D.S. Malik and M.K. Sen, Thomson.
|
|
Assessment
|
|
40% Midterm (exam,tasks,etc.) + 60% Final (exam,tasks,etc.)
|
|
Prerequisites
|
|
none
|
| Week |
Subjects |
Lecture Notes |
| 1. |
Introduction to the Course, Logic and Proofs, Propositions |
Intro slide, chapter 1 |
| 2. |
Binary Relations, POSet, Hasse Diagram, Equivalent Relation |
chapter 2 |
| 3. |
Algorithm Complexity, Modular Arithmetic, RSA |
chapter 3 |
| 4. |
Induction & Recurrence, Combinatorics & The Pigeonhole Principle |
chapter 4 & 5 |
| 5. |
Probability & Bayes Theorem, Graphs & Representations |
chapter 6 & 7 |
| 6. |
Euler Paths/Circuits, Hamilton Paths/Circuits |
chapter 7 |
| 7. |
Dijkstra's Shortest Path, Homeomorphism, Graph Coloring |
chapter 7 |
| 8. |
Midterm exam |
| 9. |
Trees, Binary Trees, Decision Trees, Complexity of Tree Algorithms |
chapter 8 |
| 10. |
Tree Isomorphism, Huffman Code, Game Trees & Pruning |
chapter 8 |
| 11. |
Transversal Algorithms, Spanning Tree Algorithms |
chapter 8 |
| 12. |
Boolean Algebras, Finite-State Machine & Automata |
chapter 9 & 10 |
| 13. |
Context Free Language & Grammar |
chapter 10 |
| 14. |
Regular Expression & Nondeterministic Finite-State Automata |
chapter 10 |
| 15. |
Review for Final exam |
chapter 1-10 |
| |
Final Exam |
|