Data Structures and Algorithms Course

Lesson 1 • Hash Tables and Hashing Basics

Introduces key-value storage via hash functions and bucket arrays. Prepares learners for collision handling and average-case BI performance analysis.

Lesson 2 • Arrays and Dynamic Arrays

Introduces contiguous memory storage and index-based access. Connects static arrays to dynamic resizing strategies used in real implementations.

Lesson 3 • Linked Lists and Pointer Chains

Teaches node-based storage using pointers or references. Contrasts linked lists with arrays to clarify trade-offs in insertion and traversal.

Lesson 4 • Memory, Variables, and Data Types

Covers how data is stored in memory and how primitive types differ. Establishes the mental model needed for all subsequent structure analysis.

Lesson 1 • Empirical Benchmarking Techniques

Bridges theoretical analysis with measured runtime experiments. Learners design controlled benchmarks to validate or challenge theoretical predictions.

Lesson 2 • Space Complexity and Trade-offs

Analyses auxiliary space usage alongside time costs. Highlights classic time-space trade-offs that guide practical algorithm selection.

Lesson 3 • Recurrence Relations

Introduces recurrences as a tool for analysing recursive algorithms. Covers the Master Theorem and substitution methods for solving them.

Lesson 4 • Big-O, Big-Theta, and Big-Omega

Defines asymptotic notations and their mathematical meaning. Provides the vocabulary used throughout the course for comparing algorithm BI performance.

Lesson 1 • Elementary Comparison Sorts

Covers bubble, selection, and insertion sort with full complexity analysis. Establishes baseline intuition before introducing more efficient approaches.

Lesson 2 • Divide-and-Conquer Sorts

Teaches merge sort and quicksort using recursive decomposition. Connects recurrence analysis from Chapter 2 to real sorting BI performance.

Lesson 3 • Sorting Algorithm Selection

Synthesises all sorting knowledge into a decision framework. Learners match algorithm choice to input size, data distribution, and memory constraints.

Lesson 4 • Linear-Time Sorting Algorithms

Presents counting sort, radix sort, and bucket sort as non-comparison methods. Clarifies the conditions under which linear time is achievable.

Lesson 1 • Memoisation and Top-Down DP

Extends recursion with result caching to eliminate redundant computation. Serves as a bridge to the full dynamic programming chapter that follows.

Lesson 2 • Linear and Binary Search

Contrasts sequential and divide-based search on sorted and unsorted data. Establishes the preconditions and complexity guarantees of each approach.

Lesson 3 • Divide and Conquer Strategy

Formalises the divide-conquer-combine paradigm beyond sorting. Learners apply it to problems like maximum subarray and closest pair of points.

Lesson 4 • Backtracking Techniques

Introduces systematic search with pruning via backtracking. Connects recursive call trees to constraint satisfaction and combinatorial problems.

Lesson 1 • Binary Tree Fundamentals

Defines tree terminology, node relationships, and structural properties. Grounds all subsequent tree algorithms in a shared vocabulary and mental model.

Lesson 2 • Red-Black Trees and B-Trees

Covers red-black colouring rules and multi-way B-tree structure. Connects these to database indexing and file system use cases.

Lesson 3 • AVL Trees and Rotations

Introduces height-balanced AVL trees and the four rotation cases. Learners implement self-balancing to guarantee O(log n) operations.

Lesson 4 • Tree Traversal Algorithms

Covers inorder, preorder, postorder, and level-order traversals. Connects traversal choice to specific output requirements and downstream algorithms.

Lesson 1 • Depth-First Search

Implements DFS recursively and iteratively with discovery and finish times. Connects DFS to cycle detection, topological sort, and connected components.

Lesson 2 • Topological Sorting

Derives topological order from DFS finish times and Kahn's algorithm. Applies ordering to dependency resolution and task scheduling problems.

Lesson 3 • Graph Terminology and Representations

Defines vertices, edges, directed vs. undirected, and weighted graphs. Compares adjacency matrix and adjacency list representations by space and access cost.

Lesson 4 • Breadth-First Search

Implements BFS using a queue and analyses its O(V+E) complexity. Applies BFS to shortest-path finding in unweighted graphs.

Lesson 1 • Minimum Spanning Trees: Kruskal

Builds MSTs by greedily adding minimum-weight edges using Union-Find. Analyses correctness via the cut property and cycle property of MSTs.

Lesson 2 • Dijkstra's Shortest Path Algorithm

Implements Dijkstra using a min-heap priority queue with O((V+E) log V) complexity. Covers correctness proof via the greedy relaxation invariant.

Lesson 3 • All-Pairs Shortest Paths

Solves shortest paths between every vertex pair using Floyd-Warshall. Analyses the O(V³) dynamic programming formulation and path reconstruction.

Lesson 4 • Minimum Spanning Trees: Prim

Grows an MST from a seed vertex using a priority queue in Prim's algorithm. Contrasts Prim with Kruskal by graph density and implementation complexity.

Lesson 1 • Classic 1D DP Problems

Solves Fibonacci, climbing stairs, and coin change using 1D DP tables. Builds table-filling intuition before advancing to 2D formulations.

Lesson 2 • DP on Trees and Graphs

Applies DP to tree structures and DAGs for advanced optimisation problems. Covers tree DP for diameter, independent sets, and DP on DAG paths.

Lesson 3 • Knapsack and Subset Problems

Solves 0/1 knapsack, unbounded knapsack, and subset sum with DP tables. Connects these to resource allocation and feasibility decision problems.

Lesson 4 • Classic 2D DP Problems

Extends DP to two-dimensional tables for string and grid problems. Covers edit distance, LCS, and grid path counting with full recurrence derivations.

Lesson 5 • Space Optimisation in DP

Reduces DP table space from O(n²) to O(n) or O(1) using rolling arrays. Applies space optimisation to knapsack, LCS, and edit distance.