Computer Science Department – Rutgers University
Spring 2018
CS 205: Final Exam Question 2 – Big O
1) Formallyprovethatiff=O(h)andg=O(h)thenf+g=O(h). 2) True or false – give a mathematical justification:
a) n = O(n2).
b) n(n+1)(n+2)−n3 =O(n3).
c) n(n+1)(n+2)−n3 =O(n2). d) nlnn = O(n2).
e) n2 = O(nlnn). f) 1/n = O(1).
g) 1000000n = O(n). h) 2n = O(3n).
i) 3n = O(2n).
j) ni=1 i(i + 1)(i + 2) = O(n4).
16:198:205
Recall the idea of mergesort: to sort a list, divide a list in two, sort the two halves, and merge them to form a sorted whole. In class, we gave an argument that the complexity of mergesort on a list of N elements could therefore be described as
M(N) = M(N/2) sort the left half + M(N/2) sort the right half + N merge the two halves = 2M(N/2) + N. (1)
Noting that M(1) = 1, since sorting a list of size 1 is easy, this led to an overall complexity of M(N) = O(N lnN). Your good buddy suggests the following: If mergesort gets such good performance dividing the list into two halves and merging them, imagine how fast a mergesort would be that split the list to sort into three parts, sorted them, then merged the result.
- 3) Like the recursive relation above, give a rough description of the overall worst case complexity of this tri- mergesort.
- 4) In terms of big-O, which approach has the smaller complexity?
- 5) In your opinion, is it worth the additional effort and overhead it would take to implement this approach? Justify.
1
Computer Science Department – Rutgers University Spring 2018
CS 205: Final Exam Question 3 – Factor Decomposition 16:198:205
Decomposing a number N into composite factors (e.g., 2059 = 29 ∗ 71) is generally understood to be a hard problem for large values of N. For some N of specific forms, factoring can actually become quite easy; observing that 40467 = 2262 − 1032, we have via the difference of squares formula
40467 = 2262 −1032 = (226−103)∗(226+103) = 123∗329. (1) One special case of an easily factorable number is when N is a perfect power of some integer base, i.e., N = ak for
some integer a, k > 1.
Consider the question, “is N = 10200 a perfect square?” One way to check might be to compute the square root.
√
Since
computation over the real numbers, a topic largely untouched in this course. The goal of this problem is to approach this computation, purely in terms of integer arithmetic.
In each of the following, when we ask for a big-O bound, we are interested in as tight an upper bound as you can justify.
- 1) Give a big-O bound for the number of bits needed to represent a number N.
- 2) Give a big-O bound for the bit-complexity of multiplying two integers between 1 and N. What is the worst case? Note, the bound should be simply in terms of N.
√
- 3) Giventhat1≤
a2. Stop when either i) a2 = N and you have found the square root, or ii) a2 > N and N does not have an integer square root. Give a big-O bound for the overall complexity of this search in terms of N.√
10200 ≈ 100.995, as the fractional part is not 0, N cannot be a perfect square. This, however, requires
N≤N,considersequentiallytakingeachnumbera∈{1,2,3,…,N−1,N}andcomputing
4) We are effectively searching the set {1, 2, 3, . . . , N − 1, N} for the value √√
N. For a given a, we can’t compare a to N since we don’t know N. However, we can compare a2 to N. Use this idea as the basis of a binary search-type algorithm. Give a big-O bound on the overall complexity of this search in terms of N. How does
it compare to the previous?
- 5) Given an integer k > 1, give a big-O bound for the bit-complexity of computing the k-th power of an integer
between 1 and N. What is the worst case? Note that the bound should be in terms of N and k.
- 6) SimilartoQuestions3,4above,giventhat1≤N1/k ≤N,wemayconsidersearchingthesequence{1,2,3,…,N− 1,N} for N1/k. For a given a, we may compare ak to N to determine if we are too high or too low. Use this idea as the basis of a binary search-type algorithm. Give a big-O bound on the overall complexity of this search, in terms of N and k.
- 7) Questions 5, 6 above assumed that k was known. What if k is unknown? If N is a perfect (non-trivial) power, what is the smallest possible value of k that power might be? What is the largest? Give a big-O bound on the largest possible k.
- 8) Consider repeating the algorithm in Question 6, for every k over the indicated range above, to search all possible powers to see if N = ak for some a, k. For clarity, write out the pseudocode of this algorithm given an input N. Give a big-O bound on the overall complexity of this search, in terms of N. Is this efficient?
1
Computer Science Department – Rutgers University Spring 2018
Bonus
- 9) The approach outlined above suggested a binary search for the base a for any given k, but utilizes a sequential search for the correct value of k. Could a binary search be utilized to find k as well?
- 10) Can you come up with a better algorithm for checking if N is a perfect (non-trivial) power?
- 11) Consider modifying the problem so that instead of finding a,k such that N = ak, you are given a large prime number P and asked to find a, k such that N ≡ ak mod P . What must change in the above approach? Try to outline an algorithm for this problem, given N,P, and given a big-O bound on its complexity. Note, operating mod P, you may assume all multiplications take constant time.
2
Computer Science Department – Rutgers University Spring 2018
CS 205: Final Exam Question 4 – Modulus and Diophantine 16:198:205
In class and in posted notes, we consider problems like trying to find integer solutions x, y to the equation
3x + 5y = D (1)
for various values of D. Using congruences, we were able to decouple the x and y variables, determine the ‘form’ that x and y must have, and then return to the original equation to discover how those two forms were related. Thinking of the above equation as a line, and noting that integer solutions must fall on that line, we were able to construct a 1-dimensional parameterization in terms of an integer parameter k, such that for any integer value of k,
5) Are you confident that your parameterization captures all integer solutions (x, y, z)? Why? Now consider the system of equations:
3x + 5y + 7z = 1 7x + 3y + 5z = 1.
(4)
x = x0 + ak y = y0 + bk,
(2)
represented an integer solution to the original equation.
- 1) For a given value of D, give an explicit formula for an (x0,y0) and a,b to parameterize the integer solutions to
the above. The formula should be in terms of D, and an integer parameter k.
- 2) Are you confident that your parameterization captures all integer solutions to 3x+5y = D? For any D? Why?
Consider now the equation:
3x + 5y + 7z = 1. (3)
- 3) Prove that for any integer value of z, there are integer solutions for x and y.
- 4) Parameterize the set of integer solutions (x,y,z) in terms of an integer z and an integer parameter k. Note, because the above equation represents a plane in 3-D space, the solutions are two dimensional, and thus require two parameters (in this case, z and k).
6) Are there any integer solutions (x,y,z) that satisfy both these equations simultaneously? The intersection of two planes is a line, so give a 1-D integer parameterization of the integer solutions to this system.
Bonus
Adapt your work here to solve for the integer solutions to:
21x + 15y + 35z = 1. (5)
What complicates the solution here, and how can you approach solving it?
1