Data Structures and Algorithms: Evaluation of ADTs Performance

This assignment focuses on evaluating the performance of different Abstract Data Types (ADTs), specifically Binary Search Trees (BST), AVL trees, and Hashing. The task involves implementing these ADTs using a chosen programming language and testing their performance with varying dataset sizes (1,000, 10,000, 50,000, 100,000, and 1,000,000 data points). The evaluation includes measuring the time complexity of creating/building, inserting, deleting, searching for a kth item, and traversing the data within each ADT. The submission requires a detailed description of the algorithms used, the methodology for measuring time, and an analysis of the results, with a focus on comparing the performance of the different ADTs based on the defined operations. The assignment aims to provide practical experience in understanding the efficiency of different data structures and their suitability for various tasks.

SSK5117: Advanced Data Structures Semester I 2016/2017
SSK5117 (1) SEMESTER I 2016/2017
ASSIGNMENT 2
Credit: As part of the 45% of total course mark
Deadline: 11 Nov 2016 11:59PM
Introduction: The objective of this assignment is to compare the performance of
different data structures and algorithm.
This is an individual assignment. You are encouraged to use relevant
references and resources to complete the task. HOWEVER, you should
cite the references or resources.
Submission: All submissions will be through the PutraBlast portal.
No submission will be accepted after the deadline.
Marking
Criteria:
To be provided
Tasks
Description:
In order to evaluate different ADTs, an evaluation with large data must
be conducted. Each ADT should be implemented by using a
programming language of your choice. Then, choose a dataset consists
of 1,000, 10,000, 50,000, 100,000 and 1,000,000 data for evaluation,
either from the given dataset. Observation includes the complexity:
a. in creating/building and destroying ADTs for the data
b. to perform insertion, deletion and search kth item.
c. to perform traversal of all data in the list.
Eventually, you need to conduct simple experiments to compare the
performance of the different ADTs based on the different operations
described above.
ADTs to be evaluated are:
1. BST
2. AVL
3. Hashing
Submission
Details:
The submission should include:
1. Brief introduction of the task
2. Methodology
a. Describe the algorithms of list of operations on the
ADTs for this experiment. You must clearly state the
steps taken. You can also include the codes as
attachment. Also the step to measure the time taken.
3. List of the results (Example)

SSK5117: Advanced Data Structures Semester I 2016/2017
1000 10000 100000 1000000
0
2
4
6
8
10
12
14
Array
Linked List
4. Analysis (please emphasize on this)
5. Conclusion