# 2159

Aim: This assignment is designed to evaluate/improve your critical thinking and problem solving

skills. It also evaluate/improve your coding skill.

1. For a tree T, let nI denote the number of its internal nodes, and let nE denote the number of its

external nodes. Show that if every internal node in T has exactly 3 children, then nE = 2nI + 1.

[2 marks]

2. Insert entries with keys, 2, 7, 3, 12, 5, 20, 14, 6, 11, 8, 15, 17, 1, 19, 23, 14 (in this order), into

an empty:

(a) heap. [1 mark]

(b) binary search tree. [1 mark]

(c) AVL tree. [1 mark]

(d) (2, 4) tree. [1 mark]

[4 marks]

3. Although merge sort runs in ????(n lg n) worst-case time and insertion sort runs in ????(n2

) worst

case time, the constant factors in insertion sort make it faster for small n. Thus, it makes sense

to use insertion sort within merge sort when sub problems become sufficiently small.

Consider a modification to merge sort in which n/k sub lists of length k are sorted using

insertion sort and then merged using the standard merging mechanism, where k is a value to

be determined.

i) Show that the n/k sub lists, each of length k, can be sorted by insertion sort in ????(nk)

worst-case time. [1 mark]

ii) Show that the sub lists can be merged in ????(n lg(n/k)) worst-case time. [2 marks]

iii) Given that the modified algorithm runs in ????(nk + n lg(n/k)) worst-case time, what is the

largest asymptotic (????-notation) value of k as a function of n for which the modified

algorithm has the same asymptotic running time as standard merge sort. [2 marks]

Attachments:

assessment-3.pdf