false

Class Notes
(837,694)

Canada
(510,398)

University of Waterloo
(18,601)

Computer Science
(798)

CS 240
(49)

Therese Biedl
(26)

Lecture

Unlock Document

Computer Science

CS 240

Therese Biedl

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

Join OneClass

Access over 10 million pages of study

documents for 1.3 million courses.

Sign up

Join to view

Continue

Continue
OR

By registering, I agree to the
Terms
and
Privacy Policies

Already have an account?
Log in

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.