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