Assignment Location: The assignment 2 is uploaded under Assessments section

(Assessment 3 – Final Assessment) on unit Moodle page.

Answer Format. When you write an answer, clearly indicate the relevant question number/letter. Include your name and student ID at the start. Also add appropriate comments to code files to indicate author name and student ID. Please refer to detailed submission guidelines in section 2.

Timeframe. You have 4 days (96 hours) to complete and submit your answers, from 10:00am on 05th June 2023 until 10:00am on 09th June 2023 (UTC+8). You mayschedule your work within this period. However, late submissions are not allowed.

Submission Location. Submit your answer document(s) to the “Assessment 3 – Final Assessment” area on Moodle under assessments section. You must verify that your submission was successful. Correctly submitting is entirely your responsibility.

Reference Material. This is an OPEN BOOK and OPEN COMPUTER assignment. You may refer to any written material, including your notes, course materials, books, websites, Unit Moodle page recordings etc. However:

•   You must complete this assignment entirely on your own. You should answer all questions in your own words and code.

•   You can use pseudo code and algorithms provide in the unit slides (Moodle page) for your implementation.

•    During the assignment, you may not communicate with any other student regarding the test.

•    During the assignment, you may not communicate with any other person in order to seek or receive an answer to any test question.

•   Your answer document will be checked by text matching software for signs of cheating,collusion and/or plagiarism.

•    The assignment questions have been designed such that any two students, working independently,should not produce the same answers.

•    The coding part of this assignment can be submitted in either python or java.

• All parts taken from your own previous submissions (practical/assignment) should also need to be referenced as per college recommended citation style .

1. Overall Assignment Description

In this assessment you will apply a detailed knowledge of data structures and algorithms to   real-life applications to show your understanding of the details covered in the unit. Detailed  description on each question and steps required to be performed can be found in the question description.

Question 1: General Understanding (Total Marks: 10)

A.  You are working on a project that involves storing and managing a large data set of customer information for a retail company. The dataset consists of millions of records, and you need to  optimize the  data  structure for efficient  searching,  insertion, and deletion operations. Additionally, you will often need to retrieve subsets of data based on various criteria.

i.      Describe the way you will store the data of an individual customer i.e., ADT (see the details of a car described above). (2 marks)

ii.      Compare  the  following  data  structures  and  select  the  best  suited  for  the application. [Hint: you can make a table for comparison] (4 marks)

a.   Hash Table

b.   2-3-4 tree

c.   B Tree (Block Tree)

d.   Graph

B.  Suggest the data structure (among we discussed) best suited to store the information such that following operations are supported (can be performed effectively/efficiently) for any given application (application).

a.   Adding new rooms (records) with a unique key

b.   Deleting old records

c.   Searching a key

i.      Which data structure you will use if want to make the adding, deleting time complexity   independent   of  the   data   size.   Support  your   selection  with appropriate comments on time complexities. (2 marks)

ii.      What is memory overhead (i.e., any extra memory used than the data size) of your selected data structure. (2 marks)

* If you are defining your ADT in terms of classes best to represent is UML class diagram(s).

Question 2: Recursion and Sorting (Total Marks: 16)

A.  You have been provided with 1 million numbers (integer type) approximately 60% of which are already sorted. You are supposed to suggest (among the listed below) the best sorting algorithm based on the data provided. Make clear comments considering stable/non-stable and in-place/not in-place properties and time complexity of each sort. (4 marks)

a.   Quick sort

b.   Counting sort

c.   Selection sort

d.   Radix Sort

B.  Consider the application of quick sort for a project that requires sorting a large dataset of student records based on their scores. The dataset contains millions of records, and you need to select an efficient sorting algorithm that can handle this large amount of data. Additionally, you want to consider the stability of the sorting algorithm, as it may be important to maintain the original order of records with the same score. (4 marks)

C.  Comment on the memory overhead of the counting sort for an application where you have to sort millions of record whit a large range of values. (3 marks)

D.  Convert the following iterative pseudo code (Fig. 1) to the recursive python code. Your code  must  include  wrapper  method  and  exception  handling. (5 marks) [clearly mention the base case in comments and provide basic test harness (simple main function in the same file)].

Fig. 1

Question 3: Stacks, Queue and Lists (Total Marks: 15)

A.  Implement a function using stack (python code) to check the equal number of terms of both sides of an expression. For example if the expression is A + B + C = X + Y + Z the function should return true and false if the number of terms are not equal on both sides. Where, A,B,C and X,Y,Z are terms in the expression. (5 marks) [You can use NumPy arrays or linked list for this implementation]

B.  Implement a queue (max size 100 elements) with the help of double ended single linked list used as document printing queue for a shared printer, try to insert  102 random printing  jobs,  however  the  queue   should  be   able  to  throw  appropriate  error messages/exceptions if no more jobs can be entertained or empty otherwise. (5 marks)

C.  Discuss in detail the selection of double ended double linked list compared to double ended single linked list, single ended single linked list and array for the implementation of queue (Part B). Discuss in detail that which data structure can be used for this implementation, effective on time complexity and memory utilisation Consider the Big O notation (asymptotic) time complexity and memory utilisation to justify your answer. (5 marks) [can be represented in tabular form]

Question 4: Trees (Total Marks: 16)

* All values given in the figures below should be used/read left to right.

A.  Considered the list/array shown in Fig. 2 and insert the elements in a Binary Search Tree, show the developed tree. Also, draw the Red Black tree on the reverse sorted data (after reverse sorting of the give data). Now compare the developed trees         describe what is the effect of sorted or partially sorted data on both trees. Which is  the best tree if compared on completeness and balance, support your answer with O notation complexity details (4 marks) [show steps for each element insertion]

Fig. 2

B.  Consider the elements presented in Fig. 3 and draw a 2-3-4 Tree form initially empty root. Show and describe each step. (3 marks)

Fig. 3

C.  Convert the tree drawn in part B to a B Tree (degree 2), also discuss that which tree is more efficient for inserting and searching elements. Consider the Big O notation (asymptotic) time complexity to support you answer. (4 marks)

D.  Consider the following elements (Fig 4) and provide an algorithm (Pseudo/python/java code) to read one value at a time and convert it into an array-based representation of a binary tree (Hint: the rules for parent, left and right child defined in heap can be used here). The array based binary tree representation should then be shown as a tree as well. (5 marks)

Fig. 4

Question 5: Graphs (Total Marks: 12)

*Consider the Fig. 5 for the following questions.

A.   Represent the following graph in Adjacency Matrix and Adjacency List (for each vertex) representation. (4 marks)

B.  If this graph is used to represent connectivity of people on a social network,          considering this application, describe that what data should be stored in vertices   (smallest entity personal unique ID e.g., twitter handle) and edges respectively. (2 marks)

C.  Described the graphical steps for the depth first search along with value stored in stack/queue. Consider vertex “5” as the starting point. (3 marks)

D.  Described the graphical steps for the breadth first search along with value stored in stack/queue. Consider vertex “8” as the starting point. (3 marks)

Question 6: Heaps (Total Marls: 13)

*Consider the number list presented in Fig. 6 for this question.

A.  Draw a min heap (tree-based) using the number list, show you working as graphical steps for each insert, representing the step by step building of the heap. (4 marks) [Hint: you can use text to represent the steps]

B.  Show an array-based representation of the number list as heap, satisfying the related arithmetic operations for traversing. (2 marks)

C.  Show the process for deleting/removing two values one after the other (78 and 13) in the tree built in part A. Show steps (including each step of the trickle-down) on the   array-based representation built in part B. (4 marks) [Hint: you can use text to          represent the steps]