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 \(\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 \(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

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