See if you can trace the execution of the following algorithms:

(a) Trace the fast divide and conquer integer multiplication method discussed in class (and in Brassard and Bratley) on the following example: 2221 is multiplied by 1211.

(b) Trace quick sort (the version discussed in class and in the textbook) on the list 9, 1, 6, 7, 4, 2, 3. Show what the array looks like after every swap (i.e. when two values are exchanged). Also, calculate the exact number of swaps the algorithm makes; when one element is exchanged with itself, that should not count as a swap.

(c) Trace the execution of Huffmans algorithm for the following set of frequencies: a : 3, b : 8, c : 7, d : 13, e : 6. Show what the tree will look like at the end (You can do this by hand or paper and pencil. Also show what will be the encoding for cbadbe with this code.

(d) Consider the Zvi-Lempel ZIP compression algorithm applied to the text: thedogisabigdog Show what will be the representation for the repeated codes (you just have to show the final representation where the compressed representation is being used, you dont have to show the normal representation part, you dont have to show the trace or intermediate steps). you can assume:

we are following exactly the same protocol described in class and in the handout.

the repeating representation is used only if the length is at least 3.

the 8-bit for pointers and 4-bit for length option is used here.

we are using the decimal notation

you dont have to calculate the number of bits