Assignment 1-Asymptotics

Assignment 1

 In the assignments, all logarithms are base 2, unless a different base is explicitly specified.
1 Asymptotics [10 marks]
Prove or disprove each of the following statements. (a) For any constant b 0, the function f : n 7→ 1 + b + b2 + b3 +···+ bn satisfies f(n) =(Θ(bn) if b 1 Θ(1) if b ≤ 1. (b) For every pair of functions f,g : Z+ →R≥1 that satisfy f = Θ(g), the functions F : n 7→ 2f(n) and G : n 7→ 2g(n) also satisfy F = Θ(G). (c) For every pair of functions f,g : Z+ →R≥1 that satisfy f = o(g), the functions F : n 7→ 2f(n) and G : n 7→ 2g(n) also satisfy F = o(G).
2 Solving recurrences [10 marks]
Solve the following recurrence relations to obtain a closed-form big-Θ expression for T(n). In each question, assume T(c) is bounded by a constant for any small constant c. (a) T(n) ≤ 9T(n 3) + n2 (b) T(n) ≤ 4T(n 4) + nlogn (c) T(n) ≤ T(n 4) + T(3n 4 ) + n (d) T(n) ≤√n·T(√n) + n Hint. The correct expression is somewhere between Ω(n) and O(nlogn).
1
CS 341: Algorithms (S’18) Assignment 1 E. Blais, N. Harms, E. Zima
3 Testing primality [10 marks]
Analyze the time complexity of the following pseudocode in terms of n using big-Θ notation. For this analysis, each operation on integers (including multiplication and squaring) takes constant time.
Algorithm 1: IsPrime(n) j ← 2; while j2 ≤ n do k ← 2; while j ∗k ≤ n do if j ∗k = n then return False; k ← k + 1; j ← j + 1; return True;
4 Common sum [10 marks]
In the CommonSum problem, we are given two arrays A and B of length n containing non-negative (not necessarily distinct) integers, and we must determine whether there are indices i1,i2,j1,j2 ∈ {1,2,...,n} for which A[i1] + A[i2] = B[j1] + B[j2]. Design an algorithm that solves the CommonSum problem and has time complexity O(n2 logn) in the setting where operations on individual integers take constant time.
Your solution must include a description of the algorithm in words, the pseudocode for the algorithm, a proof of its correctness, and an analysis of its time complexity in big-Θ notation.
5 Programming question [10 marks]
Implement the algorithm you obtained for the CommonSum problem in Question 4.
Input and output. The input consists of n + 1 lines. The first line contains an integer value n ≥ 1. The following n lines have two integer values each: A[i] and B[i] for i = 1,2,...,n. We will not be testing whether your program detects input errors. However, our tests will check that your algorithm is fast enough.
The output must have 1 line that contains TRUE or FALSE.
2
CS 341: Algorithms (S’18) Assignment 1 E. Blais, N. Harms, E. Zima
Sample input 1
4 1 2 7 8 5 6 3 4
Sample output 1
TRUE
Sample input 2
7 5 16 15 6 25 21 20 31 20 16 10 11 0 1
Sample output 2
FALSE
The valid solution for the first instance is TRUE since A[2] + A[4] = B[1] + B[2] = 10.
The valid solution for the second instance is FALSE because there are no values of i1,i2,j1,j2 ∈ {1,2,...,n} for which A[i1] + A[i2] = B[j1] + B[j2].
3