Exercise 1

Note: Credit will not be given just for answers - show all your work: your reasoning, steps you took to get your answer etc.

1. Read through an example of how to go from a high-level idea to an actual implementation.

2. Pen-and-paper (PDF) 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).
      You do not need to find c and N in every case (although you certainly can), but you do need to provide reasoning.
   2. Compare f(n)=n and g(n) = (log₂(n))²:
      • Plot both to see which one grows faster.
      • Instead of a detailed analysis using c and N, find a simpler argument to show that one of them eventually rises above the other.
   3. Analyze the following pseudocode and provide a "Big-Oh" estimate of its running time in terms of n. Explain your analysis.

      
          for i=1 to n
              for j=1 to i
                  for k=1 to j
                      sum = sum + data[i] + data[j] + data[k]
        

3. For the rest of the semester, it will be essential to know how to work with Java interfaces, both with interfaces created expressly for this course and the Java API's own interfaces.
   • Review Java interfaces.
   • Especially examine the Comparable interface. Try to find some examples using that interface.
   • Write the few lines of code needed to make the Comparable interface work for the object A in this example: CompInterfaceExample.java.
   • In your PDF for this exercise, draw a memory diagram showing the contents of the system stack (method stack) and heap before the first call to compareTo() returns. How does Java's sort method know how to sort the array of A instances, since the sort method was written and compiled long before the code for class A was written?
   Note: You will almost never write the code for an interface. Instead, your classes will implement interfaces that are already in algtest. For example, in the code below, your sorting algorithm will need to implement the Algorithm interface (among other interfaces). You have the link to the description of the interface (which tells you what methods your class needs to implement), but you don't write the interface code itself. That code is already in algtest.jar.

4. 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:
   • First: (1) create a separate directory for the course called cs3212; (2) create a directory called ex1 off of your home directory.
   • Follow the submission instructions to download the algorithm test environment.
   • Create a subdirectory called ex1 You will implement AND execute your insertion sort code in this directory.
   • 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 you will also need to implement the Algorithm interface because SortingAlgorithm extends Algorithm.
   • NOTE: both interfaces Algorithm and SortingAlgorithm are included in algtest.jar. You do not write the code for these interfaces.
   • When your class implements 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 - just the curly brackets) for the other methods. We will not test the other methods.
   • Once you have written the code for both algorithms and want to test: get into the ex1 directory and simply type the following (for Unix) at the commandline:

     
           java -jar ../algtest.jar ex1.props
         

     (You can run something similar with a DOS-prompt on Windows). The jar file contains the 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.

5. In this part of the exercise, you will 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, we want the rearranged array to be such that data[j] <= x for all j < i and data[j] > x for all j > i. Thus, informally, the rearranging places 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).
   • This same idea, which we will call partitioning, can be applied to a part of an array as well. For example, suppose we partition the part of the array below in bold:

     
            4 3 6 2 9 7 5
         

     After partitioning that part, we will get something like:

     
            4 3 2 6 9 7 5
         

     (using 6 as the partitioning element).
   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.
• In just about every algorithm you write, you will need to have your class implement the Algorithm interface. This has two methods, both of which you must implement. For the getName() method, you must return something sensible (with your name embedded). For setPropertyExtractor() method, you will just provide an empty body, unless we specify otherwise.
• Unless otherwise specified we will assume that all sorting algorithms in this course will sort in increasing order (smallest element first).
• 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:

• For this assignment and others, you will need to follow submission instructions carefully.