****************
Midterm 2 Review
****************
How to use this document
========================
+ Only contains the topics covered after midterm 1
+ Self-test using this document to see what concepts are challenging to you.
+ The slides are the most concise and focused document you can start with.
+ Course content website is the systematic view for tips, pitfalls.
+ Practice your ability to work on an algorithm on paper. Play with the
  visualization website to see how the algorithm works step by step.
+ Refer to the practice exam for the format of the exam and the types of
  questions.
+ Refer to the test exam for how the Honorlock will work.


Type of Questions
=================
+ True/False (TF)
+ Multiple Choice (MC)
+ Fill in the Blank (FIB)
+ Matching (MAT) - match a list of items to another list of items
+ Short Answer/Coding (SA)

Topics
======
Solving Recurrence
------------------
+ Recurrence relation

  * Definition
  * General form: a, b, f(n), T(n) meanings and constraints
  * Difference from closed form
  * Three example forms

    - divide and conquer
    - linear (first order)
    - linear (second order)

+ Solving recurrence

  * Substitution method

    - guess the form of the solution
    - prove by induction
    - details not needed

  * Recursion tree method

    - conversion from/to recurrence relation
    - estimate complexity (compute the total)

  * Master theorem

    - three cases
    - **know the calculation** from the recurrence relation

Greedy Algorithm
----------------
+ Definition
+ Type of problem it can solve: **optimization problem**
+ Characteristics

  * **local optima**
  * greedy choice
  * **no looking back**
  * less complex
  * intuitive
  * **approximate** algorithm

+ Compare to backtracking and brute force
+ Bin packing

  * NP-hard problem
  * Brute-force baseline :math:`\Theta (n!)`
  * Types

    - online
    - offline

      + pre-sorting (descending order of item size) in constructor

  * Heuristics

    - next fit (online only)
    - first fit
    - best fit
    - comparison

      + Most intuitive
      + Best result

  * **Able to code the process**

+ Huffman Coding

  * Data compression using variable length encoding
  * Strategy: encode frequent symbols with short codewords
  * Prefix code (no codeword is a prefix of another codeword)
  * Optimal code (overall length is minimized)
  * Prefix code tree

    - leaf nodes: symbols
    - internal nodes: prefixes
    - path from root to leaf: codeword

  * Greedy algorithm to build the tree

    - build a min priority queue of frequencies
    - **able to reproduce** from a given characters and frequencies

Combinatorics and Counting
--------------------------
+ Principles

  * Sum rule - mutually exclusive choices in one events
  * Product rule - independent events
  * Division rule - correct consistent overcounting
  * Inclusion-exclusion principle

    - two sets

  * Pigeonhole principle

+ Predefined problems and formulas

  * Permutation

    - inferred from product rule
    - standard :math:`P^n = n!`, :math:`P^{n}_{r} = \frac{n!}{(n-r)!}`
    - circular :math:`(n-1)!`, :math:`C^n_r \times (r-1)!`
    - with repetition :math:`n^r`
    - multisets (know it exists)

  * Combination

    - Take permutation and then apply division rule to correct overcounting
      (know how)
    - :math:`C^{n}_{m} = \frac{n!}{(n-m)!m!}`
    - allow repetition :math:`C^{n+r-1}_{r}` (know it exists)
    - number of all subsets :math:`2^n`

  * Partition

    - n identical items to r distinct bins

      + Star and bar method
      + :math:`C^{n+r-1}_{r-1}`

    - n distinct items to r distinct bins

      + :math:`r^n`

    - integer partition (know it exists)

  * **Know all the symbols and their meanings**
  * **Able to map a problem to a type of problem and then apply the formula**

+ Strategies

  * direct counting
  * cases combined by sum/product rule
  * counting by complement
  * count by recursion

+ Examples

  * Employ all examples to understand the principles and strategies
  * **Able to calculate** examples with changed parameters (exclude poker game
    examples)
  * Know the rank of hands in poker game
  * Know how the formulas are derived

Divide and Conquer
==================
+ Definition
+ Three stages
+ Pro and con

  * understand why

+ Applications

  * Know how three stages are implemented

+ Time complexity

  * know the recurrence relation of typical algorithms
  * use master theorem to solve them

Cross-Module Concepts
=====================
+ Relationship between algorithms

  * Different types of problem to solve
  * Exact vs approximate
  * Complexity (efficiency)

    - Greedy < Divide and conquer, backtracking < Brute force

+ Problem types and algorithms to solve them

  * find one solution (search)

    - brute force
    - backtracking
    - divide and conquer

  * find all solutions (enumeration)

    - brute force
    - backtracking

  * find best solution (optimization)

    - greedy
    - divide and conquer
    - genetic algorithm
    - all find all methods

+ Best algorithm (covered so far) for certain problem

  * TSP
  * Bin packing
  * Huffman coding
  * Max sum subarray