Week 2 Notes
Week 2 Notes CMPS 102
Popular in Algorithm Analysis
Popular in ComputerScienence
This 4 page Class Notes was uploaded by Shanee Dinay on Monday February 8, 2016. The Class Notes belongs to CMPS 102 at University of California - Santa Cruz taught by Dimitris Achlioptas in Winter 2016. Since its upload, it has received 19 views. For similar materials see Algorithm Analysis in ComputerScienence at University of California - Santa Cruz.
Reviews for Week 2 Notes
Report this Material
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: 02/08/16
Day 3 1/12/2016 CMPS 102 Intro Analysis of Algorithms Mergesort divide array into two halves recursively sort each half merge two halves to make whole takes nlogn time merging takes O(n) T (n) = 2T(n/2) + O(n) mergesort ≤ O(nlogn) to perform Merge Sort, accept the sorting… not by unfolding it You cannot beat O(n log n) a leaf is a stopping configuration (end point) n! possible inputs therefore we need n! leaves total number of leaves 2 ≥ n! now we need a lower bound for n! 1 • 2 • 3 • 4 • … • n first and last = n second and second to last = 2(n1) 3(n 3) n/2 • n/2 so 2 ≥ n n/2 n depth ≥ 2 log 2 ~ n lon 2 Asking if the element in one position is greater than in that position: decrease number of possible choices Counting Inversions Similarity metric: number of inversions between two rankings my rank: 1, 2, …, n your rank: a 1 2, …, an songs i and j inverted if i < k, but a i aj Brute Force: check all Θ(n ) pairs i and j Divide and Conquer: Divide: separate list into two pieces Conquer: recursively count inversions in each hald 5.4 Closest Pair of Points Closest Pair of Points Closest pair: given n points in the plane, find a pair with smallest Euclidean distance between them First Attempt Divide: subdivide region into 4 quadrants you get a list of x,y pairs Sort the pairs, find the distance between the two pairs that are next to each other in the sorted array O(n log n) algorithm the algorithm implicitly gets rid of having to explore all options obstacle: imposible to ensure n/4 points in each piece split problem into two parts T(n) = 2T(n/2) + O(n logn) ← sort part 2 T(n) = O(n(logn) ) this recursion has that solution Find closest pair with one point with one point in each side, assuming that distance < δ (delta) observation: only need to consider points with δ of line L sort points in 2δstrip by their coordinate only check distances of those within 11 positions in sorted list! T(n) = SORT_X, SPLIT, RECUR, BAND, SORT_Y, COMPARE_11. = 2T(n/2) + O(nlogn) Closest Pair of Points Def let sie the point in the 2δstrip, with the ih smallest ycoordinate Claim if |i j| ≥ 12, then the distance between s ind sjs at least δ Proof no two points lie in same ½δby½δ box. two points at least 2 rows apart have distance ≥2(½δ) Fact: still true if we replace 12 with 7 Day 4 1/14/2016 5.4 Closest Pair of Points ● sort by xcoordinate takes O(nlogn) ● split evenly by x to left and right ● findnearest (left); find nearest right ● form band of width δ = min(LND, RND) ● sort points inside band by ycoordinate ● measure distance of each inband point to next 11 ygreater ● return min(δ, ——— measured distances ——) Closest Pair of Points T(n) = O(nlong) + O(1) + 2T(n/2) + O(n) O(nlogn) + O(n) = O(n(logn)) 5.5 Integer Multiplication Add. given two ndigits integers a and b, compute a + b ● O(n) bit operations Multiple. Given two ndigit integers a and b, compute a x b ● brute force solution: Θ(n) bit operations Divide and Conquer: Multiplication Karatsuba Multiplication ● To multiply two ndigit integers ○ add two ½n digit integers ○ multiple three ½ndigit integers ○ add, subtract, and shift ½ndigit integers to obtain result 1.585 ● Theorem. KaratsubaOfman 1962, can multiply two ndigit integers in O(n ) bit operations ● T(n) ≤ T(floor(n/2)) + T(ceiling(n/2)) + T(1 + ceiling(n/2)) + Θ(n) ● T(n) = O(n^log22) = O(n^1.585) Master Theorem T(n) = aT(n/b) + f(n) T(n), T(0), or T(2) = some number, constant b > 1 Ex. binary search. a = 1, b = 2, f(n) We start with a problem of size n ● generate sub problems ● each of size n/b ● how many? a sub problems ● keep subdividing each problem ● we stop at k. k is the number which has the property where n/b^k is small ● b^k = n/small k ● log base b of b = log base b(n/small) ● k = log base b (n) log base b (small) ● stops at k = lob(n) Now we want to figure out how much work we do? in the first level: size n, f(n) at level i: a^i, size how much work? a•f(n/b ) ● running time of the algorithm is ○ the sum of a •f(n/) from i=0 to lob base b (n) B.S.: a = 1, b = 2, F = C ● i, k=log base 2 (n) i=0, sum of C = C•log base 2 of (n) ● Binary Search O(log2) Merge Sort ● a=2, b = 2, f(n) = O(n) i i i i ● 2 • f(n/ = 2 • C • n/ = nC ● total amount of work we are doing per layer is the same ● so the total running time is O(nlogn) ● amount of work as we go down decreases 2 0 1 2 2 ● total amount of work: n • (1/ + 1/2 + 1/2 + … ) = n • 2 1 + 1/2 + 1/4 + 1/8 + … = 2 1 + 1 = 2 treat these two equalities as the same, calculus allows you to consider this If we have spare root of n, our amount of work will increase i i1/2 i 2(n/2) = sqrt(n) • (squareroot) Ex. a = 3, b = 3, f(n) = n ● algorithm splits into 3 parts, and then does linear amount of work in each part ● 3 n/3 ● 3 (n/3) = n log base b (n) = n l2 (n) Ex. a = 3, b = 4, f(n) = n ● 3 (n/4) = n (3/4 = n • 1/(13/4) = 4n Ex. a = 3, b = 3/2, f(n) ● T(n) = 3T(n/3/2) + n i ● 3^i problems each of size (2/3) • n ● 3 • (2/3 • n = n • 2 ● in this case the amount of work increases k ● n • (1 + 2 + 3 + 4 + 5 … + 2) <— total amount of work k+1 1 x / 1x nog2 3 1
Are you sure you want to buy this material for
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'