[DAA/H2] Finished everything except ex 3.1.

2 files changed, 85 insertions, 40 deletions

diff --git a/Year 2/Design and analysis of algorithms/Homeworks/Homework2.pdf b/Year 2/Design and analysis of algorithms/Homeworks/Homework2.pdf
index 170f0e2..d78e80f 100644
--- a/Year 2/Design and analysis of algorithms/Homeworks/Homework2.pdf
+++ b/Year 2/Design and analysis of algorithms/Homeworks/Homework2.pdf
diff --git a/Year 2/Design and analysis of algorithms/Homeworks/Homework2.tex b/Year 2/Design and analysis of algorithms/Homeworks/Homework2.tex
index 1cb065b..69d7d77 100644
--- a/Year 2/Design and analysis of algorithms/Homeworks/Homework2.tex
+++ b/Year 2/Design and analysis of algorithms/Homeworks/Homework2.tex
@@ -15,6 +15,7 @@
 \usepackage{amsmath}            % Математически символи
 \usepackage{amssymb}
 \usepackage{mathtools}
+\usepackage{stmaryrd}
 \usepackage{amsfonts}           % Още математически символи
 \usepackage{cancel}             % Зачертаване
 \usepackage[dvipsnames]{xcolor} % Цветни кутийки + допълнителни цветове
@@ -105,7 +106,7 @@ Oт ред 11 $j$ става $2$ и при второ достигане на у
 \subsection{Десен фрагмент}
 
 Алгоритъма ще приключи директно ако $n < 2$.
-Иначе разглеждаме останалата част на алгоритъма.
+Иначе се изпълнява останалата част на алгоритъма.
 
 От редове 4 и 7 имаме две еднакви рекурентни извиквания:
 \begin{align}
@@ -123,7 +124,7 @@ Oт ред 11 $j$ става $2$ и при второ достигане на у
 
 \begin{align*}
 	& \text{От (3) и (4): } h(n) = 2 \, h\left( \frac{n}{3} \right) + \left\lfloor \lg n \right\rfloor \\
-	& \text{Тогава за } a = 2, b = 3, f(n) = c \quad \text{За } \varepsilon = \frac{1}{2}, f(n) \preceq \frac{n^{\log_3 2}}{\sqrt{n}}, \log_3 2 - \frac{1}{2} > 0 \xRightarrow[\text{Мастър Теоремата}]{\text{1 случай на}} h(n) \asymp n^{\log_3 2}
+	& \text{Тогава } a = 2, b = 3, f(n) = c \quad \text{За } \varepsilon = \frac{1}{2}, f(n) \preceq \frac{n^{\log_3 2}}{\sqrt{n}}, \log_3 2 - \frac{1}{2} > 0 \xRightarrow[\text{Мастър Теоремата}]{\text{1 случай на}} h(n) \asymp n^{\log_3 2}
 \end{align*}
 
 \section{Решение}
@@ -134,12 +135,13 @@ Oт ред 11 $j$ става $2$ и при второ достигане на у
 
 \subsection{Алгоритъм}
 
+От условието, нека векторите (масивите) \texttt{invvec} и \texttt{result} да се индексират от 1 до n, където $\texttt{invvec.size()} = n$ и на ред 2, \texttt{result} се създава със същия размер като \texttt{invvec}:
 \begin{lstlisting}
 vector<int> rebuild(vector<int> invvec) {
-	vector<int> result;
-	for (int i = 0; i < result.size(); i++)
-		result[i] = i + 1;
-	for (int i = invvec.size() - 1; i >= 0; i--) {
+	vector<int> result(invvec.size());
+	for (int i = 1; i <= result.size(); i++)
+		result[i] = i;
+	for (int i = invvec.size(); i >= 1; i--) {
 		for (int j = i; invvec[i] > 0; j++) {
 			swap(result[j], result[j+1]);
 			invvec[i]--;
@@ -150,72 +152,115 @@ vector<int> rebuild(vector<int> invvec) {
 \end{lstlisting}
 
 От дефинициите, инверсният вектор съдържа броя инверсии за всяко $j$ от $1$ до $n$.
-Алгоритъмът \texttt{rebuild} използва сортиран вектор (масив) в който създава инверсиите от исканата пермутация.
-Инверсния вектор се итерира в обратен ред
+Алгоритъмът \texttt{rebuild} създава сортирания вектор \texttt{result} на редове 2-4 и след това в цикъла на редове 5-10 в \texttt{result} се добавят инверсиите, определени от \texttt{invvec}.
+Инверсния вектор се итерира в обратен ред TODO
 
-Нека $f(n)$ да бъде функция по големина на входа, която определя сложността по време на \texttt{rebuild}.
-Циклите с условия на редове 3 и 5 ще се изпълнят $n$ на брой пъти (поотделно).
-За всяка итерация на цикъла с условие на ред 5, вътрешния цикъл с условие на ред 6 ще се изпълни, в най-лошия случай, точно $n - i - 1$ на брой пъти, колкото е максималния брой елементи, по-големи от $i$-тия (от числото $i+1$).
-Тоест:
+\hfill
+
+Цикъла на редове 3-4 се движи от \texttt{i = 1} до \texttt{i = n}, като в него се извършват единствено константни операции, тоест сложността му по време е $\Theta(n)$.
+
+Цикъла на редове 5-10 се движи от \texttt{i = n} до \texttt{i = 1}, като за всяка негова итерация се изпълнява цикъла на редове 5-9.
+Цикъла на редове 5-9 се движи \texttt{invvec[i]} на брой пъти, като в него се извършват единствено константни операции.
+Максималният брой инверсии за дадено $i$ е $n - i$ (колкото числа от $1$ до $n$ са по-големи от $i$).
+
+Тоест, цикъла на редове 5-10 ще се изпълнява най-много:
 \begin{align*}
-	f(n) & = n + \sum_{i = 0}^{n-1} (n - 1 - i) + c = n + \sum_{i = 0}^{n-1} (n - 1) - \sum_{i = 0}^{n-1} i + c = n + (n-1)(n-1) - \frac{(n-1)n}{2} + c \\
-	& = n + n^2 -2n + 1 - \frac{1}{2}n^2 + \frac{1}{2}n + c = \frac{1}{2}n^2 - \frac{1}{2}n + 1 + c
+	\sum_{i=1}^n (n - i) = n^2 - \sum_{i=1}^n i = n^2 - \frac{n(n+1)}{2} = n^2 - \frac{1}{2}n^2 + \frac{1}{2}n = \frac{1}{2}n^2 + \frac{n}{2} \text{ на брой пъти }
 \end{align*}
-
-$f(n) \asymp n^2$
+Което означава, че максималната му сложност по време е $O(n^2)$.
+Следователно, $\texttt{rebuild} = O(n^2)$.
 
 \section{Решение}
 
 \subsection{Алгоритъм}
 
-Понеже масивът е двойно индексиран, ще го наричам матрица.
-Нека преиндексираме входната матрица на алгоритъма: $M[0..(n-1),0..(m-1)]$, и нека $M.n$ връща $n$ и $M.m$ връща $m$.
+От условието, нека входния масив на алгоритъма \texttt{M} да е индексирана по редове от $1$ до $n$ и по колони от $1$ до $m$, където \texttt{M.rows()} връща $n$ и \texttt{M.cols()} връща $m$.
 
 \begin{lstlisting}
-bool isinteresting(matrix<int, int> M) {
-	for (int i = 1; i < M.n; i++) {
-		for (int j = 1; j < M.m; j++) {
+int isinteresting(array<int, int> M) {
+	for (int i = 2; i <= M.rows(); i++) {
+		for (int j = 2; j <= M.cols(); j++) {
 			if (M[i-1, j-1] + M[i, j] > M[i-1,j] + M[i,j-1])
-				return false;
+				return 0;
 		}
 	}
-	return true;
+	return 1;
 }
 \end{lstlisting}
 
-Доказателство за коректност:
+Нека $i \in \{2, ..., n\}, j \in \{2, ..., m\}$.
+\begin{enumerate}
+	\item Ако $M[i-1,j-1] + M[i,j] \leq M[i-1,j] + M[i,j-1]$, и \newline
+	$M[i-1,j-2] + M[i,j-1] \leq M[i-1,j-1] + M[i,j-2]$
+	\begin{align*}
+		\implies M[i-1,j-2] + M[i,j] & \leq (M[i-1,j-1] + M[i,j-2] - M[i,j-1]) \\
+		& \quad + (M[i-1,j] + M[i,j-1] - M[i-1,j-1]) \\
+		& = M[i,j-2] + M[i-1,j]
+	\end{align*}
+	
+	\item Ако $M[i-1,j-1] + M[i,j] \leq M[i-1,j] + M[i,j-1]$, и \newline
+	$M[i-2,j-1] + M[i-1,j] \leq M[i-2,j] + M[i-1,j-1]$
+	\begin{align*}
+		\implies M[i-2,j-1] + M[i,j] & \leq (M[i-2,j] + M[i-1,j-1] - M[i-1,j]) \\
+		& \quad + (M[i-1,j] + M[i,j-1] - M[i-1,j-1]) \\
+		& = M[i-2,j] + M[i,j-1]
+	\end{align*}
+\end{enumerate}
 
-\subsubsection{Лема за вътрешния цикъл}
+\textbf{Твърдение: } Aко $M[i-1,j-1] + M[i,j] \leq M[i-1,j] + M[i,j-1]$ е изпълнено, то
+за всяко $1 \leq p \leq i-1, 1 \leq q \leq j-1$, е изпълнено $M[p,q] + M[i,j] \leq M[p,j] + M[i,q]$.\newline
+\textbf{Доказателство: } Със силна индукция по $i$ и $j$.
 
-По отношение на едно изпълнение на външния цикъл, ефектът на вътрешния цикъл е, че $M[i,0..(m-1)]$ са проверени и не нарушават "интересността" на матрицата.
+\textbf{База: } $i = 2, j = 2$ и $M[1,1] + M[2,2] \leq M[1,2] + M[2,1]$ е изпълнено.
+Разглеждаме $1 \leq p \leq 1, 1 \leq q \leq 1 \implies p = 1, q = 1$, тогава $M[p,q] + M[2,2]$ е винаги изпълнено.
 
-\textbf{Доказателство:} По отношение на едно изпълнение на външния цикъл:
+\textbf{Индукционно предположение: } Допускаме, че за всички стойности до $i$ и $j$ включително твърдението е вярно.
 
-\textbf{Инвариант на вътрешния цикъл:} За всяко изпълнение на ред 3, $M[i,0..(j-1)]$ са проверени и не нарушават интересността.
+\textbf{Индукционна стъпка: } Следните 3 случая са изчерпателни:
 
-\begin{enumerate}[label=\arabic*.]
-	\item \textbf{База: } При първото изпълнение на ред 3, $j = 1$ и $M[i,0]$ запазва интересността, понеже
-	не съществува валидно $q < 0$ и неравенството се свежда до $M[0,0] \leq M[0,0]$.
-	\item \textbf{Поддръжка: } Да допуснем, че твърдението е вярно за някое нефинално достигане на ред 3.
-	
+\begin{enumerate}[label=\arabic*)]
+	\item Разглеждаме $i$ и $j+1$, за които е изпълнено $M[i-1,j] + M[i,j+1] \leq M[i-1,j+1] + M[i,j]$.\newline
+От I., следва че $M[i-1,j-1] + M[i,j+1] \leq M[i-1,j+1] + M[i-1,j-1]$.\newline
+От II., следва че $M[i-2,j] + M[i,j+1] \leq M[i-2,j+1] + M[i,j]$.\newline
+За $M[i-1,j-1]$ и $M[i-2,j]$ твърдението е съответно вярно при $1 \leq p \leq i-2, 1 \leq q \leq j-2$ и $1 \leq p \leq i-3, 1 \leq p \leq j-1$ по ИП.\newline
+Следователно, твърдението е изпълнено за $M[i,j+1]$ при $1 \leq p \leq i-2, 1 \leq q \leq j-1$.
 \end{enumerate}
 
-\subsubsection{Инвариант на външния цикъл}
-
-За всяко достигане на ред 3, подматрицата $M'[0..\min\{n-1, d\}, 0..\min\{m-1, d\}]$ е интересна.
 
 \hfill
 
-Доказателство за сложност по време:
+Външният цикъл "минава" през всеки ред (без първия), а вътрешният през всяка колона (без първата).
+В тялото на вътрешния цикъл, за всеки елемент от масива правим константата проверка, която вече показахме че правилно зачита интересеността на целия масив.
+Следователно алгоритъмът работи коректно.
 
-\subsubsection{Формула}
+В най-лошия случай, условието на ред 4 никога няма да бъде истина, циклите никога няма да спрът действие преждевременно и ще минем през всеки един елемент от масива.
+Следователно има сложност по време $O(n.m)$.
 
-\subsubsection{Доказателство}
 
 \subsection{Доказателство}
 
+Ще допуснем противното, тоест че за интересен масив $M$, $\phi(1) > \phi(2) > \cdots > \phi(n)$.
+Нека да разгледаме произволни $\phi(i), \phi(i+1)$, където $i > n$.
+То тогава:
+\begin{align*}
+	M[i,\phi(i+1)] + M[i+1,\phi(i)] \leq M[i,\phi(i)] + M[i+1,\phi(i+1)]
+\end{align*}
+
+Обаче, $M[i,\phi(i)]$ е най-левия най-малък елемент за ред $i$ в масива $M$ и $\phi(i) \neq \phi(i+1)$, тоест
+$M[i,\phi(i+1)] \nleq M[i,\phi(i)]$.
+Аналогично $M[i+1,\phi(i)] \nleq M[i+1,\phi(i+1)]$.
+
+Следователно, $M$ не интересен масив. $\lightning$
+
 \subsection{Обяснение}
 
-\subsection{Алгоритъм}
+От б), знаем че $\phi(i - 1) \leq \phi(i) \leq \phi(i+1), 1 < i < n, i \in n_o$.
+Тоест, за нечетните редове $i$, ще търсим $\phi(i)$ между стойностите на $\phi$ за съседните (четни) редове.
+Също, за ред $1$, ще търсим между $1$ и $\phi(2)$ (понеже $1 \leq \phi(1) \leq \phi(2)$) и ако $n$ e нечетно, за ред $n$, ще търсим от $\phi(n-1)$ до $m$ (понеже $\phi(n-1) \leq \phi(n) \leq m$).
+
+Общо имаме $\left\lceil \frac{n}{2} \right\rceil$ на брой нечетни реда.
+За всеки нечетен ред търсенето се извършва върху участък с индекси $s,...,k \quad 1 \leq s \leq k \leq m$, като за всяко търсене индексите ще са уникални, освен $s$ и $k$, които може да се препокрият един път (с предходния и следващия).
+Следователно, общо работата за нечетните редове ще бъде най-много $n-1 + m$ (препокривания за всички редове, освен последния който минава през целия ред).
+Тоест, сложността по време на алгоритъма ще бъде $O(n + m)$.
 
 \end{document}
\ No newline at end of file