×

Let's log you in.

or

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

×

or

45

0

2

Class Note for CSCI 212 with Professor Choi at GW

Marketplace > George Washington University > Class Note for CSCI 212 with Professor Choi at GW

No professor available

These notes were just uploaded, and will be ready to view shortly.

Either way, we'll remind you when they're ready :)

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

×
Unlock Preview

COURSE
PROF.
No professor available
TYPE
Class Notes
PAGES
2
WORDS
KARMA
25 ?

Popular in Department

This 2 page Class Notes was uploaded by an elite notetaker on Saturday February 7, 2015. The Class Notes belongs to a course at George Washington University taught by a professor in Fall. Since its upload, it has received 45 views.

×

Reviews for Class Note for CSCI 212 with Professor Choi at GW

×

×

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/07/15
CSCI 212 Class Notes 021009 Select Problem Given A list A of 71 elements a1 a2 an in an arbitrary order and an integer k 1 g k g 71 Objective Find the kth smallest element in 071 time We nd the desired element by recursively partitioning the list around the median of medians To nd the median of medians we divide the list into groups of size 7 create a list of the medians from each group and nd the median of the list of medians recursively The elements are grouped as shown below When the total number of elements is not evenly di visible by 7 ie 71 37 7 the remaining elements a g l an are not included in any of the groups Note that we used groups of size 5 when previously discussing the algorithm 117 127 7a77a87 197 701147 7a71 7117 701777 7 047ng7117 7017ng 9 9 7 1 2 g Our algorithm appears below We denote with 771 the median of group 91 SelectAk 1 Compute M the list of the medians from each group M 7 7711 7712 771LJ 2 Compute 771 the median of the list of medians 771 7 SelectMHj2l 3 Partition the elements of A into three groups L E and R such that Va 6 L a lt 771 ii Va 6 Ea 771 and iii Va 6 Ra gt 771 4 If L lt k L E return 771 If k lt L return SelectLk Otherwise return SelectRk 7 L 7 Let T71 denote the time complexity of calling Select on a list with 71 elements From the four steps of the algorithm T71 071 071 Tmax Combining terms and forming an upper bound we have T71 071 Tmax To obtain an upper bound for L and R consider each group to be a sorted column of elements in a matrix containing exactly one column for each group Now arrange the columns so that the medians ie middle elements of the columns are in a non decreasing order The number of elements in A that are 771 2 771 is 2 4 2 This implies that R Ll the number of elements in A that are greater less than 771 is g 71 7 g 717 2 371 We now nd two constants Oz and B such that L 71 371 R 71 B71 and T71 04071 By substitution we have T71 g 071 T 71 This implies that we need cna qm0ngamSmmmmggmhme1ga gopsia ggagt0ltEra the previously obtained upper bound combined with the lower bound implied from 71 B71 yields lt B lt 2 We choose 3 Substituting for B we have 1 go 04 a 04 2 2738 We choose 04 10 We derived our choices of Oz and 3 based on 71 371 which can be shown by solving for n to be true for n 2 48 Therefore7 Tn on TGT 7 for n 2 48 Given our value of a we prove using induction that Tn 10cm Basis Case Let n 48 Tn 10071 for suitably large value of c Inductive Hypothesis Assume that Tm 10cm for some value of m g n We must now show that the claim is true for m 71 17 ie7 we must show that Tn 1 100n 1 Inductive Step Tn 1 Cn 7 4 hypothesis T g n TL1 ML Similarly M g n Kw 104 Therefore Tot 1 Cn 1 10enT110ew Cn 11 L70 Cn 1g 10671 1 1 w mm by de nition of Tn By the inductive 1 Therefore7 it must be the case that Tn 10071 for all values of n 2 48 The result implies that Tn

×

25 Karma

×

×

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

Jennifer McGill UCSF Med School

"Selling my MCAT study guides and notes has been a great source of side revenue while I'm in school. Some months I'm making over \$500! Plus, it makes me happy knowing that I'm helping future med students with their MCAT."

Bentley McCaw University of Florida

Forbes

"Their 'Elite Notetakers' are making over \$1,200/month in sales by creating high quality content that helps their classmates in a time of need."

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