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.
• 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

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

Solving Recurrence

For the full notes and examples, revisit Chapter 7: 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

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 $P^n = n!$, $P^{n}_{r} = \frac{n!}{(n-r)!}$
    • circular $(n-1)!$, $C^n_r \times (r-1)!$
    • with repetition $n^r$
    • multisets (know it exists)
  • Combination
    • Take permutation and then apply division rule to correct overcounting (know how)
    • $C^{n}_{m} = \frac{n!}{(n-m)!m!}$
    • allow repetition $C^{n+r-1}_{r}$ (know it exists)
    • number of all subsets $2^n$
  • Partition
    • n identical items to r distinct bins
      • Star and bar method
      • $C^{n+r-1}_{r-1}$
    • n distinct items to r distinct bins
      • $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

Greedy Algorithm

For the full notes on these case studies, revisit Chapter 9: Greedy Algorithms.

• 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 $\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

Cross-Module Concepts

• Relationship between algorithms
  • A paradigm’s fit depends on the problem structure and required output.
  • Exact vs approximate is a separate property from the requested output.
  • There is no universal runtime ranking among paradigms; compare algorithms for the same problem using their assumptions and complexity.
• Problem types and algorithms to solve them
  • Search, enumeration, optimization, decision, and counting specify the requested output; they are not one-to-one matches with paradigms.
  • Brute force and backtracking can implement search or enumeration, and can be adapted for decision, counting, or optimization.
  • Divide and conquer, dynamic programming, greedy, branch and bound, and other paradigms apply when their structural requirements fit the problem. For example, DP may compute an optimum, a count, or a Boolean answer; branch and bound is commonly used for exact optimization.
  • Enumeration can derive search, decision, counting, or optimization answers by processing all solutions, but may do more work than needed.
• Best algorithm (covered so far) for certain problem
  • TSP
  • Bin packing
  • Huffman coding