### CS2223 Algorithms. D-2008     Exam 1 - March 28, 2008

#### Prof. Carolina Ruiz. Department of Computer Science. Worcester Polytechnic Institute.

By Prof. Ruiz

Instructions

• Use the space provided to write your answers
• Ask in case of doubt

#### Problem I. Asymptotic Growth Rates (20 points)

Rigorously prove the following property:
For any positive functions f(n), g(n), and h(n): If f(n) = O(h(n)) and g(n) = O(h(n)) then f(n) + g(n) = O(h(n))
• Remember that your proof must be general: it should apply to any positive functions f(n), g(n), and h(n) that satisfy the stated assumptions.
• Remember that your proof needs to be rigorous. It is not enough to give the intuition underlying the property to be proved. You need to use the definition of a function being big O ("order") of another function, and specify the necessary constants c's and n0's.

#### Solution:

In order to show that f(n)+g(n) = O(h(n)), we need to find constants k and n0 such that for all n ≥ n0, f(n)+g(n) ≤ kh(n). Since f(n) = O(h(n)) and g(n) = O(h(n)) then by definition:
• ∃ k1 ∃ n1 ∀ n ≥ n1, f(n) ≤ k1h(n).
• ∃ k2 ∃ n2 ∀ n ≥ n2, g(n) ≤ k2h(n).
Take k = k1 + k2, and n0= max(n1,n2). Then
f(n)+g(n) ≤ k1h(n) + k2h(n) = (k1 + k2)h(n) = kh(n), for all n ≥ n0.
Hence f(n)+g(n) = O(h(n)).

#### Problem II. Asymptotic Growth Rates (15 points)

Let f(n)= 22n, and g(n)= 2n determine whether f(n) = O(g(n)), or f(n) = Ω(g(n)), or both (i.e., f(n) = Θ(g(n))), or none of the above. Provide a precise proof of your answer.

#### Solution:

Remember that 22n = 2n+n = 2n*2n. Hence:
limn→inf(f(n)/g(n)) = limn→inf(22n/2n) = limn→inf(2n*2n/2n) = limn→inf(2n) = infinity.
Therefore, by the theorem stated in class, f(n) = Ω(g(n)).

#### Problem III. Analysis of Algorithms (45 points + 10 extra credit points)

Consider the stable matching problem discussed in class and in the textbook. Given a list of n men, n women, their "inverse" tables of preferences (as used in Homework 1), and a perfect matching (i.e., a bijection between the men and the women), the following algorithm determines whether or not the perfect mathing is stable.

Input:

• n: The number of men (1,...,n) = number of women (1,...,n)
• A 2-dimensional array: InverseMenPrefer[m,w] with 1 ≤ m,w ≤n. InverseMenPrefer[m,w] = i if woman w is the ith preferred woman on man m's preference list (1st being the most preferred one).
• A 2-dimensional array: InverseWomenPrefer[w,m] with 1 ≤ w,m ≤n. InverseWomenPrefer[w,m] = j if m is the jth preferred man on woman w's preference list (1st being the most preferred one).
• two arrays wife[m] and husband[w], with 1 ≤ m,w ≤n so that if m is matched to w then wife[m]=w and husband[w]=m.

Output:

• true, if the perfect matching given in the arrays wife and husband is stable with respect to InverseMenPrefer and InverseWomenPrefer, or
• false, otherwise, that is, if there exists an unstable pair (m,w) such that m and w prefer each other over their current spouses.

Algorithm: (See next page)
 Instruction Time taken per instruction Number of iterations ```{ stable := true . . . . . . . . . . . . . . . . . . m := 1 . . . . . . . . . . . . . . . . . . while stable AND m ≤ n do { . . . . . . . . . . . . . w := 1 . . . . . . . . . . . . . . . . . . . while stable AND w ≤ n do { . . . . . . . . . . . . . . (* we'll check below if (m,w) is an unstable pair *) if (InverseMenPrefer[m,w] < InverseMenPrefer[m,wife[m]]) AND (InverseWomenPrefer[w,m] < InverseWomenPrefer[w,husband[w]]) . . then { stable := false . . . . . . . . . . . . . } w := w + 1 . . . . . . . . . . . . . . . . . . . } m := m + 1 . . . . . . . . . . . . . . . . . . . } return(stable) . . . . . . . . . . . . . . . . . . . } ``` ```C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 ``` ```1 1 --------- | | | -- | | | | | | | | n | n |times |times | | | | | | | | | | -- | | --------- 1 ```

1. (20 points) Prove that the algorithm is correct. That is, it returns true if the given perfect matching is stable, and false if it is unstable. Your proof should decisively prove each of these two cases.

#### Solution:

Let's start by noting that the "if condition"
```    (InverseMenPrefer[m,w] < InverseMenPrefer[m,wife[m]])
AND
(InverseWomenPrefer[w,m] < InverseWomenPrefer[w,husband[w]])
```
is true
if and only if man m prefers woman w over his wife and w prefers m over her husband
if and only if the pair (m,w) is unstable
if and only if the input perfect matching is unstable.

Let's show now that the algorithm always outputs the correct answer for the given input perfect matching:

• If the input perfect matching is stable, then no unstable pair exists and hence the if condition is never true. Then, the variable "stable", which has been set to true at the beginning of the program, is never set to false, and the program correctly outputs "true".
• If the input perfect matching is unstable, then there is at least one unstable pair (m,w) that makes the if condition true. Then, the variable "stable" is set to false, stopping the iterations of both while loops, and making the program correctly output "false".

2. (25 points) Analyze the runtime of your algorithm as a function of n.
• (5 points) In the table above state how much time the execution of each instruction would take.
• (5 points) In the table above state which instructions would be repeated and how many times they would be repeated in the worst case.
• (5 points) Combine here the full runtime of the algorithm:

#### Solution:

```        T(n) = C1 + C2 + [C3 + C4 + [C5 + C6 + C7 + C8]*n + C9]*n + C10
= C' + [C'' + C'''*n]*n
= C' + C''n + C'''n2

where:

C' = C1 + C2 + C10
C'' = C3 + C4 + C9
C''' = C5 + C6 + C7 + C8
```

• (10 points) Using worst case analysis, provide an asymptotic tight bound g(n) for your T(n) function above and prove in detail that T(n) = Θ(g(n)).

#### Solution:

T(n) = C' + C''n + C'''n2. Let g(n) = n2.
In order to show that T(n) = Θ(g(n)) we need to find constants k1, k2, and n0 such that for all n ≥ n0, k1n2 ≤ T(n) ≤ k2n2.
Note that:
• T(n) = C'+ C''n + C'''n2 ≤ C'n2 + C''n2 + C'''n2 = (C'+ C''+ C''') n2 = (C'+ C''+ C''') g(n), for all n ≥ 1, and
• T(n) = C'+ C''n + C'''n2 ≥ C'''n2 = C'''g(n), for all n ≥ 0.
Hence ∃ k1=C''' ∃ k2=(C'+ C''+ C''') ∃ n0=max(0,1) ∀ n ≥ n0, k1g(n) ≤ T(n) ≤ k2g(n). Therefore T(n) = Θ(g(n)).
3. (10 extra credit points) Consider now best case analysis.
• (5 points) What is the best case scenario for this algorithm? That is, given a fixed value n > 0, what property should the rest of the input satisfy so that the algorithm will run for the least possible amount of time for that input of size n?

#### Solution:

The perfect matching should be such that m1 and w1 (the 1st man and the 1st woman) form an unstable pair. For this particular case, the runtime of the algorithm would be:
T(n) = C1 + C2 + C3 + C4 + C5 + C6 + C7 + C8 + C9 + C10, that constant.
• (5 points) Provide an asymptotic lower bound h(n) for your T(n) function in this best case scenario and argue that T(n) = Ω(h(n)).

#### Solution:

T(n) = C' + C''n + C'''n2. Let h(n) = 1.
In order to show that T(n) = Ω(h(n)) we need to find constants k and n0 such that for all n ≥ n0, T(n) ≥ k*1.
Note that: T(n) = C'+ C''n + C'''n2 ≥ 1 for all n ≥ 1. Hence ∃ k=1 ∃ n0=1 ∀ n ≥ n0, T(n) ≤ k*1. Therefore T(n) = Ω(h(n)).

#### Problem IV. Time Complexity (20 points)

This problem consists of two unrelated parts.
• (10 points) Consider two algorithms A and B that take time in Θ(n2) and Θ(n3), respectively, to solve the same problem. If other resources such as storage and programming time are of no concern, is it necessarily the case that algorithm A is always preferable to algorithm B? Justify your answer.

#### Solution:

No. Let TA and TB be the runtime functions of algorithms A and B, respectively. By definition, of Θ, TA(n) has the same growth rate as n2 for large enough n's (that is, for n ≥ nA for some constant nA ≥0), and TB(n) has the same growth rate as n3 for large enough n's (that is, for n ≥ nB for some constant nB ≥0). But for some n0 < max(nA,nB), it might happen that TA(n0) > TB(n0), and then B would be preferable to A on inputs of size n0.
• (10 points) (This part is unrelated to the previous part.) Consider two algorithms C and D that take time in O(n2) and O(n3), respectively. Could there be an implementation of algorithm D that would be more efficient (in terms of computing time) than an implementation of algorithm C on each and every possible input? Justify your answer.

#### Solution:

Yes. Note that O(.) does not provide tight bounds. Take for example f(n)=n2+n and g(n)=n. It is true for these functions that f(n)=O(n2) and g(n)=O(n3). Nevertheless, g(n) ≤ f(n) for all n, and hence an implementation of algorithm D can be more efficient than an implementation of algorithm C.