CS 170 Reading Quiz -- Week 4, Wednesday

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

1. You may recall from CS61B that a queue is a first-in-first-out data structure, with two operations: enqueue(x) appends the element x to the tail of the queue; dequeue() returns the element at the head of the queue, removing it from the queue. (The difference between a queue and a stack is that a queue is a first-in-first-out data structure, while a stack is a first-in-last-out data structure.)

Suppose we have an efficient implementation of a queue (such as a doubly-linked list with a head and tail pointer). Let N denote the number of elements currently in the queue.

(a) What is running time of the enqueue() operation, using big-O notation? No explanation needed.

(b) What is running time of the dequeue() operation, using big-O notation? No explanation needed.

2. 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 (such as one that uses 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? Explain briefly.

(b) What is running time of the deletemin() operation, using big-O notation? Explain briefly.

3. What did you find difficult or confusing about the reading or the lectures, 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.

CS 170 home page