Introduction

Every program, no matter how sophisticated, ultimately reduces to a sequence of simple operations carried out by a processor. Understanding how that happens is where this course begins.

How Computers Work

Computers, at the bare metal level, execute a sequence of machine instructions one after another to solve problems. Working with such machine instructions is difficult as,

1. The machine instructions are written in binary which makes them less readable to humans.
2. The machine instructions are CPU architecture specific — for example, the instructions that an x86 processor (found in most laptops and desktops) understands are different from the instructions that an ARM processor (found in smartphones and Apple Silicon Macs) understands. This makes machine instructions platform-dependent.

To overcome the readability issue, Assembly Language was developed. It is also a processor-specific instruction set, but the instructions are written with English words like,

ADD $1, $2
MOV EAX, 1
PUSH EBX

These assembly programs get assembled into the corresponding machine instructions and then executed.

This improved readability but platform compatibility remained a major issue. Also, assembly works directly with CPU registers, making even simple operations require many instructions. As both machine instructions and assembly work with the bare metal machine, they are referred to as Low-Level Languages.

High-Level Languages

To overcome the platform compatibility and verbosity issues of assembly, a new generation of programming languages was developed. These high-level programming languages share the same syntax (determined by the language's specification) regardless of the underlying CPU architecture. Before executing the program, it is translated into machine code specific to the target CPU.

The translation process can be of two types,

1. Compiled — the entire program is translated to machine code ahead of time by a compiler, producing an executable that runs directly (read more).
2. Interpreted — the program is executed line by line at runtime by an interpreter, without a prior compilation step (read more).

Note: The distinction between compiled and interpreted languages is out of scope for this course. The key point is that regardless of approach, high-level source code is ultimately executed as machine instructions on a specific CPU.

Though the invention of high-level languages made programming more accessible, the wide variety of languages with different syntaxes made it difficult to study programs in general. This created a need for a uniform notation to describe and analyze programs.

The Need for Formal Notation

If programs must be written in a specific language's syntax before they can be studied, then properties like performance and design patterns become hard to reason about in general. Thus, a language-independent description is needed.

This is where the study of Algorithms begins. An algorithm is a finite, ordered sequence of well-defined instructions that if followed, accomplishes a particular task. Algorithms are expressed in pseudocode — a structured, language-independent notation that captures logic clearly without being tied to any particular programming language's syntax.

By studying algorithms through pseudocode, their performance can be analyzed with mathematical models such as time complexity (how runtime scales with input size) and space complexity (how memory usage scales with input size). Recurring problem-solving patterns can also be identified to help design efficient algorithms for new problems.

Foundations of Algorithms

Definition

An algorithm is a finite, ordered sequence of well-defined instructions that, if followed, accomplishes a particular task.

From this definition we can derive the necessary properties that an algorithm must have.

Properties of Algorithms

1. Input: Zero or more quantities are externally supplied to the algorithm.
2. Output: At least one quantity will be produced by the algorithm. If an algorithm does not return anything then it must have an observable side-effect.
3. Definiteness: Each instruction is clear and unambiguous.
4. Finiteness: If we trace out the instructions of the algorithm, then for all cases, the algorithm must terminate after a finite number of steps.
5. Effectiveness: Every instruction must be so basic that it can be carried out, in principle, by a person using pen and paper. Moreover, each instruction must be feasible.

In the following sections we examine how algorithms are written.

Structure of Algorithms

Having defined what an algorithm is and its essential properties, we now look at how to express one precisely. Algorithmic notation can be considered as a language — it has its own keywords and structural rules for how instructions are ordered and numbered. The examples below introduce this notation and show how it relates to the properties defined in the previous chapter.

Example algorithms

Example 1:

Lets start with an algorithm that writes Hello World to understand it's generic structure.

\begin{algorithm}
    \caption{Write}
    \begin{algorithmic}
        \state Write "Hello World"
    \end{algorithmic}
\end{algorithm}

Now if we follow the instruction we will be instructed to write the string Hello World. From this example alone the following can be seen,

• The text Algorithm 1 is used to denote that it is an algorithm. The numbering is given for referring purpose and is usually optional.
• The algorithm has a name Write. It will be used to refer to the algorithm.
• It has a numbered line containing an instruction. The number is used mostly to identify at which instruction we are currently, while the algorithm is executing.
• The instruction itself.

Example 2:

Many times, it is required to store quantities or data in some place for future reusability to solve a problem. To take an example, consider an algorithm which swaps given two numbers.

\begin{algorithm}
    \caption{Swap}
    \begin{algorithmic}
        \input $num1$ and $num2$, the numbers to swap.
        \ensure Content of $num1$ and $num2$ are swapped.
        \state $temp \gets num1$
        \state $num1 \gets num2$
        \state $num2 \gets temp$
    \end{algorithmic}
\end{algorithm}

Here, $num1$ and $num2$ are externally supplied to Algorithm 2 — a direct instance of the Input property from the previous chapter.

If we follow the instructions line by line, one after the other, we see at the end of line 3, contents of $num1$ ends up in $num2$ and vice-versa. Tracing each variable at each step makes this clear. Assuming $num1 = a$ and $num2 = b$ initially:

This also shows why $temp$ is necessary: without it, executing $num1 \gets num2$ first would overwrite $a$, making it impossible to assign the original value of $num1$ into $num2$.

$num1$, $num2$ and $temp$ are named storage locations to store data and are called variables. The names themselves, like $num1$, are called identifiers.

From Algorithm 2 the following observations can be made,

• The same algorithm heading fields.
• The labeled Input and Ensure lines. These are not instructions as evident from the non-numbered lines but gives more context to the reader. Input describes what quantities are to be supplied from the outside. Ensure describes what is the effect of the algorithm.
• Lines like $temp \gets num1$. The symbol $\gets$ is an operator, more specifically it's an assignment operator. It assigns the value of the right hand side quantity to the left hand side quantity. Will have more discussion on operators in subsequent chapters.

Note: Different authors and textbooks follow different algorithmic notations. Though the specific keywords and symbols may vary, the core constructs they express are the same. These building blocks also appear in all general-purpose programming languages such as C, Java, and Python.

Generic Anatomy

Having seen the examples, lets define the generic structure of algorithms that are followed throughout this book,

1. Header: The header section is used to identify the algorithm. It has the form of, $$ \text{Algorithm <optional number> <algorithm name>} $$

2. Body: The body section contains

   • Algorithm Conditions: There are two types of condition checks that an algorithm can mention,

     • Precondition: Checks or assertions that has to be true before the algorithm begins it's execution. So, the algorithm always assumes these checks are done and does execution accordingly. If the input doesn't meet this condition, the algorithm isn't guaranteed to work.

       Some of the commonly used preconditions are,

       • $\text{Input}$: The quantities that are externally supplied to the algorithm.
       • $\text{Require}$: The condition that the Inputs must satisfy.

     • Postcondition: Checks or assertions that is guaranteed to be true after the algorithm completes it's execution, provided the precondition was met initially.

       Some of the commonly used postconditions are,

       • $\text{Output}$: The quantities that the algorithm produces.
       • $\text{Ensure}$: The condition that the algorithm guarantees to be true on the output. If output is not present then the algorithm has some explicit side-effect and the ensure block describes it instead — corresponding to the Output property established earlier: an algorithm that returns nothing must have an observable side-effect. For example, Algorithm 2 (Swap) produces no output value, so its Ensure block describes the side effect instead.

   • Algorithm Instructions: The actual lines that tell what to do based on the Preconditions. For the Definiteness property to hold, each instruction must be clear and unambiguous. Instructions can be sequential (one after another), conditional (do something only if a condition holds), or iterative (repeat something). After following all the instructions the Algorithm ends with satisfying the Postconditions. Often these instructions are also called Statements and in this text we use it interchangeably.

   Note: A set of Statements is called a Block.

In this text we follow these mentioned conventions.

Elements of Algorithmic Notation

As seen earlier, the actual instructions of an Algorithm follows certain structure. There are certain words or symbols that are algorithm specific, like $\gets$, the assignment operator and some are supplied by the programmer like $temp$, $num1$, $num2$ etc to identify some storage locations.

We define some terminologies which will be frequently used in this text.

Useful Terminologies

• Keyword: A keyword is a reserved word which is intended for the algorithm.
• Identifier: An identifier is a name given to a quantity. The Identifier should not be a keyword.
• Variable: A quantity whose value can change during the execution of an Algorithm.
• Constant: A quantity whose value can never change during the execution of an Algorithm.
• Data Type: Data-type refers to the type of data a variable or constant holds. Though it is rarely explicitly mentioned in the algorithm but mostly it is inferred from the context.
• Operator: Symbols which operates on quantities.

Examples

Consider the following algorithm,

\begin{algorithm}
    \caption{Circle Area}
    \begin{algorithmic}
        \input $r$, the radius of the circle whose area is to be calculated.
        \ensure $r$ is non-negative.
        \output Area of the circle of radius $r$.

        \state $PI \gets 3.14159$
        \state $ area \gets PI \cdot r \cdot r$
        \return area
    \end{algorithmic}
\end{algorithm}

Note: Constants as convention is written in all caps.

In this example we can Identify the followings,

The algorithm can also be written in smaller steps as the value of $\pi$ is a known constant

\begin{algorithm}
    \caption{Circle Area v2}
    \begin{algorithmic}
        \input $r$, the radius of the circle whose area is to be calculated.
        \ensure $r$ is non-negative.
        \output Area of the circle of radius $r$.

        \return $\pi \cdot r^2$
    \end{algorithmic}
\end{algorithm}

Observe that the return statement is a mathematical expression i.e., $\pi \cdot r^2$, which is acceptable in Algorithmic notations.

Note: Algorithmic Notations should mostly focus on readability but readable statements often becomes too verbose so most of the time mathematical expressions and set notations are used to keep statements short and readable.

Common Data Types

As discussed earlier, data types are rarely explicitly mentioned within algorithms. From context, the data type of a variable or constant is inferred It's important to understand what data types are and in which contexts which data type is suitable.

Primitive Data Type

A Primitive Data Type is a single-valued data type which cannot be decomposed into any other data type.

Different Primitive Data Types:

Note: Operators and Operands are discussed in the next chapter

Composite Data Type

A Composite Data Type is composed of multiple Primitive Data Types or some other composite data types.

A Composite Data Type is almost always explicitly stated in algorithms, as otherwise, it will be difficult to interpret it.

Different Composite Data Types

Example 1:

\begin{algorithm}
    \caption{Student Record}
    \begin{algorithmic}
    \output A Student named "John Doe" with id 1 and CGPA 8.76.
    \state $Student :=$ $\textbf{record}$ \{
        \state $\textbf{ Integer}$ $id$,
        \state $\textbf{  Real}$ $cgpa$,
        \state $\textbf{  String}$ $name$
    \state \}
    \state
    \state $\textbf{Declare}$ $student$ as $Student$
    \state
    \state $student.id \gets 1$
    \state $student.cgpa \gets 8.76$
    \state $student.name \gets "John Doe"$
    \state
    \return $student$
    \end{algorithmic}
\end{algorithm}

Let's explain the algorithm line-by-line,

Note: The data type $Student$ is written with capital $S$, whereas the variable $student$ is written with small $s$. This is a convention to distinguish between data types and variables.

Operators and Operands

Operators are one of the fundamental ways to manipulate data. In algorithms and computer programs, Operators are instructions which does some computation on a given data. The data on which an operator operates is called Operand.

Arity of an operator

Arity of an operator refers to the number of operand the operator takes. An n-ary operator operates on n operands.

From this definition, it is apparent that a binary operator refers to operators that operates on two operands.

Symbols table

Throughout this text, as a shorthand notation, many logical symbols will be used. It is important to understand the meanings of such symbols.

Assignment Operator

Assignment Operator assigns a value to a variable.

Generic Form: $x \gets y$ where $x$ is an identifier and $y$ is the value of a data type. If $y$ is an expression the evaluated value gets assigned to $x$.

Note: $:=$ can also be used as an assignment operator but in this text we stay true to it's implied meaning (see symbols table) and use it only to define new items like new data types or constants.

Arithmetic Operator

Arithmetic Operator operates on numeric data types (like integer and reals) and produces same type of data.

Generic Form: $x \circ y$, where $x,y \in \mathbb{R}$ and $\circ \in${+, -, *, /, ^, %} i.e, the operator can be addition, subtraction, multiplication, division, exponentiation and modulus.

Similar to maths, operations and variables can be combined into an expression and brackets can be used to specify custom order of execution (follow BODMAS rule).

Logical Operator

Logical Operator operates on boolean types and produces another boolean type.

Generic Form: $x \circ y$, where $x,y \in \{True, False\}$ and $\circ \in \{ \land, \lor, \oplus, \odot \}$. An unary logical operator $\lnot$ also exists which flips the given boolean value.

These logical operators' behavior can be observed by studying their respective Truth Tables.

Logical AND Truth Table:

Logical OR Truth Table:

Logical NOT Truth Table:

Logical XOR Truth Table:

Logical XNOR Truth Table:

Bit-wise Operator

The bit-wise operator operates on binary sequences, fundamentally bit-wise. As within computer, data types like Strings, Integers and Reals (Floats or Doubles) are represented as sequences of bits, Bit-wise operators can operate on all these data types. The output of this operator is also another binary sequence but the representation of the result depends on which type of variable it will reside in.

Relational Operator

Relational Operator operates on numeric types and outputs boolean type. In summery Relational Operator compares give quantities. These operators can also operate on characters and Strings but the comparison happens based on the lexicographical ordering.

General Form: $x \circ y$, where $x, y$ are of same data type and $x \in \{ =, \ne, \gt, \ge, \lt, \le \}$.

Control flow of an Algorithm

As seen in earlier chapters, Algorithms are read from top towards bottom and the instructions on each step are followed accordingly. This flow of reading instructions is called Control Flow and it always goes from top towards bottom.

All the previously described algorithms follow this same order of flow and without it the algorithm will not make any sense.

This default control flow is too restrictive. For example, lets take the following example of finding sum of all the elements of an array,

\begin{algorithm}
    \caption{Bad Sum of Array elements}
    \begin{algorithmic}
        \input $arr$, the array of 10 items
        \output $sum$ of all 10 items
        \state $sum \gets arr[0] + arr[1] + arr[2] + \cdots + arr[9]$
        \state \return $sum$
    \end{algorithmic}
\end{algorithm}

This does returns the sum of all $10$ elements within the array but it has a major flaw as what if in future we are to add more than $10$ items?. This algorithm is not capable of doing this. It would be good to have a generic algorithm which could iterate over the array elements.

Consider one more problem, given an integer and we are to return "Fizz" if it's a multiple of $3$ or "Buzz" if it's a multiple of $5$ or "FizzBuzz" if it's a multiple of $3$ and $5$.

It is impossible to solve this problem with the default control flow.

This is why there exists instructions like Conditional, Iterative and Procedure Call to make this default control flow jump to another instruction which makes this algorithmic notation Turing Complete.

Conditional Statements

Conditional statements are used to run a particular set of instructions based on specific condition. These are also called Branching Statements/Instructions.

Each Condition is nothing but a Boolean i.e, it will have a value of either True or False. So, the condition being true implies that the condition has a value True.

If

Given a condition being true, if a set of statements is to be executed then use If statements.

Syntax:

\begin{algorithm}
    \begin{algorithmic}
    \if{<condition>}
        \state <statement $1$>
        \state <statement $2$>
        \state $\cdots$
        \state <statement $n$>
    \endif
    \end{algorithmic}
\end{algorithm}

It can be intuitively read as,

If condition is true then do these.

If - Else

Given a condition being true, if a set of statements is to be executed and on the condition being false another set of statements is to be executed then If - Else statements can be used.

Syntax:

\begin{algorithm}
    \begin{algorithmic}
    \if{<condition>}
        \state <statement $1$>
        \state <statement $2$>
        \state $\cdots$
        \state <statement $n$>
    \else
        \state <statement $n+1$>
        \state <statement $n+2$>
        \state $\cdots$
        \state <statement $n+m$>
    \endif
    \end{algorithmic}
\end{algorithm}

It can be intuitively read as,

If condition is true then do these; Else do these.

If - Else If - Else

Given a condition being true, if a set of statements is to be executed, on a different condition being true another set of statements is to be executed and on all of those conditions being false another set of statements is to be executed then If - Else If - Else statements can be used.

Syntax:

\begin{algorithm}
    \begin{algorithmic}
    \if{<condition 1>}
        \state <statement set $1$
    \elseif{<condition 2>}
        \state <statement set $2$>
\state $\cdots$
    \elseif{<condition n-1>}
        \state <statement set $n-1$>
    \else
        \state <statement set $n$>
    \endif
    \end{algorithmic}
\end{algorithm}

It can be intuitively read as,

If condition $1$ is true then do these; Else If condition $2$ is true then do these; $\cdots$ ; Else If condition $n-1$ is true then do these; Else do these.

Examples

Fizz-Buzz:

Lets take the problem discussed in Control flow of an Algorithm,

Given an integer, we are to return "Fizz" if it's a multiple of $3$ or "Buzz" if it's a multiple of "5" or "FizzBuzz" if it's a multiple of $3$ and $5$. If the integer satisfies none of the condition the return the number as is.

We can use the $mod$ operator on the input. Recall from Arithmetic Operators, that a modulus operator (denoted by $mod$ or $\%$) of the form $x \% y $ returns the remainder when $x$ is divided by $y$. If the remainder is $0$ then $x$ is divisible by $y$ and $x$ will be an integer multiple of $y$. With this we write the algorithm as follows,

\begin{algorithm}
    \caption{Fizz-Buzz}
    \begin{algorithmic}
        \input $n$
        \require $n$ is an integer
        \output "Fizz", "Buzz" or "Fizz-Buzz" if $n$ is a multiple of either $3$, $5$ or $3$ and $5$ respectively. If $n$ does not satisfy none of the conditions then return $n$ as is.

        \if{$n \% 3 = 0$ \and $n \% 5 = 0$ }
            \return "Fizz-Buzz"
        \elseif{$n \% 3 = 0$}
            \return "Fizz"
        \elseif{$n \% 5 = 0$}
            \return "Buzz"
        \else
            \return $n$
        \endif
    \end{algorithmic}
\end{algorithm}

Though this algorithm is correct, it contains a lot of If statements and conditions. We can remove the else block entirely by using the Exit First strategy. Consider the following algorithm.

\begin{algorithm}
    \caption{Fizz-Buzz v2}
    \begin{algorithmic}
        \input $n$
        \require $n$ is an integer
        \output "Fizz", "Buzz" or "Fizz-Buzz" if $n$ is a multiple of either $3$, $5$ or $3$ and $5$ respectively. If $n$ does not satisfy none of the conditions then return $n$ as is.

        \if{$n \% 15 = 0$ }
            \return "Fizz-Buzz"
        \endif

        \if{$n \% 3 = 0$}
            \return "Fizz"
        \endif

        \if{$n \% 5 = 0$}
            \return "Buzz"
        \endif
        
        \return $n$
    \end{algorithmic}
\end{algorithm}

This new algorithm is significantly better as,

• It has less number of checks. $n \% 15 = 0$, $n \% 3 = 0$ and $n \% 5 = 0$ instead of $n \% 3 = 0$ twice and $n \% 5 = 0$ twice.
• Less blocks of instructions. 3 if blocks instead of 4 if-elseif-else blocks.

These won't cause much of an issue when tracing the algorithm by hand but when it's implemented in a computer comparison like this matters. We will explore more such comparisons in Performance Analysis of Algorithms part of the text.