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 on how to present or even define certain topics.)

• CS 173:
  • Building Blocks for Theoretical Computer Science by Margaret Fleck, written specifically for CS 173.
  • Mathematics for Computer Science [author pdf] by Eric Lehman, Tom Leighton, and Albert Meyer, written for the Mathematics for Computer Science course at MIT.
• CS 225:
  • Open Data Structures by Pat Morin
  • A First Course on Data Structures in Python by Don Sheehy

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 before the semester begins—either directly, by proficiency exam, or by transfer from another institution—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 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's notes on induction
• Recurrences
  • Solving divide-and-conquer recurrences via recursion trees (or the Master Theorem, if you insist)
  • Jeff'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 — w[i]
• arrays / vectors (indexed sequences) — A[i]
• stacks (LIFO lists) — push, pop
• queues (FIFO lists) — push, pull
• deques (double-ended 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; do not regurgitate the original data structure details.

• binary numbers, including 2's complement representation of negative integers
• arrays (contiguous blocks of memory)
• linked lists (singly and doubly linked, linear and circular)
• hash tables, including approrpriate skepticism about doing everything in O(1) time, especially in Python
• binary trees: worst-case depth O(n)
• binary heaps
• binary search trees
• balanced search trees: worst-case depth O(log n)
  • At least one variant of the following: B-trees (such as 2-3-trees or (a,b)-trees), AVL trees,WAVL/crumple trees, red-black trees, skip lists, treaps, splay trees
• adjacency matrices
• adjacency lists
• The difference between this list and the previous list

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; do not regurgitate the original algorithm details. We only care about worst-case running times in this class.

• Imperative programming idioms: conditionals (if, else), iteration (for, while, repeat...until), structures, array indexing, indirection (record.field), subroutines, scope, call-by-value versus call-by-reference, recursion
• elementary arithmetic à la Al-Khwarizmi and Fibonacci
• sequential search
• binary search
• comparison-based sorting:
  • insertion sort, selection sort, (standard) quicksort: O(n²) time
  • mergesort, heapsort: O(n log n) time
• radix sort: O(nw) time
• binary tree traversal: pre-order, post-order, in-order, level-order
• depth-first search (at least for rooted trees)
• breadth-first search (at least for rooted trees)