Please fill out this quiz, and press the "Submit"
button at the end.
Don't collaborate with anyone on quiz exercise solutions.
Please answer all questions.
[No spaces and no dashes.]
Login ID :
1. You may recall from CS61B that a priority queue is a data structure, with two operations:
insert(x, p) inserts the element x into the priority queue, with priority p;
deletemin() finds the element in the priority queue whose priority is minimal, deletes it from the priority queue, and returns it.
Suppose we have an efficient implementation of a priority queue, using a binary heap.
Let N denote the number of elements currently in the priority queue.
(a) What is running time of the insert() operation, using big-O notation? No explanation needed.
(b) What is running time of the deletemin() operation, using big-O notation? No explanation needed.
Is it possible for the shortest path from s to t
to visit some vertex twice?
Begin your answer with "yes" or "no", and then explain briefly why or why not (a sentence should be enough).