written-assignment-am

What is the total number of basic operations that the following code piece consume? Make your answer precise and list your steps of calculation.

int afunc(int n){
    int res = 0;   // 1
    for(int i=0;i<n;i++){   // 3n+2
        for(int j=0;j<n;j++){ // (6n+2)n
            res+=i*j;
        }
    }
    return res; // 1
}
Copy

The total number of basic operations that the code piece consumes is

For each pair of and below, decide if , , or . Justify your answer using the definition of this asymptotic notation. Note that more than one of these relations may hold for a given pair; list all correct ones.

1. and .

   (1) prove

   when

   (2) prove

   
   Now prove

   prove

• and .

Suppose , then

Let f(n) be an asymptotically positive function. Prove or disprove each of the following conjectures.
Hint: You can prove a conjecture using its definition or disprove a conjecture by giving negative examples.

(a)

is a constant

(b)

Solve the following recurrence relation and represent T(n) using a formula of n.

=T(\frac{n}{2^2})+2=T(\frac{n}{2^3})+3=T(\frac{n}{2^4})+4...=T(\frac{n}{2^i})+i$

let

In the merge sort algorithm, we divide an array into two halves, recursively sort the subarrays, and then merge them into a sorted array. Now Ming proposes a “merge sort pro” algorithm. In “merge sort pro”, an array is divided evenly into four subarrays instead of two, and the rest of the steps are similar to those of merge sort. What do you think is the time cost of “merge sort pro” if the input size is n? Prove your answer.

Let

We are given an array of n items and for any two items A and B: • We can check if A and B are equal. • We cannot check which one is greater and which one is smaller, so we cannot sort them. For example, the array may be {♥,♥,☆,○,△,♥,♥,♥,♥,♫,☆,■,♥}. Our task is to find the majority of the array, if it has one. The majority of an array is defined as the item that appears strictly more than n/2 times. For example, in the sample array above, the array size is 13 and item ♥ appears 7 times, so ♥ is the majority. Use a divide-and-conquer algorithm to solve the problem in O(n*log.n). Describe your algorithm in pseudo-code.

MERGECOUNT(A, left, right)
1.     IF left >= right
2.          RETURN
3.     center = (left + right) / 2
4.     MERGECOUNT(A, left, center)
5.     MERGECOUNT(A, center + 1, right)
6.     MERGE_WITH_COUNT(A, left, center, right)

MERGE_WITH_COUNT(A, left, center, right)
1.     Create an empty map/dictionary charCount
2.     FOR i = left to right
3.         IF A[i] exists in charCount
4.             Increment count of A[i] in charCount
5.         ELSE
6.             Set count of A[i] in charCount to 1
7.     maxChar = character with maximum count in charCount
8.     maxCount = count of maxChar in charCount
Copy