Math+computer homework

See attach file

Name:

CSE

5

2

1

1 Analysis of Algorithms
Spring 2018 Midterm Exam

Due: March 1

4

, 2018; cite all outside sources, including people

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

[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
2 #include
3 #include
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

A Little Haskell