HW2. Growth of functions, plotting and reporting (17th of Sep, 23.59)
Reporting is important, let's practice to make your homework attractive:
If you are using Python make sure to complete this homework in the Jupyter Notebook which later lets you produce either HTML or PDF file as a report (and submit the notebook .ipynb itself as the code). If you are not familiar with Jupyter Notebooks follow the instructions for setup and usage from here.
If you use some other programming language please use this overleaf template (in LaTex) to produce PDF report for this homework and submit your code as usual. You can use a desktop LaTex editor like TeXmaker or come up with your own template similar to the one provided.
In unlikely case of you using R, you can use RMarkdown to produce a report (then, submit .Rmd file along with your report).
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. Explain why the statement, “The running time of algorithm A is at least O(n2),” is meaningless.
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?