Temporal Complexity and Sorting Algorithms

Description of what to do

Exercise 1.

Given the following graph in logarithmic scale about the temporal complexity of three algorithms (A1, A2, and A3), identify which asymptotic temporal cost of the following corresponds to each of the algorithms: O(n), O(n2), O(n3), O(log n), O(n log n) or O(2n). Justify your answer (Hint: none of the three algorithms has the same asymptotic cost).

Ejercicio 2.

Given the code for the following methods, work out the computational complexity of each one of them. Justify your answer.

Algorithm 1

int sharePosition ( Phone[] a) {

int result = 0;

for (int i = 0; i < a.length – 1; i++) {

for (int j = i + 1; j < a.length; j++) {

result += a[i].shares (a[j]);

}

}

return result;

}

Algorithm 2

int divideAndConquer (int n, int k) {

2

if (k == 1) {

return Integer.Infinity;

}

int acum = 0;

for (int d = n; k <= d; d /= k) {

acum++;

}

return acum;

}

You may need to take a look at some of the simple operations on finite series to work out how many times a loop is executed (http://en.wikipedia.org/wiki/Summation).

Exercise 3.

Solve the following:

1. Let three such algorithms called A, B and C have time complexity of O(n2), O(n1.5) and O(n log n), respectively. During a test, each algorithm spends 10 seconds to process 100 data items. Estimate the time each algorithm should spend to process 10000 items.

2. Software packages A and B have processing time exactly t = 3n1.5 and t’ = 0.03n1.75, respectively. If you are interested in faster processing of up to n = 108

data items, then which package should be chosen? Justify your answer.

Exercise 4.

Solve the following:

• Sort the sequence 8, 1, 4, 1, 5, 9, 2, 6, 5 using the Insertion Sort method. Specify the vector’s state in each of the algorithm steps.

• In Java, the natural object order is defined by means of the Comparable interface. When an object implements such interface, it can use the compareTo method to determine whether an object a is less than, equal, or greater than another object b:

• If the result of a.compareTo(b) is negative, then it means that a<b

• If it is zero it means that a=b (equals should return true as well)

• If it is positive, then a>b

This Comparable interface is used by the Java sorting algorithms. Complete the compareTo method inside the Movie (edu.uoc.mecm.eda.nerdflix) class following the criteria you will find in the comments at the start of the method. After that, you can execute

3

the tests included in the same class. (Hint: to sort objects from the String class in lexicographic order you may need to ignore case).

• Many times we may want to sort an object by more than one field, apart from the one established by compareTo. In Java, this is possible by implementing the Comparator interface. We can create multiple sorting criteria for a T class implementing classes which implement Comparator<T>. For instance, we can create a class that sorts integers in the natural order, sorts them according to the number of dividers it has.

To compare them in this class, we use the compare method, which is very similar to compareTo (<0 if a<b, >0 if a>b, and 0 if a=b).

Sorting method implemented in Java can also use objects from the Comparator class as an additional parameter to specify a different order as the one specified by Comparable.

In this exercise you will have to implement a sorting filter which sorts the movies by title and creation date. You can find the code in the TitleAndYearFilter (edu.uoc.mecm.eda.nerdflix.filters) class, as well as its corresponding tests.

Exercise 5.

We have been hired to design and implement a movie streaming service called Nerdflix, in which users can search for movies among the entire catalog and watch them as desired. As part of our work, we have been specifically tasked to implement the part of the application in which users can look for movies and sort them as they wish.

It has been specified that users can only sort movies by title and creation date (by using the TitleAndYearFilter from Exercise 4).

The engineering team you command has developed two sorting algorithms which are to be checked out. The first of them is a variant of the MergeSort (edu.uoc.mecm.eda.utils), whereas the other is a variant of the QuickSort (edu.uoc.mecm.eda.utils). Moreover, our team wishes to compare these variants to the already implemented algorithm available in the Java Arrays class.

For this exercise, you will have to implement an experimental test on the computational time for each of these algorithms:

• You should try different vector sizes: 10, 100, 1.000, 10.000, 100.000, 1.000.000 and 10.000.000.

• For each vector size, you must generate 30 different instances of vectors of that size (check how random videogame collections are generated in the provided class) and calculate the mean time of that algorithm for solving problems of that size.

• After executing the experiments (which may take up to several hours), you will have to determine which algorithm works best (you can use graphic charts to help you). Moreover, you must compare the

4

M0.506 · Estructuras de Datos y Algoritmos · PEC2 · 2015-16 Máster en Ingeniería Computacional y Matemática · Estudis d'Informàtica Multimèdia i Telecomunicació

experimental cost of MergeSort, QuickSort and Arrays.sort() with the theoretical temporal cost (e.g., you can draw the theoretical costs as a reference in the chart).

To complete this exercise you can find a code skeleton (edu.uoc.mecm.eda.nerdflix.LibraryExperiment) which you will have to modify to achieve your goal. The results will automatically be stored in the result folder within your project. Take into account that the algorithms should be compared in the most similar conditions so as the comparison is fair and right.

•

5