Confidential Teaching Materials:
Quiz 8 Grading Criteria, Page 1 of 3
Quiz 8 Grading Criteria
Note: To receive any credit whatsoever, the date, your name, your student number, and your answers must
be legible and readily readable in the judgment of the grader.
Add brief explanatory comments as necessary to make sure your answers are clear and unambiguous
to the grader.
[p1] 70 points
For each part of this question you are to give the Big-O of the given algorithms, along with an explanation of your
answer. You must provide an explanation in order to receive credit. On questions which refer to an “ordered”
data structure, assume the data is in descending order.
a) Searching for a value in an ordered array of size N
LINES=7
b) Finding the largest value in an ordered linked list of size N
LINES=7
c) Performing a Mergesort on an array of N elements
LINES=7
d) Finding the smallest value in a full and balanced binary search tree
LINES=7
e) Inserting a node into an ordered linked list of size N. The linked list must still be ordered after the insertion.
LINES=7
f) Searching for the smallest value in a full and balanced binary tree of ordered linked lists. Both the binary tree
and linked lists are of size N.
LINES=7
g) Find the Big-O of the following procedure
procedure Lots_O_Loops(m, n, p isoftype in Num)
i isoftype num
i <- 0
loop
exitif(m = 0)
loop
exitif(i = p)
loop
exitif(n = 0)
n <- n – 1
endloop
i <- i + 1
endloop
m <- m – 1
endloop
endprocedure // Lots_O_Loops
LINES=7
Confidential Teaching Materials:
h) Finding the average of an array of size N
LINES=7
i) Searching for the largest value in a binary search tree
LINES=7
j) Searching for the smallest value in a linked list of ordered arrays. Both the linked list and arrays are of size N.
LINES=7
[c1] 70 points
7 points each
[p2] 30 points
Consider the following graph. It represents the graph of several cities and the distances between them.
(A)—-18—–(B)——-23——(C)
/ | / \ | \
13 | 14 15 | 2
/ | / \ | \
(E) 11 (D)—11–(F) 35 (G)
\ | |\ | | /
7 | 16 3 10 | 6
\ | | \ | | /
(H)–5—(I) \—-(J)—-25—-(K)
You work for a travel agency and your customer would like to travel to each city, but wants to travel the smallest
distance. Using a greedy search, choose the links that you would use to connect the cities. Mark the links on the
graph above. (If you make errors on your first try, and thus make a mess of the graph above, you may redraw the
appropriate graph below.) Start from node (E).
Confidential Teaching Materials:
Quiz 8 Grading Criteria, Page 3 of 3
[c2] 30 points