Assessment and Capstone Projects

Before publishing a lesson, verify that it includes:

Lesson quality checklist

Before publishing a lesson, verify that it includes:

[x] Beginner-friendly explanation without assuming hidden prerequisites.

[x] Accurate definition and terminology.

[x] Syntax and a complete compiling example where applicable.

[x] Dry run with a table or visual state changes.

[x] Time complexity and auxiliary space analysis.

[x] Correctness explanation or proof sketch.

[x] Edge cases and boundary conditions.

[x] At least one common incorrect approach and why it fails.

[x] Easy, medium, and advanced exercises.

[x] One tricky interview-style problem with a full solution.

[x] Language-specific caveats where relevant.

[x] Links to prerequisites and follow-up topics.

[x] Accessible diagrams, responsive code blocks, and usable keyboard controls.

In this course every C++ program is complete and was compiled with warnings as errors and with AddressSanitizer and UndefinedBehaviorSanitizer, and every fast algorithm that has an obvious slow counterpart is checked against it on random inputs inside the program itself.

Assessment types

Concept check (multiple choice).

Trace-the-code dry run.

Predict time/space complexity.

Implement from specification.

Optimize a brute-force solution.

Compare two approaches.

Design data structure for a use case.

Timed mixed-topic challenge.

Every module's quiz is a concept check; Module 60's shrinking stress test is a “find the bug” exercise; the problem bank in Module 63 is “implement from specification”.

Capstone projects

Contact manager using hash maps and sorting.

Browser history / undo-redo using stacks.

LRU cache using a hash map and doubly linked list.

Autocomplete using a trie.

Route planner using graph algorithms.

Task scheduler using priority queues.

Range analytics dashboard using Fenwick/segment trees.

Text search tool using KMP or Aho–Corasick.

Social-network connection analysis using graph traversal and DSU.

Mini search index using inverted indexes and ranking.

Event simulation using queues and heaps.

Reference capstone: LRU cache An LRU (least recently used) cache holds at most capacity keys; get and put must be O(1), and inserting into a full cache evicts the key used longest ago. A hash map finds a key's node; a doubly linked list keeps keys in recency order so the oldest is at the tail.

Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):

list::splice moves a node without copying or invalidating iterators, which is why the map can store list iterators safely.

#include <bits/stdc++.h>
using namespace std;

class LRUCache {
    size_t capacity;
    list<pair<int, int>> order;                                   // most recent at the front
    unordered_map<int, list<pair<int, int>>::iterator> where;     // key -> node in the list
public:
    explicit LRUCache(size_t cap) : capacity(cap) {}
    optional<int> get(int key) {
        auto it = where.find(key);
        if (it == where.end()) return nullopt;
        order.splice(order.begin(), order, it->second);           // move to front in O(1); iterators stay valid
        return it->second->second;
    }
    void put(int key, int value) {
        if (auto it = where.find(key); it != where.end()) { it->second->second = value; order.splice(order.begin(), order, it->second); return; }
        if (order.size() == capacity) { where.erase(order.back().first); order.pop_back(); }   // evict least recent
        order.push_front({key, value}); where[key] = order.begin();
    }
};

// slow reference: a vector in recency order
struct SlowLRU {
    size_t cap; vector<pair<int, int>> v;
    optional<int> get(int k) { for (size_t i = 0; i < v.size(); ++i) if (v[i].first == k) { auto p = v[i]; v.erase(v.b
…

get(1) = 10
get(2) after inserting 3: miss (evicted)
get(3) = 30, get(1) = 10
LRU cache matches a simple reference on 200 random sequences of 500 operations

Final assessment

? An algorithm runs in O(n log n) and another in O(n²). For n = 10, which is faster?
+ It depends on constants — asymptotic notation says nothing definitive about small n :: Measure; hybrids switch algorithms for small inputs.
- Always the O(n log n) one :: Not for small n.
- Always the O(n²) one :: Not necessarily.
- They are equal :: No.

? You need the k-th smallest of a range, with array updates between queries. Which structure?
+ A segment tree over values (or a persistent/merge-sort tree for static data) with logarithmic queries :: Choose by update model.
- A sparse table :: Static and min-only.
- A hash map :: No order.
- A stack :: No.

? Dijkstra gives a wrong answer. Which cause is most likely?
+ A negative edge weight :: Module 31's counterexample.
- The graph is directed :: Dijkstra handles directed graphs.
- The graph is sparse :: Irrelevant.
- The source has degree 1 :: Irrelevant.

? Which choices guarantee O(log n) search, insert and delete in an ordered set? (select all that apply)
+ AVL tree :: Height < 1.44 log n.
+ Red-black tree :: Height ≤ 2 log n.
- Plain BST :: Can degrade to O(n).
+ B-tree :: O(log_B n).

? What makes a greedy algorithm trustworthy?
+ A pro
…