[DAA/H1] Solved third exercise

2 files changed, 37 insertions, 1 deletions

diff --git a/Year 2/Design and analysis of algorithms/Homeworks/Homework1.pdf b/Year 2/Design and analysis of algorithms/Homeworks/Homework1.pdf
index eb73c12..6c3e843 100644
--- a/Year 2/Design and analysis of algorithms/Homeworks/Homework1.pdf
+++ b/Year 2/Design and analysis of algorithms/Homeworks/Homework1.pdf
diff --git a/Year 2/Design and analysis of algorithms/Homeworks/Homework1.tex b/Year 2/Design and analysis of algorithms/Homeworks/Homework1.tex
index a4f6581..0f6df85 100644
--- a/Year 2/Design and analysis of algorithms/Homeworks/Homework1.tex
+++ b/Year 2/Design and analysis of algorithms/Homeworks/Homework1.tex
@@ -31,6 +31,8 @@
 \let\oldexist\exists
 \renewcommand{\exists}{\; \oldexist}
 
+\setlist[enumerate]{label=\Roman*.}
+
 \usepackage[pdfauthor={Камен Димитров Младенов, КН Летен семестър, 2023},
 		    pdftitle={Домашна работа 1 по ДАА},
 		    pdfsubject={},
@@ -108,6 +110,40 @@
 
 \textit{Терминация:} От условието на ред 4, цикъла ще завърши при $(a+1)$-ото изпълнение, когато $i = a$. То тогава, от инварианта, върнатата стойност на ред 10 ще бъде точно $z = a^3$.
 
-\section{Доказателство}
+\section{Решение}
+
+$\textsc{SomeAlg}(A, l, h)$ сортира подмасива $A[l..h]$ на $A[1..n]$. Тоест, $\textsc{SomeAlg}(A, 1, n)$ ще сортира целия масив.
+
+\hfill
+
+Ще докажем коректността на алгоритъма с индукция по $h-l$ (което се явява дължината на нашия подмасив минус едно).
 
+\textit{База:} $h-l <= 0$. В този случай, подмасивът или има само един елемент или е празен. И в двете ситуации, подмасивът е сортиран. Условието на ред 1 спира изпълнението на алгоритъма, без да е променил подмасива.
+
+\textit{Индукционно предположение:} Допускаме, че за някои $l', h'$, $\textsc{SomeAlg}(A, l'', h'')$ сортира подмасива $A[l''..h'']$ за всички $l'' \leq l', h'' \leq h'$.
+
+\textit{Индукционна стъпка:} Разглеждаме $h - l > h' - l'$.
+Редове 2 и 3 "сортират" първия и последния елемент в подмасива $A[l..h]$ помежду си.
+На ред 4, $t$ става една трета от дължината на подмасива, закръглена надолу.
+Разглеждаме два случая относно условието на ред 5:
+\begin{enumerate}
+	\item Ако $t = 0$, то дължината на подмасива може да бъде само 2. Тогава двата елемента ще бъдат двата "крайни" елемента и от редове 2 и 3, подмасивът ще бъде сортиран.
+	\item Иначе, ако подмасивът има повече от 2 елемента. \newline
+	За удобство, обозначаваме $\alpha = A[l..t-1], \beta = A[t..l+t-1], \gamma = A[l+t..h]$ (всяка съседна трета от масива) и нека $\Gamma$ да бъдат най-големите $(h-l)/3$ елемента (елементите които ще бъдат в $\gamma$ след сортиране). От индукционно предположение, можем да сортираме всяка трета поотделно, както и съседни трети ($\alpha\beta, \beta\gamma$).\newline
+	В подмасива, елементите от $\Gamma$ ще се съдържат в $\alpha, \beta$ и/или $\gamma$.
+	На ред 6 сортираме $\alpha\beta$, което означава че всички елементи от $\Gamma$, които са били в $\alpha\beta$, сега се съдържат само в $\beta$.
+	На ред 7 сортираме $\beta\gamma$, което означава че всички елементи от $\Gamma$ се намират в $\gamma$ и са сортирани.
+	На ред 8 сортираме всички останали елементи, които са в $\alpha\beta$ (и са по-малки от тези в $\gamma$). \newline
+	Така целия подмасив е вече сортиран.
+\end{enumerate}
+	
+Сложност по време: ако на алгоритъма са му подадени $n$ елемента, в общия случай на редове 2, 3, 4 и 5 той извършва константа работа, докато на редове 6, 7 и 8, общо три пъти извиква себе си с $\frac{2}{3}$ дължината на входа. Тоест, рекурентното уравнение ще бъде:
+\begin{align*}
+	T(n) = 3T\left(\frac{2}{3}n\right) + 1
+\end{align*}
+От 1ви случай на мастър теоремата:
+\begin{align*}
+	a = 3, b = \frac{3}{2}, f(n) = 1 \preceq \frac{n^{\log_\frac{3}{2} 3}}{n^\varepsilon} \implies T(n) \asymp n^{\log_\frac{3}{2} 3}
+\end{align*}
+	
 \end{document}
\ No newline at end of file