ECS 20 Final Review Outline

• Set theory
  • set operations
  • A = B iff (A is a subset of B, and B is a subset of A)
  • finite set, cardinality, and inlusion-exclusion principles
  • power set
  • partition
• Relations
  • representations and compositions
  • types of relations: reflective, symmetric, antisymmetric, transitive
  • equivalence relation and partition
  • partial ordering relations
• Functions
  • one-to-one, onto, and invertible
  • composition
  • frequently used functions: permutation, floor and ceiling, remainder = k (mod m), exponential, logarithm
  • sequences and summations
  • recursively defined functions

• Propositional logic
  • Proposition
  • Compound propositions and truth tables:
    negation, conjunction, disjunction, and exclusive disjunction
  • Implication, bicondition and truth tables
  • Logical equivalence
  • Propositional functions
  • Universal and existential quantifications
• Proof techniques
  • Direct proof
  • Proof by contraposition
  • Proof by contradiction
  • Constructive proof
  • Proof by counterexample
  • Proof by mathematical induction

• Divisibility
• The division algorithm
• Fundamental theorem of arithmetic
• GCD
• Prime factorization based algorithm
• Euclidean algorithm
• Modular arithmetic and congruence relation

• Basic counting
  • Basic rules: the sum rule and the product rule
  • Inclusion-exclusion rule
  • Mathematical functions for counting
    • factorial function
    • binomial coefficient function
  • Permutation
  • Combination
  • The pigeonhole principles

• Recursion
  • Counting via recursion
  • Solving 1st and 2nd order homogeneous linear recurrence relations with constant coefficients
  • The binomial theroem and Pascal's triangle

• Big-O
• Big-Omega
• Big-Theta

• Notion of graphs
  • G = (V,E) basic terminology: vertex, edge, degree, adjacency, simple, ...
  • the handshaking theorem
  • representations of graphs
  • isomorphism and homeomorphism
• Special types of graphs
  • complete K_n, cycle C_n, Wheel W_n, n-cube Q_n
  • bipartite, complete bipartite K_{m,n}
  • planar graphs, Euler's formula and Kuratowski's theorem
• Connnectivity
  • path, cycle (circuit), connected graph, distance, dimeter, ...
  • Eulerian path/cycle, Euler's theorem
  • Hamiltonian path/cyle
• Trees
  • Tree = a connected and acyclic graph
  • Rooted tree, and m-ary rooted tree
  • Binary search tree

1. Homework problem sets #1 - #8 and solutions
2. Quizzes #1-#7 and solutions
3. Midterm and solution
4. Final review exercises -- to be discussed at Review Session