This page lists several basic mathematical concepts, data types, data
structures, algorithms, and complexity with links to coresponding
Wikipedia pages. Almost all of these topics are covered in CS 173 and
CS 225, and CS 373 our undergraduate discrete mathematics, data
structures and theory of computation classes. We assume that everyone
taking CS 573 is already familiar with everything
list, or at least has the intellectual maturity to learn it on the
fly. (We recommend using an actual textbook to learn any of these
concepts for the first time; the Wikipedia Cloud makes
For a solid introduction to most of these topics, I strongly recommend
Eric Lehman and Tom Leighton's
for Computer Science
course at MIT.
Naive set theory
Binary relations, including functions, equivalence relations, and partial orders
- Elementary discrete probability: Uniform vs. nonuniform distributions, expectation, variance, conditional probability
Asymptotic notation (o, O, Θ, Ω, ω); comparing asymptotic growth rates
Evaluating simple summations (at least asymptotically)
Propositional logic (T, F, ¬, ∧, ∨, ⇒, ⇔) and first-order predicate logic (∀, ∃)
Basic proof techniques: direct, indirect, exhaustive case analysis, contradiction
★ Induction ★ (or equivalently, proof by minimal counterexample), especially strong induction and structural induction
Graphs (both undirected and directed),
directed acyclic graphs
Abstract data types
You may use any of these data structures in your homeworks and exams without providing further details or citing any source. If you use a small modification of one of these data structures, just describe your changes; don't
regurgitate the original data structure details.
You may use any of these algorithms in your homeworks and exams without providing further details or citing any source. If you use a small modification of one of these algorithms, just describe your changes; don't
regurgitate the original algorithm details.
Theory of Computation/Complexity
It is useful to have some basic background in theory of computation.