Unit 4

Question 1

Determine the median of the values in this list:

[23, 42, 1, 17, 24, 38, 15, 19]

Answer 1

21

Question 2

What is quick select, and how does it differ from quick sort (in terms of approach and complexity)?

Answer 2

Quick select is a divide-and-conquer algorithm.

It uses the same overall approach as quick sort (choosing one item in a list as a pivot and partitioning the list into two based on that pivot, so that one partition has values that are less than the pivot and the other partition has values that are greater than or equal to the pivot).

However, instead of recursing into both partitions, as in quick sort, quick select only recurses into one partition – the one with the item that is being searched for. This reduces the average complexity from O(n log n) (in quick sort) to O(n) (in quick select).

Question 3

Given an alphabet {A, C, G, T} and a target string {GACCTGCT}, calculate a shift table.

Answer 3

A = 7

C = 2

G = 3

T = 1

Question 4

Given a string of {ABCCAB}, calculate its prefix table.

Answer 4

[0, 0, 0, 0, 1, 2]

Question 5

How is data in a hash table stored?

Answer 5

Data in a hash table is stored in a number of slots.

Question 6

What is mid-square an example of?

Answer 6

Mid-square is an example of a hash function.

Question 7

Draw a tree showing the correct outcome when the numbers [22, 13, 10, 34, 12, 50] are inserted into an empty binary search tree in the given order.

Answer 7

Question 8

Draw the updated AVL tree after the node with a key of 1 is deleted.

Answer 8

Question 9

Complete the following table, regarding the attached trees:

Answer 9

Question 10

Assuming a hash table with 23 slots, using the folding method, with 2 as the size of each part, what would be the hash value of the item 1459862903?

Answer 10

7

1. Split the item 1459862903 into groups of two (14 59 86 29 03)
2. Add these groups together, to give 191
3. Divide this number by the number of slots - 191 / 23 = 8, with a remainder of 7
4. The remainder is the hash value