### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Class Note for CSCI 212 with Professor Choi at GW (5)

### View Full Document

## 15

## 0

## Popular in Course

## Popular in Department

This 5 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 15 views.

## Popular in Subject

## Reviews for Class Note for CSCI 212 with Professor Choi at GW (5)

### 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/07/15

CSCI 212 Problem Notes 012709 Ordered Search Problem Given A list of n elements 11012 an in a non decreasing order such that a1 a2 an and a number m Objective Check if z is present in the list ie if a z for some i 1 g i g n We apply binary search to get an Olog n time algorithm If x is present in the list the algorithm returns the position of z A position of 71 indicates z is not present Note ah is the ith ele ment in the list 1 is the left most element and r is the rightmost element The initial call is BS1n BSLr 1 lfl gt r return 71 2 mlt7 3 If x am return m If x lt a m return BSlm 71 If x gt a m return BSm 1r After each comparison we eliminate half the elements in our list In the worst case comparisons are made until there is one element remaining The total number of comparisons is equal to the number of times that we can halve the list which is the de nition of the log function Leftmost Ordered Search Problem Given A list of n elements 11012 an in a non decreasing order such that a1 a2 g an and a number m Objective Find the left most occurrence of z in the list We apply binary search to get an Olog n time algorithm However we don t return immediately after nding an occurrence of z Instead we note the current left most position of z and continue searching for an occurrence that is further left Note 0 refers to the position of current left most occurence The initial call is LBS1n71 LBSZT c 1 lfl gt r return 0 2 m lt7 3 If x a m return LBSlm 71m If x lt am return LBSlm 71c If x gt am return LBSm 1rc Occurrences Ordered Search Problem Given A list of n elements 11012 an in a non decreasing order such that a1 a2 an and a number m Objective Compute the number of occurrences of z in the list We apply binary search algorithms to nd the leftmost and rightmost occurrences of z in the list The difference plus one is returned as the count RBSO nds the rightmost occurrence and OBSO computes the total number of occurrences Rl38lr7 c 1 lfl gt r return 0 2 mlt7 3 If x Mm7 return RBSm 1 1773771 If x lt Mm7 return RBSlm 7 10 If x gt Mm7 return RBSm 1730 OBSlr 1 m lt7LBSZT771777 HRBsw i 2 If n 7 m 1 lt 07 return 0 Otherwise7 return 71 7 m 1 LBS and RBS are both Ologn time algorithms Therefore7 OBSO is Ologn Median Ordered Search Problem Given Two lists of n elements a1 a2 Wan and b17192 71 in non decreasing orders such that algagg anandb1 b2 bn Objective Compute the median of the two lists7 ie7 the nth smallest element MSGiWiJZJZ 1 m1 lt7 7113quot7712 lt7 LLEWJ 7712 2 If n 17 return minam1 7b 3 If am1 b mg7 return am1 4 If am1 lt b 7 l1 11lj7 T2 m2 5 lfam1 gt bm27 212 g17r1m1 return MS11T17127T2771 We compare the medians of each list Based on the result7 elements are removed from each list The smallest element is searched for among the remaining elements The key observation is that the elements before the lesser median and the elements after the greater median may be discarded The time complexity is Olog Matrix Ordered Search Problem Given A number x and a matrix of n2 elements that is row and column wise sorted such that for an 112 am a11 a12 39 a1n a11 a21 an1 121 122 aZn a21 a22 a2n a12 a22 an2 A t 7 we have and am anZ ann ani anz m am a1n a2n quot39 ann Objective Find the position of m We compare z with the middle element of the matrix Each comparison allows us to eliminate 14 of the elements in the matrix or sub matrix The reason is that the upper left lower right quarter of the elements are 2 the middle element when x is greater less than the middle element Note 51 and t1 denote the rst and last row7 and 52 and t2 denote the rst and last column A position of 7171 indicates that z is not present The initial call is MS1n1n MS51t1752t2 m e ll7 m e ll If x Ahmhmg7 return 771177712 If 51 251 A 52 2527 return 717 71 lfm lt Amlmg7 ppme If r HMS51m1sgm27 717 71 return r If r HMS51m1m2 17t27 71717 return r Otherwise7 return MSm1 17t17527m2 5 lfm gt Amlmg7 If r HMS51m1m2 17t27 71717 return r If r HMSm11t17527m27 717 71 return r Otherwise7 return MSm1 1725177712 1252 At each level of recursive calls7 the number of comparisons needed for all calls at that level triples and the number of the remaining elements decreases by 14 until no elements remain see Table There are no remaining elements at some level k when the number of comparisons made is equal to the number of remaining elements from the previous level7 ie7 each remaining element is compared to z and there are no sub matrices remaining Call Level Comparisons Remaining Elements 1 1 gm 2 3 2712 3 32 W I 311 b Therefore7 the value of k satis es Bk l Gy lnz Solving for k we get k logn l The number of comparisons made is 1 3 32 3k 1 3411 3k Substituting for k we get 310g 1 3 310 3 nlog3 0nlog3 lt 0012 When n is an odd number the sub matrices will not be square In such cases7 the last row and the last column of the original matrix should be searched for z and removed in On time prior to calling MS on the remaining square matrix The sub quadratic bound on the running time is not affected In nity Ordered Search Problem Given A number x and a list of numbers such that the rst 71 numbers are not equal to in n ity and are in a non decreasing order While all remaining numbers are equal to in nity That is7 a1gaggganltooandan1an2oo Objective Check if z is present in the list We nd an in nity by iteratively checking the 21th element beginning with i 0 We then apply binary search on the list from 1 to 2quot Iso 1 727 0 2 While am 7g 00 2 EH 1 3 Return BS12i By construction7 the last element that is not equal to in nity is between 21 1 and 2i7 ie7 21 1 g n lt 2139 Therefore7 2139 g 271 and our algorithm has Ologn time complexity Shifted Ordered Search Problem Given An integer k and a list of numbers m1 m2 m such that xi lt n1 lt n2 lt lt zn lt m1ltm2ltltm71forsomei71 i n Objective Find the kth smallest element We apply a type of binary search to nd the smallest element mi in the list The key observation is that M lt implies that ml is to the right of the median The index of the kth smallest 2 2 element is returned by adding an offset to i SBSU 1 If x lt m V l r V r 71 1 A z lt ma return 1 k 71n 2 If r 711AzT lt ml return r k 71n 3 m lt7 4 If M lt mm return SBSm 177 5 If M gt mm return SBSlm We use a special remainder operator that has nn n The time complexity is Ologn because we do a binary search over the n elements Sum Ordered Search Problem Given A number x and a list of numbers 1170127 Wan in a non decreasing order such that a1 a2 an Objective Find a pair of numbers L and Li such that L aj m With each comparison we eliminate one of the numbers in the list When the sum is too low high7 the lowest highest number is removed SSZT 1 If r 7 l 07 return 7171 2 If al 3 If al 4 If al 1M m return 177 1M lt m return SSl1r 1M gt m return SSlr 71 The time complexity is On because one comparison is made each call and one element is removed each call until only one element remains Mod Problem Given Integers B7 71 and M Objective Compute B mod M in Olog n time We rely on the property that A x B mod M A mod M x B mod M mod M Below7 is the well known mod operator ie7 not the previously used special one MPn 1 lfn 17 return B 2 If n2 0 return Mpg2 2 3 IF n2 17 return B x The time complexity is Ologn because there is one comparison for each recursive call until the exponent is reduced by reducing by one half each time to one

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

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

#### "I made $350 in just two days after posting my first study guide."

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

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

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

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.