CS 313 Spring 2020 Assignment 3
The following 3 coding problems are part of the assessment and in total are worth 5% of the
course grade (the other 20% of the assessment will come from the exam). The following files
related to these problems are provided:
To answer each of the questions you will need to complete some of the provided files. You
should not modify any files unless otherwise instructed by the problems, and you should not
utilize any additional classes that are not already directly imported in the provided files. You
may modify the package statements if it is convenient.
Your submission should be a compressed folder (preferably .zip) containing all of the above files
with the required modifications made. Late submissions will not be accepted; for this reason it
is suggested that you do not wait until the last minute to submit.
1. Complete ChainHashList (2 points total). As shown in lecture, ChainHashMap
implements the essential Map methods put, get, and remove in O(n/N) time, which we
consider to be O(1) if the load factor is managed correctly. Since these methods are
closely related to the List interface methods add, set, get, and remove, it appears that
we should be able to use ChainHashMap to implement these List methods in O(1) time.
As it turns out, we cannot actually achieve O(1) runtime for all of the List methods, but it
is worth exploring why that is the case. For this problem, complete the empty
ChainHashList class by implementing the List interface using a ChainHashMap
2. Complete SortedTableMap (2 points). The SortedTreeMap from the final lecture uses
an AVLTree to implement the SortedMap interface so that the essential methods run in
O(log n) time, which is relatively quite good. For this problem, complete the empty
SortedTableMap class by using an ArrayList to implement the SortedMap
interface. It will not be possible to implement all of the essential methods so that they
run in O(log n) time, but your implementation should be as runtime efficient as possible.
Specifically, the get method can be done in O(log n) time; some other methods can be
done in O(n), some can be done in O(1).
3. Complete HeapPriorityQueue (2 points). In lecture we implemented
HeapPriorityQueue using an array-based representation of a heap (a complete binary
tree whose entries satisfy the heap-order property). For this problem, complete the
included HeapPriorityQueue class by using the LinkedBinaryTree class to
heap. Hint: the most challenging part of this problem is identifying the last Position in
the heap and the next available Position in the heap. It is suggested that you review the
array-based heap to better understand how these positions can be located. You need
not concern yourself with the runtimes of your solutions. [Note that the names of these
classes are the same because they both utilize heaps, just heaps implemented
本网站支持淘宝 支付宝 微信支付 paypal等等交易。如果不放心可以用淘宝交易！
E-mail: [email protected] 微信:itcsdx