# CPSC 411 Design and Analysis of Algorithms Review for Midterm Exam Andreas Klappenecker 1 Topics Covered

Finding Primes in the Digits of Euler's Number Asymptotic Notations: Big Oh, Big Omega, Big Theta Time complexity of Insertion Sort Lower bounds for sorting Divide-and-Conquer Algorithms

Mergesort Strassen's method for Matrix Multiplication Greedy Algorithms, Huffman codes Greedy Algorithms for Matroids Matroid Embeddings Dynamic Programming, Matrix Chain Multiplication Dynamic Programming, Longest Common Subsequence Amortized Analysis Disjoint Sets 2 Asymptotic Notations O(g) = { f:N->R | there exists an

integer n0 and a real constant C such that |f(n)| <= C|g(n)| for all n>= n0 } (g) = { f:N->R | there exists an integer n0 and a real constant c such that |f(n)| => c|g(n)| for all n>= n0 } 3 Asymptotic Notation (n2+n+6) = O(n2)

6n2 = O(n2) 10765432n2+2n+7 = (n2) (n2+n+6) = (n2) (g) = (g) O(g) (n2+n+6) = (n2) 4 Sorting Insertion Sort Best case running time: linear Worst case running time: quadratic Merge Sort O(n log n)

Any comparison based sorting (n log n) 5 Divide-and-Conquer Mergesort Quicksort Strassens matrix multiplication algorithm Recurrence relations Master theorem (no need to memorize)

6 Greedy Algorithms Coin change Huffman codes Matroids Kruskals algorithm Matroid embeddings Prims algorithm 7 Dynamic Programming

Matrix chain multiplication Longest common subsequences Variations: Edit distance 8 Amortized Analysis Aggregate Analysis Accounting Method Stacks Counter Disjoint Sets

9 Exam Some short questions Some workout problems Lectures Slides

Textbook Quizzes Homework 10