.. _Revision: Revisions ********* This chapter does not contain any new content, it is only intended to prepare you for the final exam. Multiple choice question ======================== .. quiz:: exo_complex_manipREV :title: Asymptotic notations Indicate, for each pair of expressions :math:`(A,B)` in the table below, whether :math:`A` is :math:`o`, :math:`O`, :math:`\Theta`, :math:`\Omega`, :math:`\omega` of :math:`B`. .. csv-table:: :header: :math:`A` ! :math:`B` ! :math:`o` (A < B) ! :math:`O` (A ≲ B) ! Θ (A ∼ B) :widths: 10,10,17,17,17 :delim: ! :math:`n` ! :math:`n+1` ! :quiz:`{"type":"TF","answer":"F"}`! :quiz:`{"type":"TF","answer":"T"}`! :quiz:`{"type":"TF","answer":"T"}` :math:`n` ! :math:`n^{1.5}` ! :quiz:`{"type":"TF","answer":"T"}`! :quiz:`{"type":"TF","answer":"T"}`! :quiz:`{"type":"TF","answer":"F"}` :math:`4n^2` ! :math:`n^2 + n^{1.5}` ! :quiz:`{"type":"TF","answer":"F"}`! :quiz:`{"type":"TF","answer":"T"}`! :quiz:`{"type":"TF","answer":"T"}` :math:`\log{10n}` ! :math:`10\sqrt{n}` ! :quiz:`{"type":"TF","answer":"T"}`! :quiz:`{"type":"TF","answer":"T"}`! :quiz:`{"type":"TF","answer":"F"}` :math:`n\log{n}` ! :math:`n\log{n}\log{n}` ! :quiz:`{"type":"TF","answer":"T"}`! :quiz:`{"type":"TF","answer":"T"}`! :quiz:`{"type":"TF","answer":"F"}` :math:`\log{n^{10}}` ! :math:`\log(n)` ! :quiz:`{"type":"TF","answer":"F"}`! :quiz:`{"type":"TF","answer":"T"}`! :quiz:`{"type":"TF","answer":"T"}` :math:`\log_{10}{n}` ! :math:`\log(n)` ! :quiz:`{"type":"TF","answer":"F"}`! :quiz:`{"type":"TF","answer":"T"}`! :quiz:`{"type":"TF","answer":"T"}` :math:`5^n` ! :math:`3^{n+4}` ! :quiz:`{"type":"TF","answer":"F"}`! :quiz:`{"type":"TF","answer":"F"}`! :quiz:`{"type":"TF","answer":"F"}` :math:`3^{2n + 2}` ! :math:`5^n` ! :quiz:`{"type":"TF","answer":"F"}`! :quiz:`{"type":"TF","answer":"F"}`! :quiz:`{"type":"TF","answer":"F"}` .. quiz:: complex_compound_algo_ifREV :title: Find the complexity 2 Assume that we have the following functions: - ``f1(n)`` runs in :math:`\Theta(1)` - ``f2(n)`` runs in :math:`\Theta(\log(n))` - ``f3(n)`` runs in :math:`\Theta(n)` - ``f4(n)`` runs in :math:`\Theta(n^2)` Moreover, ``cond(n)`` is a boolean function (it returns *true* or *false*) which runs in constant time :math:`\Theta(1)`. Give the runtime complexity of the following algorithms: .. code-block:: def algo1(n): f1(n) f3(n) f3(n) Runtime complexity of ``algo1(n)``: Θ(:quiz:`{"type":"SC", "values":"1,log(n),log(n)*log(n),n,n*log(n),n*log(n)*log(n), n^2, log(n)*n^2, n^3, log(n)*n^3","answer":"n"}`) .. code-block:: def algo2(n): for i = 0 to log(n): f1(n) f2(n) f1(n) f1(n) Runtime complexity of ``algo2(n)``: Θ(:quiz:`{"type":"SC", "values":"1,log(n),log(n)*log(n),n*log(n),n*log(n)*log(n), n^2, log(n)*n^2, n^3, log(n)*n^3","answer":"log(n)*log(n)"}`) .. code-block:: def algo3(n): for i = 0 to n: f2(n) f2(n) f4(n) Runtime complexity of ``algo3(n)``: Θ(:quiz:`{"type":"SC", "values":"1,log(n),log(n)*log(n),n*log(n),n*log(n)*log(n), n^2, log(n)*n^2, n^3, log(n)*n^3","answer":"n^2"}`) .. code-block:: def algo4(n): for i = 0 to n: f2(n) f2(n) f4(n) for i = 0 to n: f4(n) f2(n) Runtime complexity of ``algo4(n)``: Θ(:quiz:`{"type":"SC", "values":"1,log(n),log(n)*log(n),n,n*log(n),n*log(n)*log(n), n^2, log(n)*n^2, n^3, log(n)*n^3","answer":"n^3"}`) .. code-block:: def algo5(n): for i = 0 to log(n): if i%3 == 0: f3(n); else: f4(n); Runtime complexity of ``algo5(n)``: O(:quiz:`{"type":"SC", "values":"1,log(n),log(n)*log(n),n,n*log(n),n*log(n)*log(n), n^2, log(n)*n^2, n^3, log(n)*n^3","answer":"log(n)*n^2"}`), can we say that the bound is tight? :quiz:`{"type":"TF","answer":"T"}` .. code-block:: def algo6(n): for i = 0 to n: if cond(n): f2(n); else: f3(n); Runtime complexity of ``algo6(n)``: O(:quiz:`{"type":"SC", "values":"1,log(n),log(n)*log(n),n,n*log(n),n*log(n)*log(n), n^2, log(n)*n^2, n^3, log(n)*n^3","answer":"n^2"}`), can we say that the bound is tight? :quiz:`{"type":"TF","answer":"F"}` .. code-block:: def algo7(n): for i = 0 to n: if cond(n): f2(n); else: f2(n); Runtime complexity of ``algo7(n)``: O(:quiz:`{"type":"SC", "values":"1,log(n),log(n)*log(n),n,n*log(n),n*log(n)*log(n), n^2, log(n)*n^2, n^3, log(n)*n^3","answer":"n*log(n)"}`), can we say that the bound is tight? :quiz:`{"type":"TF","answer":"T"}` .. quiz:: count_recursion_rev :title: Count the recursive calls Consider the following recursive functions: .. code-block:: ones1(n): if n <= 0: print(1); else: ones1(n // 2); .. code-block:: ones2(n): if n <= 0: print(1); else: print(1); ones2(n // 2); .. code-block:: ones3(n): if n == 0: print(1); else: ones3(n - 1); ones3(n - 1); .. code-block:: ones4(n): if n == 0: print(1); else: ones4(n // 2); ones4(n // 2); The number of ones printed by the previous functions is in the order of: - ``ones1(n)``: Θ(:quiz:`{"type":"SC", "values":"1,log(n),log(n)*log(n),n,n*log(n), n^2, log(n)*n^2, 2^n, n!","answer":"1"}`) - ``ones2(n)``: Θ(:quiz:`{"type":"SC", "values":"1,log(n),log(n)*log(n),n,n*log(n), n^2, log(n)*n^2, 2^n, n!","answer":"log(n)"}`) - ``ones3(n)``: Θ(:quiz:`{"type":"SC", "values":"1,log(n),log(n)*log(n),n,n*log(n), n^2, log(n)*n^2, 2^n, n!","answer":"2^n"}`) - ``ones4(n)``: Θ(:quiz:`{"type":"SC", "values":"1,log(n),log(n)*log(n),n,n*log(n), n^2, log(n)*n^2, 2^n, n!","answer":"n"}`) .. quiz:: ex_sort_complex :title: Sorting time complexity Give the worst case and average case runtime complexity for the following sorting algorithms: .. csv-table:: :delim: ! :header: Algorithm ! Worst Case ! Average Case Quick sort ! O(:quiz:`{"type":"SC", "values":"n, n*log(n), n^2","answer":"n^2"}`) ! O(:quiz:`{"type":"SC", "values":"n, n*log(n), n^2","answer":"n*log(n)"}`) Insertion sort ! O(:quiz:`{"type":"SC", "values":"n, n*log(n), n^2","answer":"n^2"}`) ! O(:quiz:`{"type":"SC", "values":"n, n*log(n), n^2","answer":"n^2"}`) Merge sort ! O(:quiz:`{"type":"SC", "values":"n, n*log(n), n^2","answer":"n*log(n)"}`) ! O(:quiz:`{"type":"SC", "values":"n, n*log(n), n^2","answer":"n*log(n)"}`) Heap sort ! O(:quiz:`{"type":"SC", "values":"n, n*log(n), n^2","answer":"n*log(n)"}`) ! O(:quiz:`{"type":"SC", "values":"n, n*log(n), n^2","answer":"n*log(n)"}`) .. quiz:: ex_rec_eq :title: Solve the recurrence equation. Remember that :math:`\sum_{i=0}^{i\leq n} a^i = \frac{1-a^n}{1-a}` with :math:`a>0, a\neq 1`. - The complexity :math:`T1(n)`, with :math:`n` the length of the input, of a recursive algorithm is given by: .. math:: T1(n) = \begin{cases} c_0 & \textrm{ if } n\leq 1 \\ c_1 + 3T1(n/3) & \textrm{ otherwise.} \end{cases} with :math:`c_0` and :math:`c_1` two constants. Solve this recurrence equation, the runtime complexity is: Θ(:quiz:`{"type":"SC", "values":"1,log(n),n,n*log(n), n^2, log(n)*n^2, 2^n","answer":"n"}`) - The complexity :math:`T2(n)`, with :math:`n` the length of the input, of a recursive algorithm is given by: .. math:: T2(n) = \begin{cases} c_0 & \textrm{ if } n\leq 1 \\ c_1 + T2(n/2) & \textrm{ otherwise.} \end{cases} with :math:`c_0` and :math:`c_1` two constants. Solve this recurrence equation, the runtime complexity is: Θ(:quiz:`{"type":"SC", "values":"1,log(n),n,n*log(n), n^2, log(n)*n^2, 2^n","answer":"log(n)"}`) - The complexity :math:`T3(n)`, with :math:`n` the length of the input, of a recursive algorithm is given by: .. math:: T3(n) = \begin{cases} c_0 & \textrm{ if } n\leq 1 \\ c_1*n + T3(n/2) & \textrm{ otherwise.} \end{cases} with :math:`c_0` and :math:`c_1` two constants. Solve this recurrence equation, the runtime complexity is: Θ(:quiz:`{"type":"SC", "values":"1,log(n),n,n*log(n), n^2, log(n)*n^2, 2^n","answer":"n"}`) .. quiz:: ex_counting_sort :title: Counting sort Counting sort is a sorting algorithm for small integer numbers with a linear runtime complexity. Assume that we have an array :math:`A` of size :math:`n` containing numbers between 0 and 1000. To sort this array, counting sort proceeds as follows: - For each number between 0 and 1000 compute how many times this number appears in :math:`A`. - Create the sorted array with the right elements at the right place. For example, if the number 0 appears 5 times in :math:`A` then the 5 first numbers of the sorted array are 0; then, if the number 1 appears 3 times in :math:`A` then the elements 5, 6 and 7 of the sorted array are 1; and so on. Propose an efficient pseudo-code for counting sort under the assumption that the elements of the input array are integers between 0 and 1000. .. quiz:: ex_counting_stairs :title: Boring day You are at the bottom of a staircase made up of :math:`n` steps. You choose the following arbitrary rule for climbing the staircase. If the number of the current step (the first step has the number 0) is: - even: you can climb either 1 or 3 steps. - odd: you can only climb 1 step. You want to know the total number of different ways to reach the :math:`n`-th step starting from the bottom of the stair. Let :math:`G(m)` be the number of ways to reach the step :math:`m`. For example, reaching step 4 can be done in the following ways: - Go to step 1, then step 2, then step 3, then step 4; or - Go to step 3, then step 4 Thus, we have G(4)=2. 1. Give a recursive definition of :math:`G(m)` 2. Propose a naïve recursive pseudocode algorithm to compute :math:`G(m)`. 3. Propose an optimized dynamic programming iterative algorithm for computing :math:`G(m)`. 4. Give the runtime complexity of your algorithm with respect to :math:`n`. .. quiz:: ex_longest_alternating_subsequence :title: Longest alternating sub-sequence Let :math:`a` be an array of numbers of size :math:`n`. A subsequence of :math:`a` is an array composed of elements of :math:`a` taken in order (we can remove elements from :math:`a` but we cannot change their order). For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7], but [1,3,2,7] is not. The longest increasing subsequence problem is to find the longest subsequence :math:`s=[s_1,\dots,s_m]` of :math:`a` such that: - :math:`s_1 < s_2 > s_3 < s_4 > \ldots` **OR** - :math:`s_1 > s_2 < s_3 > s_4 < \ldots` Let :math:`L\uparrow(i)` (respectively :math:`L\downarrow(i)`) be the length of longest alternating subsequence ending at index :math:`i` of :math:`a` and whose last element is greater (respectively smaller) than its penultimate (the one before the last). 1. Give a recursive formulation of :math:`L\uparrow(i)` and :math:`L\downarrow(i)`. 2. Draw the subproblem graph of :math:`L\uparrow(4)` and :math:`L\downarrow(4)` 3. Propose a naïve recursive algorithm to compute the longest alternating subsequence of :math:`a`. .. .. quiz:: weighted_activity_selection :title: Weighted activity selection problem During the lecture we have seen the activity selection problem which was described as follows. Suppose you are in charge of allocating slots in one of the school's lecture halls. For each day, you receive several reservation requests each with a start time :math:`s_i` and a finish time :math:`f_i`. Unfortunately, you cannot accept all the reservations as some are overlapping (for example activity :math:`k` wants to starts while activity :math:`\ell` has not yet finished). You thus have to select a subset of activities that do not overlap: this is called a feasible solution. In the weighted activity selection problem, each activity as a weight :math:`w_i` which represent the amount of money the school will receive if it hosts this activity. Then, the goal is to find a subset of activities that do not overlap and whose total weight is maximal. Unfortunately, contrarily to the activity selection problem, the weighted activity selection problem cannot be solved with a greedy algorithm and one must use dynamic programming to solve it efficiently. Assume that the requests are sorted by finish time and for any request .. https://www.geeksforgeeks.org/greedy-algorithms/