Math+computer homework

Name:

CSE 5211 Analysis of Algorithms Spring 2018 Midterm Exam

Due: March 14, 2018; cite all outside sources, including people

1. (10 pts) Simplify the summation:Score ∑ 0≤k<n

[10k + (n−k)k]

2. (10 pts) Solve the recurrence T(n) = 3(n−1) + n with initial condition T(0) = 1.Score

3. (5 pts) Find the generating function for the sequence 〈1, −1, 1, −1, . . .〉 of alternating signs.Score

4. (5 pts) What sequence is associated with the generating functionScore

G(z) = x

(1−x)(1−2x)

5. (5 pts) What is the best, average, and worst-case time complexity of quicksort? Under that conditionsScore do the best and worst-cases occur?

1

1. (5 pts) (True or False) Explain your answer. If f(n) = O( √ n) then f(n) = O(n).Score

2. (5 pts) (True or False) Explain your answer. √ n = O(lg n).Score

3. (5 pts) What is the asymptotic growth rate of of Catalan numbers Cn = 1n+1 ( 2n n

) ?Score

2

The code below implements the fast Fourier transform. It is from Rosetta Code. Assume that n is a power of 2. Notice the recurrence starts at step= 1 and works up by doubling until. step≥ n. Answer the questions that follow.

1 #include <stdio . h> 2 #include <math . h> 3 #include <complex . h> 4

5 double PI ; 6 typedef double complex cplx ; 7

8 void f f t t ( cplx buf [ ] , cplx out [ ] , int n , int step ) 9 {

10 i f ( step < n) { 11 f f t t ( out , buf , n , step ∗ 2 ) ; 12 f f t t ( out + step , buf + step , n , step ∗ 2 ) ; 13

14 f o r ( int k = 0; k < n ; k += 2 ∗ step ) { 15 cplx t = cexp(−I ∗ PI ∗ k / n) ∗ out [ k + step ] ; 16 buf [ k / 2] = out [ k ] + t ; 17 buf [ ( k + n )/2] = out [ k ] − t ; 18 } 19 } 20 } 21

22 void f f t ( cplx buf [ ] , int n) 23 { 24 cplx out [ n ] ; 25 f o r ( int i = 0; i < n ; i++) out [ i ] = buf [ i ] ; 26

27 f f t t ( buf , out , n , 1 ) ; 28 }

1. (5 pts) As a function of n and step, what is the time complexity of the for loop that starts at line 14?Score Assume computing the exponential e−iπk/n, array indexing, and basic arithmetic take constant time.

2. (5 pts) What recurrence equation describes the complexity T(n, step) of the fftt function that startsScore in line 8?

3. (10 pts) As a function of n, what is the time complexity of the fft function that starts in line 22?Score

3

Here’s a supporting function to print the results of the transform. And a main routine should you want to compile, run/test the code. There are not questions to answer here.

1 void show( const char ∗ s , cplx buf [ ] ) { 2 p r i n t f ("%s" , s ) ; 3 f o r ( int i = 0; i < 8; i++) 4 i f ( ! cimag ( buf [ i ] ) ) { p r i n t f ("%g " , c r e a l ( buf [ i ] ) ) ; } 5 else { p r i n t f ("(%g, %g) " , c r e a l ( buf [ i ] ) , cimag ( buf [ i ] ) ) ; } 6 } 7

8 int main () 9 {

10 PI = atan2 (1 , 1) ∗ 4; 11 cplx buf [ ] = {1 , 1 , 1 , 1 , 0 , 0 , 0 , 0}; 12

13 show("Data: " , buf ) ; 14 f f t ( buf , 8 ) ; 15 show("\nFFT : " , buf ) ; 16 return 0; 17 }

1 A Little Haskell 1. (5 pts) The !! list index (subscript) operator is defined in Haskell by the code below. List indices haveScore

0 origin. Describe the initial conditions, recursion, and time complexity of the code.

1 ( ! ! ) : : [ a ] −> Int −> a 2 xs ! ! n | n < 0 = error "Prelude.!!: negative index" 3 [ ] ! ! _ = error "Prelude.!!: index too large" 4 (x :_) ! ! 0 = x 5 (_: xs ) ! ! n = xs ! ! (n−1)

2. (5 pts) A safe implementation of init is given below. What recurrence equation and initial conditionsScore describe the algorithm? What is the time complexity of the algorithm?

1 s a f e I n i t : : [ a ] −> Maybe [ a ] 2 s a f e I n i t [ ] = Nothing 3 s a f e I n i t [ x ] = [ ] 4 s a f e I n i t (x : xs ) = x : i n i t xs

4

3. The next few questions are about binary search.

(a) (5 pts) What pre-condition must be imposed on a list to correctly implement binary search?Score

(b) Below is a Haskell implementation of binary search on lists. It takes a list of integers, a value to search for, two integers that mark the ends of the list. If the value is found it is returned, otherwise, Nothing is.

1 binsearch : : [ Int ] −> Int −> Int −> Int −> Maybe Int 2 binsearch xs value lo hi 3 | hi < lo = Nothing 4 | xs ! ! mid > value = binsearch xs value lo (mid−1) 5 | xs ! ! mid < value = binsearch xs value (mid+1) hi 6 | otherwise = mid 7 where 8 mid = lo + (( hi − lo ) ‘ div ‘ 2)

i. (5 pts) What is the cost to index into the middle of the list?Score

ii. (5 pts) what recurrence equation models the code and what is its solution?Score

(c) (5 pts) Write a binary search program that uses constant time direct addressing into arrays.Score Compile, execute, and test your program to convince yourself it it correct. Analyze the complexity of your program. Use any programming language that supports O(1) array access. Include your program along with the analysis.

Total Points: 100 Friday, March 2, 2018

5