首页 > > 详细

讲解CPS 400、辅导Data Structures、讲解Java程序语言、辅导Java 讲解R语言编程|辅导R语言编程

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

联系我们 - QQ: 99515681 微信:codinghelp
程序辅导网!