CSC2001F - Assingment 1 Solved

Classes

 

There are 3 classes in total:

1. Dam

2 BinarySearchTree, BinaryTree, BinaryTreeNode, BinaryQueueNode, BinaryQueue

3. DamArrayApp

4. DamBSTApp

5. BSTrun

 

The Dam class contains the instance variables that are required to create a Dam.

There is a contructor that can be used to initalize Dam objects.

There is an appropriate toString()  method to print out Dam objects.

There is a compareTo() method that compares Dam names.

 

The BinarySearchTree class can create a BinarySearchTree of any data type.

It contains an insert method to add values to the BinarySearchTree.

It contains a delete() method to remove values.

It has a preOrder(), inOrder() and postOrder() method to print the values from the BinarySearchTree in different sorting pattern.

The other classes help create the Binary searchTree

 

The DamArrayApp class will create an array of Dam objects from the csv file.

The main method of the class will print all Dam objects from the array if no argument is given.

The main method will print the Dam object whose name is given as argument. It will also print out the number of comparisons that were made before finding the required Dam. If no Dam is found, the user will be told and  211 will be printed.

 

The DamBSTApp will create a variable of type BinarySearchTree and store all the Dam objects inside it.

The main method will print all Dam objects from the BinarySearchTree is no argument is given.

The main method will print the Dam object whose name is given as argument. It will also print out the number of comparisons that were made before finding the required Dam. In the case when the Dam was not found, the user will be told so.

 

BSTrun was used to obtain data to plot graphs. The size of the BinarySearchTree was varied and every element searched. The number of comparisons was then recorded.

 

 

 

 

Objective.

 

The goal of this experiment is to compare the searching efficiency of a Binary Search Tree to that of an unsorted Array.

This was done by searching for a Dam object in both data structures.

The number of comparisons(count) made before finding the object was recorded as a meaure of efficiency.

The size of the dataset(n) was varied and the respective count values were recorded for both data structures.

A graph of n(x-axis) against count(y-axis) is used to identify the best case, average case and worse case when searching through both data structures.

 

Trial runs.

 

When running the DamArrayApp with no argumnent, the first 10 lines were:

 

Name: Ngotwane Dam, FSC: 19.033000000000001, Percentage: 4.6

Name: Hartbeespoort Dam, FSC: 186.44, Percentage: 96.5

Name: Bon Accord Dam, FSC: 4.381, Percentage: 103

Name: Olifantsnek Dam, FSC: 13.677, Percentage: 32.9

Name: Rietvlei Dam, FSC: 12.25, Percentage:

Name: Buffelspoort Dam, FSC: 10.183, Percentage: 71.400000000000006

Name: Bospoort Dam, FSC: 15.798999999999999, Percentage: 98.1

Name: Lindleyspoort Dam, FSC: 14.208, Percentage: 2.7

Name: Warmbad Dam, FSC: 0.549, Percentage:  

Name: Roodeplaat Dam, FSC: 41.158000000000001, Percentage: 98.3

 

and the last 10 lines were:

 

Name: Vygeboom Dam, FSC: 78.02, Percentage: 65.7

Name: Driekoppies Dam, FSC: 250.92, Percentage: 43.7

Name: Maguga Dam, FSC: 333.75, Percentage: 29.6

Name: Longmere Dam, FSC: 4.202, Percentage: 60.4

Name: Klipkopjes Dam, FSC: 11.776999999999999, Percentage: 45.7

Name: Witklip Dam, FSC: 12.519, Percentage: 39.299999999999997

Name: Primkop Dam, FSC: 1.899, Percentage: 14.6

Name: Kwena Dam, FSC: 158.88999999999999, Percentage: 48.2

Name: Da Gama Dam, FSC: 13.526, Percentage: 57.9

Name: Inyaka Dam, FSC: 123.66, Percentage: 63.5

 

When running the DamArrayApp with 3 known Dam names the output was:

 

rahul@rahul-VirtualBox:~/files/Assignment1/src$ java DamArrayApp "Driekoppies Dam"

Name: Driekoppies Dam, FSC: 250.92, Percentage: 43.7

202

 

rahul@rahul-VirtualBox:~/files/Assignment1/src$ java DamArrayApp "Pella Dam"

Name: Pella Dam, FSC: 2.111, Percentage: 38

21

 

rahul@rahul-VirtualBox:~/files/Assignment1/src$ java DamArrayApp "De Bos Dam"

Name: De Bos Dam, FSC: 5.735, Percentage: 71.3

103

 

and when running the DamArrayApp with 1 unknown Dam, the output was:

 

rahul@rahul-VirtualBox:~/files/Assignment1/src$ java DamArrayApp "Dam Doritos"

Dam not found

211

 

When running the DamBSTApp with no arguments, the first 10 lines output was:

 

Name: Ngotwane Dam, FSC: 19.033000000000001, Percentage: 4.6

Name: Hartbeespoort Dam, FSC: 186.44, Percentage: 96.5

Name: Bon Accord Dam, FSC: 4.381, Percentage: 103

Name: Albasini Dam, FSC: 28.199000000000002, Percentage: 69.2

Name: Blyderivierpoort Dam, FSC: 54.369, Percentage: 50

Name: Allemanskraal Dam, FSC: 174.52, Percentage: 13.5

Name: Albert Falls Dam, FSC: 288.14, Percentage: 36.4

Name: Bloemhof Dam, FSC: 1240.24, Percentage: 15.5

Name: Armenia Dam, FSC: 12.957000000000001, Percentage: 10

Name: Berg River Dam, FSC: 127.05, Percentage: 31.1

 

and the last 10 lines were:

 

Name: Waterdown Dam, FSC: 37.441000000000003, Percentage: 90.1

Name: Wemmershoek Dam, FSC: 58.71, Percentage: 52.3

Name: Westoe Dam, FSC: 60.094999999999999, Percentage: 48.3

Name: Wolwedans Dam, FSC: 24.626000000000001, Percentage: 95.4

Name: Witklip Dam, FSC: 12.519, Percentage: 39.299999999999997

Name: Xonxa Dam, FSC: 115.86, Percentage: 100

Name: Wriggleswade Dam, FSC: 91.471000000000004, Percentage: 98.7

Name: Woodstock Dam, FSC: 373.25, Percentage: 77.099999999999994

Name: Xilinxa Dam, FSC: 13.823, Percentage: 27.2

Name: Zaaihoek Dam, FSC: 184.63, Percentage: 58.5

 

 

When running the DamBSTApp with 3 known Dams, the output was:

 

rahul@rahul-VirtualBox:~/files/Assignment1/src$ java DamBSTApp "Umtata"

Name: Umtata, FSC: 244.67, Percentage: 100.4

22

 

rahul@rahul-VirtualBox:~/files/Assignment1/src$ java DamBSTApp "Voelvlei Dam"

Name: Voelvlei Dam, FSC: 158.58000000000001, Percentage: 22.2

18

 

rahul@rahul-VirtualBox:~/files/Assignment1/src$ java DamBSTApp "Zaaihoek Dam"

Name: Zaaihoek Dam, FSC: 184.63, Percentage: 58.5

14

 

When running the DamBSTApp with 1 unknown Dam, the output was:

 

rahul@rahul-VirtualBox:~/files/Assignment1/src$ java DamBSTApp "Specked eggs"

Dam not found

 

 

Results.

 

 

 

When running both the DamArrayApp and DamBSTApp, the best case was when there was only one count operation.

 

 

 

 

 

 The Column F shows the worse case for the DamArrayApp and the Column M shows the worse case for the DamBSTApp

 

The Worse case for the DamArrayApp is equal to the size of the dataset. This happens when the data searched is at the end of the array

 

The DamBSTApp on the other hand is very efficient at searching large datasets. The highest number of search operations was 13 compared to the 211 from the DamArrayApp

 

 

 The average case also shows that the BinarySearchTree is more efficient. The DamBSTApp is shown by column K and the DamArrayApp is shown as Column D.

 

 

Conclusions:

 

It is clear that the BinarySearchTree is a more efficient data structure when it comes to searching.

The structure of the BinarySearchTree allows for fewer comparisons when searching for an element. The array is a good data structure for small datasets. As the dataset increases the array becomes less efficient.