CS130A: Midterm 1 Cheat Sheet
CS130A: Midterm 1 Cheat Sheet
Popular in Course
verified elite notetaker
Popular in ComputerScienence
Ted Robel Sr.
verified elite notetaker
This 2 page Bundle was uploaded by logeybearrr on Saturday June 7, 2014. The Bundle belongs to a course at University of California Santa Barbara taught by a professor in Fall. Since its upload, it has received 182 views.
Reviews for CS130A: Midterm 1 Cheat Sheet
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: 06/07/14
COMPLEXITY ANALYSIS 0 serves as an upper bound 9 serves as a lower bound 9 serves as an equality both TnOfn means Tn lt cfn for n gt n Simple statements read write assign 01 Simple operations gtgt 01 Sequence of the above rule of sums for do while loops rules of products rule of sums runtime is dominated by most expensive operation rule of products total runtime is the runtime of the operation multiplied by the iteration count if cond 01 bod Am Tn0maxAnBn else method calls A calls B B calls 0 bodyb Bn Tn OmaXAn Bn Cn HASH TABLES Characteristics and Desired Properties Keys spread out so collisions minimized MOn would like table sizem to not be much larger than the number of elementsn Hashing function hx is fast to computer near 01 Separate Chaining If the number of hash slots is at least proportional to the number of elements then a nm 01 Unsuccessful search takes average case time 90 1 under simple uniform hashing Given an hash table with 0 71 m lt 391 the expected number of probes in an unsuccessful search is at most 11 3 Inserting an element with load factorarequires at most 11 11 probes on average Given hash table with a lt1 the expected number of probes in a successful search is at most 1 1 11 D nm 1 is optimal chain length 1 12 Open Addressing Linear Hx Hx i mod m Quadratic Hx Hx I42 mod m Double Hx iH X mod m Using i 2 3 primes repeat half as much as 1 primes 13 mod 4 vs 24 mod 4 Linear Probing For successful searches 121 1 1 0 expected probes For unsuccessful searches 12 11 T 2 expected Rehash after 70 of table becomes full Build another table twice as big and prime Universal Hashing UH His universal if for all xyin U where x ywe have hxhy is equal to lHlm In other words the chance of a collision between xand yis 1m if we choose h randomly from H Suppose h is used to hash n arbitrary keys into m slots of a table T Then for a given key x the expected number of collisions with x lt nm habx a x b mod p mod m pgtm Each hash function maps Zp to Zm the keys are in the range 0 to p1 while the hash values are from 0to m1 This is nice because the table size m is arbitrary and not prime There are p1 choices of a and p choices of b so there are pp 1 hash functions Perfect Hashing PH Before PH one solution was to map keys to table size mnn so the chance of no collisions is at least 12 With PH the probability of no collisions at the second level is at least 12 but 0n space solution rather than 0nn To PH first hash into a table size Nwith UH This will cause collisions so we rehash each collided bin squaring the number of keys to get the size of second level bin zero collisions hjk ajk bj mod p mod mj CN2 NN12 pairs of keys so expected number of collisions is NN12 1m HEAPS A heap is a complete binary tree only vacancies are at the bottom level and to the right Height of a node in a heap is defined as the number of edges on the longest simple downward path from node to a leaf Completeness ensures heap of height h has between 2 h and 2 h11 nodes Heap with N nodes has height floorlog2 N dheap height logd n Minimum Heap Priority Queue insert add new element as new leftmost leaf percoateUp deleteMin root is swapped with rightmost leaf percolateDown Since height is Olog N and percolates traverse one path the cost is Olog N or Oheight of tree With index 0 empty the children of node at location i are at locations 2i and 2i1 The parent of node location j is floor 2 A leftist tree with r nodes on its right path has at least 2 r1 nodes Maximum Heap Max Heapify runs in Olg n time keeps the max heap property Build Max Heap runs in On and produces a max heap from an unordered input array Heapsort runs in On lg n and sorts an array in place Data Structures Data Structure Basic Array Dynamic Array SinglyLinked List DoublyLinked List Skip List Hash Table Binary Search Tree Cartresian Tree BTree RedBlack Tree Splay Tree 0 391 E 8 Q 0 AVL Tree 1 3 O O O 3 2 2 Search Example Factorial cont int factorial1int n if nlt1 return 1 else fact 1 for k2kltnkI01 fact k 001 return fact 101 I Both algorithms are On Worst Insertion Deletion Indexing Search Insertion I I I I I 2 2 2 2 2 2 2 2 2 2 Example Factorial am factorial rm n T00 if nlt1 return 1 Q d else return n factorialn1 Tn3ddd factorial n nn1n2 P 1 1Ef391d at 0n n factorIaln 1 Tm n 1 factorIaln 2 Tn1 n 2 factorialn 3 Tn2 2 factoria1 Q to 1 quotquotlquotl o 3 f H C k i EH cin D4 I o X 211i Space Complexity Worst Asymptomic 5 jji Q nquot n2 n3 nk1 rquot nn equot 1og n
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'