[SOLVED] Cs5800 – algorithms problem set #1 problem #1 let f(n) and g(n) be two functions, defined for each positive integer n.

CS5800 – Algorithms
Problem Set #1
Problem #1
Let f(n) and g(n) be two functions, defined for each positive integer n.
By definition, f(n) = O(g(n)) if there exist positive constants c and n0 for which 0 ≤ f(n) ≤ cg(n)
for all integers n ≥ n0.
To prove that f(n) 6= O(g(n)) one must prove that no such constants c and n0 exist.
(a) Let f(n) = n
2 + 2n + 3. Prove that f(n) = O(n
2
) and f(n) 6= O(n).
(b) Let f(n) = n log n + 100n. Prove that f(n) = O(n log n) and f(n) 6= O(n).
NOTE: in this course, we will assume log n = log2 n = lg n.
(c) Let f(n) = 2n
2 + 4 and g(n) = 4n
2 + 2. Prove that f(n) = O(g(n)) and g(n) = O(f(n)).
(d) Let f(n) and g(n) be any two functions for which f(n) and g(n) are positive numbers, for each
integer n ≥ 1.
Prove or disprove: at least one of these two statements must be true:
f(n) = O(g(n)), g(n) = O(f(n)).
Clearly and carefully justify your answer.

Problem #2
Let f(n) and g(n) be two functions, defined for each positive integer n.
To prove that f(n) 6= O(g(n)) one must prove that no such constants c and n0 exist.
For each of these questions, show your step by step work
(a) Prove that 2n+1 = O(2n
).
(b) Prove or disprove: 22n = O(2n
)?.
(c) Let f(n) = lg(lgkn) and g(n) = lgk
(lgn). Prove which one is asymptotically larger.
(c) Let f(n) = lg3n and g(n) = lg9n. Prove the relationship between f(n) and g(n) in terms of upper
bound (big O), lower bound (Ω) and tight bound (Θ)

Problem #3
Consider an array, A, whose contents is integer values. Given a particular threshold value t, an event E
between indices i < j is a critical event if ai > t ∗ aj .
In this problem, write a full program that outputs the number of critical events for an arbitrary array of
integers and any arbitrary threshold value t.
(a) Submit the code of your working program (You can use any programming language). Note, you
need to upload your source file (TA’s will download and run the code- the code can be upload in
Canvas)
(b) Submit a screen capture showing that your program outputs correct values. You only need to repeat
over 2 different arrays running with 2 different threshold.
(c) Perform an analysis of your algorithm and report its time complexity.

Problem #4
Let {a1, a2, . . . , an} be an unsorted list of n numbers.
Bubble Sort is a well-known sorting algorithm that works as follows.
Iteration #1: Compare the first two numbers. If the first number is bigger than the second, then
swap the two numbers. Compare the second and third numbers, and swap them if necessary. Keep doing
this until we have compared the final two numbers. (After this iteration, can you see why the largest
number is guaranteed to be at the end?)
Iteration #2: Start from the beginning, comparing the first two numbers, and repeating the same process
as above. But this time we only look at the first n − 1 numbers, since we know the final number is already in the right position. (After this iteration, the two largest numbers are guaranteed to be at the end.)
We keep proceeding until the entire list has been sorted. Here is the pseudocode of Bubblesort.
for i = n down to 1
for j = 1 to i-1
if a[j]>a[j+1]
swap(a[j],a[j+1])
This sorting algorithm is known as Bubble Sort, because after each complete iteration the largest unsorted number “bubbles” to the end of the list. For example, if the initial list is {1, 7, 4, 5, 2}, we have
{1, 4, 5, 2, 7} after the first iteration, {1, 4, 2, 5, 7} after the second iteration, {1, 2, 4, 5, 7} after the third
iteration, and {1, 2, 4, 5, 7} after the fourth and final iteration. We now know that the list is sorted.
(a) Demonstrate the Bubble Sort algorithm on the input list {4, 3, 2, 1, 5}. Clearly show your steps.
(b) Let C(n) and S(n) be the total number of comparisons and swaps required by Bubble Sort when
the input list has n numbers. For example, in the list {1, 7, 4, 5, 2} above, Bubble Sort requires 10
comparisons and 5 swaps.
Suppose the input list is {n, n − 1, n − 2, . . . , 3, 2, 1}, where the numbers appear in reverse order. In this worst-case scenario, determine the exact formulas for C(n) and S(n). Clearly show all
of the steps in your proof.
(c) Determine a precise “loop invariant” for Bubble Sort, clearly stating your Initialization, Maintenance, and Termination statements. Prove that your loop invariant holds, clearly and carefully
justifying each step in your proof.
(d) Consider a random permutation of {1, 2, 3, . . . , n}. Determine an exact formula for the average
expected number of swaps required by Bubble Sort. Clearly and carefully justify your answer.