An algorithm in computer science is defined as a set of instructions or a step-by-step procedure for solving a problem or accomplishing a specific task. It's like a recipe, providing a step-by-step guide for a computer to follow. It's not the code itself, but rather the underlying logic that determines how the code works.

Image credits: Rishal Hurbans

Algorithms are fundamental to the field of computer science and are used in a wide variety of applications, including data processing, automated reasoning, and calculations.

Key characteristics of algorithms

Input: An algorithm must have zero or more inputs, which are the values or data it processes.
Output: It should produce one or more outputs, which are the results of the algorithm's processing.
Definiteness: Each step of the algorithm must be clear and unambiguous.
Finiteness: The algorithm must terminate after a finite number of steps.
Effectiveness: Each operation in the algorithm must be sufficiently basic that it can be performed exactly and in a finite amount of time.
Generality: The algorithm should be applicable to a set of inputs.

Algorithms can be represented in various ways, including pseudocode, flowcharts, and actual programming languages. They are essential for the development of software and the functioning of digital systems.

Why do we need algorithms?

Algorithms are essential in computer science and information technology for several key reasons:

Problem Solving: Algorithms provide a systematic method for solving problems, both simple and complex. They are the step-by-step procedures for performing calculations, processing data, and automating reasoning tasks.
Efficiency and Optimization: Algorithms help in finding the most efficient way to process data and perform tasks. In many cases, multiple algorithms can solve the same problem, but some do so more efficiently than others. Efficient algorithms can save time, reduce computational resources, and improve overall performance, which is crucial in areas like data analysis, machine learning, and real-time processing.
Standardization and Clarity: Algorithms offer a standardized way to describe and implement solutions to problems. This clarity and standardization facilitate better communication among programmers and between programmers and machines. It ensures that a solution is not just understood but can be consistently and correctly implemented.
Scalability and Reusability: Good algorithms can handle increases in data volume or complexity. They are scalable and can be adapted or reused in different contexts and for various purposes. This reusability and scalability make them versatile tools in software development.
Predictability and Reliability: Algorithms provide predictable outcomes. Given the same input, an algorithm should always produce the same output. This predictability and reliability are fundamental for building trust in computer systems, especially in critical applications like medical systems, financial software, and safety systems.
Facilitates Decision Making: In many modern systems, especially in AI and machine learning, algorithms play a crucial role in decision-making processes. They can analyze large datasets to provide insights, make predictions, or automate decisions that would be impractical or impossible for humans to make quickly and accurately.
Foundation for Innovation: Algorithms are foundational in developing new technologies and applications. From basic data sorting and searching to complex machine learning models, algorithms are at the heart of innovation in computer science, driving advancements in fields like bioinformatics, quantum computing, and artificial intelligence.
Ubiquitous in modern life: Algorithms are pervasive in our daily lives, often working behind the scenes:
- Routing traffic on GPS apps
- Recommending movies or products
- Detecting spam email
- Matching people on dating sites
- Powering virtual assistants like Siri and Alexa
- Enabling online banking and shopping
- Securing online transactions

Algorithms are the backbone of computer science and technology. They enable efficient and effective problem-solving, data processing, automation, and innovation across a vast range of applications and industries.

Expressing algorithms

In computer science, algorithms can be expressed in various ways to ensure they are clearly understood, accurately implemented, and effectively communicated. The most common methods of expressing algorithms include:

Pseudocode: Pseudocode is a method of describing an algorithm in a structured but readable format. It's not actual code in a specific programming language but rather a way to represent the logic of an algorithm using natural language mixed with programming-like constructs IF, ELSE, FOR, WHILE, REPEAT, INPUT, OUTPUT, etc. Pseudocode is useful for explaining the algorithm's logic without getting bogged down in the syntax of a particular programming language.

Example: Pseudocode for finding the largest number in a list:
```
 // Input: A list of numbers
 // Output: The largest number in the list

 DECLARE largest_number
 DECLARE current_number

 SET largest_number TO the first number in the list

 FOR each number IN the list
   IF current_number > largest_number
     SET largest_number TO current_number

 OUTPUT largest_number
```
Flowcharts: A flowchart is a graphical representation of an algorithm. It uses various shapes like rectangles, diamonds, and ovals to denote different types of operations (like processing steps, decision points, and start/end points), and arrows to show the flow of control.

Flowcharts are particularly helpful for visualizing the flow of an algorithm, making it easier to understand the decision-making pathways and processing sequences.
Programming Languages: Algorithms can be directly implemented in programming languages like Python, Java, C++, and many others. This implementation is the actual code that can be executed by a computer. While pseudocode is language-agnostic and flowcharts are visual, programming language implementations are practical and operational, allowing for actual execution and testing of the algorithm.

Example: Find the largest number in a list:
```
 def find_maximum(numbers):
     maximum = numbers[0]
     for number in numbers:
         if number > maximum:
             maximum = number
     return maximum

 # Example usage
 numbers = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
 print(find_maximum(numbers))
```
Formal Methods: In more academic or theoretical contexts, algorithms can be expressed using formal methods. This includes mathematical notation and theoretical models like Turing machines or lambda calculus. These methods are more abstract and are typically used in theoretical computer science to prove properties about algorithms such as correctness and computational complexity.

Example: Formal description of finding the largest number in a list.
Define max as a function where max(a1, a2, ..., an) equals ai such that for all j (1 ≤ j ≤ n), ai ≥ aj.
This is a more abstract mathematical definition and is less about the process and more about the definition of what it means to be the maximum.
Natural Language Descriptions: For broader audiences or introductory explanations, algorithms can be described using natural language (plain English or any other spoken language). This approach is less technical and more focused on conveying the general idea or logic behind the algorithm without delving into specific details or technicalities.

"To find the largest number in a list, start by assuming the first number is the largest. Then, compare each number in the list with this number. If you find a number that's larger, replace your current largest number with this one. Continue until you've looked at every number. The largest number you've found is the maximum."

Each of these methods has its advantages and is suited to different stages of the algorithm development process, from initial concept and design to implementation and analysis. The choice of expression often depends on the audience, the complexity of the algorithm, and the stage of development.

Types of algorithms

In computer science, algorithms can be categorized into various types based on their approach, structure, and application. Here are some of the major types of algorithms:

Search Algorithms: These are designed to search for an element in a data structure. Examples include linear search and binary search.
Sort Algorithms: These algorithms arrange data in a certain order (e.g., ascending, descending). Common sorting algorithms include quicksort, mergesort, heapsort, and bubble sort.
Computational Algorithms: These are used for mathematical computations. Examples include algorithms for matrix multiplication, GCD calculations, and prime number generation.
Graph Algorithms: These are used for processing graphs (networks of nodes and edges). Examples include Dijkstra's algorithm for shortest paths, Kruskal's and Prim's algorithms for minimum spanning trees, and depth-first search (DFS) and breadth-first search (BFS).
Dynamic Programming Algorithms: Used for solving complex problems by breaking them down into simpler subproblems. Examples include the Fibonacci sequence calculation, the knapsack problem, and the shortest path problem.
Divide and Conquer Algorithms: These algorithms recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem. QuickSort and MergeSort are classic examples.
Greedy Algorithms: These make the most optimal choice at each step to find the overall optimum solution. Examples include Huffman Coding and Prim’s algorithm for minimum spanning trees.
Backtracking Algorithms: These are used for finding all (or some) solutions to problems that incrementally build candidates to the solutions and abandons a candidate ("backtracks") as soon as it determines that the candidate cannot possibly be completed to a valid solution. The classic example is the Eight-Queens problem.
Randomized Algorithms: These algorithms make random choices during their logic to optimize performance, often for sorting and selection problems. An example is the QuickSort algorithm, where a random element is picked as a pivot.
Recursive Algorithms: These algorithms solve problems by calling themselves with modified parameters.
Examples:
- Factorial Calculation: Computes the factorial of a number (n!) using recursion.
- Fibonacci Sequence: Generates the Fibonacci sequence using recursion.
Machine Learning Algorithms: These are used in AI for data analysis and pattern recognition. Examples include linear regression, decision trees, and neural networks.
Cryptographic Algorithms: Used for securing data and communications. They include algorithms for encryption and decryption, such as RSA, AES, and GOST 28147-89.

Each type of algorithm has its specific use cases and is selected based on the requirements of the problem at hand, such as efficiency, complexity, and the nature of the data being processed.

Example of an algorithm to sum a list of numbers

Let's create a simple Python 3 code that demonstrates key characteristics of an algorithm. We'll design an algorithm that takes a list of numbers as input and returns the sum of these numbers.

This example will showcase input, output, definiteness, finiteness, effectiveness, and generality.

def sum_numbers(numbers):
    """
    Algorithm to sum a list of numbers.

    Input:
    numbers: List of numbers

    Output:
    Sum of the numbers in the list
    """

    # Initialize the sum to 0
    total = 0

    # Iterate over each number in the list
    for number in numbers:
        # Add the number to the total sum
        total += number

    # Return the total sum
    return total

# Example usage of the algorithm
input_numbers = [1, 2, 3, 4, 5]
output = sum_numbers(input_numbers)
print("Sum of numbers:", output)

In this example:

Input: The algorithm takes a list of numbers as input (input_numbers).
Output: It outputs the sum of these numbers (output).
Definiteness: Each step in the sum_numbers function is clear and unambiguous.
Finiteness: The algorithm terminates after summing all the numbers in the list.
Effectiveness: Each operation in the algorithm (initialization, iteration, addition) is basic and can be performed in a finite amount of time.
Generality: The algorithm can be applied to any list of numbers.

This Python code is a simple yet effective illustration of the key characteristics of an algorithm in computer science.

Example of incorrect algorithm

To illustrate a counterexample of something that cannot be treated as an algorithm in the context of computer science, we'll provide a Python code snippet that violates one or more of the key characteristics of an algorithm. Specifically, let's consider a piece of code that does not have finiteness and definiteness.

def uncertain_process(numbers):
    """
    A process that attempts to sum numbers but without clear definiteness and finiteness.

    Input:
    numbers: List of numbers

    Output:
    Uncertain. It may or may not return a sum.
    """

    total = 0
    i = 0

    while True:
        # Attempt to add a number to the total
        try:
            total += numbers[i]
        except IndexError:
            # Continues indefinitely without a clear stopping condition
            continue
        except TypeError:
            # Ambiguity in handling non-numeric types
            print("Non-numeric value encountered.")

        i += 1

    # This return statement is never reached
    return total

# Example usage
input_numbers = [1, 2, 'a', 3]
result = uncertain_process(input_numbers)
print("Result:", result)

In this code:

Finiteness: The while True: loop creates an infinite loop with no clear termination condition. This violates the finiteness characteristic of an algorithm, as it does not guarantee termination after a finite number of steps.
Definiteness: The code is ambiguous in handling errors. For instance, encountering a non-numeric value (like a string 'a') results in a print statement but does not stop or properly handle the iteration. This lack of clear, unambiguous steps violates the definiteness characteristic.

As a result, this code cannot be considered as a valid algorithm in computer science due to its indefinite nature and lack of a guaranteed endpoint.

CS 101: What is an Algorithm and its Key Characteristics

Table of contents