I. The Basics (HW0)

Functions
	domain, range
	one-to-one, onto, bijective
		Know what these terms mean.
	inverses
		Know when a function is invertible.  Make sure you only 
talk about the inverse of a function when the function actually is 
invertible.

Proof
	by contradiction
	induction (weak/strong)
		Know the difference between weak and strong induction.  
Realize, that you can always use a weak inductive proof under the strong 
inductive hypothesis.

II. Discrete Math (HW1, HW2, Midterm I)

Probability
	random walks (on grid maps, on lines, etc.)
		This also shows up in combinatorics.  Know how to figure 
out the probability that you'll reach one end or the other of a line, 
using a random walk.
	drunken sailors
		The famous drunken sailors problem - drunken sailors with 
or without specific rooms who may or may not object to rooming with other 
drunken sailors.
	expected values
		Know how to calculate them.
	random variables, indicator variables
		Know how indicator variables can save you a lot of 
calculation.  I.e., the expected value of an indicator variable is simply 
the probability that the indicator variable is true.  Independent 
indicator variables are your friend.
	independence, Bayes rule, joint probabilities
		Know what Bayes rule says, and what two probabilities 
being independent means, and what that says about the joint probabilities.

Combinatorics
	combinations, permutations
	counting
		Know how to count both permutations, combinations, and 
whatever else we can think of to throw at you.
	combinatoric arguments
		Know how to make one.  I believe the classic example is 
the subcommitte problem.

II. The Next Bit (HW3, HW4, Midterm II)

Graphs
	bipartite, k-color
		Know what the properties of a bipartite or k-color graph 
is.  Know how to prove other properties of a graph given that a graph is 
bipartite, and vice versa.
	Petersen graphs
	decomposition, subgraphs
		Know what a graph decomposition is.  And what subgraphs 
are.
	planar, Euler's formula
		Be able to handle all those planar problem we've gone over 
previously.  Be able to prove things using Euler's formula.  Know what a 
planar graph is.
	Cayley's theorem, Prufer codes
	walk, path, cycle
	weighed, directed/undirected
	automorphisms, homomorphisms
		Know what automorphisms and homomorphisms are.  Know how 
to count how many there are.  Know what they do to graphs.

Recurrences
	annihilators, substitution
	tree method, Master theorem
		Be able to solve any recurrence problem with the 
appropriate usage of any of the above techniques.  Make sure you can find 
the things below using those techniques.
	upper/lower bounds
	exact solutions, base cases

III. The Final Bit

Automatons
	DFAs <-> NFAs <-> REs
		Know how to convert between the three.  Be able to prove 
that they are equivalent.  Know how to construct an appropriate 
machine/expression to recognize a given language.
	Turing machines
		Know how to construct a Turing machine to recognize a 
given language.
	computability
		Know how to make computability arguments.  The halting 
problem, and Turing machine equivalence are classics.

Groups
	groups, subgroups
		Know what a subgroup is, and which properties you have to 
prove that a subgroup has, and which ones you can simply assume the 
subgroup inherits.
	cyclic groups, generators
		Know what a generator is, and how it generators a 
subgroup.  It's g^0, g^1, g^2, g^3, ..., g^(n - 1), and not g * 0, g * 1, 
g * 2, etc.
	abelian
		Know that's it's spelled abelian, and pronounced 
commutative.
	closure, identity, inverse, associativity
		Know what these properties are.
	additive groups
	permutation groups
		Know what a permutation group is, how to prove things with 
one, and how things we prove about permutation groups apply to 
automorphisms and homomorphisms back in the graph bits.