Data Structures and Algorithms Coursework1

Individual work

Learning Outcomes#

Upon successful completion of this coursework, students will be able to understand:

Implement and modify fundamental data structures (Singly, Doubly, and Circular Linked Lists).
Apply different sorting algorithms (Insertion Sort, Quick Sort) to custom data structures.
Convert data between structural representations (List vs. Array).
Implement a hash table with collision resolution using quadratic probing.
Analyze the impact of load factor on hash table performance.
Perform Big O analysis on both linear and non-linear data structures.
Write test harnesses to validate and benchmark data structures.

Submission Requirements#

The assignment submitted should be compressed into a .zip file containing: the runnable jar file (if available) and all the program’s source files (.java).

filename format: student ID + CHC5223_CW1_Files.zip

Introduction#

This coursework focuses on the progressive development, sorting, comprehensive testing, and theoretical complexity analysis of data structures. You will implement various lists, sorting algorithms, and a dynamic hash table.

Assessment Rules#

Coursework 1 weighs 40% of the entire coursework assignment. 100% of the marks for Coursework 1 will be assessed through Class Test 1.

The test will contain questions directly related to the code you write, the algorithms you implement, and the analysis you conduct in this specification.
You must retain and understand all code and annotations created for this coursework to succeed in the test.
All of the questions in the class test include, but are not limited to, testing your ability to encode, understand and apply what you have learned.
Late or absent submissions of the source code will result in a score of zero.

Implementations#

Basic Rules#

You must make executable projects.

Do not use built-in collection libraries
(e.g., java.util.LinkedList, java.util.HashMap) for the core implementations.
Use basic arrays and your own classes.
All code must adhere to good programming practices (comments, meaningful naming).

Task 1: Singly Linked List#

Design and implement a Singly Linked List class that stores integer (int) data.

Node Structure: Create a Node class containing an integer field (data) and a pointer to the next node (next).
Core Functionality:
1. Insertion: Methods to insert a new node at the beginning and at the end of the list.
2. Deletion: Method to delete the first node containing a specific integer value.
3. Display: Method to traverse the list and print all integer values in order.
4. Search: Method to check if a specific integer value exists in the list (Linear Search).
5. Access: Method to get the data at a specific position(index).
Utility Methods:
6. Check if the list is empty.
7. Get the current size (length) of the list
Error Handling:
8. Handle cases such as deleting from an empty list or attempting to delete a non-existent value.

Task 2: Doubly Linked List#

Design and implement a Doubly Linked List class based on modifying the singly linked list code created in task 1.

Node Structure: Modify the node to include prev and next pointers.
Core Functionality:
1. Insertion: Methods to insert a new node at the beginning, at the end, and at a specific position (index).
2. Deletion: Method to delete the first node containing a specific integer value.
3. Traversal: Methods to traverse the list in both forward and backward directions.
4. Search: Method to check if a specific integer value exists in the list (Linear Search).
5. Access: Method to get the data at a specific position(index).
Utility Methods:
6. Check if the list is empty.
7. Get the current size (length) of the list.
Error Handling:
8. Handle invalid index positions during insertion.
9. Handle deletion attempts on empty lists or non-existent values.

Task 3: Circular Linked List#

Design and implement a Circular Doubly Linked List class. This implementation must be based on modifying the Doubly Linked List code created in Task 2.

Structural Modification: Last node’s next points to the first node; First node’s prev points to the last node.
Core Functionality:
1. Insertion: Methods to insert a new node at the beginning and at the end. Ensure the circular links are correctly maintained.
2. Deletion: Method to delete a node with a given value. Handle edge cases (e.g., deleting the only node).
3. Traversal: Method to traverse the list in the forward direction. The loop should stop when it returns to the starting node to avoid infinite loops.
Utility Methods:
4. Check if the list is empty.
5. Get the current size (length) of the list.

Task 4: Insertion Sort on Doubly Linked List#

Implement a sorting method insertionSort(), within the doubly Linked List class.

Sorting Functionality: Implement the Insertion Sort algorithm by manipulating next and prev pointers to rearrange the nodes (not just swapping data values).
Requirement: Sort the list in ascending order.

Task 5: Integrate Quick Sort on Doubly Linked List#

Implement a “wrapper” sorting function that converts the list to an array, sorts the array, and rebuilds the list.

Transformation to Array: Write a method listToArray() that traverses the Doubly Linked List and copies all integer values into a standard Array.
Quick Sort Algorithm: Implement the Quick Sort algorithm to sort the generated array, and implement a partitioning scheme based on a pivot strategy (middle element or random element).
Transformation Back to List: Write a method arrayToList(int[] arr) that takes the sorted array and rebuilds the Doubly Linked List from scratch, inserting elements in sorted order.
Integrated Wrapper Function: Write a method named hybridQuickSort(), which executes the above three steps in a correct sequence.

Task 6: Main Class and System Verification (Lists)#

Create a Main Class to test and verify the functionality of the three list structures using large-scale random data.

Data Generation:
1. Generate 1000 unique random integers (e.g., within the range of 1 to 10,000) using a random number generator.
2. Store this dataset in a temporary array to ensure consistency across tests.
List Population:
1. Instantiate three separate objects: one Singly Linked List, one Doubly Linked List, and one Circular Linked List.
2. Insert all 1000 unique integers into each of these three lists using their respective insertion methods.
Functionality Verification:
1. Integrity Testing: Write test logic to verify that each list type maintains its structural properties.
  - Singly: Verify the last node’s next is null.
  - Circular: Verify the last node’s next points to the head and the head’s prev points to the last node.
2. Sorting Verification:
  - Apply the sorting methods from Task 4 (Insertion Sort) and Task 5 (Hybrid Quick Sort) to the Doubly Linked List populated with the 1000 random integers.
  - Display a portion of the list (e.g., first 10 and last 10 elements) before and after sorting to verify the algorithm works correctly on large data.
Output: The program should produce clear console output showing the successful creation, population, and sorting of the lists.

Task 7: Hash Table with Quadratic Probing#

Create a Hash Table class that uses an integer array as the underlying storage and implements quadratic probing for collision resolution.

Initialization: The internal array must start with 1000 slots.
Default Load Factor: Set a default value (e.g., 0.75) if not specified by the user.
Set Load Factor Function:
1. Implement a public method: setLoadFactor(double loadFactor).
2. This function should allow the user to set the maximum load factor threshold.
3. The function must validate the input to ensure the load factor is between 0.0 and 1.0. If an invalid value is provided, the function should throw an exception or print an error message and retain the previous valid value.
Hash Function: Develop a custom hash function using the modulo operator (%) with the table size.
Collision Resolution: Implement Quadratic Probing ( $(H(key)+i^2)\bmod size$ ).
Core Operations:
1. Insert:
  - Insert an integer key.
  - Before insertion, check the current load factor.
  - If the current load factor exceeds the user-defined max load factor, trigger the resize operation (double the size and rehash), then insert the new key.
2. Search: Search for a key by following the quadratic probing sequence.
3. Delete: Remove a key. Implement “lazy deletion” (using a tombstone marker) to ensure the probing sequence for other elements remains intact.
4. Display: Print the contents of the hash table and statistics (current size, number of elements, load factor).
Dynamic Resizing:
1. Double the table size: Double the size of the underlying array when the load factor threshold is exceeded.
2. Rehash: Transfer all existing elements (excluding tombstones) from the old table to the new table using the new hash function (new size).

Task 8: Main Class Verification and Performance Comparison (Hash Table)#

Create a verification test within the Main Class to compare the performance of the Hash Table under different load factor settings.

Object Creation:
Create Hash Table Object A: Set the max load factor to 1.0 using the setLoadFactor() function.
Create Hash Table Object B: Set the max load factor to 0.75 using the setLoadFactor() function.
Data Preparation:
Create a data set of 1000 unique random integers.
Performance Benchmarking:
Measure the time taken to insert the last 250 integers of the dataset.
1. Insert the first 750 integers into both hash tables (this “warms up” the table and may trigger resizing, but we are not measuring this part).
2. Start a timer.
3. Insert the remaining 250 integers into Hash Table A.
4. Stop the timer and record the time for Table A.
5. Reset the timer.
6. Insert the same 250 integers into Hash Table B.
7. Stop the timer and record the time for Table B.
Output:
1. Display the time consumption for inserting the last 250 elements for both tables.
2. Display the final size of the underlying arrays for both tables (to show the impact of different load factors on memory/resizing).

Task 9: Big O Analysis for Linked Lists (Annotation)#

(Note: Annotation should be embedded in the implementation of Task 6, but is listed here for clarity as a distinct requirement)

Within the Main Class code (Task 6 section), create a dedicated block comment.
Perform a Big O analysis comparing the three linked lists (Singly, Doubly, Circular) for Access, Search, different Insertions, and Deletion.
Describe the applicable scenarios for different types of linked lists, and explain why each type of linked list is suitable for those scenarios by combining their key characteristics.

Task 10: Big O Analysis for Hash Table (Annotation)#

(Note: Annotation should be embedded in the implementation of Task 8, but is listed here for clarity as a distinct requirement)

Within the Task 8 code section, create a dedicated block comment.
Perform a Big O analysis for the Hash Table operations:
1. Best Case (Insert/Search/Delete)
2. Worst Case (Insert/Search/Delete)
3. Average Case
4. Resizing Impact: Analyze the time complexity of insertion when a resize (rehashing) occurs.
Explain how changing the max load factor affects the performance of the hash table.
1. What happens to search/insert speed if you set a very low load factor (e.g., 0.5)?
2. What happens to memory usage and collision frequency if you set a very high load factor (e.g., 0.95)?
Explain the trade-off between memory efficiency (higher load factor) and time efficiency (lower load factor).
Evaluate how well your quadratic probing handled collisions during the insertion of the 1000 elements.

Obtaining Help#

It is encouraged to request further clarification on what is required for this assignment. Please try to do this during normal contact time and avoid asking for such help in the last week before the deadline.

You can discuss the requirements and the material covered in the assignment with others, but what you create must be all your own work. Be careful to avoid collusion.

Feedback#

In addition to the written feedback of the class test that we aim to provide within the normal interval, you will be able to obtain fast, brief, verbal formative feedback and help on correcting your work in your practical classes.

音乐

音乐