# Midterm Exam

Bart Massey 2018-08-06

This exam is due before class Monday 12 February 2018. You may take up to three hours to work on the exam, broken up however you wish. Please use only your textbook and notes and the notes on the wiki.

Please submit your exam by email as a PDF (only) to myself bart@cs.pdx.edu and Sascha sastrand@pdx.edu. A subject line of "NB Algs Exam W2018" would be really helpful. You may do the exam with pencil and paper and scan it to PDF if you are a really clear writer. Otherwise get whatever tool you're using to output PDF and send that.

1. Let's pair a couple of people up! Exactly how many unordered pairs of people (sets of two people) can be chosen from a set of n people? Justify your answer.

2. When lining up children, it is well known that children born in odd years get along fine, but children born in even years must be separated if they are too close in age.

Given: An array a of unique positive integers.

Find: A permutation of the elements of a such that

• All even elements of a are in ascending order
• All odd elements of a are in ascending order
• Any pair of even numbers i, i+2 is separated by at least one odd number

Report failure if no such permutation exists.

For example, the array [2,8,20,12,10,25,1] might be arranged as [2,8,1,10,25,12,20]. The array [2,8,20,12,10,25,26] has no solution.

(a) Give pseudocode for an algorithm for this problem that runs in worst-case O(|a|^2) time and O(1) space. Explain the correctness and complexity of your algorithm.

(b) Give pseudocode for an algorithm for this problem that runs in worst-case O(|a| lg |a|) time and O(|a|) space. Explain the correctness and complexity of your algorithm.

3. You have an implementation of a max-heap that includes the standard functions `upheap(h,i)` and `downheap(h,i)` that move an element at position i to its proper place in the heap h. Your heap implementation includes the standard `insert(h,x)` and `extract_max(h)` operations.

Let us add the `alter(h,i,x)` operation, which changes the value of the heap entry at position i to x and then restores the heap property.

Give pseudocode for an algorithm for `alter()`. What is the worst-case running time of your algorithm?