Module Title: Data Structures and Algorithms

Module Code: COS5021-B

Module Credit: 20

Level: L5

Academic Year: 2024/25

Date due: Check on the Canvas.

Length limit: There is no limit whereas each question should be explained for each steps performed.

Learning Outcomes:

This assessment will evaluate follow learning outcomes of the module:

LO1: Recognise common data structures and fundamental algorithms and be familiar with the associated terminology.

LO2: Define Abstract Data Types in terms of their data structures.

Assessment Methods:

Resit- Coursework - This consists of six (06) questions including their sub-parts. You need to answer all the questions according to the question asked. Note: Understanding the questions is part of the assessment and no AI tools would be used for this assessment.

Please take note of the following regulations/advice where appropriate:

• Check the assignment marking criteria when doing your assessment.

• Go through your lecture/lab materials on the canvas for more understanding.

Guidelines:

Each student is given a (different) list of numbers to be used, in sequence, as keys for entries into a heap, into a hash table and into an AVL tree.

Your assignment is to show the trace of the operations of insertion, re-structuring, etc.

involved for your list of keys when they are entered into a heap, a hash table and an AVL tree.

Form. of Submission

Your submission should be.

 in a plain text file

 uploaded in Canvas module assessment section.

 The content of your submitted file should be as follows.

1. Have your UoB in the first line, e.g.

DSA Coursework 16012345

2. The word 'data' and your assigned list of keys, e.g.

keys 25, 10, 15, ...

Find your keys against your name and UB number in Data file.

I recommend that you copy and paste the whole line on to your submission document. When you paste the line, it will be quite noticeable if it shows someone else's UB number. You can then safely delete your UB number from the copy, knowing you have the right data.

1. Binary Heap

The task here is to show a trace of the operations needed to insert objects with your (list of) keys, one by one, into an initially empty miniHeap with restoration of heap order (if necessary) with each insertion.

Your submission should have the section heading 'Heap trace' followed by the coded trace of operations:

 Hx to create a hole at location x in the heap;

 X to move the hole up the heap by swapping the hole with its parent;

 Ixx to insert key xx into the hole;

with the coded operations in sequence on successive lines, e.g.

Heap trace

H1

I25

H2

X

I10

H3

I15

...

2. Heap Build

For this part, your keys are loaded into the heap without application of heap order. Show a trace of the operations in the heapBuild process, to apply heap order to the (loaded) heap.

Your submission should have the section heading 'Heap Build trace' followed by the coded trace of operations:

 Xxx to swap the object having key xx with its parent;

with the coded operations in sequence on successive lines, e.g.

Heap Build trace

X15

...

3. Heap Sort

This part is for heap maintenance during the output phase of heap sort, i.e. you begin with the heap resulting from the previous section (2. Heap Build). Show a trace of the operations to output each object (from the root) and then to restore heap order after each output.

Your submission should have the section heading 'Heap Sort trace' followed by the coded trace of operations:

 Mxx to remove the object with key xx from the root (and so create a hole at the root);

 L to move the hole down the heap by swapping the hole with its left child;

 R to move the hole down the heap by swapping the hole with its right child;

 Xxx to move object having key xx into the hole (and delete the node that previously contained key xx);

with the coded operations in sequence on successive lines, e.g.

Heap trace

M10

L

L

X57

M12

R

X39

M15

L

L

X84

...

4. AVL Tree

The task here is to show a trace of the operations needed to insert objects with your (list of) keys, one by one, into an initially empty AVL tree with restoration of AVL balance (if necessary) after each insertion.

Your submission should have the section heading 'AVL trace' followed by the coded trace of operations:

 Ixx to insert key xx at the root of the previously empty AVL tree;

 IxxLyy to insert key xx as the left child of the node containing key yy;

 IxxRyy to insert key xx as the right child of the node containing key yy;

 Rxx to rotate the node containing key xx with that of its parent (in order to restore AVL balance);

with the coded operations in sequence on successive lines, e.g.

AVL trace

I25

I10L25

I15R10

R15

R15

...

5. Hash Table (1)

The task here is to show a trace of the operations needed to insert objects with your (list of)

keys, one by one, into an initially empty 11-bucket hash table with

0 1 2 3 4 5 6 7 8 9 10

11 12 13 14 15 16 17 18 19 20 21

22 23 24 25 26 27 28 29 30 31 32

33 34 35 36 37 38 39 40 41 42 43

44 45 46 47 48 49 50 51 52 53 54

55 56 57 58 59 60 61 62 63 64 65

66 67 68 69 70 71 72 73 74 75 76

77 78 79 80 81 82 83 84 85 86 87

88 89 90 91 92 93 94 95 96 97 98

99

1 2 3 1 2 3 1 2 3

10 11 12 13 14 15 16 17

18 19 20 21 22 23 24 25 26

27 28 29 30 31 32 33 34 35

36 37 38 39 40 41 42 43 44

45 46 47 48 49 50 51 52 53

54 55 56 57 58 59 60 61 62

63 64 65 66 67 68 69 70 71

72 73 74 75 76 77 78 79 80

81 82 83 84 85 86 87 88 89

90 91 92 93 94 95 96 97 98

99

 (primary) hash function h1(x) = x mod 11 (see table at the end of this page)

 and using linear probing for collision resolution.

Your submission should have the section heading 'Hash Table trace 1' followed by the coded trace of operations:

 Pn to probe bucket n (to see if it already contains an entry);

 Ixx@n to insert key xx into bucket n;

with the coded operations in sequence on successive lines, e.g.

Hash Table trace

P3

I25@3

P10

I10@10

P3

P4

I14@4

...

6. Hash Table (2)

The task here is the same as for the previous section (5. Hash Table (1)) except that collision resolution is to use the secondary hash function h2(x) = (x mod 3) + 1 (see table at the end of this page).

Your submission should have the section heading 'Hash Table trace 2' followed by the coded trace of operations (same coding as for previous section).

Hash Functions

The body of each table contains key values. The value of the hash function for a key is shown (in bold) at the head of the column in which the key appears.

primary hash function secondary hash function

Coursework Marking Criteria

Since every student gets a different data set, it is not possible to give a sample solution to the coursework. There is a single marking criterion: correctness of the solution. However partial credit will be awarded to solutions based on what mistakes are made. It is very important that for each step of the questions in the entire coursework should be backup with its explanation.

For instance, if you insert/delete a key in the tree, you should clearly explain why you have inserted/deleted the key in the respected location. May be due to a current key is less than or greater than the previous key etc. Keep in your mind a mistake at the early stage could end with wrong tree or answers and you will be deducted the marks. Double-check your current step while proceeding with the further steps.

The components of the coursework are weighted as follows:

 Binary Heap: 20%

 Heap Build: 15%

 Heap Sort: 15%

 AVL Tree: 20%

 Hash Table (1): 15%

 Hash Table (2): 15%