Introduction to the course; understand the methodologies and tools used throughout. Get a proper definition of what an algorithm is and the kind of problems algorithms solve.

• Course methodology, tools and grading vehicles — how theory, practice sessions and group work fit together over the 30 sessions.
• Definition of an algorithm — a finite, deterministic, well-defined procedure mapping input to output; correctness vs. efficiency as separate concerns.

Introduction to asymptotic notation as a means to describe the efficiency of an algorithm, capturing the order of growth of both time and space as a function of input size n.

• Asymptotic notation — Big-O (upper bound), Ω (lower bound) and Θ (tight bound); why we drop constants and lower-order terms.
• Order of growth — comparing constant, logarithmic, linear, linearithmic, quadratic and exponential cost as n grows.

Understand how simple linear data structures store data in memory, and how the distribution of that data impacts how items can be rearranged and looked up. Arrays give contiguous, index-addressable storage; linked lists scatter nodes joined by pointers.

• Arrays — contiguous memory enabling O(1) random access by index, but O(n) insertion/deletion from shifting.
• Linked lists — pointer-joined nodes giving O(1) insert/delete at a known position but O(n) access and linear search.

Foundations of sorting a collection of items; implement your first sorting algorithms. Both are simple, in-place, comparison-based sorts that are quadratic in the worst case.

• Insertion Sort — grow a sorted prefix one element at a time; O(n²) worst case but O(n) on nearly-sorted input.
• Bubble Sort — repeatedly swap adjacent out-of-order pairs until no swaps remain; always O(n²) comparisons.

How linked lists can be a good alternative to arrays when memory efficiency matters; when each structure is better suited. Linked lists grow without reallocation but lose locality of reference.

• Linked lists for memory-efficient storage — dynamic growth without pre-sized buffers; singly vs. doubly linked variants.
• Array vs. linked-list trade-offs — random access & cache locality (array) vs. cheap splicing & unbounded growth (list).

Recursion as a tool to enhance the expressiveness of an algorithm; the Divide and Conquer strategy that splits a large problem into independent subproblems, solves them recursively, and combines the results.

• Recursion fundamentals — base case vs. recursive case; the call stack; how a problem refers to a smaller instance of itself.
• Divide and Conquer — divide into subproblems, conquer recursively, combine; cost captured by recurrences solved with the Master Theorem.

Binary search uses Divide and Conquer to efficiently look up elements in a sorted collection by halving the search interval each step; implement it for any collection of data.

• Binary search — compare to the midpoint and discard half the range each step; O(log n) on sorted input.
• Generalizing — the same halving idea applies to any monotonic predicate, not just equality lookup.

Dives deeper into Quicksort — another example of Divide and Conquer, used to sort a collection of linear data by partitioning around a pivot and recursing on each side.

• Quicksort — choose a pivot, partition smaller/larger elements around it, recurse; in-place with small constants.
• Pivots — average O(n log n), but a poor pivot degrades to O(n²); randomisation mitigates this.

Merge Sort as a good alternative to Quicksort for Divide-and-Conquer sorting; recursively split the list in half, sort each half, and merge the two sorted halves. Understand the differences and when to use each.

• Merge Sort — guaranteed O(n log n) and stable, but needs O(n) auxiliary space.
• Merge Sort vs. Quicksort — merge sort for stability/guaranteed bounds & linked lists; quicksort for in-place speed on arrays.

Linear structures built on top of arrays and linked lists that impose ordering restrictions, useful when insertion order affects extraction order. They expose a deliberately narrow interface so the discipline is guaranteed.

• Stack (LIFO) — last-in, first-out; push/pop/peek in O(1). Drives recursion, undo, and expression evaluation.
• Queue (FIFO) — first-in, first-out; enqueue/dequeue in O(1). Drives scheduling and breadth-first traversal.

Arrays with more than one dimension; how they are stored in memory (typically row-major, flattened into one contiguous block) and the efficiency of typical read/update operations.

• Memory layout — multidimensional indices mapped to one linear offset; row-major vs. column-major and its effect on cache behaviour.
• Read/update efficiency — element access stays O(1); iteration order matters for performance. Use cases: matrices, grids, images, game boards.

Entering non-linear data structures: hashtables enable fast item retrieval based on hash functions, which map a key to a bucket index so insert, lookup and delete avoid scanning the whole collection.

• Hash functions — deterministic maps from keys to indices that should spread keys uniformly across buckets.
• Collisions — distinct keys landing in the same bucket, resolved by chaining (lists per bucket) or open addressing (probing); load factor governs performance.

Trees as graph-like structures (a connected, acyclic graph with a root): how a tree is arranged and how an algorithm visits all its nodes recursively.

• Tree anatomy — root, parent/child, leaves, subtrees, depth and height; the recursive definition of a tree.
• Traversal — visiting every node exactly once in O(n); pre-/in-/post-order variants of depth-first walking.

Breadth First and Depth First, the most common traversal techniques; implement both and know when to use each. BFS explores level by level; DFS dives down one branch before backtracking.

• Breadth First Search (BFS) — level-order using a queue; finds the shallowest/closest node first.
• Depth First Search (DFS) — explore deep first using a stack or recursion; natural for full enumeration and detecting structure.

A deeper look at a commonly used tree: the Binary Search Tree, which keeps elements ordered so search mirrors binary search.

• BST ordering invariant — every key in the left subtree < node < every key in the right subtree.
• Operations — search, insert and delete in O(h) where h is height: O(log n) if balanced, O(n) if degenerate.

Tree-like structures where items are arranged by priority or weight; a (binary) heap keeps the highest- or lowest-priority element at the root for instant access. How they work and when to use them.

• Heap property — every parent dominates its children (max-heap or min-heap); stored compactly in an array.
• Priority queue — insert and extract-min/max in O(log n), peek in O(1); the engine behind Dijkstra and scheduling.

Graphs hold many (possibly directional and/or weighted) relations among elements. What a graph is, what problems it suits, how to represent and traverse it, and how to find the shortest path between two nodes.

• Graph definitions — vertices and edges; directed vs. undirected, weighted vs. unweighted; adjacency list (sparse) vs. matrix (dense).
• Traversal & shortest path — BFS gives the fewest-edges path on unweighted graphs.
• Dijkstra's algorithm — greedy single-source shortest path on non-negative weights using a priority queue.

Dijkstra's limitations (it fails with negative-weight edges) and how algorithms like Bellman-Ford come to the rescue by relaxing every edge repeatedly. Plus two DFS-based tools for directed graphs.

• Bellman-Ford — relax all edges V−1 times; handles negative weights and detects negative cycles.
• Cycle detection — using Depth First search and node colouring / recursion-stack tracking.
• Topological sort — a linear ordering of a DAG so every edge points forward; the basis of dependency resolution and scheduling.

Tackling the "impossible" — problems with no known fast (polynomial) solution, the NP-complete class. Greedy algorithms make the locally optimal choice at each step; for hard problems, approximation algorithms trade exactness for speed.

• Greedy strategy — commit to the best immediate choice; optimal only when the problem has the greedy-choice property and optimal substructure.
• NP-complete problems — no known polynomial algorithm; verifying a solution is easy but finding one seems exponential.
• Approximation algorithms — fast methods that return a provably near-optimal answer.

Solving complex problems by breaking them into simpler subproblems, solving each once, and storing the results for reuse — turning exponential recomputation into polynomial work.

• Overlapping subproblems — the same subproblems recur, so caching (memoization) avoids recomputation.
• Optimal substructure — an optimal solution is composed of optimal solutions to its subproblems.
• Top-down vs. bottom-up — recursion with a memo table vs. iterative tabulation; e.g. Fibonacci O(2ⁿ) → O(n), 0/1 knapsack in O(nW).