LaTeX for CS Papers: Algorithms, Code, Proofs, and Diagrams

\usepackage{algorithm}
\usepackage{algpseudocode}
 
\begin{algorithm}
\caption{Binary Search}\label{alg:binary}
\begin{algorithmic}[1]
\Procedure{BinarySearch}{$A, target$}
    \State $left \gets 0$
    \State $right \gets \Call{Length}{A} - 1$
    \While{$left \leq right$}
        \State $mid \gets \lfloor (left + right) / 2 \rfloor$
        \If{$A[mid] = target$}
            \State \Return $mid$
        \ElsIf{$A[mid] < target$}
            \State $left \gets mid + 1$
        \Else
            \State $right \gets mid - 1$
        \EndIf
    \EndWhile
    \State \Return $-1$
\EndProcedure
\end{algorithmic}
\end{algorithm}

\usepackage[ruled,vlined]{algorithm2e}
 
\begin{algorithm}[H]
\SetAlgoLined
\KwIn{Array $A$, target value $x$}
\KwOut{Index of $x$ or $-1$}
$left \leftarrow 0$\;
$right \leftarrow n-1$\;
\While{$left \leq right$}{
    $mid \leftarrow \lfloor(left + right)/2\rfloor$\;
    \eIf{$A[mid] = x$}{
        \Return $mid$\;
    }{
        \If{$A[mid] < x$}{
            $left \leftarrow mid + 1$\;
        }
        \Else{
            $right \leftarrow mid - 1$\;
        }
    }
}
\Return $-1$\;
\caption{Binary Search}
\end{algorithm}

\usepackage{listings}
\usepackage{xcolor}
 
\lstdefinestyle{mystyle}{
    backgroundcolor=\color{gray!10},
    basicstyle=\ttfamily\footnotesize,
    keywordstyle=\color{blue}\bfseries,
    stringstyle=\color{orange},
    commentstyle=\color{green!60!black},
    numbers=left,
    numberstyle=\tiny\color{gray},
    breaklines=true,
    tabsize=4
}
\lstset{style=mystyle}
 
\begin{lstlisting}[language=Python, caption={Quicksort Implementation}]
def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quicksort(left) + middle + quicksort(right)
\end{lstlisting}

\usepackage{minted}
 
\begin{minted}[linenos, bgcolor=gray!10]{python}
def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quicksort(left) + middle + quicksort(right)
\end{minted}

\usepackage{listings}
\lstinline{for i in range(n)}
 
% Or with minted:
\mintinline{python}{for i in range(n)}
 
% Or simple:
\texttt{for i in range(n)}

The algorithm runs in $O(n \log n)$ time.
Space complexity is $\Theta(n)$.
The lower bound is $\Omega(n)$.

\newcommand{\bigo}[1]{\ensuremath{\mathcal{O}(#1)}}
\newcommand{\bigtheta}[1]{\ensuremath{\Theta(#1)}}
\newcommand{\bigomega}[1]{\ensuremath{\Omega(#1)}}
 
% Usage:
The algorithm runs in \bigo{n \log n} time.

\newcommand{\cclass}[1]{\ensuremath{\mathsf{#1}}}
 
The problem is in \cclass{NP}.
This shows \cclass{P} = \cclass{NP} implies...
It's \cclass{PSPACE}-complete.

\usepackage{tikz}
\usetikzlibrary{arrows.meta, positioning, automata}
 
% Finite automaton
\begin{tikzpicture}[
    ->,
    >=Stealth,
    node distance=2cm,
    every state/.style={thick, fill=gray!10}
]
\node[state, initial] (q0) {$q_0$};
\node[state, right of=q0] (q1) {$q_1$};
\node[state, accepting, right of=q1] (q2) {$q_2$};
 
\path (q0) edge node[above] {0} (q1)
      (q1) edge node[above] {1} (q2)
      (q0) edge[loop above] node {1} ()
      (q1) edge[loop above] node {0} ();
\end{tikzpicture}

\usetikzlibrary{graphs, graphdrawing}
\usegdlibrary{trees}
 
% Binary tree
\begin{tikzpicture}[
    every node/.style={circle, draw, minimum size=7mm}
]
\graph[tree layout, grow=down, sibling distance=15mm] {
    8 -> {
        4 -> {2, 6},
        12 -> {10, 14}
    }
};
\end{tikzpicture}

\usetikzlibrary{chains}
 
\begin{tikzpicture}[
    node distance=1cm and 2cm,
    neuron/.style={circle, draw, minimum size=8mm},
    layer/.style={rectangle, draw, minimum height=4cm}
]
% Input layer
\foreach \i in {1,...,3}
    \node[neuron] (i\i) at (0, -\i) {$x_\i$};
 
% Hidden layer
\foreach \i in {1,...,4}
    \node[neuron] (h\i) at (2, -\i+0.5) {};
 
% Output layer
\foreach \i in {1,...,2}
    \node[neuron] (o\i) at (4, -\i-0.5) {$y_\i$};
 
% Connections
\foreach \i in {1,...,3}
    \foreach \j in {1,...,4}
        \draw[->] (i\i) -- (h\j);
\foreach \i in {1,...,4}
    \foreach \j in {1,...,2}
        \draw[->] (h\i) -- (o\j);
\end{tikzpicture}

\usepackage{amsthm}
 
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}{Definition}[section]
 
\begin{theorem}[Halting Problem]
\label{thm:halting}
The halting problem is undecidable.
\end{theorem}
 
\begin{proof}
Suppose for contradiction that there exists a Turing machine $H$
that decides the halting problem...
\end{proof}

\begin{proof}
We proceed by induction on $n$.
 
\textbf{Base case:} When $n = 0$, the claim holds trivially.
 
\textbf{Inductive step:} Assume the claim holds for $n = k$.
We show it holds for $n = k + 1$...
\end{proof}

\newenvironment{case}[1]{\textbf{Case #1:}}{}
 
\begin{proof}
We consider three cases:
\begin{case}{$x < 0$}
    In this case, $f(x) = -x$, so...
\end{case}
\begin{case}{$x = 0$}
    Here $f(x) = 0$, which trivially satisfies...
\end{case}
\begin{case}{$x > 0$}
    Finally, when $x > 0$, we have $f(x) = x$...
\end{case}
\end{proof}

% Sets
$A \cup B$          % Union
$A \cap B$          % Intersection
$A \setminus B$     % Difference
$A \subseteq B$     % Subset
$x \in A$           % Membership
$\emptyset$         % Empty set
$\mathbb{N}$        % Natural numbers
$\{x \mid x > 0\}$  % Set builder
 
% Logic
$\forall x$         % For all
$\exists x$         % There exists
$\neg p$            % Negation
$p \land q$         % Conjunction
$p \lor q$          % Disjunction
$p \Rightarrow q$   % Implication
$p \Leftrightarrow q$ % Equivalence

\newcommand{\graph}{\ensuremath{G = (V, E)}}
 
Let \graph be an undirected graph where $|V| = n$ and $|E| = m$.
The degree of vertex $v$, denoted $\deg(v)$, is...

\usepackage{amsmath}
 
$\Pr[X = k]$                    % Probability
$\mathbb{E}[X]$                 % Expectation
$\text{Var}[X]$                 % Variance
$X \sim \mathcal{N}(\mu, \sigma^2)$  % Distribution

\usepackage{booktabs}
 
\begin{table}[t]
\centering
\caption{Algorithm Performance Comparison}
\label{tab:performance}
\begin{tabular}{lrrr}
\toprule
Algorithm & Time (ms) & Memory (MB) & Accuracy (\%) \\
\midrule
Baseline & 245.3 & 128.4 & 87.2 \\
Proposed & \textbf{123.7} & 142.1 & \textbf{94.6} \\
Variant A & 189.2 & \textbf{98.3} & 91.3 \\
\bottomrule
\end{tabular}
\end{table}

\begin{table}[t]
\centering
\caption{Time and Space Complexity}
\begin{tabular}{lcc}
\toprule
Operation & Time & Space \\
\midrule
Insert & $O(\log n)$ & $O(1)$ \\
Delete & $O(\log n)$ & $O(1)$ \\
Search & $O(\log n)$ & $O(1)$ \\
Build & $O(n \log n)$ & $O(n)$ \\
\bottomrule
\end{tabular}
\end{table}

% If algorithm and figure numbering conflict:
\usepackage{algorithm}
\floatname{algorithm}{Algorithm}
\renewcommand{\thealgorithm}{\arabic{algorithm}}

\lstset{breaklines=true}
% Or for minted:
\begin{minted}[breaklines]{python}

% Inside algorithmic:
\State $x \gets x + 1$ \Comment{Increment $x$}

% Good: one sentence per line
This is the first sentence.
This is the second sentence.
This helps with git diffs.
 
% Bad: paragraph as single line
This is the first sentence. This is the second sentence. This makes git diffs hard to read.

% Complexity
$O(n)$, $\Theta(n)$, $\Omega(n)$
 
% Probability
$\Pr[E]$, $\mathbb{E}[X]$
 
% Sets
$\mathbb{N}, \mathbb{Z}, \mathbb{R}$
 
% Logic
$\forall, \exists, \neg, \land, \lor$