Algorithm Pseudocode

\documentclass[11pt,a4paper]{article}
\usepackage[margin=1in]{geometry}
\usepackage{algorithm}
\usepackage{algpseudocode}
\usepackage{amsmath,amssymb}
\usepackage{booktabs}
\usepackage{hyperref}
\usepackage{xcolor}
\usepackage{fancyhdr}

\definecolor{algblue}{RGB}{0,60,120}

\pagestyle{fancy}
\fancyhf{}
\fancyhead[L]{\small Algorithm Documentation}
\fancyhead[R]{\small CS 4210 -- Advanced Algorithms}
\fancyfoot[C]{\thepage}
\renewcommand{\headrulewidth}{0.4pt}

\algnewcommand\algorithmicforeach{\textbf{for each}}
\algdef{S}[FOR]{ForEach}[1]{\algorithmicforeach\ #1\ \algorithmicdo}

\title{\textbf{Algorithm Documentation}\\[0.3em]\large Selected Algorithms with Pseudocode and Analysis}
\author{Prof.\ Evelyn Hartwell\\Department of Computer Science}
\date{Fall 2025}

\begin{document}

\maketitle
\tableofcontents
\newpage

\section{Introduction}

This document presents pseudocode and complexity analysis for three fundamental algorithms in computer science. Each algorithm is presented with detailed line-by-line commentary, correctness arguments, and asymptotic analysis. All pseudocode follows the conventions of Cormen et al.\ (\textit{Introduction to Algorithms}, 4th ed.).

\section{Merge Sort}

\subsection{Description}

Merge Sort is a divide-and-conquer sorting algorithm that recursively splits an array into halves, sorts each half, and merges the sorted halves. It guarantees $O(n \log n)$ worst-case performance and is stable.

\subsection{Pseudocode}

\begin{algorithm}[H]
\caption{Merge Sort}\label{alg:mergesort}
\begin{algorithmic}[1]
\Require Array $A[1 \ldots n]$
\Ensure $A$ is sorted in non-decreasing order
\Statex
\Procedure{MergeSort}{$A, p, r$}
    \If{$p < r$} \Comment{Base case: subarray has at least 2 elements}
        \State $q \gets \lfloor (p + r) / 2 \rfloor$ \Comment{Find the midpoint}
        \State \Call{MergeSort}{$A, p, q$} \Comment{Sort left half}
        \State \Call{MergeSort}{$A, q+1, r$} \Comment{Sort right half}
        \State \Call{Merge}{$A, p, q, r$} \Comment{Merge sorted halves}
    \EndIf
\EndProcedure
\Statex
\Procedure{Merge}{$A, p, q, r$}
    \State $n_1 \gets q - p + 1$ \Comment{Size of left subarray}
    \State $n_2 \gets r - q$ \Comment{Size of right subarray}
    \State Create arrays $L[1 \ldots n_1 + 1]$ and $R[1 \ldots n_2 + 1]$
    \For{$i \gets 1$ \textbf{to} $n_1$}
        \State $L[i] \gets A[p + i - 1]$
    \EndFor
    \For{$j \gets 1$ \textbf{to} $n_2$}
        \State $R[j] \gets A[q + j]$
    \EndFor
    \State $L[n_1 + 1] \gets \infty$ \Comment{Sentinel value}
    \State $R[n_2 + 1] \gets \infty$
    \State $i \gets 1,\; j \gets 1$
    \For{$k \gets p$ \textbf{to} $r$}
        \If{$L[i] \leq R[j]$}
            \State $A[k] \gets L[i]$
            \State $i \gets i + 1$
        \Else
            \State $A[k] \gets R[j]$
            \State $j \gets j + 1$
        \EndIf
    \EndFor
\EndProcedure
\end{algorithmic}
\end{algorithm}

\subsection{Complexity Analysis}

\begin{itemize}
    \item \textbf{Recurrence:} $T(n) = 2T(n/2) + \Theta(n)$
    \item \textbf{Time Complexity:} $\Theta(n \log n)$ in all cases (best, average, worst)
    \item \textbf{Space Complexity:} $\Theta(n)$ auxiliary space for the temporary arrays $L$ and $R$
    \item \textbf{Stability:} Stable, since the merge step preserves the relative order of equal elements (line 22 uses $\leq$)
\end{itemize}

By the Master Theorem (Case 2 with $a=2$, $b=2$, $f(n)=\Theta(n)$):
\[
T(n) = \Theta(n^{\log_2 2} \log n) = \Theta(n \log n)
\]

\newpage
\section{Dijkstra's Shortest Path}

\subsection{Description}

Dijkstra's algorithm finds the shortest paths from a single source vertex to all other vertices in a weighted directed graph with non-negative edge weights. It uses a priority queue to greedily select the vertex with the smallest tentative distance.

\subsection{Pseudocode}

\begin{algorithm}[H]
\caption{Dijkstra's Algorithm}\label{alg:dijkstra}
\begin{algorithmic}[1]
\Require Directed graph $G = (V, E)$ with weight function $w: E \to \mathbb{R}_{\geq 0}$, source $s \in V$
\Ensure $d[v]$ = shortest path distance from $s$ to $v$ for all $v \in V$
\Statex
\Procedure{Dijkstra}{$G, w, s$}
    \ForEach{vertex $v \in V$}
        \State $d[v] \gets \infty$
        \State $\pi[v] \gets \textsc{nil}$ \Comment{Predecessor pointer}
    \EndFor
    \State $d[s] \gets 0$
    \State $S \gets \emptyset$ \Comment{Set of vertices with finalized distances}
    \State $Q \gets V$ \Comment{Min-priority queue keyed by $d[\cdot]$}
    \While{$Q \neq \emptyset$}
        \State $u \gets \Call{ExtractMin}{Q}$ \Comment{Vertex with smallest $d$ value}
        \State $S \gets S \cup \{u\}$
        \ForEach{vertex $v \in \text{Adj}[u]$} \Comment{Relax outgoing edges}
            \If{$d[v] > d[u] + w(u, v)$}
                \State $d[v] \gets d[u] + w(u, v)$ \Comment{Update distance}
                \State $\pi[v] \gets u$ \Comment{Update predecessor}
                \State \Call{DecreaseKey}{$Q, v, d[v]$}
            \EndIf
        \EndFor
    \EndWhile
    \State \Return $d, \pi$
\EndProcedure
\end{algorithmic}
\end{algorithm}

\subsection{Complexity Analysis}

The running time depends on the priority queue implementation:

\begin{center}
\begin{tabular}{@{}lcc@{}}
\toprule
\textbf{Priority Queue} & \textbf{ExtractMin} & \textbf{Total Time} \\
\midrule
Array (unsorted) & $O(V)$ & $O(V^2)$ \\
Binary heap & $O(\log V)$ & $O((V + E) \log V)$ \\
Fibonacci heap & $O(\log V)$ amortized & $O(V \log V + E)$ \\
\bottomrule
\end{tabular}
\end{center}

\begin{itemize}
    \item \textbf{Space Complexity:} $\Theta(V)$ for the distance and predecessor arrays
    \item \textbf{Correctness:} Relies on the property that all edge weights are non-negative. The greedy choice at line 10 is safe because no future path through unvisited vertices can yield a shorter distance to $u$.
\end{itemize}

\newpage
\section{Knapsack (Dynamic Programming)}

\subsection{Description}

The 0/1 Knapsack problem asks: given $n$ items, each with weight $w_i$ and value $v_i$, and a knapsack of capacity $W$, select a subset of items that maximizes total value without exceeding the weight capacity. This dynamic programming solution runs in pseudo-polynomial time.

\subsection{Pseudocode}

\begin{algorithm}[H]
\caption{0/1 Knapsack via Dynamic Programming}\label{alg:knapsack}
\begin{algorithmic}[1]
\Require Items with weights $w[1 \ldots n]$ and values $v[1 \ldots n]$; capacity $W$
\Ensure Maximum achievable value and the selected items
\Statex
\Procedure{Knapsack}{$w, v, n, W$}
    \State Create table $K[0 \ldots n][0 \ldots W]$
    \For{$i \gets 0$ \textbf{to} $n$} \Comment{Initialize base cases}
        \For{$j \gets 0$ \textbf{to} $W$}
            \If{$i = 0$ \textbf{or} $j = 0$}
                \State $K[i][j] \gets 0$
            \ElsIf{$w[i] \leq j$} \Comment{Item $i$ fits}
                \State $K[i][j] \gets \max\bigl(v[i] + K[i-1][j - w[i]],\; K[i-1][j]\bigr)$
            \Else \Comment{Item $i$ does not fit}
                \State $K[i][j] \gets K[i-1][j]$
            \EndIf
        \EndFor
    \EndFor
    \Statex
    \State \Comment{Backtrack to find selected items}
    \State $\mathit{result} \gets K[n][W]$
    \State $j \gets W$
    \State $\mathit{selected} \gets \emptyset$
    \For{$i \gets n$ \textbf{downto} $1$}
        \If{$K[i][j] \neq K[i-1][j]$}
            \State $\mathit{selected} \gets \mathit{selected} \cup \{i\}$
            \State $j \gets j - w[i]$
        \EndIf
    \EndFor
    \State \Return $\mathit{result}, \mathit{selected}$
\EndProcedure
\end{algorithmic}
\end{algorithm}

\subsection{Complexity Analysis}

\begin{itemize}
    \item \textbf{Time Complexity:} $\Theta(nW)$ --- two nested loops over $n$ items and $W$ capacity units
    \item \textbf{Space Complexity:} $\Theta(nW)$ for the table $K$. Can be reduced to $\Theta(W)$ if only the optimal value (not the item set) is needed, by keeping only two rows of $K$.
    \item \textbf{Classification:} This is \emph{pseudo-polynomial} because $W$ is not polynomial in the input size (which is $O(n \log W)$ bits). The problem is NP-hard in general.
\end{itemize}

\subsection{Optimality Substructure}

The recurrence relation captures the optimal substructure:
\[
K[i][j] = \begin{cases}
0 & \text{if } i = 0 \text{ or } j = 0 \\
K[i-1][j] & \text{if } w_i > j \\
\max\bigl(v_i + K[i-1][j-w_i],\; K[i-1][j]\bigr) & \text{otherwise}
\end{cases}
\]

\section{Summary}

\begin{center}
\begin{tabular}{@{}llll@{}}
\toprule
\textbf{Algorithm} & \textbf{Paradigm} & \textbf{Time} & \textbf{Space} \\
\midrule
Merge Sort & Divide \& Conquer & $\Theta(n \log n)$ & $\Theta(n)$ \\
Dijkstra's & Greedy & $O(V \log V + E)^*$ & $\Theta(V)$ \\
0/1 Knapsack & Dynamic Programming & $\Theta(nW)$ & $\Theta(nW)$ \\
\bottomrule
\multicolumn{4}{@{}l@{}}{\footnotesize $^*$With Fibonacci heap} \\
\end{tabular}
\end{center}

\end{document}