Lab5 - Time Complexity

Write a report in overleaf and upload the link in UN Moodle (do not include emails because it sends annoying email updates)

1. Cormen, Leiserson, Rivest and Stein (300 points)
   • Problem 1-1 - solve from 1 microsecond (10^-6 s) for step to for 1 nanoseconds (10^-9 s) for step.
   • Problem 3-1
2. Dasgupta, Papadimitriou and Vazirani (100 points)
   • Exercise 0.1.
   • Exercise 0.2.
3. Time by instruction estimation (200 points): Run 100 x 100 random integer matrix multiplication ten times in C++ in https://www.onlinegdb.com/online_c++_compiler and take time using std::chrono, estimate the time by instruction with min of the running times assuming the you do 2n^3 - n^2 ( n=100) instructions . Do the same with Pyhton native, Numpy and Fortran in Colab, hints:
   • The PyData Toolbox with Scott Sanderson https://www.youtube.com/watch?v=YAHZa8xZWBU
   • https://github.com/ssanderson/pydata-toolbox
   • To be able to run Fortan cells Google Colab you have to install and load fortanmagic before running “pip install -U fortran-magic” in a cell and “%reload_ext fortranmagic” in the following cell.
4. Solve T(n) = 2 T(n-2) + 2, with n = 2k and for T(0) = 0, and T(0)= 1 by Recursive Substitution and the Graphical Method. (100 points)
5. Complete the following table (300 puntos)