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 & j1 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 & in & in
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]} &tn
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
S0; t0 Loop:
Loop Invariant: S = sum{A[1..t]} & tn 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: CS & 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 xS – C and yC, 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
xanarbitrarychipin S–C if C = then C C {x} else do
y an arbitrary chip in C if Test(x,y)
then CC{x} else CC–{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
xanarbitrarychipin S–C
then C C {x} else do
y an arbitrary chip in C if Test(x,y)
then CC{x}
else CC–{y}; SS–{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.
• 1RGB+1n+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], tn, 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], tn, 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], tn, 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
