Sale!

# CMPSC 465 Writing Assignment 1 solution

\$30.00

Writing Assignment 1 CMPSC 465
INSTRUCTIONS:
1. Use the provided latex template to write your solutions.
Problem 1 (15 points).
For each pairs of functions below, indicate one of the three: f = O(g), f = Ω(g), or f = Θ(g).
1. f(n) = n
1.01
, g(n) = n
0.99
·logn

Category:

## Description

5/5 - (1 vote)

Writing Assignment 1 CMPSC 465
INSTRUCTIONS:
1. Use the provided latex template to write your solutions.
Problem 1 (15 points).
For each pairs of functions below, indicate one of the three: f = O(g), f = Ω(g), or f = Θ(g).
1. f(n) = n
1.01
, g(n) = n
0.99
·logn
2. f(n) = n, g(n) = n
0.99
·(logn)
2
3. f(n) = 100 ·log(100 · n
3
), g(n) = (logn)
2
4. f(n) = n
2
·logn
2
, g(n) = n ·(logn)
3
5. f(n) = n
2.01
·logn
3
, g(n) = n
2
·(logn)
2
6. f(n) = (logn)
logn
, g(n) = n
2
7. f(n) = (logn)
logn
, g(n) = n
loglogn
8. f(n) = (n ·logn)
logn
, g(n) = n
(logn)
2
9. f(n) = n
2
· 2
n
, g(n) = 3
n
10. f(n) = 2
n·logn
, g(n) = 3
n
11. f(n) = n!, g(n) = (logn)
n
12. f(n) = n!, g(n) = n
n
.
13. f(n) = log(n!), g(n) = logn
n
.
14. f(n) = ∑
n
k=1
(1/k), g(n) = logn
15. f(n) = ∑
n
k=1
k
2
, g(n) = n
2
·logn
Problem 2 (10 points).
Solve each of the following recursions using master theorem.
1. T(n) = 16 ·T(n/2) +100 · n
2
.
2. T(n) = 4 ·T(n/2) +1000 · n
2
.
3. T(n) = 8 ·T(n/2) +10 · n
3.5
.
4. T(n) = 2 ·T(n/2) +n ·log(n).
5. T(n) = 8 ·T(n/2) +n
1.5
·log2
(n).
1
Writing Assignment 1 CMPSC 465 Fall 2020 (Instructor: Mingfu Shao) Due: Sep. 12, 11:59pm
Problem 3 (9 points).
Assume you have functions f and g satisfying that f(n) is O(g(n)). For each of the following statements,
decide if you think it is true or false and give a proof or counterexample.
1. ln f(n) = O(lng(n)).
2. 2
f(n) = O(2
g(n)
).
3. f(n)
2 = O(g(n)
2
).
Problem 4 (10 points).
Consider recursion T(n) = Θ(n) +T(a · n) +T(b · n), T(1) = 1, a ≥ 0, b ≥ 0. Prove the following:
1. T(n) = Θ(n), if a+b < 1.
2. T(n) = Θ(n ·logn), if a+b = 1.
Problem 5 (16 points).
For each pseudo-code below, give the asymptotic running time in Θ notation. You may assume that standard
arithmetic operations take Θ(1) time.
1.
for i := 1 to n do
j := i;
while j < n do
j := j +5;
end
end
2.
for i := 1 to n do
for j := 4i to n do
s := s+2;
end
end
3.
for i := 1 to n do
j := n;
while i
5 < j do
j := j −1;
end
end
4.
for i := 1 to n do
j := 2;
while j < i do
j := j
4
;
end
end
2
Writing Assignment 1 CMPSC 465 Fall 2020 (Instructor: Mingfu Shao) Due: Sep. 12, 11:59pm
Problem 6 (10 points).
Design a divide-and-conquer algorithm to calculate x
n
(n is a positive integer) in O(logn) time. You may
assume that multiplying any two numbers can be done in Θ(1) time.
Problem 7 (10 points).
Given two sorted arrays A and B of size m and n respectively, design an algorithm to find the median of A
and B. Your algorithm should run in O(log(m+n)) time.
Problem 8 (10 points).
Given an array of points P = [p1, p2,··· , pn] on 2D plane, where point pi = (xi
, yi) is given as its x- and
y-coordinates, and integer k, 1 ≤ k ≤ n, design an algorithm to find the closest k points to the origin in P.
Your algorithm should run in O(n) time.
3