Class Notes (837,694)
Canada (510,398)
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
Unlock Document

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

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