# Graph Search, Shortest Paths, and Data Structures Week 3 | Problem Set #3 Quiz Answer

## Graph Search, Shortest Paths, and Data Structures Week 3 | Problem Set #3 Quiz Answer

#### Problem Set #3

Question 1)

Suppose you implement the functionality of a priority queue using a sorted array (e.g., from biggest to smallest). What is the worst-case running time of Insert and Extract-Min, respectively? (Assume that you have a large enough array to accommodate the Insertions that you face.)

- Ө(n) and Ө(n)
- Ө(n) and Ө(1)
- Ө(log n) and Ө(1)
- Ө(1) and Ө(n)

Question 2)

Suppose you implement the functionality of a priority queue using an unsorted array. What is the worst-case running time 1/1 point of Insert and Extract-Min, respectively? (Assume that you have a large enough array to accommodate the Insertions that you face.)

- Ө(1) and Ө(log n)
- Ө(n) and Ө(n)
- Ө(n) and Ө(1)
- Ө(1) and Ө(n)

Question 3)

You are given a heap with n elements that supports Insert and Extract-Min. Which of the following tasks can you achieve in O(log n) time?

- Find the fifth-smallest element stored in the heap.
- Find the largest element stored in the heap.
- Find the median of the elements stored in the heap.
- None of these.

Question 4)

You are given a binary tree (via a pointer to its root) with n nodes. As in lecture, let size(x) denote the number of nodes in the subtree rooted at the node x. How much time is necessary and sufficient to compute size(x) for every node x of the tree?

- Ө(n)
- Ө(n2)
- Ө(height)
- Ө(n log n)

Question 5)

Suppose we relax the third invariant of red-black trees to the property that there are no three reds in a row. That is, if a node and its parent are both red, then both of its children must be black. Call these relaxed red-black trees. Which of the following statements is not true?

- Every red-black tree is also a relaxed red-black tree.
- There is a relaxed red-black tree that is not also a red-black tree.
- The height of every relaxed red-black tree with n nodes is O(log n).
- Every binary search tree can be turned into a relaxed red-black tree (via some coloring of the nodes as black or red).