A.1

1), 2)

f2 w: n (C), b: n (C)
f3 w: n (C), b: n (C) 
f4 w: lg n (B), b: lg n (B)
f1 w: n^2 (E), b: n^2 (E) 
f5 w: n (C), b: n (C)

A.2

3) complete

4) min priority queue

5) 4 9 8 100 12 14 13

6) 4 9 8 10 12 14 13 100

7) 8 9 13 10 12 14 100


A.3

8) 12 3 1 \ 2 \\ 11 7 5 4 \\ 6 \\ 9 8 \\ 10 \\ \ 13 \ 14 \ 15 \\

9) 2 1 4 6 5 8 10 9 7 11 3 15 14 13 12

10) 12 3 1 \ 2 \\ 11 7 5 4 \\ 6 \\ 9 \ 10 \\ \ 13 \ 14 \ 15 \\

11) 1 \ 12 3 2 \\ 11 7 5 4 \\ 6 \\ 9 8 \\ 10 \\ \ 13 \ 14 \ 15 \\


A.4

12)  A C B I G F E H D

13) A B G D F H I E C 

14) A B C D E G I F H 

Part B:

B.1.

15) yes

16) no

17) yes

18) yes

19) no

20) no


B.2.

use: 
"read" for "read and print"
"insert" for "read and insert"
"remove" for "remove and print"

21) yes:

X Y U V W ---> X U W V Y

print(X) insert(Y) print(U) insert(V) print(W)  remove(V) remove(Y)

22)

no:

X Y U V W ---/---> Y U W X V

insert(X) print(Y) print(U) insert(V) print(W) print(X) print(V)

However print(X) can only be printed after V.

B.3.

23)

double evaluate(const vector<double> &p, double x) {
   double sum = 0.0;

   for (int i = 0; i <= p.size(); i++) {
      double term = p[i];
      
      for (int j = 0; j < i; j++) {
         term *= x;
      }

      sum += term;
   }
   return sum;
}


24)

double evaluate(const vector<double> &p, double x) {
   double sum = 0.0;
   double xi = 1.0;  // Initialized to x^0

   for (int i = 0; i <= p.size(); i++) {
      
      sum += p[i] * xi;

      xi *= x;
   }
   return sum;
}