# CS代写 – cscodehelp代写

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

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