Purchase Solution

Algorithm analysis for N elements

Not what you're looking for?

Ask Custom Question

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;
}

The tree should be something like below where black arrows are children and reds are siblings.

Attachments
Purchase this Solution

Solution Summary

The solution provides an algorithm analysis for N elements by creating a program to run.

Solution Preview

Please see the attachment.

Problem #1
I attached a slides to show that this problem can be solved in linear time . Please see my slides.
Here is the pseudo-code corresponding to the algorithm in the slides.
int kthLargest(int array[], int k)
BEGIN
1. int L[] = {}; // Define an empty array L
2. int R[] = {}; // Define an empty array R
3. m = selectMedian(array[]); // Select the median element in array
4. For i=0; i<array.length; i++) {
4.1 If array[i]>m Then L=L+array[i]; // Larger element is added to L
4.2 If array[i]<m Then R=R+array[i]; // Smaller element is added to R
5. EndFor
6. if (k==m) return m;
7. if (k<m) return kthLargest(L, k); // Find kth largest element in L
8. if (k>m) return kthLargest(R,k); // Find kth largest element in R
END
int select(array[])
BEGIN
1. Let n = array.length; // n is the length of the array
2. If n<=5 Then // If ...

Purchase this Solution


Free BrainMass Quizzes
Javscript Basics

Quiz on basics of javascript programming language.

Inserting and deleting in a linked list

This quiz tests your understanding of how to insert and delete elements in a linked list. Understanding of the use of linked lists, and the related performance aspects, is an important fundamental skill of computer science data structures.

Basic Networking Questions

This quiz consists of some basic networking questions.

Word 2010: Tables

Have you never worked with Tables in Word 2010? Maybe it has been a while since you have used a Table in Word and you need to brush up on your skills. Several keywords and popular options are discussed as you go through this quiz.

Excel Introductory Quiz

This quiz tests your knowledge of basics of MS-Excel.