Class Notes (837,694)
CS 240 (49)
Lecture

# Cheat Sheet #1 I tried to fit in as much details as I could in one page

1 Page
450 Views

School
Department
Computer Science
Course
CS 240
Professor
Therese Biedl
Semester
Fall

Description
Algorithm: A step-by-step process for Notation Definition Linear Time f (n) is O(g(n)) there exist constants c > 0 and n0 > 0 Counting Sort: stable , but need to set value {0..k} carrying out a series of computations. Program: An implementation of an s.t. ((all)n => n0)(0 <= f (n) <= cg(n)) Running time : Equal(n+k) when k = O(n) algorithm. f (n) is Omega(g(n)) there exist constants c > 0 and n0 > 0 Running time or memory requirement s.t. ((all)n => n0)(0 _<= cg(n) <= f (n)) Radix Sort: elements with same number of digits(d) of programs are dependent on f (n) is equal(g(n)) there exist constants c1, c2 > 0 and n0 > 0 Each digit has value in {0…k-1} hardware, OS, and compiler. s.t. ((all)n => n0)(0 <= c1g(n) <= f (n) <= c2g(n)) Efficiency depend on(time,memory) f (n) is o(g(n)) for all constants c > 0, there exists a constant n0 > 0 Running time: Equal(d(n+k)) when k = O(n) and d s.t. ((all)n _=>n0)(0 <= f (n) < cg(n)) is constant f (n) is smallomega(g(n)) for all constants c > 0, there exists Priority queue x=log(a)b -> a^x = b constant n0 > 0 >QuickSort Running Time Balanced node: A node is balanced if the heights of its Unsorted array log(a)b = log(c)a/log(c)b. ((all)n _ n0(0esCacsges))tsfinto))two Equal(n*logn) two subtrees differ by at most one (an empty subtree is 1- (selection sort) log a + log b = log a*b WorstCase min or max Equal(n^2) defined to have height −1). Insert: O(1) sum(0 to n) i = n(n+1)/2 AverageCase split into (k-1)&(n-k) Equal(n*logn) AVL Tree: A Binary Search Tree such that every node is balanced, Height AVL is O(logn) Extract Max : O(n) sum(0 to n-1) q^i =(1-q^n)/(1-q) Auxiliary Space Equal(n) because recursion depth Sorted Array sum(1 to n) 1/I = O(logn) Recurse on small parts causes auxiliary O(logn) Insert O(logn) perform at most one rotation or double 2- (Insertion sort) Delete O(logn) perform as many times as needed Insert : O(n) Heap: is a type of binary tree,stores items with keys,all full, last level to the Rotations in O(1) Extract Max: O(1) left, key of parent larger than children(max-heap), height: Equal(logn) Advantage storing way: easier to implement, mores space efficiency A randomized algorithm is an algorithm that uses 3- (heap) random numbers inits execution & depends on it Insert: O(logn) Indexes: Left( 2*i ), Right( 2*i + 1 ) , parent( floor(i/2)) EMax: O(logn) Building heaps: T(exp)(x) = E[T(x, R)] = Sum T(x, R).Pr [R]. Solution1: start with empty heap & insert one by one & perform bubble QuickSort is the fastest comparison-based sorting up (1toN) worst case time Equal(n*logn) algorithm in practice in the average case. Build PQ: O(n) Little space used Solution2: heapify which bubbles down(n/2 to 1) worst case Equal(n) Sorting in O(nlogn) Sorting using heaps O(n*logn) Hashing: ◮ f (n) = o(g(n)) if L = 0. B-Trees: A generalization of binary search trees - Keys range from {0…U-1} buckets or slots ◮ f (n) = equal(g(n)) if 0 < L < infinity - Node x stores k keys in non-decreasing order and - duplicates cause collisions ◮ f (n) = smallomega(g(n)) if L = infinity - Space O(U) ; insert, delete, search take Equal(1) references to its k + 1 children. - Uniform hashing :make it equally likely - Keys of subtrees at children are between the corresponding boundary keys at x. - interpret keys as natural numbers, or division method h(k) = k mod M and M is a prime, multiplication method - all levels are the at the same level h(k) = floor(M(kA – floor(kA) ) ) where 0 < A < 1 is a suitable constant - B-tree of order M: each node has at most M − 1 Dealing with collisions keys (and therefore atmost M children), also each Chaining : each bucket is a unsorted linked-list, load factor alfa = n/M where n is the # of elements , expected length is alfa, for search expected time is Equal(alfa + 1) , keep load factor constant, no explicit non-root node has at least ⌈M/2⌉− 1 keys (and therefore at least ⌈M/2⌉ children) need to rehash A B-tree of order M with n keys has - Opening addressing: fxns to store key, use probe sequence , keep load factor smaller than 1 , rehashing is Height Equal(log(M/2) n) = Equal(log n). required often, fast computation(linear hashing) vs better average time( double hashing) , deletion is Search Time: O (height. Log(2)M) = O (log(M/2)n)
More Less

Related notes for CS 240
Me

OR

Join OneClass

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

Join to view

OR

By registering, I agree to the Terms and Privacy Policies
Just a few more details

So we can recommend you notes for your school.