This page lists several basic mathematical concepts, data types, data structures, and algorithms with links to coresponding Wikipedia pages. Almost all of these topics are covered in CS 173 and CS 225, our undergraduate discrete mathematics and data structures classes. We assume that everyone taking CS 573 is already familiar with
everything on this 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 some
very strange choices.)
Mathematics
For a solid introduction to most of these topics, I strongly recommend Eric Lehman and Tom Leighton's extensive
lecture notes for the
Mathematics for Computer Science course at MIT.
-
Elementary algebra
-
Logarithm identities
-
Naive set theory
-
Binary relations, including functions, equivalence relations, and partial orders
-
Modular arithmetic
- Elementary discrete probability: Uniform vs. nonuniform distributions, expectation, 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
-
Recurrences
-
Graphs (both undirected and directed),
trees,
directed acyclic graphs
Abstract data types
Data structures
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.
Algorithms
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.