CISC320 algorithms, 11S, midterm exam review notesReading covered: Chapters 1-5 (in ch 3 and 4 especially 3.5, 3.6, 4.3, 4.4, 4.6) 6.1, 6.3Definitions of estimation tools: big-O, Ω, Θ.• the inequalities b e tween functions defining these must hold up to a positive constant factor.For instance, f (n) is O(g(n)) requires f(n) ≤ c ∗ g(n), for some positive c. Often the firstchallenge in proving a big-O relationship is guessing c, i.e. finding a c that will work.• The inequalities may be wrong for a few small values of n. It is only required that they betrue for all values of n after some threshold. For instance, n is O(n ∗ log(n)) even though whenn = 1, we see that n > c ∗ n ∗ log(n), regardless of c. On the other hand – and what c ounts –for all n ≥ 2, we see that n ≤ n ∗ log(n) is true because log(n) ≥ 1 for n ≥ 2.Master theorem and Muster theorem• Master theorem (applies to rec urrences diving down to n/b) and Muster theorem (applies torecurrences stepping down to n − b)• divide and conquer sorting (merge sort) (p50)• lower bound for sorting (p51)• divide and conquer selection (randomized median) (homework problem)Themes: divide and conquer algorithms may be organized around applicable case of Master theorem(see algorithms list below).Algorithms to which Master theorem applies:• Case 1 of Master theorem: selection (randomized median)• Case 2 of Master theorem: merge sort, binary search• Case 3 of Master theorem: stooge sort has recurrence T(n) = 3T((2/3)n), for n > 2.Algorithms to which Muster theorem applies:• Case 1 of Muster theorem: a < 1 doesn’t come up much.• Case 2 of Muster theorem: insert sort has recurrence T(n) = T(n-1) + O(n) [ insert sort onthe first n-1 followed by insert the last elt.]• Case 3 of Muster theorem applies to many exponential algorithms: For instance on a robotarm tour variant. The problem as to find a minimal cost tour through all the points of aweighted graph in which all nodes have degree at most k. Pick a point a, remove it, and, foreach pair b,c of neighbors, combine them into one point. find the optimal tour through theresulting graph, add the cost of going from b to a to c. Take the minimal of all those tours.The recurrence is T(n) = (k)(k-1)/2 T(n-2) + O(n). Muster theorem says T(n) is O(nkn).[()k2)n/2= kn.]Graphs• Breadth first search (bfs) in (undirected) graphs and digraphs (directed graphs).• Single source shortest path via bfs.1Themes: basic graph representation and terminology, bfs is basis of solving some problems.Chapter 6.1: Minimal Spanning Trees. Prim’s (uses priority queue) and Kruskal’s (uses union-find) algorithmsChapter 6.3: Dijkstra’s algorithm (assuming a priority queue) for single source shortest paths inweighted graphs.Overall: Things to know about each algorithm:• Why is it correct (vis a vis it’s input/output specification)? What are the theorems andproperties used to explain it’s workings?• What measure, n, of it’s input is used as basis for analysis (for instance, n = bound on numberof bits in numbers, or n = size of an array)?• What formula (function of that n) estimates it’s runtime? Usually the formula is a recurrencerelation.• What is the solution of that formula/recurrence up to big O or Θ?Kinds of questions: multiple choice, short answer, analyze given algorithm, write (simple)
View Full Document