Project due date is March 1, 2018 by 1:00pm central time

In this project, you will work on the algorithm (discussed in Module 1) to determine the length of the

longest sub sequence of consecutive integers in an array.

You will implement the algorithm using Hash tables. You are provided with sample code in

Java representing the linked list-based implementation of Hash tables (as an array of Linked Lists). You

could go through the code to understand the implementation of a Hash table and the functions that can be

called on it.

In the Module 1 slides, it was mentioned that the array of integers for the algorithm has to be unique.

Actually, it is not a mandatory requirement. The algorithm can still work on a random array of integers

with some integers repeated. However, for an arbitrary array (that could have repeated integers), the

algorithm could waste time in determining multiple occurrences of the same sub sequence of consecutive

integers. For example, if the array is: 7 2 1 3 1 1 3 4, the algorithm would find three instances of the

longest sub sequence 1 2 3 4 as well as two occurrences of a smaller sub sequence 3 4. On the other hand,

if the array is: 7 2 1 3 4, the algorithm would find only one instance of the longest sub sequence 1 2 3 4.

In this project, you will implement two versions of the algorithm: The first version would be the

implementation of the algorithm (as discussed in Module 1) without any optimization. The second version

would be an implementation of the algorithm with an optimization strategy. In this regard, you are

supposed to design a strategy to prevent the algorithm from searching for the same sub sequence more

than once and implement an optimized version of the algorithm incorporating the strategy. You could use

additional space as part of this optimization strategy, as large as O(n), where n is the number of elements

in the input array. The expectation is that the additional space used would aid in reducing the run time.

You are given a startup code in Java titled: HashTable_LinkedList_ContinuousSeqVersion

that has the Linked List-based implementation of a Hash table as well as the main function setup to run

the algorithm for several trials and measure the average length of the longest sub sequence of consecutive

integers and the average run time (referred to in the code as average detection time and is measured in

milliseconds).

The number of trials is always 25. The maximum value for an element in the array is 25000 (i.e., the

range of elements generated is 1...25000). Note that the programs are likely to run for a longer time, even

if the implementation is correct. So, patiently wait!

The parameters that you will vary for a particular run of the code are as follows:

(N) number of elements to be generated: 10000, 100000

(S) size of the hash table: 11, 101, 1009

Report (Submission) :Include the following and submit as one single PDF file.

(1 - 25 pts) Provide a description of your optimization strategy and explain how it could reduce the run

time at the cost of additional space, if any.

(2 - 45 pts) The implementation code of the algorithm without and with optimization.

(3 - 15 pts) Present a table (the values of N as rows and the values of S as columns) for each of the

average largest sequence length and the average detection time (in milliseconds).

(4 - 15 pts) Discuss the impact of the size of the hash table on the average detection time

Code Project Using Start up code below:

import java.util.*;

// implementing hash tables as an array of linked lists

class Node{

private int data;

private Node nextNodePtr;

public Node(){}

public void setData(int d){

data = d;

}

public int getData(){

return data;

}

public void setNextNodePtr(Node nodePtr){

nextNodePtr = nodePtr;

}

public Node getNextNodePtr(){

return nextNodePtr;

}

}

class List{

private Node headPtr;

public List(){

headPtr = new Node();

headPtr.setNextNodePtr(null);

}

public Node getHeadPtr(){

return headPtr;

}

public boolean isEmpty(){

if (headPtr.getNextNodePtr() == null)

return true;

return false;

}

public void insert(int data){

Node currentNodePtr =

headPtr.getNextNodePtr();

Node prevNodePtr = headPtr;

while (currentNodePtr != null){

prevNodePtr = currentNodePtr;

currentNodePtr =

currentNodePtr.getNextNodePtr();

}

Node newNodePtr = new Node();

newNodePtr.setData(data);

newNodePtr.setNextNodePtr(null);

prevNodePtr.setNextNodePtr(newNodePtr);

}

public void insertAtIndex(int insertIndex, int data){

Node currentNodePtr =

headPtr.getNextNodePtr();

Node prevNodePtr = headPtr;

int index = 0;

while (currentNodePtr != null){

if (index == insertIndex)

break;

prevNodePtr = currentNodePtr;

currentNodePtr =

currentNodePtr.getNextNodePtr();

index++;

}

Node newNodePtr = new Node();

newNodePtr.setData(data);

newNodePtr.setNextNodePtr(currentNodePtr);

prevNodePtr.setNextNodePtr(newNodePtr);

}

public int read(int readIndex){

Node currentNodePtr =

headPtr.getNextNodePtr();

Node prevNodePtr = headPtr;

int index = 0;

while (currentNodePtr != null){

if (index == readIndex)

return

currentNodePtr.getData();

prevNodePtr = currentNodePtr;

currentNodePtr =

currentNodePtr.getNextNodePtr();

index++;

}

return -1; // an invalid value indicating

// index is out of range

}

public void modifyElement(int modifyIndex, int data){

Node currentNodePtr =

headPtr.getNextNodePtr();

Node prevNodePtr = headPtr;

int index = 0;

while (currentNodePtr != null){

if (index == modifyIndex){

currentNodePtr.setData(data);

return;

}

prevNodePtr = currentNodePtr;

currentNodePtr =

currentNodePtr.getNextNodePtr();

index++;

}

}

public boolean deleteElement(int data){

Node currentNodePtr =

headPtr.getNextNodePtr();

Node prevNodePtr = headPtr;

Node nextNodePtr = headPtr;

while (currentNodePtr != null){

if (currentNodePtr.getData() == data){

nextNodePtr =

currentNodePtr.getNextNodePtr();

prevNodePtr.setNextNodePtr(nextNodePtr);

return true;

}

prevNodePtr = currentNodePtr;

currentNodePtr =

currentNodePtr.getNextNodePtr();

}

return false;

}

public int countList(){

Node currentNodePtr =

headPtr.getNextNodePtr();

int numElements = 0;

while (currentNodePtr != null){

numElements++;

currentNodePtr =

currentNodePtr.getNextNodePtr();

}

return numElements;

}

public void IterativePrint(){

Node currentNodePtr =

headPtr.getNextNodePtr();

while (currentNodePtr != null){

System.out.print(currentNodePtr.getData()+" ");

currentNodePtr =

currentNodePtr.getNextNodePtr();

}

System.out.println();

}

public boolean containsElement(int data){

Node currentNodePtr = headPtr.getNextNodePtr();

while (currentNodePtr != null){

if (currentNodePtr.getData() == data)

return true;

currentNodePtr =

currentNodePtr.getNextNodePtr();

}

return false;

}

}

class Hashtable{

private List[] listArray;

private int tableSize;

public Hashtable(int size){

tableSize = size;

listArray = new List[size];

for (int index = 0; index < size; index++)

listArray[index] = new List();

}

public int getTableSize(){

return tableSize;

}

public void insert(int data){

int hashIndex = data % tableSize;

listArray[hashIndex].insert(data);

}

public void deleteElement(int data){

int hashIndex = data % tableSize;

while (listArray[hashIndex].deleteElement(data));

}

public boolean hasElement(int data){

int hashIndex = data % tableSize;

return listArray[hashIndex].containsElement(data);

}

public void printHashTable(){

for (int hashIndex = 0; hashIndex < tableSize;

hashIndex++){

System.out.print("Hash Index: " +

hashIndex + " : ");

listArray[hashIndex].IterativePrint();

}

}

}

class HashTable_LinkedList_ContinuousSeqVersion{

public static void main(String[] args){

Scanner input = new Scanner(System.in);

int numElements;

System.out.print("Enter the number of elements you want to store in

the hash table: ");

numElements = input.nextInt();

int maxValue;

System.out.print("Enter the maximum value for an element: ");

maxValue = input.nextInt();

int hashTableSize;

System.out.print("Enter the size of the hash table: ");

hashTableSize = input.nextInt();

int numTrials;

System.out.print("Enter the number of trials: ");

numTrials = input.nextInt();

Random randGen = new Random(System.currentTimeMillis());

int totalLongestSequenceLength = 0;

long totalDetectiontime = 0;

for (int trials = 1; trials <= numTrials; trials++){

long startTime = System.currentTimeMillis();

Hashtable hashTable = new Hashtable(hashTableSize);

int array[] = new int[numElements];

for (int index = 0; index < numElements; index++){

array[index] = 1 + randGen.nextInt(maxValue);

hashTable.insert(array[index]);

}

int longestSubsequenceLength = 0; // longest sequence length for the

particular trial

// Implement your algorithm here and find the longestSequenceLength

for the array

long endTime = System.currentTimeMillis();

totalLongestSequenceLength += longestSubsequenceLength;

totalDetectiontime += (endTime - startTime);

}// trials

System.out.println("Average Longest Subsequence Length: "+(((double)

totalLongestSequenceLength)/numTrials));

System.out.println("Average detection time (milliseconds):

"+(((double) totalDetectiontime)/numTrials));

}

}

Annotations