Algorithm Design and Problem Solving


Project 1: Median or How to deserve a princess



Hand-out: 6.10., deadline: 27.10.


  1. Find in a literature at least 3 exact methods of median computation and process them into a survey where you are to analyze their advantages, disadvantages, compare them mutually. You will get 4 points for this survey.
  2. The same done for approximate methods, another 4 points.
  3. You can also try to implement the methods and compare them for large N against behaviour of some O(N log N) sorting algorithm; you are expected to process results into a documentation. For each implemented method you will obtain 3 points, together maximally 9 points. Subproject 3 can be solved also in the case you did not solve subproject 1 and/or 2.