### 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 (2)

### View Full Document

## 16

## 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 16 views.

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

### 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 Class Notes 021709 Activity Scheduling Problem Given A set of 71 activities A ai 7 5i 121 Objective Find a schedule S Q A of activities with maximum cardinality that do not overlap The start time and nish time of activity a are denoted by s and fi respectively Activities i and j overlap if s lt fj and 57 lt flu Our algorithm initially sorts the activities by nish time and possibly relabels them such that f1 f2 g f The earliest nishing activity is added to the schedule The remaining activities are iterated over Activities that overlap with the most recently scheduled activity are ignored while the next rst nishing activity that does not overlap with the most recently scheduled activity is added to the schedule The resulting schedule is optimal ie it has a maximum number of activities Schedulen 1 SortA 2 7271 Slt7a1 3 Forj72ton lijEfiS7SUaJandi7j 4 Return S lterating through all activities takes On time complexity However the sorting has a time com plexity of Onlog Therefore the total time complexity is Onlog We now prove the opti mality of the solution returned by our algorithm Proof We must show that 1 some optimal schedule contains a1 ie the rst nishing activity and 2 an optimal schedule for 71 activities that includes the rst nishing activity a1 is composed of an optimal solution for the subproblem A Aa1 U ailsi lt f1 1 Let S Q A be an optimal schedule such that an S Therefore there must exist some other rst nishing activity ak E A By construction we have fk 2 f1 ie activity ak will nish at the same time or later than a1 We can de ne a new solution S Sak U 04 by replacing the rst nishing activity in S with an S has the same cardinality as S Further f1 fk implies that there are no new con icts with the remaining elements Therefore there exists an optimal schedule S that contains the rst nishing activity a1 2 Assume an optimal solution for A contains k segments including the rst nishing segment a1 It must be the case that k 7 1 is the maximum number of segments for the subproblem A Aa1 U ailsi lt f1 Suppose that there exists a solution for A that includes gt k 7 1 segments We could then replace our original k 7 1 segment schedule with the gt k 7 1 segment schedule The resulting schedule includes gt k711 k segments in total This contradicts are as sumed k segment optimal schedule Therefore an optimal schedule that includes the rst nishing segment a1 includes an optimal solution to the remaining subproblem A Aa1 U ailsi lt f1 By 1 and 2 there exists an optimal schedule that combines the rst nishing segment a1 with an optimal solution to the remaining subproblem Aa1 U ailsi lt f1 Therefore our greedy algorithm is optimal Coin Changing Problem Given Coins with values of 1 5 10 25 and 50 and number of cents 71 Objective Make change for 71 cents such the total number of coins used is minimized Our algorithm greedily includes as many coins of each value in decreasing order of value as possi ble without exceeding 71 cents The solution returned is a 5 tuple representing the optimal fewest quantity of coins used lts elements correspond to the quantity of coins with values 1 5 10 25 and 50 respectively The time complexity is 01 Changen fe nfen50 1 2 nq e nf25 3 d lt 4 5 i 71d lt nq10 PT T n as 315 13 1 m m 7 71k lt nd5 Return 71k7 7 14716 Proof Let G 9192 g5 be our greedy solution and let P 191192 p5 be an optimal solution such that 2119 lt 21 91 Let k denote the index of the rightmost quantity where gk 7 pk ie the largest coin value where the quantities differ It must be the case that gk gt 5 Otherwise gk 5k or gk lt 5 which contradicts our assumption on them differing or yields a number of cents greater than n Observe than an optimal solution necessarily has 0 nk 4 0 g k g 1 0 g d g 2 and 0 q 1 Otherwise a solution 5 using less coins could be formed eg 3 value 10 coins replaced by 1 value 5 and 1 value 25 coin Consider all possible values of the index k If k 5 at least 50 must compensated for by the quantity of coins in 191192 p4 At least 4 additional coins must be used which implies there exists a solution 5 with at least three coins less than the optimal solution P by using one value 50 coin Similarly if k 4 a solution 5 exists with at least two coins less than P by using one value 25 coin For k 3 at least a value of 10 must be compensated for by coins in 191 and p2 However the highest value that an optimal solution can obtained with such coins is 9 The case for k 2 is similar For k 1 the optimal solution cannot obtain a total of 71 cents We see that each value of k for an optimal solution P that uses less coins than C leads to a contradiction which implies that such a solution P with less coins than C cannot exist Therefore our greedy solution is optimal Proof alternative Consider an alternative Changen algorithm that includes a coin of largest value c with c g n and recursively solves the problem for n 7 0 cents We must show that 1 some optimal solution contains a coin of largest value c g n and 2 an optimal solution for 71 cents that includes a coin of value c is composed of an optimal solution for n 7 0 cents 1 Assume that no optimal solution contains a value 0 coin lf 1 g n lt 5 0 must equal 1 because the solution contains only value 1 coins This is a contradiction since 0 is of largest value 71 If 5 g n lt 10 c is 5 Therefore we could use a coin of value c to form a new solution with fewer coins than the optimal solution This is a contradiction The cases for 10 g n lt 25 and n 2 25 are similar Therefore there exists an optimal solution that contains a largest value c g n coin 2 Assume an optimal solution for 71 cents contains k coins including a largest value c g n coin It must be the case that k 7 1 coins are used to make change for n 7 0 cents Suppose that there exists a solution for n 7 0 cents that uses lt k 7 1 coins We could then replace our original k 7 1 coin n 7 c soluti0n with the lt k 71 coin solution The resulting solution would use lt k 71 1 k coins in total This contradicts our assumed k coin optimal solution Therefore an optimal so lution that includes a largest value c g n coin includes an optimal solution to an 7170 subproblem By 1 and 2 there exists an optimal solution that combines a largest value c g n coin with an optimal solution to the remaining 71 7 c subproblem Therefore our greedy algorithm is optimal Optimal Storage on Tapes Problem Given A set of programs 1 2 n with each program i having length 1 Objective Find a permutation of the programs that minimizes the mean retrieval time MRT Our algorithm sorts and possible relabels the programs such that ll lg Zn The resulting permutation minimizes the MRT assuming all programs are retrieved equally often from the tape The proof is as follows Proof Let I i1i2in be any permutation the programs 1 2n Minimizing the MRT is equivalent to minimizing the total retrieval time TRT The TRT of a permutation I is TRTU 22171 7 k 1lk If there exists indices a and I such that a lt b and id gt lib ie two programs not in a non decreasing order we can de ne a new permutation I that inter changes the positions of the program The TRT ofthe new partition is 221k7 a 7 b n 7 k 1lk n 7 a 1lb n 7 b 1la The difference between the TRTs of the permutations is TRTI TRTIlzz1kakb 71 k 1lik n a1lia n bi 1 ibl ELM 1701 k 1lik n7a1lib n7b1lia n7a1lia n7b1lib 7n7a1lib 7 n7b 1lia nb1libli na1lialib na1lialibnb1lialib bialiailib gt 0 The result implies that we have obtained a permutation with a lower MRT from a permutation that does not have 1 values in a non decreasing order Therefore any permutation that is not in a non decreasing order cannot have a minimum MRT Among all permutations with 1 values in a non decreasing order the MRTs are all equal eg when we have multiple programs with the same length Therefore the permutation in a non decreasing order returned by our algorithm is optimal String Search Problem Given A pattern string p of m characters and a text string 25 of 71 characters with m g 71 Objective Determine ifp is a substring a t in On time We apply the Knuth Morris Pratt KMP algorithm which solves the problem in On time As an example consider the problem of nding a pattern p 010100 in some text if It is possible to construct a nite state machine FSM that nds p such as the one shown in Fig 1 Observe the following properties of the FSM When a match occurs a transition to a state with a higher index i is made The next text character is then compared with the character dictating the transitions from the new state When a mismatch occurs the next text character is not necessarily checked immediately Instead the FSM transitions to a state at least one index lower than the current state and compares the current text character with another pattern character The backward transitions occur until either a match is found or a mismatch occurs in statei O ie with the rst character of the pattern at which point the next text character is checked mismatch mismatCh mismatch mismatch next text mismatch mismatch Figure 1 A FSM that searches for the pattern 010100 The states that the backward transitions transition to are determined by properties of the pattern A mismatch at statei k implies that we ve already matched the rst k characters of the pattern The characters form a pre x of the pattern It also implies that we ve mismatched on what would have been the k 1 character of our pre x of the pattern Therefore we transition back to a state i h where h is the length of the longest substring of the length k pattern pre x that is both a pre x and suf x of the pattern pre x The reason is that after mismatching with the k 1 pattern character we do not necessarily have to return to the beginning of the pattern Instead we are allowed to attempt to nd a match with the h 1 pattern character The reason is that the last h characters of the k character pattern pre x we matched can also form the rst h characters of a new pattern match Such a match is possible because our k character pattern pre x contained a length h substring that is both a pre x and a suf x of it KM nds the longest such substring for each possible length of pattern pre x during the preprocessing phase described below Preprocess 1 7Llt0jlt71 2 While 72 lt m While 0 Z 0 A Plil 7gle j H Sljl ilti1jltj1 The element pm with 0 g i g m 7 1 is the ith character of the length m pattern p The element contains the length of the longest substring that is both a pre x and a suf x of a pre x of length i of the pattern The algorithm iterates through each of the m elements of the pattern Successive longest pre xsu x substring lengths si 1 are computed by checking ifpsi pm ie if the character after the longest pre xsuf x substring is equal to the i 1 character of the pattern If not it keeps checking the remaining longest pre xsuf x substrings in decreasing length similarly It stops when the character after a longest pre xsuf x substring matches or no more substrings remain For our example pattern p we obtain s0 m 710 0 1 23 1 Observe how s0 m compactly represents the backwards transitions of our FSM Note that the value sm 1 would be used if we wanted our FSM to nd multiple occurrences of the pattern The outer while loop executes for m iterations and the inner loop iterates until we decrease j past 0 Each time it executes it decreasesj by at least 1 Observe that j is only increased by 1 in each iteration of the outer loop Since j cannot be decreased more times than it has been increased the number of iterations of the iterations of the inner loop is at most m One comparison is made during each iteration of the loop Therefore the time complexity ofthe KM preprocessing is 0m Searching for the pattern is similar to the preprocessing The basic idea is to view the text as the concatenation of the pattern and the text For our example we would have 010100t0n 7 1 Therefore an occurrence of the pattern in the text is found when we nd for some pre x of length H 1 of the text a longest pre xsuf x subsequence of length m KM searches as described below Search 1 7Llt0jlt0 2 Whileiltn While 3 Z 0 A tlil 291le j H 8131 ilti1jltj1 lfj m return i 7 j the index of the rst character of the match in the text The analysis of Search follows that of Preprocess However here we increasej up to n times in the outer while loop Using similar reasoning as before the time complexity of Search is With preprocessing KM has a time complexity 0m Therefore when m g n the time complexity of KM is

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

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

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

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

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