Exercise 1

Read through an example of how to go from a high-level idea to an actual implementation. There's nothing to submit for this part.
Pen-and-paper exercises:
1. Among the following functions, for each distinct pair f_i and f_j, identify the "order" relationship: is f_i = O(f_j), f_i = Ω(f_j), or f_i = Θ(f_j)? The functions are:
  f₁(n) = n,
  f₂(n) = n log(n),
  f₃(n) = n log(n²),
  f₄(n) = n^2.5,
  f₅(n) = n sqrt(n),
  f₆(n) = n²log(n).
2. Find the appropriate "order" relationship between n log(n) and 10n and find the constants c and N.
3. Analyze the following code and provide a "Big-Oh" estimate of its running time. Explain your analysis.
```
    for (int i=0; i < n; i++) {
      for (int j=0; j < n*n; j++)
        sum += data[i] * data[j];
      for (int j=0; j < 4*n; j++)
        sum += data[i] + data[j];
    }
  
```
4. Duplicate removal, part I. In this problem, we are given an array of positive (nonzero) integers with possible duplicates, such as: [2,3,2,2,1]. The general goal is to return a new array with all the duplicates removed, as in: [2,1,3]. We'll consider a variation in which we return the original array reorganized so that all the unique elements are found from the first element onwards until the last unique element, as in: [2,1,3,_,_]. Here, we also compute the new length n=3, which is the number of non-duplicate elements. The reorganized array need not have the elements in the same order as in the original. Now consider the following attempt, written in pseudocode. (Assume array indices start at 1, and the array A. is available globally to all the methods):
```
    Algorithm: removeDuplicates
        for i=1 to n 
            if isDuplicate (i)
                remove (i)
            endif
        endfor
    return n

    Method: isDuplicate (i)
        for j=1 to n
            if A[j] = A[i]
                return true
            endif
        endfor
        return false

    Method: remove (i)
    // Removes and performs a left-shift.
        for j=n-1 to i
            A[j] = A[j+1]
        endfor
        n = n -1
     
```
  - If the algorithm were to work, how long does it take to run, expressed in order-notation? Explain your answer.
  - There are actually some algorithmic errors (we won't worry about syntax). Can you find them? How would you fix them? Submit corrected pseudocode, written in the same style.
Note: Credit will not be given only for answers - show all your work: your reasoning, steps you took to get your answer etc.
Implement the Insertion Sort method (see the Wikipedia entry) and compare it to the SelectionSort technique in Module 1. To implement, you will need to follow these steps:
- Create a separate directory for the course called cs3212.
- Follow the submission instructions to download the algorithm test environment, if you haven't already done this earlier.
- Create a directory called ex1 under cs3212 for all the work in this exercise.
- Next, download the following two text files: ex1.props and ex1.props2
- Write your code in files called InsertionSort.java and SelectionSort.java.
- Both of these need to implement the SortingAlgorithm interface. Note that your class will need to implement the Algorithm interface because SortingAlgorithm extends Algorithm.
- In implementing the Algorithm interface, only provide an empty implementation for setPropertyExtractor.
- You will only need to write code for the sortInPlace (int[]) method in the SortingAlgorithm interface. However, you will need to provide at least empty implementations (method definition, but empty body) for the other methods. We will not test the other methods.
- Once you have written and compiled the code for both algorithms and want to test: get into the yourusername1 directory and simply type the following (for Unix):
```
      % java -jar ../algtest.jar ex1.props
    
```
  (You can run something similar with a DOS-prompt). The jar file contains an algorithm test environment which will run your program and perform some tests.
- If you like you may run a test with the second properties file, ex1.props2. For this purpose you will have to be at a machine that can display a Java GUI (so, you can't run it on hobbes).
Write code that takes as input an array of integers and rearranges the array to have the following property:
- Suppose the first element in the original array has the value x.
- In the new array, suppose that x is in position i, that is data[i] = x. Then, data[j] <= x for all j < i and data[j] > x for all j > i. Thus, informally, all the values to the "left" of x are less than (or equal to) x and all values to the right are larger than x.
- Here's an example. Suppose the array has the elements in this initial order: 4,3,9,2,7,6,5. After one possible (there are many) partition, we get: 3,2,4,5,9,7,6. That is, the leftmost element, 4, is positioned in the resulting array so that all elements less than 4 (that is, 2, 3) are to its left (in no particular order), and all elements larger than 4 are to its right (again, in no particular order).
Write your code in a file called MyPartition.java:
- Make your class it implement the PartitionAlgorithm interface.
- You will only need to write code for the leftIncreasingPartition method. Provide an empty implementation for the other - we will not test it. Note: your partitioning code will be in this method.
- Observe that you are given a sub-range within the array which you will re-arrange. Do NOT touch elements outside the subrange.
- Use the ex1.props3 properties file for this problem.

Note:

What is an empty implementation of a method? For a void-returning method, it means you write out the method definition (with parameters) and curly braces, but don't add any code in between the braces. For a method that needs to return something, you can return some default value. The purpose is just to let the result compile.
Unless otherwise specified we will assume that all sorting algorithms in this course will sort in increasing order (smallest element first).

NOTE: do NOT write code for interfaces that we provide, such as the SortingAlgorithm interface. or PartitionAlgorithm interface. These interfaces are already in algtest.jar. In general, when you write code for an algortihm in a Java class, that class will need to implement the appropriate interface, as in:


    import edu.gwu.algtest.*;
    import edu.gwu.util.*;
    import edu.gwu.debug.*;

    public class MyPartition implements PartitionAlgorithm {

        public int leftIncreasingPartition(int[] data, int left, int right)
        {
            // Your code here 
        }

        public int rightIncreasingPartition(int[] data, int left, int
    right)
        {
            // Empty implementation 
            return -1;
        }

        public static void main (String[] argv)
        {
            // Your own test code here 
        }

    }

For each of your algorithms, write a main method in which you perform some testing independent of the environment we provide you. You will be graded on the testing you perform.
The algorithm testing environment only helps with testing - it does NOT help with debugging, which you are expected to do on your own. In this regard, the test-environment may indicate that your code has failed a test, but will not provide additional detail (this is what we mean by "helps with testing, but not debugging").
For this assignment and others, we expect you to write clean, documented code following the guidelines mentioned on the homepage.

Submission:

Do NOT submit hardcopy of your code. All pen-and-paper submissions need to be PDF in the same zip file that you upload for an Exercise or Assignment.
For this Exercise, call your PDF ex1.pdf
For this assignment and others, you will need to follow submission instructions carefully.