[DAA/H2] Solved 1st exercise and sketched out the other two

2 files changed, 221 insertions, 0 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
new file mode 100644
index 0000000..170f0e2
--- /dev/null
+++ 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
new file mode 100644
index 0000000..1cb065b
--- /dev/null
+++ b/Year 2/Design and analysis of algorithms/Homeworks/Homework2.tex
@@ -0,0 +1,221 @@
+% Document MUST be built with XeLaTeX!
+\documentclass[11pt,a4paper]{article}
+
+\usepackage[margin=1.5cm]{geometry}
+
+% Поддръжка на български език
+% Thanks to https://tex.stackexchange.com/a/136926
+\usepackage{fontspec}
+\defaultfontfeatures{Ligatures=TeX}
+\setmainfont{CMU Serif}
+\setsansfont{CMU Sans Serif}
+
+\usepackage[bulgarian,english]{babel}
+
+\usepackage{amsmath}            % Математически символи
+\usepackage{amssymb}
+\usepackage{mathtools}
+\usepackage{amsfonts}           % Още математически символи
+\usepackage{cancel}             % Зачертаване
+\usepackage[dvipsnames]{xcolor} % Цветни кутийки + допълнителни цветове
+\usepackage{indentfirst}        % Индентация на параграф след секция
+\usepackage{color}
+
+\usepackage{listings}           % Въведение на код
+\lstset{
+	language=C++,
+	numbers=left,
+	mathescape=true,
+	basicstyle=\ttfamily,
+	tabsize=4
+}
+
+\usepackage{enumitem}
+\setlist[enumerate]{label=\arabic*.}
+
+\renewcommand{\thesection}{Задача \arabic{section}.}
+\renewcommand{\thesubsection}{\alph{subsection})}
+\renewcommand{\thesubsubsection}{$\cdot$}
+	% Мерси https://tex.stackexchange.com/a/184755
+\makeatletter
+\renewcommand*{\@alph}[1]{%
+  \ifcase#1\or а\or б\or в\or г\or
+    д\or е\or ж\or з\or и\or й\or к\or
+    л\or м\or н\or о\or п\or р\or с\or т\or у\or
+    ф\or х\or ц\or ч\or ш\or щ\or ъ\or ю\or я\or
+    \else\@ctrerr\fi
+}
+\makeatother
+
+\let\oldforall\forall
+\renewcommand{\forall}{\; \oldforall}
+
+\let\oldexist\exists
+\renewcommand{\exists}{\; \oldexist}
+
+\setlist[enumerate]{label=\Roman*.}
+
+\usepackage[pdfauthor={Камен Димитров Младенов, КН Летен семестър, 2023},
+		    pdftitle={Домашна работа 2 по ДАА},
+		    pdfsubject={},
+		    pdfkeywords={},
+		    colorlinks=true,
+		    urlcolor=blue]{hyperref}
+
+\title{\vspace{-1.5cm}Домашно №2 по ДАА на Компютърни Науки}
+\author{Камен Димитров Младенов, Група 6}
+\date{9 Април 2023}
+
+\begin{document}
+
+\maketitle
+
+\section{Решение}
+
+\subsection{Ляв фрагмент}
+
+Цикъла ще извърши точно $m . n = n . n . n = n^3$ итерации.
+Тоест за $c > 0, f(n) = n^3 + c \asymp n^3$ по дефиниция.
+
+\subsection{Централен фрагмент}
+
+Алгориътма ще приключи директно ако $n < 10$. Иначе се изпълнява останалата част на алгоритъма.
+
+Условието на цикъла на ред 4 никога няма да е вярно, понеже $6 \ngtr 8$.
+
+Тялото на цикъла с условие на ред 7 ще се изпълни точно един път: при първо достигане на условието $n - j = n - 6 \geq 10 - 6 = 4 > 1$, на ред 8 $j$ става $n$ и на второто достигане на условието $n - j = n - n = 0 \ngtr 1$.
+От това единствено изпълнение имаме рекурентно извикване:
+\begin{align}
+	g(n-1) + g(n-2)
+\end{align}
+
+Тялото на цикъла с условие на ред 10 ще се изпълни точно един път: към момента $j = n$ и при първо достигане на условието, $n \geq n$.
+Oт ред 11 $j$ става $2$ и при второ достигане на условието, $2 = j \ngeq n$ понеже $n \geq 10$.
+От това единствено изпълнение	 имаме рекурентно извикване:
+\begin{align}
+	g(n-j) = g(n-2)
+\end{align}
+
+\begin{align*}
+	& \text{От (1) и (2): } g(n) = g(n-1) + 2g(n-2) + c \\
+	& \text{Характеристично уравнение: } x^n = x^{n-1} + 2x^{n-2} \quad x^2 - x - 2 = 0 \quad \text{с корени } \{-1, 2\}_M \\
+	& \text{Нехомогенната част е константа и няма корени.} \quad g(n) = c_1 (-1)^n + c_2 2^n \implies g(n) \asymp 2^n
+\end{align*}
+
+\subsection{Десен фрагмент}
+
+Алгоритъма ще приключи директно ако $n < 2$.
+Иначе разглеждаме останалата част на алгоритъма.
+
+От редове 4 и 7 имаме две еднакви рекурентни извиквания:
+\begin{align}
+	h\left( \frac{n}{3} \right)
+\end{align}
+
+Ще покажем, че тялото на цикъла с условие на ред 5 ще се изпълни точно 
+\begin{align}
+	\left\lfloor \lg n \right\rfloor \text{ на брой пъти.}
+\end{align}
+Ако допуснем, че $n = 2^k$ за някое $k \in \mathbb{N}$, то тогава $i$ последователно ще придобие стойностите $2^1, 2^2, ..., 2^k$, тоест цикъла ще се изпълни $k = \log_2 n \in \mathbb{N}$ на брой пъти.
+\newline
+Ако $n \neq 2^k$ за което и да е $k \in \mathbb{N}$, то тогава съществува $k' \in \mathbb{N}$, такова че $2^{k'} < n < 2^{k' + 1}$ и тогава $i$ придобива стойностите $2^1, 2^2, ..., 2^{k'}$. 
+Понеже $k' < \lg n < k' + 1$, то цикъла ще се изпълни $k' = \left\lfloor \lg n \right\rfloor \in \mathbb{N}$ на брой пъти.
+
+\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}
+\end{align*}
+
+\section{Решение}
+
+\subsection{Инверсен вектор}
+
+Инверсния вектор е $(4, 1, 1, 0, 2, 3, 0, 0, 0)$
+
+\subsection{Алгоритъм}
+
+\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--) {
+		for (int j = i; invvec[i] > 0; j++) {
+			swap(result[j], result[j+1]);
+			invvec[i]--;
+		}
+	}
+	return result;
+}
+\end{lstlisting}
+
+От дефинициите, инверсният вектор съдържа броя инверсии за всяко $j$ от $1$ до $n$.
+Алгоритъмът \texttt{rebuild} използва сортиран вектор (масив) в който създава инверсиите от исканата пермутация.
+Инверсния вектор се итерира в обратен ред
+
+Нека $f(n)$ да бъде функция по големина на входа, която определя сложността по време на \texttt{rebuild}.
+Циклите с условия на редове 3 и 5 ще се изпълнят $n$ на брой пъти (поотделно).
+За всяка итерация на цикъла с условие на ред 5, вътрешния цикъл с условие на ред 6 ще се изпълни, в най-лошия случай, точно $n - i - 1$ на брой пъти, колкото е максималния брой елементи, по-големи от $i$-тия (от числото $i+1$).
+Тоест:
+\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
+\end{align*}
+
+$f(n) \asymp n^2$
+
+\section{Решение}
+
+\subsection{Алгоритъм}
+
+Понеже масивът е двойно индексиран, ще го наричам матрица.
+Нека преиндексираме входната матрица на алгоритъма: $M[0..(n-1),0..(m-1)]$, и нека $M.n$ връща $n$ и $M.m$ връща $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++) {
+			if (M[i-1, j-1] + M[i, j] > M[i-1,j] + M[i,j-1])
+				return false;
+		}
+	}
+	return true;
+}
+\end{lstlisting}
+
+Доказателство за коректност:
+
+\subsubsection{Лема за вътрешния цикъл}
+
+По отношение на едно изпълнение на външния цикъл, ефектът на вътрешния цикъл е, че $M[i,0..(m-1)]$ са проверени и не нарушават "интересността" на матрицата.
+
+\textbf{Доказателство:} По отношение на едно изпълнение на външния цикъл:
+
+\textbf{Инвариант на вътрешния цикъл:} За всяко изпълнение на ред 3, $M[i,0..(j-1)]$ са проверени и не нарушават интересността.
+
+\begin{enumerate}[label=\arabic*.]
+	\item \textbf{База: } При първото изпълнение на ред 3, $j = 1$ и $M[i,0]$ запазва интересността, понеже
+	не съществува валидно $q < 0$ и неравенството се свежда до $M[0,0] \leq M[0,0]$.
+	\item \textbf{Поддръжка: } Да допуснем, че твърдението е вярно за някое нефинално достигане на ред 3.
+	
+\end{enumerate}
+
+\subsubsection{Инвариант на външния цикъл}
+
+За всяко достигане на ред 3, подматрицата $M'[0..\min\{n-1, d\}, 0..\min\{m-1, d\}]$ е интересна.
+
+\hfill
+
+Доказателство за сложност по време:
+
+\subsubsection{Формула}
+
+\subsubsection{Доказателство}
+
+\subsection{Доказателство}
+
+\subsection{Обяснение}
+
+\subsection{Алгоритъм}
+
+\end{document}
\ No newline at end of file