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.
2. Submit your solution to Gradescope. Make sure only one of your group members submits. After
submitting, make sure to add your group members.
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.
2. Submit your solution to Gradescope. Make sure only one of your group members submits. After
submitting, make sure to add your group members.
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