Basic Options (For self practice and code review)

• Quick select, probabilistic
  See book, Section 4.6.  Try with different settings of probability – 0.5, 0.2, 0.8 etc.

Project 2 Options (Choose the option that matches the last digit of GWID) 

Option 0: Quick select, deterministic (median of medians method)
See textbook, Section 4.6

Option 1: Closest pair of points
See textbook, Section 4.7

Option 2,3: Staircase / Pareto-optimal Points
See textbook, Section 4.11, Exercise #12

Option 4,5: Convex hull
We are given a set P of n points in a two-dimensional plan, and we want to compute the convex hull of P. The convex hull is defined as the smallest convex polygon containing the points. (A way to visualize a convex hull is to imagine nails on all the points of the plane and put an elastic band around the points – the shape of the elastic band is the convex hull.) Describe an O(n log n) time divide and conquer algorithm to find the convex hull of the set P of n points.

Option 6: Finding Max Number in Circular Shifted Array
We are given an array A[1..n] of sorted integers that has been circularly shifted
some positions to the right. For example, [35, 42, 5, 15, 27, 29] is a sorted array that has been
circularly shifted 2 positions, while [27, 29, 35, 42, 5, 15] has been shifted 4 positions.
We can obviously find the largest element in A in O(n) time. Describe an O(log n) algorithm.

Option 7: Kruskal’s Algorithm for Minimum Spanning Tree
See textbook, Section 5.5

Option 8: Merging Sorted Lists
See textbook, Section 5.3
You are given an array a[] of numbers, where a[i] is the size of the i-th list to merge.  You have to produce the sequence in which to merge the lists, and the total cost of merging all the lists.  Implementation Notes: Use a heap data structure.  (You don’t have to implement your own heal structure, you can simply use the inbuilt one in Java/C#.)

Option 9: Hoffman Coding
Given a set of symbols and their frequency of usage, find a binary code for each symbol, such that:
a. Binary code for any symbol is not the prefix of the binary code of another symbol.
b. The weighted length of codes for all the symbols (weighted by the usage frequency) is minimized.