Algorithms

The content here is under the Attribution 4.0 International (CC BY 4.0) license

Algorithms are the foundation of computer science and programming, providing a systematic approach to problem-solving. They are essential for processing data, executing operations, and implementing solutions in software development. The approach I have been exposed to is to compare it with a recipe (Bell, 2024), where the ingredients are the data and the steps are the instructions to manipulate that data. This analogy helps in understanding how algorithms work and their importance in software engineering. However, for it to make sense, it has to be taken literally.

Take, for example, the book Grokking Algorithms. It has a different approach to learning the most popular algorithms that are used out there (Bhargava, 2016). However, things start simple but quickly evolve to other more complex areas such as performance and complexity.

At the university, students are exposed to a variety of those problems and are tested against them from the start. However, not everyone finds the understanding and problem-solving aspect of it straightforward. In this section, the space is dedicated to the study of algorithms, focusing on the implementation and analysis of algorithms from a practical approach, starting with easy problems and gradually moving to more complex ones.

Introduction

Algorithms in computer science are step-by-step procedures or formulas for solving problems. They are essential for tasks such as data processing, calculations, and automated reasoning. Understanding algorithms is crucial for software development, as they provide the foundation for efficient and effective problem-solving. The part that is most challenging is the analysis of algorithms, which involves evaluating their efficiency and performance. This includes understanding time complexity, space complexity, and how algorithms scale with input size.

When transitioning from the recepe analogy to a more practical approach, it is important to understand that algorithms are not just about following steps, but also about making decisions based on the data and the problem at hand. This involves understanding the data structures used, the operations performed, and how they interact with each other.

In the context of this introduction, we will explore various algorithms, their implementations, and their applications in real-world scenarios. We will also delve into the analysis of algorithms, focusing on how to evaluate their performance and efficiency. Note that each algorithm is presented with a specific problem to a specific area of knowledge, for example, sorting algorithms are presented with the problem of sorting data, while graph algorithms are presented with the problem of traversing and analyzing graphs.

Sorting algorithms

These algorithms are used to arrange data in a specific order, such as ascending or descending. They are fundamental in computer science and are used in various applications, from databases to search engines. Sorting algorithms can be categorized into different types, such as comparison-based sorting (e.g., quicksort, mergesort) and non-comparison-based sorting (e.g., counting sort, radix sort). Each type has its own advantages and disadvantages, depending on the data and the specific use case.

The evaluation of sorting algorithms is often done based on their time complexity, which measures how the execution time of the algorithm grows with the size of the input data. Common time complexities for sorting algorithms include O(n log n) for efficient algorithms like mergesort and quicksort, and O(n^2) for less efficient algorithms like bubble sort and insertion sort.

Linear search

Linear search is a simple algorithm that checks each element in a list sequentially until the desired element is found or the end of the list is reached. It is straightforward but inefficient for large datasets, with a time complexity of O(n).

function linearSearch(arr: number[], target: number): number {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) {
            return i;
        }
    }
    return -1;
}

Linear search is the simplest algorithm that does not take into account multiple occurrences of the same element. It is a basic algorithm that can be used to understand the concept of searching in a list. It is used for iterating over elements and coming across different scenarios in APIs and data processing tasks. However, it is not efficient for large datasets, as it has a time complexity of O(n).

Use cases for linear search include:

• Finding an element in an unsorted list.
• Checking for the existence of an element in a dataset.
• Iterating through a list to perform operations on each element.

Bubble Sort

Bubble sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The process is repeated until the list is sorted. It has a time complexity of O(n^2) in the worst case, making it inefficient for large datasets.

Selection Sort

Selection sort is a simple sorting algorithm that divides the input list into two parts: a sorted part and an unsorted part. It repeatedly selects the smallest (or largest) element from the unsorted part and moves it to the end of the sorted part. The time complexity is O(n^2), making it inefficient for large datasets.

Why selection sort is not efficient for large datasets:

• This means that as the size of the dataset increases, the number of comparisons and swaps grows quadratically, leading to significant performance degradation. For large datasets, more efficient algorithms like quicksort or mergesort, which have average time complexities of O(n log n), are preferred.
• Selection sort is not efficient for large datasets because it has a time complexity of O(n^2), which means that the number of comparisons and swaps grows quadratically with the size of the dataset. This leads to significant performance degradation as the dataset size increases.

Insertion Sort

Merge Sort

Quick Sort

Shell Sort

Recursion

Recursion is a programming technique where a function calls itself to solve a problem. It is often used in algorithms that can be broken down into smaller subproblems, such as tree traversals and factorial calculations.

Graph algorithms

These algorithms are used to analyze and traverse graphs, which are data structures consisting of nodes and edges. They are essential for solving problems related to networks, social media, and transportation systems.

Search algorithms

These algorithms are used to find specific data within a dataset. They are crucial for applications such as databases, search engines, and data retrieval systems.

Greedy algorithms

Greedy algorithms make the locally optimal choice at each stage with the hope of finding a global optimum. They are often used in optimization problems, such as finding the shortest path or minimum spanning tree.

Resources

• Analysis of algorithms
• Visualgo
• Toptotal

References

1. Bell, A. (2024). Lecture 1: Introduction to CS and Programming Using Python. https://www.youtube.com/watch?v=xAcTmDO6NTI&list=PLUl4u3cNGP62A-ynp6v6-LGBCzeH3VAQB
2. Bhargava, A. (2016). Grokking Algorithms: An Illustrated Guide for Programmers and Other Curious People. Manning Publications.