$(1)$ 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)$ 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.

$(3)$ 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$

$(4)$ 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.