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).