Exercise: Algorithms

1. Complexity and Efficency:
   1. How complex is an algorithm that computes the inner product of two vectors with dimension n.
   2. Assume you run a sorting algorithm on a CPU that does 10⁹ operations per second (1 GHz) and you want to order an array with n=10⁷ (10 million) elements. Also assume that one machine cycle corresponds to one operation in the sense of metric of the algorithm.
      Compare the running times of an algorithm with O(n²) with an algorithm with O(n log(n)).
   3. Find one function example and bound for each asymptotic bound type: Big-Theta "Θ", Big-Oh O, Big-Omega "Ω", Little-oh "o" and Little-Omega "ω".

2. Calculation with Boolean Logic

3. Abstract Data Types: Array, List and Hash
   1. Implement a telephone book in Java. It must be possible to enter names and numbers or read them from a file.
   2. Realize an implementation where the telephone book data is stored in an array.
   3. Extend the implementation to store the telephone book data in a list.
   4. Extend the implementation to store the telephone book data in a hash-table.
   5. Compare the performance (search time for 1000 telephone numbers) of array, list and hash-table for a village(1000 phones), a small town(100000 phones) and New York (10 million phones).

4. Quick Sort:
   1. Implement the Quick Sort algorithm in Java or pseudo code.
   2. Prepare to explain your implementation.

5. k-means clustering:
   1. Implement the k-means algorithm basted on the Java EM-Algo code.
   2. Prepare to explain your implementation.