%!TEX program = lualatex
\documentclass[handout, problems]{../../latex-common/cse311-common}
    \sectionnumber{1}
    \topic{Writing Pseudocode}

\begin{document}
    \maketitle
Most problems in 421 are written is pseudocode. The idea for pseudocode is to communicate a \textbf{high-level} description of an algorithm. Your goal is to be specific and concrete enough that
\begin{itemize}
    \item A competent programmer (say, one of your classmates) could implement the code and get the right output.
    \item You can analyze the running time.
    \item You can prove the code correct.
\end{itemize}

\textbf{BUT} still be high-level enough that
\begin{itemize}
    \item A reader can quickly and easily understand the main ideas behind your algorithm. 
    \item A reader unfamiliar with $\langle~\text{your favorite language}~\rangle$ can still understand your algorithm and implement it in their favorite language.
\end{itemize}

\section{Use Universal Code Idioms Explicitly}
Loops, conditionals, and especially recursion are generally clearer in code-like structures, rather than in English. The only exception is extremely simple loops/conditionals.

\subsection{Examples}
\textbf{Good}
\begin{algorithmic}
    \For{$i$ from $1$ to $n$}
        \State $\texttt{sum} \gets \texttt{sum}+i$
        \If{\texttt{sum} is even}
            \State print \texttt{i}
        \EndIf
    \EndFor
\end{algorithmic}

\textbf{Bad}\\
    For every integer from $1$ to $n$, add the integer to the running sum. If the sum to that point is even then print that integer.

The English is hard to understand! Is the ``If...'' inside the loop or outside? Even very ideas like this are probably better in code form. On the other hand, this principle isn't universal.
\subsection{Examples}
\textbf{Ok}
\begin{algorithmic}
    \If{$n < 100$}
        \State $\texttt{triangleCount} \gets 0$
        \For{each vertex $u$}
            \For{each vertex $v$}
                \For{each vertex $w$}
                    \If{$u \neq v$ and $v \neq w$ and $u \neq w$}
                        \If{$(u,v)\in E$ and $(u,w)\in E$ and $(v,w)\in E$}
                            \State \texttt{triangleCount++}
                        \EndIf
                    \EndIf
                \EndFor
            \EndFor
        \EndFor
        \State \texttt{trangleCount} $\gets$ \texttt{triangleCount} / 6 \Comment{divide by 3! for overcounting}
    \EndIf
\end{algorithmic}
\textbf{Better}
\begin{algorithmic}
    \If{$n < 100$}
        \State Brute-force check every triple of distinct vertices and count the number of triangles. 
    \EndIf
\end{algorithmic}

Simple code, or code that is conceptually-simple, but takes up a lot of space can often be replaced 
\section{Use Variable Names}



Look at the bad example from the last section. ``The running sum'' and ``the sum'' refer to the same thing, but we used different words for them. In everyday English this is ok, but potentially confusing. In the last line is ``that integer'' the iteration-counting variable ($\texttt{i}$) or the running sum (\texttt{sum})? 

In general, anytime
\begin{itemize}
    \item You need 3-or-more words to refer to a thing (like ``the vertex that just came off the queue'' or ``the edge we are currently examining'')  OR
    \item You refer to the same thing with words multiple times (``the integer'' and later ``that integer'')
\end{itemize}
You probably want a variable name.

\section{Use Math Notation and Terminology}
\textbf{Good}
\begin{algorithmic}
    \State Let $\bar{x}$ be the mean of $x_1,...,x_n$
\end{algorithmic}

\textbf{Good}
\begin{algorithmic}
    \State $\texttt{mean-x} \gets \frac{x_1+\cdots +x_n}{n}$
\end{algorithmic}

\textbf{Bad}
\begin{algorithmic}
    \State \texttt{sum} $\gets 0$
    \For{$i$ from $0$ to $n-1$}
        \State $\texttt{sum} += x[i]$
    \EndFor
    \State $\texttt{mean} \gets \texttt{((double) sum )/ n}$
\end{algorithmic}
It takes 4-or-so lines of real code to communicate this idea. It takes one line or math or English. Use the thing that's faster to read, write, and understand!

\section{Make sure your intention is unambiguous}
A sentence like:

for every element: decide using memoization if it's better to keep this element or omit this element by comparing the maximum cost including this element vs maximum cost excluding this element

is not specific enough for pseudocode. What are those values that I'm comparing? Once I know them what does it mean to be better (bigger? smaller? Closer to a target value?). This would be a good 1-sentence of intuition in a comment; it's not specific enough for a programmer to implement. 
% \section{Don't rely on language-specific quirks}
% Language-specific-quirks are things that work differently between languages. Things like integer vs. floating-point division, short-circuiting evaluation of booleans, or obscure code-golf-tricks should be explained in a comment or (if possible) totally avoided.

% \textbf{Bad}
% \begin{algorithmic}
%     \State \If{}
% \end{algorithmic}

\section{In general...}

\begin{itemize}
    \item If you could put your pseudocode into a python interpreter, and it would pretty much compile, you're probably including too much detail.
   \item If you ever use three or more words to refer to an object (like "the vertex we're processing now" or "the next vertex to come out of the queue") you probably want to make things more code-like (e.g. a variable name like \texttt{curr} or notation like \texttt{next = queue.removeMin()})
    \item Phrases like "repeat this process until..." or "...and so on" or "make a recursive call" are likely to be ambiguous in English and are much better written in code form.
    \item Use good style in your pseudocode! Indent and/or use braces for nested structures, use meaningful variable names, you can even write comments!
\end{itemize}

\section{A Bigger Example}
Modify BFS to find all vertices $v$ such that there is a walk from $u$ to $v$ using exactly $3$ edges (in an unweighted graph $G$). 

\textbf{Bad}\\
Modify BFS by adding a boolean \texttt{reachIn3} and an integer \texttt{dist}. Every time you process an edge, update the destination vertex's \texttt{dist} to be one more than the other vertex's \texttt{dist}. If it's 3, set \texttt{reachIn3} to be true. Put the vertex on the queue. Additionally, if a distance ever becomes 4 or more, the algrotihm ends.

This snippet is very hard to understand! What's ``the other rvertex''? Which vertex is ``the vertex'' put onto the queue? Variable names would make this better, but there are still A LOT of changes here to understand exactly what is being said. 

\textbf{good}
\begin{algorithmic}
    \State Place $u$ on a Queue $q$, set $u.\texttt{dist}$ to $0$.
    \While{$q$ is not empty}
        \State \texttt{curr} $\gets$ $q.\texttt{dequeue()}$
        \For{each edge $(\texttt{curr},v)$}
            \State $v.dist \gets \texttt{curr.dist}+1$
            \If{\texttt{v.dist}==3}
                \State $\texttt{v.reach3}\gets \texttt{true}$
            \ElsIf{\texttt{v.dist}<3}
                \State $\texttt{q.enqueue(v)}$
            \Else
                \State break
            \EndIf
        \EndFor
    \EndWhile
\end{algorithmic}

\section{In \LaTeX}
We use the AlgPseudocode package to make our staff solutions. algorithm2e is another commonly-used package. 
Both have documentation and examples available. 

We use an alternate font to refer to variable names or other code-like things. We use $\backslash$texttt$\{\}$, but other fonts (or even the standard font) is fine as long as we can understand.

If you wish to avoid one of the \LaTeX packages and just type what you want to show up, you can try the verbatim environment (put $\backslash$begin\{verbatim\} and $\backslash$end\{verbatim\} around the text you'd like to appear). Note that you cannot use commands or math-mode inside the verbatim environment. The main advantage of verbatim is that it doesn't ``eat'' your tabs/spaces and newlines the way normal \LaTeX does. 

\end{document}