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

Recently Viewed Presentations

• Attempts to Return to Fixed Rates Readings BusinessWeek articles on dollar crisis "New Eurocurrency Era" "More than a supersnake" R.A.Mundell, "Gold Would Serve" Wall Street Journal articles on Baker's Plan for use of gold in price index EMS: Reasons Extreme...
• Teori Model Betty Neuman . Konsep utama yang terdapat pada model Neuman, meliputi: stresor, garis pertahanan dan perlawanan, tingkatan pencegahan, lima variabel sistem klien, struktur dasar, intervensi dan rekonstitusi (Fitzpatrick & Whall, 1989)
• A saline flush pushes the tail of the injected contrast medium bolus into the central blood volume and makes use of contrast medium that would otherwise remain unused in the injection tubing and peripheral veins. It therefore increases both the...
• In aerobatics the aircraft experiences high "G" What has stalling got to do. with these? It is vital for a pilot to understand stalling thoroughly, if he is to fly an aircraft confidently at the low speeds required for take-off...
• Distributed Systems6. Medium Access Control Sublayer. Simon Razniewski. Faculty of Computer Science. Free University of Bozen-Bolzano. A.Y. 2014/2015
• Databases are organized searchable information sources They form part of the "invisible net" - you cannot access them by google, only by rights of "membership" (subscription) Let's look at Granger's Poetry D/base On a school computer, type in webcat and...
• CAT: coelioscopie myomectomie pré FIV-ICSI elle vous montre 6 courbes de température depuis 6 mois poids = 68 kg taille = 155 IMC = 29.9 diagnostic? dysovulation Syndrome des ovaires polykystiques critères de Rotterdam oligo spanioménorrhée hyperandrogénie clinique ou biologique...
• The reality of this great mystery is manifested throughout the Christmas season in the solemnity of the Holy Family of Jesus, Mary and Joseph, in the celebration of Mary, the Mother of God on New Year's Day and the Epiphany...