Course info

Topics

Mathematical Logic and Proofs:

Propositional logic, operations on propositions, truth tables, Tautologies, logical equivalence, normal forms, Predicate logic, quantifiers, nested quantifiers, Inference rules, methods of proof (direct, indirect, contradiction, contraposition)

Set Theory and Functions:

Sets, set operations, Venn diagrams, Sequences, summations, cardinality of sets, Functions: injections, surjections, bijections, inverse and composition

Induction and Recursion:

Mathematical induction and strong induction, Well-ordering principle, Recursive definitions, Structural induction

Combinatorics:

Basic counting principles (addition, multiplication), Pigeonhole principle, Permutations and combinations, Binomial coefficients, Pascal’s triangle, binomial theorem, Recurrence relations: linear/nonlinear, homogeneous/inhomogeneous, Relations and properties: reflexive, symmetric, transitive, Closures of relations, equivalence relations, partial orders

Group Theory and Algebraic Structures:

Groups, semigroups, monoids, Rings, fields, vector spaces, Lattices and applications

Graph Theory:

Graph basics, types, and representations, Graph models of computation, Eulerian and Hamiltonian paths/circuits, Trees: properties, traversals, spanning trees, Graph matching, vertex/edge coloring, Chromatic number, applications, Recap of key discrete structures across topics, Integration into CS applications (algorithms, networking, cryptography)

Problem sets on the core topics.