Questions:
Algorithm analysis for N elements
1) find the kth largest value in an unsorted array of N elements. Estimate the running time. It should be better than quick sort running time. I think O(n + klogn) is an efficient running time (if you can do a better algo, please do so). I don't need the entire program. Just functions that show the timing. This is how I did it. Please correct my solution
kthLargest(A,n) {
BuildMaxHeap(A);
for(I=1; I<=k; I++)
kth[I] = GetMax(A);
} time = O(n + klogn)
BuildMAxHeap(A) {
heapsize[a] = length[A];
for(I= length[A]/2; I>= 1; I--)
MaxHeapify(A,I);
} time = O(n/2 logn)
GetMax(A) {
if(heapsize[A] < 1)
return error
max = A[1]
A[1] = A[heapsize[A]]
heapsize[A] = heapsize[A] - 1
MaxHeapify(A,1)
return max;
} time = O(logn)
3) What is running time of insertion sort if all keys are equal.
4) How to recursively multiply XY, where X = 2222 and Y = 4321
This is from book. I understand what is happening, however, I don't know how to write a recursive function for this! I hope this helps.
Suppose we want to multiply two n-digit numbers x and y. If exactly one of x and y is negative, then the answer is negative; otherwise it is positive. Thuse we can perform this check and then assume that x,y >= 0. If x = 61,438,521 and y = 94,736,407, xy = 5,820,464,730,934,047. Let us break x and y into two halves. Then x1 = 6,143, x2 = 8,521, y1 = 9473, and y2 = 6,407.
We also have x = x1 * 10^4 + x2 and y = y1* 10^4 + y2
xy = x1y1*10^8 + (x1y2 + x2y1)10^4 + x2y2
x1y2 + x2y1 = (x1 - x2)(y2 - y1) + x1y1 + x2y2
Figure below shows how only 3 recursive subproblems need to be solved
|
Function
|
Value
|
Complexity
|
|
x1
x2
y1
y2
|
6,143
8,521
9,473
6,407
|
Given
Given
Given
Given
|
|
d1 = x1 - x2
d2 = y2 - y1
|
-2,378
-3,066
|
O(n)
O(n)
|
|
x1y1
x2y2
|
58,192,639
54,594,047
|
T(n/2)
T(n/2)
|
|
d1d2
d3 = d1d2 + x1y1+ x2y2
|
7,290,948
120,077,634
|
T(n/2)
O(n)
|
|
x2y2
d3*10^4
x1y1*10^8
|
54,594,047
1,200,776,340,000
5,819,263,900,000,000
|
Computed above
O)n)
O(n)
|
|
x1y1*10^8 + d3*10^4 + x2y2
|
5,820,464,730,934,047
|
O(n)
|
5) Write a function to traverse a general tree stored with child/sibling with postorder.
ADT:
typedef struct node *node_ptr
struct node {
type elem;
node_ptr child;
node_ptr sibling;
