Algorithms Supervision 2

Recommended reading

Chapters 4, 15, 16 of Introduction to Algorithms (3rd edition) by Cormen, Leiserson, Rivest & Stein.

Exercises

Bolded items are taken from the exercise sheet:

1. 1. Sketch a proof of why a comparison-based sorting algorithm can never do better than O(n log n) complexity.
   2. Describe an algorithm which is able to sort faster than O(n log n).
   3. Why do we ever use comparison-based algorithms if faster algorithms are available?
2. Use recurrence relations to find the complexity of:
   1. Binary search
   2. Quicksort, where the pivot always splits the list perfectly in half
   3. Quicksort, where the pivot is always the largest or smallest element of the list
   4. Quicksort, where the pivot always splits the list in the ratio 10%:90%
   5. An algorithm which behaves like: T(n) = T(n^½) + k, with T(2) = 1
3. 1. Exercise 24
   2. Write a Fibonacci program which makes use of dynamic programming. How many function calls does this version make?
4. Exercise 25
5. Your task is to write a routefinding application, which suggests which roads to use to travel between two distant cities. You are given a list of cities, and a list of roads which directly connect two cities each. Each city has a pair of geographical co-ordinates, and each road has a length. Your boss has heard lots of buzzwords recently, and insists that the algorithm uses one of the following approaches:
   1. Divide and conquer
   2. Greedy
   3. Backtracking
   4. MM method
   For each approach, briefly describe how the routefinding algorithm could work (using pseudocode or diagrams if you like), and discuss its practicality.
6. Generate a Huffman code for "CAMBRIDGE COMPSCIS CAN COMPRESS CHARACTERS". What compression rate do you get over using the same number of bits for each character? Give example strings which compress better and worse when using this Huffman code.