DOC PREVIEW
UD CISC 320 - Midterm Exam Teview Notes

This preview shows page 1 out of 2 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 2 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 2 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

UD CISC 320 - Midterm Exam Teview Notes

Download Midterm Exam Teview Notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Midterm Exam Teview Notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Midterm Exam Teview Notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?