CSC 17 Lab 4:


1. Finish lab 3.


2. Extra exercise (part theoretical, part implementation):

1. Devise (on paper) an algorithm to find the ith largest element
in an array.  Sketch the pseudocode of a function that returns the
*index* of the ith largest element.

For example, if A is the array int[] A = {3,1,4,6,7,8,2,9}; then
calling your function ithlargest(A,3) should return 4, which is the
*index* of the 7, which is the third largest integer in the array.  If
the ith largest element does not exist: (for example, when A is {5,2},
there is no 3rd largest element) your function can just return -1.
Duplicates count.  For example, the third largest element in
{5,5,5,5,5} is 5.

3. NOW analyze the time complexity of your algorithm for the AVERAGE
and WORST case scenarios. The measure of complexity should be relative
to the size of the array.  Is it linear, logarithmic, ... or ??

4. Implement the function in java:

public class lab4
{
  public static int ithlargest(int[] A, int i)

  // ... (also write a main to test)
}

part 4 will be graded on a "best effort" basis.