Com S 311 Section B Introduction to the Design and Analysis of Algorithms
Lecture Two for Week 2
Xiaoqiu (See-ow-chew) Huang
Iowa State University
February 4, 2021
Floors and Ceilings
For any integer n, we have n + n = n.
22
This was proved before.
For any real number x ≥ 0 and integers a,b > 0, we have ⌈x ⌉
a = x , (3.4) b ab
⌊x ⌋
a = x . (3.5) b ab
Floors and Ceilings
Define k = x . Then x = abk + s for some real number s with ab
0 ≤ s < ab.
If s = 0, then each side in (3.4) and (3.5) becomes k, so (3.4) and
(3.5) hold. Consider the case where 0 < s < ab. Note that
x =k+1. ab
Dividing each side by a, we have 0 < s/a < b. By (3.3) and the definition of s , we have
ss a 0
bb
a≤ a−(b−1). (3.7)
bb
By (3.3), we have a 0, then the polynomial p(n) is asymptoticaly positive and we can show that p(n) is in Θ(nd).
A function f (n) is polynomially bounded if f (n) is in O(nk ) for some constant k.
Exponentials
For any real number a > 0 and any integers m and n, the following identities hold:
a0 = 1,
a1 = a,
a−1 = 1/a,
(am)n = amn = (an)m, aman = am+n.
Any exponential function with a base strictly greater than 1 grows faster than any polynomial function. For example, 2n grows much faster than nd for any nonnegative integer d.
For any real number x, the exponential function ex is of the
following form
ex =1+x+x2 +x3 +…=∞ xi, 2! 3! i=0 i!
where e ≈ 2.71828 is the base of the natural logarithm function.
Logarithms
The following notations are used in the analysis of algorithms: lg n = log2 n (binary logarithm),
ln n = loge n (natural logarithm), lgk n = (lg n)k (exponentiation),
lg lg n = lg(lg n) (composition).
An important notational convention: lg n + k = (lg n) + k, not lg(n + k).
Logarithms
For all real a > 0, b > 0, c > 0, and n, the following identities are useful:
a = blogb a,
logc (ab) = logc a + logc b, logb an = n logb a,
log a=logca, b logc b
logb (1/a) = − logb a, loga= 1 ,
b loga b alogb c = clogb a,
where the logarithm bases are not 1.
The Maximum-Subarray Problem
For an array A[1..n] of positive and negative values, the score S(i,j) of a subarray A[i..j] with i ≤ j is the sum of all values in the subarray:
S(i,j) = jk=i A[k] for i ≤ j.
The maximum-subarray problem is to find a subarray A[i..j] with i ≤ j such that its score is the maximum over all subarrays. This subarray is called a maximum subarray.
Array index
1 2 3 4 5 6 7 8 9 10 11 12
-15 20 35 -5 25 -30 10 -20 15 -5 10 -14
Array values
The Maximum-Subarray Problem
ThescoreofasubarrayA[2..5]is20+35−5+25=75. This subarray is a maximum subarray.
The number of subarrays is Θ(n2). Thus, an algorithm that generates every subarray would take Ω(n2) time.
We use divide-and-conquer to design an efficient algorthm for finding the maximum subarray in O(n log n) time.
The algorithm consists of a recursive procedure, which calls itself on the whole input array A[1..n] to find its maximum subarray.
The Maximum-Subarray Problem
In general form, the procedure finds a maximum subarray of the subarray A[low..high].
Set mid = ⌊(low + high)/2⌋.
The maximum subarray is either entirely located in the subarray A[low ..mid ], or entirely located in the subarray A[mid + 1..high], or contains the positions mid and mid + 1.
The maximum subarray is found by finding maximum subarrays of A[low ..mid ] and A[mid + 1..high] and A[i ..mid , mid + 1..j ] with low ≤ i ≤ mid < j ≤ high, and by taking one with the largest score of the three.
1 2 3 4 5 6 7 8 9 10 11 12
-15 20 35 -5 25 -30 10 -20 15 -5 10 -14
low = 1, high = 12, mid = floor((1+12)/2) = 6
1 2 3 4 5 6 7 8 9 10 11 12
[-15 20 35 -5 25 -30][10 -20 15 -5 10 -14]
low = 1, high = 6, mid = 3 low = 7, high = 12, mid = 9
1 2 3 4 5 6 7 8 9 10 11 12
[-15 20 35][-5 25 -30][10 -20 15] [-5 10 -14]
low = 1,
high = 3,
mmid = 2
low = 4,
high = 6,
mid = 5
low = 7,
high = 9,
mid = 8
low = 10,
high = 12,
mid = 11
1 2 3 4 5 6 7 8 9 10 11 12
[-15 20] [35][-5 25][-30][10 -20] [15] [-5 10][-14]
low = 1,
high = 2,
mid = 1
low = 4,
high = 5,
mid = 4
low = 7,
high = 8,
mid = 7,
low = 10,
high = 11,
mid = 10
1 2 3 4 5 6 7 8 9 10 11 12
[-15] [20] [35][-5] [25][-30][10][-20] [15] [-5] [10][-14]
Subar. size
2 (2, 2, 20)
3 (2, 3, 55)
6 (2, 5, 75)
12 (2, 5, 75) is better than (2, 7, 55) containing
the positions mid (= 6) and mid + 1 ( = 7)
FIND-MAXIMUM-SUBARRAY(A, low, high)
1 if high = low // subarray of one value
2 3 4
5
return (low, high, A[low]) elsemid=floor((low+high)/2)
(left-low, left-high, left-sum) =
FIND-MAXIMUM-SUBARRAY(A, low, mid)
(right-low, right-high, right-sum) =
FIND-MAXIMUM-SUBARRAY(A, mid+1, high)
Max subarray: (FirstIndex, LastIndex, Score)
(5, 5, 25)
(5, 5, 25)
(7, 7, 10) (11, 11, 10)
(9, 9, 15) (11, 11, 10)
(9, 11, 20)
6 7
8 9
10 11
1 2 3 4 5 6 7 8 9
(cross-low, cross-high, cross-sum) =
FIND-MAX-CROSSING-SUBARRAY(A, low, mid, high)
if left-sum >= right-sum and
left-sum >= cross-sum
return(left-low, left-high, left-sum)
elseif right-sum >= left-sum and
right-sum >= cross-sum
return(right-low, right-high, right-sum)
else return (cross-low, cross-high, cross-sum)
FIND-MAX-CROSSING-SUBARRAY(A, low, mid, high)
left-sum = negative infinity
sum = 0 // Finds a maximum left portion
for i = mid downto low
sum = sum + A[i]
if sum > left-sum
left-sum = sum
max-left = i
right-sum = negative infinity
sum = 0 // Finds a maximum right portion
10
11
12
13
14
15
for j = mid + 1 to high
sum = sum + A[j]
if sum > right-sum
right-sum = sum
max-right = j
return (max-left, max-right, lest-sum + right-sum)
Analysis of FIND-MAXIMUM-SUBARRAY
We can show that the algorithm is correct by formulating and proving loop invariants. The proof is omitted.
Let the running time of FIND-MAXIMUM-SUBARRAY on an array of n values be bounded from above by T(n).
Based on the above analysis, we obtain the following recurrence for T (n) for some constant d > 0.
T(1) = d,
T (n) = T ( n ) + T ( n ) + dn if n > 1. 22
Analysis of FIND-MAXIMUM-SUBARRAY
Assume that n is a perfect power of 2. Then the recurrence for T(n) becomes
T (n) = 2T (n/2) + dn if n > 1.
We show by mathematical induction that
T (n) ≤ cn lg n + en if n ≥ 2. (1)
Base: We show that (1) holds at n = 2. The left side:
T(2) = 2T(1)+d2 = 2d +2d = 4d.
The right side:
c 2 lg 2 + e 2 = 2c + 2e ≥ 4d = T (2) if c ≥ d and e ≥ d .
Analysis of FIND-MAXIMUM-SUBARRAY
Induction: Assume that
T(n/2) ≤ c(n/2)lg(n/2)+e(n/2) for some n/2 ≥ 2.
Then we show that (1) holds. By the assuption, the left side becomes:
T(n) = 2T(n/2)+dn ≤ 2(c(n/2)lg(n/2)+e(n/2))+dn
= cn(lg n − lg 2) + en + dn = cn lg n − cn + en + dn ≤ cn lg n + en if −cn + dn ≤ 0 or c ≥ d.
So set c and e to d > 0. We have
T (n) ≤ dn lg n + dn ≤ 2dn lg n if n ≥ 2.
If n is not a power of 2, then we use the previous proof to show thatT(n)≤cnlgnforeveryn≥n0 forsomec>0andn0 >0.