Topics for the Final Exam:
==========================

From Test 1 (note, all of cardinality is included):
---------------------------------------------------
Logic:
	- Proving logical formulas are equivalent: both by truth tables and logical equivalences
	- Translating from English to logic, and logic to English
	- De Morgan's law for negation
	- Quantifiers, negation
	- Translating to and from English with quantifiers and negation of quantifiers
	- Boolean functions
	- Use rules of inference

Proofs:
	- Direct proof
	- Contradiction, contrapositive
	- Proof by cases
	- Prove a collection of statements are equivalent
	- Know how to prove things rigorously
	- Know how to disprove statements (e.g., counterexample)

Sets:
	- Set operations: union, intersection, complement, set minus, cartesian product (tuples), power set
	- Set relations: element of, subset of, equality
	- Know how to prove two sets are the same
	- De Morgan's law for sets
	- Notation for unions and intersections of sequences of sets
	- Cardinality (finite, countable, uncountable)

Functions:
	- Definition of a function: domain, codomain, and the mapping
	- Injection, Surjection, Bijection - you should be able to prove or disprove a function is any of these, and give examples
	- Function composition, inverse

Sequences and Series (Summations):
	- Find formulas that generate a sequence by looking for a pattern
	- Know the geometric series and arithmetic series
	- Index substitution


From Test 2:
------------
Induction:
	- Be able to perform inductive proofs
	- Know the difference between weak and strong induction

Recursive Definitions:
	- Know how to recursively define: a set, a function, a sequence, and know the difference between these three
	- Prove recursive definitions are true using induction
	- Fibonacci numbers, towers of Hanoi

Number Theory:
	- Definition of mod, divides
	- GCD, LCM, relatively prime
	- Definition of prime, prime factorization
	- Euclidean Algorithm
	- Modular Inverses: when do they exist, and how do we find them
	- Solve linear congruences
	- RSA: understand why it works, and how to use the algorithm with reasonable numbers

Combinatorics:
	- Combinations, permutations, repetition, no repetition: definitions, when to use them, formulas
	- Counting functions from one set to another
	- Word problems
	- Binomial coefficients and the binomial theorem


New material:
-------------

Probability:
	- Definition: a sample space, probability distribution over that sample space, random variables
	- Expected value and variance, rules about linearity
	- The basic distributions covered in class
	- Conditional probability
	- Independence of events, random variables
	- Finding probabilities by counting

Graphs (extra credit):
	- Definition of undirected and directed graphs; G=(V,E) with E being unordered or ordered vertex pairs
	- Basic definitions: adjacent, degree, paths, connected
	- Storage: Adjacency lists, adjacency matrix; handshaking lemma
	- Trees, rooted trees
	- Induction on trees and graphs
	- Planar graphs: definition, non-planar graph examples, Euler's formula