Discrete Math (CS201)
The course introduces the necessary mathematics knowledge for computer science. The scope spreads widely and therefore, it might not dive in too much. Don't let the flood of concepts and proofs scare you. The best way to learn discrete math is to read the slides carefully and know the steps to solve the homework by heart.
About
- Instructor:
Shan CHEN (陈杉) - Semester:
2023 Fall - Textbook:
Discrete Mathematics and Its Applications
| Chapter | Content | Note |
|---|---|---|
| Logic and Proofs | Propositional Logic Predicate Logic Proof and Logic Equivalence |
Most Abstract Part Follow the Logic |
| Sets and Functions | Sets and Cardinality Function Sequence and Summation Countability of Sets |
Proof Matters |
| Complexity of Algorithms | Growth Complexity P, NP, NPC and NP Hard |
Concepts and Analysis of Algorithm |
| Number Theory and Cryptography | Divisibility and Modular Prime and (extended) GCD Congruence and Invert Chinese Remainder Theorem Euler's Theorem Fermat's Little Theorem RSA and DH Key Exchange |
Hardest Part Computing and Proofs of the Theorem |
| Induction and Recursion | Mathematical Induction Recurrences Master Theorem Divide and Conquer |
Proof by Induction Expand Recusive Expression |
| Counting | Basic Rules Binomial Coefficients and Identities Inclusion and Exclusion Linear Recurrence Equation Generating Functions |
Calculation Matters |
| Relation | Properties Closure \(n\)-ary Relation Ordering and Comparability |
Proof Matters |
| Graph and Trees | Basic Concepts and Properties Representation and Isomorphism Connectivity Euler and Hamilton Paths Planar Coloring Shortest Path Trees and MST |
The most useful part Similar to the content of DSAA (CS 203) |
Project
Exam
Well, professor Chen won't leak any exam questions, however, the exam comes mostly from the homework and the slides. If you'd like to do some exam questions, refer to wLUOw's repo