ADA 2021 Mideterm p6 + p7 Solution & Grading policy

--- tags: ADA2021 --- # ADA 2021 Mideterm p6 + p7 Solution & Grading policy ## Rubrics on gradescope For subproblem 6-(b), 6-(d), 6-(e), the rubrics will only shows that your submission is empty or not. If you're submission is not empty, there will be some comments on individual subproblems in the "comments" section. For subproblem 6-(a), 6-$c$, 6-(f), the rubrics is for grading. If you didn't receive full credit, you can see some comments in the "comments" section. ## 6-(a) ### Solution Let $dp(i)$ be the maximum subarray sum that the subarray ends at $a_i$. We can have the following transition: $$ dp(i) = \begin{cases} a_1 & i = 1 \\ \max(0, dp(i - 1)) + a_i & \text{otherwise} \end{cases} $$ After calculating the dp values, the answer will be $\max(0, \max_{1 \leq i \leq n} dp(i))$. ### Grading Policy If your algorithm only sums up all positive numbers, or simply sums up all numbers, you receive 0 points in this subproblem. Otherwise, one minor mistake will receive -0.5 point penalty. Common minor mistakes includes: * No specification of the answer value. * No consideration of all negative number case (in this case, the answer should be $0$) * No base case / Wrong base case ## 6-(b) ### Solution Let $dp(i, j)$ be the maximum subarray value that ends at $a_i$ and has already remove at most $j$ elements. Note that $a_i$ might also be removed. We can have the following transitions: $$ dp(i, j) = \begin{cases} 0 & i = 0, j \geq 0 \\ -\infty & j < 0 \\ \max(dp(i - 1, j - 1), dp(i - 1, j) + a_i, a_i) & \text{otherwise} \\ \end{cases} $$ After calculating the above dp values, the answer will be $\max_{0 \leq i \leq N, 0 \leq j \leq K}dp(i, j)$ #### Time complexity proof: Since there are $O(NK)$ states and for each states, the transition takes $O(1)$ time. So the time complexity is $O(NK)$. #### Correctness proof: Considering the maximum subarray the ends at $a_i$, and has removed $j$ elements($a_i$ might be deleted), let the optimal solution is $OPT$ There are three cases: * $a_i$ is the start of the subarray * $a_i$ is not in the subarray, then $OPT$ is the optimal substructure in $dp(i - 1, j - 1)$ * $a_i$ is in the subarray, then $OPT/i$ is the optimal substructure in $dp(i - 1, j)$ And the above three cases includes all the possible cases, so we can find the best subarray after calculating all the above dp values! ### Grading Policy The 5 points in this subproblem is divided into three parts: * algorithm (3 points) * 0.5 point for base case * 0.5 point for answer value * 2 points for transition function: * If your problem becomes "choosing a prefix as a subarray"(no $a_i$ term in the transition function), you will receive -1 as penalty, since it's a major mistake * The other two terms $dp(i - 1, j - 1), dp(i - 1, j) + a_i$, each term counts 0.5 point * time complexity proof (1 points): * If you write pseudo code and I can easily tell that the complexity is $O(NK)$, you can receive 1 point * You need to state "there are $O(NK)$ states and $O(1)$ cost for each transition" to receive 1 point * If you only write $O(NK)$, you will receive 0.5 point * otherwise, you will receive 0 point * correctness proof (1 points) * If there's one minor mistake in your correctness proof, you will receive -0.5 as penalty * minor mistakes includes: * You lost some cases * You didn't mention the operations you can do * Other penalty * If your algorithm is $O(NK^2)$, you will receive additional -1 penalty ## 6-$c$ ### Solution We can sort those $m$ numbers. And then we can delete the smallest $\min(K, \text{number of negative numbers})$ numbers. ### Grading policy If your algorithm simply adds up all the $m$ numbers, you will receive 0 points. Otherwise, there's a -0.5 penalty for each minor mistakes. Minor mistakes includes: * delete more then $K$ numbers * delete some positive numbers ## 6-(d) ### Solution Let's take a look at the following submatrix: $$ \begin{pmatrix} f(l_1, r_1) & f(l_1, r_2) \\ f(l_2, r_1) & f(l_2, r_2) \end{pmatrix} $$ where $1 \leq l_1 < l_2 \leq N, 1 \leq r_1 < r_2 \leq N$. If $l_2 > r_1$, then $f(l_2, r_1) = \min(0, a_1, a_2, \dots, a_N) \times N - (l_2 - r_1)$ is always smaller then $f(l_2, r_2)$, so it's always meet the definition of totally monotone matrix. So we only need to consider the case that $l_2 \leq r_1$ Assume that we remove $k_1$ elements in $f(l_2, r_1)$, and $k_2$ elements in $f(l_2, r_2)$. First of all, I need to show that $k_1 \leq k_2$ by proof by contradiction. Assume that $k_1 > k_2$, then there must be a negative number in $[l_2, r_1]$ such that this number is not deleted in $f(l_2, r_2)$. If I delete this number, the solution is better. Thus, $k_1 \leq k_2$ must holds. After proofing $k_1 \leq k_2$, we can split into two cases: $f(l_2, r_1) > f(l_2, r_2)$ and $f(l_2, r_1) = f(l_2, r_2)$. Case 1: $f(l_2, r_1) > f(l_2, r_2)$ We can show that, from $f(l_2, r_1)$ to $f(l_1, r_1)$, we need to add $a_{l_1}, \dots, a_{l_2 - 1}$, similarly, we need to add $a_{l_1}, \dots, a_{l_2 - 1}$ when we transfer from $f(l_2, r_2)$ to $f(l_1, r_2)$. Since the two terms add the same elements, and $k_1 \leq k_2$. It means that $f(l_2, r_1)$ can delete more elements or equal elements in $[l_1, l_2 - 1]$. Thus, $f(l_1, r_1) > f(l_1, r_2)$ must holds. Case 2: $f(l_2, r_1) = f(l_2, r_2)$ Similar to the previous case. We can show that, from $f(l_2, r_1)$ to $f(l_1, r_1)$, we need to add $a_{l_1}, \dots, a_{l_2 - 1}$, similarly, we need to add $a_{l_1}, \dots, a_{l_2 - 1}$ when we transfer from $f(l_2, r_2)$ to $f(l_1, r_2)$. Since the two terms add the same elements, and $k_1 \leq k_2$. It means that $f(l_2, r_1)$ can delete more elements or equal elements in $[l_1, l_2 - 1]$. Thus, $f(l_1, r_1) \geq f(l_1, r_2)$ must holds. Thus, we can show that $B$ is a totally monotone matrix! ### Grading policy * If you didin't prove the case of $l_1 > r_2$, you will receive a -2 penalty. * One minor mistake will receive a -1 penalty. * If your algorithm successfully show that $\begin{pmatrix} f(i, j) & f(i, j + 1) \\ f(i + 1,j) & f(i + 1, j + 1) \end{pmatrix}$ is a totally monotone matrix, but fail to extend this to the general case, you will receive a -2 penalty. ## 6-(e) ### Solution I'll prove this by proof of contradiction. If there exist a pair $(i, j)$, such that $i < j, h(i) > h(j)$, then we can take a look at the following matrix: $$ \begin{pmatrix} X & h(i) \\ h(j) & Y \end{pmatrix} $$ The row of the matrix is row $i$ and row $j$, and $X, Y$ are arbitrary values. Since $h(j)$ is the leftmost maximum element of row $j$, we can show that $h(j) \geq Y$. Since $h(i)$ is the leftmost maximum element of row $i$, we can show that $h(i) > X$. But by the definition of totally monotone matrix, $h(j) \geq Y$ must imply $X \geq h(i)$, which is a contradiction. Thus, we can prove that, for any $(i, j)$ satisfying $i < j$, $h(i) \leq h(j)$ must holds. Thus, $h(1) \leq h(2) \leq \dots \leq h(n)$ ### Grading Policy * If you give a nice try, you will recive $1 - 0.5 \times \text{number of minor mistake}$ points * If you give a correct proof, you will receive $3 - 0.5 \times \min(2, \text{number of minor mistake})$ points * Otherwise, you receive $0$ points. ## 6-(f) ### Solution Let $R$ be the set of row indexes The algorithm goes as follows: ``` divide_and_conquer(R): if |R| == 1: // base case Find h(R[0]) in O(mg(n, m)) time return; // divide divide R into odd-indexed rows (R_odd) and even_indexed rows (R_even) divide_and_conquer(R_even) // conquery insert 0 to the head of R_even and insert n + 1 to the tail of R_even Let h(0) = 1, h(n + 1) = m Get h(R_odd[i]) by looping from h(R_even[i]) to h(R_even[i + 1]) ``` ### time complexity proof We can see that: * $T(1) = O(mg(n, m))$ * $T(n) = T(\frac{n}{2}) + (n + m)g(n, m)$ We can split the above recursion relation by the terms of $n, m$: * $T(n) = T(\frac{n}{2}) + ng(n, m)$ * $T(n) = ng(n, m) + \frac{n}{2}g(n, m) + \dots$ * $T(n) = ng(n, m)$ * $T(n) = T(\frac{n}{2}) + mg(n, m)$ * $T(n) = m \log n g(n, m)$ Overall, the time complexity is $O((n + m \log n)g(n, m))$ ### correctness proof If $h(i)$ is calculated in base case, it's trivial that it's correct. Otherwise, $h(R_{odd}[i])$ is updated from $h(R_{even}[i])$ and $h(R_{even}[i + 1])$. Since $R_{even}[i] \leq R_{odd}[i] \leq R_{even}[i + 1]$ and $h(R_{even}[i])$ and $h(R_{even}[i + 1])$ is calculated correctly, we can calculate $h(R_{odd}[i])$ correctly. (Since we have proved that $h(R_{even}[i]) \leq h(R_{odd}[i]) \leq h(R_{even}[i + 1])$) ### Grading policy * Divide: 3 points * one minor mistake will receive -1 penalty * Conquer: 3 points * one minor mistake will receive -1 penalty * time complexity analysis: 2 points * one minor mistake will receive -0.5 penalty * minor mistakes includes: * $T(n) = T(\frac{n}{2}) + ng(n, m)$ analysis wrong * miss $g(n, m)$ in complexity term * correctness proof: 1 point * one minor mistkae will receive -0.5 penalty  ## 7 - Comments * Each comment worth 0.5 points * Note that if your comment is "No comments" or something like that, the "No comments" counts for one comment ## 7 - Format * If you fail to write **Your Name** on the answer sheet, you will receive 0 points * If you fail to write every problem on separte page, you will receive 0 points * Otherwise, you can receive 2 points.