Practice

C++ exercises

Make a change, predict what it will do, and compare the result.

1
C++ Basics
Write and run a first program.
Adapt the lesson example. Change one value or element, predict the result, and explain why it changes.
Review lesson →Open compiler
Show starting example
C++
```
#include <iostream>
using namespace std;

int main() {
  cout << "Hello Programonic\n";
}
```
2
C++ conditions and range loops
Filter a sequence while accumulating a result.
Change the test to value >= 0. Does this total change?
Reveal answer and reasoning
No, adding zero does not change a sum. A count of matching values would change.
Review lesson →Open compiler
Show starting example
C++
```
#include <iostream>
#include <vector>
#include <cassert>
int main() {
    std::vector<int> values{-2, 0, 3, 5};
    int total = 0;
    for (int value : values) {
        if (value > 0) total += value;
    }
    std::cout << total << '\n';
    assert(total == 8);
}
```
3
C++ functions and references
Use a reference parameter to update a caller's value.
Change the parameter to int score instead of int& score.
Reveal answer and reasoning
The caller would remain 80 because only a local copy changes; the existing assertion would fail.
Review lesson →Open compiler
Show starting example
C++
```
#include <iostream>
#include <cassert>
void add_bonus(int& score, int bonus) {
    score += bonus;
}
int main() {
    int score = 80;
    add_bonus(score, 5);
    std::cout << score << '\n';
    assert(score == 85);
}
```

C++ recursive factorial

Trace recursive calls and their return values.

Evaluate factorial(5) and factorial(0).

Reveal answer and reasoning

They return 120 and 1.

Review lesson →Open compiler

Show starting example

C++

#include <iostream>
#include <stdexcept>
#include <cassert>
unsigned long factorial(int n) {
    if (n < 0 || n > 12) throw std::out_of_range("use 0 through 12");
    if (n == 0) return 1;
    return static_cast<unsigned long>(n) * factorial(n - 1);
}
int main() {
    std::cout << factorial(4) << '\n';
    assert(factorial(0) == 1);
}

C++ strings and string streams

Use std::string, parse text with getline and istringstream, and convert between text and numbers.

What does text.substr(8) return?

Reveal answer and reasoning

The rest of the string from index 8: "nic is fun".

Review lesson →Open compiler

Show starting example

C++

#include <iostream>
#include <sstream>
#include <string>

int main() {
  std::string text = "Programonic is fun";
  std::cout << text.size() << " " << text.substr(0, 7) << " " << text.find("is") << "\n";

  std::istringstream input("alpha 3\nbeta 5\ngamma x\n");
  std::string line;
  int total = 0;
  while (std::getline(input, line)) {
    std::istringstream fields(line);
    std::string name;
    int value;
    if (fields >> name >> value) {
      std::cout << name << "=" << value << "\n";
      total += value;
    } else {
      std::cout << "bad line: " << line << "\n";
    }
  }
  std::cout << "total " << total << "\n";
  std::cout << std::to_string(42) + "!" << " " << std::stoi("123") + 1 << "\n";
}

C++ references, const, and auto

Pass large objects without copying, protect them with const, and let the compiler deduce types.

What happens if sum takes the vector by value instead?

Reveal answer and reasoning

It still works, but each call copies the whole vector first, which costs O(n) time and memory.

Review lesson →Open compiler

Show starting example

C++

#include <algorithm>
#include <iostream>
#include <vector>

void add_bonus(std::vector<int>& scores, int bonus) {
  for (int& s : scores) {
    s += bonus;
  }
}

int sum(const std::vector<int>& scores) {
  int total = 0;
  for (int s : scores) {
    total += s;
  }
  return total;
}

int main() {
  std::vector<int> scores = {82, 91, 76};
  add_bonus(scores, 5);
  std::cout << scores[0] << " " << scores[1] << " " << scores[2] << "\n";
  std::cout << sum(scores) << "\n";

  auto [low, high] = std::minmax_element(scores.begin(), scores.end());
  std::cout << *low << " " << *high << "\n";

  auto copy = scores;
  copy[0] = 0;
  std::cout << scores[0] << " " << copy[0] << "\n";

  auto& alias = scores;
  alias[0] = 100;
  std::cout << scores[0] << "\n";
}

C++ lambdas and the standard algorithms

Sort, search, count, transform, and remove elements with algorithms and small anonymous functions.

How would you sort strings by length?

Reveal answer and reasoning

std::sort(words.begin(), words.end(), [](const std::string& a, const std::string& b) { return a.size() < b.size(); });

Review lesson →Open compiler

Show starting example

C++

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

void show(const char* label, const std::vector<int>& v) {
  std::cout << label << ":";
  for (int x : v) {
    std::cout << " " << x;
  }
  std::cout << "\n";
}

int main() {
  std::vector<int> v = {5, 2, 8, 1, 9, 3};

  std::sort(v.begin(), v.end(), [](int a, int b) { return a > b; });
  show("descending", v);

  auto it = std::find_if(v.begin(), v.end(), [](int x) { return x < 4; });
  std::cout << "first below 4: " << *it << "\n";

  int threshold = 4;
  auto above = std::count_if(v.begin(), v.end(), [threshold](int x) { return x > threshold; });
  std::cout << "above " << threshold << ": " << above << "\n";

  std::vector<int> squares(v.size());
  std::transform(v.begin(), v.end(), squares.begin(), [](int x) { return x * x; });
  std::cout << "sum of squares: " << std::accumulate(squares.begin(), squares.end(), 0) << "\n";

  v.erase(std::remove_if(v.begin(), v.end(), [](int x) { return x % 2 != 0; }), v.end());
  show("evens only", v);
}

8
C++ Classes
Group data and behavior.
Adapt the lesson example. Change one value or element, predict the result, and explain why it changes.
Review lesson →Open compiler
Show starting example
C++
```
#include <iostream>
class Counter { public: int value = 0; void increment() { value++; } };
int main() { Counter c; c.increment(); std::cout << c.value; }
```

C++ constructors and encapsulation

Initialize private state and expose a controlled interface.

Create another Counter(10) and increment only the first.

Reveal answer and reasoning

The objects remain independent; the second still reports 10.

Review lesson →Open compiler

Show starting example

C++

#include <iostream>
#include <stdexcept>
class Counter {
    int value_;
public:
    explicit Counter(int start) : value_(start) {
        if (start < 0) throw std::invalid_argument("negative start");
    }
    void increment() { ++value_; }
    int value() const { return value_; }
};
int main() {
    Counter counter(2);
    counter.increment();
    std::cout << counter.value() << '\n';
}

C++ abstract classes and virtual dispatch

Invoke derived behavior through a base reference.

Implement a Square derived from Shape.

Reveal answer and reasoning

Store one side and override area to return side * side. A side of 5 gives 25 through a Shape reference.

Review lesson →Open compiler

Show starting example

C++

#include <iostream>
class Shape {
public:
    virtual int area() const = 0;
    virtual ~Shape() = default;
};
class Rectangle : public Shape {
    int width_, height_;
public:
    Rectangle(int w, int h) : width_(w), height_(h) {}
    int area() const override { return width_ * height_; }
};
int main() {
    Rectangle rectangle(3, 4);
    const Shape& shape = rectangle;
    std::cout << shape.area() << '\n';
}

C++ composition and RAII

Let owned members manage their resources automatically.

Create an empty GradeBook and call total.

Reveal answer and reasoning

It returns 0 because the loop has no iterations.

Review lesson →Open compiler

Show starting example

C++

#include <iostream>
#include <vector>
class GradeBook {
    std::vector<int> scores_;
public:
    void add(int score) { scores_.push_back(score); }
    int total() const {
        int sum = 0;
        for (int score : scores_) sum += score;
        return sum;
    }
};
int main() {
    GradeBook book;
    book.add(80);
    book.add(90);
    std::cout << book.total() << '\n';
}

12
C++ function templates
Reuse one type-checked algorithm for different types.
Predict maximum(4, 4).
Reveal answer and reasoning
It returns 4; the comparison is false and the right value is selected.
Review lesson →Open compiler
Show starting example
C++
```
#include <iostream>
template <typename T>
T maximum(T left, T right) {
    return left > right ? left : right;
}
int main() {
    std::cout << maximum(3, 7) << '\n';
    std::cout << maximum(2.5, 1.5) << '\n';
}
```

C++ inheritance and virtual functions

Call the right method through a base-class pointer, and see what slicing does.

What does the vector print if sound is not declared virtual?

Reveal answer and reasoning

Rex says ..., Tom says ..., and Generic says ..., because a call through the base class would always use Animal::sound.

Review lesson →Open compiler

Show starting example

C++

#include <iostream>
#include <memory>
#include <string>
#include <vector>

class Animal {
 public:
  explicit Animal(std::string name) : name_(std::move(name)) {}
  virtual ~Animal() = default;
  virtual std::string sound() const { return "..."; }
  std::string speak() const { return name_ + " says " + sound(); }

 private:
  std::string name_;
};

class Dog : public Animal {
 public:
  using Animal::Animal;
  std::string sound() const override { return "Woof"; }
};

class Cat : public Animal {
 public:
  using Animal::Animal;
  std::string sound() const override { return "Meow"; }
};

int main() {
  std::vector<std::unique_ptr<Animal>> animals;
  animals.push_back(std::make_unique<Dog>("Rex"));
  animals.push_back(std::make_unique<Cat>("Tom"));
  animals.push_back(std::make_unique<Animal>("Generic"));

  for (const auto& animal : animals) {
    std::cout << animal->speak() << "\n";
  }

  Animal sliced = *animals[0];
  std::cout << "sliced copy: " << sliced.speak() << "\n";
}

C++ operator overloading

Give a Vec2 class natural arithmetic, comparison, and output operators.

How do you support 3 * a?

Reveal answer and reasoning

Add a free function Vec2 operator*(int k, const Vec2& v) { return v * k; }.

Review lesson →Open compiler

Show starting example

C++

#include <iostream>

struct Vec2 {
  int x;
  int y;

  Vec2 operator+(const Vec2& other) const { return {x + other.x, y + other.y}; }
  Vec2 operator-(const Vec2& other) const { return {x - other.x, y - other.y}; }
  Vec2 operator*(int k) const { return {x * k, y * k}; }
  bool operator==(const Vec2& other) const { return x == other.x && y == other.y; }
};

std::ostream& operator<<(std::ostream& out, const Vec2& v) {
  return out << "(" << v.x << ", " << v.y << ")";
}

int main() {
  Vec2 a{1, 2};
  Vec2 b{3, 4};
  std::cout << a + b << "\n";
  std::cout << b - a << "\n";
  std::cout << a * 3 << "\n";
  std::cout << (a + b == Vec2{4, 6}) << " " << (a == b) << "\n";
}

C++ smart pointers and ownership

Use unique_ptr for single ownership, shared_ptr for shared ownership, and weak_ptr to observe.

What would happen if you tried to copy a unique_ptr?

Reveal answer and reasoning

The program would not compile, because unique_ptr's copy constructor is deleted. You must use std::move.

Review lesson →Open compiler

Show starting example

C++

#include <iostream>
#include <memory>
#include <string>

struct Resource {
  std::string name;
  explicit Resource(std::string n) : name(std::move(n)) { std::cout << "create " << name << "\n"; }
  ~Resource() { std::cout << "destroy " << name << "\n"; }
};

int main() {
  auto a = std::make_unique<Resource>("A");
  auto b = std::move(a);
  std::cout << "a is null: " << (a == nullptr) << "\n";

  {
    auto shared = std::make_shared<Resource>("S");
    auto second = shared;
    std::cout << "owners: " << shared.use_count() << "\n";
  }

  std::weak_ptr<Resource> weak;
  {
    auto temp = std::make_shared<Resource>("T");
    weak = temp;
    std::cout << "alive inside: " << !weak.expired() << "\n";
  }
  std::cout << "alive after: " << !weak.expired() << "\n";
  std::cout << "end of main\n";
}

16
C++ vectors and iterator invalidation
Grow a dynamic array and use checked access.
What does values.at(3) do after these operations?
Reveal answer and reasoning
It throws std::out_of_range because valid indices are 0, 1, and 2.
Review lesson →Open compiler
Show starting example
C++
```
#include <iostream>
#include <vector>
#include <cassert>
int main() {
    std::vector<int> values{2, 4};
    values.push_back(6);
    values.at(1) = 5;
    for (int value : values) std::cout << value << '\n';
    assert(values.size() == 3);
}
```

C++ binary search with lower_bound

Find an insertion position and check whether it is a match.

Predict lower_bound for 9.

Reveal answer and reasoning

It returns end(), corresponding to insertion index 4. Do not dereference it.

Review lesson →Open compiler

Show starting example

C++

#include <algorithm>
#include <iostream>
#include <vector>
#include <cassert>
int main() {
    std::vector<int> values{2, 4, 4, 8};
    auto found = std::lower_bound(values.begin(), values.end(), 4);
    if (found != values.end() && *found == 4) {
        std::cout << (found - values.begin()) << '\n';
    }
    auto missing = std::lower_bound(values.begin(), values.end(), 5);
    std::cout << (missing - values.begin()) << '\n';
    assert(missing != values.end() && *missing == 8);
}

C++ stack and queue adapters

Compare LIFO and FIFO removal on the same values.

Remove one more item from each and predict the next pair.

Reveal answer and reasoning

The stack top is 1 and the queue front is 3.

Review lesson →Open compiler

Show starting example

C++

#include <iostream>
#include <stack>
#include <queue>
int main() {
    std::stack<int> stack;
    std::queue<int> queue;
    for (int value : {1, 2, 3}) { stack.push(value); queue.push(value); }
    std::cout << stack.top() << ' ' << queue.front() << '\n';
    stack.pop();
    queue.pop();
    std::cout << stack.top() << ' ' << queue.front() << '\n';
}

C++ ordered maps and frequencies

Count keys and traverse them in sorted order.

Add green once to the input.

Reveal answer and reasoning

Output becomes blue 1, green 1, red 2 in key order.

Review lesson →Open compiler

Show starting example

C++

#include <iostream>
#include <map>
#include <string>
#include <cassert>
int main() {
    std::map<std::string, int> counts;
    for (const std::string word : {"red", "blue", "red"}) ++counts[word];
    for (const auto& entry : counts) {
        std::cout << entry.first << ' ' << entry.second << '\n';
    }
    assert(counts.find("green") == counts.end());
}

C++ linked lists with unique ownership

Build a node chain with automatic destruction.

What does first hold after head = std::move(first)?

Reveal answer and reasoning

It is empty. The chain is owned by head, so do not dereference first.

Review lesson →Open compiler

Show starting example

C++

#include <iostream>
#include <memory>
#include <utility>
struct Node {
    int value;
    std::unique_ptr<Node> next;
    explicit Node(int v) : value(v) {}
};
int main() {
    auto head = std::make_unique<Node>(2);
    head->next = std::make_unique<Node>(3);
    auto first = std::make_unique<Node>(1);
    first->next = std::move(head);
    head = std::move(first);
    for (const Node* current = head.get(); current; current = current->next.get()) {
        std::cout << current->value << '\n';
    }
}

C++ sorting: insertion sort, merge sort, and std::stable_sort

Write two sorts by hand and sort records with a comparator, keeping equal items in order.

Which of std::sort and std::stable_sort would you choose to sort by two keys in two passes?

Reveal answer and reasoning

std::stable_sort, because the second pass must not undo the order created by the first.

Review lesson →Open compiler

Show starting example

C++

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

void insertion_sort(std::vector<int>& a) {
  for (std::size_t i = 1; i < a.size(); ++i) {
    int key = a[i];
    std::size_t j = i;
    while (j > 0 && a[j - 1] > key) {
      a[j] = a[j - 1];
      --j;
    }
    a[j] = key;
  }
}

std::vector<int> merge_sort(const std::vector<int>& a) {
  if (a.size() <= 1) {
    return a;
  }
  std::size_t mid = a.size() / 2;
  std::vector<int> left = merge_sort(std::vector<int>(a.begin(), a.begin() + mid));
  std::vector<int> right = merge_sort(std::vector<int>(a.begin() + mid, a.end()));
  std::vector<int> merged;
  std::size_t i = 0, j = 0;
  while (i < left.size() && j < right.size()) {
    merged.push_back(left[i] <= right[j] ? left[i++] : right[j++]);
  }
  while (i < left.size()) merged.push_back(left[i++]);
  while (j < right.size()) merged.push_back(right[j++]);
  return merged;
}

struct Student {
  std::string name;
  int grade;
};

int main() {
  std::vector<int> data = {5, 2, 9, 1, 5, 6};
  std::vector<int> copy = data;
  insertion_sort(copy);
  for (int x : copy) std::cout << x << " ";
  std::cout << "\n";
  for (int x : merge_sort(data)) std::cout << x << " ";
  std::cout << "\n";

  std::vector<Student> students = {{"Ada", 90}, {"Bo", 85}, {"Cy", 90}, {"Di", 85}};
  std::stable_sort(students.begin(), students.end(),
                   [](const Student& a, const Student& b) { return a.grade > b.grade; });
  for (const Student& s : students) std::cout << s.name << ":" << s.grade << " ";
  std::cout << "\n";
}

C++ singly linked list with unique_ptr

Own each node with a unique_ptr, push at the front, reverse the list, and let destructors do the cleanup.

Why does print use raw pointers?

Reveal answer and reasoning

It only reads the list and does not take ownership, so non-owning raw pointers (from get()) are the right tool.

Review lesson →Open compiler

Show starting example

C++

#include <iostream>
#include <memory>
#include <utility>

struct Node {
  int value;
  std::unique_ptr<Node> next;
  Node(int v, std::unique_ptr<Node> n) : value(v), next(std::move(n)) {}
};

class List {
 public:
  void push_front(int value) { head_ = std::make_unique<Node>(value, std::move(head_)); }

  void reverse() {
    std::unique_ptr<Node> previous;
    while (head_) {
      std::unique_ptr<Node> next = std::move(head_->next);
      head_->next = std::move(previous);
      previous = std::move(head_);
      head_ = std::move(next);
    }
    head_ = std::move(previous);
  }

  void print() const {
    for (const Node* n = head_.get(); n != nullptr; n = n->next.get()) {
      std::cout << n->value << (n->next ? " -> " : "\n");
    }
  }

 private:
  std::unique_ptr<Node> head_;
};

int main() {
  List list;
  for (int v = 4; v >= 1; --v) {
    list.push_front(v);
  }
  list.print();
  list.reverse();
  list.print();
}

C++ binary search tree traversals

Insert values into a BST and visit them depth-first and level by level.

How would you print the tree height with level order?

Reveal answer and reasoning

Process the queue one level at a time (using the queue size at the start of each level) and count the number of levels.

Review lesson →Open compiler

Show starting example

C++

#include <iostream>
#include <memory>
#include <queue>

struct Node {
  int value;
  std::unique_ptr<Node> left;
  std::unique_ptr<Node> right;
  explicit Node(int v) : value(v) {}
};

void insert(std::unique_ptr<Node>& root, int value) {
  if (!root) {
    root = std::make_unique<Node>(value);
  } else if (value < root->value) {
    insert(root->left, value);
  } else if (value > root->value) {
    insert(root->right, value);
  }
}

void in_order(const Node* node) {
  if (node == nullptr) {
    return;
  }
  in_order(node->left.get());
  std::cout << " " << node->value;
  in_order(node->right.get());
}

void level_order(const Node* root) {
  std::queue<const Node*> pending;
  pending.push(root);
  while (!pending.empty()) {
    const Node* node = pending.front();
    pending.pop();
    std::cout << " " << node->value;
    if (node->left) pending.push(node->left.get());
    if (node->right) pending.push(node->right.get());
  }
}

int main() {
  std::unique_ptr<Node> root;
  for (int v : {50, 30, 70, 20, 40, 60, 80}) {
    insert(root, v);
  }
  std::cout << "in order:";
  in_order(root.get());
  std::cout << "\nlevel order:";
  level_order(root.get());
  std::cout << "\n";
}

C++ priority_queue and the top-k pattern

Use a binary heap to get the smallest element quickly, and keep the k largest values of a stream.

How would you store (distance, node) pairs with the smallest distance first?

Reveal answer and reasoning

Use std::priority_queue<std::pair<int,int>, std::vector<std::pair<int,int>>, std::greater<>>; pairs compare by the first element first.

Review lesson →Open compiler

Show starting example

C++

#include <functional>
#include <iostream>
#include <queue>
#include <vector>

int main() {
  std::priority_queue<int> max_heap;
  for (int v : {5, 1, 8, 3, 9, 2}) {
    max_heap.push(v);
  }
  std::cout << "largest first:";
  while (!max_heap.empty()) {
    std::cout << " " << max_heap.top();
    max_heap.pop();
  }
  std::cout << "\n";

  std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;
  for (int v : {5, 1, 8, 3}) {
    min_heap.push(v);
  }
  std::cout << "smallest: " << min_heap.top() << "\n";

  const std::size_t k = 3;
  std::priority_queue<int, std::vector<int>, std::greater<int>> top;
  for (int v : {7, 12, 3, 19, 5, 11, 2, 15}) {
    top.push(v);
    if (top.size() > k) {
      top.pop();
    }
  }
  std::vector<int> result;
  while (!top.empty()) {
    result.push_back(top.top());
    top.pop();
  }
  std::cout << "top 3 ascending:";
  for (int v : result) std::cout << " " << v;
  std::cout << "\n";
}

C++ graphs: BFS, DFS, and connected components

Store a graph as adjacency lists, visit it breadth-first and depth-first, and count its components.

How many components does the graph have?

Reveal answer and reasoning

Three: nodes 0, 1, 2, 3 form one component, 4 and 5 form another, and node 6 is alone in the third.

Review lesson →Open compiler

Show starting example

C++

#include <iostream>
#include <queue>
#include <vector>

void dfs(const std::vector<std::vector<int>>& g, int node, std::vector<bool>& seen) {
  seen[node] = true;
  std::cout << " " << node;
  for (int next : g[node]) {
    if (!seen[next]) {
      dfs(g, next, seen);
    }
  }
}

int main() {
  std::vector<std::vector<int>> g(7);
  auto edge = [&](int a, int b) {
    g[a].push_back(b);
    g[b].push_back(a);
  };
  edge(0, 1); edge(0, 2); edge(1, 3); edge(2, 3); edge(4, 5);

  std::vector<bool> seen(7, false);
  std::queue<int> pending;
  pending.push(0);
  seen[0] = true;
  std::cout << "bfs from 0:";
  while (!pending.empty()) {
    int node = pending.front();
    pending.pop();
    std::cout << " " << node;
    for (int next : g[node]) {
      if (!seen[next]) {
        seen[next] = true;
        pending.push(next);
      }
    }
  }
  std::cout << "\n";

  std::vector<bool> visited(7, false);
  std::cout << "dfs from 0:";
  dfs(g, 0, visited);
  std::cout << "\n";

  std::vector<bool> marked(7, false);
  int components = 0;
  for (int start = 0; start < 7; ++start) {
    if (!marked[start]) {
      ++components;
      std::queue<int> q;
      q.push(start);
      marked[start] = true;
      while (!q.empty()) {
        int node = q.front();
        q.pop();
        for (int next : g[node]) {
          if (!marked[next]) {
            marked[next] = true;
            q.push(next);
          }
        }
      }
    }
  }
  std::cout << "components: " << components << "\n";
}

C++: best, worst, and average case of linear search

Count comparisons to see that one algorithm can have different costs on different inputs.

What is the average number of comparisons for n = 100 when every item is equally likely?

Reveal answer and reasoning

(100 + 1) / 2 = 50.5 comparisons.

Review lesson →Open compiler

Show starting example

C++

#include <iostream>
#include <vector>

int comparisons = 0;

int linear_search(const std::vector<int>& values, int target) {
  for (std::size_t i = 0; i < values.size(); ++i) {
    ++comparisons;
    if (values[i] == target) {
      return static_cast<int>(i);
    }
  }
  return -1;
}

int main() {
  std::vector<int> values = {7, 3, 9, 1, 5, 8, 2, 6};
  int n = static_cast<int>(values.size());

  comparisons = 0;
  linear_search(values, 7);
  std::cout << "best case: " << comparisons << "\n";

  comparisons = 0;
  linear_search(values, 6);
  std::cout << "worst case, last item: " << comparisons << "\n";

  comparisons = 0;
  linear_search(values, 100);
  std::cout << "absent: " << comparisons << "\n";

  int total = 0;
  for (int v : values) {
    comparisons = 0;
    linear_search(values, v);
    total += comparisons;
  }
  std::cout << "average over present items: " << static_cast<double>(total) / n << "\n";
}

C++: amortized cost of a growing array

Count the copies made by a doubling array to see why push_back is amortized constant time.

How many copies after 64 appends?

Reveal answer and reasoning

63 copies (1 + 2 + 4 + 8 + 16 + 32).

Review lesson →Open compiler

Show starting example

C++

#include <cstddef>
#include <iostream>

class IntList {
 public:
  IntList() = default;
  IntList(const IntList&) = delete;
  IntList& operator=(const IntList&) = delete;
  ~IntList() { delete[] data_; }

  void add(int value) {
    if (size_ == capacity_) {
      std::size_t bigger = capacity_ == 0 ? 1 : capacity_ * 2;
      int* grown = new int[bigger];
      for (std::size_t i = 0; i < size_; ++i) {
        grown[i] = data_[i];
        ++copies_;
      }
      delete[] data_;
      data_ = grown;
      capacity_ = bigger;
    }
    data_[size_++] = value;
  }

  std::size_t copies() const { return copies_; }

 private:
  int* data_ = nullptr;
  std::size_t size_ = 0;
  std::size_t capacity_ = 0;
  std::size_t copies_ = 0;
};

int main() {
  IntList list;
  for (int i = 1; i <= 16; ++i) {
    list.add(i);
  }
  std::cout << "appends=16 copies=" << list.copies() << "\n";
  std::cout << "copies per append=" << static_cast<double>(list.copies()) / 16 << "\n";
}

C++: a hash join with unordered_map

Join two tables by building a hash table on one and probing it with each row of the other.

What if two departments shared the same id?

Reveal answer and reasoning

unordered_map keeps one value per key, so a duplicate key would be rejected by insert. Use unordered_multimap to keep both.

Review lesson →Open compiler

Show starting example

C++

#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>

struct Employee {
  std::string name;
  int dept;
};

int main() {
  std::unordered_map<int, std::string> departments = {{1, "Eng"}, {2, "Ops"}};
  std::vector<Employee> staff = {{"Ada", 1}, {"Bo", 2}, {"Cy", 1}, {"Di", 3}};

  int probes = 0;
  for (const Employee& e : staff) {
    ++probes;
    auto it = departments.find(e.dept);
    if (it != departments.end()) {
      std::cout << e.name << " -> " << it->second << "\n";
    }
  }
  std::cout << "probes=" << probes << " nested-loop comparisons="
            << staff.size() * departments.size() << "\n";
}

C++: an ordered index with std::map

Answer range and nearest-key queries with lower_bound and upper_bound.

How would you list ages 30 or older?

Reveal answer and reasoning

Iterate from by_age.lower_bound(30) to by_age.end(); that prints 31 and 45.

Review lesson →Open compiler

Show starting example

C++

#include <iostream>
#include <iterator>
#include <map>
#include <string>

int main() {
  std::map<int, std::string> by_age = {{31, "Cy"}, {24, "Ada"}, {45, "Di"}, {29, "Bo"}};

  std::cout << by_age.begin()->first << " " << by_age.rbegin()->first << "\n";

  std::cout << "range 25..40:";
  for (auto it = by_age.lower_bound(25); it != by_age.upper_bound(40); ++it) {
    std::cout << " " << it->first << "=" << it->second;
  }
  std::cout << "\n";

  auto above = by_age.lower_bound(30);
  auto below = std::prev(above);
  std::cout << "below 30: " << below->first << ", at or above 30: " << above->first << "\n";
}

C++: page replacement with FIFO and LRU

Count page faults for two replacement policies and see Belady's anomaly.

Which policy would you choose for a program that loops over a few pages repeatedly?

Reveal answer and reasoning

LRU, because recently used pages are likely to be used again, so keeping them resident avoids faults.

Review lesson →Open compiler

Show starting example

C++

#include <algorithm>
#include <deque>
#include <iostream>
#include <vector>

int fifo_faults(const std::vector<int>& refs, std::size_t frames) {
  std::deque<int> memory;
  int faults = 0;
  for (int page : refs) {
    if (std::find(memory.begin(), memory.end(), page) == memory.end()) {
      ++faults;
      if (memory.size() == frames) {
        memory.pop_front();
      }
      memory.push_back(page);
    }
  }
  return faults;
}

int lru_faults(const std::vector<int>& refs, std::size_t frames) {
  std::vector<int> memory;  // least recently used page at the front
  int faults = 0;
  for (int page : refs) {
    auto it = std::find(memory.begin(), memory.end(), page);
    if (it != memory.end()) {
      memory.erase(it);
    } else {
      ++faults;
      if (memory.size() == frames) {
        memory.erase(memory.begin());
      }
    }
    memory.push_back(page);
  }
  return faults;
}

int main() {
  std::vector<int> refs = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1};
  std::cout << "FIFO, 3 frames: " << fifo_faults(refs, 3) << "\n";
  std::cout << "LRU,  3 frames: " << lru_faults(refs, 3) << "\n";

  std::vector<int> belady = {1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5};
  std::cout << "Belady FIFO, 3 frames: " << fifo_faults(belady, 3) << "\n";
  std::cout << "Belady FIFO, 4 frames: " << fifo_faults(belady, 4) << "\n";
}

C++: protecting shared data with std::mutex

Run two threads that increment one counter and use a lock to keep every update.

How could you avoid the mutex for a plain counter?

Reveal answer and reasoning

Use std::atomic<int> and call fetch_add(1), which makes each increment atomic without a lock.

Review lesson →Open compiler

Show starting example

C++

#include <iostream>
#include <mutex>
#include <thread>

int main() {
  int counter = 0;
  std::mutex m;

  auto work = [&]() {
    for (int i = 0; i < 100000; ++i) {
      std::lock_guard<std::mutex> lock(m);
      ++counter;
    }
  };

  std::thread a(work);
  std::thread b(work);
  a.join();
  b.join();
  std::cout << "counter=" << counter << "\n";
}

C++: the Internet checksum

Compute the 16-bit ones'-complement checksum used by IP, TCP, and UDP, and use it to detect corruption.

Why is the checksum field set to zero while the sender computes it?

Reveal answer and reasoning

Because the checksum covers the whole header; including the old field value would change the sum. The sender zeroes it, computes, and then stores the result.

Review lesson →Open compiler

Show starting example

C++

#include <cstdint>
#include <iomanip>
#include <iostream>
#include <vector>

std::uint16_t checksum(const std::vector<std::uint8_t>& bytes) {
  std::uint32_t sum = 0;
  for (std::size_t i = 0; i + 1 < bytes.size(); i += 2) {
    sum += (bytes[i] << 8) | bytes[i + 1];
  }
  if (bytes.size() % 2 == 1) {
    sum += bytes.back() << 8;
  }
  while (sum >> 16) {
    sum = (sum & 0xFFFF) + (sum >> 16);
  }
  return static_cast<std::uint16_t>(~sum);
}

void show(const char* label, std::uint16_t value) {
  std::cout << label << "0x" << std::hex << std::setw(4) << std::setfill('0') << value << std::dec << "\n";
}

int main() {
  std::vector<std::uint8_t> packet = {0x00, 0x01, 0xf2, 0x03, 0xf4, 0xf5, 0xf6, 0xf7};
  std::uint16_t c = checksum(packet);
  show("checksum:        ", c);

  packet.push_back(static_cast<std::uint8_t>(c >> 8));
  packet.push_back(static_cast<std::uint8_t>(c & 0xFF));
  show("intact packet:   ", checksum(packet));

  packet[2] ^= 0x01;
  show("one bit flipped: ", checksum(packet));
}

C++: forwarding with longest-prefix match

Pick the most specific route that matches a destination address, as a router does.

Which hop is chosen for 10.1.2.200 if the /24 route is removed?

Reveal answer and reasoning

B, because the next most specific match is 10.1.0.0/16.

Review lesson →Open compiler

Show starting example

C++

#include <cstdint>
#include <iostream>
#include <string>
#include <vector>

struct Route {
  std::uint32_t network;
  int prefix;
  std::string next_hop;
};

std::uint32_t ip(int a, int b, int c, int d) {
  return (static_cast<std::uint32_t>(a) << 24) | (b << 16) | (c << 8) | d;
}

std::string lookup(const std::vector<Route>& table, std::uint32_t dest) {
  int best = -1;
  std::string hop = "drop";
  for (const Route& r : table) {
    std::uint32_t mask = r.prefix == 0 ? 0 : 0xFFFFFFFFu << (32 - r.prefix);
    if ((dest & mask) == r.network && r.prefix > best) {
      best = r.prefix;
      hop = r.next_hop;
    }
  }
  return hop;
}

int main() {
  std::vector<Route> table = {
      {ip(10, 0, 0, 0), 8, "A"},
      {ip(10, 1, 0, 0), 16, "B"},
      {ip(10, 1, 2, 0), 24, "C"},
      {ip(0, 0, 0, 0), 0, "default"},
  };
  std::cout << "10.1.2.9 -> " << lookup(table, ip(10, 1, 2, 9)) << "\n";
  std::cout << "10.1.9.9 -> " << lookup(table, ip(10, 1, 9, 9)) << "\n";
  std::cout << "10.9.9.9 -> " << lookup(table, ip(10, 9, 9, 9)) << "\n";
  std::cout << "8.8.8.8  -> " << lookup(table, ip(8, 8, 8, 8)) << "\n";
}

C++: a small unit-test harness

Check results and expected exceptions with a macro and a template, and report failures.

Add a test for the upper boundary.

Reveal answer and reasoning

CHECK(parse_percent("100") == 100); 100 is the largest allowed value, so it must be accepted.

Review lesson →Open compiler

Show starting example

C++

#include <iostream>
#include <stdexcept>
#include <string>

int failures = 0;

#define CHECK(cond)                                  \
  do {                                               \
    if (cond) {                                      \
      std::cout << "PASS " #cond "\n";               \
    } else {                                         \
      std::cout << "FAIL " #cond "\n";               \
      ++failures;                                    \
    }                                                \
  } while (0)

template <typename E, typename F>
bool throws(F fn) {
  try {
    fn();
  } catch (const E&) {
    return true;
  } catch (...) {
    return false;
  }
  return false;
}

int parse_percent(const std::string& text) {
  int value = std::stoi(text);
  if (value < 0 || value > 100) {
    throw std::out_of_range("percent out of range");
  }
  return value;
}

int main() {
  CHECK(parse_percent("42") == 42);
  CHECK(parse_percent("0") == 0);
  CHECK(throws<std::out_of_range>([] { parse_percent("101"); }));
  CHECK(throws<std::invalid_argument>([] { parse_percent("abc"); }));
  std::cout << "failures: " << failures << "\n";
}

C++: the observer pattern with std::function

Notify any number of listeners without the publisher knowing what they do.

How do you let a listener be removed later?

Reveal answer and reasoning

Return an id from subscribe and keep listeners in a map from id to callback, then erase by id.

Review lesson →Open compiler

Show starting example

C++

#include <functional>
#include <iostream>
#include <string>
#include <vector>

class EventBus {
 public:
  void subscribe(std::function<void(const std::string&)> listener) {
    listeners_.push_back(std::move(listener));
  }

  void publish(const std::string& event) const {
    for (const auto& listener : listeners_) {
      listener(event);
    }
  }

 private:
  std::vector<std::function<void(const std::string&)>> listeners_;
};

int main() {
  EventBus bus;
  std::vector<std::string> log;

  bus.subscribe([&log](const std::string& e) { log.push_back(e); });
  bus.subscribe([](const std::string& e) { std::cout << "got " << e << "\n"; });

  bus.publish("order_placed");
  bus.publish("order_shipped");
  std::cout << "logged " << log.size() << " events\n";
}

C++: preventing buffer overflows with bounds checks

Reject writes that do not fit in a buffer and use at() so out-of-range reads fail safely.

Why is the terminating zero included in the length check?

Reveal answer and reasoning

A C string needs one extra byte for the terminating '\0'. Without counting it, a name that exactly fills the buffer would write one byte beyond it.

Review lesson →Open compiler

Show starting example

C++

#include <cstddef>
#include <cstring>
#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>

bool copy_name(const std::string& input, char* out, std::size_t capacity) {
  if (input.size() + 1 > capacity) {
    return false;
  }
  std::memcpy(out, input.c_str(), input.size() + 1);
  return true;
}

int main() {
  char buffer[8];
  std::cout << copy_name("Ada", buffer, sizeof buffer) << " " << buffer << "\n";
  std::cout << copy_name("Programonic", buffer, sizeof buffer) << " " << buffer << "\n";

  std::vector<int> scores = {82, 91, 76};
  try {
    std::cout << scores.at(1) << "\n";
    std::cout << scores.at(7) << "\n";
  } catch (const std::out_of_range&) {
    std::cout << "index 7 rejected\n";
  }
}

C++: validating untrusted input with std::from_chars

Parse a port number strictly and reject anything that is not exactly a number in range.

How would you also allow surrounding spaces?

Reveal answer and reasoning

Trim the spaces first, then parse the trimmed view; do not make the parser itself lenient.

Review lesson →Open compiler

Show starting example

C++

#include <charconv>
#include <iostream>
#include <optional>
#include <string_view>

std::optional<int> parse_port(std::string_view text) {
  int value = 0;
  const char* end = text.data() + text.size();
  auto [ptr, ec] = std::from_chars(text.data(), end, value);
  if (ec != std::errc() || ptr != end) {
    return std::nullopt;
  }
  if (value < 1 || value > 65535) {
    return std::nullopt;
  }
  return value;
}

int main() {
  for (std::string_view input : {"8080", "0", "70000", "80a", "", " 22"}) {
    auto port = parse_port(input);
    std::cout << "'" << input << "' -> ";
    if (port) {
      std::cout << *port << "\n";
    } else {
      std::cout << "rejected\n";
    }
  }
}

C++: splitting a sum across std::async tasks

Run two halves of a computation concurrently and combine the results with futures.

How would you split the work into four parts?

Reveal answer and reasoning

Launch four async tasks over ranges 0–250, 250–500, 500–750, and 750–1000, then add the four get() results.

Review lesson →Open compiler

Show starting example

C++

#include <functional>
#include <future>
#include <iostream>
#include <numeric>
#include <vector>

long long sum_range(const std::vector<int>& v, std::size_t from, std::size_t to) {
  return std::accumulate(v.begin() + from, v.begin() + to, 0LL);
}

int main() {
  std::vector<int> data(1000);
  std::iota(data.begin(), data.end(), 1);

  auto first = std::async(std::launch::async, sum_range, std::cref(data), 0, 500);
  auto second = std::async(std::launch::async, sum_range, std::cref(data), 500, 1000);

  long long total = first.get() + second.get();
  std::cout << "sum 1..1000 = " << total << "\n";
}

C++: lock-free counting with std::atomic

Increment a shared counter from four threads without a mutex.

What would counter++ on a plain int do here?

Reveal answer and reasoning

It is a data race, which is undefined behaviour in C++: increments would usually be lost and the total would be less than 200000.

Review lesson →Open compiler

Show starting example

C++

#include <atomic>
#include <iostream>
#include <thread>
#include <vector>

int main() {
  std::atomic<int> counter{0};
  std::vector<std::thread> threads;

  for (int t = 0; t < 4; ++t) {
    threads.emplace_back([&counter] {
      for (int i = 0; i < 50000; ++i) {
        counter.fetch_add(1, std::memory_order_relaxed);
      }
    });
  }
  for (std::thread& th : threads) {
    th.join();
  }
  std::cout << "counter=" << counter.load() << "\n";
}

C++: A* search with a Manhattan-distance heuristic

Guide a shortest-path search with an estimate of the remaining distance.

What heuristic makes A* behave like breadth-first search?

Reveal answer and reasoning

h = 0 for every cell; then f equals g and cells are expanded in order of distance from the start.

Review lesson →Open compiler

Show starting example

C++

#include <cstdlib>
#include <iostream>
#include <queue>
#include <string>
#include <tuple>
#include <vector>

int main() {
  std::vector<std::string> grid = {
      "S..#.",
      ".#...",
      ".#.#.",
      "....G",
  };
  int rows = 4, cols = 5;
  int goal_r = 3, goal_c = 4;
  auto h = [&](int r, int c) { return std::abs(r - goal_r) + std::abs(c - goal_c); };

  std::vector<std::vector<int>> best(rows, std::vector<int>(cols, 1000));
  using Item = std::tuple<int, int, int, int, int>;  // f, h, g, row, col
  std::priority_queue<Item, std::vector<Item>, std::greater<Item>> open;
  best[0][0] = 0;
  open.emplace(h(0, 0), h(0, 0), 0, 0, 0);

  int expanded = 0;
  int dr[] = {1, -1, 0, 0};
  int dc[] = {0, 0, 1, -1};
  while (!open.empty()) {
    auto [f, hv, g, r, c] = open.top();
    open.pop();
    if (g > best[r][c]) {
      continue;
    }
    ++expanded;
    if (r == goal_r && c == goal_c) {
      std::cout << "path length " << g << ", expanded " << expanded << " cells\n";
      return 0;
    }
    for (int k = 0; k < 4; ++k) {
      int nr = r + dr[k], nc = c + dc[k];
      if (nr < 0 || nr >= rows || nc < 0 || nc >= cols || grid[nr][nc] == '#') {
        continue;
      }
      if (g + 1 < best[nr][nc]) {
        best[nr][nc] = g + 1;
        open.emplace(g + 1 + h(nr, nc), h(nr, nc), g + 1, nr, nc);
      }
    }
  }
  std::cout << "no path\n";
}

C++: minimax with alpha-beta pruning

Search a game tree and skip branches that cannot change the result.

Does pruning ever change the root value?

Reveal answer and reasoning

No. Alpha-beta returns exactly the minimax value; it only skips branches that cannot affect it.

Review lesson →Open compiler

Show starting example

C++

#include <algorithm>
#include <climits>
#include <iostream>
#include <vector>

int visited = 0;

int search(const std::vector<int>& leaves, int depth, int index, bool maximizing,
           int alpha, int beta, bool prune) {
  if (depth == 3) {
    ++visited;
    return leaves[index];
  }
  int best = maximizing ? INT_MIN : INT_MAX;
  for (int child = 0; child < 2; ++child) {
    int value = search(leaves, depth + 1, index * 2 + child, !maximizing, alpha, beta, prune);
    if (maximizing) {
      best = std::max(best, value);
      alpha = std::max(alpha, best);
    } else {
      best = std::min(best, value);
      beta = std::min(beta, best);
    }
    if (prune && beta <= alpha) {
      break;
    }
  }
  return best;
}

int main() {
  std::vector<int> leaves = {3, 5, 6, 9, 1, 2, 0, -1};

  visited = 0;
  int plain = search(leaves, 0, 0, true, INT_MIN, INT_MAX, false);
  std::cout << "minimax value " << plain << ", leaves visited " << visited << "\n";

  visited = 0;
  int pruned = search(leaves, 0, 0, true, INT_MIN, INT_MAX, true);
  std::cout << "alpha-beta value " << pruned << ", leaves visited " << visited << "\n";
}

C++: entailment by enumerating models

Test whether a knowledge base entails a query by checking every truth assignment.

Does the KB entail 'A or B'?

Reveal answer and reasoning

Yes. 'A or B' is one of its own sentences, so it holds in every model of the KB.

Review lesson →Open compiler

Show starting example

C++

#include <iostream>

bool kb(bool a, bool b, bool c) {
  return (a || b) && (!a || c) && (!b || c);
}

template <typename Query>
bool entails(Query query) {
  for (int mask = 0; mask < 8; ++mask) {
    bool a = mask & 1, b = mask & 2, c = mask & 4;
    if (kb(a, b, c) && !query(a, b, c)) {
      return false;
    }
  }
  return true;
}

int main() {
  int models = 0;
  for (int mask = 0; mask < 8; ++mask) {
    if (kb(mask & 1, mask & 2, mask & 4)) {
      ++models;
    }
  }
  std::cout << std::boolalpha;
  std::cout << "KB models: " << models << "\n";
  std::cout << "entails C: " << entails([](bool, bool, bool c) { return c; }) << "\n";
  std::cout << "entails A: " << entails([](bool a, bool, bool) { return a; }) << "\n";
}

C++: backward chaining from a goal

Prove a goal by finding a rule that concludes it and then proving that rule's conditions.

What would the output be for goal 'wet'?

Reveal answer and reasoning

'goal wet' followed by an indented 'goal rain -> fact', then 'proved'.

Review lesson →Open compiler

Show starting example

C++

#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>

std::set<std::string> facts = {"rain", "cold"};
std::map<std::string, std::vector<std::string>> rules = {
    {"wet", {"rain"}},
    {"ice", {"wet", "cold"}},
    {"slippery", {"ice"}},
};

bool prove(const std::string& goal, int depth) {
  std::cout << std::string(depth * 2, ' ') << "goal " << goal;
  if (facts.count(goal)) {
    std::cout << " -> fact\n";
    return true;
  }
  auto rule = rules.find(goal);
  if (rule == rules.end()) {
    std::cout << " -> no rule\n";
    return false;
  }
  std::cout << "\n";
  for (const std::string& condition : rule->second) {
    if (!prove(condition, depth + 1)) {
      return false;
    }
  }
  return true;
}

int main() {
  std::cout << (prove("slippery", 0) ? "proved" : "not proved") << "\n";
  std::cout << (prove("sunny", 0) ? "proved" : "not proved") << "\n";
}

C++: linear regression with gradient descent

Fit y = w·x + b by repeatedly moving the parameters against the gradient of the mean squared error.

What does the model predict for x = 5?

Reveal answer and reasoning

3·5 − 2 = 13, because the fitted line is y = 3x − 2.

Review lesson →Open compiler

Show starting example

C++

#include <iomanip>
#include <iostream>
#include <vector>

int main() {
  std::vector<double> x = {0, 1, 2, 3, 4};
  std::vector<double> y = {-2, 1, 4, 7, 10};
  double w = 0.0, b = 0.0, rate = 0.05;
  double n = static_cast<double>(x.size());

  for (int epoch = 0; epoch < 5000; ++epoch) {
    double gw = 0.0, gb = 0.0;
    for (std::size_t i = 0; i < x.size(); ++i) {
      double error = w * x[i] + b - y[i];
      gw += 2 * error * x[i] / n;
      gb += 2 * error / n;
    }
    w -= rate * gw;
    b -= rate * gb;
  }
  std::cout << std::fixed << std::setprecision(2);
  std::cout << "w=" << w << " b=" << b << "\n";
  std::cout << "prediction for x=10: " << w * 10 + b << "\n";
}

C++: k-means clustering

Group unlabeled points by alternating between assigning points to centers and moving centers to the mean.

What happens if a cluster loses all of its points?

Reveal answer and reasoning

Its mean is undefined. The code above leaves that center unchanged; other implementations re-seed it from a random point.

Review lesson →Open compiler

Show starting example

C++

#include <cmath>
#include <iomanip>
#include <iostream>
#include <vector>

struct Point {
  double x, y;
};

int main() {
  std::vector<Point> points = {{1, 1}, {1.5, 2}, {3, 4}, {5, 7}, {3.5, 5}, {4.5, 5}, {3.5, 4.5}};
  std::vector<Point> centers = {points[0], points[3]};
  std::vector<int> label(points.size(), 0);

  for (int round = 0; round < 10; ++round) {
    for (std::size_t i = 0; i < points.size(); ++i) {
      double best = 1e18;
      for (int c = 0; c < 2; ++c) {
        double d = std::hypot(points[i].x - centers[c].x, points[i].y - centers[c].y);
        if (d < best) {
          best = d;
          label[i] = c;
        }
      }
    }
    for (int c = 0; c < 2; ++c) {
      double sx = 0, sy = 0;
      int count = 0;
      for (std::size_t i = 0; i < points.size(); ++i) {
        if (label[i] == c) {
          sx += points[i].x;
          sy += points[i].y;
          ++count;
        }
      }
      if (count > 0) {
        centers[c] = {sx / count, sy / count};
      }
    }
  }
  std::cout << std::fixed << std::setprecision(2);
  for (int c = 0; c < 2; ++c) {
    std::cout << "center " << c << ": (" << centers[c].x << ", " << centers[c].y << ")\n";
  }
  for (std::size_t i = 0; i < points.size(); ++i) {
    std::cout << label[i];
  }
  std::cout << "\n";
}

C++: a perceptron learns OR but not XOR

Train the same neuron on two gates and compare the accuracy it can reach.

What do you add to a perceptron to solve XOR?

Reveal answer and reasoning

A hidden layer with a non-linear activation, which gives a multilayer network.

Review lesson →Open compiler

Show starting example

C++

#include <algorithm>
#include <iostream>

int train(const int targets[4], int epochs) {
  const int inputs[4][2] = {{0, 0}, {0, 1}, {1, 0}, {1, 1}};
  double w1 = 0, w2 = 0, bias = 0, rate = 0.1;
  int best = 0;
  for (int epoch = 0; epoch < epochs; ++epoch) {
    for (int i = 0; i < 4; ++i) {
      double sum = w1 * inputs[i][0] + w2 * inputs[i][1] + bias;
      int output = sum > 0 ? 1 : 0;
      int error = targets[i] - output;
      w1 += rate * error * inputs[i][0];
      w2 += rate * error * inputs[i][1];
      bias += rate * error;
    }
    int correct = 0;
    for (int i = 0; i < 4; ++i) {
      double sum = w1 * inputs[i][0] + w2 * inputs[i][1] + bias;
      correct += ((sum > 0 ? 1 : 0) == targets[i]);
    }
    best = std::max(best, correct);
  }
  return best;
}

int main() {
  const int or_targets[4] = {0, 1, 1, 1};
  const int xor_targets[4] = {0, 1, 1, 0};
  std::cout << "OR best accuracy: " << train(or_targets, 200) << "/4\n";
  std::cout << "XOR best accuracy: " << train(xor_targets, 200) << "/4\n";
}

C++: stable softmax and cross-entropy loss

Turn raw scores into probabilities, measure the loss, and avoid overflow.

What is the softmax of equal logits {1, 1, 1, 1}?

Reveal answer and reasoning

Each probability is 0.25, because all exponents are equal.

Review lesson →Open compiler

Show starting example

C++

#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <vector>

std::vector<double> softmax(const std::vector<double>& z) {
  double largest = *std::max_element(z.begin(), z.end());
  std::vector<double> p(z.size());
  double total = 0.0;
  for (std::size_t i = 0; i < z.size(); ++i) {
    p[i] = std::exp(z[i] - largest);
    total += p[i];
  }
  for (double& v : p) {
    v /= total;
  }
  return p;
}

int main() {
  std::cout << std::fixed << std::setprecision(3);
  std::vector<double> p = softmax({2.0, 1.0, 0.1});
  std::cout << p[0] << " " << p[1] << " " << p[2] << "\n";
  std::cout << "loss if class 0 is true: " << -std::log(p[0]) << "\n";
  std::cout << "loss if class 2 is true: " << -std::log(p[2]) << "\n";

  std::vector<double> big = softmax({1000.0, 1001.0});
  std::cout << big[0] << " " << big[1] << "\n";
}

C++: convolution with zero padding

Apply a Laplacian kernel so the output has the same size as the input and responds to a single bright pixel.

What would the output be for a uniform image of all 5s?

Reveal answer and reasoning

Interior pixels give 0, because 4·5 − 4·5 = 0. Border pixels are non-zero because the missing neighbours are treated as zeros.

Review lesson →Open compiler

Show starting example

C++

#include <iomanip>
#include <iostream>
#include <vector>

int main() {
  const int n = 5;
  std::vector<std::vector<int>> image(n, std::vector<int>(n, 0));
  image[2][2] = 10;
  int kernel[3][3] = {{0, 1, 0}, {1, -4, 1}, {0, 1, 0}};

  std::vector<std::vector<int>> out(n, std::vector<int>(n, 0));
  for (int r = 0; r < n; ++r) {
    for (int c = 0; c < n; ++c) {
      int sum = 0;
      for (int kr = -1; kr <= 1; ++kr) {
        for (int kc = -1; kc <= 1; ++kc) {
          int rr = r + kr, cc = c + kc;
          if (rr >= 0 && rr < n && cc >= 0 && cc < n) {
            sum += image[rr][cc] * kernel[kr + 1][kc + 1];
          }
        }
      }
      out[r][c] = sum;
    }
  }
  for (const auto& row : out) {
    for (int v : row) {
      std::cout << std::setw(4) << v;
    }
    std::cout << "\n";
  }
}

C++: grayscale conversion and thresholding

Convert color pixels to brightness with luminance weights and split them into foreground and background.

Which weights are used by the older NTSC formula and by modern HDTV (Rec. 709)?

Reveal answer and reasoning

NTSC (Rec. 601) uses 0.299, 0.587, 0.114. Rec. 709 uses 0.2126, 0.7152, 0.0722.

Review lesson →Open compiler

Show starting example

C++

#include <cmath>
#include <iostream>
#include <vector>

struct Rgb {
  int r, g, b;
};

int main() {
  std::vector<Rgb> pixels = {{255, 0, 0}, {0, 255, 0}, {0, 0, 255}, {255, 255, 255}};
  std::vector<int> gray;
  double total = 0;
  for (const Rgb& p : pixels) {
    int value = static_cast<int>(std::lround(0.299 * p.r + 0.587 * p.g + 0.114 * p.b));
    gray.push_back(value);
    total += value;
  }
  double threshold = total / gray.size();

  std::cout << "gray:";
  for (int v : gray) {
    std::cout << " " << v;
  }
  std::cout << "\nthreshold: " << threshold << "\nbinary:";
  for (int v : gray) {
    std::cout << " " << (v > threshold ? 1 : 0);
  }
  std::cout << "\n";
}

C++ Basics

C++ conditions and range loops

C++ functions and references

C++ recursive factorial

C++ strings and string streams

C++ references, const, and auto

C++ lambdas and the standard algorithms

C++ Classes

C++ constructors and encapsulation

C++ abstract classes and virtual dispatch

C++ composition and RAII

C++ function templates

C++ inheritance and virtual functions

C++ operator overloading

C++ smart pointers and ownership

C++ vectors and iterator invalidation

C++ binary search with lower_bound

C++ stack and queue adapters

C++ ordered maps and frequencies

C++ linked lists with unique ownership

C++ sorting: insertion sort, merge sort, and std::stable_sort

C++ singly linked list with unique_ptr

C++ binary search tree traversals

C++ priority_queue and the top-k pattern

C++ graphs: BFS, DFS, and connected components

C++: best, worst, and average case of linear search

C++: amortized cost of a growing array

C++: a hash join with unordered_map

C++: an ordered index with std::map

C++: page replacement with FIFO and LRU

C++: protecting shared data with std::mutex

C++: the Internet checksum

C++: forwarding with longest-prefix match

C++: a small unit-test harness

C++: the observer pattern with std::function

C++: preventing buffer overflows with bounds checks

C++: validating untrusted input with std::from_chars

C++: splitting a sum across std::async tasks

C++: lock-free counting with std::atomic

C++: A* search with a Manhattan-distance heuristic

C++: minimax with alpha-beta pruning

C++: entailment by enumerating models

C++: backward chaining from a goal

C++: linear regression with gradient descent

C++: k-means clustering

C++: a perceptron learns OR but not XOR

C++: stable softmax and cross-entropy loss

C++: convolution with zero padding

C++: grayscale conversion and thresholding