Cpt S 515 Homework #1
No late homework!
1. In Lesson 1, algorithm’s complexity is measured on input size instead of
input values. Please indicate the input size for an algorithm that solves the
following problem:
Given: a number n and two primes p, q,
Question: is it the case that n = p · q?
2. In Lesson 2, we learned linear-time selection algorithm where the input
array of numbers are cut into groups of size 5. Show that, when the group
size is 7, the algorithm still runs in linear time.
3. In Lesson 2, we learned closest pair algorithm that runs in O(n log n)
time. However, that algorithm can be improved further when additional
assumption is made. Here is one. Suppose that there are n
2 bugs sitting on
a piece of paper of size n by n. Any two bugs must stay away by at least 1.
Each bug is given as a pair of coordinates. Design a linear-time algorithm
that finds the closest pair of bugs. (Hint: since the input size is n
2
, the linear
time here really means the running time is O(n
2
) where the n
2
is the number
of bugs.)
4. Algorithms are to solve problems, or more precisely, to solve problems
that have a precise mathematica definition. However, in practice, figuring
out what is exactly the problem is not easy at all. (You may search internet)
Suppose that you would like to write an algorithm to decide the similarity
between two C programs. What would you do?
1
