[DAA/H1] Solved first exercise

2 files changed, 88 insertions, 0 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
new file mode 100644
index 0000000..3ab5c11
--- /dev/null
+++ 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
new file mode 100644
index 0000000..3164a75
--- /dev/null
+++ b/Year 2/Design and analysis of algorithms/Homeworks/Homework1.tex
@@ -0,0 +1,88 @@
+% 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}
+\DeclareMathOperator{\cotg}{cotg} \DeclareMathOperator{\arccotg}{arccotg}
+\usepackage{amsfonts}           % Още математически символи
+\usepackage{cancel}             % Зачертаване
+\usepackage[dvipsnames]{xcolor} % Цветни кутийки + допълнителни цветове
+\usepackage{indentfirst}        % Индентация на параграф след секция
+
+\usepackage{enumitem}
+\setlist[enumerate]{label=\arabic*.}
+
+\renewcommand{\thesection}{Задача \arabic{section}.}
+
+\let\oldforall\forall
+\renewcommand{\forall}{\; \oldforall}
+
+\let\oldexist\exists
+\renewcommand{\exists}{\; \oldexist}
+
+\usepackage[pdfauthor={Камен Димитров Младенов, КН Летен семестър, 2023},
+		    pdftitle={Домашна работа 1 по ДАА},
+		    pdfsubject={},
+		    pdfkeywords={},
+		    colorlinks=true,
+		    urlcolor=blue]{hyperref}
+
+\title{\vspace{-1.5cm}Домашно №1 по Дизайн и анализ на алгоритми на специалност Компютърни
+науки, 2 поток, летен семестър 2022/2023г.}
+\author{Камен Димитров Младенов, Група 6}
+\date{26 Март 2023}
+
+\begin{document}
+
+\maketitle
+
+\section{Доказателство}
+
+\textbf{I.} Ще докажем, че $n^{1 + \lg n} \preceq T(n)$ с индукция по n.
+По дефиниция, това е същото като да докажем, че съществува положителна константа $c_1$ и положително $n_0$, такова че за всяко $n \geq n_0$, $T(n) \geq c_1 n^{1+\lg n}$.
+
+Индуктивното предположение е, че
+\begin{align*}
+	T\left(\frac{n}{2}\right) \geq c_1 \left(\frac{n}{2}\right)^{1+\lg \frac{n}{2}}
+\end{align*}
+
+Тогава
+\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 && \\
+	& \geq c_1 n^{1+\lg n} \text{ за всеки избор на } c_1 > 0 \text{ и } n_0 > 0 &&
+\end{align*}
+
+\textbf{II.} Ще засилим твърдението и ще докажем, че $T(n) \preceq n^{1+\lg n} - 1$ с индукция по n, тоест че $\exists c_2 > 0 \exists n_0 > 0 \forall n \geq n_0 : T(n) \leq c_2 n^{1 + \lg n} - 1$
+
+Индуктивното предположение е, че
+\begin{align*}
+	T\left(\frac{n}{2}\right) \leq c_2 \left(\frac{n}{2}\right)^{1 + \lg \frac{n}{2}} - 1
+\end{align*}
+
+И тогава
+\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}
+\end{align*}
+
+\section{Доказателство}
+
+\section{Доказателство}
+
+\end{document}
\ No newline at end of file