• WhatYouShouldKnowAboutMath

List of things you should know about if you want to do ComputerScience. Italicized entries are not covered in CS202.

Things you should already know about:

• High school algebra: solving equations etc.
• High school calculus: derivatives, integrals. (Not actually required but will be more useful than you think.)

Things you should learn somewhere along the way:

• Logic
  • Propositional logic: ¬, ∧, ∨, ⇒, ⇔
  • First-order logic: ∀, ∃, P(x)
  • Equality and uniqueness
• Proofs
  • Direct proofs
    • Proving P ∧ Q
    • Proving P ∨ Q
    • Proving P ⇒ Q
    • Proving P ⇔ Q
    • Proving ¬P
    • Proving statements with quantifiers: ∀x P(x), ∃x P(x)
  • Indirect proofs
  • Induction
• Mathematical structures
  • The natural numbers ℕ; Peano axioms
  • Sets
    • Membership (∈), subsets (⊆)
    • Comprehension: { x ∈ S | P(x) }
    • Unions (A∪B), intersections (A∩B), and set differences (A\B)
    • Power sets
    • Proving equality

    • Russell's Paradox, ZFC axioms

  • Relations
  • Functions
    • Injections, surjections, and bijections
    • Inverses
    • Composition
  • Orders
    • Partial orders
    • Total orders
    • Well orders

    • Ordinals and order types

• Graphs
  • Undirected graphs
  • Directed graphs
  • Subgraphs
  • Special classes of graphs
    • Paths
    • Cycles
    • Trees
    • Bipartite graphs

  • Hypergraphs

• Algebraic structures
  • Semigroups
  • Monoids
  • Groups
    • Cyclic groups
    • Products
    • Abelian groups: definition, classification of finite abelian groups
    • Homomorphisms
  • Rings
  • Fields
  • Vector spaces

  • Lattices and Boolean algebras

  • Categories

• Standard algebraic structures
  • Integers: ℤ

  • Integers mod m: ℤ_m

  • Rationals: ℚ
  • Reals: ℝ

  • Complex numbers: ℂ

• Tools for algorithm analysis
  • Inequalities
  • Asymptotic notation
  • Sums
  • Recurrences
• Combinatorics
  • Counting
  • Binomial coefficients
  • Stirling numbers
  • Generating functions

• Linear algebra¹

  • Vectors
  • Vector addition
  • Dot-product
  • Matrices and linear transformations
    • Matrix multiplication
    • Transposition
    • Inverses

    • Eigenvalues and eigenvectors

    • Complex matrices

  • Subspaces

    • Bases

    • Projections

    • Subspaces associated with matrices

• Probability
  • Probability spaces and probability axioms
  • Basic probability laws
  • Conditional probability
  • Expectation and related concepts
    • Expectation
    • Variance
    • Conditional expectation
  • Stochastic processes
    • Markov chains

    • Poisson processes

    • Martingales and stopping times

• Number theory
  • Divisibility
    • Primes and composites
    • Prime factors
    • GCD

  • Structure of ℤ_m

    • Chinese Remainder Theorem
    • Fermat's Little Theorem

    • Inverses in ℤ^*_p

    • Cryptographic primitives: RSA, Diffie-Hellman, discrete logarithm

CategoryMathNotes