$(1)(5$ marks$)$ Given two arrays A$[0..$n $1]$ and B$[0..$n $1]$ of numbers. Find their

intersection set, i$.$e$.,$ the set that contains those numbers that are both in A and B$.$ A

brute$-$force algorithm would be easy: for each number in A$,$ check to see whether it is

in B$.$

$($a$)$ Analyze the time complexity of the brute$-$force algorithm for solving the problem.

$($b$)$ Design a presorting$-$based algorithm for solving the problem and analyze its

complexity.

$(2)(5$ marks$)$ You are given a dictionary, in which each word can have a maximum of $10$

letters. $($This assumption is unrealistic.$)$ Design a presorting$-$based algorithm to find

all sets of anagrams. For example, eat, ate and tea belong to the same anagram set.

Analyze the complexity of your algorithm.

$(4)(4$ marks$)$ For the following list of numbers, construct an AVL tree by inserting them,

one by one successively, into an empty tree: $4,7,9,2,3,5,6,8$

$(5)(5$ marks$)$ Deletion is another operation that could cause an AVL tree to be

unbalanced. Suppose that you are given a pointer pointing to the node to be deleted.

Discuss what you should do in order to make sure that, after deleting the node, the

tree is still AVL.

$(6)(6$ marks$)$ Apply Prim$$s algorithm and Kruskal$$s algorithm, respectively, to the

following graph to find its MST$.$ Show details.

$(7)(5$ marks$)$ Apply Dijkstra$$s algorithm to the above graph to find the shortest paths

from vertex a to all other vertices. Show details. $(6)(6$ marks$)$ Apply Prim's algorithm and Kruskal's algorithm, respectively, to the following graph to find its MST$.$ Show details.