代做CPS 400、代写Data Structures、代做Java程序语言、代写Java

日期：2018-11-30 10:20

CPS 400 Data Structures and Algorithms

Programming Assignment 3

Fall 2018

This programming assignment will focus on two different ways to

implement the dictionary ADT. The first one uses binary search trees

and the second one uses hash tables. You will implement the basic

dictionary operations (i.e. insert, delete and find) and study the

performance of these operations via empirical means. By completing

this assignment, you will be able to describe, compare and contrast the

implementations of these operations by binary search trees versus hash

tables.

Submission guideline

Put all of your Java source files and your written report (in pdf format)

in a single directory. Then zip them together into a single zip

file. Follow the naming convention as in the project 2 to label your

submission. Upload your submission on or before 5pm, Nov 28, 2018.

No penalty if you upload your work on or before 5pm, Nov 29, 2018.

The blackboard link will stop accepting submissions (disappear) on

5pm, Nov 29, 2018 and you will receive a grade zero if you do not

upload your work by 5pm, Nov 29, 2018. In addition, you need to

submit a hardcopy of your report at the beginning of class (5 pm) on

11/29/2018. If you submit your hardcopy late, a 25% penalty on your

project grade will be imposed.

This programming assignment is an individual project. You cannot

collaborate with any other student(s). If you use any resource(s) that

are not provided by the instructor, it is your responsibility to state

them in your report. Failure to do will be considered as a violation of

academic integrity and will be reported.

Part 1. Binary search trees

1. Select either BTNode or IntBTNode class as the basis, implement

the dictionary operations insert, delete and find as member

functions. As explained in class, IntBTNode class is a simplified

version and is recommended.

2. Design test cases to verify each of these dictionary operations.

3. Conduct computational experiements to estimate the height of a

randomly built binary search trees. You will consider the following

two cases:

cps 400 data structures and algorithms 2

Case 1: the trees are built by inserting randomly selected elements

to an empty binary tree. No delete operations are performed.

Case 2: the trees are built by inserting randomly selected elements

to an empty binary tree, followed by a sequence of

dictionary operations which include both insert and delete.

Part 2. Chained Hash tables

1. Starting from the ChainedTable class as the basis, implement

the dictionary operations containsKey, get, put and remove as

member functions.

2. Design test cases to verify each of these dictionary operations.

3. Write a function maxChainLength, which is a member function for

the class ChainedTable). It will compute the length of the longest

chain in the chained hash table.

4. Conduct an computational experiement to create an empty chained

hash table T followed by inserting elements randomly to T. We

then compute the length of the longest chain of T and the experiment

will be repeated multiple times. We will use the average

value obtained to gain insights regarding the efficiency of the dictionary

operations.

5. Repeat the computational experiment stated previously mulitiple

times. Each time we will use a chained hash table of different size.

6. Repeat the computational experiment stated previously multiple

times. Each time we use the hash function h(x) = x(mod p) but the

table size p varies.

Report

You will need to submit a printed report (about 3-5 pages) regarding

your work in project 3. Your report should contains details that are

not covered in this description document.

Implementation: list of tasks

Part 1: Binary search trees

Task 1: Implement and test the height function

Implement the height function and design test cases to verify your

work. Give a concise summary in your report.

cps 400 data structures and algorithms 3

Task 2: Implement and test each of the dictionary operations

Implement the dictionary operations and design test cases to verify

your work. Give a concise summary in your report.

Task 3: An experiment to estimate the height of a randomly built

binary search trees (for Case 1)

Case 1 (use insert operations only)

1. Let A be the array of integers: A=[1,..,1000].

2. For i = 1, . . . , 100, use the function given in RandEx class, create

a permutation of the array A, say Pi

randomly. Each Pi contains

the numbers 1, . . . , 1000 but the ordering of these numbers are

different. For example, one of the Pi may be [1000, ..., 1].

3. For each Pi

(i = 1, . . . , 100), starting with an empty tree Ti

,

insert the numbers from Pi

to Ti

. Compute the height of the

resulting tree. Call it hi

.

4. After you have computed the values hi (i = 1, . . . , 100), compute

H, the average of hi

. That is,

H =

h1 + . . . + h100

100

5. Print the value of H to the screen.

Give a concise summary of this task in your report.

Task 4: An experiment to estimate the height of a randomly built

binary search trees (for Case 2)

1. Let A be the array of integers: A=[1,..,1000].

2. For i = 1, . . . , 100, use the function given in RandEx class, create

a permutation of the array A, say Pi

randomly. Each Pi contains

the numbers 1, . . . , 1000 but the ordering of these numbers are

different.

3. For each Pi

(i = 1, . . . , 100), starting with an empty tree Ti

,

insert the numbers from Pi

to Ti

.

4. Randomly select 100 elements from A and store them in an

array Di

. Delete each element in Di

from the tree Ti one by one.

5. After completing all of the delete operations, re-insert the elements

from Di

to the tree Ti at an random order.

6. After re-insertion are completed, Compute the height of the

tree. Call it ki

.

cps 400 data structures and algorithms 4

7. After you have computed the values ki (i = 1, . . . , 100), compute

K, the average of ki

. That is,

K =

k1 + . . . + k100

100

8. Print the value of K to the screen.

Give a concise summary of this task in your report.

Part 2: Chained hash tables

Unless otherwise stated, the size of the hash table in this project is set

to the prime number p = 47.

Task 1: Implement and test the four required member functions

Implement the four required functions and design test cases to

verify your work. Give a concise summary in your report.

Task 2: Implement and test the member function maxChainLength.

Implement the required function and design test cases to verify

your work. Give a concise summary in your report.

Task 3: Conduct an experiment to estimate the maximum of chain

length for hash tables

1. Let the table size be p = 47.

2. Let U be the collection of numbers ranging from 0 to the integer

Integer.MAX_VALUE-1.

3. Create an empty hash table H. Select 1000 distinct integers

randomly from U and call them t1, ..., t1000. Use the put function

to insert them to H. Use maxChainLength to compute the the

maximum length of the chains in H. Let the result be l1.

4. Repeat the previous step 49 times and obtain the values l2, . . . , l50,

as defined similarly. Compute the average value L:

L =

l1 + . . . + l50

50

5. Report the value L by printing it to the screen.

Give a concise summary of this task in your report.

Task 4: Conduct an experiment to examine the effect of changing

table size on the maximum change length of hash table

1. Repeat the experiment in Task 3 for the following table size: 48,

51 and 64.

cps 400 data structures and algorithms 5

2. Show the results to the screen.

Give a concise summary of this task in your report.

? Task 5: Conduct an experiment to examine the effect of using hash

function of the form h(x) ≡ x mod p the maximum change length

of hash table

1. Repeat the experiment in Task 3 for the following cases:

– table size: 47 and the hash function is h(x) ≡ x mod 47

– table size: 64 and the hash function is h(x) ≡ x mod 64

2. Show the results to the screen.

Give a concise summary of this task in your report