Stuff You Already Know
This page lists several basic mathematical concepts, data types, data structures, and algorithms that are typically covered in CS 173, CS 225, and earlier courses, with pointers to the corresponding Wikipedia entries. We assume you are already familiar with all of them. You can use any of these in your homework or exam solutions without providing further details or citing any source.
For a detailed review of any of these topics, we strongly recommend using an actual textbook or one of the following online resources. (Beware that Wikipedia occasionally makes some very strange choices.)
Because familiarity with these topics is crucial for success in 374, we are strictly enforcing the prerequisites CS 173 (or Math 213) and CS 225. Students who do not already have credit for these courses—either directly, by proficiency exam, or by transfer from another institution—before the semester begins will be dropped.
Discrete Mathematics

Elementary algebra

Logarithm identities

Naive set theory

Binary relations, including functions, equivalence relations, and partial orders

Modular arithmetic

Asymptotic notation (o, O, Θ, Ω, ω); comparing asymptotic growth rates

Evaluating simple summations (at least asymptotically)

Propositional logic (T, F, ¬, ∧, ∨, ⇒, ⇔) and firstorder 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
 scalars
(booleans,
characters,
integers, reals, etc.)
 records
 pointers / references
 strings —
w[i]
 arrays / vectors (indexed sequences) —
A[i]
 stacks (LIFO lists)
—
push
, pop
 queues (FIFO lists)
—
push
, pull
 deques (doubleended queues)
—
push
, shove
, pop
, pull
 priority queues
—
insert
, findmin
, extractmin
, decreasekey
 dictionaries
—
insert
, delete
, find
 ordered dictionaries
—
insert
, delete
, find
, pred
, succ
 graphs (directed and undirected)
Elementary 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.
Elementary 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. We only care about worstcase running times in this class.
 Imperative programming idioms: conditionals (
if
, else
), iteration (for
, while
, repeat
...until
), structures, array indexing, indirection (record➔field
), subroutines, scope, callbyvalue versus callbyreference, recursion
 elementary arithmetic à la AlKhwarizmi and Fibonacci
 sequential search
 binary search
 comparisonbased sorting:
 radix sort: O(nw) time
 binary tree traversal: preorder, postorder, inorder, levelorder
 depthfirst search (at least for rooted trees)
 breadthfirst search (at least for rooted trees)