linear-expected-time algorithm, Data Structure & Algorithms

Implement a linear-expected-time algorithm for selecting the kth smallest element

Algorithm description

1. If |S| = 1, then k = 1 and return the element in S as the answer.

2. Pick a pivot element, v[S]. Partition S-{v} into S1 and S2, as done with quicksort

3. If k<=|S1|, then the kth smallest element must be in S1. In this case, return quickselect(S1,k).

4. If k=1+|S1|, the pivot is the kth smallest element and return it.

5. Otherwise, the kth smallest element lies in S2, and it is the (k-|

S1|-1)st smallest element in S2, and return quickselect(S2,k-| S1|-1).

Deliverables

1. Source code, i.e. *.java file

2. Time complexity analysis

 

Posted Date: 3/14/2013 1:46:55 AM | Location : United States







Related Discussions:- linear-expected-time algorithm, Assignment Help, Ask Question on linear-expected-time algorithm, Get Answer, Expert's Help, linear-expected-time algorithm Discussions

Write discussion on linear-expected-time algorithm
Your posts are moderated
Related Questions
Program for Linear Search. Program: Linear Search /*Program for Linear Search*/ /*Header Files*/ #include #include /*Global Variables*/ int search; int

Data type An implementation of an abstract data type on a computer. Therefore, for instance, Boolean ADT is implemented as the Boolean type in Java, and bool type in C++;

Q. What is the need of using asymptotic notation in the study of algorithm? Describe the commonly used asymptotic notations and also give their significance.

Think of a program you have used that is unacceptably slow. Identify the specific operations that make the program slow. Identify other basic operations that the program performs q

Definition of Algorithm Algorithm must have the following five characteristic features: 1.      Input 2.      Output 3.      Definiteness 4.      Effectiveness 5

Explain the Scan-Line Algorithm This image-space method for removing hidden surfaces is an extension of the scan-line algorithm for filling polygon interiors. Instead of fillin

What do you mean by hashing? Hashing gives the direct access of record from the file no matter where the record is in the file. This is possible with the help of a hashing func

What is a first-in-first-out data structure ? Write algorithms to perform the following operations on it – create, insertion, deletion, for testing overflow and empty conditions.

Q. Prove the hypothesis that "A tree having 'm' nodes has exactly (m-1) branches".      Ans: A tree having m number of nodes has exactly (m-1) branches Proof: A root

What is Efficiency of algorithm? Efficiency of an algorithm can be precisely explained and investigated with mathematical rigor.  There are two types of algorithm efficiency