1. Graph Traversals (205 points).

Consider the graph below:

a) (30 points). If we perform a BFS traversal starting from vertex 7, what will be the final vertex visited?

○ 1           ○ 2           ○ 3           ○ 4           ○ 5           ○ 6           ○ 7           ○ 8

b) (40 points). What start vertex (or vertices) will result in a DFS pre-order of 84265173? Assume ties are broken numerically. If no start vertex would yield 84265173 from a pre-order traversal, select

Impossible.

□ 1 □ 2 □ 3 □ 4 □ 5 □ 6 □ 7 □ 8 □ Impossible

c) (60 points) What start vertex (or vertices) will result in a DFS post-order of 84265173? Assume ties are broken numerically. If no start vertex would yield 84265173 from a post-order traversal, select    Impossible.

□ 1 □ 2 □ 3 □ 4 □ 5 □ 6 □ 7 □ 8 □ Impossible

d) (75 points) Suppose we want a DFS pre-order of 12345678, i.e. in numerical order. In the original graph, there is no vertex that could possibly yield this order if we perform a pre-order traversal.

What is the minimum number of edges we'd need to add to the graph so that a pre-order traversal could yield this order from some start vertex?

○ 1 ○ 2 ○ 3 ○ 4 ○ 5 ○ 6 ○ 7 ○ 8 ○ Impossible

2. Heaps and Tree Traversals (120 Points).

Suppose we have an ArrayHeap that uses the array representation from class and discussion  (also called "tree representation 3B" in lecture). Recall that in this representation that the leftmost item is unused.

Consider a heap with the following underlying array:

a) (35 points) Suppose we perform a pre-order traversal of the heap represented by this array. What will be the last value in the pre-order traversal?

○ -5      ○ - 1      ○ 3        ○ 0        ○ 4        ○ 5        ○ 6        ○ 10

b) (35 points) Suppose we perform an in-order traversal of the heap represented by this array. What will be the last value in the in-order traversal?

○ -5      ○ - 1      ○ 3        ○ 0        ○ 4        ○ 5        ○ 6        ○ 10

c) (50 points) Suppose we are using our heap to represent a priority queue. If we call removeMin on the heap above, where will the 10 end up after removeMin has completed execution?

Assume removeMin works as described in lecture and discussion. By "completed execution", we mean the entire operation is done and the array again obeys our heap properties.

○ 10 will not move.

○ 10 will not be present in the heap.

○ In the root position previously occupied by a -5.

○ In a position previously occupied by a 4.

○ In a position previously occupied by a 5.

○ In a position previously occupied by a 6.

○ In a position previously occupied by a - 1.

○ In a position previously occupied by a 0.

3. Space Git (75 Points)

Answer the following multiple choice questions regarding the Git version control system. For each question, choose the best answer.

a) (25 Points) Sklurp the space horse was stuck on project 1 after spending a few days on it, so Sklurp    decided to start over from the skeleton code. Sklurp first deleted the proj1 directory in their sp21-s***   repo, but then realized they weren't sure what to do next to get the skeleton code to come back. Which of the following commands could Sklurp enter next to restore the working directory so that it contains the   skeleton code for proj1? Assume the CWD is Sklurp's sp21-s*** repo.

○ git pull skeleton master

○ git add * then git commit -m "starting over"

○ git pull skeleton origin

○ git push

○ git push origin master

○ git checkout skeleton/master -- proj1

b) (25 Points) Later in the semester, Sklurp tried to start back over on Gitlet. After executing some other Git commands they don’t remember, git status is telling them that their sp21-s*** repo is in a            “detached HEAD” state. What does this mean? Note that this question is independent of part a).

○ Their repo isn’t in a clean state. Some changes need to be committed.

○ They are no longer synced with the skeleton repo.

○ Some files were deleted after they were added, but before they were committed.

○ They tried to git push origin master and something went wrong, so HEAD changed its value.

○ HEAD is pointing to a commit that is not pointed to by a branch.

○ HEAD is pointing to corrupt files in the staging area.

c) (25 Points) What command below might possibly work to get Sklurp out of "detached HEAD" state? Below,  [some hash] means some hash id, e.g. Sklurp would actually type something

like 8bc2dc48260553244d2f72cf56d916a56eea96c2, and not literally  [some hash]. Again, assume the CWD is Sklurp's sp21-s*** repo.

○ git checkout master

○ git add * then git commit -m "starting over"

○ git pull skeleton master

○ git checkout [some hash] .

○ git pull origin master

4. Hashing. (195 points)

a) Those are the facts (40 Points). Throughout this problem, assume we're using a hashtable (as seen in lecture) to represent a set. Suppose that each bucket of the hashtable is stored as a left leaning red black  tree, and we are inserting items that implement the Comparable interface. Which of the following           statements are true about such a hashtable?

b) Adding (120 points). Suppose now that we build a Set using a hashtable, where we     represent each bucket with a linked list. Suppose we've added the Picture objects below with the given hashcodes in red:

○ 0        ○ 1        ○ 2        ○ 3        ○ 4

2) (40 points) If we resize our hashtable by doubling its size, items with which hashcode will end up in a different bucket number than before the resize operation? Assume we're starting from the original

figure above without the         .

□ 5          □ 1          □ 3          □ 103      □ 28        □ 9

3) (40 points) Suppose that we perform the following actions on the original hashtable with 5 buckets illustrated in the image above:

1.   Picture x =

2.   hashTable.add(x); // as above, x's hashCode is 9!

3.   x.turnPink(); // modifies x

4.   System.out.println(hashTable.contains(x));

Assume that the turnPink method changes some of x's pixels pink and adds a 3rd eye so that it looks like        . This change to the object may result in its hashcode changing.

For which of the following hashcodes will line 4 of the above code print out true? Note that a Picture object's equals method returns true only if their pixel values are exactly identical.

□ x.hashCode() is - 1 □ x.hashCode() is 0 □ x.hashCode() is 4 □ x.hashCode() is 14

□ None of these

5. By the Numbers (370 Points).

a) Hash tables. For the three questions below, suppose we have an initially empty hash table with 32 buckets and which does not resize in any of these problems. The hash table starts empty for each sub- part, for example any additions done in part 1 don't affect part 2. Do not assume anything about how the items are spread out.