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 1 Notes

by: Shanee Dinay
Shanee Dinay
GPA 3.94
View Full Document for 0 Karma

View Full Document


Unlock These Notes for FREE

Enter your email below and we will instantly email you these Notes for Algorithm Analysis

(Limited time offer)

Unlock Notes

Already have a StudySoup account? Login here

Unlock FREE Class Notes

Enter your email below to receive Algorithm Analysis notes

Everyone needs better class notes. Enter your email and we will send you notes for this class for free.

Unlock FREE notes

About this Document

Week 1 notes of Computer Science Algorithms Analysis. Topics include Merge Sort and Divide and Conquer Algorithms.
Algorithm Analysis
Dimitris Achlioptas
Class Notes
Algorithms Analysis, Computer Science, Divide and Conquer, Merge Sort




Popular in Algorithm Analysis

Popular in ComputerScienence

This 3 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 35 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 1 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 1 ­ 1/5/2016    CMPS 102  Dimitris Achlioptas Office E2 343A  Final Exam Thursday March 17th, 2016 12:00pm ­ 3:00pm  Website  TA Office Hours: Thursday 1:45pm­2:45, Friday 2:00pm­3:00pm  Textbook ­ Tardos and Kleinberg Algorithm Design    Section: Monday 11:00am­12:10 J Baskin 156  Section: Monday 12:30pm­1:40pm J Baskin 156  Section: Tuesday 4:00pm­5:10pm J Baskin 156  Section: Wednesday 9:30am­10:40am J Baskin 156    This week there will be review in the sections  ­ material that will be helpful in the class  ­ know  ­ big O notation  ­ basic data structures  ­ think of them as contracts  ­ very elementary  No programming  Midterm and Final will have a past homework question  ­ DO THE HOMEWORK  If you collaborate, write it down, site it  He will not tolerate cheating    Homework  Homework ­ 6­7 questions and and hour and a half for each question!!!  Latex  ­ look it up and use it  ­ ask someone to send you a file of their own  Typeset… type the homework  Heavily revise what you are writing as you are writing  Type the homework and print it, he does not care about seeing the evolution of our code  “The algorithm I proposed is…” pseudocode    A First Problem: Stable Matching    Day 2 ­ 1/7/2016    CMPS 102  Dimitris Achlioptas    TA and their Sections  Joe: Office Hours Thursday 2:00pm, Friday 2:00pm  Ankit:     Midterm: February 18th, 2016 Thursday  Review on Monday Sessions    We will cover Chapters 5, 4, 6, 7 of the textbook. Maybe 8.  Review Chapter 2 and 3    1.2 Five Representative Problems    Interval Scheduling  Input: Set of jobs with start times and finish times  Goal: Find maximum cardinality subset of mutually compatible jobs  Independent Set  Input: Graph  Goal: Find maximum cardinality independent set  subset of nodes such that no two joined by an edge  Set    set is: {2, 3, 5, 8, 9}    Chapter 5: Divide and Conquer    Divide and Conquer:  ­ break up problem into several parts  Mergesort 5.1  ­ sorting given n elements  ­ divide array into two halves  ­ recursively sort each half  ­ merge two halves to make sorted whole  Converting Inversions  ­ Music sites try to match your song preferences with others  ­ you rank n songs  ­ music site consults database to find people with similar tastes  ­ Similarity metric: number of inversions between two rankings  2​ ­ brute force: check all Θ(n​ ) pairs i and j  (2​ n choose 2 = n(n­1) / 2 ~ n​ 2  ­ our goal is to give an O(nlogn) algorithm  Divide and Conquer  ­ divide: separate list into two pieces  ­ conquer: recursively count inversions in each half  ­ Let’s say the time to solve the problem is  ­ T(n) = 2T(n/2)  2​ ­ number of inversions n/2 • n/2 = n​  / 4  ­ bad  ­ If this was a homework question this is the point you will try to reach   


Buy Material

Are you sure you want to buy this material for

0 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."

Kyle Maynard Purdue

"When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the I made $280 on my first study guide!"

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."

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.