Answers to CS302 Midterm Exam #2 - April 14, 2026

James S. Plank

The exam featured a lot of "bank" questions -- this answer guide is for the example exam, but has information about the other banks when appropriate.

Questions 1 and 2 are "what is your username" and "if you have comments, put them here." So we start with question 3.

Questions 3-12

In the answer, I have the reference material for where you find the answer explained.

Key=Selection: O(n²) (Sorting lecture notes).
Key=Heap: O(n log n) (Sorting lecture notes).
Key=Merge: O(n log n) (Sorting lecture notes).
Key=Bucket: O(n) (Sorting lecture notes).
Key=DFS: O(E). We don't need the V, because the graph is connected, so the DFS will always visit every edge. (Graph Intro, graph representations, depth first search.)
Key=Dijkstra: O(E log V) (Breadth-First Search, Shortest Paths and Dijkstra's Algorithm). Again you don't need to add V, because the graph is connected, so E ≥ V.
Key=BFS: O(E) -- BFS. (Breadth-First Search, Shortest Paths and Dijkstra's Algorithm). Once again, you don't need to add V because the graph is connected.
Key=Adjacency-Lists: O(V2). When the average number of incident edges is V/2, then there are V*V/2 edges in the graph. That is O(V2).
Key=Inheritance: Inheritance. In an interface, the superclass only has method prototypes. In inheritance, the superclass can have member variables, like expenses. (Interfaces and Inheritance.)
Key= Maxflow: You just eyeball this one -- 38. There are 10 units of flow from SABC. 10 units from SACT. 18 units from SCT. (Network Flow).

Grading: Each question was worth 2.5 points. If you gave me extraneous things in a Big-O equation, like O(V+E) for the DFS question, or O(V+ElogV) to the Dijkstra question, then you lost some fractional points.

Questions 13-15

Key=Insertion: Reading the file is O(n) and doing insertion sort is O(n²). So, when I quadruple the size of the input, it will take 4 seconds to read the file, and 20*16 = 320 seconds to do the insertion sort. The answer is 324 seconds.
Key=Quicksort: Reading the file is O(n) and doing quicksort is O(n log n). So, when I quadruple the size of the input, it will take 4 seconds to read the file. The log, base two of 1,000,000 is 20 (roughly). So, let b equal 1,000,000. The time to do 20b operations is 20 seconds. Therefore the time to do 22*4b operations is 88. So the answer is 92 seconds. I accepted any answer between 85 and 110.
Key=DFS-Adjmatrix: Creating the adjacency matrix is O(n²), and doing the DFS is O(E). Regardless of our graph, the maximum size for E is O(n²), so the program is O(n²). Therefore, when we quadruple the input, we need to multiply the running time by 16. The answer is 64 seconds.

Grading: 3 points per question. On the Insertion question, I gave 2.8 if you were within a few seconds of 324. Otherwise, I gave a point if your time was over 100. If it was linear, the time would be 84, so any answer around that value. received no credit.

On the quicksort question, I gave three points to any answer between 85 and 110. If you gave an answer between 80 and 84, you received one point, and if you answered greater than 110, you got a point.

On the DFS question, you got full credit for 64 seconds. I gave 0.5 points for values less than 10; 1 point for values between 10 and 19; 1.5 points for values between 20 and 30. 2 points for 32, and 1.5 points for 256.

Question 16

Bubble Sort: All the questions were of the form:
D-GB-H-IFC-JEA
The D and H stayed where they were. G swaps with B. I swaps with F and C. J swaps with E and A. So you end with:
D-BG-H-FCI-EAJ
There were five banks. Here are the answers for the five banks:
I-KD-P-QHE-XMC | L-PE-U-VJG-XTB | P-SH-U-WLJ-YTE | N-SD-X-YJH-ZTB | N-RC-T-ULK-ZSA I-DK-P-HEQ-MCX | L-EP-U-JGV-TBX | P-HS-U-LJW-TEY | N-DS-X-JHY-TBZ | N-CR-T-LKU-SAZ
Selection sort: We swap M with the smallest element -- B. And then F with the next smallest element -- C. The answer is BCQLJFWMRI. Here are all of the banks, where I've broken out the two smallest characters so that you can see the answer:
MFQLJ-C-W-B-RI | ZXKMH-E-IN-A-W | IMFX-C-UZ-B-LW | FQY-B-TIN-A-XO | RNMVQX-I-YZ-K BCQLJ-F-W-M-RI | AEKMH-X-IN-Z-W | BCFX-M-UZ-I-LW | ABY-Q-TIN-F-XO | IKMVQX-R-YZ-N
Insertion sort: After four passes of the algorithm, the first five characters will be sorted, and the last five will be unchanged. Here are all of the banks:
WRKSI-JLMGC | WNLKQ-ICTVR | YVCGI-BXEMA | YAQHG-IJURP | XPFLW-DBHSQ IKRSW-JLMGC | KLNQW-ICTVR | CGIVY-BXEMA | AGHQY-IJURP | FLPWX-DBHSQ
The answer is IKRSWJLMGC.

Merge sort: Before the final merge, the first half of characters will be sorted, and the last half will be sorted. Here are the banks:

YMLCH-KVANF  |  ZVUEH-QXCWF  |  XRNGJ-LTASH  |  XRQDJ-NUCSI  |  ZPMBE-KVAQD
CHLMY-AFKNV  |  EHUVZ-CFQWX  |  GJNRX-AHLST  |  DJQRX-CINSU  |  BEMPZ-ADKQV

In each of the three pivot selections, you answer the middle of the three characters -- beginning, end, middle. When the string is ISHAVWGLQ, the three characters are I, V and Q, so the answer is Q.
Here are the answers for the three pivot selections for every string:
DAEMSHFIT S DCEMRGFLS R EDJSTMKQX T GEJSUMKPX U HGITUNMPW U HLGCPQEIJ J HTEAUWBPR R ISHAVWGLQ Q JBFQVNHME J KAHQTPJLB K LSICTVHNR R MAJXYVLQG M MRLFSVINP P NAETWRLQC N QGLVWUMSJ Q
For the example question (PPSFPHPTQB), Whenever we see the pivot, we swap it into the other set. So:
- Swap P in index 1 with B in index 9.
- Swap S in index 2 with P in index 6.
- Swap P in index 4 with H in index 5.
The answer is PBPFHPSTQP.
Here are the answers for the banks:
PPSFPHPTQB | HVDTZESFAU | IIRCIEIUQB | GXCRYEHFAS | IIREIHIUJA PBPFHPSTQP | HADFEZSTVU | IBICEIRUQI | GACFEYHRXS | IAIEHIRUJI
For the example question (QXIUYMRPAW), we don't ever see the pivot here, so it's easier:
- Swap X in index 1 with A in index 8.
- Swap U in index 3 with P in index 7.
- Swap Y in index 4 with M in index 5.
The answer is QAIPMYRUXW.
Here are the answers for the banks:
QXIUYMRPAW | LLPBLELRMA | LRENTGMHCP | KKNBKJKSMA | IYCMZDKGAT QAIPMYRUXW | LALBELPRML | LCEHGTMNRP | KAKBJKNSMK | IACGDZKMYT

Grading: All questions but the pivot questions were worth three points. The pivot questions were worth two points. There was partial credit given.

Question 17

I would simply start from A and go to L, identifying components on the way:

- A is clearly in its own component:      A
- B, F and I are in the same component:   A BFI
- C is in that component too:             A BCFI
- D and E are in the same component:      A BCFI DE
- E gives us no new information:          A BCFI DE
- F and J are in the same component:      A BCFIJ DE
- G and L are in the same component:      A BCFIJ DE GL
- H and K are in the same component:      A BCFIJ DE GL HK
- I gives us no new information:          A BCFIJ DE GL HK
- J gives us no new information:          A BCFIJ DE GL HK
- K gives us no new information:          A BCFIJ DE GL HK
- L gives us no new information:          A BCFIJ DE GL HK

So the answer is 5.

In your grading file, your answer was keyed off othe adjacency list for B. Here are the answers for the various banks:

Key      Answer
-------- ------
0-B{F,I}   5
0-B{}      5
0-B{K,L}   4
0-B{J,K}   4
0-B{I}     4

Walk through the DFS:

Visit A: call DFS(B)                             A
  Visit B: call DFS(A), then C, F, J             B 
    Visit A: Already visited
    Visit C: call DFS(B), then D                 C
      Visit B: Already visited
      Visit D: call DFS(C), then E, I, J         D
        Visit C: Already visited
        Visit E: call DFS(D)                     E
          Visit D: Already visited                
        Visit I: call DFS(D), then H             I
          Visit D: Already visited
          Visit H: call DFS(I)                   H
            Visit I: Already visited
        Visit J: call DFS(B), then D and G       J
          Visit B: Already visited
          Visit D: Already visited
          Visit G: call DFS(J)                   G
    In fact, at this point, we've visited
    everything but F, so print that last         F

The answer is ABCDEIHJGF.

In the grading file, I keyed your exam with the line of the adjacency matrix for node A. Here are the keys and answers:

1-A|.X........  1-A|.XX....XX.  1-A|.......X..  1-A|.......XX.  1-A|...X..X...
  abcdeihjgf      abegjchifd      ahbjdcfegi      ahbfjigcde      adgefihbjc

Walk through the BFS. You only need to keep track of the backedges for nodes J and D.

                                 ABCDEFGHIJ  Q: A
Put A on the queue: Path_length: 0.........  Q: A
Process A:          Path_length: 01........  Q: B 
Process B:          Path_length: 012..2...2  Q: CFJ   -- Backedge for J is BJ.  Distance is 2.
Process C:          Path_length: 0123.2...2  Q: FJD   -- Backedge for D is CD.
Process F:          Path_length: 0123.2...2  Q: JD
Process J:          Path_length: 0123.23..2  Q: DG
Process D:          Path_length: 0123423.42  Q: G  -- We're done.  Distance to I is 4.

The answers are 2, 4, BJ, CD.

In the grading file, I keyed your exam with the adjacency list for node B. Here are the keys and answers:

  B{A,C,F,J}  |       B{H}     |      B{F}     |      B{J}      |   B{F,H,J}
      2       |        2       |       2       |       2        |      2
      4       |        4       |       4       |       4        |      4
     BJ       |       HF       |      EJ       |      JI        |     HE
     CD       |       DC       |      JI       |      GD        |     BF

Grading: Each of the three problems was worth 5 points.

Question 18

Since I have given you the order of processing the multimap, you only need to update the distance vector at each step, you only really need to look into when a node's distance is first set, and when it changes. Let's start with the unset ones: C, E, F and G:

C is first set by node H. H's distance is 45, so this is 47. C-47.
E is first set by node G. G's distance is 97, so this is 110. E-110.
F is first set by node D. D's distance is 79, so this is 79+72 = 141. F-141.
G is first set by node D. D's distance is 79, so this is 79+18 = 97. G-97.

The order is C-47, F-141, G-97, E-110. You can flip the order of F and G if you want.

Ok -- so the first setting of each node is:

   A   B   C   D   E   F   G   H   I   J
   0  92  47  79 110 141  97  45  99  66

The nodes whose final distances are different from the above are B-89, F121, I-86 and J-62. I said I didn't care about order, so you don't need to figure out when they were changed.

In your grading, I keyed off the adjacency list for node A (yes, I gave you an adjacency matrix, but you can turn the line for A into a list):

Key                               A{92,79,45,99,66} 
1st 4 Questions (order matters)   C-47,G-97,F-141,E-110  (You can flip G and F)
2nd 4 Questions (any order)       B-89,F-121,I-86,J-62

Key                               A{37,21,17,12,80} 
1st 4 Questions (order matters)   I-23,B-82,D-38,C-91 (You can flip B and D )
2nd 4 Questions (any order)       B-68,C-60,J-78,J-46

Key                               A{24,66,85,30}
1st 4 Questions (order matters)   E-75,I-68,D-47,H-62 (You can flip E and I)
2nd 4 Questions (any order)       G-32,I-45,H-55,E-33

Key                               A{8,10,2,86,70}
1st 4 Questions (order matters)   D-3,E-5,F-43,J-74 (You can flip D and E)
2nd 4 Questions (any order)       I-63,I-20,J-65,H-81

Key                               A{48,9,84,2}
1st 4 Questions (order matters)   J-78,D-31,H-46,C-51 (You can flip D and H)
2nd 4 Questions (any order)       J-43,G-79,G-52,B-12

For grading, the first four questions were worth 8 points, as were the second four questions.

Question 19

Straightforward. This has a main() attached so you can test it:

#include <string>
#include <vector>
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

void dfs(int node, vector <int> &am, int &visited)
{
  int i;

  if (visited & (1 << node)) return;
  visited |= (1 << node);
  printf("%d\n", node);
  for (i = 0; i < am.size(); i++) {
    if (am[node] & (1 << i)) dfs(i, am, visited);
  }
}

int main()
{
  vector <int> am;
  int f, t, i, v;

  while (cin >> f >> t) {
    if (f >= am.size()) am.resize(f+1, 0);
    if (t >= am.size()) am.resize(t+1, 0);
    am[f] |= (1 << t);
    am[t] |= (1 << f);
  }

  for (i = 0; i < am.size(); i++) printf("AM[%d]: 0x%x\n", i, am[i]);

  v = 0;
  dfs(0, am, v);
  return 0;
}

Here we test it on the following graph:

  0 ----------> 1 --------> 3  
  |             |
  |             |
  |             |
  v             v
  2 --> 5 ----> 4

UNIX> ( echo 0 1 ; echo 0 2 ; echo 1 3 ; echo 1 4 ; echo 2 5 ; echo 5 4 ) | a.out
AM[0]: 0x6
AM[1]: 0x18
AM[2]: 0x20
AM[3]: 0x0
AM[4]: 0x0
AM[5]: 0x10
0
1
3
4
2
5
UNIX>

Grading: This was 11 points. Typically you started with 11 points and were deducted for things like:

Wrong arithmetic on checking visited: -1 point
Wrong arithmetic on setting visited: -0.5 point
Wrong arithmetic on the for loop: -2 points
Not checking the adjacency matrix inside the for loop: -4 points

Some of you just wrote a DFS without any bit arithmetic. If it was correct, it was worth 5 points. If you skipped checking adjacency, then 4 points.