New User Special Price Expires in

Let's log you in.

Sign in with Facebook


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


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here

Week 2 Notes

by: Shanee Dinay
Shanee Dinay
GPA 3.94

Preview These Notes for FREE

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

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Week 2 notes of Computer Science Algorithms Analysis. Topics include Merge Sort, Closest Pair of Points Problem, Integer Multiplication, and Master Theorem.
Algorithm Analysis
Dimitris Achlioptas
Class Notes
Computer Science, Algorithm Analysis, Merge Sort, Master Theorem
25 ?




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.

Similar to CMPS 102 at UCSC

Popular in ComputerScienence


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


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


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'

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


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


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:

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

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.