Implement the first algorithm for finding the kth smallest integer in a set of integers and test your program for different sets of integers generated by a random number generator. Implement the...

1 answer below »


Implement the first algorithm for finding the kth smallest integer in a set of integers and test your program for different sets of integers generated by a random number generator.






Implement the first algorithm without using a temporary array for partitioning .






Implement the second algorithm for finding the kth smallest integer and test your program for different sets of integers generated by a random number generator and compare the CPU times for both algorithms


1. Write a dive and conquer algorithm for determining the best time to purchase and the best time to sell a stock. Assume the price of the stock vs the time is represented by the array S of integers. Compute the complexity of your algorithm. The complexity should be not more than Θ (nlogn).



i.e Given an array A of non-negative integers of size n. Find the two indices p and s ,


0=



Indices.


















2. Use the divide and conquer technique to develop an efficient algorithm that finds the index of the turning point in a sequence of at least three integers. The sequence consists of an increasing subsequence of at least one integer and is followed by a decreasing subsequence of at least one integer. For example,



7 8 9 20 40 30 15 10



The integer 40 is the turning point and its index =4 (starting from zero)




Compute the best complexity, worse complexity, and average complexity.














3. Write for the following problem a recursive algorithm whose worst-case time complexity is not worse than Θ (n∙lgn). Given a list of n distinct positive integers, partition the list into two sublists, each of size n/2, such that the difference between the sums of the integers in the two sublists is maximized. You may assume that n is a multiple of 2.



Suggest an algorithm with worse complexity Θ(n).






















4. Write an efficient algorithm that searches for a value in the n × m table A (two-dimensional array). This table is sorted along the rows and columns —that is,



A[i][j]




A[i][j]


6. Rewrite the algorithm for merging two sorted subarray of the array A( listed below )with out storing the repeated value. Assume each sorted subarray has no repeated value.



void merge2(index low, index mid, index high)


{


index i,j,k;


keytype U{low..high];


i=low;j=mod+1;k=low;


while (i


{


if (S[i]


{


U[k]=S[i];


i++;


}


else


{


U[k]=S[j]


j++;


}


k++;


}


if (i>mid)


move S[j] through S[high} to U[k] through U[high];


else


move S[j] through S[high] to U[k] through U[high];


move U[low] through U[high] to S[low} through S[high];


}





tfth-2-rarggrhu-cdxjuirm.docx
Answered 1 days AfterJul 09, 2021

Answer To: Implement the first algorithm for finding the kth smallest integer in a set of integers and test...

Kshitij answered on Jul 10 2021
133 Votes
jul09_21/Algo1.java
jul09_21/Algo1.java
/*   Created by IntelliJ IDEA.
 *   Author: Kshitij Varshney (kshitijvarshne1)
 *   Date: 09-Jul-21
 *   Time: 5:54 PM
 *   File: Algo1.java
 */
package July.jul09_21;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
public class Algo1 {
    public static void main(String[] args) {
        Set s = new HashSet<>();
        for (int i = 0; i < 50; i++) {
            s.add((int) (Math.random() * 100 + 1));
        }
        System.out.println(findKthSmallest(s, 4));
    }
    private static Integer findKthSmallest(Set s, int k) {
        int arr[] = new int[s.size()];
        int i = 0;
        for (Integer integer : s) {
            arr[i] = integer;
            i++;
        }
        Arrays.sort(arr);
        return arr[k - 1];
    }
}
jul09_21/Algo2.java
jul09_21/Algo2.java
/*   Created by IntelliJ IDEA.
 *   Author: Kshitij Varshney (kshitijvarshne1)
 *   Date: 10-Jul-21
 *   Time: 5:25 PM
 *   File: Algo2.java
 */
package July.jul09_21;
import java.util.Collections;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;
public class Algo2 {
    public static void main(String[] args) {
        Set s = new HashSet<>();
        for (int i = 0; i < 50; i++) {
            s.add((int) (Math.random() * 100 + 1));
        }
        System.out.println(findKthSmallest(s, 4));
    }
    // without using any array
    private static Integer findKthSmallest(Set s, int k) {
        PriorityQueue maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        for (Integer i : s) {
            maxHeap.add(i);
            if (maxHeap.size() > k) {
                maxHeap.poll();
            }
        }
        return maxHeap.poll();
    }
}
jul09_21/Algo3.java
jul09_21/Algo3.java
/*   Created by IntelliJ IDEA.
 *   Author: Kshitij Varshney (kshitijvarshne1)
 *   Date: 10-Jul-21
 *   Time: 5:30 PM
 *   File: Algo3.java
 */
package July.jul09_21;
import java.util.*;
public class Algo3 {
    public static void main(String[] args) {
        int start = (int) (System.currentTimeMillis() / 100);
        Set s = new HashSet<>();
        for (int i = 0; i < 50; i++) {
            s.add((int) (Math.random() * 100 + 1));
        }
        System.out.println(findKthSmallest(s, 4));
        long end1 = (int) System.currentTimeMillis() / 100;
        long totalTime = end1 - start;
        System.out.println("Total execution time :- " + totalTime / 1000);
        long start1 = System.currentTimeMillis() / 100;
        System.out.println(findKthSmallest2(s, 4));
        long end2 = (int) System.currentTimeMillis() / 100;
        long totalTime2 = end2 - start1;
        System.out.println("Total execution time :- " + totalTime2 / 1000);
    }
    private static Integer findKthSmallest(Set s, int k) {
        PriorityQueue maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        for (Integer i : s) {
  ...
SOLUTION.PDF
SOLUTION.PDF

Answer To This Question Is Available To Download

Related Questions & Answers

More Questions »

Submit New Assignment

Copy and Paste Your Assignment Here
Have files?