CSCI203 ASSIGNMENT 1
CSCI203 ASSIGNMENT 1
1. Prove that x log y = y log x
2. Let g(n) be the number of ways to write a string of n zeros and ones so that
there are never two successive zeros. Show that g(n) = fib(n+2). (Hint: try induction.)
3. Which of the following statements are true? Prove your answers.
a. n2
O(n3
)
b. n2
Ω(n3
)
c. 2n Θ(2n+1)
d. n! Θ((n+1)!)
4. An alternative proof that there are an infinite number of primes begins as
follows. Assume that the set of prime numbers is finite. Let P be the largest
prime. Consider X=P! and Y=X+1. Complete the proof and construct an
algorithm bigprime(P) based on the proof. It should be clear from the
algorithm that it terminates with a new prime larger than P. (Note: this
algorithm should not involve bruteforce testing of candidate primes by
exhaustive division.)
5. Suppose A and B are two finite sets. Show that
where denotes the number of
elements in set A. What is the equivalent equation for three sets, A, B and C?
6. Two algorithms take n^2 days and n^3 seconds to solve an instance of size n.
Which is the better algorithm? What is the breakeven value for n? How long
will the algorithms take at this value of n?
7. A function f (x) such that f (a) and f (b) have different signs must have at least
one root (value where the function is zero) between a and b. Devise an
algorithm based on finding the value of x at which the line joining the points
(a, f(a)) and (b, f(b)) crosses the xaxis and then determining the sign of the
function at this point.
8. Use the secant method of question 7 to perform three iterations with f(x) = x3

4x + 1, a = 1 and b = 2. Tabulate the values of all variables at each stage.
9. Give two functions f(n) and g(n) such that neither f(n) nor g(n) tends to a limit
as n tends to infinity, but both f(n)+g(n) and f(n)/g(n) do tend to a limit.
10. A certain algorithm takes 0.0001 x 2n
seconds to solve an instance of size n.
Show that it just solves an instance of size 38 in a year. What size problem
could be solved in a year on a machine 100 times as fast? A second algorithm
takes 0.01 x n3
seconds to solve an instance of size n. What size problem could
it solve in a year? With a machine 100 times as fast? For what range of n is the
first algorithm better?
Assignments should be typed into a text file called ass1.txt and submitted via the
submit program in Unix.
submit u user c csci203 a 1 ass1.txt
where your unix userid should appear instead of user.
1. Prove that x log y = y log x
2. Let g(n) be the number of ways to write a string of n zeros and ones so that
there are never two successive zeros. Show that g(n) = fib(n+2). (Hint: try induction.)
3. Which of the following statements are true? Prove your answers.
a. n2
O(n3
)
b. n2
Ω(n3
)
c. 2n Θ(2n+1)
d. n! Θ((n+1)!)
4. An alternative proof that there are an infinite number of primes begins as
follows. Assume that the set of prime numbers is finite. Let P be the largest
prime. Consider X=P! and Y=X+1. Complete the proof and construct an
algorithm bigprime(P) based on the proof. It should be clear from the
algorithm that it terminates with a new prime larger than P. (Note: this
algorithm should not involve bruteforce testing of candidate primes by
exhaustive division.)
5. Suppose A and B are two finite sets. Show that
where denotes the number of
elements in set A. What is the equivalent equation for three sets, A, B and C?
6. Two algorithms take n^2 days and n^3 seconds to solve an instance of size n.
Which is the better algorithm? What is the breakeven value for n? How long
will the algorithms take at this value of n?
7. A function f (x) such that f (a) and f (b) have different signs must have at least
one root (value where the function is zero) between a and b. Devise an
algorithm based on finding the value of x at which the line joining the points
(a, f(a)) and (b, f(b)) crosses the xaxis and then determining the sign of the
function at this point.
8. Use the secant method of question 7 to perform three iterations with f(x) = x3

4x + 1, a = 1 and b = 2. Tabulate the values of all variables at each stage.
9. Give two functions f(n) and g(n) such that neither f(n) nor g(n) tends to a limit
as n tends to infinity, but both f(n)+g(n) and f(n)/g(n) do tend to a limit.
10. A certain algorithm takes 0.0001 x 2n
seconds to solve an instance of size n.
Show that it just solves an instance of size 38 in a year. What size problem
could be solved in a year on a machine 100 times as fast? A second algorithm
takes 0.01 x n3
seconds to solve an instance of size n. What size problem could
it solve in a year? With a machine 100 times as fast? For what range of n is the
first algorithm better?
Assignments should be typed into a text file called ass1.txt and submitted via the
submit program in Unix.
submit u user c csci203 a 1 ass1.txt
where your unix userid should appear instead of user.
You'll get 1 file (8.6KB)