[Solved] CS344 Problem Set 1

1. Big-O notation. We have learnt big-O notation to compare the growth rates of functions, this exercise helps you to better understand its definition and properties.

(a) (10 points) Suppose n is the input size, we have the following commonly seen functions in complexity analysis: f₁(n) = 1,f₂(n) = logn,f₃(n) = n,f₄(n) = nlogn,f₅(n) = n²,f₆(n) = 2ⁿ. Intuitively, the growth rate of the functions satisfy 1 < logn < n < nlogn < n² < 2ⁿ. Prove this is true.

[Hint: You are expected to prove the following asymptotics by using the definition of big-O notation: 1 = O(logn),logn = O(n),n = O(nlogn),nlogn = O(n²),n² = O(2ⁿ). Note: Chap 3.2 of our textbook provides some math facts in case you need.]

Answer:

Using The Definition:f(n) is O(g(n)) if and only if there exists positive constants C and k such that |f(n)| <= C |g(n)| for all n >= k.

Note: All of the log is base on 10.

let f(n) = 1,g(n) = logn 1 C logn (for all n k) choose k = 10

1 C logn (for all n 10)

(for all n 10) choose C = 1

1 1 logn (for all n 10) 1 logn (for all n 10) that always true. So f(n) = O(g(n)) implies 1 = O(logn)

let f(n) = logn,g(n) = n logn C n (for all n k) choose k = 10 logn C n (for all n 10)

(for all n 10) choose

logn C n (for all n 10) (for all n 10) (for all n 10) that always true. So f(n) = O(g(n)) implies logn = O(n)

let f(n) = n,g(n) = nlogn n C nlogn(for all n k) choose k = 10 n C n logn(for all n 10) 1 C logn (for all n 10) choose C = 1 n C n logn(for all n 10)

1 logn (for all n 10) that always true. So f(n) = O(g(n)) implies n = O(n logn)

let f(n) = nlogn,g(n) = n² nlogn C n² (for all n k) choose n = 10 nlogn C n² (for all n 10) logn C n (for all n 10)

(for all n 10) choose

(for all n 10)

(for all n 10) (for all n 10) that always true. So f(n) = O(g(n)) implies nlogn = O(n²)

let f(n) = n²,g(n) = 2ⁿ n² C 2ⁿ (for all n k) choose k = 1 n² C 2ⁿ (for all n 1)

(for all n 1) choose

(for all n 1)

(for all n 1)

(for all n 1) that always true. So f(n) = O(g(n)) implies n² = O(2ⁿ)

In sum, we can get that he growth rate of the functions satisfy 1 < logn < n < nlogn < n2 < 2n.

(b) (10 points) Let f,g : N R⁺, prove that O(f(n) + g(n)) = O(max{f(n),g(n)}).

[Hint: The key is max{f(n),g(n)} f(n) + g(n) 2 max{f(n),g(n)}. Note: Proving this will help you to understand why we can leave out the insignificant parts in big-O notation and only keep the dominate part, e.g., O(n²+nlogn+n) = O(n²).] Answer:

Given f,g : N R⁺ f(n) f(n) + g(n),g(n) f(n) + g(n)

Therefore, max{f(n),g(n)} f(n) + g(n)

Let max{f(n),g(n)} = f(n)

Therefore, g(n) max{f(n),g(n)}

Thus, f(n) + g(n) 2max{f(n),g(n)}

Let max{f(n),g(n)} = g(n)

Therefore, f(n) max{f(n),g(n)}

Thus, f(n) + g(n) 2max{f(n),g(n)}

From above, we can get that max{f(n),g(n)} f(n) + g(n) 2max{f(n),g(n)}

From f(n) + g(n) 2max{f(n),g(n)} for every n 1 We can get that f(n) + g(n) = O(max{f(n),g(n)}.

From max{f(n),g(n)} f(n) + g(n) for every n 1

We can get that max{f(n),g(n)} = f(n) = g(n)

In sum, O(f(n) + g(n)) = O(max{f(n),g(n)}), for f,g : N R⁺.

2. Proof of correctness. (10 points) We have the following algorithm that sorts a list of integers to ascending order. Prove that this algorithm is correct. [Hint: You are expected to use mathematical induction to provide a rigorous proof.]

Answer:

Invariant of outer loop: At start of iteration the outer for loop,A[0 : i 1] is sorted. Invariant of inner loop: at start of iteration the inner for loop, A[min_index] is the smallest value from A[i : j].

Algorithm 1: Sort a list

Input: Unsorted list A = [a₁,,a_n] of n items

Output: Sorted list items in ascending order for i = 0, i < n 1, i++ do

Initialization:

Prior to the first iteration of outer loop, A[0] is the A[minindex], the array A[1 : i1] is empty.

Prior to the first iteration of inner loop, the sub-array A[j : n] contains the single value.

Maintenance:

The invariant holds at the start of the iteration j = i + 1 of the inner for loop. At the start of the first iteration, A[i]is the A[min_index], then comparing the all elements with A[min_index] from A[j : n]. The smallest value instead of the A[min_index], became the new A[min_index].

At the end of each outer loop, swapping the A[i],A[min_index]. Therefore, the sub array is sorted from A[0 : i].

Termination:

When i = n 1,the outer for loop is ended. All values in A[0 : n 2] are sorted and A[length 1] is biggest value from A[0 : n 1], therefore, all values in A[0 : n 1] are sorted.

when i = n 1,j = n, the inner for loop is ended. A[n 1] is smallest value from a[n 1 : n].

3. Practice the recursion tree. (10 points) We have already had a recurrence relation of an algorithm, which is T(n) = 2T(n/2) + 3n. Solve this recurrence relation, i.e. express it as T(n) = O(f(n)), by using the recursion tree method. [Note: If you find it difficult to draw a picture using Latex directly, you can draw it using Microsoft PowerPoint and then save it as a picture file (.png or .jpg), or you can draw on a piece of paper by hand, and take a picture of it using your phone. Then, you can insert the picture into your latex code and compile it into the final PDF submission. The following code shows an example of how to insert figures in latex code, as shown in Figure 1.]

Answer:

Figure 1: recursion tree.

4. Practice with the iteration method. We have already had a recurrence relation of an algorithm, which is T(n) = 4T(n/2) + n² logn.

(a) (5 points) Solve this recurrence relation, i.e., express it as T(n) = O(f(n)), by using the iteration method.

Answer:

Note: all the log is base on 2.

Given T(n) = 4T(n/2) + n² logn.

Using the Iteration method: T(n/2) = 4T(n/2²) + (n/2)² log(n/2).

T(n) = 4T(n/2) + n² logn

T(n) = 4[4T(n/2²) + (n/2)² log(n/2)] + n² logn.

T(n) = 4²T(n/2²) + n² log(n/2) + n² logn

T(n) = 4²T(n/4) + n²[log(n/2) + logn]

As same we get that: T(n/4) = 4T(n/2³) + (n/2²)² log(n/2²)

T(n) = 4²T(n/4) + n²(log(n/2) + logn)

T(n) = 4²[4T(n/2³) + (n/2²)² log(n/2²)] + n² log(n/2) + n² logn

T(n) = 4³ T(n/2³) + n² log(n/2²) + n² logn/2) + n² logn

T(n) = 4³ T(n/2³) + n²[log(n/2²) + logn/2) + logn]

In sum,we can find that

Let n = 1,T(1) = n/2^k = 1

k

(b) (5 points) Prove, by using mathematical induction, that the iteration rule you have observed in 4(a) is correct and you have solved the recurrence relation correctly. [Hint: You can write out the general form of T(n) at the iteration step t, and prove that this form is correct for any iteration step t by using mathematical induction. Then by finding out the eventual number of t and substituting it into your general form of T(n), you get the O() notation of T(n).]

Answer:

Using the mathematical introduction

Base case: let n = 2,T(2) = 4T(2/2) + 4log2 = 4T(1) + 4 = 4c + 4 k(4log²(2)) So, T(2) = O(n² log²(2))is true. Assume T(n) = O(n² log² n)is true.

letn = k + 1

T(k + 1) = 4T(k + 1/2) + (k + 1)² log(k + 1)

T(k + 1) = 4[(k + 1/2)² log²(k + 1/2)] + (k + 1)² log(k + 1)

T(k + 1) = (k + 1)² log²(k + 1/2) + (k + 1)² log(k + 1)

T(k + 1) = (k + 1)² (log²(k + 1/2)] + log(k + 1)) k(k + 1)² log²(k + 1)

(log²(k + 1/2) + log(k + 1)) klog²(k + 1)

(log²(k + 1) log²(2) + log(k + 1)) klog²(k + 1) is true. So, we get that whenn = k + 1,T(k + 1) = O((k + 1)² log²(k + 1)) Thus, T(n) = O(n² log²(n)) is true.

5. Practice with the Master Theorem. Solve the following recurrence relations; i.e. express each one as T(n) = O(f(n)) for the tightest possible function f(n) using the Master Theorem, and give a short justification. Unless otherwise stated, assume T(1) = 1.

[To see the level of detail expected, we have worked out the first one for you.]

(z) T(n) = 6T(n/6) + 1. We apply the master theorem with a = b = 6 and with d = 0. We have a > b^d, and so the running time is O(n^log6(6)) = O(n).

• (5 points) T(n) = 3T(n/4) + n

Answer:

Using master method T(n) = a T(n/b) + O(n^d)

T(n) = 3T(n/4) + n we get that a = 3,b = 4,d = 1/2 bd = 41/2 = 2,a > bd

so, O(nlog_b(a) = O(nlog₄(3))

• (5 points) T(n) = 7T(n/2) + (n³)

Answer:

T(n) = 7T(n/2) + (n³) a = 7,b = 2,d = 3 b^d = 2³ = 8,a < b^d

So, O(n^d) = O(n³)

• (5 points) T(n) = 2T(n/3)+n^c, where c 1 is a constant that doesnt depend on n.

Answer:

T(n) = 2T(n/3) + n^c a = 2,b = 3,d = c 1 b^d 3 so, a < b^d, O(n^d) = O(n^c)

6. Proof of the Master Theorem. (15 points) Now that we have practiced with the recursion tree method, the iteration method, and the Master method. The Master Theorem states that, suppose T(n) = a T(n/b) + O(n^d), we have:

O(n^d logn), if a = b^d

d d

T(n) = O(n ), if a < b

O(nlogb a), if a > bd

Prove that the Master Theorem is true by using either the recursion tree method or the iteration method.

Answer:

Assume n = b^kandO(n^d) = n^d

T(n) = T(bk) = a T(bk1 + bkd = a(a T(bk2 + bd(k1)) + bkd

T(n) = a2 T(bk2) + abd(k1) + bkd

T(n) = a3 T(bk3 + a2 T(bd(k2)) + abd(k1) + bkd In sum, let p = b^d,q = a/r pk = bbk = (bk)d = nd,ak = alog_b(n) = nlog_b(a)

So, we get that

There are three situations in for different values of q. when a = b^d,d = log_b(a),p = a

Therefore,

when a < b^d,d > log_b(a),p > a

k

Therefore,

when a > b^d,d < log_b(a),p < a

Therefore,

7. Algorithm design. Each of n users spends some time on a social media site. For each i = 1,,n, user i enters the site at time a_i and leaves at time b_i a_i. You are interested in the question: how many distinct pairs of users are ever on the site at the same time? (Here, the pair (i,j) is the same as the pair (j,i)).

Example: Suppose there are 5 users with the following entering and leaving times:

User	Enter time	Leave time
1	1	4
2	2	5
3	7	8
4	9	10
5	6	10

Then, the number of distinct pairs of users who are on the site at the same time is three: these pairs are (1,2), (4,5), (3,5). (Drawing the intervals on a number line may make this easier to see).

(a) (10 points) Given input (a₁,b₁),(a₂,b₂),,(a_n,b_n) as above in no particular order (i.e., not sorted in any way), describe a straightforward algorithm that takes (n²)time to compute the number of pairs of users who are ever on the site at the same time, and explain why it takes (n²)-time. [We are expecting pseudocode and a brief justification for its runtime.]

Answer:

input: List containing the time interval of each users (a1,b1),(a2,b2),(a3,b3),(an,bn). There are n users.

for i = 0,i < n 1,i + + (outer loop) for j = i + 1,j < n,j + + (inner loop) if A[ai] >= A[bj]orA[bi] <= A[aj]

Output: (i,j)

We compare the each users time intervals with all the time intervals of the left users. if we find the overlap, we will output the serial numbers of two users with overlapping time.

Time complexity = n 1 + n 2 + n 3 + n 4 + + 1 = n (n 1)/2 = O(n²), because outer loop need to run from i = 0 to i = n 2. the inner loop need to run from j = i + 1toj = n 1.

(b) (10 points) Give an (nlog(n))-time algorithm to do the same task and analyze its running time. (Hint: consider sorting relevant events by time). [We are expecting pseudocode and a brief justification for its runtime.]

Answer:

Input: List containing the time interval of each users (a1,b1),(a2,b2),(a3,b3),(an,bn)

A = [a1,a2,a3an] of n users. (All of the start time) B = [b1,b2,b3..bn] of n users. (All of the end time)

Procedure insert(valueA, root) if (root == null) root= new node(valueA) return if (root.data > valueA) root.left = newnode(valueA) return if(root.data < valueA) if (root.right == null) root.right = newnode(valueA) return insert(valueA,root.right

for i = 0,i < n,i + + (outer loop) for j = 0,j < n,j + + (inner loop) if A[bi] <= A[aj]

Output: (i,j)(i + 1,j)..(n,j) end procedure

First, We put the start time and end time in two different arraysThen, we used the binary search tree to sort the array A with ascending. final, compare the users end time with all the start time of the users, when we find the end time is bigger than start time, the left start time have overlap with end time.

Time complexity O(logn) O(n) = O(logn n), because the big O of binary search tree is O(logn),every time, we need compare the two array n times.