Algorithms.tex

%%%%%%%%%%%%%%% LaTeX Compiler: XeLaTeX %%%%%%%%%%%%%%%

% License for LaTeX Configuration File

% This LaTeX configuration file is created by Lin, Xuanyu, HKUST, and is provided under the terms of the MIT License. You are free to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of this configuration file, subject to the following conditions:

% 1. The above copyright notice and this license notice shall be included in all copies or substantial portions of the configuration file.

% 2. The configuration file is provided "as is", without warranty of any kind, express or implied, including but not limited to the warranties of merchantability, fitness for a particular purpose and noninfringement. In no event shall the authors or copyright holders be liable for any claim, damages or other liability, whether in an action of contract, tort or otherwise, arising from, out of or in connection with the configuration file or the use or other dealings in the configuration file.

% By using this configuration file, you agree to the terms and conditions of this license. If you do not agree to these terms and conditions, you must not use the configuration file.

\documentclass[10pt]{article}
% Text setting
% \usepackage{newtxtext}
\usepackage{setspace}
\usepackage[dvipsnames,svgnames]{xcolor}
\usepackage{comment}
% Chinese characters setup
\usepackage{fontspec}
\usepackage{xeCJK}
\setCJKmainfont{SimSun}
% Dealing with special characters
\usepackage[utf8]{inputenc}
% \usepackage[T1]{fontenc} % Conflict with fontspec & xeCJK
\usepackage{pifont}
% Mathematical formula typesetting
\usepackage{unicode-math}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{mathrsfs}
\setmathfont{Latin Modern Math}
% \usepackage{amssymb} % Contained in package unicode-math
% Jump (Math) \llbracket & \rrbracket
\usepackage{stmaryrd}
% Chemical formulas and equations
\usepackage[version=4]{mhchem}
% Graphics
\usepackage{graphicx}
\graphicspath{ {./images/} }
\usepackage[export]{adjustbox}
% Tables, enumeration
\usepackage{multirow}
\usepackage{caption}
\usepackage{subcaption}
\usepackage{enumitem}
% Adjust the position
\usepackage{float}
% Frames, reference
\usepackage{framed}
\usepackage[strict]{changepage}
\usepackage{hyperref}
\hypersetup{
	colorlinks=true,
	linkcolor=black,
	filecolor=magenta,      
	urlcolor=blue,
}
% Page & paragraph settings
\usepackage{fancyhdr}
\usepackage{geometry}
\geometry{left=1.5cm, right=1.5cm, top=2cm, bottom=2cm}
\usepackage{indentfirst}
\setlength{\parindent}{2em}
\setlength{\parskip}{0em}
% Algorithm & coding environment
\usepackage[ruled,vlined]{algorithm2e}
\usepackage[framemethod=TikZ]{mdframed}
\usepackage{listings}
\usepackage{wrapfig}
\usepackage{booktabs}
\usepackage{makecell}
% New command
\newcommand\course{COMP 3711}  
\newcommand\coursetitle{Design and Analysis of Algorithms}
\newcommand\semester{Fall 2023}
\renewcommand{\labelenumi}{\alph{enumi}}
\newcommand{\Z}{\mathbb Z}
\newcommand{\R}{\mathbb R}
\newcommand{\Q}{\mathbb Q}
\newcommand{\NN}{\mathbb N}
\newcommand{\dd}{\mathrm{d}}
\DeclareMathOperator{\Mod}{Mod}
\renewcommand\lstlistingname{Algorithm}
\renewcommand\lstlistlistingname{Algorithms}
\def\lstlistingautorefname{Alg.}
\newtheorem*{theorem}{Theorem}
\newtheorem*{lemma}{Lemma}

%%%%%%%%%%%%%%% Page Setup %%%%%%%%%%%%%%%

\pagestyle{fancy}
\headheight 35pt
\lhead{\course\ \coursetitle\ \semester}
\rhead{\includegraphics[width=2.5cm]{logo-hkust.png}}
\lfoot{}
\pagenumbering{arabic}
\cfoot{}
\rfoot{\small\thepage}
\headsep 1.2em

%%%%%%%%%%%%%%% Boxframe Setup %%%%%%%%%%%%%%%

\definecolor{blueshade}{rgb}{0.95,0.95,1} % Horizontal Line: DarkBlue
\definecolor{greenshade}{rgb}{0.90,0.99,0.91} % Horizontal Line: Green
\definecolor{redshade}{rgb}{1.00,0.90,0.90}% Horizontal Line: LightCoral
\definecolor{brownshade}{rgb}{0.99,0.97,0.93} % Horizontal Line: BurlyWood

\newenvironment{formal}[2]{%
	\def\FrameCommand{%
		\hspace{1pt}%
		{\color{#1}\vrule width 2pt}%
		{\color{#2}\vrule width 4pt}%
		\colorbox{#2}%
	}%
	\MakeFramed{\advance\hsize-\width\FrameRestore}%
	\noindent\hspace{-4.55pt}% Disable indenting first paragraph
	\begin{adjustwidth}{}{7pt}%
		\vspace{2pt}\vspace{2pt}%
	}
	{%
		\vspace{2pt}\end{adjustwidth}\endMakeFramed%
}

%%%%%%%%%%%%%%% Problem Environment Setup %%%%%%%%%%%%%%%

\mdfdefinestyle{problemstyle}{
	linecolor=black,linewidth=1pt,
	frametitlerule=true,
	frametitlebackgroundcolor=gray!20,
	roundcorner=10pt,
	innertopmargin=\topskip,
	frametitlealignment=\hspace{0em},
}

\mdfsetup{skipabove=\topskip,skipbelow=\topskip}
\mdtheorem[style=problemstyle]{Problem}{Problem}
\newenvironment{Solution}{\textbf{Solution.}}

%%%%%%%%%%%%%%% Coding Environment S6etup %%%%%%%%%%%%%%%

\lstset{
	basicstyle=\tt,
	% Line number
	numbers=left,
	rulesepcolor=\color{red!20!green!20!blue!20},
	escapeinside=``,
	xleftmargin=2em,xrightmargin=2em, aboveskip=1em,
	% Background frame
	framexleftmargin=1.5mm,
	frame=shadowbox,
	% Background color
	backgroundcolor=\color[RGB]{252,236,227},
	% Style
	keywordstyle=\color{blue}\bfseries,
	identifierstyle=\bf,
	numberstyle=\color[RGB]{0,192,192},
	commentstyle=\it\color[RGB]{0,153,51},
	stringstyle=\rmfamily\slshape\color[RGB]{128,0,0},
	% Show space
	showstringspaces=false
}

%%%%%%%%%%%%%%% Document Begins %%%%%%%%%%%%%%%

\begin{document}
	
%%%%%%%%%%%%%%% Title Page %%%%%%%%%%%%%%%

\begin{titlepage}
	\begin{center}
		\vspace*{3cm}
		
		\Huge
		\hrulefill
		\vspace{1cm}
		
		\huge
		\textbf{COMP 3711 Course Notes\\}
		\vspace{1cm}
		\textbf{Design and Analysis of Algorithms}
		\vspace{1cm}
		
		\hrulefill
		
		\vspace{1.5cm}
		\Large

		\textbf{LIN, Xuanyu}
		
		\vfill
		
		$\mathscr{ALGORITHMS}$
		
		\vspace{1cm}
		
		\course \ Design and Analysis of Algorithms
		
		\vspace{1cm}
		
		\includegraphics[width=0.4\textwidth]{logo-hkust.png}
		\\
		
		\Large
		
		\today
		
	\end{center}
\end{titlepage}

%%%%%%%%%%%%%%% Article Begins %%%%%%%%%%%%%%%

\begin{comment}

\begin{abstract}
	Abstract Abstract Abstract Abstract Abstract Abstract Abstract Abstract Abstract Abstract Abstract Abstract Abstract Abstract Abstract Abstract Abstract Abstract Abstract Abstract Abstract Abstract Abstract Abstract Abstract Abstract Abstract Abstract Abstract Abstract Abstract Abstract Abstract
\end{abstract}

\tableofcontents

\begin{center}
	\section*{\LARGE Title}
\end{center}

\section{Section 1}

This is a link to \href{https://www.google.com}{Google}.

$$
\vec{\nabla} \cdot \vec{E}=\frac{1}{\epsilon_{0}} \cdot \rho
$$

\begin{formal}{DarkBlue}{blueshade}
	\textbf{Theorem 1.1} 这是一段中文。\hyperref[ref1]{[1]}
	
	$$
	\vec{\nabla} \cdot \vec{E}=\frac{1}{\epsilon_{0}} \cdot \rho
	$$
	
	\noindent This is an English sentence.
\end{formal}


\begin{center}
	\begin{tabular}{|c|c|c|}
		\hline
		\multirow{2}{*}{A} & B & C \\
		\cline{2-3}
		& D & E \\
		\hline
	\end{tabular}
\end{center}

\begin{algorithm}
	\SetAlgoLined
	\KwIn{$a, b$}
	\KwOut{$c$}
	$c = a + b$\;
	\Return{$c$}\;
	\caption{Addition}
\end{algorithm}

\begin{Problem}[Title]
	
	\lstset{language=Python}
	\begin{lstlisting}[tabsize=4]
print("Hello World!")
	\end{lstlisting}

\end{Problem}

\begin{Solution}
	
	Text
	
\end{Solution}

\section{References}

\label{ref1}

[1] Google \href{https://www.google.com}{https://www.google.com}

\end{comment}

\tableofcontents

\newpage

\section{Asymptotic Notation}

\begin{formal}{DarkBlue}{blueshade}
	
	\noindent \textbf{Upper Bounds} $T(n) = O(f(n))$
	
	if exist constants $c > 0$ and $n_0 \geq 0$ such that for all $n \geq n_0$, $T(n) \leq c \cdot f(n)$.
	
	\noindent \textbf{Lower Bounds} $T(n) = \Omega(f(n))$
	
	if exist constants $c > 0$ and $n_0 \geq 0$ such that for all $n \geq n_0$, $T(n) \geq c \cdot f(n)$.
	
	\noindent \textbf{Tight Bounds} $T(n) = \Theta(f(n))$
	
	if $T(n) = O(f(n))$ and $T(n) = \Omega(f(n))$.
	
	\noindent \textbf{Note:} Here "=" means "is", not equal.
	
\end{formal}

\section{Introduction - The Sorting Problem}

\subsection{Selection Sort}

\begin{algorithm}
	\SetAlgoLined
	\KwIn{An array $A[1 ... n]$ of elements}
	\KwOut{Array $A[1 ... n]$ of elements in sorted order (asending)}
	\For{$i \gets 1$ to $n-1$}{
		\For{$j \gets i+1$ to $n$}{
			\If{$A[i]>A[j]$}{
				swap $A[i]$ and $A[j]$
			}
		}
	}
	\caption{Selection Sort}
\end{algorithm}

Running Time: $\frac{n(n-1)}{2}$

Best-Case = Worst-Case: $T(n) = \Theta(\frac{n(n-1)}{2}) = \Theta(n^2)$

\subsection{Insertion Sort}

\begin{algorithm}
	\SetAlgoLined
	\KwIn{An array $A[1 ... n]$ of elements}
	\KwOut{Array $A[1 ... n]$ of elements in sorted order (asending)}
	\For{$i \gets 2$ to $n$}{
		$j \gets i-1$
		\While{$j \geq 1$ and $A[j] > A[j+1]$}{
			swap $A[j]$ and $A[j+1]$
		}
		$j \gets j-1$
	}
	\caption{Insertion Sort}
\end{algorithm}

Running Time: Depends on the input array, ranges between $(n-1)$ and $\frac{n(n-1)}{2}$

Best-Case: $T(n) = n-1 = \Theta(n)$ (Useless)

Worst-Case: $T(n) = \Theta(\frac{n(n-1)}{2}) = \Theta(n^2)$ (Commonly-Used)

Average-Case: $T(n) = \Theta(\sum_{i=2}^n \frac{i-1}{2}) = \Theta(\frac{n(n-1)}{4}) = \Theta(n^2)$ (Sometimes Used)

\subsection{Wild-Guess Sort}

\begin{algorithm}
	\SetAlgoLined
	\KwIn{An array $A[1 ... n]$ of elements}
	\KwOut{Array $A[1 ... n]$ of elements in sorted order (asending)}
	$\pi \gets [4,7,1,3,8,11,5,...]$\ \ Create random permutation
	Check if $A[\pi[i]] \leq A[\pi[i+1]]$ for all $i = 1,2,...,n-1$
	If yes, output A according to $\pi$ and terminate
	else $Insertion-Sort(A)$
	\caption{Wild-Guess Sort}
\end{algorithm}

Running Time: Depends on the random generation, could be faster than the insertion sort.

\subsection{Worst-Case Analysis}

The algorithm's worst case running time is $O(f(n)) \implies $ On all inputs of (large) size $n$, the running time of the algorithm is $\leq c \cdot f(n)$.

The algorithm's worst case running time is $\Omega (f(n)) \implies $ There exists at least one input of (large) size $n$ for which the running time of the algorithm is  $\geq c \cdot f(n)$.

Thus, Insertion sort runs in $\Theta (n^2)$ time.

\begin{formal}{DarkBlue}{blueshade}
	
	\textbf{Notice}
	
	Selection sort, insertion sort, and wild-guess sort all have worst-case running time $\Theta (n^2)$. How to distinguish between them?
	
	$\bullet$ Closer examination of hidden constants
	
	$\bullet$ Careful analysis of typical expected inputs
	
	$\bullet$ Other factors such as cache efficiency, parallelization are important
	
	$\bullet$ Empirical comparison
	
\end{formal}

\begin{formal}{DarkGreen}{greenshade}

	\textbf{Stirling's Formula}
	
	Prove that $\log (n!) = \Theta (n \log n)$
	
	First $\log (n!) = O (n \log n)$ since:
	
	$$
	\log (n!) = \sum_{i=1}^n \log i \leq n \times \log n = O (n \log n)
	$$

	Second $\log (n!) = \Omega (n \log n)$ since:
	
	$$
	\log (n!) = \sum_{i=1}^n \log i \geq \sum_{i=n/2}^n \log i \geq n/2 \times \log n/2 = n/2 (\log n - \log 2) = \Omega (n \log n)
	$$
	
	Thus, $\log (n!) = \Theta (n \log n)$

\end{formal}

\newpage

\section{Divide \& Conquer}

\textbf{Main idea of D \& C:} Solve a problem of size $n$ by breaking it into one or more smaller problems of size less than $n$. Solve the smaller problems recursively and combine their solutions, to solve the large problem.


\subsection{Binary Search}

\begin{formal}{Brown}{brownshade}
	
	\textbf{Example: Binary Search}
	
	\textbf{Input:} A sorted array $A[1,...,n]$, and an element $x$
	
	\textbf{Output:} Return the position of $x$, if it is in $A$; otherwise output nil
	
	\textbf{Idea of the binary search:} Set $q \gets$ middle of the array. If $x = A[q]$, return $q$. If $x < A[q]$, search $A[1,...,q-1]$, else search $A[q+1,...,n]$.
	
\end{formal}

\begin{algorithm}
	\SetAlgoLined
	\KwIn{Array $A[1 ... n]$ of elements in sorted order}
	\SetKwFunction{BinarySearch}{BinarySearch}
	\BinarySearch{$A[], p, r, x$}($p, r$ being the left \& right iteration, $x$ being the element being searched){
		
		\If{$p > r$}{
			\Return{nil}
		}
		$q \gets [(p+r)/2]$
		
		\If{$x = A[q]$}{
			\Return{$q$}
		}
		\If{$x < A[q]$}{
			\BinarySearch{$A[], p, q-1, x$}
		}
		\Else{
			\BinarySearch{$A[], q+1, r, x$}
		}
	}
	\caption{Binary Search}
\end{algorithm}

Recurrence of the algorithm, supposing $T(n)$ being the number of the comparisons needed for $n$ elements:

\noindent $T(n) = T(\frac{n}{2}) + 2$ if $n > 1$, with $T(1) = 2$.

$\implies T(n) = 2\log_2 n + 2 \implies O(\log n)$ algorithm

\begin{formal}{Brown}{brownshade}
	
	\textbf{Example: Binary Search in Rotated Array}
	
	Suppose you are given a sorted array $A$ of $n$ distinct numbers that 
	has been rotated $k$ steps, for some unknown integer $k$ between 1 and $n-1$. That is, $A[1 ... k]$ is sorted in increasing order, and $A[k+1 ... n]$ is also sorted in increasing order, and $A[n] < A[1]$.
	
	Design an $O(\log n)$-time algorithm that for any given x, 
	finds x in the rotated sorted array, or reports that it does not 
	exist.
	
	\noindent \textbf{Algorithm:}
	
	First conduct a $O(\log n)$ algorithm to find the value of $k$, then search for the target value in either the first part or the second part.
	
	$Find-x(A, x)$
	
	$k \leftarrow Find-k(A, 1, n)$ (First find $k$)
	
	$if\ x \geq A[1]\ then\ return\ BinarySearch(A, 1, k, x)$
	
	$Else\ return\ BinarySearch(A, k+1, n, x)$
	
\end{formal}

\newpage

\begin{formal}{Brown}{brownshade}
	
	\textbf{Example: Finding the last 0}
	
	You are given an array $A[1 ... n]$ that contains a sequence of 0 
	followed by a sequence of 1 (e.g., 0001111111). $A$ contains $k$ 0(s) ($k>0$ and $k<<n$) and at least one 1.
	
	Design an $O(\log k)$-time algorithm that finds the position $k$ of the last 0.

	\noindent \textbf{Algorithm:}
	
	$i\leftarrow1$
	
	$while\ A[i]=0$
	
	\quad \quad $i\leftarrow2i$
	
	$find-k(A[i/2 ... i])$

\end{formal}

\subsection{Merge Sort}

\textbf{Principle of the Merge Sort:}

$\bullet$ Divide array into two halves.

$\bullet$ Recursively sort each half.

$\bullet$ Merge two halves to make sorted whole.

\begin{algorithm}
	\SetAlgoLined
	\SetKwFunction{MergeSort}{MergeSort}
	\SetKwFunction{Merge}{Merge}
	\MergeSort{$A, p, r$}($p, r$ being the left \& right side of the array to be sorted){
		
		\If{$p = r$}{
			\Return
		}
		$q \gets [(p+r)/2]$
		
		\MergeSort{$A, p, q$}
		
		\MergeSort{$A, q+1, r$}
		
		\Merge{$A, p, q, r$}
		
		\underline{First Call:} \MergeSort{$A, 1, n$}
	}
	\caption{Merge Sort}
\end{algorithm}

\begin{algorithm}
	\SetAlgoLined
	\KwIn{Two Arrays $L\gets A[p ... q]$ and $R\gets A[q+1 ... r]$ of elements in sorted order}
	\SetKwFunction{Merge}{Merge}
	\Merge{$A, p, q, r$}{
		
		Append $\infty$ at the end of $L$ and $R$
		
		$i\gets 1,\ j\gets 1$
		
		\For{$k \gets p$ to $r$}{
		
			\If{$L[i] \leq R[j]$}{
				
				$A[k] \gets L[i]$
				
				$i \gets i + 1$

			}
		
			\Else{
			
				$A[k] \gets R[j]$
				
				$j \gets j + 1$
		
			}
			
		}

	}
	\caption{Merge}
\end{algorithm}

Let $T(n)$ be the running time of the algorithm on an array of size $n$.

\noindent \textbf{Merge Sort Recurrence:}
$$
T(n) \leq T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + O(n), \quad n>1, \quad T(1) = O(1)
$$
\textbf{Simplification:}
$$
\implies T(n) = 2T(n/2) + n, \quad n>1, \quad T(1) = 1
$$
\textbf{Result:}
$$
T(n) = n\log_2 n + n = O(n\log n)
$$

\newpage

\subsection{Inversion Counting}

\textbf{Definition of the Inversion Numbers:} Given array $A[1 ... n]$, two elements $A[i]$ and $A[j]$ are inverted if $i < j$ but $A[i] > A[j]$. The inversion number of $A$ is the number of inverted pairs.

\begin{formal}{DarkBlue}{blueshade}
	
	\textbf{Theorem:}

	The number of swaps used by Insertion Sort = Inversion Number (Proved by induction on the size of the array)
	
	\noindent \textbf{Algorithm to Compute Inversion Number:}
	
	Algorithm 1: Check all $\Theta(n^2)$ pairs.
	
	Algorithm 2: Run Insertion Sort and count the number of swaps – Also $\Theta(n^2)$ time.
	
	Algorithm 3: Divide and Conquer
	
\end{formal}

\subsubsection{Counting Inversions: Divide-and-Conquer}

\textbf{Principle of the Algorithm:}

$\bullet$ Divide: divide array into two halves

$\bullet$ Conquer: recursively count inversions in each half

$\bullet$ Conbine: count inversions where $a_i$ and $a_j$ are in different halves, and return sum of three quantities

Inversion counting during the combine step is very similar to the Merge Algorithm (Algorithm 6), by counting the sum of each inversion number of the right array (indicated by $I[j]$) comparing to the left array.

\begin{algorithm}
	\SetAlgoLined
	\KwIn{Two Arrays $L\gets A[p ... q]$ and $R\gets A[q+1 ... r]$ of elements in sorted order}
	\SetKwFunction{Count}{Count}
	\Count{$A, p, q, r$}{
		
		$i\gets 1,\ j\gets 1,\ c\gets 0$
		
		\While{$(i \leq q-p+1) \&\& (j \leq r-q)$}{
			
			\If{$L[i] \leq R[j]$}{
				
				$i \gets i+1$
				
			}
			
			\Else{
				
				$I[j] = q-p-i+2$
				
				$c \gets c+I[j]$
				
				$j \gets j+1$
				
			}
			
		}
		
	}
	\caption{Inversion Count during Combination}
\end{algorithm}

The time-complexity of the algorithm is $\Theta(n\log n)$, same as the Merge Sort.

\subsubsection{Implementation of the Algorithm}

\begin{algorithm}
	\SetAlgoLined
	\SetKwFunction{Sort}{Sort-and-Count}
	\SetKwFunction{Merge}{Merge-and-Count}
	\Sort{$A, p, r$}{
		
		\If{$p = r$}{
			\Return{0}
		}
		$q \gets \lfloor(p+r)/2\rfloor$
		
		$c_1 \gets$ \Sort{$A, p, q$}
		
		$c_2 \gets$ \Sort{$A, q+1, r$}
		
		$c_3 \gets$ \Merge{$A, p, q, r$}
		
		\Return{$c_1 + c_2 + c_3$}
		
		\underline{First Call:} \Sort{$A, 1, n$}
	}
	\caption{Main Algorithm}
\end{algorithm}

\begin{algorithm}
	\SetAlgoLined
	\KwIn{Two Arrays $L\gets A[p ... q]$ and $R\gets A[q+1 ... r]$ of elements in sorted order}
	\SetKwFunction{Merge}{Merge-and-Count}
	\Merge{$A, p, q, r$}{
		
		Append $\infty$ at the end of $L$ and $R$
		
		$i\gets 1,\ j\gets 1, c\gets 0$
		
		\For{$k \gets p$ to $r$}{
			
			\If{$L[i] \leq R[j]$}{
				
				$A[k] \gets L[i]$
				
				$i \gets i + 1$
				
			}
			
			\Else{
				
				$A[k] \gets R[j]$
				
				$j \gets j + 1$
				
				$c \gets c+q-p-i+2$
				
			}
			
		}
	
		\Return{$c$}
		
	}
	\caption{Merge-and-Count}
\end{algorithm}

\subsection{Basic Summary of D\&C: Problem Size \& Number of Problems}

\textbf{Observations of D\&C in Logarithmic Patterns:}

$\bullet$ Break up problem of size $n$ into $p$ parts of size $n/q$.

$\bullet$ Solve parts recursively and combine solutions into overall solution.

$\bullet$ At level $i$, we break $i$ times and we have $p^i$ problems of size $n/q^i$.

$\bullet$ When we cannot break up any more, usually when the problem size 
becomes 1. Usually $i \approx \log_q n$.

\begin{formal}{DarkGreen}{greenshade}

The number of problems at (bottom) level $\log_q n$ is $p^i = p^{\log_q n} = n^{\log_q p}$.

\end{formal}

\vspace{1em}

\textbf{Observations of D\&C in Non-Logarithmic Patterns:}

$\bullet$ Break up problem of size $n$ into $p(\leq 2)$ parts of size $n-q$. (e.g. $q=1$ for Hanoi Problem)

$\bullet$ Assume that $q=1$

$\bullet$ At level i, we break $i$ times and we have $p^i$ problems of size $n-i$.

$\bullet$ If we stop when the problem size becomes 1, then $n-i=1 \implies i=n-1$.

\begin{formal}{DarkGreen}{greenshade}

The number of problems at (bottom) level $n-1$ is: $p^i = p^{n-1}$.

\end{formal}

\subsection{Maximum Contiguous Subarray}

\begin{formal}{Brown}{brownshade}
	
	\textbf{Example: The Maximum Subarray Problem}
	
	\textbf{Input:} An array of numbers $A[1,...,n]$, both positive and negative
	
	\textbf{Output:} Find the maximum $V(i, j)$, where $V(i, j) = \sum_{k=i}^j A[k]$
	
\noindent \textbf{Brute-Force Algorithm}

\textbf{Idea:} Calculate the value of $V(i, j)$ for each pair $i\leq j$ and return the maximum value.

Requires three nested for-loop, time complexity: $\Theta(n^3)$.

\noindent \textbf{A Data-Reuse Algorithm}

\textbf{Idea:} $V(i, j) = V(i, j-1) + A[j]$

Requires two nested for-loop, time complexity: $\Theta(n^2)$.

\end{formal}

\newpage

\subsubsection{A D\&C Algorithm}

\textbf{Idea:} Cut the array into two halves, all subarrays can be classified into three cases: entirely in the first/second half, or crosses the cut.

\textbf{Compare with the merge sort:} Whole algorithm will run in $\Theta(n\log n)$ time if the cross-cut can be solved in $O(n)$ time.

\begin{algorithm}
	\SetAlgoLined
	\SetKwFunction{MaxSubArray}{MaxSubArray}
	\MaxSubArray{$A, p, r$}{
		
		\If{$p = r$}{
			\Return{$A[p]$}
		}
		$q \gets \lfloor(p+r)/2\rfloor$
		
		$M_1 \gets$ \MaxSubArray{$A, p, q$}
		
		$M_2 \gets$ \MaxSubArray{$A, q+1, r$}
		
		$L_m, R_m \gets -\infty$
		
		$V \gets 0$
		
		\For{$i \gets q$ to $p$}{
		
			$V \gets V+A[i]$
			
			\If{$V>L_m$}{
			
				$L_m \gets V$
			
			}
		
		}
	
		$V \gets 0$
		
		\For{$i \gets q+1$ to $r$}{
			
			$V \gets V+A[i]$
			
			\If{$V>R_m$}{
				
				$R_m \gets V$
				
			}
			
		}
		
		\Return{$\max(M_1, M_2, L_m+R_m)$}
		
		\underline{First Call:} \MaxSubArray{$A, 1, n$}
	}
	\caption{Maximum Subarray}
\end{algorithm}

\textbf{Recurrence:} $T(n) = 2T(n/2)+n \implies T(n) = \Theta(n\log n)$

\subsubsection{Kadane's Algorithm}

\textbf{Idea:} Based on the principles of \textbf{Dynamic Programming}. Let $V[i]$ be the (local) maximum sub-array that ends at $A[i]$, then we let:

$\bullet V[1] = A[1]$

$\bullet V[i] = \max(A[i], A[i] + V[i-1])$

The maximum of $V[i]$, namely $V_{max}$ is the maximum continuous subarray found so far.

\begin{algorithm}
	\SetAlgoLined
	
	$V_{max} \gets -\infty; V \gets 0; \text{start} \gets 1; \text{end} \gets 1; \text{temp} \gets 1$ (Note: start \& end specify the maximum sub-array)
		
	\For{$i\gets 1$ to $n$}{
	
	$V\gets V+A[i]$
	
	\If(// Implies $V[i-1]$ is negative, restart from the current position){$V < A[i]$}{
		
		$V\gets A[i]; \text{temp}\gets i$
		
		}

	\If(// Found a max sum, update start and end){$V > V+{max}$}{
	
		$V_{max}\gets V; \text{start}\gets \text{temp}; \text{end}\gets i$

		}

	}
	
	\caption{Kadane's Algorithm}
\end{algorithm}

\textbf{Time Complexity:} $\Theta(n)$

\begin{formal}{Brown}{brownshade}
	
	\textbf{Example: Maximizing Stock Profits}
	
	You are presented with an array $p[1\dots n]$ where $p[i]$ is the price of the stock on day $i$.
	
	Design an divide-and-conquer algorithm that finds a strategy to make as much money as possible, i.e., it finds a pair $i, j$ with $1\leq i\leq j\leq n$ such that $p[j]-p[i]$ is maximized over all possible such pairs. Note that you are only allowed to buy the stock once and then sell it later.

\vspace*{1em}

\noindent \textbf{Idea 1: Divide and Conquer}

$\bullet$ Cut the array into two halves.

$\bullet$ All $i, j$ solutions can be classified into three cases: both $i, j$ are entirely in the first(second) half, or $i$ is in the left half while $j$ is in the right half.

$\bullet$ Maximizing a Case 3 result $p[j]-p[i]$ means finding the smallest value in the first half and the largest in the second half.

\textbf{Time Complexity:} $T(n) = 2T(n/2) + n \implies T(n) = \Theta(n\log n)$

\vspace*{1em}

\noindent \textbf{Idea 2: Kadane's Algorithm}

$\bullet$ Create a \textbf{Profit} array with $Profit[i]=Price[i+1]-Price[i]$.

$\bullet$ Perform the Kadane's Algorithm.

\textbf{Time Complexity:} $O(n)$

\end{formal}

\subsection{Integer Multiplication}

\subsubsection{A Simple D\&C Algorithm for Integer Multiplication}

\textbf{Goal:} Given two $n$-bit binary integers $a$ and $b$, compute: $a\cdot b$.

\textbf{Idea:} Multiplication by $2^k$ can be done in one time unit by a left shift of $k$ bits.

$\bullet$ Rewrite the two numbers as $a = 2^{n/2} a_1 + a_0$, $b = 2^{n/2} b_1 + b_0$.

$\bullet$ The product becomes: $a\cdot b = (2^{n/2} a_1 + a_0)(2^{n/2} b_1 + b_0) = 2^n a_1 b_1 + 2^{n/2} (a_1 b_0 + a_0 b_1) + a_0 b_0$

$\bullet$ The new computation requires 4 products of integers, each with $n/2$ bits.

$\bullet$ Apply D\&C by splitting a problem of size $n$, to 4 problems of size $n/2$.

\begin{algorithm}
	\SetAlgoLined
	\SetKwFunction{Multiply}{Multiply}
	\Multiply{$A, B$}{
		
		$n\gets$ size of $A$
		
		\If{$n = 1$}{\Return{$A[1]\cdot B[1]$}}
		
		$mid \gets \lfloor n/2 \rfloor$
		
		$U \gets$ \Multiply($A[mid+1..n], B[mid+1..n]$) // $a_1b_1$
		
		$V \gets$ \Multiply($A[mid+1..n], B[1..mid]$) // $a_1b_0$
		
		$W \gets$ \Multiply($A[1..mid], B[mid+1..n]$) // $a_0b_1$
		
		$Z \gets$ \Multiply($A[1..mid], B[1..mid]$) // $a_0b_0$
		
		$M[1..2n]\gets 0$
		
		$M[1..n]\gets Z$ // $a_0b_0$
		
		$M[mid+1..]\gets M[mid+1..] \oplus V \oplus W$ // $+[(a_1b_0+a_0b_1)\ll\text{(left shift) } n/2]$
		
		$M[2mid+1..]\gets M[2mid+1..] \oplus U$ // $+[a_1b_1\ll n]$
		
		\Return{$M$}
		
	}
	\caption{Binary Multiplication}
\end{algorithm}

\textbf{Time Complexity:} $T(n) = 4T(n/2) + n\implies T(n) = \Theta(n^2)$

\newpage

\subsubsection{Karatsuba Multiplication}

\textbf{Goal:} Given two $n$-bit binary integers $a$ and $b$, compute: $a\cdot b$.

\textbf{Idea:}

$\bullet$ We've seen that $ab = a_1b_1 2^n + (a_1b_0+a_0b_1) 2^{n/2} + a_0b_0$, so we only need the result of $a_1b_0+a_0b_1$.

$\bullet$ Note that $a_1b_0+a_0b_1 = (a_1+a_0)(b_1+b_0) - a_1b_1 - a_0b_0$, thus only requires performing 3 multiplications of size $n/2$.

\begin{algorithm}
	\SetAlgoLined
	\SetKwFunction{Multiply}{Multiply}
	\Multiply{$A, B$}{
		
		$n\gets$ size of $A$
		
		\If{$n = 1$}{\Return{$A[1]\cdot B[1]$}}
		
		$mid \gets \lfloor n/2 \rfloor$
		
		$U \gets$ \Multiply($A[mid+1..n], B[mid+1..n]$) // $a_1b_1$
		
		$Z \gets$ \Multiply($A[1..mid], B[1..mid]$) // $a_0b_0$
		
		$A'\gets A[mid+1..n] \oplus A[1..mid]$ // $a_1+a_0$
		
		$B'\gets B[mid+1..n] \oplus B[1..mid]$ // $b_1+b_0$
		
		$Y \gets$ \Multiply($A', B'$) // $(a_1+a_0)(b_!+b_0)$
		
		$M[1..2n]\gets 0$
		
		$M[1..n]\gets Z$ // $a_0b_0$
		
		$M[mid+1..]\gets M[mid+1..] \oplus Y \ominus U \ominus Z$ // $+[(a_1b_0+a_0b_1)\ll\text{(left shift) } n/2]$
		
		$M[2mid+1..]\gets M[2mid+1..] \oplus U$ // $+[a_1b_1\ll n]$
		
		\Return{$M$}
		
	}
	\caption{Binary Multiplication (Karatsuba's Multiplication Algorithm)}
\end{algorithm}

\textbf{Time Complexity:} $T(n) = 3T(n/2) + n\implies T(n) = \Theta(n^{\log_2 3}) = \Theta(n^{1.585\cdots})$

For recent research, see: \href{https://annals.math.princeton.edu/2021/193-2/p04}{Integer Multiplication in $O(n\log n)$ Time (David Harvey \& Joris van der Hoeven, 2021)}

\subsection{Matrix Multiplication}

$$
\left[
\begin{matrix}
	c_{11} & c_{12} & \cdots & c_{1n}\\
	c_{21} & c_{22} & \cdots & c_{2n}\\
	\cdots & \cdots & \cdots & \cdots\\
	c_{n1} & c_{n2} & \cdots & c_{nn}
\end{matrix}
\right]
=
\left[
\begin{matrix}
	a_{11} & a_{12} & \cdots & a_{1n}\\
	a_{21} & a_{22} & \cdots & a_{2n}\\
	\cdots & \cdots & \cdots & \cdots\\
	a_{n1} & a_{n2} & \cdots & a_{nn}
\end{matrix}
\right]
\left[
\begin{matrix}
	b_{11} & b_{12} & \cdots & b_{1n}\\
	b_{21} & b_{22} & \cdots & b_{2n}\\
	\cdots & \cdots & \cdots & \cdots\\
	b_{n1} & b_{n2} & \cdots & b_{nn}
\end{matrix}
\right]\quad
c_{ij} = \sum_{k=1}^n a_{ik} b_{kj}
$$

\textbf{Brute Force Method:} $\Theta (n^3)$ time.

\subsubsection{A D\&C Solution to Matrix Multiplication}

$$
\left[
\begin{matrix}
	C_{11} & C_{12}\\
	C_{21} & C_{22}
\end{matrix}
\right]
=
\left[
\begin{matrix}
	B_{11} & B_{12}\\
	B_{21} & B_{22}
\end{matrix}
\right]
\left[
\begin{matrix}
	A_{11} & A_{12}\\
	A_{21} & A_{22}
\end{matrix}
\right]\quad
\begin{cases}
	C_{11} = (A_{11}\times B_{11}) + (A_{12}\times B_{21})\\
	C_{12} = (A_{11}\times B_{12}) + (A_{12}\times B_{22})\\
	C_{21} = (A_{21}\times B_{11}) + (A_{22}\times B_{21})\\
	C_{22} = (A_{21}\times B_{12}) + (A_{22}\times B_{22})
\end{cases}
$$

\textbf{Recursion:} $T(n) = 8T(n/2) + O(n^2) \implies T(n) = O(n^3)$

\newpage

\subsubsection{Strassen's Matrix Multiplication Algorithm}

\textbf{Idea:} Muliply 2-by-2 block matrices with only 7 multiplications

$$
\left[
\begin{matrix}
	C_{11} & C_{12}\\
	C_{21} & C_{22}
\end{matrix}
\right]
=
\left[
\begin{matrix}
	B_{11} & B_{12}\\
	B_{21} & B_{22}
\end{matrix}
\right]
\left[
\begin{matrix}
	A_{11} & A_{12}\\
	A_{21} & A_{22}
\end{matrix}
\right]
$$
$$
\begin{cases}
	P_1 = A_{11} \times (B_{12}-B_{22})\\
	P_2 = (A_{11}+A_{12}) \times B_{22}\\
	P_3 = (A_{21}+A_{22}) \times B_{11}\\
	P_4 = A_{22} \times (B_{21}-B_{11})\\
	P_5 = (A_{11}+A_{12}) \times (B_{11}+B_{22})\\
	P_6 = (A_{12}-A_{22}) \times (B_{21}+B_{22})\\
	P_7 = (A_{11}-A_{21}) \times (B_{11}+B_{12})
\end{cases}
\quad
\begin{cases}
	C_{11} = P_5+P_4-P_2+P_6\\
	C_{12} = P_1+P_2\\
	C_{21} = P_3+P_4\\
	C_{22} = P_5+P_1-P_3-P_7
\end{cases}
$$

\textbf{Recursion:} $T(n) = 7T(n/2) + n^2 \implies T(n) = \Theta(n^{\log_2 7}) = \Theta(n^{2.807\cdots})$

For recent research, see: \href{https://arxiv.org/abs/1401.7714}{Powers of Tensors and Fast Matrix Multiplication (Le Gall, 2014)}

Conjecture: Close to $\Theta(n^2)$

\subsection{Master Theorem}

For recurrences of form
$$
T(n) = a T(n/b) + f(n) \text{ or } T(n) \leq a T(n/b) + f(n) \text{, Let } c \equiv \log_b a
$$

where

$\bullet$ $a \geq 1$ and $b > 1$ both being constants

$\bullet$ $f(n)$ is a (asymptotically) positive polynomial function

$\bullet$ $n/b$ could be either $\lfloor n/b \rfloor$ or $\lceil n/b \rceil$

\subsubsection{Master Theorem for Equalities}

\begin{formal}{Green}{greenshade}
	
	\begin{enumerate}[label=(\arabic*)]
		\item Work Increases: $f(n) = O(n^{c-\epsilon})$ for some $\epsilon \implies T(n) = \Theta(n^c)$
		
		\item Work Remains: $f(n) = \Theta(n^c \log^k n)$ for $k > -1 \implies T(n) = \Theta(n^c \log^{k+1} n)$
		
		Note: For the case $k = -1$, $T(n) = \Theta(n^c \log \log n)$;\quad
		For the case $k < -1$, $T(n) = \Theta(n^c)$
		
		\item Work Decreases: $f(n) = \Omega(n^{c+\epsilon})$ for some $\epsilon \implies T(n) = \Theta(f(n))$
		
		Note: Rigorously, the third case requires $af(n/b) \leq kf(n)$ for some $k<1$ and sufficiently large $n$
		
		\item For a special case $T(n) = \sum_i T(\alpha_i n) + n$ where $\alpha_i > 0$ with $\sum_i \alpha_i < 1$, we have $T(n) = \Theta(n)$
	\end{enumerate}
	
\end{formal}



\subsubsection{Master Theorem for Inequalities}

\begin{formal}{Green}{greenshade}
	
	\begin{enumerate}[label=(\arabic*)]
		\item Work Increases: $f(n) = O(n^{c-\epsilon})$ for some $\epsilon \implies T(n) = O(n^c)$
		
		\item Work Remains: $f(n) = O(n^c) \implies T(n) = O(n^c \log n)$
		
		\item Work Decreases: $f(n) = \Omega(n^{c+\epsilon})$ for some $\epsilon \implies T(n) = O(f(n))$
	\end{enumerate}
	
\end{formal}

\newpage

\section{Advanced Sorting Algorithms}

\subsection{Probability \& Statistics, Random Permutation}

$$
E[X] = \sum i \cdot Pr[X = i]
$$

$$
E[X+Y] = E[X] + E[Y]
$$

For independent random variables $X$ \& $Y$, 

$$
E[XY] = E[X] \cdot E[Y]
$$

\begin{algorithm}
	\SetAlgoLined
	\SetKwFunction{RandomPermute}{RandomPermute}
	\RandomPermute{$A$}{
		
		$n\gets A.length$
		
		\For{$i\gets 1 \text{ to } n$}{
		
			swap $A[i]$ with $A[Random(1,i)]$
			
		}
		
	}
	\caption{Random Permutation}
\end{algorithm}

\subsection{Randomized Algorithm - Quicksort}

\textbf{Idea:} Quicksort chooses item as pivot. It partitions array so that all items less than or equal to pivot are on the left and all items greater than pivot on the right. It then recursively Quicksorts left and right sides.


\begin{algorithm}
	\SetAlgoLined
	\SetKwFunction{Quicksort}{Quicksort}
	\SetKwFunction{Partition}{Partition}
	\Quicksort{$A, p, r$} // Array from $A[p]$ to $A[r]$ {
		
		\If{$p \geq r$}{
			\Return
		}
	
		$q = $\Partition($A, p, r$) // Set a new pivot position
		
		\Quicksort($A, p, q-1$)
		
		\Quicksort($A, q+1, r$)
		
		\underline{First Call:} \MaxSubArray{$A, 1, n$}
		
	}
		
	\vspace{1em}
	
	\Partition{$A, p, r$}{
	
		$x\gets A[r]$ // Set the last item as pivot, or randomly swap away the last item before choosing the pivot
		
		$i\gets p-1$
		
		\For{$j\gets p$ to $r-1$}{
		
			\If{$A[j]\leq x$}{
			
				$i\gets i+1$
				
				swap $A[i]$ and $A[j]$ // Put all items $\leq A[r]$ on the left
			
			}
		
		}

		swap $A[i+1]$ and $A[r]$

		\Return{$i+1$}

	}
	
	\caption{Quicksort}
\end{algorithm}

\newpage

\subsubsection{Running Time}

\textbf{Best Case:} Always select the median element as the pivot - $\Theta(n\log n)$ time.

\textbf{Worst Case:} Always select the smallest (or the largest) element - $\Theta(n^2)$ time.

To make running time independent of input, we can randomly choose an element as the pivot by swapping it with last item in array before running the partition.

\subsubsection{Binary Tree Representation}

\begin{figure}[h]
	\centering
	\includegraphics[width=0.8\textwidth]{img4-1}
\end{figure}

\subsubsection{Expected Running Time for Random-Based Quicksort} 

$\bullet$ Two elements $z_i$ and $z_j$ are compared at most once, iff $z_i$ or $z_j$ is the first to be chosen among $z_i, \cdots, z_j$

$\bullet$ The probability above (any indicated two elements $z_i$ and $z_j$ are compared) is $\frac{2}{j-1+1}$

$$
\implies E_{\text{Num of comparisons made}} = \sum_{i<j} \frac{2}{j-1+1} = O(n\log n)
$$

\subsubsection{Find the i-th Smallest Element Using Quicksort}

\begin{formal}{Brown}{brownshade}
	
	\textbf{Example: Find the i-th Smallest Element}
	
	Given an unsorted array $A[1\dots n]$ and an integer $i$, return the $i$-th smallest element of $A[1\dots n]$.
	
\vspace*{1em}

\noindent \textbf{Idea:}

\noindent 1. Choose a Pivot $x$ from $A[p\dots r]$

\noindent 2. Partition $A$ around $x$. (linear time)

\noindent 3. After partitioning, pivot $x$ will be at known location $q$

If $i = q-p+1$, then $x$ is the actual solution

If $i < q-p+1$, then the $i$-th element of $A[p\dots r]$ is the $i$-th element of $A[p\dots q-1]$, solve recursively

If $i > q-p+1$, then the $i$-th element of $A[p\dots r]$ is the $j = (i-q+p-1)$-th element of $A[q+1\dots r]$, solve recursively

\end{formal}

\begin{algorithm}
	\SetAlgoLined
	\SetKwFunction{Select}{Select}
	\Select{$A, p, r, i$}{
		
		\If{$p=r$}{
			\Return{$A[p]$}
		}
		
		Randomly choose an element in $A[p\dots r]$ as the pivot and swap it with $A[r]$
		
		$q$ \gets Partition($A, p, r$)
		
		$k$ \gets $q-p+1$
		
		\If{$i=k$}{
			\Return{$A[q]$}
		}
	
		\ElseIf{$i<k$}{
			
			\Return{\Select{$A, p, q-1, i$}}
			
		}

		\Else{
		
			\Return{\Select{$A, q+1, r, i-k$}}
		
		}
		
	}
	
	\underline{First Call:} \Select{$A, 1, n, i$}
	
	\caption{i-th Smallest Element}
\end{algorithm}

\subsubsection{Expected Running Time for Finding the i-th Smallest Element}

$\bullet$ A pivot is "good" if it's between the 25\%- and 75\%-percentile of sorted $A$, eliminating at least 1/4 of the array. The probability for such "good" pivot is 1/2.

$\bullet$ Let $i$-th stage be the time between the $i$-th good pivot (not including) and the $(i+1)$-st good pivot (including), $i=0, 1, 2, \cdots$, then the expected pivots selected within a stage is 2.

$\bullet$ Let $Y_i =$ the running time of $i$-th stage, $X_i =$ the num. of pivots (recursive calls) in $i$-th stage. Then $Y_i \leq X_i (3/4)^i n$.
$$
\implies E[Y_i] \leq E[X_i (3/4)^i n] = 2(3/4)^i n \implies \text{Expected Total Running Time} \leq E[\sum_i Y_i] \leq \sum_i 2(3/4)^i n = O(n)
$$

\begin{formal}{Brown}{brownshade}
	
	\textbf{Example: i-th Smallest Element in Two Sorted Arrays}
	
	Given two sorted arrays $A1$ and $A2$ of sizes $m$ and $n$. Design an
	algorithm to find the $k$-th smallest element in the union of the elements in $A1$ and $A2$ $(k \leq m+n)$.
	
\end{formal}

\begin{algorithm}
	\SetAlgoLined
	\SetKwFunction{Search}{Search}
	\Search{$\text{array }A1, \text{array }A2, \text{start1 }1, \text{end1 }k, \text{start2 }1, \text{end2 }k, \text{Order }k$}{
		
		\textbf{Main Idea:} Compare elements $A1[k/2]$ and $A2[k/2]$
		
		\If{$A1[k/2] < A2[k/2]$}{
			
			Eliminate first half of $A1$
			
			\Return{\Search{$A1, A2, k/2+1, \text{end1}, \text{start2}, \text{end2}, k/2$}}
			
		}
		
		\Else{
		
			Eliminate first half of $A2$
			
			\Return{\Search{$A1, A2, \text{start1}, \text{end1}, k/2+1, \text{end2}, k/2$}}
		
		}
		
	}
	
	\caption{i-th Smallest Element in Two Sorted Arrays}
\end{algorithm}

\textbf{Time Complexity:} $\Theta(\log k)$

\newpage

\subsection{Heapsort}

\subsubsection{Priority Queues}

\textbf{Main Idea:} Processing the shortest job first - Extracting the smallest element from the queue.

A Priority Queue is an abstract data structure that supports two 
operations: Insert \& Extract-Min.

\textbf{Implementations:}

1. Unsorted list + a pointer to the smallest element: $O(1)$ Insert \& $O(n)$ Extract-Min

2. Sorted doubly linked list + a pointer to first element: $O(n)$ Insert \& $O(1)$ Extract-Min

\subsubsection{Binary Heap Implementation}

$\bullet$ All levels are full except possibly the lowest level

$\bullet$ If the lowest level is not full, then nodes must be packed to 
the left

$\bullet$ The value of a node is at least the value of its parent — Min-heap

$\bullet$ Both Insert \& Extract-Min can be done in $O(\log n)$ time

\begin{formal}{DarkBlue}{blueshade}
	
	\textbf{Notice}
	
	The binary tree here is DIFFERENT from the Binary Search Tree, which requires ALL left nodes $<$ parent, while ALL right nodes $>$ parent.
	
\end{formal}

\textbf{Array Implementation of Heap}

$\bullet$ The root is in array position 1

$\bullet$ For any element in array position $i$, the left child is in position $2i$, the right child is in position $2i+1$, the parent is in position $\lfloor i/2 \rfloor$

\begin{figure}[h]
	\centering
	\begin{subfigure}[b]{0.2\textwidth}
		\centering
		\includegraphics[width=\textwidth]{img4-2}
		%\caption{}
	\end{subfigure}
	%\hfill
	\begin{subfigure}[b]{0.5\textwidth}
		\centering
		\includegraphics[width=\textwidth]{img4-3}
		%\caption{}
	\end{subfigure}
	%\caption{}
\end{figure}

\subsubsection{Heapsort}

\textbf{Insert}

$\bullet$ Add the new element to the next available position at the lowest level.

$\bullet$ Restore the min-heap property if violated.
\begin{algorithm}
	\SetAlgoLined
	\SetKwFunction{Insert}{Insert}
	\Insert{$x, i$}{
		
		$A[i]$ \gets $x$
		
		$j=i$
		
		\While(// $A[j]$ is less than its parent){$j>1$ and $A[j] < A[\lfloor j/2 \rfloor]$}{
			
			Swap $A[j]$ and $A[\lfloor j/2 \rfloor]$
			
		}
	
		$j=\lfloor j/2 \rfloor$
		
	}
	
	\caption{Add item $x$ to heap $A[1 \dots i-1]$}
\end{algorithm}

\textbf{Time Complexity:} $O(\log n)$

\newpage

\textbf{Extract-Min:} Should preserve both min-heap property \& completeness

$\bullet$ Copy the last element to the root (overwrite).

$\bullet$ Restore the min-heap property by percolating (or bubbling 
down): if the element is larger than either of its children, then
interchange it with the smaller of its children.
\begin{algorithm}
	\SetAlgoLined
	\SetKwFunction{Extract}{Extract-Min}
	\Extract{$i$}{
		
		Output($A[1]$)
		
		Swap $A[1]$ and $A[i]$
		
		$A[i] = \infty$, $j = 1$, $l = A[2j]$, $r = A[2j+1]$ // Left \& Right Children
		
		\While( // if $A[j]$ is larger than a child, swap with the smaller child){$A[j] > \min(l, r)$}{
		
			\If{$l<r$}{
			
				Swap $A[j]$ with $A[2j]$, $j=2j$
			
			}
		
			\Else{
			
				Swap $A[j]$ with $A[2j+1]$, $j=2j+1$
			
			}

			$l=A[2j], r=A[2j+1]$

		}
		
	}
	
	\caption{Remove the smallest item $A[1]$ in the heap $A[1 \dots i]$}
\end{algorithm}

\textbf{Time Complexity:} $O(\log n)$

\textbf{Total Time Complexity:} Build a binary heap of $n$ elements \& Perform $n$ Extract-Min operations: $O(n\log n)$

\begin{formal}{Brown}{brownshade}
	
	\textbf{Example: Merging $k$ Sorted Arrays}
	
	Suppose that you have $k$ sorted arrays, each with $n$ elements, and you want to combine them into a single sorted array of $kn$ elements.

\textbf{Solution 1:} Merge the first two arrays, then merge it with the third, and so on. Time Complexity = $\sum_{i=2}^k in = O(k^2 n)$

\textbf{Solution 2:} Divide recursively $k$ sorted arrays into two parts, conduct the merging for the subproblems. $T(k) = 2T(k/2) + kn \implies \text{Time Complexity = }T(k) = O(kn\log k)$

\textbf{Solution 3 (Heapsort):} Insert the first element of each array into an empty min-heap. Extract-min every time and insert the next item of in the same array as the one being extracted. Time Complexity = $O(kn\log k)$

\end{formal}

\begin{formal}{Brown}{brownshade}

	\textbf{[Operation Implementation]}
	
	\textbf{Decrease-Key:} Decreases the value of one specified element (Used in Dijkstra's Algorithm)
	
	\textbf{Modification of the heaps to support it in $O(\log n)$ time:} Change the heap tree to a binary search tree.

\end{formal}

For more information, see: \href{https://en.wikipedia.org/wiki/Binary_heap}{Binary Heap (Wikipedia)}

Some websites markdown:
\href{https://www.zhihu.com/question/31387715}{Zhihu}
\href{http://www.matrix67.com/blog/archives/1209}{Web 1}
\href{http://www.matrix67.com/blog/archives/1523}{Web 2}


\newpage

\subsection{Linear-Time Sorting}

\subsubsection{Decision Trees and Lower Bounds}

\textbf{Decision Tree Model}
\begin{figure}[h]
	\centering
	\includegraphics[width=0.6\textwidth]{img4-4}
\end{figure}

\textbf{Fact:} A binary tree with $n$ leaves must have height $\Omega(\log n)$.

\textbf{Theorem:} Any algorithm for finding location of given element in a sorted array of size $n$ must have running time $\Omega(\log n)$ in the decision-tree model.

\begin{formal}{Green}{greenshade}
	
	\textbf{Theorem:} Any \textbf{comparison-based sorting algorithm} (only by using comparisons without using thetr accurate values) requires $\Omega(n\log n)$ time.
	
	Given $n$ numbers, there are $n!$ possible permutations, resulting in the tree height being $\Omega(\log(n!))$. Thus, the time complexity is bounded as $\Omega(\log(n!)) = \Omega(n\log n)$.
	
\end{formal}

\subsubsection{Linear-time Sorting}

\textbf{Counting-Sort}

$\bullet$ Assumes that the elements are integers from 1 to $k$

\begin{algorithm}
	\SetAlgoLined
	\KwIn{$A[1\cdots n]$ where $A[j]\in {1,2,\cdots,k}$}
	\KwOut{$B[1\cdots n]$, sorted}
	\SetKwFunction{CountingSort}{Counting-Sort}
	
	\CountingSort{$A, B, k$}{
	
	Let $C[1\cdots k]$ be a new array
	
	\For( // Initialize Counters){$i \gets 1$ to $k$}{$C[i] \gets 0$}
	
	\For( // Count the number of each element){$j \gets 1$ to $n$}{$C[A[j]] \gets C[A[j]] + 1$}
	
	\For( // Count the accumulative number of elements){$i \gets 2$ to $k$}{$C[i] \gets C[i] + C[i-1]$}
	
	\For( // Move the items into proper location){$j \gets n$ to 1}{
	
		$B[C[A[j]]] \gets A[j]$
		
		$C[A[j]] \gets C[A[j]] - 1$
	
		}
	
	}
	
	\caption{Counting-Sort Algorithm}
\end{algorithm}

\textbf{Time Complexity:} $\Theta(n+k)$

\textbf{Space Complexity:} $\Theta(n+k)$

\newpage

\textbf{Radix-Sort}

\begin{algorithm}
	\SetAlgoLined
	\KwIn{An array of $n$ numbers, each has at most $d$ digits}
	\KwOut{A sorted array}
	\SetKwFunction{RadixSort}{Radix-Sort}
	\RadixSort{$A, d$}{
	
	\For{$i \gets 1$ to $d$}{
	
		Use Counting-Sort to sort array $A$ on digit $i$
	
		}
		
	}
	
	\caption{Radix-Sort Algorithm}
\end{algorithm}

\textbf{Time Complexity:} $\Theta(d(n+k))$

\subsection{Sorting Reprise \& Comparison}

\begin{center}
\renewcommand{\arraystretch}{1.5}
\begin{tabular}{|c|c|c|c|c|c|}
	\hline
	& Insertion Sort & Merge Sort & Quick Sort & Heap Sort & Radix Sort \\
	\hline
	Running Time & $\Theta(n^2)$ & $\Theta(n\log n)$ & $\Theta(n\log n)$ & $\Theta(n\log n)$ & $\Theta(d(n+k))$ \\
	\hline
	Randomized & No & No & Yes & No & No \\
	\hline
	Working Space & $\Theta(1)$ & $\Theta(n)$ & $\Theta(\log n)$ & $\Theta(1)$ & $\Theta(n+k)$ \\
	\hline
	Comparison-Based & Yes & Yes & Yes & Yes & No \\
	\hline
	Stable & Yes & Yes & No & No & Yes \\
	\hline
	Cache Performance & Good & Good & Good & Bad & Bad \\
	\hline
	Parallelization & No & Excellent & Good & No & No \\
	\hline
\end{tabular}
\end{center}

\newpage

\section{Greedy Algorithms}

\subsection{Basic Greedy Algorithms}

A greedy algorithm always makes the choice that looks best at the moment and adds it to the current partial solution.

Greedy algorithms don't always yield optimal solutions, but when they do, they're usually the simplest and most efficient algorithms available.

Usually, greedy algorithms involve a sorting step that dominates the total cost.

\begin{formal}{Brown}{brownshade}
	
	\textbf{Example: Interval Scheduling}

	Job $j$ starts at $s_j$ and finishes at $f_j$.

	Two jobs are compatible if they don't overlap.

	Goal: Find maximum size subset \textbf{(Note: Not the longest duration)} of mutually compatible jobs.

\end{formal}

\begin{figure}[h]
	\centering
	\includegraphics[width=0.6\textwidth]{img5-1}
\end{figure}

\textbf{Three Possible Rules:}

$\bullet$ [Earliest Start Time] Consider jobs in increasing order of start time $s_j$.

$\bullet$ [Shortest Interval] Consider jobs in increasing order of duration $f_j - s_j$.

$\bullet$ [Fewest Conflicts] Consider jobs in increasing order of number of conflicts $c_j$ with other jobs.

\begin{figure}[h]
	\centering
	\includegraphics[width=0.8\textwidth]{img5-2}
\end{figure}

All three rules may not yield optimal solutions.

\newpage

\textbf{Correct Greedy Algorithm:}

Consider jobs in increasing order of finish time $f_j$. Take each job if compatible with all previously taken jobs.
\begin{figure}[h]
	\centering
	\includegraphics[width=0.6\textwidth]{img5-3}
\end{figure}
\begin{algorithm}
	\SetAlgoLined
	Sort jobs by finish time $f_j$, i.e. $f_1 \leq f_2 \leq \cdots \leq f_n$

	$A \gets \varnothing$, $last \gets 0$

	\For{$j \gets 1$ to $n$}{
	
		\If{$s_j \geq last$}{
		
			$A \gets A \cup \{j\}$
			
			$last \gets f_j$
		
		}
	
	}

	\Return{$A$}

	\caption{Greedy Algorithm}
\end{algorithm}

See Page 13 of \href{C:/Users/user/OneDrive\%20-\%20HKUST\%20Connect/University/Computer/Design\%20and\%20Analysis\%20of\%20Algorithms/Lecture\%20Notes/11_Greedy_all.pdf\#page=13}{11\_Greedy\_all.pdf} for the proof.

\begin{formal}{Brown}{brownshade}
	
	\textbf{Example: The Fractional Knapsack Problem}

	Input: Set of $n$ items: item $i$ has weight $w_i$ and value $v_i$, and a knapsack with capacity $W$.

	Goal: Find $0 \leq x_1, \dots, x_n \leq 1$ to maximize $\sum_{i=1}^n v_i x_i$ subject to $\sum_{i=1}^n w_i x_i \leq W$.
	(Note: $x_i$ is the fraction of item $i$ to be taken)

	$\bullet$ The $x_i$ must be 0 or 1: The 0/1 knapsack problem.

	$\bullet$ The $x_i$ can be any value in [0,1]: The fractional knapsack problem.

\end{formal}

\begin{algorithm}
	\SetAlgoLined
	\SetKwFunction{FractionalKnapsack}{Fractional-Knapsack}
	\FractionalKnapsack{$w, v, W, x[]$}{
	
		Sort $\frac{v_i}{w_1}$ so that $\frac{v_1}{w_1} \geq \frac{v_2}{w_2} \geq \cdots \geq \frac{v_n}{w_n}$

		\For{$i \gets 1$ to $n$}{

			\If{$w_i$ < W}{

				$x_i \gets 1$

				$W \gets W - w_i$

			}

			\Else{

				$x_i \gets W / w_i$

				\Return{$x$}

			}

		}

		\Return{$x$}
	
	}
	
	\caption{Fractional-Knapsack Algorithm}
\end{algorithm}

\newpage

\begin{formal}{Brown}{brownshade}
	
	\textbf{Example: Hiking Problem}

	Suppose you are going on a hiking trip over multiple days. For safety reasons you can only hike during daytime. You can travel at most $d$ kilometers per day, and there are $n$ camping sites along the hiking trail where you can make stops at night.
	Assuming the starting point of the trail is at position $x_0 = 0$, the camping sites are at locations $x_1, \cdots, x_n$, and the end of the trail is at position $x_n$.
	Design an $O(n)$-time algorithm to find a plan that uses the minimum number of days to finish the trip. You can assume that $x_{i+1} − x_i \leq d$ for all $i$ (otherwise there is no solution).

	\textbf{Idea:} For each day $i$, stop at the furthest camping site, i.e. stop at the largest $x_j$ such that $x_j$ minus the start location of day $i$ is at most $d$.

\end{formal}

\begin{formal}{Brown}{brownshade}
	
	\textbf{Example: Interval Partitioning}

	Lecture $j$ starts at $s_j$ and finishes at $f_j$. Two lectures are compatible if they don't overlap. Goal: Find minimum number of classrooms to schedule all lectures.

	\textbf{Idea:} Sort the class by start time. Insert in order, opening new classroom when needed.

\end{formal}

\subsection{Huffman Coding}

\begin{formal}{Brown}{brownshade}
	
	\textbf{Example: Huffman Coding}

	\textbf{Input:} A set of characters and their frequencies.

	\textbf{Goal:} Find a prefix-free binary code (i.e. no codeword is a prefix of another) with minimum expected codeword length.

	\textbf{Rigorous Problem Definition:} Given an alphabet $A$ of $n$ characters $a_1,\cdots,a_n$ with weights $f(a_1),\cdots,f(a_n)$, find a binary tree $T$ with $n$ leaves labeled $a_1,\cdots,a_n$ such that
	\[
		B(T) = \sum_{i=1}^n f(a_i) \cdot d_T(a_i)
	\]
	
	is minimized, where $d_T(a_i)$ is the depth of leaf $a_i$ in $T$.
	
	\textbf{Greedy Idea:}

	$\bullet$ Pick two characters $x, y$ from $A$ with the smallest weights
	
	$\bullet$ Create a subtree that has these two characters as leaves

	$\bullet$ Label the root of this subtree as $z$ and set $f(z)\gets f(x)+f(y)$

	$\bullet$ Remove $x$ and $y$ from $A$ and add $z$ to $A$

	$\bullet$ Repeat until only one character is left

\end{formal}

See Page 13 of \href{C:/Users/user/OneDrive\%20-\%20HKUST\%20Connect/University/Computer/Design\%20and\%20Analysis\%20of\%20Algorithms/Lecture\%20Notes/12_Huffman_all.pdf\#page=13}{12\_Huffman\_all.pdf} for the proof.

\subsection{Stable Matching}

\begin{formal}{Brown}{brownshade}
	
	\textbf{Example: Stable Matching Problem}

	\textbf{Problem:} Finding a stable matching between two equally sized of elements given an ordering of preferences for each element. A matching is a bijection from the elements of one set to the elements of the other set.

	\textbf{Input:} Two sets $A$ and $B$ of equal size $n$, each with a strict ordering of preferences for the elements of the other set.

	\textbf{Output:} A matching $M$ between $A$ and $B$ such that there is no pair $(a, b)$ and $(a', b')$ in $M$ such that $a$ prefers $b'$ to $b$ and $b'$ prefers $a$ to $a'$.

\end{formal}

\newpage

\subsubsection*{Gale-Shapley Algorithm [Gale-Shapley 1962]}

Intuitive algorithm that guarantees to find a stable matching.

Also known as the deferred acceptance algorithm or propose-and-reject algorithm.

\begin{algorithm}
	\SetAlgoLined
	\SetKwFunction{GaleShapley}{Gale-Shapley}
	\GaleShapley{}{
	
		Initialize each participant (employers and applicants) to be free.

		\While{some employer is free and has an applicant to send an offer to}{

			Choose such an employer e

			a = 1st applicant on e's list to whom e has not yet sent an offer

			\If{a is free}{
				assign e and a to be matched
			}
			\ElseIf{a perfers e to the current employer e'}{
				assign e and a to be matched, and e' to be free
			}
			\Else{
				a rejects e
			}

		}

	}
	
	\caption{Gale-Shapley Algorithm}
\end{algorithm}

\textbf{Time Complexity:} Algorithm terminates after at most $n^2$ iterations of while loop, as each employer can only send at most 1 offer to each of the $n$ applicants.

\textbf{Efficient Implementation Details:}

To evaluate whether a perfers e to the current employer e', we can create inverse of preference list of employers for each applicant. Such structure yields a constant time access for comparison and requires $O(n^2)$ (Same as the current time complexity) for all applicants.

\textbf{Note:}

$\bullet$ For a given problem instance, several stable matchings might exist. All executions of Gale-Shapley (for different orders in which employers send offer) yield the same stable matching result, which is optimal for the employers. (i.e. each employer gets the best possible partner in any possible stable matching)

$\bullet$ To get an applicant optimal algorithm, let applicants apply and employers accept/reject (apply the algorithm in reverse order)

$\bullet$ Suppose the graph is not bi-partite. i.e. for each of the $2n$ person, we have the list of preferences, over the remaining $2n-1$ person, then there may not be a stable matching.

\begin{figure}[h]
	\centering
	\includegraphics[width=0.6\textwidth]{img5-4}
\end{figure}

\section{Dynamic Programming}

\subsection{1D Dynamic Programming}














\subsection{2D Dynamic Programming}

\subsection{Dynamic Programming over Intervals}

\subsection{Summary of Dynamic Programming}


















\newpage

\section{Graph Algorithms}

\subsection{Graph Introduction}

\subsubsection{Finding Euler Path}

\textbf{Graph} $G = (V, E)$

\textbf{Assumption:} In most cases we assume simple graphs, i.e. no self-loops and no parallel edges. (at most one or two edges between any two vertices in undirected or directed graph)

$\bullet$ \textbf{Undirected Graph:} $\sum_{v\in V} \deg(v) = 2E$

$\bullet$ \textbf{Directed Graph:} $\sum_{v\in V} \deg^{out}(v) = \deg^{in}(v) = E$

\textbf{Theorem:} A (multi)graph has such a path (known as an Euler path) iff it contains exactly 0 or 2 vertices with an odd degree.

\textbf{Hierholzer's Algorithm:} Find an Euler path in $O(E)$ time.
\begin{algorithm}
	\SetAlgoLined
	\SetKwFunction{FindPath}{FindPath}
	
	$u \gets$ any odd-degree vertex

	\If{$u$ does not exist}{

		$u \gets$ any vertex

	}

	\FindPath{u}

	\While{there are still edges not yet taken}{

		$u \gets$ any previously seen vertex that is endpoint of an unused edge

		$p\gets$\FindPath{u}

		insert $p$ into the existing path at $u$

	}

	\vspace*{1em}

	\FindPath{u}:{

		\While{$u$ has an edge not yet taken}{

		take that edge

		$u \gets v$

		}

	}
	
	\caption{Hierholzer's Algorithm}
\end{algorithm}

\subsubsection{Graph Representation}

\textbf{Adjacency List:} For each vertex $v$, store a list of all vertices $u$ such that $(v, u) \in E$.

$\bullet$ \textbf{Space Complexity:} $O(V+E)$

$\bullet$ More commonly used, as most graphs are sparse

\textbf{Adjacency Matrix:} $A[i][j] = 1$ if $(i, j) \in E$, $A[i][j] = 0$ otherwise.

$\bullet$ \textbf{Space Complexity:} $O(V^2)$

\subsubsection{Path and Connectivity}

\textbf{Path:} A sequence of vertices $v_1, v_2, \cdots, v_k$ such that $(v_i, v_{i+1}) \in E$ for all $i = 1, \cdots, k-1$. The length of such path is $k-1$.

\textbf{Simple Path:} A path with no repeated vertices.

\textbf{Undirected Connected Graph:} A graph is connected if there is a path between every pair of vertices.

\textbf{Directed Strongly Connected Graph:} A directed graph is strongly connected if there is a path from $u$ to $v$ and a path from $v$ to $u$ for every pair of vertices $u$ and $v$.

\textbf{Directed Weakly Connected Graph:} A directed graph is weakly connected if replacing all of its directed edges with undirected edges produces a connected (undirected) graph.

\textbf{Cycle:} A cycle is a path $v_1, v_2, \cdots, v_k$ such that $(v_1, v_k) \in E$.

\textbf{Distance:} The distance between two vertices $u$ and $v$ is the length of the shortest path between them.

\subsubsection{Trees}

\textbf{Tree:} A tree is an undirected graph that is connected and acyclic (not containing a cycle).

\textbf{Rooted Tree:} A rooted tree is a tree in which one vertex has been designated the root. Every edge is directed away from the root.

\textbf{Leaf:} A leaf is a vertex of degree 1.

\textbf{Parent, Child, Ancestor, Descendant:} If $(u, v) \in E$, then $u$ is the parent of $v$ and $v$ is the child of $u$. $u$ is an ancestor of $v$ and $v$ is a descendant of $u$.

\textbf{Forest:} A forest is an undirected graph that is acyclic.

\begin{theorem}
	For any undirected graph $G = (V, E)$, the following statements are equivalent:
	
	$\bullet$ $G$ is a tree
	
	$\bullet$ $G$ is connected and $|E| = |V| - 1$
	
	$\bullet$ $G$ is acyclic and $|E| = |V| - 1$
	
	$\bullet$ Any two vertices of $G$ are connected by a unique simple path
	
	$\bullet$ $G$ is connected and removing any edge disconnects $G$
	
	$\bullet$ $G$ is acyclic and adding any edge creates a cycle
	
	$\bullet$ $G$ is connected and has no cycles
	
	$\bullet$ $G$ is acyclic and has $|E| = |V| - 1$
	
	$\bullet$ $G$ is connected, and for any vertices $u$ and $v$, there is a unique simple path from $u$ to $v$
\end{theorem}

\subsection{Breadth First Search}

\textbf{Idea:} Explore outward from $s$ in all possible directions, adding nodes one "layer" at a time.

\begin{wrapfigure}{r}{0.3\textwidth}
	\centering
	\includegraphics[width=0.3\textwidth]{img7-1}
\end{wrapfigure}

\textbf{Property:} $L_{i+1}$ contains all nodes that do not belong to an earlier layer, and that have an edge to a node in $L_i$.

\textbf{Theorem:}  For each $i$, $L_i$ consists of all nodes at distance exactly $i$ from $s$. There is a path from $s$ to $t$ iff $t$ appears in some layer, where the distance from $u$ to $v$ is the number of edges on the shortest path from $u$ to $v$.

\begin{algorithm}
	\SetAlgoLined
	\SetKwFunction{BFS}{BFS}
	\SetKwFunction{Enqueue}{Enqueue}
	\BFS{G, s}{

		\ForEach(// Initialize the discoverys state, distance and parent except the starting point){$u \in V-\{s\}$}{

			$u.color \gets WHITE$

			$u.d \gets \infty$

			$u.p \gets NIL$

		}

		$s.color \gets GRAY$

		$s.d \gets 0$

		Initialize an empty queue $Q$ // Temporary storage of the vertices to be processed

		\Enqueue{$Q, s$}{

			\While{$Q \neq \varnothing$}{

				$u \gets$ Dequeue($Q$) // Dequeue the first element in the queue (FIFO), reduce the required space for the queue

				\ForEach{$v \in G.Adj[u]$}{

					\If{$v.color = WHITE$}{

						$v.color \gets GRAY$ // Discovered but unprocessed

						$v.d \gets u.d + 1$

						$v.p \gets u$

						\Enqueue{$Q, v$}

					}

				}

				$u.color \gets BLACK$ // Processed

			}

		}

	}
	
	\caption{BFS Algorithm}
\end{algorithm}

\textbf{Time Complexity:} $\sum_u (1+\deg{u}) = \Theta(E)$ if the graph is connected.

To transfer through non-connected graphs, simply check if any vertex is still white after the first BFS, if so, run BFS again starting from that vertex.

\subsubsection{Strong Connectivity in Directed Graphs}

\textbf{Def.} Node $u$ and $v$ are mutually reachable if there is a path from $u$ to $v$ and a path from $v$ to $u$.

\textbf{Def.} A graph is strongly connected if every pair of nodes is mutually reachable.

\textbf{Observation 1:} A graph $G$ is strongly connected if there exists such a vertex $v$ that every other vertex forms a mutually-reachable pair with $v$. In this case, every other vertex has the similar property.

\textbf{Observation 2:} A graph $G$ is strongly connected if and only if every vertex $v$ is mutually reachable with every other vertex.

\textbf{Idea to check strong connectivity in directed graphs:} Run BFS from $v$, then \textbf{REVERSE ALL THE EDGES} and run BFS again from $v$. If all vertices are visited in both BFS, then the graph is strongly connected.

\textbf{Note:} Given the adjacency list, one can convert $G$ to its reverse $G^T$ within $O(V+E)$ time.

\textbf{Time Complexity:} $O(E)$

\subsubsection{Strongly Connected Components in $O(VE)$ Time}

\begin{algorithm}
	\SetAlgoLined
	\SetKwFunction{StronglyConnectedComponents}{StronglyConnectedComponents}
	\StronglyConnectedComponents{G, s}{

		create $G^T$ // Reverse all the edges

		\While{$G$ has unvisited vertices}{

			Run BFS on $G$ starting from an unvisited vertex $v$

			Run BFS on $G^T$ starting from an unvisited vertex $v$

			$C \gets$ all visited vertices in both BFSs

			output $C$ as a strongly connected component

			remove $C$ and all its edges from $G$ and $G^T$

		}

	}
	
	\caption{Strongly Connected Components}
\end{algorithm}

\textbf{Time Complexity:} $O(VE)$

\subsubsection{Strongly Connected Components in $O(V+E)$ Time}

Let $C$ and $C'$ be distinct strongly connected components in directed graph $G=(V, E)$.

\textbf{Observation 1:} Let $u, v \in C$ and $u', v' \in C'$. If there is an edge from $u$ to $u'$, then there is no edge from $v'$ to $v$.

\textbf{Observation 2:} Let $d(U) = \min{u.d: u \in U}$ being the discovery time and $f(U) = \max{u.f: u \in U}$ being the finish time of a set of vertices $U$. Suppose $u \in C$ and $v \in C'$ with $(u, v) \in E$. Then $f(C) > f(C')$. (i.e. $C$ is finished later than $C'$)

\textbf{Observation 3:} Suppoose $f(C) > f(C')$, then $E^T$ contains no edge from $C$ to $C'$.

\textbf{Key Point:} In general, when the depth-first search of 
$G^T$ in line 3 visits any strongly connected component, any edges out of that component must be to components that the search has already visited. Each depth-first tree, therefore, corresponds to exactly one strongly connected component.

\begin{algorithm}
	\SetAlgoLined
	\SetKwFunction{StronglyConnectedComponents}{StronglyConnectedComponents}
	\StronglyConnectedComponents{G, s}{

		call $DFS(G)$ to compute finish times $u.f$ for each vertex $u$

		create $G^T$ // Reverse all the edges

		call $DFS(G^T)$, but consider the vertices in decreasing order of $u.f$ in the main loop of DFS (computed in line 1)

		output the vertices of each tree in the depth-first forest formed in line 3 as a separate strongly connected component

	}

	\caption{Strongly Connected Components Modified}
\end{algorithm}

\textbf{Note:} See next subsection for the DFS algorithm.

\textbf{Time Complexity:} $\Theta(V+E)$

\newpage

\begin{formal}{Brown}{brownshade}
	
	\textbf{Example: Check Bipartite Graph}

	\textbf{Problem:} Given an undirected graph $G = (V, E)$, check if $G$ is bipartite.

	\textbf{Idea:} Run BFS from any vertex. Use $d[v]$ to store the distance from the root to any other vertex $v$. Set $S$ to be the set of all vertices with even $d[v]$, and $V-S$ to be the set of all vertices with odd $d[v]$.

	$\bullet$ $G$ is partite if and only if all edges $(u, v)$ in the graph satisfy that the parity of $d[u]$ and $d[v]$ are different.

	$\bullet$ Alternatively, whether $G$ is bipartite is equivalent to whether $G$ does not contain any odd cycle. To check so, simply do BFS to find if there is any edge, both of whose endpoints are in the same layer.
	
\end{formal}

\subsection{Depth First Search}

\begin{algorithm}
	\SetAlgoLined
	\SetKwFunction{DFS}{DFS}
	\SetKwFunction{DFSVisit}{DFSVisit}
	\DFS{G}{

		\ForEach{$u \in V$}{

			$u.color \gets WHITE$

			$u.p \gets NIL$

		}

		$time \gets 0$

		\ForEach{$u \in V$}{

			\If{$u.color = WHITE$}{

				\DFSVisit{$u$}

			}

		}

	}

	\vspace*{1em}
	
	\DFSVisit{$u$}{

		$time \gets time + 1$

		$u.d \gets time$

		$u.color \gets GRAY$

		\ForEach{$v \in G.Adj[u]$}{

			\If{$v.color = WHITE$}{

				$v.p \gets u$

				\DFSVisit{$v$}

			}

		}

		$u.color \gets BLACK$

		$time \gets time + 1$

		$u.f \gets time$

	}
	
	\caption{DFS Algorithm}

\end{algorithm}

\subsubsection{Cycle Detection in Undirected Graphs}

\begin{formal}{Brown}{brownshade}
	
	\textbf{Example: Cycle Detection}

	\textbf{Problem:} Given an undirected graph $G = (V, E)$, check if $G$ contains a cycle.

	\textbf{Idea:} A tree (connected and acyclic) has $|E| = |V| - 1$. If $G$ contains a cycle, then $|E| > |V| - 1$. Therefore, we can check if $|E| > |V| - 1$ after running DFS.

	\textbf{Time Complexity:} $\Theta(V+E)$

\end{formal}

\begin{formal}{Brown}{brownshade}
	
	\textbf{Example: Cycle Detection}

	\textbf{Problem:} Given an undirected graph $G = (V, E)$, check if $G$ contains a cycle. If so, find a cycle.

	\textbf{Def.} All edges, after running BFS or DFS, can be classified into three categories: tree edges, back edges and forward/cross edges.

	\textbf{Tree edges:} Traversed by BFS/DFS.

	\textbf{Back edges:} Connecting a node with one of its ancestors in the BFS/DFS tree which is not a tree edge.

	\textbf{Forward/Cross edges:} Connecting two nodes with no ancestor/descendant relationship in the BFS/DFS tree.

\end{formal}

\begin{theorem}
	In a BFS on an undirected graph, there are no back edges.
\end{theorem}

\begin{theorem}
	In a DFS on an undirected graph, there are no cross edges.
\end{theorem}

\begin{formal}{Brown}{brownshade}

	\textbf{Idea:} Run DFS. If there is a back edge, then there is a cycle. To find a cycle, simply find the path from the current vertex to the ancestor vertex. If no, then there is no cycle.

	\noindent \textbf{Time Complexity:} $\Theta(V)$

\end{formal}

\begin{algorithm}
	\SetAlgoLined
	\SetKwFunction{CycleDetection}{CycleDetection}
	\SetKwFunction{DFSVisit}{DFSVisit}
	\CycleDetection{G}{

		\ForEach{$u \in V$}{

			$u.color \gets WHITE$

			$u.p \gets NIL$

		}

		\ForEach{$u \in V$}{

			\If{$u.color = WHITE$}{

				\DFSVisit{$u$}

			}

		}

		\Return{"No Cycle"}

	}

	\vspace*{1em}
	
	\DFSVisit{$u$}{

		$u.color \gets GRAY$

		\ForEach{$v \in G.Adj[u]$}{

			\If{$v.color = WHITE$}{

				$v.p \gets u$

				\DFSVisit{$v$}

			}

			\ElseIf(// back edge (u, v)){$v \neq u.p$}{

				output "Cycle detected"

				\While{$u \neq v$}{
				
					output $u$

					$u \gets u.p$

				}

				output $v$

				\Return

			}

		$u.color \gets BLACK$

		}

	}
	
	\caption{DFS Algorithm for Cycle Detection}

\end{algorithm}

\newpage
\subsection{Topological Sort}

\textbf{Def.} Directed acyclic graph (DAG) is a directed graph with no cycles.

\textbf{Def.} A topological sort of a DAG $G = (V, E)$ is a linear ordering of all its vertices such that if $G$ contains an edge $(u, v)$, then $u$ appears before $v$ in the ordering.

\textbf{Idea:} A DAG must contain at least one vertex with no incoming edges. Output a vertex $u$ with in-degree zero in current graph. Remove this vertex and all its outgoing edges. Repeat until all vertices are removed.

\begin{algorithm}
	\SetAlgoLined
	\SetKwFunction{TopologicalSort}{TopologicalSort}
	\TopologicalSort{G}{

		Initialize an empty queue $Q$
		
		\ForEach{$u \in V$}{

			\If{in-degree($u$) = 0}{

				\Enqueue{$Q, u$} // Enqueue all vertices with in-degree 0

			}
		
		}

		\While{$Q \neq \varnothing$}{

			$u \gets$ Dequeue($Q$)

			output $u$

			\ForEach{$v \in G.Adj[u]$}{

				in-degree($v$) $\gets$ in-degree($v$) - 1 // remove $u$'s outgoing edges

				\If{in-degree($v$) = 0}{

					\Enqueue{$Q, v$}

				}

			}

		}

	}
	
	\caption{Topological Sort}

\end{algorithm}

For each vertex, we need to check all its outgoing edges $\sum_{v\in V} out-degree(v) = E$.

\textbf{Time complexity:} $O(V+E)$

\textbf{Alternative Implementation Using DFS:} Apply DFS from a node with in-degree 0. Output the vertices in reverse order of their finish times.

\newpage
\subsection{Minimum Spanning Tree}

\subsubsection{Definition}

\textbf{Spanning Tree:} Given a connected undirected graph $G = (V, E)$, a spanning tree of $G$ is a subgraph that is a tree and connects all the vertices together.

\textbf{Minimum Spanning Tree:} A minimum spanning tree (MST) or minimum weight spanning tree $S$ is a subset of the edges $T \subseteq E$ of a connected, edge-weighted (un)directed graph that connects all the vertices together, with the minimum possible total edge weight $\sum w(e)$. 

\subsubsection{Prim's Algorithm}

\textbf{Idea:}

$\bullet$ Initialize the set $S$ to have any single vertex $s$. Initialize $T$ to be empty.

$\bullet$ Add minimum cost edge $e = (u, v)$ with $u \in S$ and $v \notin S$ to $T$.

$\bullet$ Add $v$ to $S$.

$\bullet$ Repeat until $S = V$.

\begin{algorithm}
	\SetAlgoLined
	\SetKwFunction{Prim}{Prim}
	\Prim{G, root}{

		\ForEach{$u \in V$}{

			$u.key \gets \infty$

			$u.p \gets NIL$

			$u.color \gets WHITE$

		}

		$root.key \gets 0$

		Initialize an empty min-priority queue $Q$ // e.g. Use min-heap to implement so that we can conduct extract-min method

		\While{$Q \neq \varnothing$}{

			$u \gets$ Extract-Min($Q$)

			$u.color \gets BLACK$

			\ForEach{$v \in G.Adj[u]$}{

				\If{$v.color = WHITE$ and $w(u, v) < v.key$}{

					$v.p \gets u$

					$v.key \gets w(u, v)$ // Let $v.key$ specify the minimum weight of any edge connecting $v$ to a vertex already processed.

					Decrease-Key($Q, v, w(u, v)$) // Changes the value in the min-priority queue (or min-heap), same as the above line. See page 17 for Decrease-Key method.

				}

			}

		}

	}
	
	\caption{Prim's Algorithm}

\end{algorithm}

\textbf{Time Complexity:} $O(E\log V)$

\subsubsection{The Cut Lemma}

\textbf{Assumption:} All edge weights are distinct.

\begin{lemma}
	Let $S$ be any subset of nodes, and let $e = (u, v)$ be the minimum weight edge connecting $S$ to $V-S$. Then, every minimum spanning tree must contain the edge $e$.
\end{lemma}

\subsubsection{Kruskal's Algorithm}

\textbf{Idea:} Start with an empty tree $T$. Add edges in increasing order of weight (according to the cut lemma), skipping those whose addition would create a cycle.

$\bullet$ To check whether the new edge forms a cycle, using DFS would cost a total time of $O(E\cdot V)$. Alternatively, we can use "union-find" data structure to check it.

\newpage
\textbf{Union-Find Data Structure:}

$\bullet$ Maintain a collection of disjoint sets that support the following operations:

$\bullet$ \textbf{Find-Set($u$):} Given a node $u$, find a set which contains $u$.

$\bullet$ \textbf{Union($u, v$):} Given two nodes $u$ and $v$, merge the two sets containing $u$ and $v$.

\begin{figure}[h]
	\centering
	\includegraphics[width=0.6\textwidth]{img7-2}
\end{figure}

\textbf{Methods of Union-Find Data Structure:}

$\bullet$ Initalization: Make-Set($x$): Set the parent to itself, and height to 0

$\bullet$ Find-Set($x$): Return the root of the tree containing $x$ by calling its parent.

$\bullet$ Union($x, y$): Let $a, b$ be the roots of the trees containing $x$ and $y$ with $a.height \leq b.height$. Make the shorter tree $a$ subtree of the taller tree by setting $a.p = b$.

\begin{theorem}
	The running time fo Find-Set and Union are both $O(\log n)$. Specifically, for a tree with height $h$, it contains at least $2^h$ nodes.
\end{theorem}

\begin{algorithm}
	\SetAlgoLined
	\SetKwFunction{Kruskal}{Kruskal}
	\Kruskal{G}{

		\ForEach{$u \in V$}{

			Make-Set($u$)

		}

		sort the edges of $G$ into increasing order by its weight

		\ForEach{edge $(u, v) \in E$ in the above order}{

			\If{Find-Set($u$) $\neq$ Find-Set($v$)}{

				output edge $u, v$

				Union($u, v$)

			}

		}

	}
	
	\caption{Kruskal's Algorithm}

\end{algorithm}

\textbf{Time Complexity:} $O(E\log E + E\log V) = O(E\log V)$

\textbf{Note:} If the edges are already sorted, then the time complexity can be reduced to be closed to $O(E)$.

\textbf{Remark:}

$\bullet$ When the distinct-weight-assumption is removed, the only thing that needs to be changed is that, instead of choosing \textbf{the} smallest cost edge, we choose \textbf{a} smallest cost edge that does not create a cycle.

$\bullet$ If the graph $G$ is an undirected connected graph with distinct edge weights. Then, there is a unique MST for $G$.

\begin{formal}{Brown}{brownshade}

	\textbf{Example: Bottleneck Weight of MST}

	\textbf{Theorem:} Let $G = (V,E)$ be a connected undirected graph with weights on the edges. The bottleneck weight of any spanning tree $T$ of $G$ is the maximum weight of an edge in $T$. Prove that the minimum spanning tree (MST) minimizes the bottleneck weight over all spanning trees.

	\textbf{Idea:} Suppose the heaviest weight $e$ with weight $w(e)$ connects two components $A$ and $B$, with $A \cup B = V$. Assume another MST $T'$ has a smaller bottleneck weight. Then, there must be an edge $e'$ in $T'$ with weight $w(e')$ that connects $A$ and $B$. Remove $e$ from $T$ and add $e'$ to $T$ forms a new spanning tree $T''$ with smaller total weight. This contradicts the assumption that $T$ is an MST.

\end{formal}

\begin{formal}{Brown}{brownshade}

	\textbf{Example: Euclidean Traveling Salesman Problem}

	\textbf{Input:} Undirected fully-connected graph $G = (V, E)$ with edge cost $C(e)$ for each $e \in E$.

	\textbf{Output:} A minimum-cost cycle that visits each vertex exactly once.

	\textbf{Notes: Euclidean} Traveling Salesman implies that the cost is the Euclidean distance between the two vertices, which satisfies the triangle inequality: $C(u, v) \leq C(u, w) + C(w, v)$.

	\textbf{Remark:} This problem is NP-hard. There is no known polynomial-time algorithm that solves it. There are two approximate solutions using MST.

\end{formal}

\begin{figure}[h]
	\centering
	\begin{subfigure}[b]{0.3\textwidth}
		\centering
		\includegraphics[width=\textwidth]{img7-3}
	\end{subfigure}
	\hfill
	\begin{subfigure}[b]{0.3\textwidth}
		\centering
		\includegraphics[width=\textwidth]{img7-4}
	\end{subfigure}
	\hfill
	\begin{subfigure}[b]{0.3\textwidth}
		\centering
		\includegraphics[width=\textwidth]{img7-5}
	\end{subfigure}
	\caption*{Euclidean Traveling Salesman Problem}
\end{figure}

\subsection{Shortest Paths}

\begin{figure}[h]
	\centering
	\includegraphics[width=0.5\textwidth]{img7-6}
	\caption*{An Overview of Shortest Path Algorithms}
\end{figure}
\begin{formal}{Brown}{brownshade}

	\textbf{Example: Shortest Path between Two Vertices}

	\textbf{Problem:} Given a directed graph $G = (V, E)$ with non-negative edge weights $w(e)$ for each $e \in E$, a source and a destination vertex $s,t \in V$, find the shortest path from $s$ to $t$.

	\textbf{Idea:} Run BFS. The shortest path from $s$ to $v$ is the path from $s$ to $v$ with the fewest edges.

	\textbf{Def:} $\delta(u, v)$ represents the length of the shortest path from $u$ to $v$.

\end{formal}

\begin{figure}[h]
	\centering
	\includegraphics[width=0.4\textwidth]{img7-7}
\end{figure}
\begin{lemma}
	Let $P=(s, \cdots, u, \cdots, v)$ be a shortest $s-t$ path, then the subpaths $P_1 = (s, \cdots, u)$ and $P_2 = (u, \cdots, v)$ must be shortest $s-u$ and $u-t$ paths respectively.
\end{lemma}

\subsubsection{Bellman Ford Algorithm}

\textbf{Idea:} Relax all edges $|V|-1$ times. The shortest path from $s$ to $v$ is the path from $s$ to $v$ with the fewest edges.

\begin{algorithm}
	\SetAlgoLined
	\SetKwFunction{BellmanFord}{BellmanFord}
	\BellmanFord{G, s}{

		\ForEach{$u \in V$}{

			$u.d \gets \infty$

			$u.p \gets NIL$

		}

		$s.d \gets 0$

		\For{$i \gets 1$ \KwTo $|V|-1$}{

			\ForEach{$(u, v) \in E$}{

				Relax($u, v, w$)

			}

		}

		\ForEach{$(u, v) \in E$}{

			\If{$v.d > u.d + w(u, v)$}{

				\Return{"Negative Cycle"}

			}

		}

	}
	
	\caption{Bellman Ford Algorithm}

\end{algorithm}





\subsection{Maximum Flow and Bipartite Matchings}

\begin{comment}
\section{AVL Trees}

\section{Basic String Matching}

\section{Hashing}
\end{comment}

\newpage

\section*{Homework 1}

\textbf{Name: LIN, Xuanyu, SID: 20838295, Email Address: xlinbf@connect.ust.hk}

\begin{Problem}
	
	For each pair of expressions $(A, B)$ below, indicate whether $A$
	is $O, \Omega, \text{or } \Theta$ of B. List all applicable relations. No explanation is needed.
	
	\noindent (a) $A = n^3-100n$, $B = n^2+50n$
	
	\noindent (b) $A = \log_2(n^2)$, $B = \log_{2.7}(n^4)$
	
	\noindent (c) $A = 10^{10000}$, $B = \frac{n}{10^{10000}}$
	
	\noindent (d) $A = 2^{n\log n}$, $B = n^{10}+8n^2$
	
	\noindent (e) $A = 2^n$, $B = 2^{n+\log n}$
	
	\noindent (f) $A = 3^{3n}$, $B = 3^{2n}$
	
	\noindent (g) $A = (\sqrt{2})^{\log n}$, $B = \sqrt{\log n}$
	
\end{Problem}

\textbf{Solution.}
	
	(a) $A = \Omega(B)$
	
	(b) $A = O(B), A = \Omega(B), A = \Theta(B)$
	
	(c) $A = O(B)$
	
	(d) $A = \Omega(B)$
	
	(e) $A = O(B)$
	
	(f) $A = \Omega(B)$
	
	(g) $A = \Omega(B)$

\newpage

\begin{Problem}
	
	Derive asymptotic upper bounds for T(n) in the following recurrences. Make your bounds as tight as possible. You may assume that $n$ is a power of 2 for (a), $n$ is a power of 4 for (b), and $\sqrt{n}$ is always an integer for (c).
	
	\noindent (a) $T(1) = 1$; $T(n) = 4T(n/2) + n^2$ for $n>1$.
	
	\noindent (b) $T(1) = 1$; $T(n) = 16T(n/4) + n$ for $n>1$.
	
	\noindent (c) $T(2) = 1$; $T(n) = T(\sqrt{n}) + 1$ for $n>1$.
	
\end{Problem}

\textbf{Solution.}

(a)
$$
\begin{aligned}
	T(n) &= 4T(n/2) + n^2 = 4[4T(n/4) + (n/2)^2] + n^2 = 4\{4[4T(n/8) + (n/4)^2] + (n/2)^2\} + n^2\\
	&= 4\{4\{4\{\cdots [4T(1) + 2^2] + 4^2\} + \cdots + (n/4)^2\} + (n/2)^2\} + n^2\\
	&= 4^{\log_2 n} + 4^{\log_2 n - 1} \times 2^2 + 4^{\log_2 n - 2} \times 4^2 + \cdots + 4^{1} \times (n/2)^2 + n^2\\
	&= n^2 + \frac{n^2}{4} \times 2^2 + \frac{n^2}{4^2} \times 4^2 + \cdots + 4 \times (n/2)^2 + n^2\\
	&= n^2 (\log_2 n + 1) = O(n^2\log n)
\end{aligned}
$$

(b)
$$
\begin{aligned}
	T(n) &= 16T(n/4) + n = 16[16T(n/4^2) + n/4] + n = 16\{16[16T(n/4^3) + n/4^2] + n/4\} + n\\
	&= 16\{16\{16\{\cdots [16T(1) + 4] + 4^2\} + \cdots + n/4^2\} + n/4\} + n\\
	&= 16^{\log_4 n} + 16^{\log_4 n - 1} \times 4 + 16^{\log_4 n - 2} \times 4^2 + \cdots + 16^{1} \times n/4 + n\\
	&= n^2 + \frac{n^2}{4} + \frac{n^2}{4^2} + \cdots + 4n + n\\
	&= \frac{n-4n^2}{1-4} = \frac{4}{3} n^2 -\frac{1}{3} n = O(n^2)
\end{aligned}
$$

(c)
$$
\begin{aligned}
	T(n) &= T(\sqrt{n}) + 1 = T(n^{1/2^2}) + 2 = T(n^{1/2^3}) + 3 = \cdots = T(2) + \log_2 (\log_2 n) = O(\log_2 (\log_2 n))
\end{aligned}
$$

\newpage

\begin{Problem}
	
	\noindent (a) Describe a recursive algorithm that returns a list of all possible $n\times n$ binary arrays where $n$ is a positive input integer. An array is binary if each of its entry is either 0 or 1. You can either describe your algorithm in text or in a documented pseudocode. Make sure that your algorithm is recursive. Make sure that your description is understandable.
	
	\noindent (b) Write down the recurrence for the running time of your
	recursive algorithm in (a) with the boundary condition(s). Explain your notations. Solve your recurrence from scratch to obtain the
	the running time of your algorithm.
	
\end{Problem}

\textbf{Solution.}

(a) Main Idea: Recursively solve the problem by reducing the $k\times k$ array to $(k-1)\times (k-1)$ array. Then generate all the binary array of the remaining $1\times (k-1)$, $(k-1)\times 1$ and $1\times 1$ array. For each kind of array for the $(k-1)\times (k-1)$ array, we insert the remaining $(2k-1)$ elements into it, forming the $(k\times k)$ array.

\begin{algorithm}
	\SetAlgoLined
	\SetKwFunction{AllBinaryArrays}{AllBinaryArrays}
	\SetKwFunction{GenerateRemaining}{GenerateRemaining}
	\AllBinaryArrays{$n$}{
		
		EmptyArray $\gets$ array$[n][n]$
		
		ArrayList<Type=array$[n][n]$> $\gets [\ ]$
		
		\If{n = 1}{
		
			ArrayList.append(array$[n][n] = 0$, array$[n][n] = 1$) // Set the last element to 0 \& 1, others remaining 0
			
			\Return{ArrayList}
		
		}
		
		ArrayList\_1, ArrayList\_2, ArrayList\_3 $\gets$ \GenerateRemaining{$n$}
		
		PreviousArrayList$[\ ][2:n][2:n] \gets$ \AllBinaryArrays{$n-1$}
		
		// Insert the remaining $(2n-1)$ elements into the $n\times n$ array, forming all kinds of $(n\times n)$ array
		
		\ForEach{Combination of ArrayList\_1, ArrayList\_2, ArrayList\_3}{
		
			ArrayList.append(PreviousArrayList$[\ ][2:n][2:n]$.set(PreviousArrayList$[\ ][1][2:n]\gets$ ArrayList\_1, PreviousArrayList$[\ ][2:n][1]\gets$ ArrayList\_2, PreviousArrayList$[\ ][1][1]\gets$ ArrayList\_3))

		}
		
		\Return{ArrayList}
		
	}

	\vspace*{1em}
	
	/* Recursively generate all the kinds of $1\times (n-1)$, $(n-1)\times 1$ and $1\times 1$ array respectively */

	\GenerateRemaining{$n$}{
		
		ArrayList\_1<Type=array$[1][n-1]$> $\gets [\ ]$\\
		ArrayList\_2<Type=array$[n-1][1]$> $\gets [\ ]$\\
		ArrayList\_3<Type=array$[1][1]$> $\gets [\ ]$
		
		\If{$n=2$}{
		
			\Return{$[[0], [1]], [[0], [1]], [[0], [1]]$} // To be assigned to $1\times (n-1)$, $(n-1)\times 1$ and $1\times 1$ array

		}
		
		ArrayList\_1$[\ ][1][2:n-1]$, ArrayList\_2$[\ ][2:n-1][1]$, ArrayList\_3$[\ ][1][1]$ $\gets$ \GenerateRemaining{$n-1$} // Assign all possible cases of the previous arrays into all the array in the corresponing list
		
		// Set the new element inserted to be 0 and 1
		
		ArrayList\_1 = ArrayList\_1$[\ ][1][2:n-1]$.set$[\ ][1][1]\gets 0$ + ArrayList\_1$[\ ][1][2:n-1]$.set$[\ ][1][1]\gets 1$
		
		ArrayList\_2 = ArrayList\_2$[\ ][2:n-1][1]$.set$[\ ][1][1]\gets 0$ + ArrayList\_1$[\ ][2:n-1][1]$.set$[\ ][1][1]\gets 1$
		
		\Return{ArrayList\_1, ArrayList\_2, ArrayList\_3}
		
	}

	\underline{First Call:} \AllBinaryArrays{$n$}

	\caption{All $n\times n$ Binary Arrays}
\end{algorithm}

(b) \textbf{Recurrence:} Suppose $T(n) = T(n-1) + O(f(n))$

$f(n)$ contains generating the remaining $1\times (n-1)$, $(n-1)\times 1$ and $1\times 1$ arrays as well as inserting such arrays into the original $n\times n$ array. The first part requires $O(n)$ time as a simple recursion while the second part requires $O(n\times 2^n)$ time, considering the insertion time.

Thus,

$$
T(n) = T(n-1) + O(n\times 2^n) = \sum_{k=1}^n k\times 2^k = O(n2^n)
$$



\newpage

\begin{Problem}
	
	Let $A[1..n]$ be an array of $n$ elements. One can compare in $O(1)$ time two elements of $A$ to see if they are equal or not; however,
	the order relations $<$ and $>$ do not make sense. That is, one can check whether $A[i] = A[j]$ in $O(1)$ time, but the relations $A[i] < A[j]$ and $A[i] > A[j]$ are undefined and cannot be determined.
	
	\noindent In the tutorial you developed an $O(n\log n)$-time divide-and-conquer algorithm for finding a majority element of $A$ if one exists. In this assignment you need to generalize this problem.
	
	\noindent Let $k\in [1..n]$ be a fixed integer. An element of $A[1..n]$ is a k-major element if its number of occurrences in A is greater than $n/k$. For example, if $n = 30$, then a 10-major element should occur greater than 3 times (i.e., at least 4 times). Note that it is possible that no k-major exists for a particular k; it is also possible that there are multiple k-major elements for a particular k.
	
	\noindent This problem concerns with designing a divide-and-conquer algorithm for finding \textbf{all} 10-major elements in $A[1..n]$ in $O(n\log n)$ time; if there is no 10-major element, report so. Answer the following questions.
	
	(a) What is the maximum number of 10-major elements in
	$A[1..n]$? Explain.
	
	(b) Design a divide-and-conquer algorithm that finds all 10-major elements in $A[1..n]$ in $O(n\log n)$ time; if there is no 10-major element, your algorithm should report so. Recall that one can check whether $A[i] = A[j]$ in $O(1)$ time, but the relations $A[i] < A[j]$ and $A[i] > A[j]$ are undefined and cannot be computed.
	
	\noindent \textbf{Write your algorithm in documented pseudocode. Also, explain in text what your pseudocode does. Explain the correctness of your algorithm.}
	
	\noindent Since your algorithm uses the divide-and-conquer principle, it should
	be recursive in nature. That is, it should work on $A[1..n]$ in the
	first call to return all 10-major elements of $A[1..n]$, and in subsequent recursive calls, it may recurse on many subarrays $A[p..q]$ for some $p, q\in [1..n]$ to return all 10-major elements of $A[p..q]$
	
	\noindent Given a particular subarray $A[p..q]$, a 10-major element of $A[p..q]$ is not necessarily a 10-major element of $A[1..n]$. Conversely, a 10-major element of $A[1..n]$ is not necessarily a 10-major element of $A[p..q]$.
	
	(c) Derive a recurrence relation that describes the running time $T(n)$ of your algorithm. Explain your reasoning. State the boundary condition(s).
	
	(d) Solve your recurrence \textbf{from scratch} to show that $T(n) = O(n\log n)$.
	
\end{Problem}

\newpage

\textbf{Solution.}

(a) The maximum number of 10-major elements is 9. If there were 10 10-major elements in an array of $n$ numbers, each 10-major elements should appear at least $\lfloor n/10 \rfloor + 1$ times, resulting in a total of at least $10 \lfloor n/10 \rfloor + 10 > 10(n/10-1) + 10 = n$ numbers to be presented. For 9 10-major elements, supposing there are 100 numbers in total, each such elements appear 11 times would satisfy the requirement.

(b) Since the 10-major elements require the elements to appear at least $\lfloor n/10 \rfloor + 1$ times, we can infer that, if we cut the array into 10 subarrays, such elements must also be a 10-major elements in at least one of the subarray. Reporting such elements in the subarray to the previous recurrsion and checking if they are still 10-major elements in the previous recurrsion can help us get all the 10-major elements.

\begin{algorithm}
	\SetAlgoLined
	\SetKwFunction{GetMajorElements}{GetMajorElements}
	\GetMajorElements{$A[n]$}{
		
		\If{len($A$) = 0 or 1}{\Return{$A$}} // Return $A$ itself as it stores nothing or the only 10-major element
		
		PossibleMajorElements $\gets [\ ]$
		
		TrueMajorElements $\gets [\ ]$
		
		\For{$i \gets$ 0 to 9}{
			
			start $\gets \lceil ni/10 \rceil$
			
			end $\gets \lceil n(i+1)/10 \rceil - 1$
		
			PossibleMajorElements.append(\GetMajorElements{$A[start:end]$})

			// Check whether the elements in the PossibleMajorElements array are still 10-major elements in $A$
			
			\ForEach{elements in PossibleMajorElements}{
			
				Count its appearances in $A$, append it into TrueMajorElements if its appearances $\geq \lfloor n/10 \rfloor + 1$
		
			}

		}
		
		\Return{TrueMajorElements}
		
	}
	
	\underline{First Call:} \GetMajorElements{$A[n]$}
	
	\caption{Get All 10-Major Elements}
\end{algorithm}

Correctness: As any 10-major element must be a 10-major element in at least one of the subarray, we must get all the possible answers.

(c) \textbf{Recurrence:} Suppose $T(n) = 10T(n/10) + O(f(n))$ with $T(1) = 1$

$f(n)$ contains counting the appearance number of each element in PossibleMajorElements within the array $A$. We've derived that there are at most 9 10-major elements in any subarray, indicating that there are no more than $9\times 10 = 90$ candidates stored in PossibleMajorElements. Comparing such 90 elements to the original array $A$ costs $O(n)$ time complexity. Thus, $f(n) = n$

$$
T(n) = 10T(n/10) + O(n) \text{ with } T(1) = 1
$$

(d)
$$
T(n) = 10T(n/10) + O(n) = 100T(n/100) + 11n = 1000T(n/1000) + 111n = \cdots = 10^{\log_{10}n} T(1) + 100 n\log_{10} n = O(n\log n)
$$

\newpage

\section*{Homework 2}

\textbf{Name: LIN, Xuanyu, SID: 20838295, Email Address: xlinbf@connect.ust.hk}

\begin{figure}[h]
	\centering
	\includegraphics[width=0.6\textwidth]{hw2-1}
\end{figure}

\textbf{Solution.}

(a) \textbf{Main Idea:} Construct a segment tree data structure such that each node stores the count of numbers within a specific range. The root represent the whole range of the sequence, with its left and right children represent two halves of its range. If a range doesn't contain any number, then the node ends.

In such tree structure, we can get the range query by starting at the root node of the segment tree and going through its nodes according to the rule:

$\bullet$ If the current node's range falls completely within the query range, return its count.

$\bullet$ If the current node's range does not overlap with the query range, return 0.

$\bullet$ Otherwise, recursively query the left and right child nodes and return the sum their results.

\textbf{Space Occupied:} $O(1+2+4+\cdots+n) = O(2n-1) = O(n)$

\textbf{Time Complexity:} $O(\log n)$ as it's a binary tree structure.

(b) \textbf{Main Idea:} Construct a array with length as large as the maximum number of the given array to store the sum of the numbers that are smaller than the index of the current position.

The detail are as follows:

$\bullet$ Suppose the largest element of the array is $k$, construct an array of $k$ numbers, calling it $A[k]$.

$\bullet$ $A[0] = 0$. For $i = 0$ to $k$, $A[i] = A[i-1] + i \times \#\text{Number of elements equal to $i$ in the array}$

$\bullet$ To get the range-sum in $(i, j]$, simply substract $A[j]$ by $A[i]$ to get the answer in $O(1)$ time.

\textbf{Space Occupied:} $O(k)$ where $k$ is the largest element in the array.

\textbf{Time Complexity:} $O(1)$

\newpage

\begin{figure}[h]
	\centering
	\includegraphics[width=0.6\textwidth]{hw2-2}
\end{figure}

\textbf{Solution.}

\textbf{First Attempt:} Make use of the Batcher's odd even merge sort algorithm, construct a sorting network. We can construct a sorting network which consists of $\log_2 n$ stages, with wach stage having $n/2$ switches. (No further idea about such method)

\textbf{Reference:} \href{https://en.wikipedia.org/wiki/Batcher_odd%E2%80%93even_mergesort}{Wiki: Batcher's Odd Even Merge Sort}

\textbf{Second Attempt:} Make use of the binary tree construction. First, construct a binary tree with $n$ inputs being placed at $n$ nodes in a tree with height $\log n$. At each node, a switch is placed to switch the position of, and only the position of its two children. The tree is constructed via pre-order tree transversal. After all the switches are set to a specific state, the output is extracted accordingly also via pre-order tree transversal.

Total switches used:
$$
\sum_{i=1}^{\log n} \frac{n}{2^i} = O(n\log n)
$$

\textbf{Correctness:} We are proving that different types of combination of switches yeilds distinct solutions, so that using $O(n\log n)$ switches, we are able to perform $2^{n\log n} \sim n!$ distinct types of output.

By modifying a switch at a node, we're only modifying the two children which is directly connected to the current node, i.e, whenever the states of the switches are not identical, the two trees are not identical, resulting in the different extracted result via pre-order tree transversal. Thus, $O(n\log n)$ switches are enough to generate all the $n!$ distinct permutations of the array.

\textbf{Reference:}
\href{https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/}{Tree Traversal Techniques – Data Structure and Algorithm Tutorials}

\newpage

\begin{figure}[h]
	\centering
	\includegraphics[width=0.6\textwidth]{hw2-3}
\end{figure}

\textbf{Solution.}

\textbf{Main Idea:} Use divide-and-conquer to find the largest element, which requires $n-1$ comparisons. During such comparison, the second largest element must be eliminated by the largest element. As a result, we are able to examine through the $\log_2 n$ to get the second larget element.

$\bullet$ To get the largest element, we've conducted the comparison like a "single elimination tournament" with guaranteed $n-1$ comparisons.

$\bullet$ Note that the second largest element must be eliminated by the largest element. Thus, we construct a list for every of the $n$ element to store all the elements eliminated by this number. Every time when we eliminate an element, we append the number eliminated by it (the "loser" of the comparison) to the list of the "winner".

$\bullet$ After we've got the largest element, we traverse through the list stored by the largest element to obtain the second largest element. The list contains $\log n$ elements, which requires $\log n - 1$ comparisons.

$\bullet$ Thus, we need $n + \log n - 2$ comparisons in total.

\newpage

\begin{figure}[h]
	\centering
	\includegraphics[width=0.6\textwidth]{hw2-4}
\end{figure}

\textbf{Proof.}

The algorithm is identical as the procedure described as below:

$\bullet$ First, randomly choose a number in range $[1, n-m+1]$ to append to $S$.

$\bullet$ Next, randomly choose a number in range $[1, n-m+2]$ to append to $S$. If it's already in $S$, then append $n-m+2$ to $S$.

$\bullet$ Then, randomly choose a number in range $[1, n-m+3]$ to append to $S$. If it's already in $S$, then append $n-m+3$ to $S$.

$\bullet$ $\cdots$

$\bullet$ Finally, randomly choose a number in range $[1, n]$ to append to $S$. If it's already in $S$, then append $n$ to $S$. (A total of $m$ random pick is conducted)

We can check the consistency of the probability by calculating the probability of each number to be chosen.

Consider an arbitrary number $k$, evaluating the probability of $k$ NOT to be chosen:

$\bullet$ If $k \leq n-m+1$, then
$$
\text{The number $k$ is NOT chosen} = \frac{n-m}{n-m+1} \cdot \frac{n-m+1}{n-m+2} \cdots \frac{n-1}{n} = \frac{n-m}{n}
$$

$\bullet$ Suppose $n-m+1 < k \leq n$, then we've already chosen $k-n+m-1$ numbers $\implies$ At the random draw in range $[1, k]$, the probability of $k$ NOT to be chosen is $[k-(k-n+m-1+1)]/k = (n-m)/k$. (Condition: At the draw in range $[1, k]$, neither the elements that have been drawn nor $k$ itself are pulled out) In the remaining random pick, the calculation is the same as the above circumstance.
$$
\text{The number $k$ is NOT chosen} = \frac{n-m}{k} \cdot \frac{k}{k+1} \cdots \frac{n-1}{n} = \frac{n-m}{n}
$$

From the above discussion, we see that the probabilities of each elements to be drawn are identical, all equals to $1-\frac{n-m}{n} = \frac{m}{n}$. This yields directly that the probability of each combination of RANDOM-SAMPLE to be drawn is also identical.

\newpage

\begin{figure}[h]
	\centering
	\includegraphics[width=0.6\textwidth]{hw2-5}
\end{figure}
Note: The summation range should be from 2 to $n-1$ instead of 1 to $n-1$ for (d).

\textbf{Solution.}

(a) In the quicksort, the probabilities of each element to be chosen are identical, all equals to $1/n$, where $n$ indicates the number of elements.
$$
\implies E[X_i] = \frac{1}{n}
$$

(b) Note that according to the quicksort, the array to be sorted is splitted into two subarrays according to the element that is randomly chosen. The two subarrays are of length $i-1$ and $n-i$ if the $i$-th smallest element is chosen randomly. According to the recursive algorithm, the "Merge" step requires $\Theta(n)$ time. Thus,
$$
E[T(n)] = E\bigg[\sum_{i=1}^{n} X_i \cdot (T(i-1) + T(n-i) + \Theta(n))\bigg]
$$

(c) The deriviation is as follows:
$$
\begin{aligned}
	E[T(n)] &= E\bigg[\sum_{i=1}^{n} X_i \cdot (T(i-1) + T(n-i) + \Theta(n))\bigg] = E\bigg[\sum_{i=1}^{n} \frac{1}{n} \cdot (T(i-1) + T(n-i) + \Theta(n))\bigg]\\
	&= \Theta(n) + \frac{1}{n} \cdot E\bigg[\sum_{i=1}^{n} (T(i-1) + T(n-i))\bigg] = \Theta(n) + \frac{2}{n} \sum_{i=1}^{n} E[T(i-1)] = \Theta(n) + \frac{2}{n} \sum_{i=0}^{n-1} E[T(i)] = \Theta(n) + \frac{2}{n} \sum_{i=2}^{n-1} E[T(i)]
\end{aligned}
$$

(d) According to the integral inequality, the left hand rule,
$$
\sum_{k=2}^{n-1} k \log k \leq \int_2^n k \log k = \frac{\frac{k^2}{2} \log k - \frac{k^2}{4}}{\log 2}\bigg|_2^n = \frac{n^2}{2} \log n - \frac{n^2}{4 \log 2} - 1
$$
$$
\implies \sum_{k=2}^{n-1} k \ln k \leq \frac{n^2}{2} \log n - \frac{n^2}{4 \log 2} - 1 \leq \frac{n^2}{2} \log n - \frac{n^2}{8}
$$

(e) Recurrence:
$$
\begin{aligned}
	E[T(n)] &= \Theta(n) + \frac{2}{n} \sum_{i=2}^{n-1} E[T(i)] \leq \Theta(n) + \frac{2}{n} \sum_{i=2}^{n-1} [i \log i + \Theta(n)] \leq \Theta(n) + \frac{2}{n} \sum_{i=2}^{n-1} i \log i\\
	&\leq \frac{2}{n} \bigg[\frac{n^2 \log n}{2} - \frac{n^2}{8}\bigg] + \Theta(n) = n \log n - \frac{1}{4} n + \Theta(n) = n \log n + \Theta(n)
\end{aligned}
$$

\newpage

\section*{Homework 3}

\textbf{Name: LIN, Xuanyu, SID: 20838295, Email Address: xlinbf@connect.ust.hk}

\begin{figure}[h]
	\centering
	\includegraphics[width=0.5\textwidth]{hw3-1(1)}
\end{figure}
\begin{figure}[h]
	\centering
	\includegraphics[width=0.5\textwidth]{hw3-1(2)}
\end{figure}

\newpage

\textbf{Solution.}

(a)
\begin{proof}
	The proof goes as follows:

	1. There must exists a minimal cover $A$ of $\mathscr{L}$.

	2. If there exists a minimal cover $A$ of $\mathscr{L}$ such that at least one point in $A$ is not any of the $f_j$, then we are able to construct a new cover $A'$ of the same size such that every point in $A'$ is one of the $f_j$.

	1. Easy to see that the set $A_1$ with size in $[1,n]$ consisting of all $s_i$s is a cover of $\mathscr{L}$. This set the upper bound of the size of the minimal set to be $n$. The size of any other possible set $A_2$ has a lower bound, which is 1. Thus, there must exists a minimal cover $A$ of $\mathscr{L}$.

	2. If there exists a minimal cover $A$ of $\mathscr{L}$ such that at least one point in $A$ is not any of the $f_j$, we store such points in a set $B$. For every points $i$ in $B$, we trace the timeline to find the smallest $f_i$ such that $f_i \geq i$.[1] We then replace $i$ with $f_i$ in $A$, forming the new set $A'$ which is still a cover of $\mathscr{L}$, and the size of $A'$ is the same as $A$. Thus, we've constructed a new cover $A'$ of the same size such that every point in $A'$ is one of the $f_j$.

	Note: [1] If there doesn't exist a $f_i \geq i$, that means $i$ is not covered by any interval, which contradicts the assumption that $A$ is a cover of $\mathscr{L}$.
\end{proof}

(b) The algorithm is as follows:

\begin{algorithm}
	\SetAlgoLined
	\SetKwFunction{FindMinimalCover}{FindMinimalCover}
	\KwIn{$n$ sets of intervals $\mathscr{L} = \{I_1, ..., I_n\}$}
	\KwOut{A minimal cover $A$ of $\mathscr{L}$}
	\FindMinimalCover{$\mathscr{L}$}{
		
		Sort all the intervals in $\mathscr{L}$ in ascending order based on their ending time $f_j$

		\While{$\mathscr{L} != null$} {
			$A$.append($\mathscr{L}[0].f$) // Append the interval with the smallest ending time to $A$

			$cur_f = \mathscr{L}[0].f$
			
			\ForEach{$I \in \mathscr{L}$} {
				\If{$I.s \leq cur_f$} {
					$\mathscr{L}$.remove($I$) // Remove all the intervals that are already covered by the current point
				}
			}

		}
		
		\Return{$A$}
		
	}

	\caption{Find a Minimal Cover $A$}
\end{algorithm}

(c)
\begin{proof}
	Suppose the minimal cover genrated by the former algorithm is $A = \{a_1, ..., a_m\}$, and the actual minimal cover is $A' = \{a'_1, ..., a'_{m'}\}$ with $m'<m$.

	We first rank the interval set $\mathscr{L}$ in ascending order based on their ending time $f_j$, resulting in $\mathscr{L} = \{I_{k_1}, I_{k_2}, ..., I_{k_n}\}$.

	1. If there's any element in $A'$ not in $A$, i.e., $\exists \alpha \in A'$ such that $\alpha \notin A$, find the minimal subscript $x$ such that $a_1=a'_1, ..., a_{x-1}=a'_{x-1}$ but $a_x\neq a'_x$.

	1.1 If $a'_x < a_x$, then modifying $a'_x$ to $a_x$ in $A'$ also forms a cover of $\mathscr{L}$ with the same total size. This is because we've already covered all the intervals that ends before $a_x$. If we apply the algorithm to a modified set that elimnates the covered intervals, then $a_x$ is the end of the first interval while $a'_x$ is not. Problem (a) has already proved that we are able to modify any non-$f_j$ point to one of the $f_j$.
	
	1.2 If $a'_x > a_x$, then at least one interval is not covered by $A'$. We first eliminate all the intervals that ends before $a_x$. According to the algorithm, $a_x$ is the end of the first non-eliminated interval (i.e., not being covered by previous $a$). If $a'_x > a_x$, then the non-eliminated interval $I_{k_i}$ has the property that $s_{k_i} < f_{k_i} < a'_x$, resulting in $A'$ not covering $I_{k_i}$. Contradiction!

	2. If $A' subsetneqq A$, the previous part already suggested that $A = A'\cup \{a_{m'+1}, a_{m'+2}, ..., a_{m}\}$. However, the previous algorithm already suggested that each of the $a_i$ is an end of some interval $I_{k_i}$ such that $I_{k_i}$ is not covered by the previous items, i.e., $a_{m'+1}$ is the end of ont of $I_{k_i}$, such that $I_{k_i}$ is not covered by $A'$. Thus, $A'$ is not a minimal cover of $\mathscr{L}$. Contradiction!
\end{proof}

(d) Sorting the intervals in ascending order based on their ending time $f_j$ requires $O(n\log n)$ time. The while loop requires $O(n)$ time. Thus, the total time complexity is $O(n\log n)$.

\newpage

\begin{figure}[h]
	\centering
	\includegraphics[width=0.6\textwidth]{hw3-2}
\end{figure}

\textbf{Solution.}

(a)
\begin{figure}[h]
	\centering
	\includegraphics[width=0.3\textwidth]{hw3-2-ans}
\end{figure}

(b)
\begin{center}
	\renewcommand{\arraystretch}{1.5}
	\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|}
		\hline
		Letter & a & b & c & d & e & f & g & h & i & j \\
		\hline
		Code & 0100 & 000 & 101 & 1110 & 110 & 011 & 100 & 001 & 0101 & 1111 \\
		\hline
	\end{tabular}
\end{center}

(c)
\begin{center}
	\renewcommand{\arraystretch}{1.5}
	\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|}
		\hline
		Letter & b & c & e & f & g & h & a & d & i & j \\
		\hline
		Code & 000 & 101 & 110 & 011 & 100 & 011 & 0100 & 1110 & 0101 & 1111 \\
		\hline
	\end{tabular}
\end{center}

\newpage

\begin{figure}[h]
	\centering
	\includegraphics[width=0.6\textwidth]{hw3-3}
\end{figure}

\textbf{Solution.}

1. $p_1$ sends offer to $j_4$: $p_1-j_4$

2. $p_2$ sends offer to $j_2$: $p_1-j_4$, $p_2-j_2$

3. $p_3$ sends offer to $j_4$, $j_4$ rejects: $p_1-j_4$, $p_2-j_2$

4. $p_4$ sends offer to $j_2$, $j_2$ unpairs with $p_2$: $p_1-j_4$, $p_4-j_2$

5. $p_2$ sends offer to $j_3$: $p_1-j_4$, $p_4-j_2$, $p_2-j_3$

6. $p_3$ sends offer to $j_2$, $j_2$ rejects: $p_1-j_4$, $p_4-j_2$, $p_2-j_3$

7. $p_3$ sends offer to $j_3$, $j_3$ unpairs with $p_2$: $p_1-j_4$, $p_4-j_2$, $p_3-j_3$

8. $p_2$ sends offer to $j_1$: $p_1-j_4$, $p_4-j_2$, $p_3-j_3$, $p_2-j_1$ Stable!

Final Matching: $p_1-j_4$, $p_4-j_2$, $p_3-j_3$, $p_2-j_1$

\newpage

\begin{figure}[h]
	\centering
	\includegraphics[width=0.6\textwidth]{hw3-4}
\end{figure}

\textbf{Solution.}

\textbf{Main Idea:} First sort the tasks by its deadlines $d(t)$. Create an array $p(t)$ such that for each task $t$, $p(t)$ returns the largest index of the compatible tasks $t'$ with $t'<t$. Suppose the maximum possible total value for the first $i$ sorted tasks is $V(i)$, then
\[
\begin{cases}
	V[i] = \max\{V[i-1], v_i + V[p(i)]\} \\
	V[0] = 0
\end{cases}
\]

\begin{algorithm}
	\SetAlgoLined
	\SetKwFunction{TaskScheduling}{TaskScheduling}
	\TaskScheduling{$T$}{
		
		Sort the tasks by its deadlines $d(t)$
		
		\For{$i = 1$ to $n$}{
			
			$p[i] \gets$ largest index of the (sorted) compatible tasks $i'$ with $i'<i$. // Do binary search for previous deadlines $d(t_{i'})$ and compare with the current releasing time $r(t_i)$
			
		}
		
		$V[0] \gets 0$
		
		\For{$i = 1$ to $n$}{
		
			$V[i] \gets \max\{V[i-1], v_i + V[p(i)]\}$
		
		}
		
	}
	
	\Return{$V[n]$}
	
	\caption{Task Scheduling}
\end{algorithm}

\textbf{Time complexity:}

\(\bullet\) Sorting the tasks -> $O(n\log n)$

\(\bullet\) Comstruct $p[i]$ -> each value requires $O(\log n)$ time using binary search -> $n\times O(\log n) = O(n\log n)$

\(\bullet\) Calculating $V[i]$ -> $O(n)$

Altogether, the algorithm requires a time complexity of $O(n\log n)$

\newpage

\begin{figure}[h]
	\centering
	\includegraphics[width=0.5\textwidth]{hw3-5}
\end{figure}

\textbf{Solution.}

First Attempt: Simply do the DFS for each grid in four directions
\begin{algorithm}
	\SetAlgoLined
	\KwIn{$A[1\cdots n][1\cdots n]$}
	\KwOut{length, indices}
	\SetKwFunction{DFS}{DFS}
	\DFS{$i,j$,prev,path[]}{
		
		\If{$i<0$ or $j<0$ or $i>=n$ or $j>=n$ or $A[i][j]<$prev}{
			\Return{0,[]}
		}
		
		left, leftPath[] = \DFS($i,j-1,A[i][j],$leftPath)
		
		leftPath.append($A[i][j]$)
		
		right, rightPath[] = \DFS($i,j+1,A[i][j],$rightPath)
		
		rightPath.append($A[i][j]$)
		
		top, topPath[] = \DFS($i-1,j,A[i][j],$topPath)
		
		topPath.append($A[i][j]$)
		
		bottom, bottomPath[] = \DFS($i+1,j,A[i][j],$bottomPath)
		
		bottomPath.append($A[i][j]$)
		
		\Return{$\max{\text{left,right,top,bottom}}+1$,Corresponding\_Path[]}
		
		\underline{First Call:}
		
		Max = 0, MaxPath[] = null
		
		\ForEach{Grid}{
			curMax, curMaxPath[] = \DFS{Grid.x,Grid.y,-1,[]}

			\If{curMax > Max}{
				Max = curMax\\
				MaxPath = curMaxPath
			}
		}
	}

	\Return{curMax, curMaxPath}
	
	\caption{DFS for Grid Paths}
\end{algorithm}

However, this algorithm has a time complexity of $~O(n^2\cdot 4^{n^2})$, too large!

\newpage

Second Attempt: The previous attempt may recall the DFS algorithm on the same grid for multiple times. All we need to do is creating an array to store the calculated results to avoid recalculation.
\begin{algorithm}
	\SetAlgoLined
	\KwIn{$A[1\cdots n][1\cdots n]$}
	\KwOut{length, indices}
	\SetKwFunction{DFS}{DFS}
	Memory = [][][] // For each grid, reserve an array to store the longest increasing result starting at such grid
	\DFS{$i,j$,prev,path[]}{
		
		\If{Memory[i][j] != null}{
			\Return{len(Memory[i][j]),Memory[i][j]}
		}
		
		\If{$i<0$ or $j<0$ or $i>=n$ or $j>=n$ or $A[i][j]<$prev}{
			\Return{0,[]}
		}
		
		left, leftPath[] = \DFS($i,j-1,A[i][j],$leftPath)
		
		leftPath.append($A[i][j]$)
		
		right, rightPath[] = \DFS($i,j+1,A[i][j],$rightPath)
		
		rightPath.append($A[i][j]$)
		
		top, topPath[] = \DFS($i-1,j,A[i][j],$topPath)
		
		topPath.append($A[i][j]$)
		
		bottom, bottomPath[] = \DFS($i+1,j,A[i][j],$bottomPath)
		
		bottomPath.append($A[i][j]$)
		
		Get the longest path $P[]$ among the four candidates
		
		$Memory[i][j] \gets P$
		
		\Return{$\max{\text{left,right,top,bottom}}+1$,Corresponding\_Path[]}
		
		\underline{First Call:}
		
		Max = 0, MaxPath[] = null
		
		\ForEach{Grid}{
			curMax, curMaxPath[] = \DFS{Grid.x,Grid.y,-1,[]}

			\If{curMax > Max}{
				
				Max = curMax
				
				MaxPath = curMaxPath
				
			}
		}
	}
	
	\Return{curMax, curMaxPath}
	
	\caption{DFS for Grid Paths}
\end{algorithm}

\textbf{Time Complexity:} DFS for each grid is called at most once, as later calls would directly return the value stored in $Memory[][][]$. All the other functions calls requires a constant time. Thus, the time complexity is $O(n^2)$.

\newpage

\section*{Homework 4}

\textbf{Name: LIN, Xuanyu, SID: 20838295, Email Address: xlinbf@connect.ust.hk}

\begin{figure}[h]
	\centering
	\includegraphics[width=0.6\textwidth]{hw4-1}
\end{figure}

\textbf{Solution.}

(a) Suppose at least one vertex $v$ has degree $\geq 3$, while other vertices have degree $\geq 2$. Then, the number of edges $l$ satisfies:
\[
	l = \frac{1}{2} \sum_{v\in V} d(v) \geq \frac{1}{2} \times 3 + \frac{1}{2} \times (n-1) \times 2 = n + \frac{1}{2} > n
\]

Contradicts with the assumption that the graph has $n$ edges. Thus, every vertex has a degree of 2.

\vspace*{1em}

(b) Suppose the undirected graph $G$ with $n$ vertices has its every vertex of different degree. Notice that each vertex should have a degree between 0 and $n-1$ (a total of $n$ different values), there must be a vertex with degree 0 and a vertex with degree $n-1$. However, the vertex with degree $n-1$ must be connected to all the other vertices, which contradicts with the assumption that there exists a vertex with degree 0. Thus, there must be at least two vertices with the same degree.

\vspace*{1em}

(c) We begin the proof with a lemma:
\begin{lemma}
	For any graph $G$ with $n \geq 3$ vertices, if every vertex has a degree of two, then $G$ must either be a cycle, or a union of several cycles, each with at least three vertices.
\end{lemma}
\begin{proof}
	We start from an arbitrary vertex $v_1$ in the graph, tracing its two edges to the other two vertices $v_{11}\neq v_{12}$ called "ends", forming a tree. We continue to trace the two branch $v_{11}\ \&\ v_{12}$. Each new branch should either introduce a new vertex, forming a new "end" or connect to each other, forming a complete cycle. (That is, unable to connect to any vertex that already exists in the tree.) Since the number of vertices is finite, the process must terminate, forming a cycle. Thus, every vertex should be in a cycle of length $\geq 3$. In this case, the graph must either be a cycle, or a union of several cycles, each with at least three vertices.
\end{proof}

We then come to the main proof:
\begin{proof}
	Restate the problem in an equivalent way as follows (Invert the connection and disconnection):

	In a group of 10 vertices, each one of them has a degree of 2. Prove that there exists 4 vertices such that non of them connects to the other three.

	According to \textbf{Lemma}, the graph must either be a cycle, or a union of several cycles, each with at least three vertices. In the case of 10 vertices, there are at most 3 cycles. Note to the fact that if two vertices are not in the same cycle, they are unconnected.
	
	$\bullet$ If the graph is a single cycle. We start by naming any one of the vertex to be $v_1$, transversing the cycle to name the vertices as $v_2, v_3, ..., v_{10}$. Then, we are able to find 4 vertices such that non of them connects to the other three, i.e., $v_1, v_3, v_5, v_7$.
	
	$\bullet$ If the graph is a union of two cycles, then there must be either at least one cycle of length $\geq 6$ or both cycles of length 5. In the former case, we take three vertices from the cycle of length $\geq 6$ (i.e., $v_1, v_3, v_5$) and one vertex from the other cycle. In the latter case, we take two unconnected vertices from each of the two cycles. Both cases yields the result.

	$\bullet$ If the graph is a union of three cycles, then there must be two cycles of length 3 and one of length 4. In this case, we take the two unconnected vertices from the cycle of length 4, and one vertex from each of the cycle of length 3, which yields the result.

\end{proof}

\newpage

\begin{figure}[h]
	\centering
	\includegraphics[width=0.6\textwidth]{hw4-2}
\end{figure}

\textbf{Solution.}

\textbf{Main Idea:}

$\bullet$ When trasversing the bipartite graph using DFS, the current vertex jumps between the two sets of vertices.

$\bullet$ Since each vertex must connect to the other set of vertices, we can assign the vertices in two values 0 and 1. Every edge must connect two vertices with different values.

$\bullet$ We assign the values during DFS, and check whether there exists an edge connecting two vertices with the same value. If so, the graph is not bipartite. Otherwise, the graph is bipartite.

$\bullet$ Whether the graph is connected or not doesn't affect the result, as we have ensured that every vertex is visited during the DFS.

\textbf{Remark of the Following Algorithm:} In the following algorithm, we use $u.color$ to store whether a vertex is processed or not (WHITE, GRAY, BLACK). We use another variable $u.value$ to store the assigned values of the vertex (0 or 1) as described above.

\begin{algorithm}
	\SetAlgoLined
	\SetKwFunction{CheckBipartiteGraph}{CheckBipartiteGraph}
	\SetKwFunction{DFSVisit}{DFSVisit}
	
	isBipartite = true

	\CheckBipartiteGraph{G}{

		\ForEach{$u \in V$}{

			$u.color \gets WHITE$

			$u.p \gets NIL$

			$u.value \gets 0.5$

		}

		\ForEach{$u \in V$}{

			\If{$u.color = WHITE$}{

				$u.value \gets 0$

				\DFSVisit{$u$}

			}

		}

		\Return{isBipartite}

	}

	\vspace*{1em}
	
	\DFSVisit{$u$}{

		$u.color \gets GRAY$

		\ForEach{$v \in G.Adj[u]$}{

			\If{$v.color = WHITE$}{

				$v.p \gets u$

				$v.value \gets 1 - u.value$

				\DFSVisit{$v$}

			}

			\ElseIf{$v.color = GRAY$}{

				\If{$v.value = u.value$}{

					isBipartite = false

				}

			}

		}

		$u.color \gets BLACK$

	}
	
	\caption{DFS Check Bipartite Graph}

\end{algorithm}

\textbf{Time Complexity:} This algorithm is identical to the DFS algorithm, which requires $O(n+m)$ time.

\newpage

\begin{figure}[h]
	\centering
	\includegraphics[width=0.6\textwidth]{hw4-3}
\end{figure}

\textbf{Solution.}

\textbf{Idea:} Note to the symmetry of "Maximizing the lowerbound weight" and "Minimizing the upperbound weight", we can reassign the edges with negative weights accordingly and construct a MST for the whole graph to solve the problem.

$\bullet$ We claim that the path between any two vertices in a generated MST is one of the "Minimum lowerbound path" between them.

\begin{proof}
	We prove the claim by contradiction.
	
	We consider the minimum lowerbound weight path between the two vertices $u$ and $v$. Suppose the generated MST $M = (V, E_{MST})$ contains a unique path ${e_i}$ from $u$ to $v$, while the actual "Minimum lowerbound path" between them is ${e'_i} \neq {e_i}$ with $\sum wt(e'_i) < \sum wt(e_i)$.

	Consider the union of edges $E_{MST} \cup {e'_i}$, which absolutely form some cycles. We claim that all cycles are formed by the edges in ${e_i} \cup {e'_i}$.

	% This is a fake proof
	$\bullet$ If there exists a cycle $C$ that contains an edge $\{e \notin {e_i}\} \cup {e'_i}$, then there also exists a cycle formed by the edges in $\{e \notin {e_i}\} \cup {e_i} = E_{MST}$, as both ${e_i}$ and ${e'_i}$ has the same starting and ending point. This contradicts with the assumption that $M$ is a MST.

	Thus, we are able to remove only the edges in ${e_i}$ from $E_{MST} \cup {e'_i}$ to form a new MST $M'$. However, $\sum wt(M') = \sum wt(M) - \sum wt({e'_i}) + \sum wt({e'_i}) = \sum wt(M) < \sum wt(M)$. Contradiction!
\end{proof}

Thus, our algorithm could start from generated $n$ MSTs rooted at each vertex using Prim's algorithm, and then report the "Minimum lowerbound path" between any two vertices using the claim above.

\textbf{Time Complexity:} Prim's algorithm for all vertices requires $O(EV\log V)$ time. The remaining part requires $O(V^2)$ time. Thus, the total time complexity is $O(EV\log V)$.

\newpage

\begin{figure}[h]
	\centering
	\includegraphics[width=0.6\textwidth]{hw4-4(1)}
\end{figure}
\begin{figure}[h]
	\centering
	\includegraphics[width=0.6\textwidth]{hw4-4(2)}
\end{figure}

\textbf{Solution.}

(a)
\begin{figure}[H]
	\centering
	\includegraphics[width=0.6\textwidth]{hw4-4-ans(1)}
\end{figure}

\newpage
(b)
\begin{figure}[H]
	\centering
	\includegraphics[width=0.6\textwidth]{hw4-4-ans(2)}
\end{figure}

\newpage
\textbf{Appendix:} The following is the code for the algorithm in (b):

\lstset{language=Python}
\begin{lstlisting}[tabsize=4]
def floyd_warshall(graph):
n = len(graph)
dist = graph

for k in range(n):
	for i in range(n):
		for j in range(n):
			dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
	print("k =", k+1)
	for row in dist:
		print(row)
	print("--------------------")

return dist

graph = [
[0, float('inf'), 10, float('inf'), 2, float('inf'), 5],
[float('inf'), 0, float('inf'), 10, float('inf'),\
float('inf'), float('inf')],
[float('inf'), float('inf'), 0, 20, float('inf'), 8, float('inf')],
[float('inf'), float('inf'), 6, 0, float('inf'),\
float('inf'), float('inf')],
[float('inf'), float('inf'), float('inf'), 50, 0, float('inf'), 2],
[float('inf'), float('inf'), float('inf'),\
float('inf'), float('inf'), 0, float('inf')],
[float('inf'), 2, float('inf'), 20, float('inf'), 3, 0]

]

result = floyd_warshall(graph)
\end{lstlisting}

\newpage

\begin{figure}[h]
	\centering
	\includegraphics[width=0.6\textwidth]{hw4-5}
\end{figure}

\newpage
\textbf{Solution.}
\begin{figure}[H]
	\centering
	\includegraphics[width=0.6\textwidth]{hw4-5-ans(1)}
\end{figure}
\begin{figure}[H]
	\centering
	\includegraphics[width=0.6\textwidth]{hw4-5-ans(2)}
\end{figure}

\end{document}