### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# CS130A: Midterm 1 Cheat Sheet

UCSB

GPA 3.75

### View Full Document

## About this Document

## 182

## 0

## Popular in Course

## Popular in ComputerScienence

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

### 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

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### 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'

## Why people love StudySoup

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.