Description

Assignment 2
Deadline: Sunday 13/04/2025 @ 23:59
[Total Mark for this Assignment is 8]
Student Details:
Name: ###

ID: ###

CRN: ###
Instructions:

• You must submit two separate copies (one Word file and one PDF file) using the Assignment Template on
Blackboard via the allocated folder. These files must not be in compressed format.

• It is your responsibility to check and make sure that you have uploaded both the correct files.
• Zero mark will be given if you try to bypass the SafeAssign (e.g. misspell words, remove spaces between
words, hide characters, use different character sets, convert text into image or languages other than English
or any kind of manipulation).

• Email submission will not be accepted.
• You are advised to make your work clear and well-presented. This includes filling your information on the cover
page.

• You must use this template, failing which will result in zero mark.
• You MUST show all your work, and text must not be converted into an image, unless specified otherwise by
the question.

• Late submission will result in ZERO mark.
• The work should be your own, copying from students or other resources will result in ZERO mark.
• Use Times New Roman font for all your answers.

Restricted – ‫مقيد‬

Question One

Pg. 01
Learning
Outcome(s):
CLO4:
Demonstrate
implemented
solution with
appropriate data
structure and
algorithm for the
assigned
problem.

Question One

2 Marks

What is the main property of a binary search tree, and how does this property
affect the way data is organized and searched within the tree?
A binary search tree is a hierarchical structure that follows a specific ordering
principle. Each node in the tree has a value, and all elements in its left subtree are
smaller than the node’s value, while all elements in its right subtree are greater than the
node’s value. This organization ensures that data remains sorted, allowing for efficient
searching, insertion, and deletion (Lorenzen et al., 2023).
The properties of a binary search tree directly impact the way data is managed and
retrieved. Searching for a specific value is highly efficient because the tree can be
traversed in a logarithmic manner. The process begins at the root and moves left or
right based on whether the target value is smaller or larger than the current node. This
approach eliminates the need for scanning all elements, which would be necessary in
an unsorted list or array. Additionally, the structure of the binary search tree allows for
efficient range queries and ordered data retrieval using an in-order traversal, which
visits nodes in ascending order. However, the efficiency of these operations depends
on whether the tree remains balanced. An unbalanced binary search tree can slow
down operations, making balancing techniques such as self-adjusting trees necessary to
maintain optimal performance (Xu, 2022).

Restricted – ‫مقيد‬

Question Two

Pg. 02
Learning
Outcome(s):
Describe basic
and advanced
data structures
such as linked
lists, stacks, and
queues

Question Two

2 Marks

Why is rehashing necessary in a hash table, and what are the key steps
involved in the rehashing process?
Rehashing becomes necessary when the hash table reaches a high load factor, meaning
that a significant portion of its slots are occupied, leading to increased collisions and
degraded performance. As the number of elements grows, the probability of multiple
keys mapping to the same index rises, causing longer probe sequences and slower
operations. To maintain optimal efficiency, rehashing expands the hash table size and
redistributes existing elements using a new hash function (Heller, 2022).
The rehashing process involves several key steps. First, the load factor is monitored,
and when it exceeds a predefined threshold, a new, larger hash table is allocated.
Typically, the new size is chosen as a prime number to minimize clustering and
improve distribution. Next, all elements from the old table are reinserted into the new
table using a recalculated hash function, ensuring that each key is mapped to an
appropriate index. Since the table size has changed, the hash values of existing
elements are recomputed, preventing previous collisions from persisting. This
restructuring enhances lookup speed and reduces the likelihood of performance
degradation. Rehashing is an essential technique for maintaining efficiency in dynamic
hash tables, ensuring that operations remain fast and scalable as data volume increases
(Department of Computer Science, n.d.).

Restricted – ‫مقيد‬

Question Three

Pg. 03
Learning
Outcome(s):

Question Three

2 Marks

Compare the two sorting algorithms for sorting the list in the previous
question in terms of the following:
CLO2: Outline the
differences
between different
data structures as
well as searching
and sorting
algorithms

1. Which algorithm required fewer operations?
Merge sort generally requires fewer operations than insertion sort when dealing with
large datasets. This is because merge sort follows a divide-and-conquer approach,
breaking the list into smaller parts, sorting them, and then merging the results
efficiently. The time complexity for merge sort is O(n log n) in all cases, meaning it
scales well for larger inputs. In contrast, insertion sort checks each element one by one
and places it in its correct position by shifting existing elements. This results in an
O(n²) time complexity in the worst case, meaning that as the number of elements
grows, the number of comparisons and shifts increases significantly (Pal Singh Bedi &
Kaur, 2022).
2. How would the performance change if the list were already sorted
(e.g., [A, E, E, L, M, P, X])?
If the list is already sorted, insertion sort performs significantly better because it only
needs to check that each element is in its proper position. Since no shifting is required,
insertion sort completes in O(n) time, making it very efficient in this scenario. On the
other hand, merge sort does not take advantage of an already sorted list. It still divides
and merges the list, maintaining its standard O(n log n) time complexity. This means
that for small or mostly sorted datasets, insertion sort is far superior in terms of
efficiency (Khaznah et al., 2022).

Restricted – ‫مقيد‬

Question Four

Pg. 04
Learning
Outcome(s):
Demonstrate
implemented
solution with
appropriate data
structure and
algorithm for the
assigned problem

Question Four

2 Marks

Sort the list [ E, X, A, M, P, L, E ] in alphabetical order using both Insertion
sort and Merge sort. Show all your steps.
Insertion Sort
Insertion Sort works by picking elements one by one and inserting them into their
correct position among the already sorted elements.
Initial List: [E, X, A, M, P, L, E]
Step-by-step execution:
1. Consider the second element X. It is already larger than E, so the list remains
unchanged: [E, X, A, M, P, L, E]
2. Consider the third element A. Move it left past X and E: [A, E, X, M, P, L, E]
3. Consider M. Move it left past X: [A, E, M, X, P, L, E]
4. Consider P. Move it left past X but keep it after M: [A, E, M, P, X, L, E]
5. Consider L. Move it left past X, P, and M: [A, E, L, M, P, X, E]
6. Consider the last E. Move it left past X, P, and M: [A, E, E, L, M, P, X]
Final Sorted List (Insertion Sort): [A, E, E, L, M, P, X]
Merge Sort
Merge Sort follows a divide-and-conquer approach where the list is split into smaller
parts, sorted individually, and then merged back together.
Step-by-step execution:
1. Split the list into two halves:

Restricted – ‫مقيد‬

Question Four

Pg. 05
o

Left: [E, X, A]

o

Right: [M, P, L, E]

2. Recursively split until each part contains one element:
o

Left half splits into [E] and [X, A]

o

[X, A] splits into [X] and [A]

o

Right half splits into [M, P] and [L, E]

o

[M, P] splits into [M] and [P]

o

[L, E] splits into [L] and [E]

3. Merge sorted parts:
o

[X] and [A] merge into [A, X]

o

[E] and [A, X] merge into [A, E, X]

o

[M] and [P] merge into [M, P]

o

[L] and [E] merge into [E, L]

o

[M, P] and [E, L] merge into [E, L, M, P]

o

Finally, [A, E, X] and [E, L, M, P] merge into [A, E, E, L, M, P, X]

Final Sorted List (Merge Sort): [A, E, E, L, M, P, X]

Restricted – ‫مقيد‬

Question Four

Pg. 06
References

Department of Computer Science. (n.d.). Hash tables: Rehashing. In University of
Vermont, University of Vermont. University of Vermont.

Heller, S. (2022). Challenges and opportunities in developing a hash table optimized
for persistent memory. In Storage Developers Conference.

Khaznah, A., Wala, A., Sahar, A., Fatimah, A., Narjis, A., & Azza, A. (2022). Analysis
and comparison of sorting algorithms (Insertion, Merge, and HEAP) using Java.
koreascience.kr.
Lorenzen, A., Leijen, D., Swierstra, W., & Lindley, S. (2023). The functional essence
of imperative binary search trees. In Microsoft Research, Microsoft Technical
Report.
Pal Singh Bedi, H., & Kaur, A. (2022). Comparative Study of Different Sorting
Algorithms used in Data Structures. INTERNATIONAL JOURNAL OF
RESEARCH CULTURE SOCIETY, 6(3), 114–117.

Xu, Z. (2022). Breadth-First Search Multi-Dimensional Binary Search Tree based
Algorithms for Structural. Science Gate.

Restricted – ‫مقيد‬

Purchase answer to see full
attachment