Author: AllenYGY
status: DONE
created: 2023-12-27T02:09
updated: 2024-06-11T01:14
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
}
The total number of basic operations that the code piece consumes is
For each pair of
(1) prove
(2) prove
Now prove
Suppose
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)
(b)
Solve the following recurrence relation and represent T(n) using a formula of n.
=T(\frac{n}{2^2})+2
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