[DAA/H1] Minor tweaks and fixes to wording

2 files changed, 12 insertions, 12 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 6c3e843..e398cba 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 0f6df85..1d48737 100644
--- a/Year 2/Design and analysis of algorithms/Homeworks/Homework1.tex
+++ b/Year 2/Design and analysis of algorithms/Homeworks/Homework1.tex
@@ -43,7 +43,7 @@
 \title{\vspace{-1.5cm}Домашно №1 по Дизайн и анализ на алгоритми на специалност Компютърни
 науки, 2 поток, летен семестър 2022/2023г.}
 \author{Камен Димитров Младенов, Група 6}
-\date{26 Март 2023}
+\date{27 Март 2023}
 
 \begin{document}
 
@@ -63,8 +63,8 @@
 \begin{align*}
 	T(n) = n^2 T\left(\frac{n}{2}\right)+1 & \geq n^2 . c_1 \left(\frac{n}{2}\right)^{1+\lg \frac{n}{2}} + 1 && \\
 	& = n^2 c_1 \frac{n^{\lg n}}{2^{\lg n}} + 1 & \text{// } & \lg \frac{n}{2} = \lg n - \lg 2 \\
-	& = c_1 n^{1+\lg n} \frac{n}{2^{\lg n}} + 1 & \text{// } & 2^{\lg n} = n \\
-	& = c_1 n^{1+\lg n} + 1 && \\
+	& = c_1 n^{1+\lg n} \frac{n}{2^{\lg n}} + 1 && \\
+	& = c_1 n^{1+\lg n} + 1 & \text{// } & \frac{n}{2^{\lg n}} = \frac{n}{n} = 1 \\
 	& \geq c_1 n^{1+\lg n} \text{ за всеки избор на } c_1 > 0 \text{ и } n_0 > 0 &&
 \end{align*}
 
@@ -77,10 +77,10 @@
 
 И тогава
 \begin{align*}
-	T(n) = n^2 T\left(\frac{n}{2}\right)+1 & \leq n^2 \left( c_2 \left(\frac{n}{2}\right)^{1 + \lg \frac{n}{2}} - 1 \right) + 1 \\
-	& = c_2n^{\lg n + 1} - n^2 + 1 \\
-	& = c_2n^{\lg n + 1} - 1 - n^2 + 2 \\
-	& \leq c_2n^{\lg n + 1} - 1 \text{ за всеки избор на } c_2 > 0 \text{ и } n_0 \geq \sqrt{2}
+	T(n) = n^2 T\left(\frac{n}{2}\right)+1 & \leq n^2 \left( c_2 \left(\frac{n}{2}\right)^{1 + \lg \frac{n}{2}} - 1 \right) + 1 & \\
+	& = c_2n^{\lg n + 1} - n^2 + 1 & \text{// От I.} \\
+	& = c_2n^{\lg n + 1} - 1 - n^2 + 2 & \\
+	& \leq c_2n^{\lg n + 1} - 1 \text{ за всеки избор на } c_2 > 0 \text{ и } n_0 \geq \sqrt{2} &
 \end{align*}
 
 \section{Доказателство}
@@ -97,7 +97,7 @@
 	& = i + 3 \left( \frac{(i-1)i(2(i-1)+1)}{6} + \frac{(i-1)i}{2} \right) = i + 3 \left( \frac{2i^3-2i^2}{6} \right) = i^3
 \end{align*}
 
-\textit{База:} При първото достигане на ред 4, $i = 0$ и променливите $x, y, z$ имат стойностите, зададени на ред 2. В същото време, при инварианта $6(0+1) = 6, 1+3.0.(0+1) = 1, 0^0 = 0$.
+\textit{База:} При първото достигане на ред 4, $i = 0$ и променливите $x, y, z$ имат стойностите, зададени на ред 2. В същото време, при инварианта $x = 6(0+1) = 6, y = 1+3.0.(0+1) = 1, y = \sum_{j=0}^{-1}1 + 3j(j+1) = 0$.
 
 \textit{Поддръжка:} Допускаме, че твърдението е изпълнено за $k$-тото нефинално изпълнение на ред 4 (където $i = k-1$). Разглеждаме следващото достигане на ред 4. $i$ приема стойността $k$. В цикъла, след завършването на текущата итерация:
 \begin{align*}
@@ -129,7 +129,7 @@ $\textsc{SomeAlg}(A, l, h)$ сортира подмасива $A[l..h]$ на $A[
 \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
+	За удобство, обозначаваме $\alpha = A[l..(l+t-1)], \beta = A[(l+t)..(h-t-1)], \gamma = A[(h-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$ и са сортирани.
@@ -137,13 +137,13 @@ $\textsc{SomeAlg}(A, l, h)$ сортира подмасива $A[l..h]$ на $A[
 	Така целия подмасив е вече сортиран.
 \end{enumerate}
 	
-Сложност по време: ако на алгоритъма са му подадени $n$ елемента, в общия случай на редове 2, 3, 4 и 5 той извършва константа работа, докато на редове 6, 7 и 8, общо три пъти извиква себе си с $\frac{2}{3}$ дължината на входа. Тоест, рекурентното уравнение ще бъде:
+Сложност по време: ако на алгоритъма са му подадени $n$ елемента, в общия случай на редове 2, 3, 4 и 5 той извършва работа, която не зависи от входа, тоест константа работа $c$, докато на редове 6, 7 и 8, общо три пъти извиква себе си с $\frac{2}{3}$ дължината на входа. Тоест, рекурентното уравнение ще бъде:
 \begin{align*}
-	T(n) = 3T\left(\frac{2}{3}n\right) + 1
+	T(n) = 3T\left(\frac{2}{3}n\right) + c
 \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}
+	a = 3, b = \frac{3}{2}, f(n) = c \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