Double Hashing Map: Implement Map interface by using an open addressing hash
table. Collisons are resolved by double hashing.
2. Recursive Hashing Set: Implement Set interface by using a chaining hash table.
The reference of the value s stored n the table f there s no collison. Collisons are
resolved by inserting the values (mapped to the same table entry) into another hash
table of same type. So, the structure s recursive.
3. MergeSort with DoubleLinkedList : Implement merge sort with double linked list.
Analyze the runining time of your method.
4. Average Run Time Analysis: Collect data about the average running-time of each
Algorithm discussed n class. Create arrays of random integers and then measure the
time t takes to sort for each algorithm. Repeat this process, for at least 10 different
size of arrays and at least 10 times for each array size. Report the average runtime
(draw graphs) for each algorithm. (Hnt: System.nanoTime() gives you a
nanosecond-precise time)
5. Worst-case Performance Analysis: In order to compare worst-case performance of
sort algorithms (discussed n class) perform the following experiment: For each
algorithm generate input arrays giving worst-case performance. Generate arrays of at
least 4 different szes:100, 1000, 5000, 10000. Report the performance analysis and
show that graphics.
*each algorithm: 5 sorting algorithms
Queston1:MergeSort wth dll
Four algorithms n books codes: Insertion Sort, Merge Sort, Quick Sort, HeapSort.
Q4 average run time analysis and Q5 worst-case performance analyiss steps must be
applied to all algorithms ( 5 sorting algorithm)
---------------------------------------------------------------------------------------------------------------------------
Note:
● Obey OOP principles
● Use ntellJ IDE on the given VM. VM download lnk can be found on moodle(n HW1)
● Your submission s studentnumber.zp and include following files:
● intellJ project file
○ Q1 folder
○ Q2 folder
○ Q3 folder
○ Q4 folder
○ Q5 folder
● o Report.pdf
● o Javadoc
● The report must be n format “ReportFormat_hw5.doc”
