CS代写 – cscodehelp代写

STUDY MATERIAL:
• [CLRS] chapters 2, 4.1-2, 12.1, 31.1-2, 33.4 • Lecture Note 4

Copyright By cscodehelp代写 加微信 cscodehelp

 The algorithm design process: Central Tools: Iteration & Recursion Partial correctness: Assertions Termination: Measure of Progress
 Iterative Algorithms: Loop Invariant Incremental Method
 Recursive Algorithms:
Recursive Pre- & Post- Condition & strong induction Divide-&-Conquer Method

The Algorithm Design Process
We are given the pleasurable task of designing an algorithm for a computational problem.
 Where should we start?
 What design process should we follow?  Are we on the right track?
 Is there a systematic way to convince ourselves, our friends,
and all skeptics, that our algorithm is correct?
 Is our algorithm guaranteed to terminate on every possible input?
 Is there a better algorithm? …

Assertions
 An assertion is a true/false logical statement about the state of the variables and data structures of the algorithm.
 Although they appear as inserted comments, assertions are not descriptions of the code’s intended purpose or an explanation of its action.
 Important examples of assertions are:  Pre-Condition
 Post-Condition
 Loop Invariant
 What are assertions good for?
 They guide us along the design process. They should be with us from the
initial design stage; to the middle, keeping us on track; to the end, convincing us that we have a correct algorithm, if we maintain correct assertions.
 The design process might go through a revise-&-repeat cycle. If our assertions show us we are not quite on the right track, they usually also show us what is lacking and suggest ways of correction!

Algorithm GuessWhat(n)
Pre-Cond: input n is a natural number
Post-Cond: output is ——————– (fill in the blanks)
Termination:
Measure of Progress:
MP = n – i.
Each iteration reduces MP by 1.
while i < n do j  j + j end-while return j end § What is true about values of i, j & n here? § Any relationship between them? Initial MP = n. Loop exits when Algorithm GuessWhat(n) Pre-Cond: input n is a natural number Post-Cond: output is 2n (how can we be sure?) i  0  1 = 20 & j1 i MP  0. # iterations = n. 0  n loop  Loop-Invariant: j = 2 & i  n Establish LI (induction Base) (induction hypothesis) Maintain LI (induction) & progress towards goal if i  n then exit loop  j = 2  2j = 2i+1 & i+1  n j  j+ j end-loop so now: j’= 2i’ & i’ n j=2i & in & in Exit loop, use LI & reach goal returnj  Algorithm ALG(Input) Pre-Cond: Input satisfies problem instance specifications Post-Cond: output satisfies problem solution requirements Pre-Cond & ALG Code  Post-Cond Partial Correctness Warranty: If input satisfies Pre-Cond, and if ALG is executed on that input, and if ALG eventually terminates, then the output is guaranteed to satisfy Post-Cond. Post-Cond is not guaranteed to hold if input does not satisfy Pre-Cond, or if ALG does not terminate on the given input. Total Correctness = Partial Correctness + Termination. ASSERTIONS Assertion0 code fragment Assertion1 Assertion0 & code fragment  Assertion1 Assertion0 code fragment Assertion1 Sequential code: Assertion 0 code 1 Assertion 1 code 2 ................. Assertion M-1 code M Assertion M Assertion 0 & code 1  Assertion 1 Assertion 1 & code 2  Assertion 2 Assertion 2 & code 3  Assertion 3 .... Assertion M-1 & code M  Assertion M Assertion0 code 1 Assertion1 Assertion M-1 code M Assertion M If-then-else: Assertion0 then code+ else code- Assertion1 Assertion0 & cond & code+  Assertion1 and Assertion0 & cond & code-  Assertion1 Assertion0 NO code- cond code+ Assertion1 Many ... many paths from Pre- to Post- Assertion. Pre-Assertion cond0 NO Don’t trace It suffices to verify each code fragment block only once! cond1 NO code1- code2+ all paths one-by-one! cond2 NO code2- Post-Assertion Loop Invariant Algorithm ALG(Input) Pre-Cond: Input satisfies problem instance specifications Pre-Loop Code Loop Invariant if exit-condition then exit loop Post-Loop-Cond Post-Loop Code Post-Cond: output satisfies problem solution requirements Pre-Cond & Algorithm Code  Post-Cond Loop-Invariant  induction hypothesis Pre-Cond & Pre-Loop-code  Loop-Invariant  induction base Loop-Invariant & exit-cond & Loop-code  Loop-Invariant  induction Loop-Invariant & exit-cond  Post-Loop-Cond Post-Loop-Cond & Post-Loop-code  Post-Cond  clean up loose ends ASSERTIONS ALGORITHM ALG (Input) Pre-Cond: Input satisfies problem instance specifications Pre-Cond & Pre-Loop-code  Loop-Invariant Loop-Invariant & exit-cond  Post-Loop-Cond Post-Loop-Cond & Post-Loop-code  Post- -Loop Code Loop Invariant Loop-Invariant & exit-cond & Loop-code  Loop-Invariant exit-cond Post-Loop-Cond Post-Loop Code Post-Cond: output satisfies problem solution requirements Pre-Cond : input A[1..n] is an array of numbers, n 0 EXAMPLE PROBLEM: Sum of array items. Pre-Loop Code Incremental Method Loop Invariant NO star of the show: YES Start with the exit-cond Post-Loop-Cond the Loop Invariant. Post-Loop Code Post-Cond: output is sum of the items in the input array Pre-Cond : input A[1..n] is an array of numbers, n 0 Pre-Loop Code Loop Invariant: S = sum{A[1..t]} &... Incremental Method exit-cond Post-Loop-Cond Post-Loop Code Post-Cond: output is sum of the items in the input array Pre-Cond : input A[1..n] is an array of numbers, n 0 Pre-Loop Code Loop Invariant: S = sum{A[1..t]} &... Incremental Method Post-Cond: output is sum of the items in the input array exit-cond S = sum{A[1..n]} Post-Loop-Cond & Post-Loop-code  Post-Cond Pre-Cond : input A[1..n] is an array of numbers, n 0 Incremental Method Post-Cond: output is sum of the items in the input array Pre-Cond & Pre-Loop-code  Loop-Invariant Loop Invariant: S = sum{A[1..t]} &... Let’s not use “t = n”. Loop won’t terminate with bad input, e.g., n < 0. exit-cond S = sum{A[1..n]} Post-Loop-Cond & Post-Loop-code  Post-Cond Pre-Cond : input A[1..n] is an array of numbers, n 0 Incremental Method Post-Cond: output is sum of the items in the input array Pre-Cond & Pre-Loop-code  Loop-Invariant Loop Invariant: S = sum{A[1..t]} &... Let’s not use “t = n”. Loop won’t terminate with bad input, e.g.,n < 0. S = sum{A[1..n]} Post-Loop-Cond & Post-Loop-code  Post-Cond Pre-Cond : input A[1..n] is an array of numbers, n 0 Pre-Cond & Pre-Loop-code  Loop-Invariant Incremental Method Loop Invariant: S = sum{A[1..t]} &... S = sum{A[1..n]} S  S + A[t] Loop-Invariant & exit-cond & Loop-code  Loop-Invariant Post-Loop-Cond & Post-Loop-code  Post-Cond Post-Cond: output is sum of the items in the input array Pre-Cond : input A[1..n] is an array of numbers, n 0 Pre-Cond & Pre-Loop-code  Loop-Invariant Incremental Method Strengthen LI Loop Invariant: S = sum{A[1..t]} &... Loop-Invariant & exit-cond  Post-Loop-Cond S  S + A[t] S = sum{A[1..n]} Loop-Invariant & exit-cond & Loop-code  Loop-Invariant Post-Loop-Cond & Post-Loop-code  Post-Cond Post-Cond: output is sum of the items in the input array Pre-Cond : input A[1..n] is an array of numbers, n 0 Pre-Cond & Pre-Loop-code  Loop-Invariant LI changed. -Loop Code or Loop Code ? No revision needed. Lucky this time! Loop Invariant: S = sum{A[1..t]} & t  n S  S + A[t] Loop-Invariant & exit-cond & Loop-code  Loop-Invariant Loop-Invariant & exit-cond  Post-Loop-Cond S = sum{A[1..n]} Post-Loop-Cond & Post-Loop-code  Post-Cond Post-Cond: output is sum of the items in the input array Pre-Cond : input A[1..n] is an array of numbers, n 0 Termination: Measure of Progress: MP = n – t. Each iteration reduces MP by 1. Pre-Cond & Pre-Loop-code  Loop-Invariant Loop Invariant: Initial MP = n. Loop exits when S = sum{A[1..t]} &tn S  S + A[t] Loop-Invariant & exit-cond & Loop-code  Loop-Invariant We certify this is a correct algorithm! Loop-Invariant & exit-cond  Post-Loop-Cond # iterations = S = sum{A[1..n]} Post-Loop-Cond & Post-Loop-code  Post-Cond Post-Cond: output is sum of the items in the input array Algorithm SUM(A[1..n]) Pre-Cond: input A[1..n] is an array of numbers, n 0 S0; t0 Loop: Loop Invariant: S = sum{A[1..t]} & tn if t  n then exit loop t  t+1; S  S + A[t] S = sum{A[1..n]} Post-Cond: output is sum of the items in the input array end Pre-Cond & Algorithm Code  Post-Cond Loop-Invariant  induction hypothesis Pre-Cond & Pre-Loop-code  Loop-Invariant  induction base Loop-Invariant & exit-cond & Loop-code  Loop-Invariant  induction Loop-Invariant & exit-cond  Post-Loop-Cond Post-Loop-Cond & Post-Loop-code  Post-Cond  clean up loose ends ASSERTIONS Loop Invariant may need revision If LI is too strong, it may require too much effort to either establish or maintain it. Pre-Cond & Pre-Loop-code  Loop-Invariant Loop-Invariant & exit-cond & Loop-code  Loop-Invariant Loop-Invariant & exit-cond  Post-Loop-Cond Post-Loop-Cond & Post-Loop-code  Post-Cond If LI is too weak, it may not imply the induction, or may not imply the desired end goal. INCREMENTAL ALGORITHMS Incremental progress over time is an exponential multiplier. Water droplets gathered incrementally bring about a sea. -Persian proverb  Incremental Method & its Loop Invariant  Problems:  VLSI Chip Testing  In-place Tri-Partition  Maximum Sum Sub-Array  Longest Smooth Sub-Array Pre-Cond: S is a set of input objects C  ; Obtain Sol() Loop Invariant: CS & Sol(C) is solution to C Incremental Method This is generic. It may need to be strengthened in a given application. return Sol(C) Post-Cond: output is solution to S x  a selected object from S – C; C  C  {x}; Update Sol(C); Items are given to you one-by-one. You need to update solution before next object is given. Examples: SUM and on-line Insertion Sort. C=S & Sol(C) is solution to C You are given all input objects in advance of any computation. You may choose any previously unselected input object. Example: Selection Sort. Problem: VLSI Chip Testing [CLRS Problem 4-5, page 109]  Pre-Condition: Input is a set S of VLSI chips, each chip is either good or bad (unknown to us). Strictly more than half of these chips are good. (Note: this implies S  .)  Post-Condition: Output is one of the good chips from the input.  Notation: MTHG(S) = “More Than Half of the chips in S are Good”.  Primitive operation: Boolean Test(x,y) on any pair of chips x and y. Test(x,y) = True  x & y are either both good or both bad False  at least one of x or y is bad  Use this primitive operation to solve the problem.  Comment: If good and bad chips are 50-50, Test would be unable to break the good-bad symmetry. If less than 50% are good, that’s even worse! Where to start? • Brute Force: Compare each chip against every other chip. This requires O(n2) Tests. Can we do it faster, incrementally? • Incremental method could be quite effective! How? Suppose we pick a pair of chips x and y from S and invoke Test(x,y). • If Test(x,y) = False, then at least one of x or y is bad (the other is good or bad). We can discard both x & y (S  S – {x,y}, and proceed with what’s left). We still have MTHG(S). So, S still contains a good chip. There is hope !!! • If Test(x,y) = True, then what? If x & y both happen to be bad, then discarding both is still safe. But x & y could both be good. It’s unsafe to discard them both. Why? You no longer have the guarantee that MTHG(S)! You may have inadvertently discarded all the good chips! • How should we “repair” this shortcoming? Strengthen the Loop Invariant. ............................................ P.T.O. Strengthen the Loop Invariant • Notation: MTHG(S) = “More Than Half of the chips in S are Good”. AllGood(C) = “chips in set C are all good”. Uniform(C) = “chips in set C are either all good or all bad”. Note: [MTHG(C) & Uniform(C)]  [AllGood(C) & C]. • Strengthen Loop Invariant: In addition to MTHG(S), maintain a candidate subset C of the chips with the guarantee: Uniform(C). • Now, how can you maintain LI and make progress? Idea: pick xS – C and yC, then Test(x,y). What happens? What if S – C is empty? What if C is empty? non-candidate tested chips “discarded” Pre-Cond: input is a set S of n VLSI chips & MTHG(S). Pre-Cond & Pre-Loop-code  Loop-Invariant Incremental Method Loop-Invariant & exit-cond & Loop-code  Loop-Invariant Loop Invariant: C  S & Uniform(C) & MTHG(S) Loop-Invariant & exit-cond  Post-Loop-Cond Post-Loop-Cond & Post-Loop-code  Post-Cond xanarbitrarychipin S–C if C =  then C  C  {x} else do y  an arbitrary chip in C if Test(x,y) then CC{x} else CC–{y}; C   & AllGood(C) S  S – {x,y} return any one chip from C Post-Cond: output is a good chip from the input Measure of Progress: MP = |S – C| . # iterations  n. Algorithm VLSIChipTesting( S ) § takes O(n) Tests Pre-Cond: input is a set S of n VLSI chips & MTHG(S). Loop Invariant: C  S & Uniform(C) & MTHG(S) if C = S then exit loop xanarbitrarychipin S–C then C  C  {x} else do y  an arbitrary chip in C if Test(x,y) then CC{x} else CC–{y}; SS–{x,y} end-do C   & AllGood(C) return any one chip from C Post-Cond: output is a good chip from the input end INPUT: OUTPUT: INPUT: OUTPUT: Problem: In-Place Tri-Partition An array A[1..n], where each item A[i]  {red, green, blue}, i=1..n. A permutation of A[1..n] so that all red items appear first, then all green items, then all blue items. Same colour items can appear in any order within their colour group. 1 2 3 4 5 6 7 8 9 10 11 12 3 10 7 11 8 4 5 2 6 1 9 12 Restriction: This has to be done in-place, within array A. We are allowed to use only O(1) additional scalar variables (e.g., array indices). [We cannot use O(n) additional memory cells such as lists.] Applications: Partitioning in QuickSort & QuickSelect, In-place bucketing, etc. CLAIM: We can do this partitioning in O(n) time incrementally. The Loop Invariant not processed yet Loop Invariant: • A[1..R-1] are all reds. • A[R..G-1] are all greens. • A[B+1..n] are all blues. • 1RGB+1n+1. Measure of Progress: # unprocessed items. MP = B – G +1. Exit Condition: G > B. (i.e., all items processed)
Establish Loop Invariant:
(R, G, B)  (1, 1, n).
i.e., all n items are unprocessed.
Maintain LI & Make Progress:
Reduce MP while maintaining LI? How? Process A[G]. What’s its colour?
If A[G] = green then G++
If A[G] = blue
then A[G]  A[B]; B–
If A[G] = red
then A[G]  A[R]; R++; G++

Another Loop Invariant
not processed yet
Exercise 1:
Solve the 3-partition problem in-place in O(n) time, using the alternative Loop Invariant shown above.
Exercise 2:
Generalize the 3-partition problem to 4-partition, 5-partition, …
In general, for any integer C, 2  C  n, show that the C-partition problem can be solved in O(Cn) time, using O(C) extra memory cells.
Therefore, if C is any constant, the C-partition problem can be solved in O(n) time, using O(1) extra memory cells.

Problem: Maximum Sum Sub-Array
 INPUT: an array A[1..n] of arbitrary real numbers (positive, zero, negative). OUTPUT: a contiguous sub-array, say A[i+1..j], of A[1..n] with max element
sum (i.e., A[i+1] + A[i+2] + ··· + A[j] is max possible).
 Example: [ 2, 1, -6, -3, 2, -4, 6, -2, -1, 1, 3, -4, 7, -5, 2, -3, 2, 1 ].
 Brute Force Method: Try every sub-array A[i+1..j], for all 0  i  j  n. This can be done in O(n2) time. How?
We can obtain sum(A[i+1..j]) in O(1) time if we first spend O(n) pre-processing time to obtain PrefixSum[0..n], where
PrefixSum[t] = sum(A[1..t]), for t=0,1,…,n, (computed incrementally):
PrefixSum[0]  0; for t  1..n do PrefixSum[t] PrefixSum[t-1]+A[t] Now, sum(A[i+1..j]) = PrefixSum[j] – PrefixSum[i].
 Can we solve the problem in sub-quadratic time incrementally?
Let’s try ………………………………………………………………………. P.T.O.

Incremental Solution
 A[1..t] = prefix of A considered incrementally so far.
 Suppose maximum sum subarray of A[1..t] is A[i+1..j], Let’s denote that solution by:
BestSol(t) = A[i+1..j], and SolSum(t) = sum(A[i+1..j]).
 Loop Invariant: BestSol(t) = A[i+1..j], tn, SolSum(t) = sum(A[i+1..j]),
and … (?)
0  i  j  t  n.
1i jtt+1 n A BestSol(t) A[t+1]
BestSol(t) & SolSum(t) & A[t+1]  BestSol(t+1) & SolSum(t+1)
Enough info in Loop Invariant?

Examine the Loop Invariant
LI(t) & A[t+1]
BestSol(t) = A[i+1..j], SolSum(t) = sum(A[i+1..j]), A[t+1]
Maintain LI
& progress
BestSol(t+1) = ?, SolSum(t+1) = ?
which case are we in?
Case 1: A[t+1] is not part of BestSol(t+1): BestSol(t+1) = BestSol(t) and
SolSum(t+1) = SolSum(t).
Case 2: A[t+1] is part of BestSol(t+1): BestSol(t+1) = a suffix of A[1..t+1].
Which suffix?
LI is not strong enough. It should also tell us what is the
maximum sum suffix of A[1..t] and its element sum.
1 t t+1 n A
Best Suffix

Revise the Loop Invariant
Best Suffix
BestSol(t) = A[i+1..j], tn, SolSum(t) = sum(A[i+1..j]),
maintain LI & progress
LI(t+1) (the one with bigger sum):
1) A[t+1] excluded:
BestSuffix(t+1) = A[t+2..t+1] (i.e., nil) SuffixSum(t+1) = 0
2) A[t+1] included:
BestSuffix(t+1) = (BestSuffix(t) , A[t+1]) SuffixSum(t+1) = SuffixSum(t) + A[t+1]
BestSol(t+1) = BestSol(t) or BestSuffix(t+1), whichever has bigger sum.
Loop Invariant:
LI(t) & A[t+1]
BestSuffix(t) = A[k+1..t], SuffixSum(t) = sum(A[k+1..t])
SuffixSum(t+1) is better of two choices
BestSol(0) SolSum(0)
 A[1..0] (nil)  0
establish LI
BestSuffix(0)  A[1..0] SuffixSum(0)  0

Pre-Cond: input is an array A[1..n] of arbitrary integers.
(i, j, k, t)  (0, 0, 0, 0) SolSum  SuffixSum  0
Loop Invariant:
BestSol(t) = A[i+1..j], tn, SolSum = sum(A[i+1..j]), BestSuffix(t) = A[k+1..t], SuffixSum = sum(A[k+1..t])
Incremental Method
if SuffixSum + A[t] > 0
BestSol(n) = A[i+1..j]
return A[i+1..j]
Post-Cond: output is max-sum-subarray of input
then SuffixSum  SuffixSum + A[t] else SuffixSum  0; k  t
if SolSum < SuffixSum then SolSum  SuffixSum; (i, j)  (k, t) MP = n – t. # iterations  n. Algorithm MaxSumSubArray( A[1..n] ) § takes O(n) time Pre-Cond: input is an array A[1..n] of arbitrary integers. (i, j, k)  (0, 0, 0) § t  0 SolSum  SuffixSum  0 for t  1 .. n do Loop Invariant: BestSol(t) = A[i+1..j], SolSum = sum(A[i+1..j]), BestSuffix(t) = A[k+1..t], SuffixSum = sum(A[k+1..t]) if SuffixSum + A[t] > 0
then SuffixSum  SuffixSum + A[t] else SuffixSum  0; k  t
if SolSum < SuffixSum then SolSum  SuffixSum; (i, j)  (k, t) end-for BestSol(n) = A[i+1..j] return A[i+1..j] 程序代写 CS代考 加微信: cscodehelp QQ: 2235208643 Email: kyit630461@163.com

Posted in Uncategorized

Leave a Reply

Your email address will not be published. Required fields are marked *