Assignment 3 - COP 3530, Fall 2007

Please read the assignment submission rules and the academic dishonesty page before you start work on this assignment. Failure to comply by these rules will cost a significant percentage of your assignment grade.

Remember:

Have your name, UF ID, and discussion session number as comments at the top of your code.
ONLY SOFT copy is REQUIRED.
Put each question in a separate file. One file one question ONLY.
Jar all the files directly WITHOUT the dataStructures folder.
Make sure to write a main method for every coding problem at the end of your code.
Put the complexity analysis and other non-coding parts of THIS question in comments at the beginning of your code.
For pen-paper questions, we only accept the following format file: Plain TEXT and PDF. Plain TEXT format is preferred. Also put each pen-paper question in separated files. Name it as Qx.txt, where x is the sequence number of this question. For example, if Question 1 is a pen-paper question, put your solution to the file "Q1.txt"
Misspellings and wrong capitalization of class and method names (Java is case sensitive), incorrect method signatures, and improper jarring of files will be penalized heavily.

Make sure your classes are in the package dataStructures. If you do not understand what packages are you can read this tutorial, if you have trouble with the classpath settings you could try reading this tutorial.

For any coding question below, even though you may not use any of the methods of the class you are extending, you MAY use the constructor of the class to be extended when you create the constructor of your new class. For example, you may do something like this:

public ALLExtended (){

   super();

public ALLExtended( int n ){

   super(n);

You may NOT use any built-in array functions in the java API.

In this problem you will run simulations to compare the time complexity of three sorting algorithms: quick sort, selection sort, and insertion sort.
There will be no coding involved, as the driver class is given below and the sorting algorithms are implemented in the applications package.

package applications;

import dataStructures.*;

import java.util.EnumSet;

import java.util.Random;

public class TimeComplexity {

public static double counter_ = 0;

public enum SortOption {

HeapSort,QuickSort, SelectionSort, InsertionSort

}

public static void sort(Comparable[] task, SortOption option) {

counter_ = 0;

switch (option) {

case HeapSort:

break;

case QuickSort:

QuickSort.quickSort(task);

break;

case SelectionSort:

SelectionSort.selectionSort(task);

break;

case InsertionSort:

InsertionSort2.insertionSort(task);

break;

}

public static void main(String[] args) {

int n = 5000; // size of the lists to be sorted

Random generator = new Random(19580427);

double[] time = new double[10]; //keeps the total times for each sorting method

for (int i = 0; i < 10; i++) {

time[i] = 0;

}

Integer[] lst = new Integer[n];

int round = 10; //number of times the test will be run

for (int j = 0; j < round; j++) {

for (int i = 0; i < n; i++) {

lst[i] = generator.nextInt(); //Random data set

}

int index = 0;

for (SortOption so : EnumSet.range(SortOption.QuickSort, SortOption.InsertionSort)) {

Integer[] tempLst = lst.clone();

long startTime = System.nanoTime();

sort(tempLst, so);

time[index] += System.nanoTime() - startTime;

index++;

}

int index = 0;

for (SortOption so : EnumSet.range(SortOption.QuickSort, SortOption.InsertionSort)) {

String output = "";

output = "For " + so.toString() + " with array size of: " + n;

output = output + " Average time consumption: " + time[index] / (1000000* round) + "ms";

System.out.println(output);

System.out.println("");

index++;

}

(a) Test these sorting algorithms on random data sets with different sizes (ie. 50, 500, 1000, 5000). Record the results.

(b) Guess the time complexity of these algorithms using your results. Do they agree with theoretical expectations?

Note:

1) This sample program should be complied and launched from /applications instead of /dataStructures. Java version 1.5 or higher is also required.

2) When you apply the quick sort to arrays containing more than 3000 elements, you may get the following exception:

>java applications.TimeComplexity

Exception in thread "main" java.lang.StackOverflowError

at applications.QuickSort.quickSort(QuickSort.java:38)

at applications.QuickSort.quickSort(QuickSort.java:53)

at applications.QuickSort.quickSort(QuickSort.java:54)

at applications.QuickSort.quickSort(QuickSort.java:53)

To avoid this exception, you should launch your class using:

> java -Xoss8m -Xss8m applications.TimeComplexity

Here, we use –Xoss and –Xss to specify the stack size of our program directly. 8m is the new stack size. If the problem persists, try a bigger stack or contact TAs. The reason for this problem is the data structures package implements the quick sort recursively. As a result, the program stack with the default size (about 256K) soon gets exhausted.

2. Extend the class ArrayLinearList to include a new method delete( int pos, int k) that deletes k elements starting at the position pos from the original ArrayLinearList. For example, consider the original list L = [0,1,2,3,4,5]. Assuming ArrayLinearList starts from position 0, after L.delete(2,3) is invoked, L becomes [0,1,5].

The template for the class is given below:

package dataStructures;

import utilities.ChangeArrayLength;

public class ArrayLinearListWithDelete extends ArrayLinearList {

// data members (if necessary) go here

// constructors go here

public void delete(int pos, int k) {

// your code goes here

}

// helper methods(if necessary) go here

public static void main(String[] args)

{

ArrayLinearListWithDelete L = new ArrayLinearListWithDelete();

for (int i = 0; i < 6; i++)

{

L.add(i, i);

}

System.out.println(L.toString());

L.delete(2,3);

System.out.println(L.toString());

}

You are not allowed to call the method remove ( int index) in the ArrayLinearList class. Calling such methods can cost up to 100% of the question grade.

(a) Why is the following implementation of delete( int pos, int k) incorrect? If corrected, would it be efficient?

public void delete (int pos, int k) {

if (k<0)

{

throw new IndexOutOfBoundsException("k < 0");

}

if (pos < 0 || pos + k > size)

{

throw new IndexOutOfBoundsException("pos = " + pos + " size = " + size);

}

for(int i = 0 ; i < k ; i++)

{

for( int j = size - 1; j > pos ; j-- )

{

element[j - 1] = element[j];

}

size--;

}

(b) Write your code for the class ArrayLinearListWithDelete. Test your code.

(d) Write your own code to compare the time consumption of your own delete function and the one given in (a), by simulating deletion of 50, 500 and 5000 elements from a random array with a size of 6000. The deletion should start from the same position.

Note:

You may place the code for (d) within the same java file for (b). In this way, you can name the implementation in (a) as “deleteSlow(int pos, int k)”. You may also add a new method “simulate()” to ArrayLinearListWithDelete for the simulation, if you don’t want to put too much code in the main function.