Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

COMS 311:  Homework 2

Submission format.     Your submission file should be in pdf format. Name your submis- sion file:  <Your-net-id>-311-hw2 .pdf.  For instance, if your netid is asterix, then your submission file will be named asterix-311-hw2 .pdf.

You are required to type-set your solution. You can use word, latex and any other type- setting tool to type your solution; you need to make sure you export/save it in pdf before submission.

For questions where you are asked to write an algorithm, you are required to write  pseudocode.   Do  not  write  code  in  any  specific  language  such  as  Java, Python, C/C++, etc.

Learning outcomes.

1. Determine whether or not a function is Big-O of another function

2. Analyze asymptotic worst-case time complexity of algorithms

3. Design of algorithms (heap and hashing)

Finite Series.

1 + 2 + 3 + . . . + n = n(n + 1)/2

12 + 22 + 32 + . . . + n2  = n(n + 1)(2n + 1)/6

13 + 23 + 33 + . . . + n3  = n2 (n + 1)2 /22

1 + T + T2 + T3 + . . . + Tn − 1  =  if T  1

For instance, when T = 1/2

1 + 1/2 + 1/22 + . . . + 1/2n − 1  = 2(1 - 1/2n )

Infinite series.

1 + T + T2 + T3 + . . . = 1/(T - 1) when T < 1

(a) for  (i=1;  i<=n;  i++)  {

for  (j=1;  j<=n*i;  j++)  {

<Do-something-atomic>

}

}

(b)  //  Given  array  A  and  integer  k

//  k  is not present  in  A

i=1;

j=n;

while  (i<=j)  {

while  (A[i]  <  k)  i++;

while  (A[j]  >  k)  j-- ;

if  (i<=j)  {

t  =  A[i];

A[i]  =  A[j];

A[j]  =  t;

}

}

3.  Consider an array A of integers. Write an algorithm (using hashing) that outputs the length of the longest subarray where the sum of the elements in the subarray is equal to 0.  For instance, for the array A = {13, 11, -2, 1, 7, -15, -2, 3, -3, 10} the output of your algorithm should be 8, for the array A = {13, 1, 0, -2} the output should be 1, and the for the array A = {13, 1, -2} the output should be 0.  Derive the runtime of your algorithm.  Part of the grade will depend on the efficiency of your algorithm. (20pts)

4. Extra Credit Draw a binary min-heap tree and the corresponding array where the elements are inserted to the heap in following order:

50 64 87 90 23 14 2 51 27

(10pts)