Guidelines for writing pseudocode:

1. C/Java/Python instructions are fine. But do not write object-oriented additions. Do not declare or use any class. Declare only procedures (if necessary) and explain in words what each procedure does, and what is the use of each parameter.

2. One instruction per line

3. Match the brackets with a horizontal line

4. Number your lines

5. Write down if your array is indexed 0...n1 or 1...n.

6. If you decide to use procedures/functions/methods from the class (such as, say, DELETE- MAX(S) for S a max-heap), explain clearly what they do and in what running time. Explain the data structures, if any.

Question: Suppose we are given a n-element sequence S such that each element in S represents a different vote in an election, where each vote is given as an integer representing the ID of the chosen candidate (these IDs come from the range 1 . . . n^5). Suppose you know the number k < n of candidates running. Describe a O(n log k) worst-case algorithm for determining who wins the election. Argue that your running time is correct. Note that k could be much smaller than n and O(n log n) is only a partial solution.