Fiche de révision : Fundamentals of Algorithms and Data Structures

📋 Course Outline

1. Algorithm Definition
2. Algorithm Expression
3. Program Concept
4. Complexity Notion
5. Search Algorithms
6. Sorting Algorithms
7. Data Structures
8. Stacks and Queues
9. Linked Lists
10. Trees and Binary Trees
11. Graph Representations
12. Hashing Techniques

📖 1. Algorithm Definition

🔑 Key Concepts & Definitions

• Algorithm: A finite sequence of elementary operations arranged in a specific order, which specifies a calculation scheme. According to the Encyclopedia Universalis, it is a schema of calculation expressed as a finite set of elementary operations obeying a determined sequence. (Source: Encyclopaedia Universalis)

• Algorithm as Data Transformation: An algorithm functions as a process that transforms input data into output results through a series of well-defined steps. It systematically processes data to achieve a certain goal. (Implied from the general definition)

• Deterministic Algorithm: An algorithm that, given the same input, always produces the same sequence of operations and results. This property ensures consistency and predictability in execution. (Source: Encyclopaedia Universalis)

• Historical Origin of Algorithms: The concept predates modern computers, with early formulations by Euclid (3rd century BC) and the Babylonians (1800 BC, during Hammurabi's era). The term "algorithm" itself derives from Al-Khwarizmi (820 AD), whose work on arithmetic and calculation rules significantly influenced the development of systematic problem-solving methods. (Source: Encyclopaedia Universalis)

• Algorithm as a Data Transformation Process: It is a process that takes data (inputs) and applies a finite set of elementary operations to produce results (outputs). This emphasizes the functional aspect of algorithms in converting data from one form to another. (Implied from the general definition)

📝 Essential Points

• An algorithm is a finite, well-ordered sequence of elementary operations designed to solve a specific problem or perform a task.
• The concept of algorithms originated long before the advent of computers, with roots in ancient mathematics, notably by Euclid and the Babylonians.
• The term "algorithm" is derived from Al-Khwarizmi's name, whose work in the 9th century laid foundational principles for systematic calculation methods.
• Algorithms are characterized by their determinism; the same input always yields the same sequence of operations and results.
• An algorithm can be viewed as a data transformation process, converting inputs into outputs through a series of steps.

💡 Key Takeaway

An algorithm is a finite, deterministic sequence of elementary operations that transforms data into results, with origins tracing back to ancient mathematicians like Euclid and Al-Khwarizmi, forming the basis of systematic problem-solving in computing.

📖 2. Algorithm Expression

🔑 Key Concepts & Definitions

• Algorithm expression is independent of programming language: The conceptual formulation of an algorithm does not rely on any specific programming language, meaning its logic and structure remain consistent regardless of the language used for implementation. This allows for universal understanding and transferability of algorithmic ideas (see section 1-2).

• Algorithm must be expressed in a programming language for execution: To be executed by a computer, an algorithm needs to be translated into a specific programming language. This step involves coding the algorithm's logic into syntax and structures that a machine can interpret and run (see section 1-2).

• Algorithm + data structures = program (Wirth): According to Wirth (1976), a complete program is formed by combining the algorithmic logic with appropriate data structures. The data structures organize and store data efficiently, enabling the algorithm to operate effectively, thus creating a functional program.

📝 Essential Points

• The core idea is that algorithms are conceptual procedures that are language-agnostic; they describe what needs to be done, not how it is done in a specific language.
• To execute an algorithm, it must be translated into a programming language, which provides the syntax and semantics for implementation.
• The combination of an algorithm and suitable data structures results in a program capable of solving a specific problem, emphasizing the importance of both components in software development.
• This distinction underscores the universality of algorithmic thinking and the necessity of language-specific coding for practical execution.

💡 Key Takeaway

Algorithm expression is a language-independent conceptual framework that must be translated into a programming language to be executed, and when combined with data structures, it forms a complete program as per Wirth's principle.

📖 3. Program Concept

🔑 Key Concepts & Definitions

• Program (see source): A program is a logical sequence of instructions executed by a computer to perform a specific task or solve a problem. It guides the hardware through a series of operations to achieve desired results.
• Program (see source): It abstracts hardware by providing a set of instructions that manipulate data, allowing the hardware to process information into meaningful outputs without requiring the user to understand the underlying physical components.
• Programs and Data (see source): Both reside in main memory during execution, meaning they are loaded into the computer's primary storage to be accessible for processing by the processor.
• Processor (see source): The central processing unit (CPU) performs arithmetic and logical operations on data, executing the instructions specified by the program to transform inputs into outputs.

📝 Essential Points

• A program is essentially a sequence of instructions that the computer follows to accomplish a task, emphasizing the importance of logical order and determinism (see source).
• The abstraction provided by a program allows users to operate hardware independent of its physical details, focusing instead on what needs to be done rather than how at the hardware level.
• Both programs and data are stored in main memory during execution, highlighting the importance of memory management for effective processing.
• The processor executes instructions by performing arithmetic (e.g., addition, subtraction) and logical (e.g., AND, OR, NOT) operations, which are fundamental to data transformation within programs.

💡 Key Takeaway

A program is a carefully structured sequence of instructions that abstracts hardware complexity, enabling the processor to manipulate data and produce results efficiently during execution in main memory.

📖 4. Complexity Notion

🔑 Key Concepts & Definitions

• Algorithm complexity (see source): Measures the execution cost of an algorithm, primarily focusing on the time required to complete its operations, which depends on data size and input values. It provides a way to evaluate and compare algorithm efficiency.

• Worst-case, average-case, and best-case complexities (see source): These are scenarios used to analyze an algorithm's performance:

  • Worst-case: maximum time taken for any input of size n.
  • Average-case: expected time over all possible inputs of size n.
  • Best-case: minimum time for the most favorable input of size n.

• Asymptotic complexity and Big O notation (see source): A mathematical framework to describe the growth rate of an algorithm's execution time as input size n approaches infinity. If T(n) ≤ c·f(n) for some constants c and n₀, then T(n) = O(f(n)), indicating T(n) is asymptotically bounded by f(n).

• Rules for calculating complexity of loops, conditionals, sequences (see source):

  • Loop complexity is generally proportional to the number of iterations; nested loops multiply their complexities.
  • Conditionals contribute the maximum complexity of their branches.
  • Sequences sum the complexities of individual steps.

• Examples of complexity classes (see source): Common classes include:

  • O(1): constant time
  • O(log n): logarithmic time
  • O(n): linear time
  • O(n log n): linearithmic time
  • O(n²): quadratic time
  • O(n³): cubic time
  • O(2^n): exponential time

📝 Essential Points

• The execution time (T.e) of an algorithm depends on data size n and input values; larger data generally increases T.e, but the rate of increase varies with the complexity class.
• Worst-case complexity provides an upper bound, ensuring performance limits are understood, especially critical for real-time or large-scale applications.
• Asymptotic analysis, using Big O notation, simplifies comparison by focusing on dominant growth terms, ignoring constant factors and lower-order terms.
• Calculating complexity involves analyzing loops, conditionals, and sequences:
  • Loop complexity: multiply the complexity by the number of iterations.
  • Conditionals: consider the branch with the highest complexity.
  • Sequences: sum the complexities of individual steps.
• Examples illustrate how different algorithms for the same problem can have vastly different complexities, affecting their suitability for large data.

💡 Key Takeaway

Algorithm complexity measures execution cost in terms of time, enabling comparison and optimization. Asymptotic notation like Big O provides a practical way to evaluate algorithm efficiency for large data, guiding the choice of the most suitable algorithm for a given problem.

📖 5. Search Algorithms

🔑 Key Concepts & Definitions

• Sequential search in an unsorted array (see source): A method that scans each element in the array one by one until the target element is found or the end of the array is reached. Its time complexity is O(n), where n is the number of elements, because in the worst case, every element must be checked.

• Sequential search in a sorted array with early stopping (see source): An optimized version of sequential search that stops the search process as soon as it encounters an element greater than the target, leveraging the array's sorted property. This reduces unnecessary comparisons, but in the worst case, still has O(n) complexity.

• Search function returns index or -1 if not found (see source): A common convention where the search operation outputs the position (index) of the target element within the array if it exists, or -1 if the element is absent, indicating unsuccessful search.

• Insertion and deletion operations in arrays (see source): Procedures to add or remove elements from an array. Insertion at the end is typically O(1) if space permits, but insertion or deletion at arbitrary positions requires shifting elements, resulting in O(n) time complexity due to element movement.

📝 Essential Points

• Sequential search in an unsorted array has O(n) worst-case complexity because it may need to examine every element to find the target or conclude absence.

• When the array is sorted, early stopping in sequential search improves efficiency in practice, especially if the target is near the beginning or the array contains larger elements early on, but the worst-case complexity remains O(n).

• In arrays, insertion and deletion are not constant-time operations; inserting or deleting an element at a specific position involves shifting subsequent elements, leading to O(n) time complexity.

• The search function's output—either the index of the found element or -1—provides a straightforward way to verify search success or failure.

💡 Key Takeaway

Sequential search methods are simple and effective for small or unsorted datasets, with linear time complexity, while operations like insertion and deletion in arrays require shifting elements, also resulting in linear time costs. The search function's return value clearly indicates success or failure, facilitating further processing.

📖 6. Sorting Algorithms

🔑 Key Concepts & Definitions

• Sorting problem: The task of arranging elements in a collection based on a key field, such as numerical or alphabetical order. The goal is to produce an ordered sequence that satisfies specific criteria.

• Stable sorting: A sorting method that preserves the initial relative order of elements with equal keys. According to AUTHOR (date), stability ensures that if two elements are equal, their original order remains unchanged after sorting.

• In-place sorting: A sorting technique that uses only the existing memory of the data structure, without requiring additional space proportional to the input size. This approach minimizes memory usage during sorting.

• Elementary O(n^2) sorting algorithms: Basic sorting algorithms with quadratic time complexity, suitable for small datasets. These include bubble sort, selection sort, and insertion sort.

• Bubble sort: An elementary sorting algorithm that repeatedly swaps adjacent elements if they are in the wrong order. This process continues until the entire array is sorted, with the largest elements "bubbling" to the end through repeated passes.

📝 Essential Points

• The sorting problem involves ordering elements based on a key field, which can be numerical, alphabetical, or any comparable attribute. Efficient sorting is crucial for data organization, searching, and retrieval.

• Stable sorting is particularly important when the order of equal elements carries significance, such as in multi-criteria sorting or maintaining original insertion order. AUTHOR (date) emphasizes its importance in preserving data integrity.

• In-place sorting algorithms are preferred when memory resources are limited, as they do not require additional space beyond the input array. This is especially relevant in embedded systems or large datasets.

• Elementary algorithms like bubble sort perform repeated adjacent swaps, which makes them simple but inefficient for large datasets. Despite their quadratic time complexity, they are useful for educational purposes and small data.

• The bubble sort algorithm continues passes over the array, swapping neighboring elements if they are out of order, until no swaps are needed, indicating the array is sorted.

💡 Key Takeaway

Elementary O(n^2) sorting algorithms, such as bubble sort, are simple and easy to implement but are inefficient for large datasets. Stable and in-place sorting are important properties that influence the choice of sorting method depending on the application's requirements.

📖 7. Data Structures

🔑 Key Concepts & Definitions

Key data in records:
A specific field within a record used to uniquely identify or organize data. It serves as the primary attribute for sorting or searching, such as a student ID or product code. (see section 3)

Satellite data:
The remaining fields in a record that are not part of the key. These contain supplementary information associated with the key, like a student's name or age, and are processed alongside the key during data operations.

Data structures as containers:
Abstract or concrete implementations designed to organize, store, and manage data efficiently. They provide mechanisms for data access, insertion, deletion, and organization, serving as the foundation for algorithms and applications. (see section 1-8)

Arrays:
Basic data structures that store elements of the same type in contiguous memory locations. Arrays allow direct access to elements via their index, enabling efficient retrieval and modification. They are fundamental for implementing more complex structures like lists or matrices.

📖 8. Stacks and Queues

🔑 Key Concepts & Definitions

• Stack (pile): An abstract data type following the Last-In-First-Out (LIFO) principle, where the most recently added element is the first to be removed. (No specific author/date provided)

• Queue (file): An abstract data type based on the First-In-First-Out (FIFO) principle, where the earliest added element is the first to be removed. (No specific author/date provided)

• Push/Pop Operations: Operations specific to stacks; push adds an element to the top of the stack, pop removes the top element. (No specific author/date provided)

• Enqueue/Dequeue Operations: Operations specific to queues; enqueue adds an element at the rear, dequeue removes an element from the front. (No specific author/date provided)

• LIFO (Last-In-First-Out): The principle that the last element added to a stack is the first to be removed. (No specific author/date provided)

• FIFO (First-In-First-Out): The principle that the first element added to a queue is the first to be removed. (No specific author/date provided)

📝 Essential Points

• Stacks and queues are fundamental data structures used to manage collections of elements with specific orderings—LIFO for stacks, FIFO for queues.

• Operations push/pop for stacks and enqueue/dequeue for queues are the primary methods to add or remove elements, respecting their respective principles.

• The stack structure is useful in scenarios like function call management, undo mechanisms, and syntax parsing, where the most recent operation needs to be accessed first.

• The queue structure is applicable in scheduling, buffering, and breadth-first search algorithms, where elements are processed in the order they arrive.

• These data types abstract the underlying implementation, allowing flexible usage across different programming contexts.

💡 Key Takeaway

Stacks and queues are essential abstract data types that organize data according to LIFO and FIFO principles, respectively, enabling efficient management of ordered collections in various computational processes.

📖 9. Linked Lists

🔑 Key Concepts & Definitions

• Linked list structure: A linear collection of nodes where each node contains data and a pointer to the next node, forming a chain. (Source: M. E. RIFFI, 2025/2026)

• Node: The fundamental unit of a linked list, comprising two parts: the data (or content) and a pointer (or reference) to the next node in the sequence. (Source: M. E. RIFFI, 2025/2026)

• Insertion in linked lists: The process of adding a new node at a specified position (beginning, end, or middle) by adjusting pointers, without shifting existing elements. (Source: M. E. RIFFI, 2025/2026)

• Deletion in linked lists: Removing a node by re-linking the previous node's pointer to the node following the one to be deleted, effectively excising it from the chain. (Source: M. E. RIFFI, 2025/2026)

• Advantages over arrays for dynamic data: Linked lists allow efficient insertion and deletion at arbitrary positions without shifting elements, and they can grow or shrink in size dynamically, unlike arrays which require contiguous memory and resizing. (Source: M. E. RIFFI, 2025/2026)

📝 Essential Points

• A linked list's structure relies on nodes connected via pointers, enabling flexible memory usage and dynamic resizing. Unlike arrays, linked lists do not require contiguous memory blocks, which makes them suitable for applications where the size of data changes frequently.

• Insertion and deletion operations are efficient in linked lists because they involve only pointer adjustments, especially at the beginning or end of the list, avoiding the costly shifting of elements seen in arrays.

• The main advantage over arrays is the ability to insert or delete elements in constant time (O(1)) at known positions, provided the node's location is known, and the list is singly linked (see source for detailed algorithms).

• Despite their flexibility, linked lists have disadvantages such as higher memory overhead due to storing pointers and slower access times (O(n)) for random element access compared to arrays.

💡 Key Takeaway

Linked lists provide a flexible, dynamic data structure ideal for applications requiring frequent insertions and deletions, offering advantages over arrays in managing variable-sized data efficiently.

📖 10. Trees and Binary Trees

🔑 Key Concepts & Definitions

• Tree (see source): A hierarchical data structure composed of nodes connected by edges, where each node has a parent (except the root) and zero or more children, forming a parent-child relationship. It models a hierarchy with a single entry point called the root.

• Node (see source): The fundamental element of a tree, containing data and references (or links) to its child nodes. Each node may have a parent node (except the root) and multiple children.

• Binary Tree (see source): A specialized tree where each node has at most two children, commonly referred to as the left and right child. This restriction simplifies traversal and operations.

• Traversal Methods (see source): Procedures to visit all nodes in a tree systematically. Common traversal methods include:

  • Pre-order: visit the current node, then recursively traverse the left and right subtrees.
  • In-order: recursively traverse the left subtree, visit the current node, then traverse the right subtree.
  • Post-order: recursively traverse the left and right subtrees, then visit the current node.
  • Level-order: visit nodes level by level from top to bottom.

• Properties of Traversals (see source): Traversal methods allow for various operations such as searching, printing, or modifying nodes. They are fundamental for algorithms like sorting, searching, and tree manipulation.

📝 Essential Points

• A tree is a non-linear data structure with nodes connected via parent-child relationships, forming a hierarchy with a unique root node (see source). It is used to represent structured data such as organizational charts, file systems, and decision processes.

• Each node in a tree contains data and references to its children, enabling recursive traversal and manipulation. The parent-child links define the structure's hierarchy.

• A binary tree restricts each node to having at most two children, which simplifies algorithms for traversal, insertion, and deletion, and is the basis for more complex structures like binary search trees and heaps.

• Traversal methods systematically visit nodes in a specific order:

  • Pre-order: useful for copying trees.
  • In-order: yields nodes in sorted order for binary search trees.
  • Post-order: used for deleting or freeing nodes.
  • Level-order: processes nodes level by level, often implemented with queues.

• Traversal properties are essential for algorithms that require visiting all nodes, such as searching for a value or printing the tree structure.

💡 Key Takeaway

A tree is a hierarchical data structure with parent-child relationships, and binary trees are a simplified form where each node has at most two children. Traversal methods enable systematic access to all nodes, underpinning many algorithms in data management and processing.

📖 11. Graph Representations

🔑 Key Concepts & Definitions

• Adjacency Matrix: A two-dimensional array used to represent a graph where each cell (i, j) indicates the presence or absence of an edge between vertices i and j. For a graph with n vertices, it is an n x n matrix. (Source: RIFFI, 2025/2026)

• Adjacency List: A collection of lists where each list corresponds to a vertex and contains all adjacent vertices connected by edges. It is an efficient way to represent sparse graphs, reducing space complexity compared to adjacency matrices. (Source: RIFFI, 2025/2026)

• Directed Graph: A graph where edges have a direction, going from one vertex to another, represented as ordered pairs (u, v). The adjacency matrix or list reflects the directionality, indicating edges from u to v only. (Source: RIFFI, 2025/2026)

• Undirected Graph: A graph where edges have no direction; connections are bidirectional. In adjacency representations, the matrix or list is symmetric, showing mutual connectivity between vertices. (Source: RIFFI, 2025/2026)

• Graph Traversal (Basics): The process of visiting all vertices and edges in a graph systematically, typically using algorithms like Depth-First Search (DFS) or Breadth-First Search (BFS). Traversal helps in exploring graph structure, connectivity, and pathfinding. (Source: RIFFI, 2025/2026)

📝 Essential Points

• Adjacency matrix provides constant-time edge lookup (O(1)) but uses O(n²) space, making it suitable for dense graphs. It is straightforward to implement but less efficient for sparse graphs. (RIFFI, 2025/2026)

• Adjacency list uses space proportional to the number of edges plus vertices (O(n + e)), making it ideal for sparse graphs. Traversal algorithms like DFS and BFS are more efficient with adjacency lists, especially in large, sparse graphs. (RIFFI, 2025/2026)

• Directed graphs are used to model asymmetric relationships such as web links or one-way streets. Their adjacency representations reflect directionality, affecting traversal and pathfinding algorithms. (RIFFI, 2025/2026)

• Undirected graphs model symmetric relationships like social networks or road maps. Their adjacency matrices are symmetric, simplifying certain algorithms but potentially increasing space usage. (RIFFI, 2025/2026)

• Graph traversal algorithms (DFS and BFS) are fundamental for exploring graphs, detecting connectivity, cycles, and shortest paths. DFS uses a stack or recursion, while BFS uses a queue, systematically visiting vertices. (RIFFI, 2025/2026)

💡 Key Takeaway

Graph representations like adjacency matrices and lists are essential for efficiently modeling different types of graphs, with traversal algorithms enabling systematic exploration of their structure. The choice of representation depends on graph density and application needs.

📖 12. Hashing Techniques

🔑 Key Concepts & Definitions

• Hash function (source): A deterministic function that maps keys from a set U to indices in a table of size m (i.e., h: U → {0, 1, ..., m-1}). It aims to distribute keys uniformly to minimize collisions (source).
• Collision (source): Occurs when two distinct keys produce the same hash value (h(x) = h(y) with x ≠ y). A good hash function should be as injective as possible to reduce collisions.
• Chaining (haching indirect) (source): A collision resolution method where all elements that hash to the same index are stored in a linked list or chain outside the table, allowing multiple elements per slot (source).
• Open addressing (direct chaining) (source): A collision resolution technique where, upon collision, a new position is computed for the element using a secondary function, and the element is stored in an alternative slot within the table (source).
• Double hashing (source): A collision resolution method that employs two hash functions to compute probe sequences, dispersing elements more evenly and avoiding clustering (source).

📝 Essential Points

• The primary goal of hashing is to reduce access time by directly mapping keys to table indices (source).
• The hash function must be deterministic, fast to compute, and produce a uniform distribution to minimize collision probability (source).
• Collisions are inevitable; thus, effective resolution methods are essential. Chaining involves external linked lists, while open addressing searches for alternative slots within the table (source).
• In chaining, the table contains only references to linked lists, making it flexible but potentially less cache-efficient. In open addressing, all data is stored within the table, requiring careful probing strategies (source).
• Double hashing uses a secondary hash function to generate probe sequences, reducing clustering and improving performance in high load factors (source).
• The choice of method depends on application constraints, such as memory availability and expected load factors (source).

💡 Key Takeaway

Hashing techniques efficiently access data by mapping keys to table indices using hash functions, with collision resolution methods like chaining and double hashing ensuring reliable data retrieval even in the presence of collisions.

📊 Synthesis Tables

⚠️ Common Pitfalls & Confusions

1. Confusing algorithm definition with program implementation; algorithms are language-agnostic, programs are language-specific.
2. Mistaking deterministic algorithms for non-deterministic; the same input always yields the same output in deterministic algorithms.
3. Overlooking the importance of data structures in algorithm efficiency; Wirth emphasizes algorithm + data structures = program.
4. Misinterpreting Big O notation as actual runtime; it describes growth rate, not precise execution time.
5. Ignoring the difference between worst-case and average-case complexity; both are critical for performance analysis.
6. Assuming all sorting algorithms have the same complexity; e.g., bubble sort O(n²) vs. quicksort O(n log n).
7. Confusing linked lists with arrays; linked lists are dynamic, pointer-based, and better for insertions/deletions.

✅ Exam Checklist

• Know the definition of an algorithm as a finite, deterministic sequence of elementary operations, referencing Encyclopaedia Universalis, Euclid, and Al-Khwarizmi.
• Understand that algorithm expression is language-independent but must be translated into a programming language for execution, as per Wirth’s principle.
• Be able to describe the program concept as a sequence of instructions that abstracts hardware, stored in main memory, with the CPU executing arithmetic and logical operations.
• Master the notion of complexity, including worst-case, average-case, and best-case scenarios, and how Big O notation characterizes growth rates.
• Know key search algorithms (e.g., binary search) and sorting algorithms (e.g., quicksort, bubblesort), including their efficiency and typical use cases.
• Recall the main data structures: arrays, linked lists, trees, graphs, hash tables, and their properties.
• Understand stacks (LIFO) and queues (FIFO): their operations and applications.
• Be familiar with linked lists: structure, advantages, and typical operations.
• Know trees and binary trees: structure, traversal methods, and their role in efficient searching.
• Recognize graph representations: adjacency matrix and adjacency list, and their advantages.
• Comprehend hashing techniques: hash functions, collision handling methods like chaining and open addressing.
• Know the historical origins of algorithms from Euclid and Al-Khwarizmi.
• Be able to analyze an algorithm’s complexity based on input size and structure.
• Understand the rules for calculating complexity of loops, conditionals, and sequences.
• Be aware of common pitfalls in algorithm and data structure understanding.
• Know the importance of combining algorithms with suitable data structures to form efficient programs.
• Recognize that algorithm efficiency impacts software performance and scalability.