Class Notes (835,600)
Canada (509,275)
CS 240 (49)
Lecture

Cheat Sheet #2 I tried to fit in as much details as I could in one page- its a useful for reviewing

1 Page
201 Views
Unlock Document

Department
Computer Science
Course
CS 240
Professor
Therese Biedl
Semester
Fall

Description
Bubble-up (Node i ):Time = O(logn) use 4 insert Heapsort /* Heapify: */Equal(n) QuickSort Running time details while (p(i ) exists) and (value(p(i)) < value(i)) { for i := n/2 downto 1 exchange values(i ) and value(p(i )); Bubble-down(i) i ← p(i );} /* ExtractMax one at a time */ while (n > 1) { Bubble-down (Node i ): Time:O(logn) use EMax Swap(A[n], A[1]); while (i has children) { n--; let j be the child of i with the largest value Bubble-down(1);} if value(j) > value(i ) then exchange values(i ) and value(j); QuickSortRecurseOnSmallerPart(int[] A, int left, int right): Rotations i ← j ; int myLeft := left, myRight := right; RandomPermute(A, n): otherwise for i ← 1 to n while (myLeft < myRight) do break;} exchange(A[i ], A[random(i , n)]) | int i := Partition(A, myLeft, myRight); | if (i-myLeft) < (myRight - i) then QuickSort(int[] A, int left, int right): | | QuickSortRecurseOnSmallerPart(A, myLeft, i-1); if left < right | | myLeft = i+1 | else int i := Partition(A, left, right); | | QuickSortRecurseOnSmallerPart(A, i+1, myRight); QuickSort(A, left, i-1); QuickSort(A, i+1, right); | | myRight = i-1 Partition(A, left, right): Theorem pivot := A[right]; The height of an AVL tree with n nodes is O(log n). i := left-1; Proof: What is the least number of nodes (nh) of an AVL-tree of height h? for j := left to right Recurrence relation: ni = ni−1 + ni−2 + 1. Predecessor: at most right in leftsubtree if A[j] <= pivot ni = Fi+3 – 1 = floor( feta^(i+3) / sqrt(5) ) + ½ - 1 Successor : at most left in rightsubtree i := i+1 Therefore, ni = equal( feta^I ) Flooring and ceiling swap(A[j], A[i]) Hence, n ≥ nh = equal(feta^I.) implies h = O(logn) 3/2 floor(1) ceiling (2) return i; 5/2 floor(2) ceiling (3) Running time of Partition: Extendable hashing: search 7/2 floor(3) ceiling (4) Equal(right − left + 2). Summation equations Given a key k, compute h(k) = a1a2 . . . aL. Auxiliary Space: Equal(1). ◮ Probe block B(a1 . . . ad ). ◮ Perform a binary search to find all items in the block. If the directly resides in internal memory, we have only a single memory Priority queue sort block transfer. for i ← 1 . . . n do PQ.insert(A[i]); for i ← n . . . 1 do Insert(x) is done as follows: ◮ Unsuccessful Search(x): A[i] = PQ.extractMax(); ◮ Search for x to find the proper block to insert ◮ Computing the hash value h(x) takes Equal(1). ◮ If the block has space then done ◮ A list is searched to the end of the list. ◮ If the block is full (i.e. has already S keys) and k < d, perform ablock split: ◮ By uniform hashi
More Less

Related notes for CS 240

Log In


OR

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


OR

By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.


Submit