feat: initial commit

1 files changed, 205 insertions, 0 deletions

diff --git a/main.tex b/main.tex
new file mode 100644
index 0000000..1c80e91
--- /dev/null
+++ b/main.tex
@@ -0,0 +1,205 @@
+\documentclass[a4paper]{article}
+
+% Imports
+\usepackage{amssymb}
+\usepackage{amsmath}
+\usepackage{multicol}
+\usepackage{ragged2e}
+\usepackage{blindtext}
+\usepackage[english]{babel} %this is the dictionary you will use
+\usepackage{graphicx,mathdots,chemarr,fancyvrb,comment} %some more packages
+\usepackage{tikz} %some more packages
+%the packages from here on will help with creating a graph
+%tikzpicture
+\graphicspath{ {/home/butterdog/Documents/texassets/} }
+\usepackage[many]{tcolorbox}
+\usepackage{wrapfig}
+\usepackage{scalerel}
+\usepackage{pict2e}
+\usepackage{tkz-euclide}
+\usepackage{scalerel}
+\usepackage{pict2e}
+\usepackage{tkz-euclide}
+\usepackage{listings}
+\usepackage{color}
+\usepackage{xifthen}
+\usepackage{hyperref}
+\usepackage{xstring} % for \IfStrEqCase
+
+\newcounter{lemmacount}
+\newcounter{proofcount}
+\definecolor{dkgreen}{rgb}{0,0.6,0}
+%\definecolor{gray}{rgb}{0.5,0.5,0.5}
+\definecolor{red}{HTML}{ffb3b3}
+\definecolor{redbar}{HTML}{ff0000}
+\definecolor{mauve}{rgb}{0.58,0,0.82}
+\definecolor{cyanbar}{HTML}{00bfff}
+\definecolor{cyan}{HTML}{b3f0ff}
+\definecolor{greenbar}{HTML}{00ff00}
+\definecolor{green}{HTML}{8cd98c}
+\definecolor{black}{HTML}{000000}
+\definecolor{main}{HTML}{5989cf}    % setting main color to be used
+\definecolor{sub}{HTML}{cde4ff}     % setting sub color to be used
+\tcbset{
+	sharp corners,
+	colback = white,
+	before skip = 0.2cm,    % add extra space before the box
+	after skip = 0.5cm      % add extra space after the box
+}                           % setting global options for tcolorbox
+\makeatletter
+
+
+%My Custom Commands
+\newcommand{\mnewline}{\newline\newline\newline}
+\newcommand{\mline}{\rule{0.5cm}{0.5pt}}
+\newcommand{\proj}[1]{\text{Proj}_{#1}}
+\newcommand{\st}{\ni:}
+\newcommand{\evaline}[2]{\Big|^{#1}_{#2}}
+\newcommand{\nulli}[1]{\text{Null }{#1}}
+\newcommand{\ran}[1]{\text{ran }{#1}}
+\newcommand{\col}[1]{\text{Col }({#1})}
+\newcommand{\re}[1]{\text{Re}({#1})}
+\newcommand{\im}[1]{\text{Im}({#1})}
+\newcommand{\spa}[1]{\text{span}\{{#1}\}}
+%\newcommand{\neproof}[3]{$\text{Let } \epsilon > {#2} \text{ be given}$\\\text{Choose $N = {#1}$\text{ Suppose $n > N  > {#3}$}}}
+\newcommand{\neproof}[3]{ %The first one is without the 3rd argument and the second one is
+	\ifthenelse{\isempty{#3}}{$\text{Let } \epsilon > {#2} \text{ be given}$\\\text{Choose $N = {#1}$\text{ Suppose $n > N$}}}
+	{$\text{Let } \epsilon > {#2} \text{ be given}$\\\text{Choose $N = {#1}$\text{ Suppose $n > N  > {#3}$}}} 
+}
+\newcommand{\infobox}[2]{\begin{InfoBox}
+		\smash{\raisebox{-5pt}{\includegraphics[width=0.77cm,height=0.68cm]{information}}}{\bf #1}\newline\newline
+		{#2}
+\end{InfoBox}}
+\newcommand{\warningbox}[2]{\begin{WarningBox}
+		\smash{\raisebox{-6pt}{\includegraphics[width=0.70cm,height=0.70cm]{warning}}}
+		{\bf #1}\newline\newline
+		{#2}
+\end{WarningBox}}
+\newcommand{\theorybox}[2]{\begin{TheoryBox}
+		\smash{\raisebox{-6pt}{\includegraphics[width=0.70cm,height=0.70cm]{theorem}}}
+		{\bf #1}\newline\newline
+		{#2}
+\end{TheoryBox}}
+\newcommand{\notebox}[2]{\begin{NoteBox}
+		\smash{\raisebox{-6pt}{\includegraphics[width=0.55cm,height=0.70cm]{reminder}}}
+		{\bf #1}\newline\newline
+		{#2}
+\end{NoteBox}}
+\newcommand{\proofbox}[3]{%
+  \IfStrEqCase{#1}{%
+    {lemma}{\stepcounter{lemmacount}\def\proofboxlabel{Lemma \thelemmacount}}%
+    {proof}{\stepcounter{proofcount}\def\proofboxlabel{Proof \theproofcount}}%
+  }[\PackageError{proofbox}{Unknown proofbox type '#1'}{Use 'lemma' or 'proof'}]%
+  \begin{ProofBox}
+    \IfStrEq{#2}{}%
+      {{\bf \proofboxlabel:}}%
+      {{\bf \proofboxlabel\ (#2):}}%
+    \newline\newline
+    {#3}
+  \end{ProofBox}
+}
+\renewcommand*\env@matrix[1][*\c@MaxMatrixCols c]{%
+	\hskip -\arraycolsep
+	\let\@ifnextchar\new@ifnextchar
+	\array{#1}}
+\newtcolorbox{InfoBox}{
+	colback = sub, 
+	colframe = main, 
+	boxrule = 0pt, 
+	leftrule = 6pt % left rule weight
+}
+\newtcolorbox{WarningBox}{
+	colback = red, 
+	colframe = redbar, 
+	boxrule = 0pt, 
+	leftrule = 6pt % left rule weight
+}
+\newtcolorbox{TheoryBox}{
+	colback = cyan, 
+	colframe = cyanbar, 
+	boxrule = 0pt, 
+	leftrule = 6pt % left rule weight
+}
+\newtcolorbox{NoteBox}{
+	colback = green, 
+	colframe = greenbar, 
+	boxrule = 0pt, 
+	leftrule = 6pt % left rule weight
+}
+\newtcolorbox{TitleBox}{
+	boxrule = 2pt,
+	rounded corners
+}
+\newtcolorbox{ProofBox}{
+	boxrule = 1.3pt,
+}
+\makeatother
+\usepackage[letterpaper,left=6mm,includemp=true,marginparwidth=12mm,marginparsep=1mm,reversemarginpar,right=19mm,
+includefoot=true,top=19mm,nohead,footskip=12mm,bottom=6mm]{geometry}
+% Here are the custom commands I have created. They are increadibly retarded
+% mnewline: creates 3 newlines
+% mline: Creates a horizontal line
+% proj: Creates a Proj with a suitable subscript - Takes an argument
+% st: creates a ni and a : as the 'such that'
+% evaline: creates a vertical line for evaluated definite integrals. First argument is upper limit, second is lower. - Takes two arguments
+% nulli: creates a Null (with a whitespace) - Takes an argument
+% col: creates a Col (with a whitespace) - Takes an argument
+% ran: creates a ran (with a whitespace) - Takes an argument
+% re: creates a Re() - Takes an argument
+% im: creates a Im() - Takes an argument
+% sp: creates a span{} - Takes an argument
+% neproof: Creates a cookie cutter N-epsilon proof. First argument set's N's value and second argument sets epsilon greater than value and the third (optional) argument sets the n > N > value. IF YOU DO NOT WANT THE THIRD ARGUMENT YOU NEED AN EMPTY CURLY BRACKET
+\begin{document}
+	\setlength{\parindent}{1cm}
+	\begin{center}
+		{\bf \Large CSCC73}
+	\end{center}
+	\begin{TitleBox}
+		\begin{center}
+			\section{\bf Greedy Algorithms}
+		\end{center}
+	\end{TitleBox}
+	\theorybox{Definition -- Optimization Problem}{An optimization problem is one where we want to find the min or max of a given objective function subject to constraints. The min/max is called the {\bf optimal solution}. Note that there often can be multiple.}
+	\theorybox{Definition -- Greedy Algorithm}{A greedy algorithm is one that builds up the solution in stages, iteratively working on the previous stage's partial solution by judging what is going to likely lead to a more correct next solution.\\
+	A greedy algorithm is what we say is {\bf greedy} and {\bf irrevocable}. Greedy referring to how the above process is very myopic and doesn't look past the immediate next stage, and irrevocable means that we do not backtrace, what is done is done.}
+	Greedy algorithms are commonly used to solve optimization problems. However, greedy is not always possible. A greedy algorithm is definietly not guaranteed to work, but when it does, it can be very fast because of the greedy and irrevocable properties of the algorithm.\\\\
+	\subsection{Example Optimization Problem applying a Greedy Algorithm}
+	\theorybox{Definition -- Interval Scheduling}{An Interval Scheduling problem is one where we have $n$ jobs, each has a start time defined by $s(j_n)$ and an end time defined by $f(j_n)$ with $s(j_n) \le f(j_n)$ . The problem is a maximizing problem. What is the largest set of non-conflicting jobs can we have? A set that satisfies this condition is called a {\bf feasible set}.}
+	\theorybox{Definition -- Job Time Interval}{A job time interval for a job $j_i$ is defined as $\Big[s(j_i), f(j)\Big)$}
+	\theorybox{Definition -- Conflicting Job}{A conflicting job is one where the interval of one job overlaps with another.}
+	An example of an interval scheduling issue is the lecture hall. We have $n$ lectures that we want to schedule with varying durations, start times and end times. So to make the most of the lecture hall, how can we best schedule each lecture to maximize the number of lectures that happen on a given day?.
+	\warningbox{Max Cardinality}{We are looking for the largest possible set of non-conflicting issues. This means that the set cannot be extended. However, being non-extendible does NOT mean that we have the largest set. Its only a one way implication. It is easy to imagine how.}
+	Given our pseudocode for a scheduler, we will always get a set that is non-extendible. But how do we know if it is the largest? Well the thing is that we do not always get the largest. So how can we modify the algorithm to ensure this? One trick that we can pull is sorting our data beforehand. But how should we do this?
+	\subsubsection{Sort jobs by earliest start time}
+	So what if we sort jobs, in ascending order, by their start time? This is easily disproved as a bad idea. Imagine we have one mega long job, and we have a bunch of mini jobs, where none start before the mega long job.
+	\subsubsection{Sort jobs by shortest job interval}
+	This is also easily disproved as a bad idea. To find a counter example, just take two long jobs that do not conflict, then put a shorter job that conflicts with both.
+	\subsubsection{Sort jobs by smallest number of job interval conflicts}
+	This one is also not optimal. It requires a slightly more complex counter example.\\
+	Note that this option is also dependent on the order we pick. The counter example chosen illustrates this.
+	\subsubsection{Sort jobs by finish time}
+	This option will be guaranteed to produce an optimal outcome.\\
+	\subsection{Proving that sorting by finish time is optimal}
+	There are two approaches to this proof. Either we can use the ``promising set'' method or the ``greedy always ahead'' method. Note that both of these proofs prove some kind of loop invariant. It is then up to us to show that the partial solution is indeed correct, and then show that our loop ends.
+	\theorybox{Theory -- Promising Set Greedy Algorithm Proof}{The promising set proof method for a greedy algorithm is one where you aim to show that the partial solution (and ultimately the solution generated by the last stage) are all subsets of an optimal solution. This should be proved via induction.}
+	\theorybox{Theory -- Greedy Always Ahead Algorithm Proof}{The Greedy Always Ahead Algorithm proof involves trying to show that the algorithm is always ``doing the right thing ''. This should be proved via induction.}
+	\theorybox{Information -- Soft by Finish Time INTSCHED}{Pseudocode:\\
+	Running Time:\\
+	If we pick a competent sorting algorithm, we can finish the sort in $\mathcal{O}(n\log n) + \mathcal{O}(n) = \mathcal{O}(n\log n)$}
+	\subsubsection{Promising Proof}
+	\proofbox{lemma}{bruh}
+	We say ``promising'', because here, we want to prove that every partial answer is a subset of an optimal answer. First we will need the promising set lemma, which goes as follows:\\
+	Lemma: Promising set $\forall\text{ iter } t\exists \text{ opti set } A^*_t \st A_T \subseteq A^*_t$\\
+	In regular English, this means for each iteration $t$, it's partial solution is a subset of an optimal solution.\\
+	We will prove this via induction.\\
+	Base case: Empty set. This is trivial, the empty set is a subset of all sets.\\
+	Induction set: Assume $A_t \subseteq A_t^*$, we will show that $A_{t+1} \subseteq A^*_{t+1}$\\\\
+	We will break $t+1$ into two cases. First, what if $j_{t+1}$ is in conflict with another job? In which case we just say that $A_{t+1} = A_t$ and we are done.\\
+	Next we will consider if we have to include $j_{t+1}$. In this case we will break it down further into two sub cases. First, what if $j_{t+1}$ IS part of $A_t^*$? Then in this case $A^*_t = A^*_t$.\\
+	If $j_{t+1} \not\in A^*_t$ is a bit more complex. This means that $j_{t+1}$ is in conflict with some job in $A_t^*$. If that is the case then we want to show that $j_{t+1}$ is ONLY in conflict with one job in the $A_t^*$. If it is, then we can swap it out. Otherwise we are in some deep shit. So lets consider, what if there is more than one conflict? Well then that goes against our entire premise since we have the set of jobs sorted by earliest finish time. This would mean that the first job that $j_{t+1}$ is in conflict with would actually have been considered BEFORE $j_{t+1}$, and we wouldn't have this situation to begin with. As such this case is invalid. So that means $j_{t+1}$ is only in conflict with one job called $j'$. And as such we toss out $j'$ and say: $A^*_{t+1} = \big(A^*_t - \{j'\}\big)\cup \{j_{t+1}\}$ and $A_t \cup \{j_{t+1}\} \subseteq A_{t+1}^* = A_{t+1}$. $\square$\\\\
+	\subsubsection{Greedy-Always-Ahead Proof}
+	For this method, we will change our invariant to the following:\\
+	Lemma: $\forall i \in [1,\ldots,k], f(j_i) \leq f(j_i^*)$\\
+	Proof:\\
+	Base case: Trivial.
+\end{document}