## Description

The following problems are from the 3rd edition of Introduction to Algorithms, CLRS. Attempt to solve

these problems independently and then discuss the solutions in your Homework discussion groups.

Submit a “professional” looking individual solution in Canvas. A subset of the problems will be graded

for correctness.

1) (CLRS) 1.2-2. Suppose we are comparing implementations of insertion sort and merge sort on

the same machine. For inputs of size n, insertion sort runs in 8n2

steps, while merge sort runs in

64nlgn steps. For which values of n does insertion sort beat merge sort?

Note: lg n is log “base 2” of n or log2 𝑛. There is a review of logarithm definitions on page 56. For

most calculators you would use the change of base theorem to numerically calculate lgn.

That is: lgn = log2 𝑛 =

log 𝑛

log2

. Where log 𝑛 = log10 𝑛 and is calculated using the log button on

your calculator.

2) (CLRS) Problem 1-1 on pages 14-15. Fill in the given table. Hint: It may be helpful to use a

spreadsheet or Wolfram Alpha to find the values.

3) (CLRS) 2.3-3 on page 39. Use mathematical induction to show that when n is an exact power of

2, the solution of the recurrence

𝑇(𝑛) = {

2 , 𝑖𝑓 𝑛 = 2

2𝑇(

𝑛

2

) + 𝑛, 𝑖𝑓 𝑛 = 2

𝑘

, for 𝑘 > 1

is T(n) = n lg n.

4) For each of the following pairs of functions, either f(n) is O(g(n)), f(n) is Ω(g(n)), or f(n) = Θ(g(n)).

Determine which relationship is correct and explain.

a. f(n) = n0.75

; g(n) = n0.5

b. f(n) = n; g(n) = log2

n

c. f(n) = log n; g(n) = lg n

d. f(n) = en

; g(n) = 2n

e. f(n) = 2n

; g(n) = 2n-1

f. f(n) = 2n

; g(n) =2

2

𝑛

g. f(n) = 2n

; g(n) = n!

h. f(n) = nlgn; g(n) = n√𝑛

5) Describe in words and give pseudocode for a (n lgn) time algorithm that, given a set S of n integers

and another integer x, determines whether or not there exist two elements in S whose sum is exactly

x. Demonstrate your algorithm on the set S = { 12, 3, 4, 15, 11, 7 } and x = 20.

CS 325-400 Summer 16

Homework Assignment 1

6) Let f1 and f2 be asymptotically positive functions. Prove or disprove each of the following

conjectures. To disprove give a counter example.

a. If f1(n) = O( g1(n)) and f2(n) = O( g2(n)) then f1(n)+f2(n) = O( g1(n)+g2(n) ) .

b. If f1(n) = O(g1(n)) and f2(n) = O(g2(n)), then

𝑓1 (𝑛)

𝑓2 (𝑛)

= 𝑂 (

𝑔1(𝑛)

𝑔2(𝑛)

)

c. max (f1(n) , f2(n)) = ( f1(n) + f2(n) ).

7) Fibonacci Numbers:

The Fibonacci sequence is given by : 0, 1, 1, 2, 3, 5, 8, 13, 21, ….. By definition the Fibonacci

sequence starts at 0 and 1 and each subsequent number is the sum of the previous two. In

mathematical terms, the sequence Fn of Fibonacci number is defined by the recurrence relation

Fn = Fn-1 + Fn-2 with F0=0 and F1=1

An algorithm for calculating the nth Fibonacci number can be implemented either recursively or

iteratively.

Example Recursive:

fib (n) {

if (n = 0) {

return 0;

} else if (n = 1) {

return 1;

} else {

return fib(n-1) + fib(n-2);

}

}

Example Iterative:

fib (n) {

fib = 0;

a = 1;

t = 0;

for(k = 1 to n) {

t = fib + a;

a = fib;

fib = t;

}

return fib;

}

CS 325-400 Summer 16

Homework Assignment 1

a) Implement both recursive and iterative algorithms to calculate Fibonacci Numbers in the

programming language of your choice. Provide a copy of your code with your HW pdf. We will not be

executing the code for this assignment. You are not required to use the flip server for this assignment.

b) Use the system clock to record the running times of each algorithm for n = 5, 10, 15, 20, 30, 50, 100,

1000, 2000, 5000, 10,000, …. You may need to modify the values of n if an algorithm runs too fast or too

slow to collect the running time data. If you program in C your algorithm will run faster than if you use

python. The goal of this exercise is to collect run time data. You will have to adjust the values of n so

that you get times greater than 0.

c) Plot the running time data you collected on graphs with n on the x-axis and time on the y-axis. You

may use Excel, Matlab, R or any other software.

d) What type of function (curve) best fits each data set? Again you can use Excel, Matlab, any software

or a graphing calculator to calculate the regression curve. Give the equation of the function that best

“fits” the data and draw that curve on the data plot. Why is there a difference in running times?