HW2. Growth of functions, plotting and reporting (16th of Sep, 23.59)
EX1. Function ordering.
Rank the following functions by their order of growth, that is, find an arrangement f1, f2, …, fn of the functions satisfying f1 = Ω(f2), f2 = Ω(f3), etc. If some functions satisfy f1 = Θ(f2), then mark it as well.
The functions are: 2lg*n, n3, lg*n, en, n, n2, lg(n!), 2n, n!, 22^n, ln(n), (n + 1)!, nlg(n), 1, 22^(n+1). (Note: since we couldn't insert triple layer powers in here, we used ^ symbol for that. Also lg* is called iterated logarithm so treat it accordingly)
EX2. Use Gnuplot or other plotting library (e.g. matplotlib if you use Python, or ggplot2 in R) to visually compare growth rates of functions (at least 8) from the task 1. If possible let all functions have their own colour (you can use color wheel to keep them distinguishable) and type (dotted line, dashed, etc.), also add color legend. Provide meaningful names for both axes. How can you avoid some functions to flatten out on the plot? Can you see the same ordering as you have came up with in the first task?
Gnuplot brief tutorial - http://people.duke.edu/~hpgavin/gnuplot.html.
EX3. True, false, or else? “For every problem whose solution can be quickly verified, one can also solve it quickly. E.g. if we can verify solution of a sudoku puzzle in O(n) where n is number of cells in the sudoku table, then we can come up with an algorithm of same order or polynomial degree to solve the puzzle.” elaborate by explaining P, NP and NP-completeness concepts.
EX4. Use a sorting algorithm you implemented last week. Explore which inputs cause it to work slower (on average) and which make it finish faster. Show that this pattern persists over many runs. What is a strategy for designing these inputs?
Hint: you may want to look up for the concept of inversions of an array or list of items considered for sorting.
EX5. Recurrences (e.g. T(n) = 2* T ( n/2 ) + n )) can be used to determine time complexity of an algorithm - e.g. using “The Master Theorem”. T(n) stands for the number of operations that needs to be done on array of size n in order to solve some task (e.g. sort an array of size n). The same recurrence can also be recursively calculated. In this task, you will be working with the following recurrence:
T(n) = T( n/i ) + T( n - n/i ) + n
Note that n/i can be expressed as a fraction of n (e.g. if i = 2, then n/i = n/2, which can reflect splitting array of size n into two equal partitions). Keep in mind that T(1) = 1, T(0) = 0. For subtasks 1 and 2 (to make it simpler), when n < i, then T(n) = n. When the result of a division is not an integer, e.g. T(3/2), then you can choose to either round it down or up, but make sure to do the same in both.
Calculate the number of operations (plug in numbers to to a function T(n)) in the following three scenarios:
- i = 2 (e.g. T(n) = T(n/2) + T(n - n/2) + n);
- Incrementally change the value of i from 3 to 10, assess how this changes T(n);
- Instead of splitting according to i, select splits at random (T(n) = T(x) + T(n-x) + n where x is a random integer from 1 to n-1.), like the selection of a pivot in Quicksort. Repeat the experiment several times and calculate the average. To which “i” is the random selection similar to?
Make a plot, which includes every scenario to show how T(n) changes as n increases. To the resulting plot, add two functions: n*log(n) and n^2. What is the relationship between the three scenarios and these two functions?
EX6. (bonus 2p) Devise an experiment to attempt to detect and measure the effect of the memory caching on the program execution run time. E.g. manipulating values nearby or far from each other. Can you detect when the calculations get slower significantly when you start addressing areas outside of the cache?