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.
SID: [No spaces and no dashes.]
Login ID : [e.g., cs170-xy]
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).