×

### Let's log you in.

or

Don't have a StudySoup account? Create one here!

×

or

by: Shanee Dinay

19

0

4

# Week 2 Notes CMPS 102

Shanee Dinay
UCSC
GPA 3.94

Get a free preview of these Notes, just enter your email below.

×
Unlock Preview

Week 2 notes of Computer Science Algorithms Analysis. Topics include Merge Sort, Closest Pair of Points Problem, Integer Multiplication, and Master Theorem.
COURSE
Algorithm Analysis
PROF.
Dimitris Achlioptas
TYPE
Class Notes
PAGES
4
WORDS
CONCEPTS
Computer Science, Algorithm Analysis, Merge Sort, Master Theorem
KARMA
25 ?

## 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

×

×

### What is Karma?

#### 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(n­1)  ­ 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​, …, a​n  ­ songs i and j inverted if i < k, but a​ i​ a​j ­ 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: sub­divide 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 si​e the point in the 2δ­strip, with the i​h smallest y­coordinate  Claim ­ if |i ­ j| ≥ 12, then the distance between s​ i​nd s​j​s 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 x­coordinate  takes O(nlogn)  ● split evenly by x to left and right  ● find­nearest (left); find nearest right  ● form band of width δ = min(LND, RND)  ● sort points inside band by y­coordinate  ● measure distance of each in­band point to next 11 y­greater  ● 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 n­digits integers a and b, compute a + b  ● O(n) bit operations  Multiple. Given two n­digit integers a and b, compute a x b  ● brute force solution: Θ(n) bit operations  Divide and Conquer: Multiplication  Karatsuba Multiplication  ● To multiply two n­digit integers  ○ add two ½n digit integers  ○ multiple three ½n­digit integers  ○ add, subtract, and shift ½n­digit integers to obtain result  1.585​ ● Theorem. Karatsuba­Ofman 1962, can multiply two n­digit 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(log​2​)  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​ i​1/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/(1­3/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​ / 1­x  n​og2 3 ­ 1

×

×

### BOOM! Enjoy Your Free Notes!

×

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'

## Why people love StudySoup

Steve Martinelli UC Los Angeles

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

Allison Fischer University of Alabama

#### "I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over \$600 per month. I LOVE StudySoup!"

Bentley McCaw University of Florida

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

Parker Thompson 500 Startups

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

Become an Elite Notetaker and start selling your notes online!
×

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com