1.

a. _ C G E K M H U V R Q P L

b. _ G K H P M L U V R Q

2. 

a.

Level Order of Tree:
Q E S D L A F P

Nodes whose link to its parent are red:
E A F P

b. 

Level Order of Tree:
L E Q D F P S A

Nodes whose link to its parent are red: 
A

3. 

a.

Case 1. No

Case 2. Yes

b.

Case 1. No 

Case 2. Yes

Case 3. No

4. 

a. pop, pop, pop, push, push

b. Mystery is a FIFO Queue: the remove function holds each object one at a time and continues popping until it reaches the bottom object in the stack, which is the value of y, and returns it. The bottom object of the stack is the first one in.

c. add: O(1), remove: O(N)

5. 

a. True (O(N))

b. False

c. False

d. True

e. True

f. False

g. True

h. True

6. 

a. ~(8 M + 40 N)

b. ~(16 L)

c. 16/42 

7. The algorithm has three steps. 

First step: iterate through the array, and for each element S of the array, sort the underlying character array of S using optimized merge sort. (i.e. convert it to a char[], sort the char[], then convert the char[] to a string again). Now, each string is in alphabetical order, so two strings are anagrams iff they are equal as strings. 

Second step: sort the whole array, again using optimized merge sort. This ensures that equal strings (which are in 1-1 correspondence with equivalent strings in the original array) are next to each other. 

Third step: iterate through the array and count how many distinct elements appear. (To be precise, count the number of values i such that a[i] != a[i-1], and add 1).

Each of the three steps has worst-case performance which is O(NM(log N + log M))
Sorting each string S as a char[] takes time O(M log M). Since we are using merge sort, the M log M time is an actual guarantee. The conversion between String and char[] is O(M), so it can be neglected. Since there are N strings, the first step takes O(NM(log M)).

The second step takes time O(MN(log N)) since merge sort has worst-case linearithmic performance and each compare may take O(M) when two strings are equal.

The final step iterates through the array and does compare operations which take time O(M) at each iteration, so it is O(NM)