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 worstcase time complexity of quicksort? Under that conditionsScore
do the best and worstcases 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
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 precondition 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
Topquality papers guaranteed
100% original papers
We sell only unique pieces of writing completed according to your demands.
Confidential service
We use security encryption to keep your personal data protected.
Moneyback guarantee
We can give your money back if something goes wrong with your order.
Enjoy the free features we offer to everyone

Title page
Get a free title page formatted according to the specifics of your particular style.

Custom formatting
Request us to use APA, MLA, Harvard, Chicago, or any other style for your essay.

Bibliography page
Don’t pay extra for a list of references that perfectly fits your academic needs.

24/7 support assistance
Ask us a question anytime you need to—we don’t charge extra for supporting you!
Calculate how much your essay costs
What we are popular for
 English 101
 History
 Business Studies
 Management
 Literature
 Composition
 Psychology
 Philosophy
 Marketing
 Economics