$1.$

To sort or not to sort? Design a reasonably efficient algorithm for solving each of the following problems and determine its efficiency class.

a$.$ You are given in telephone bills and m checks sent to pay the bills $($n $>=$ m$).$ Assuming that telephone numbers are written on the checks, find out who failed to pay. $($For simplicity, you may also assume that only one check is written for a particular bill and that it covers the bill in full.$)$

b$.$ You have a file of n student records indicating each student$$s number, name, home address, and date of birth. Find out the number of students from each of the $50$ U$.$S$.$ states.

$2.$

Solve the following system by Gaussian elimination:

X$\_1+$ x$\_2+$ x$\_3=2.2$x$\_1+$ x$\_2+$ x$\_3=3.$ X$\_1$ x$\_2+3.$ X$\_3=8.$

$3.$

a$.$ Give an example of a system of two linear equations in two unknowns that has a unique solution and solve it by Gaussian elimination.

b$.$ Give an example of a system of two linear equations in two unknowns that has no solution and apply Gaussian elimination to it$.$

c$.$ Give an example of a system of two linear equations in two unknowns that has infinitely many solutions and apply Gaussian elimination to it$.$

$4.$

For each of the following lists, construct an AVL tree by inserting their elements successively, starting with the empty tree.

a$.1,2,3,4,5,6$

b$.6,5,4,3,2,1$

c$.3,6,5,1,2,4$

$5.$

Construct a$2-3$treeforthelistC, O$,$ M$,$ P$,$ U$,$ T$,$ I, N$,$ G$.$ Use the alphabetical order of the letters and insert them successively starting with the empty tree.

$6.$

a$.$ Construct a heap for the list $1,8,6,5,3,7,4$ by the bottom$-$up algorithm.

b$.$ Construct a heap for the list $1,8,6,5,3,7,4$ by successive key insertions $($top$-$down algorithm$).$

c$.$ Is it always true that the bottom$-$up and top$-$down algorithms yield the same heap for the same input?

$7.$

Sort the following lists by heapsort by using the array representation of heaps.

a$.1,2,3,4,5($in increasing order$)$

b$.5,4,3,2,1($in increasing order$)$

c$.$ S$,$ O$,$ R$,$ T$,$ I, N$,$ G $($in alphabetical order$)$