COMPUTING SCIENCE 210
Algorithm Analysis and Data Structures

Review Questions — General

Choosing an appropriate algorithm

1. Describe an efficient algorithm for the extremal problem, defined below. Your algorithm should be described in high-level terms, using pseudo-code. You may use as a subroutine (and without explanation) any algorithm we have discussed in this course.

   Extremal Problem

   Input: An array A of n distinct integers, where n is divisible by 10.

   Output: Two arrays, S and L, each of size n/10, where S contains the smallest n/10 elements from A, and L contains the largest n/10 elements in A. [Note: Within any group, the elements are not required to be in any particular order.]

   What is the running time of your algorithm? (Give enough detail to justify your answer.)

2. Compare hash tables with AVL trees for representing sets and mappings. In particular, discuss their relative execution times for the Map operations get(k), put(k,v), and remove(k), for the priority operations min() and removeMin(), and for listing the elements of the set in order. Include any other considerations that you deem to be relevant and significant.