Data Structures and Algorithms I (COSC-201) - StudyGuide
Data Structures and Algorithms I (COSC-201) - StudyGuide
Popular in Course
Popular in COSC
This 1 page Bundle was uploaded by Feynman Liang on Tuesday April 1, 2014. The Bundle belongs to a course at Amherst College taught by a professor in Fall. Since its upload, it has received 347 views.
Reviews for Data Structures and Algorithms I (COSC-201) - StudyGuide
I'm pretty sure these materials are like the Rosetta Stone of note taking. Thanks Feynman!!!
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 04/01/14
COSC 201 Final Review Feynman Liang Asymptotic Analysis Focuses on dominant asymptotic term generally highest order polynomial of n nondominant terms annihilated during proof To prove nd c and no which holds for 0 Ogn Elc gt O st Vn gt no 0 g fn g cgn 0 gn Ec1c2 gt 0 st Vn gt no 0 S C19n S fn S C29n 0 Elc gt O st Vn gt no 0 g cgn 3 fn Recurrence Function which calls itself Needs a nonrecursive base case Prepost conditions truth at startend of method Assertions truth at point in execution loop invariants truth at each iteration of loop Master Theorem Quick way to solve recurrences Tn aT fnwherea 2 1 b gt 1 0 Case 1 If fn E On1 gb 6 for some constant e gt 0 then Tn E n1 gb 391 0 Case 2 If fn E n1 gb log n for some constant k 2 0 then Tn E n1 gb logk1 n 0 Case 3 If fn E 2n1 gb for some constant e gt 0 AND af g cfn for some constant c lt 1 and suf ciently large n then Tn E n1 gb 391 Ex Straussen s matrix multiplication 1 ifn 1 f n n n 7f 18lt gt2 lfn 75 1 This recurrence is case 1 182 E On1 g2 76 for e g logo 7 2 thus fn E On1 g2 7 Inductive Proof To prove Pk is true for Vk 2 b using strong induction 1 Prove Pb for some base case b 2 Assume Pn is true for b g n g k show that this implies PIlt 1 Weak induction only assumes Pk to prove Pk 1 This doesn t allow you to use any states past the n 1 state while proving Pn Divide and Conquer Can be represented by a recurrence tree with number levels depth of recurrence and children per node number of subproblems per recurrence Dynamic Programming Solves optimization problems which exhibit optimal substructure optimal sol n depends on optimal solution of subproblems To implement de ne the optimal solution to the problem recursively ex bestab bestak bestk1b for kab Examples maximumsubsequence traveling salesman rod cutting VO O Vk maxvk1p for Olti k Memoization Cache past calculations improve performance on overlapping subproblems Solution reconstruction Add a step to algorithm which keeps track of how optimal value was obtained by lling in array Data Structures ADTs Data structures are used to abstract lower level implementation details while allowing organization of data ADTs provide operation on the data structures Arrays 0 Insert O1 unsorted On sorted 0 Delete O1 On 1 if need to shift 0 Search On unsorted Ologn sorted Priority Queue Data structure which maintains sorted order Typically implemented using minmax heap or sorted array Min Max Heap Tree structure which has property that Vchildren max heap or Zmin heap parent Implies root node is maxmin To maintain heap property must sift up compare two children for one parent slot Sorted array can be used as minmax heap where every 239 entries represent the kth level of the heap 1223333 For binary max 2 children heap 0 insert Olog n insert to empty on bottom and sift up 0 getMinMax O1 get root element 0 deleteMinMax Olog n delete top and sift up Graphs A graph contains n vertices connected by m edges Degree of vertex is number of edges it has max degree is denoted d Paths can have weight weighted and direction digraph Simple path is a path which does not visit a node twice can prove shortest path is simple using induction on removing cycles in path Undirected max number of edges directed n2 Type allNeighbors isNeighbor insertEdge Adj Matrix On O1 O1 Adj Llst Od Od O1 Edge L1st Om Om O1 Vertex Edge Omaxmd Omaxmd Omn Adj matrix has isNeighbor run time advantage space On2 Adj list has allNeighbors advantage space Ond Set Collection of elements with no redundancies Maintaining set independence requires looking up the element during insertion to check redundancies Hash table implementation 01 for all array implementation Op Unsorted Sorted insert On On lookup On Olog n delete On2 On Hash Table Can be used to implement mapset dictionary Contains M buckets and n elements Uses a hash function to convert input to a bucket index Good hash functions have uniform distribution of hash values computationally cheap Typically consume set number of bits and performs bit operations to hash Without collisions runtimes are 0 Insert O1 0 Delete O1 0 Lookup O1 To resolve collisions we can nd a new bucket open addressing using different methods hki returns another place to insert i if bucket hk is taken 0 Linear probing hk v Pgv mod M 0 Quadratic probing hk u 122 mod M 0 Double hashing hk u 12 hg I mod M Problem with linear probing is if something collides once it will always collide Simpler probing faster but more likely to cause clustering lled blocks which increase number of collisions Large clusters at end of buckets effectively shrinks size of M Quadratic and double hash resolve by varying probed bucket dependent upon i or hg Separate chaining is another collision resolution method where we just append to collided bucket make linked list Operations are n M Performance degrades more gracefully don t need to resize when full Performance of hash map depends on load factor nm Problems and Algorithms Sorting Stable Relative positions of elements don t change after sort In place Requires constant memory overhead Insertion Sort Construct sorted sub array at start of array Insert elements one by one and swap to maintain order On2 Merge Sort Divide and conquer Recursively split array down middle until single elements then merge all back together Tn 2T cn E n log n Quick Sort Pick partition element k partition around k lt kkgt Recur on both sides Expected On log n worst On2 if partition is always max or min Can randomize partition element to avoid worst case Selection of kth largest Binary Search Divide and conquer on sorted array Guesses middle element and recurs on side dependent upon whether guess was gt or lt expected Tn W c E logn Quick Select Randomized quick sort discards half which does not contain kth largest On2 worst always partition around minmax S2n log n best Median of medians Deterministic Quick Select Partition into blocks of size 5 calculate medians of the n5 blocks and take median of that to be new partition element O T g On 6 On time Matrix Algorithms Matrix Multiplication Dynamic programming solves optimal chain parenthesis by diagonally lling in a solution matrix Straussen s solves multiplication in On1 g2 7 Floyd Warshall Solves APSPtransitive closure in On3 instead of n4 by moving k loop outside Iterates over intermediate node k rather than path length T lt G for k1 to n for i1 to n for j1 to n Transitive Closure Warshall algorithm Tii Tii Tliakl ampampTki All Pairs Shortest Paths Floyd s algorithm iterate across the ks all table lookups Mij minofTij Tik Tkj
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'