CS 170 Reading Quiz -- Week 4, Tuesday

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.


Name:

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.


2. Let G be a directed graph where each edge has a positive length. In other words, the length of every edge is strictly greater than 0. Let s and t be two vertices in G.

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


3. What did you find difficult or confusing about the reading for the upcoming lecture, and what would you most like to see explained better? If nothing was difficult or confusing, and you understand the material pretty well, tell us what you found most interesting. Please be as specific as possible.


4. What questions do you still have about previous material? If nothing was difficult or confusing, and you understand the material pretty well, tell us what you found most interesting. Please be as specific as possible.


CS 170 home page