Midterm 1 Review

How to use this document

• 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

Environment

• Know the toolchain: g++, make, git
• Windows environment: WSL only! No MinGW!
• Building process of modular programs
  • Three steps: preprocessing, compilation, linking
  • Multi-step compilation:
    1. Preprocessing + compilation: g++ -c
    2. Linking: g++ without -c
  • Makefile (basics only)
    • Write a simple rule with three parts: target, dependencies, recipe/commands
    • clean target
    • Triggering rules make <target>, make, make <target list>
      • first target is default
• Code organization
  • Header: public declarations of functions, classes, global variables
  • Source/cpp: everything else
    • Private declarations
    • Definitions
• Conventions in this class
  • Naming, casing: camelCase for functions and variables, PascalCase for classes and structs, all lowercase for file names
  • File extensions: hpp, cpp
  • Documentation and comments
• git
  • clone, add, commit, push, status

Math

• Exponent: know the definition
• Logarithm: know the definition, $log(n)$ is less complex than $n$
• Modulus: know the definition, applications in random number generation and hash table
• Proof methods:
  • Direct proof
  • Proof by contradiction
  • Proof by induction
  • Proof by contrapositive

Algorithm Analysis

• Definition
• Two types: empirical and theoretical
• Asymptotic definitions
  • Big-O notation: definition, upper bound
  • Big-Omega notation: definition, lower bound
  • Big-Theta notation: definition, exact bound Most Important
• Best/worst/average cases
  • Each defines a function on the input size n
  • Each has its own upper, lower, and exact bounds
• Estimate Exact Bound Big-Theta
  • know big theta for common structures

Amortized Analysis

• Definition
• Motivation

Tree

For explanations and examples, revisit Chapter 3: Tree Revisit; AVL Tree.

• Definitions: computer science vs graph theory; recursive
• Concepts
  • root, leaf, internal nodes
  • parent, child, sibling, ancestor, descendant
  • path, length of path, depth of nodes, level of nodes, height of tree
  • degree of node, degree of tree
  • Able to find and different on a tree diagram
• Characteristics
  • ordered vs unordered
• Behaviors
  • traversal: definitions of preorder, inorder (discussed with binary tree), postorder, level-order
  • search: definitions of depth-first search, breadth-first search
  • insertion: discussed in BST
  • deletion: discussed in BST
• Implementation
  • variable number of children
  • first child, next sibling

Binary Tree

• Definition: degree 2 ordered tree
• Three special types
  • full binary tree
  • complete binary tree
  • perfect binary tree
• Applications

Binary Search Tree

• Definition of search tree
• Behaviors: know the details on how they work on paper
  • search
  • insertion: always at leaf
  • deletion: three cases, how successor/predecessor is used
• Analysis
  • determined by tree height
  • ideal tree height: $\Theta(\log n)$
  • worst case tree height: $\Theta(n)$
  • degradation of efficiency: unbalance tree or even a list

Self-balancing

• Motivation: avoid degradation of efficiency
• Definition: height-balanced automatically

AVL Tree

• Balance factor: $BF = h_l - h_r$, know how to calculate on diagram
• Balance condition: $BF \in \{-1, 0, 1\}$
• Self-balancing
  • triggered: insertion/deletion causes balance factor to be +2/-2
  • recursively check balance factor and rotate from bottom up
• Imbalance and rotation types
  • LL imbalance - right rotation
  • RR imbalance - left rotation
  • LR imbalance - left-right double rotation
  • RL imbalance - right-left double rotation
• Hints and Pitfalls
  • -1 for nullptr as a subtree height
  • Positive BF means left subtree is taller; negative BF means right subtree is taller

B-Tree

• Balanced tree
  • All leaves are at the same level
• N-ary search tree
• Application:
  • index in file system and database
• Always balanced
• Behaviors
  • search
  • insertion
    • always at leaf
    • adjustment when full
      • split and promote middle key
      • check full recursively from bottom up to root
  • deletion
    • internal or leaf node
    • how successor/predecessor is used when deleting from internal node
    • adjustment when underflow
      • borrow from sibling
      • merge with sibling

B+ Tree

• Difference from B-tree
  • internal nodes do not store data, it stores the duplicate keys of its predecessor or successor position in leaves
  • leaf nodes are linked together to allow sequential access
  • all data are stored in leaves
• Pro and con vs B-tree
  • sequential and range access
  • less key redistribution between internal nodes and leaves
• Application:
  • index in file system and database

Problem Classification By The Goal

• Search: find one qualifying solution (a witness)
• Enumeration: find all qualifying solutions
• Optimization: find the best solution under an objective; an approximate solution may be acceptable when explicitly allowed
• Decision: answer yes/no, often whether a qualifying solution exists
• Counting: report how many qualifying solutions exist
• Evaluation

These are output goals, not algorithmic paradigms. Full enumeration can be used to answer search, decision, counting, or optimization questions, but many algorithms answer those goals without listing every solution.

Algorithmic Classification

• By Paradigm
  • brute force know details
  • backtracking know details
  • divide and conquer know the name
  • greedy know the name
  • dynamic programming know the name
  • branch and bound (not covered)
• By data structure
  • array
  • linked list
  • tree
  • graph
• By characteristics
  • Exact vs approximate
  • Deterministic vs randomized (non deterministic)

Brute-Force

• Definition
• No optimization, pruning, or heuristic
• Exact algorithms
• Can implement search or enumeration and derive decision, counting, or optimization results by examining candidates
• Exponent or factorial time complexity

Backtracking

• Definition
• Two approaches
  • recursive: base case, recursive case, backtracking operation
  • iterative: use of stack
• Feasibility check to reject partial solutions
• Backtracking operation when partial solution is rejected
• Steps in pseudocode

Genetic Algorithm

• Inspiration from natural evolution
• Approximation algorithm
  • not guaranteed to find the optimal solution
  • can find a good solution in a reasonable amount of time
• Characteristics: brief understanding
• Concepts
  • population
  • individual and encoding - binary, integer, real-valued, permutation
  • selection - roulette wheel, tournament selection
  • fitness
  • crossover - one-point crossover, two-point crossover
  • mutation - bit flip, swap mutation
  • replacement - elitism, generational replacement, steady-state replacement
• Parameters
  • population size
  • crossover rate
  • mutation rate
  • number of generations (if not using other termination condition)
• Steps in pseudocode