Computer Science Assignment on AVL Trees, Hash Maps, and Greedy Algorithms

5/2/2021 Submit Exam 2 | Gradescope

https://www.gradescope.com/courses/225864/assignments/1191153/submissions/new 2/44

making. Your assumptions will be given fair consideration if needed,

but they may be deemed an errant assumption.

Q1.1 Academic Integrity Agreement 1 Point

Save Answer

Q2 Java Maps 5 Points

For each part below assume that:

1. The map data structure is initially empty (the parts are independent,

not cumulative)

2. Methods use the Java Map interface (<- that's a link to it)

Q2.1 Map Declarations 1 Point

Given the declaration:

Map<String, Integer> m = new SomeMap<String, Integer>() // SomeMap has functionally correct Map behavior

The keys will be:

Save Answer

All work submitted will due to my independent work, without

influence by other people and will follow the rules for resources

that can (and can't) be used.

ý

Integerý

Stringý

None of the aboveý

5/2/2021 Submit Exam 2 | Gradescope

https://www.gradescope.com/courses/225864/assignments/1191153/submissions/new 3/44

Q2.2 Map operations 1 1 Point

Consider the following operations:

Map<String, Integer> m = new SomeMap<String, Integer>() m.put("Binary Heap", 1); m.put("Unordered List", 12); m.put("Ordered List", 6);

What value will be returned by m.get("Binary Heap") ?

Save Answer

Q2.3 Map operations 2 1 Point

Consider the following operations:

Map<String, Integer> m = new SomeMap<String, Integer>() m.put("Binary Heap", 1); m.put("Unordered List", 12); m.put("Ordered List", 6);

What value will be returned by m.get("Ordered") ?

Save Answer

1ý

12ý

6ý

None of the aboveý

1ý

12ý

6ý

None of the aboveý

5/2/2021 Submit Exam 2 | Gradescope

https://www.gradescope.com/courses/225864/assignments/1191153/submissions/new 4/44

Q2.4 Map operations 3 1 Point

Consider the following operations:

Map<String, Integer> m = new SomeMap<String, Integer>() m.put("A", 1); m.put("B", 2); m.put("A", 4); m.put("C", 3); m.put("C", 2); m.put("B", 1);

What value will be returned by `m.get("C")`?

Save Answer

Q2.5 Map operations 4 1 Point

Consider the following operations:

Map<String, Integer> m = new SomeMap<String, Integer>() m.put("A", 1); m.put("B", 2); m.put("A", 4); m.put("C", 3); m.put("C", 2); m.put("B", 1);

What value will be returned by `m.keySet().size()`

Enter your answer here

1ý

2ý

3ý

4ý

None of the aboveý

5/2/2021 Submit Exam 2 | Gradescope

https://www.gradescope.com/courses/225864/assignments/1191153/submissions/new 5/44

Save Answer

Q3 Simple Maps and Lists 1 10 Points

For the following parts give the time complexity for the following

method pseudo-code (that is, for each give the time complexity of the

entire method). All questions assume there are items in each list.

insertAllItems(List keys, List values, Map map) for i=0 to keys.size()-1 key = keys.get(i) value = values.get(i) map.put(key, value)

Q3.1 Linked / Unordered Linked 2 Points

Assuming that List s are both Linked Lists and the map is

implemented with an Unordered Linked List:

Save Answer

Q3.2 Array Lists / Unordered Linked 2 Points

Assuming that List s are both Array Based Lists and the map is

implemented with an Unordered Linked List:

n

ý O(1)

ý O(n)

ý O(n ⋅ log(n))

ý O(n )2

ý O(n )3

None of the aboveý

5/2/2021 Submit Exam 2 | Gradescope

https://www.gradescope.com/courses/225864/assignments/1191153/submissions/new 6/44

Save Answer

Q3.3 Array / Ordered Array 2 Points

Assuming that List s are both Array Based Lists and the map is

implemented with an Ordered Array-Based List (items are in

ascending order by keys):

Save Answer

Q3.4 Array / Hash 2 Points

Assuming that List s are both Array Based Lists and the map is

implemented with a Hash Table of size (Assume assume SUH):

ý O(1)

ý O(n)

ý O(n ⋅ log(n))

ý O(n )2

ý O(n )3

None of the aboveý

ý O(1)

ý O(n)

ý O(n ⋅ log(n))

ý O(n )2

ý O(n )3

None of the aboveý

n

5/2/2021 Submit Exam 2 | Gradescope

https://www.gradescope.com/courses/225864/assignments/1191153/submissions/new 7/44

Save Answer

Q3.5 Linked / Hash 2 Points

Assuming that List s are both Linked Lists and the map is

implemented with a Hash Table of size (Assume SUH):

Save Answer

Q4 Map Gets 8 Points

For the following parts give the time complexity for the following

method pseudo-code (that is, for each give the time complexity of the

entire method). All questions assume there are items in the list.

confirmAllKeysPresent(List keys, Map map) for i=0 to keys.size()-1 key = keys.get(i) if map.get(key) == null

ý O(1)

ý O(n)

ý O(n ⋅ log(n))

ý O(n )2

ý O(n )3

None of the aboveý

n

ý O(1)

ý O(n)

ý O(n ⋅ log(n))

ý O(n )2

ý O(n )3

None of the aboveý

n

5/2/2021 Submit Exam 2 | Gradescope

https://www.gradescope.com/courses/225864/assignments/1191153/submissions/new 8/44

return False return True

Q4.1 All Implementations 2 Points

Independent of the implementations used for the List and Map ,

what's the lower bound on execution time:

Remaining sub-parts are about upper bounds

Save Answer

Q4.2 Array / Unordered Linked 2 Points

Assuming that List is an Array Based List and the map is

implemented with a Unordered Linked List:

Save Answer

ý Ω(1)

ý Ω(n)

ý Ω(n ⋅ log(n))

ý Ω(n )2

ý Ω(n )3

None of the aboveý

ý O(1)

ý O(n)

ý O(n ⋅ log(n))

ý O(n )2

ý O(n )3

None of the aboveý

5/2/2021 Submit Exam 2 | Gradescope

https://www.gradescope.com/courses/225864/assignments/1191153/submissions/new 9/44

Q4.3 Array / Ordered Array 2 Points

Assuming that List is an Array Based List and the map is

implemented with a Ordered Array Based List (items are in ascending

order by keys):

Save Answer

Q4.4 Linked / Hash 2 Points

Assuming that List is a Linked List and the map is implemented with

a Hash Table of size (You may assume SUH):

Save Answer

Q5 Hash Load Factors 6 Points

ý O(1)

ý O(n)

ý O(n ⋅ log(n))

ý O(n )2

ý O(n )3

None of the aboveý

n

ý O(1)

ý O(n)

ý O(n ⋅ log(n))

ý O(n )2

ý O(n )3

None of the aboveý

5/2/2021 Submit Exam 2 | Gradescope

https://www.gradescope.com/courses/225864/assignments/1191153/submissions/new 10/44

For the following problems assume a hash table has items and

buckets.

Q5.1 Load Factor <1 1 Point

Assume the load factor is less than 1. This means that:

Save Answer

Q5.2 put() 2 Points

Assuming Simple Uniform Hashing, but that the table does not rehash

to increase the number of buckets, the time complexity of put() is

most accurately described by:

Save Answer

Q5.3 get()

n m

ý m < n

ý m > n

ý m = n

ý O(1)

ý O(log( )) n m

ý O(log( )) m n

ý O(m)

ý O(n)

ý O( ) n m

ý O( ) m n

ý O(m + n)

None of the aboveý

5/2/2021 Submit Exam 2 | Gradescope

https://www.gradescope.com/courses/225864/assignments/1191153/submissions/new 11/44

2 Points

Assuming Simple Uniform Hashing, but that the table does not rehash

to increase the number of buckets, and that each bucket is

implemented with an Ordered array list (in ascending order by key),

the time complexity of get() is most accurately described by:

Save Answer

Q5.4 put() 2 1 Point

If a hash function does not achieve Simple Uniform Hashing, the time complexity of put() should be considered to be:

ý O(1)

ý O(log( )) n m

ý O(log( )) m n

ý O(m)

ý O(n)

ý O( ) n m

ý O( ) m n

ý O(m + n)

None of the aboveý

5/2/2021 Submit Exam 2 | Gradescope

https://www.gradescope.com/courses/225864/assignments/1191153/submissions/new 12/44

Save Answer

Q6 Hash Code Concepts 3 Points

Q6.1 Distinct Objects 1 Point

Two distinct String objects that are considered equivalent (Java's

a.equals(b) would be true ) must have identical hash codes:

Save Answer

Q6.2 Objects 1 Point

Given the Java code:

Type a = someMethod(); // "Type" is a type of object, not a prim Type b = anotherMethod();

ý O(1)

ý O(log( )) n m

ý O(log( )) m n

ý O(m)

ý O(n)

ý O( ) n m

ý O( ) m n

ý O(m + n)

None of the aboveý

Trueý

Falseý

5/2/2021 Submit Exam 2 | Gradescope

https://www.gradescope.com/courses/225864/assignments/1191153/submissions/new 13/44

If a.hashCode()==b.hashCode() is true then a.equals(b) must

also be true:

Save Answer

Q6.3 Compression 1 Point

The "Multiplication method" will uniformly distribute items across

buckets for any value of the multiplier (for any in ):

Save Answer

Q7 Binary Search Tree Questions 0 Points

The following questions will refer to locations in a binary search tree

with nodes labeled with letters as follows:

LABELS CORRESPOND TO LOCATIONs IN A COMPLETELY FULL

TREE, even if the tree isn't full!!!

Trueý

Falseý

A k ⋅ A mod 1

Trueý

Falseý

5/2/2021 Submit Exam 2 | Gradescope

https://www.gradescope.com/courses/225864/assignments/1191153/submissions/new 14/44

If the problem asks for a location, answer with a capital letter (A- O).

If the problem asks for a value at a specific location, answer with an appropriate number, like 10, or NONE if there's nothing in the

designated location. (Use the word "NONE" (without the quotes))

When using letters for locations double check your work by

comparing the "path" to get to the node in your work with the same

path in the tree above. For example, to get to the "?" node in the

following tree:

the path from the root would be left, right, right. Comparing that to the

"full" tree above, going left, right, right from the root leads to node "K",

so the "?" is at location "K".

Confirm that you understand the notation. Give the location of the ?

node in:

Save Answer

G (Hint: This is the correct answer! Make sure you understand how

to pick the correct letter for a node)

ý

Z (This is the wrong answer)ý

5/2/2021 Submit Exam 2 | Gradescope

https://www.gradescope.com/courses/225864/assignments/1191153/submissions/new 15/44

Save Answer

Q8 BST Operations 8 Points

The following are all operations on simple, binary search trees (they

are not balanced AVL trees).

Inserts and removals follow the same conventions described in lecture.

Q8.1 1. insert(6) 1 Point

Given the following tree:

Following an insert(6) , which location will contain the 6 (use a

single capital letter for the answer):

Enter your answer here

Save Answer

Q8.2 insert(0) 1 Point

Given the following tree:

5/2/2021 Submit Exam 2 | Gradescope

https://www.gradescope.com/courses/225864/assignments/1191153/submissions/new 16/44

Following an insert(0) , which location will contain the 0 (use a

single capital letter for the answer):

Enter your answer here

Save Answer

Q8.3 inserts()s & remove() 1 1 Point

Given the following tree:

Following the set of operations: insert(4) , insert(2) , insert(1) ,

remove(9) what value will be in location A (number):

5/2/2021 Submit Exam 2 | Gradescope

https://www.gradescope.com/courses/225864/assignments/1191153/submissions/new 17/44

Enter your answer here

Save Answer

Q8.4 inserts() & remove() 2 1 Point

Given the following tree:

Following the set of operations: insert(4) , insert(2) , insert(1) ,

remove(9) (same as previous problem) what value will be in location

B (number):

Enter your answer here

Save Answer

Q8.5 find() Visits 1 1 Point

A find(key) will "visit" nodes in the tree, starting with the root. You

can think of a visit as occurring the instant that find() evaluates the

node's value (that is, accesses a .value member variable).

Given the following tree:

5/2/2021 Submit Exam 2 | Gradescope

https://www.gradescope.com/courses/225864/assignments/1191153/submissions/new 18/44

How many nodes will be visited for find(42) (number: )

Enter your answer here

Save Answer

Q8.6 find() Visits 2 1 Point

Given the following tree:

How many nodes will be visited for find(1) (number: )

:

Enter your answer here

Save Answer

0 … ∞

0 … ∞

5/2/2021 Submit Exam 2 | Gradescope

https://www.gradescope.com/courses/225864/assignments/1191153/submissions/new 19/44

Q8.7 BST Height 2 Points

Assume that is an even number greater than 6 and that integers will

be inserted into a binary search tree in the following order:

, , , , , , , ...,

The height of the binary search tree is best approximated by:

Save Answer

Q9 AVL Trees 11 Points

The following are all operations on AVL trees!

Inserts and removals follow the same conventions described in lecture

( remove() will use the in-order successor!)

Q9.1 insert(19) 1 Point

Given the following AVL tree:

n

2 n

+2 n 1 −2

n 1 +2 n 2 −2

n 2 +2 n 3 −2

n 3 n

1ý

ý log(n)

ý 2 n

ý n

ý 2 ⋅ n

ý n2

5/2/2021 Submit Exam 2 | Gradescope

https://www.gradescope.com/courses/225864/assignments/1191153/submissions/new 20/44

Following an insert(19) , which location will contain the 19 (use a

single capital letter for the answer):

Enter your answer here

Save Answer

Q9.2 insert(28) 1 Point

Given the following AVL tree:

5/2/2021 Submit Exam 2 | Gradescope

https://www.gradescope.com/courses/225864/assignments/1191153/submissions/new 21/44

Following an insert(28) , which location will contain the 28 (use a

single capital letter for the answer):

Enter your answer here

Save Answer

Q9.3 remove(9) 1 Point

Given the following AVL tree:

Following a remove(9) , which value will be in the location that was

occupied by the 9 (a number)?

Enter your answer here

Save Answer

Q9.4 remove(2) 1 1 Point

Given the following AVL tree:

5/2/2021 Submit Exam 2 | Gradescope

https://www.gradescope.com/courses/225864/assignments/1191153/submissions/new 22/44

Following a remove(2) , which value will be in the location B (a number)?

Enter your answer here

Save Answer

Q9.5 remove(2) 2 1 Point

Given the following AVL tree:

5/2/2021 Submit Exam 2 | Gradescope

https://www.gradescope.com/courses/225864/assignments/1191153/submissions/new 23/44

Following a remove(2) , which value will be in location D?

Enter your answer here

Save Answer

Q9.6 remove(24) 1 1 Point

Given the following AVL tree:

Following a remove(24) , which value will be in location C (number)?

Enter your answer here

Save Answer

Q9.7 remove(24) 2 1 Point

Given the following AVL tree:

5/2/2021 Submit Exam 2 | Gradescope

https://www.gradescope.com/courses/225864/assignments/1191153/submissions/new 24/44

Following a remove(24) , what location will contain the value 5 (letter)?

Enter your answer here

Save Answer

Q9.8 AVL Height 2 Points

Assume that is an even number greater than 6 and that integers will

inserted into an AVL search tree in the following order:

, , , , , , , ...,

The best asymptotic approximation of the height height of the tree is:

Save Answer

n

2 n

+2 n 1 −2

n 1 +2 n 2 −2

n 2 +2 n 3 −2

n 3 n

ý O(1)

ý O(log(n))

ý O( )2 n

ý O(n)

ý O(2 ⋅ n)

ý O(n )2

5/2/2021 Submit Exam 2 | Gradescope

https://www.gradescope.com/courses/225864/assignments/1191153/submissions/new 25/44

Save Answer

Q9.9 min() 2 Points

The minimum value in an AVL tree will only occur at a leaf node (a

node with no children):

Save Answer

Q10 Map Implementations 6 Points

Different Map implementations have different strengths and

weaknesses. For each question indicate which implementation is best

at the given operation (best in terms of time complexity)

You may assume the simple uniform hashing assumption for hash

maps and that the total number of buckets exceeds .

Q10.1 Enumerating 2 Points

Enumerating all the keys in ascending order:

Save Answer

Q10.2 Minimum 2 Points

Trueý

Falseý

n

Hash Mapý

Unordered Linked List based Mapý

Binary Search Tree based Mapý

5/2/2021 Submit Exam 2 | Gradescope

https://www.gradescope.com/courses/225864/assignments/1191153/submissions/new 26/44

Getting the key with the minimum value:

Save Answer

Q10.3 remove() 2 Points

The remove() operation:

Save Answer

Q11 Graph 1 4 Points

Consider the following graph:

Hash Mapý

Ordered Linked List based Mapý

Binary Search Tree based Mapý

Hash Mapý

Ordered Linked List based Mapý

Binary Search Tree based Mapý

5/2/2021 Submit Exam 2 | Gradescope

https://www.gradescope.com/courses/225864/assignments/1191153/submissions/new 27/44

Q11.1 Directed or Undirected 1 Point

The graph is:

Save Answer

Q11.2 Simple 1 Point

The graph is simple:

Undirectedý

Directedý

Trueý

Falseý

5/2/2021 Submit Exam 2 | Gradescope

https://www.gradescope.com/courses/225864/assignments/1191153/submissions/new 28/44

Save Answer

Q11.3 Acyclic 1 Point

The graph is acyclic:

Save Answer

Q11.4 Topological Sort 1 Point

The node order: A, C, D, B, E, F, G, I, H is a topological order:

Save Answer

Q12 Graph 2 4 Points

Consider the following graph:

Trueý

Falseý

Yesý

No, but there are valid topological ordersý

There isn't a valid topological sort for this graphý

5/2/2021 Submit Exam 2 | Gradescope

https://www.gradescope.com/courses/225864/assignments/1191153/submissions/new 29/44

Q12.1 Directed or Undirected 1 Point

The graph is:

Save Answer

Q12.2 Simple 1 Point

The graph is simple:

Save Answer

Q12.3 Acyclic

Undirectedý

Directedý

Trueý

Falseý

5/2/2021 Submit Exam 2 | Gradescope

https://www.gradescope.com/courses/225864/assignments/1191153/submissions/new 30/44

1 Point

The graph is acyclic:

Save Answer

Q12.4 Connected Components 1 Point

How many distinct sets of "connected components" does the graph

contain (number ):

Enter your answer here

Save Answer

Q13 Graph Implementations 6 Points

Consider each of the following graph implementations and their

impact:

Q13.1 Graph Implementations 1 2 Points

A graph implementation will use the adjacency matrix approach (using

a 2D array) and will only support simple, undirected weighted graphs.

It's not known in-advance how many vertices the graph will contain

and new vertices may be added dynamically. Assuming the matrix is

always sized to support the current graph, the time complexity of

adding a new vertex is:

Trueý

Falseý

0 − ∞

5/2/2021 Submit Exam 2 | Gradescope

https://www.gradescope.com/courses/225864/assignments/1191153/submissions/new 31/44

Save Answer

Q13.2 Graph Implementations 2 2 Points

A graph implementation will use the adjacency matrix approach (using

a 2D array) and will only support simple, undirected weighted graphs.

(I.e., same as the prior part). Assuming the matrix is always sized to

support the current graph, the time complexity of removing an edge is:

Save Answer

Q13.3 Graph Implementations 3 2 Points

ý O(1)

ý O(∣V ∣)

ý O(∣E∣)

ý O(∣V ∣ + ∣E∣)

ý O(∣V ∣ )2

ý O(∣E∣ )2

ý O((∣V ∣ + ∣E∣) )2

None of the aboveý

ý O(1)

ý O(∣V ∣)

ý O(∣E∣)

ý O(∣V ∣ + ∣E∣)

ý O(∣V ∣ )2

ý O(∣E∣ )2

ý O((∣V ∣ + ∣E∣) )2

None of the aboveý

5/2/2021 Submit Exam 2 | Gradescope

https://www.gradescope.com/courses/225864/assignments/1191153/submissions/new 32/44

Assume a graph is implemented with adjacency lists (that is, vertices

have lists of edges). What is the worst-case time complexity to

enumerate the edges from a single vertex in a simple graph:

Save Answer

Q14 BFS 5 Points

Consider Breadth First Search of the following graph:

Q14.1 BFS(A) 1 Point

ý O(1)

ý O(∣V ∣)

ý O(∣E∣)

ý O(∣V ∣ + ∣E∣)

ý O(∣V ∣ )2

ý O(∣E∣ )2

ý O((∣V ∣ + ∣E∣) )2

None of the aboveý

5/2/2021 Submit Exam 2 | Gradescope

https://www.gradescope.com/courses/225864/assignments/1191153/submissions/new 33/44

Would the following be a valid order for breadth-first search starting

from A ( BFS(A) ):

A, B, E, D, C, F

Save Answer

Q14.2 BFS(B) 1 Point

Would the following be a valid order for breadth-first search starting

from B ( BFS(B) ):

B, A, E, D, C, F

Save Answer

Q14.3 BFS(D) 1 Point

Would the following be a valid order for breadth-first search starting

from D ( BFS(D) ):

D, E, B, F, A, C

Save Answer

Yes, that would be a valid order for BFSý

No, that order would not be possible with BFSý

Yes, that would be a valid order for BFSý

No, that order would not be possible with BFSý

Yes, that would be a valid order for BFSý

No, that order would not be possible with BFSý

5/2/2021 Submit Exam 2 | Gradescope

https://www.gradescope.com/courses/225864/assignments/1191153/submissions/new 34/44

Q14.4 BFS Order 2 Points

Assume BFS starts at vertex . If BFS's initial visit to vertex happens

before its initial visit to vertex , then there must be a shorter path (in

terms of the number of edges) from to than from to .

(Here you can consider the "initial visit" to be when BFS first loops

through the vertex's edges)

Save Answer

Q15 DFS 7 Points

Given the following graph:

Consider using the DFS algorithm given in lecture (Slide 65)

Assume that:

time is a global variable and that it's 0 prior to the first time DFS()

is called on a vertex.

x v

t

x v x t

Yesý

Noý

5/2/2021 Submit Exam 2 | Gradescope

https://www.gradescope.com/courses/225864/assignments/1191153/submissions/new 35/44

Edges are ordered based on alphabetical order of their opposite

end. For example, Vertex F has edges connecting to C and B. Since

B comes first in the alphabet, the edge to B would be before the

edge to C in F's adjacency list.

Note: If you're not proficient at alphabetical order, please carefully

double check your work: a b c d e f

All the following parts assume that DFS starts at vertex A ( DFS(A) )

Q15.1 DFS(A) 1 1 Point

What will A's start time be (number )?

Enter your answer here

Save Answer

Q15.2 DFS(A) 2 1 Point

Which vertex will be the first to have a finish time assigned (letter

from A-F):

Enter your answer here

Save Answer

Q15.3 DFS(A) 3 1 Point

Which vertex will be the second to have a finish time assigned (letter

from A-F):

Enter your answer here

0 − ∞

5/2/2021 Submit Exam 2 | Gradescope

https://www.gradescope.com/courses/225864/assignments/1191153/submissions/new 36/44

Save Answer

Q15.4 DFS(A) 4 1 Point

What will D's finish time be (number )

Enter your answer here

Save Answer

Q15.5 DFS(A) 5 1 Point

What will A's finish time be (number )?

Enter your answer here

Save Answer

Q15.6 DFS General 2 Points

Assume DFS starts at vertex . If DFS's initial visit to vertex happens

before its initial visit to vertex , then there must be a shorter path (in

terms of the number of edges) from to than from to .

(Here you can consider the "initial visit" to be when DFS first starts

looping through a vertex's edges)

Save Answer

0 − ∞

0 − ∞

x v

t

x v x t

Yesý

Noý

5/2/2021 Submit Exam 2 | Gradescope

https://www.gradescope.com/courses/225864/assignments/1191153/submissions/new 37/44

Q16 Dijkstra's Algorithm 9 Points

Consider the following graph:

For the following problems assume that:

A Vertex's Adjacent edges are processed in alphabetical order

based on the opposite end. So the Vertex would iterate through

it's edges in order: edge to , edge to , and finally the edge to .

If identical values are in a priority queue, the first one with that value

is removed first. For example, if there are two items in a priority

queue with the value 3, the first one that was set to 3 will be

removed before the one that was set to 3 second. (That is, you

should assume the priority queue is stable)

You should use the version of Dijkstra's algorithm from Wikipedia

that utilized a priority queue (Link: Dijkstra's Algorithm with PQ)

The following questions ask about the "n-th" vertex removed from the

priority queue. The start vertex is considered to be the first (1st) vertex

removed from the queue.

x

v y z

5/2/2021 Submit Exam 2 | Gradescope

https://www.gradescope.com/courses/225864/assignments/1191153/submissions/new 38/44

Note: If you're not proficient at alphabetical order, please carefully

double check your work: s t u v w x y z

--

All the following parts assume that Dijkstra's starts at vertex s ( Dijkstra(s) )

Q16.1 Dijkstra(s) 1 1 Point

What will be the fourth (4th) vertex removed from the priority queue

(letter s-z)?

Enter your answer here

Save Answer

Q16.2 Dijkstra(s) 2 1 Point

Which vertex will be the first to have its priority decreased as a result

of line 21 executing twice on that vertex (that is, the vertex that is the first to have its priority decreased twice) (letter s-z)

Enter your answer here

Save Answer

Q16.3 Dijkstra(s) 3 1 Point

What will be the sixth (6th) vertex removed from the priority queue

(letter s-z)?

Enter your answer here

S A

5/2/2021 Submit Exam 2 | Gradescope

https://www.gradescope.com/courses/225864/assignments/1191153/submissions/new 39/44

Save Answer

Q16.4 Dijkstra(s) 4 1 Point

What is the length of the shortest path from to (number )?

Enter your answer here

Save Answer

Q16.5 Dijkstra(s) 5 1 Point

What will be the last vertex removed from the priority queue (letter s-

z)?

Enter your answer here

Save Answer

Q16.6 Dijkstra's General 1 1 Point

Dijkstra's algorithm will never find any correct path lengths on any

graph if the graph contains any negative edge weights.

Save Answer

Q16.7 Dijkstra's General 2 2 Points

w s 0 − ∞

Trueý

Falseý

5/2/2021 Submit Exam 2 | Gradescope

https://www.gradescope.com/courses/225864/assignments/1191153/submissions/new 40/44

The version of Dijkstra's algorithm used for this problem may fail to

terminate (i.e., loop forever) if a graph has negative edge weights.

Save Answer

Q16.8 Dijkstra's General 3 1 Point

Dijkstra's algorithm is an example of a greedy algorithm:

Save Answer

Q17 Prim's Algorithm 7 Points

Consider the following graph:

Trueý

Falseý

Trueý

Falseý

5/2/2021 Submit Exam 2 | Gradescope

https://www.gradescope.com/courses/225864/assignments/1191153/submissions/new 41/44

For the following problems assume that:

A Vertex's Adjacent edges are processed in alphabetical order

based on the opposite end. So the Vertex would iterate through

it's edges in order: edge to , edge to , and finally the edge to .

If identical values are in a priority queue, the first one with that value

is removed first. For example, if there are two items in a priority

queue with the value 3, the first one that was set to 3 will be

removed before the one that was set to 3 second. (That is, you

should assume the priority queue is stable)

You should use the version of Prim's algorithm from lecture (Link:

Prim's Algorithm on Slides 13 and 14)

The following questions ask about the "n-th" vertex removed from the

priority queue. The start vertex is considered to be the first (1st) vertex

removed from the queue.

All the sub-parts assume z is the start vertex

Q17.1 Prim(z) 1 Point

x

v y z

5/2/2021 Submit Exam 2 | Gradescope

https://www.gradescope.com/courses/225864/assignments/1191153/submissions/new 42/44

Which vertex will be the first (1st) removed from the PQ (letter s-z):

Enter your answer here

Save Answer

Q17.2 Prim(z) 1 Point

Which vertex will be the first to have its priority decreased twice (the '"decrease" priority associated with u' happens twice on the vertex)

(letter s-z):

Enter your answer here

Save Answer

Q17.3 Prim(z) 1 Point

The minimum weight from y that is used in the MST is (number 1,3,4):

Enter your answer here

Save Answer

Q17.4 Prim(z) 1 Point

The minimum weight from x that is used in the MST is (number 1,2,3):

Enter your answer here

Save Answer

5/2/2021 Submit Exam 2 | Gradescope

https://www.gradescope.com/courses/225864/assignments/1191153/submissions/new 43/44

Q17.5 Prim(z) 1 Point

The fifth (5th) vertex extracted from PQ is (letter s-z):

Enter your answer here

Save Answer

Q17.6 MST General 1 Point

The set of edges that forms a minimal spanning tree must be distinct

(it's not possible to ever have two different sets of edges that form

valid minimal spanning trees):

Save Answer

Q17.7 Prim General 1 Point

Prim's algorithm is an example of a greedy algorithm:

Save Answer

Q18 Exam Assumptions 0 Points

Indicate any assumptions that you made that had an impact on your

solution to specific problems. Clearly indicate: 1) Each problem/part

and 2) The corresponding assumptions. For example:

Trueý

Falseý

Trueý

Falseý