Course outline

• Counting
  • 6.1 - Counting and probability
  • 6.2 - Possibility Trees and the Multiplication Rule
  • 5.1 - Basic definition of set theory; 5.2 Properties of sets
  • 6.3 - Counting Elements of disjoint sets: The Addition Rule
  • 6.4 - Counting Subsets of a set: Combinations
  • 6.5 - r-Combinations with Repetition allowed
  • Birthday problem and Stirling's approximation
  • Number of subsets of a set, Binomial theorem
• Induction and Recursion
  • 4.1 - Sequences
  • 4.2 - Mathematical Induction I
  • 4.3 - Mathematical Induction II
  • 4.4 - Strong Mathematical Induction and the Well-Ordering Principle
  • General form of Inclusion/Exclusion, Derangements
  • 8.1 - Recursively defined sequences
  • 8.2 - Solving recurrence relations by Iteration
  • 8.3 - Second-Order Linear Homogeneous Recurrence Relations with Constant Coefficients
• Functions and O-notation
  • 7.1 - Functions defined on General sets
  • 7.3 - One-to-One and Onto, Inverse functions
  • 7.4 - Application: The Pigeonhole Principle
  • 7.5 - Composition of functions
  • 9.1 - Real-valued functions of a real variable and their graphs
  • 9.2 - O-notation
  • 9.3 - Application: Efficiency of Algorithms I. Sequencial search, insertion sort
  • 9.4 - Exponential and logarithmic functions: graphs and orders
  • 9.5 - Application: Efficiency of Algorithms II. Binary search, merge sort
• Graphs and Finite State Automata
  • 12.2 - Finite state automata
  • 11.1 - Graphs, degree
  • 11.2 - Paths, circuits. Connectedness. Euler circuits
  • 11.2 - Euler circuits. Hamiltonian circuits. Euler's formula
  • 11.3 - Counting paths. Adjacency matrix.
• Error-correcting codes
  • Codewords, Hamming distance. Hamming 4-7 code
  • More Hamming codes, t-error correcting codes
  • Check sum for ISBN, American banking system, barcodes