Math+computer homework

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 #inc lude <s td i o . h> 2 #inc lude <math . h> 3 #inc lude <complex . h> 4

5 double PI ; 6 typede f double complex cp lx ; 7

8 void f f t t ( cp lx buf [ ] , cp lx out [ ] , i n t n , i n t s tep ) 9 {

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

14 f o r ( i n t k = 0 ; k < n ; k += 2 ∗ s tep ) { 15 cp lx 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 ( cp lx buf [ ] , i n t n) 23 { 24 cp lx out [ n ] ; 25 f o r ( i n t 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 , cp lx buf [ ] ) { 2 p r i n t f (“%s” , s ) ; 3 f o r ( i n t 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 i n t main ( ) 9 {

10 PI = atan2 (1 , 1) ∗ 4 ; 11 cp lx 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 : in 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 b insearch : : [ Int ] −> Int −> Int −> Int −> Maybe Int 2 b insearch xs value l o h i 3 | h i < l o = Nothing 4 | xs ! ! mid > value = binsearch xs value l o (mid−1) 5 | xs ! ! mid < value = binsearch xs value (mid+1) h i 6 | otherwise = mid 7 where 8 mid = lo + ( ( h i − l o ) ‘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

Our website has a team of professional writers who can help you write any of your homework. They will write your papers from scratch. We also have a team of editors just to make sure all papers are of HIGH QUALITY & PLAGIARISM FREE. To make an Order you only need to click Ask A Question and we will direct you to our Order Page at WriteDemy. Then fill Our Order Form with all your assignment instructions. Select your deadline and pay for your paper. You will get it few hours before your set deadline.