IV - Discrete Mathematics & Algorithms

Jump to Topic

Discrete mathematics and algorithms bring together key topics from both mathematics and computer science that are essential for modern computational methods. Discrete mathematics, as a distinct branch of mathematics, explores well-defined structures—like graphs, sets, and combinatorial systems—that support clear logical reasoning and analysis. In parallel, the study of algorithms, central to computer science, focuses on designing systematic procedures for solving complex problems efficiently. This section unites these interrelated areas, reflecting their synergy in advancing machine learning. This section will cover core topics including graph theory, combinatorics, the theory of computation and more. Whether you are interested in the abstract reasoning of mathematics or the practical implementation of efficient algorithms, blending theoretical insights with practical algorithm design gives you a comprehensive foundation for analyzing and optimizing computational processes.

\(G = (V, E)\)

Part 1: Intro to Graph Theory

Undirected graph Directed graph Multigraph Weighted graph Complete graph Adjacent Degree of a vertex \(k\)-regular Isomorphism
\( {}_n C_r \)

Part 2: Intro to Combinatorics

Fundamental counting principle Combination Binomial coefficient Multinomial coefficient Pascal's relation Chu's theorem Sum of powers of positive integers Permutation
\(M\)

Part 3: Intro to Theory of Computation

Finite automata Regular language State diagram Deterministic finite automata (DFAs) Nondeterministic finite automata (NFAs) Regular expression
0 ∧ 1

Part 4: Boolean Logic

Logical operations Boolean algebra Circuits
S →

Part 5: Context-Free Languages

Context-free grammars Nonregular language Pumping lemma Pushdown automata Deterministic pushdown automata (DPDAs) Deterministic context-free languages (DCFLs)
TM

Part 6: Turing Machines

Turing machine Turing-recognizable Decidability Computability Church-Turing thesis Unsolvability Undecidable problems
\(O (g(n))\)

Part 7: Time Complexity

Time complexity(Running time) Asymptotic analysis Big-O notation Little-o notation: Time complexity class Class P
\(C_n\)

Part 8: Eulerian & Hamiltonian

Eulerian Eulerian cycle (Euler tour) Eulerian path (Eulerian trail) Hamiltonian Hamiltonian cycle Adjacency matrix< Adjacency list Space complexity
\(P \neq NP\) ?

Part 9: Class NP

Polynomial verifiability Nondeterministic polynomial time NP-completeness NP-hard Polynomial-time reduction P vs NP question