CS 573: Stuff You Already Know

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 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, 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

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.

• 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

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.

• 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

It is useful to have some basic background in theory of computation.

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

---