Week 1 - Algorithm PDF

Preview

Summary

Week 1 - Algorithm...

Description

Tutorial Solutions 1

comp2823

Solution 1.

√

n, n, n log n, n3 , 2n ,

s1 2019

3n , n!, nn n2

Solution 2. 1

n log n , log log n, 2log log n , log n!

Solution 3. a) The first iteration prints 1 star, second prints two, third prints three and so on. The total number of stars is 1 + 2 + · · · + n, namely, n

∑ j =1

n

j≤

∑ n = n2 = O ( n2 ) . j =1

b) Assume for simplicity that n is even. We lowerbound the number of stars printed during iterations 2n through n: n

n

j =1

j=n/2

∑j≥ ∑

n2 n = = Ω ( n2 ) . 2 4

Solution 4. a) The number of iterations is n + n − 1 + · · · + 1 = (2n), which is bounded by n2 . In the iteration corresponding to indices (i, j) we need to scan j − i + 1 entries from A, so it takes O ( j − i + 1) = O (n). Thus, the overall time is O (n3 ). b) In an implementation of this algorithm, Line 3 would be computed with a for loop; when i < 41n and j > 34 n, this loop would iterate least n/2 times, which takes Ω (n) time. There are n2 /16 pairs (i, j) of this kind, which is Ω (n2 ). Thus, the overall time is Ω (n3 ).

comp2823

Tutorial Solutions 1

s1 2019

Solution 5. The idea is very simple, suppose we had at our disposal an array B whose ith entry is the entries i through n − 1 of A; in other words, B[i] =

n −1

∑ A[ k ]. k =i

B[i ]− B[ j+1] Then C [i][ j] is simply j−i+1 . If we can compute B in O (n2 ) time we are done. In fact, we can compute B is just O (n) time.

1: 2: 3: 4: 5: 6: 7: 8:

function summing-up-fast(A) B [ n] = 0 for i = n − 1, . . . , 0 do B [ i ] = B [ i + 1] + A[ i ] for i = 0, . . . , n − 1 do for j = i, . . . , n − 1 do B[i ]− B[ j+1] C [i][ j] = j−i+1 return C

The correctness of the algorithm is clear since −1 A [ k ] j ∑kn=−i1 A[k] − ∑nk= B [ i ] − B [ j + 1] j +1 ∑k=i A[k] C [i][ j] = . = = j−i+1 j−i+1 j−i+1

as desired. For the time complexity, we note that the for loop in Line 3 runs in O (n) time and the nested for loops starting in Line 5 runs in O (n2 ) time, yielding the desired overall complexity. Solution 6. Since f = O ( g), it follows that there exists n0 > 0 and c > 0 such that f (n) ≤ cg(n) for all n > n0 . Since g = O (h), it follows that there exists n0′ > 0 and c′ > 0 such that g(n) ≤ ch (n) for all n > n0 . It follows that for all n > max(n0 , n0′ ) we have f (n) ≤ c g(n) ≤ c c′ h(n). Thus, if we define n0′′ = max(n0 , n′0 ) and c′′ = c c′ , the above inequality means f = O ( h ). Solution 7. The straightforward solution is to do a double for loop over the entries of the array returning “found duplicates” right away when we find a pair of identical elements, and “found no duplicates” at the end if we exit the for loops. The complexity of this solution is O (n2 ). A better solution is to sort the elements and then do a linear time scan testing adjacent positions. As we shall see later in class one can sort an array of length n in O (n log n) time.

Tutorial Solutions 1

comp2823

s1 2019

Solution 8. a) We only sketch the instance. Consider the following preference lists m1 w1 w2 · · · m2 w2 w3 · · · .. .

wn − 1 wn

wn w1

mn wn w1 · · ·

wn − 2 wn − 1

w1 m1 m2 · · · w2 m1 m2 · · · .. .

m n −1 m n m n −1 m n

wn m 1 m 2 · · ·

m n −1 m n

Each man proposes to a free woman, so there only n proposals.

b) We only sketch the instance. Consider the following preference lists m1 w1 w2 · · · m2 w1 w2 · · · .. .

wn − 1 wn wn − 1 wn

w1 m1 m2 · · · w2 m1 m2 · · · .. .

m n −1 m n m n −1 m n

mn w1 w2 · · ·

wn − 1 wn

wn m 1 m 2 · · ·

m n −1 m n

Imagine mn proposes first, followed by mn−1 and so on up to m1 . Each man proposes to w1 , who progressively gets a better partners and ends up with m1 . This involves n proposals. In a second round, mn proposes to w2 , followed by mn−1 , and so on up to m2 . Again, w2 gets progressively better partners and ends up with m2 . This involves another n − 1 proposals.

This keeps going on until mn finally proposes to wn and the algorithm terminates, having made a total of n + n − 1 + · · · + 1 = Ω (n2 ) proposals....