CS 473: Stuff You Already Know

This page lists several basic mathematical concepts, data types, data structures, and algorithms that are typically covered in CS 173 and CS 225, and covered in more detail in CS 374, with pointers to the corresponding Wikipedia entries. We assume that everyone taking CS 473 is already familiar with everything on this list, or at least has the intellectual maturity to learn it on the fly. You can use any of these in your homework or exam solutions without providing further details or citing any source.

For 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.)

• Building Blocks for Theoretical Computer Science by Margaret Fleck, written specifically for CS 173.
• Mathematics for Computer Science by Eric Lehman, Tom Leighton, and Albert Meyer, written for the Mathematics for Computer Science course at MIT.
• Open Data Structures by Pat Morin, an open-content textbook (like open source, but for words) that really ought to be the standard reference for CS 225.
• Jeff's algorithms lecture notes

Mathematics

• 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, 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
  • Jeff Erickson's notes on induction
• Recurrences
  • Solving divide-and-conquer recurrences via recursion trees (or at least the Master Theorem)
  • Solving linear recurrences via annihilators (or characteristic polynomials, or generating functions, or...)
  • Jeff Erickson's notes on solving recurrences
• Graphs (both undirected and directed), trees, directed acyclic graphs

---

Abstract data types

• scalars (booleans, characters, integers, reals, etc.)
• records
• pointers / references
• strings
• arrays / vectors (indexed sequences)
• stacks (LIFO lists)
• queues (FIFO lists)
• deques (double-ended queues)
• priority queues
• dictionaries
• graphs (directed and undirected)

---

Data structures

• binary numbers, including 2's complement representation of negative integers
• arrays
• linked lists (single and double, linear and circular)
• hash tables
• binary trees: worst-case depth is O(n)
• binary heaps
• binary search trees
• balanced search trees: worst-case depth is O(log n)
  • At least one of the following: B-trees (such as 2-3-trees or (a,b)-trees), AVL trees, red-black trees, splay trees, treaps, skip lists
• adjacency matrices
• adjacency lists
• The difference between this list and the previous list

---

Algorithms

• elementary arithmetic á la Al-Kwarizmi
• sequential search
• binary search
• comparison-based sorting:
  • insertion sort, selection sort, (standard) quicksort: worst-case time is O(n²)
  • mergesort, heapsort: worst-case time is O(n log n)
• radix sort
• binary tree traversal: pre-order, post-order, in-order, level-order
• depth-first search
• breadth-first search
• topological sorting
• Dijkstra's shortest-path algorithm

---

Theory of Computation/Complexity

• Finite automata: DFAs and NFAs
• Context-free grammars
• Turing Machine
• Undecidability
• Non-determinism
• Common time complexity classes, in particular P and NP