Practice

C exercises

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

1
C Variables
Declare typed values.
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 <stdio.h>
int main(void) {
  int score = 91;
  printf("%d\n", score);
  return 0;
}
```
2
C Arrays
Store a fixed sequence.
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 <stdio.h>
int main(void) {
  int scores[] = {82, 91, 76};
  printf("%d\n", scores[1]);
  return 0;
}
```
3
C Pointers
Work with memory addresses.
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 <stdio.h>
int main(void) {
  int score = 91;
  int *pointer = &score;
  printf("%d\n", *pointer);
  return 0;
}
```
4
C conditions, loops, and totals
Combine a counted loop with an even-number condition.
Change the endpoint to 8.
Reveal answer and reasoning
The total becomes 20 because 8 is included.
Review lesson →Open compiler
Show starting example
C
```
#include <stdio.h>
#include <assert.h>
int main(void) {
    int total = 0;
    for (int i = 1; i <= 6; i++) {
        if (i % 2 == 0) total += i;
    }
    printf("%d\n", total);
    assert(total == 12);
    return 0;
}
```

C strings and null terminators

Traverse characters without reading beyond the string.

Extend the condition to include o and u, and use 'education'.

Reveal answer and reasoning

The count is 5: e, u, a, i, o.

Review lesson →Open compiler

Show starting example

#include <stdio.h>
#include <assert.h>
int main(void) {
    const char text[] = "learning";
    int count = 0;
    for (int i = 0; text[i] != '\0'; i++) {
        if (text[i] == 'a' || text[i] == 'e' || text[i] == 'i') {
            count++;
        }
    }
    printf("%d\n", count);
    assert(count == 3);
    return 0;
}

C functions and pointer parameters

Modify caller-owned values through valid addresses.

Trace swapping x=5 and y=5.

Reveal answer and reasoning

The temporary is 5, both assignments store 5, and the two values remain equal.

Review lesson →Open compiler

Show starting example

#include <stdio.h>
#include <assert.h>
void swap(int *a, int *b) {
    int temporary = *a;
    *a = *b;
    *b = temporary;
}
int main(void) {
    int x = 3, y = 8;
    swap(&x, &y);
    printf("%d %d\n", x, y);
    swap(&x, &x);
    assert(x == 8 && y == 3);
    return 0;
}

C structures and records

Group related fields into a typed record.

Set second.name[0] to 'E'. Does first.name change?

Reveal answer and reasoning

No. The arrays are separate; first prints Ada and second prints Eda.

Review lesson →Open compiler

Show starting example

#include <stdio.h>
#include <assert.h>
struct Student { char name[20]; int score; };
int main(void) {
    struct Student first = {"Ada", 82};
    struct Student second = first;
    second.score = 95;
    printf("%s %d\n", first.name, first.score);
    printf("%s %d\n", second.name, second.score);
    assert(first.score == 82);
    return 0;
}

8
C dynamic memory and ownership
Allocate, check, use, and free a heap buffer.
Allocate five ints and print the fifth initialized value.
Reveal answer and reasoning
Change both the allocation count and loop bound to 5, then print values[4], which is 50.
Review lesson →Open compiler
Show starting example
C
```
#include <stdio.h>
#include <stdlib.h>
int main(void) {
    int *values = malloc(3 * sizeof *values);
    if (values == NULL) return 1;
    for (int i = 0; i < 3; i++) values[i] = (i + 1) * 10;
    printf("%d\n", values[2]);
    free(values);
    values = NULL;
    return 0;
}
```

C reading and writing text files

Write lines to a file with fprintf, read them back with fgets, and parse each line with sscanf.

Why is fclose important?

Reveal answer and reasoning

It flushes buffered data to the file and releases the file handle. Without it, data can be lost and handles leak.

Review lesson →Open compiler

Show starting example

#include <stdio.h>

int main(void) {
  FILE *file = fopen("lesson_data.txt", "w+");
  if (file == NULL) {
    printf("could not open the file\n");
    return 1;
  }
  fprintf(file, "alpha 3\nbeta 5\ngamma 8\nbad line\n");
  rewind(file);

  char line[64];
  int total = 0;
  int good = 0;
  while (fgets(line, sizeof line, file) != NULL) {
    char name[32];
    int value;
    if (sscanf(line, "%31s %d", name, &value) == 2) {
      printf("%s -> %d\n", name, value);
      total += value;
      good++;
    } else {
      printf("skipped a malformed line\n");
    }
  }
  fclose(file);
  remove("lesson_data.txt");
  printf("%d good lines, total %d\n", good, total);
  return 0;
}

C bit manipulation and flags

Set, clear, test, and toggle bits with &, |, ^, ~, and shifts, and count set bits.

How do you test whether the execute flag is set?

Reveal answer and reasoning

(perms & FLAG_EXEC) != 0 is true when the bit is set.

Review lesson →Open compiler

Show starting example

#include <stdint.h>
#include <stdio.h>

#define FLAG_READ (1u << 0)
#define FLAG_WRITE (1u << 1)
#define FLAG_EXEC (1u << 2)

static int popcount(uint32_t x) {
  int count = 0;
  while (x != 0) {
    x &= x - 1;
    count++;
  }
  return count;
}

static int is_power_of_two(uint32_t x) {
  return x != 0 && (x & (x - 1)) == 0;
}

int main(void) {
  unsigned perms = FLAG_READ | FLAG_WRITE;
  printf("can write: %d\n", (perms & FLAG_WRITE) != 0);
  perms |= FLAG_EXEC;
  perms &= ~FLAG_WRITE;
  perms ^= FLAG_READ;
  printf("perms: %u\n", perms);
  printf("popcount(255) = %d, popcount(1024) = %d\n", popcount(255), popcount(1024));
  printf("64 is a power of two: %d, 66: %d\n", is_power_of_two(64), is_power_of_two(66));

  int a = 5, b = 9;
  a ^= b;
  b ^= a;
  a ^= b;
  printf("swapped: a=%d b=%d\n", a, b);
  return 0;
}

C two-dimensional arrays

Store a matrix, transpose it, and multiply it with another one.

What are the dimensions of the product of a 2×3 matrix and a 3×4 matrix?

Reveal answer and reasoning

2×4: the result has the row count of the first matrix and the column count of the second.

Review lesson →Open compiler

Show starting example

#include <stdio.h>

int main(void) {
  int a[2][3] = {{1, 2, 3}, {4, 5, 6}};
  int t[3][2];

  for (int r = 0; r < 2; r++) {
    for (int c = 0; c < 3; c++) {
      t[c][r] = a[r][c];
    }
  }
  printf("transpose:\n");
  for (int r = 0; r < 3; r++) {
    printf("%d %d\n", t[r][0], t[r][1]);
  }

  int p[2][2] = {{0, 0}, {0, 0}};
  for (int i = 0; i < 2; i++) {
    for (int j = 0; j < 2; j++) {
      for (int k = 0; k < 3; k++) {
        p[i][j] += a[i][k] * t[k][j];
      }
    }
  }
  printf("a times its transpose:\n");
  for (int i = 0; i < 2; i++) {
    printf("%d %d\n", p[i][0], p[i][1]);
  }
  return 0;
}

C macros versus inline functions

See how a macro evaluates its arguments more than once and why a function is safer.

Why is the macro result 4 and not 3?

Reveal answer and reasoning

The condition i++ > 2 increments i to 4 and then the true branch evaluates i++ again, returning 4 and leaving i at 5.

Review lesson →Open compiler

Show starting example

#include <stdio.h>

#define MAX_MACRO(a, b) ((a) > (b) ? (a) : (b))

static inline int max_function(int a, int b) {
  return a > b ? a : b;
}

static int calls = 0;

static int five(void) {
  calls++;
  return 5;
}

int main(void) {
  int i = 3;
  int from_macro = MAX_MACRO(i++, 2);
  printf("macro: result %d, i = %d\n", from_macro, i);

  int j = 3;
  int from_function = max_function(j++, 2);
  printf("function: result %d, j = %d\n", from_function, j);

  calls = 0;
  int m = MAX_MACRO(five(), 2);
  printf("macro called five() %d times (result %d)\n", calls, m);

  calls = 0;
  int f = max_function(five(), 2);
  printf("function called five() %d time (result %d)\n", calls, f);
  return 0;
}

C array search with explicit length

Search only within the supplied array bounds.

Search for 5 and then 4.

Reveal answer and reasoning

The results are 0 and -1 respectively.

Review lesson →Open compiler

Show starting example

#include <stdio.h>
#include <assert.h>
int find(const int values[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (values[i] == target) return i;
    }
    return -1;
}
int main(void) {
    int values[] = {5, 2, 7};
    printf("%d\n", find(values, 3, 7));
    assert(find(values, 0, 7) == -1);
    assert(find(values, 3, 9) == -1);
    return 0;
}

C linked nodes and traversal

Connect records with pointers and follow a chain.

Link first directly to third.

Reveal answer and reasoning

Traversal prints 10 then 30; second still exists but is not reachable from first.

Review lesson →Open compiler

Show starting example

#include <stdio.h>
struct Node { int value; struct Node *next; };
int main(void) {
    struct Node third = {30, NULL};
    struct Node second = {20, &third};
    struct Node first = {10, &second};
    for (struct Node *current = &first; current != NULL; current = current->next) {
        printf("%d\n", current->value);
    }
    return 0;
}

C array-based stacks and circular queues

Build a fixed-capacity stack and a queue that wraps around the end of its array.

What does the stack hold after the two pops?

Reveal answer and reasoning

The values 10 and 20, with 20 on top.

Review lesson →Open compiler

Show starting example

#include <stdio.h>

#define CAP 4

typedef struct {
  int data[CAP];
  int top;
} Stack;

static int push(Stack *s, int value) {
  if (s->top == CAP) {
    return 0;
  }
  s->data[s->top++] = value;
  return 1;
}

static int pop(Stack *s, int *out) {
  if (s->top == 0) {
    return 0;
  }
  *out = s->data[--s->top];
  return 1;
}

typedef struct {
  int data[CAP];
  int head;
  int size;
} Queue;

static int enqueue(Queue *q, int value) {
  if (q->size == CAP) {
    return 0;
  }
  q->data[(q->head + q->size) % CAP] = value;
  q->size++;
  return 1;
}

static int dequeue(Queue *q, int *out) {
  if (q->size == 0) {
    return 0;
  }
  *out = q->data[q->head];
  q->head = (q->head + 1) % CAP;
  q->size--;
  return 1;
}

int main(void) {
  Stack s = {{0}, 0};
  for (int v = 10; v <= 40; v += 10) {
    push(&s, v);
  }
  printf("fifth push succeeded: %d\n", push(&s, 50));
  int a, b;
  pop(&s, &a);
  pop(&s, &b);
  printf("popped %d then %d\n", a, b);

  Queue q = {{0}, 0, 0};
  for (int v = 1; v <= 4; v++) {
    enqueue(&q, v);
  }
  int x, y;
  dequeue(&q, &x);
  dequeue(&q, &y);
  enqueue(&q, 5);
  enqueue(&q, 6);
  printf("dequeued %d and %d, then wrapped around; queue holds:", x, y);
  int value;
  while (dequeue(&q, &value)) {
    printf(" %d", value);
  }
  printf("\n");
  return 0;
}

C binary search and the standard bsearch

Find a value in a sorted array in logarithmic time, by hand and with the library function.

How many steps does the worst case need for 1,000,000 elements?

Reveal answer and reasoning

At most 20 steps, because 2^20 is just over a million.

Review lesson →Open compiler

Show starting example

#include <stdio.h>
#include <stdlib.h>

static int binary_search(const int *a, int n, int key, int *steps) {
  int low = 0, high = n - 1;
  *steps = 0;
  while (low <= high) {
    (*steps)++;
    int mid = low + (high - low) / 2;
    if (a[mid] == key) {
      return mid;
    }
    if (a[mid] < key) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  return -1;
}

static int compare_ints(const void *x, const void *y) {
  int a = *(const int *)x;
  int b = *(const int *)y;
  return (a > b) - (a < b);
}

int main(void) {
  int primes[] = {2, 3, 5, 7, 11, 13, 17, 19};
  int n = (int)(sizeof primes / sizeof primes[0]);
  int steps;

  int index = binary_search(primes, n, 11, &steps);
  printf("11: index %d in %d steps\n", index, steps);
  index = binary_search(primes, n, 4, &steps);
  printf("4: index %d in %d steps\n", index, steps);

  int key = 17;
  int *found = bsearch(&key, primes, (size_t)n, sizeof primes[0], compare_ints);
  printf("bsearch finds 17 at index %d\n", found ? (int)(found - primes) : -1);
  return 0;
}

C sorting: bubble sort versus quicksort

Implement two sorts, count their comparisons, and see why O(n log n) beats O(n²).

How many comparisons does bubble sort need on an already sorted array of 9 elements?

Reveal answer and reasoning

8 comparisons, because one pass with no swaps proves that the array is sorted.

Review lesson →Open compiler

Show starting example

#include <stdio.h>

static long comparisons = 0;

static void bubble_sort(int *a, int n) {
  for (int pass = 0; pass < n - 1; pass++) {
    int swapped = 0;
    for (int i = 0; i < n - 1 - pass; i++) {
      comparisons++;
      if (a[i] > a[i + 1]) {
        int tmp = a[i];
        a[i] = a[i + 1];
        a[i + 1] = tmp;
        swapped = 1;
      }
    }
    if (!swapped) {
      break;
    }
  }
}

static void quick_sort(int *a, int low, int high) {
  if (low >= high) {
    return;
  }
  int pivot = a[high];
  int boundary = low;
  for (int i = low; i < high; i++) {
    comparisons++;
    if (a[i] < pivot) {
      int tmp = a[i];
      a[i] = a[boundary];
      a[boundary] = tmp;
      boundary++;
    }
  }
  int tmp = a[boundary];
  a[boundary] = a[high];
  a[high] = tmp;
  quick_sort(a, low, boundary - 1);
  quick_sort(a, boundary + 1, high);
}

static void show(const char *label, const int *a, int n) {
  printf("%s:", label);
  for (int i = 0; i < n; i++) {
    printf(" %d", a[i]);
  }
  printf("\n");
}

int main(void) {
  int one[] = {9, 4, 7, 1, 8, 2, 6, 3, 5};
  int two[] = {9, 4, 7, 1, 8, 2, 6, 3, 5};
  int n = 9;

  comparisons = 0;
  bubble_sort(one, n);
  show("bubble", one, n);
  printf("bubble comparisons: %ld\n", comparisons);

  comparisons = 0;
  quick_sort(two, 0, n - 1);
  show("quick ", two, n);
  printf("quick comparisons: %ld\n", comparisons);
  return 0;
}

C binary search trees with malloc and free

Allocate tree nodes dynamically, traverse them in order, and release every node.

Which function visits nodes in the order 50 30 20 40 70 60 80?

Reveal answer and reasoning

A pre-order traversal: print the node first, then the left subtree, then the right subtree.

Review lesson →Open compiler

Show starting example

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
  int value;
  struct Node *left;
  struct Node *right;
} Node;

static Node *insert(Node *root, int value) {
  if (root == NULL) {
    Node *node = malloc(sizeof *node);
    if (node == NULL) {
      exit(1);
    }
    node->value = value;
    node->left = NULL;
    node->right = NULL;
    return node;
  }
  if (value < root->value) {
    root->left = insert(root->left, value);
  } else if (value > root->value) {
    root->right = insert(root->right, value);
  }
  return root;
}

static void in_order(const Node *root) {
  if (root == NULL) {
    return;
  }
  in_order(root->left);
  printf(" %d", root->value);
  in_order(root->right);
}

static int height(const Node *root) {
  if (root == NULL) {
    return 0;
  }
  int l = height(root->left);
  int r = height(root->right);
  return 1 + (l > r ? l : r);
}

static void free_tree(Node *root) {
  if (root == NULL) {
    return;
  }
  free_tree(root->left);
  free_tree(root->right);
  free(root);
}

int main(void) {
  Node *root = NULL;
  int values[] = {50, 30, 70, 20, 40, 60, 80, 40};
  for (int i = 0; i < 8; i++) {
    root = insert(root, values[i]);
  }
  printf("in order:");
  in_order(root);
  printf("\n");
  printf("height: %d\n", height(root));
  free_tree(root);
  return 0;
}

C string algorithms

Write strlen and strcmp by hand, check palindromes, and count occurrences with strstr.

Why does the example print 1 for my_strcmp("apple", "apple") == 0?

Reveal answer and reasoning

The comparison expression is true, which C represents as the integer 1. The two strings are identical, so strcmp returns 0.

Review lesson →Open compiler

Show starting example

#include <ctype.h>
#include <stdio.h>
#include <string.h>

static size_t my_strlen(const char *s) {
  size_t n = 0;
  while (s[n] != '\0') {
    n++;
  }
  return n;
}

static int my_strcmp(const char *a, const char *b) {
  while (*a != '\0' && *a == *b) {
    a++;
    b++;
  }
  return (unsigned char)*a - (unsigned char)*b;
}

static int is_palindrome(const char *s) {
  int i = 0;
  int j = (int)strlen(s) - 1;
  while (i < j) {
    if (!isalnum((unsigned char)s[i])) {
      i++;
    } else if (!isalnum((unsigned char)s[j])) {
      j--;
    } else if (tolower((unsigned char)s[i]) != tolower((unsigned char)s[j])) {
      return 0;
    } else {
      i++;
      j--;
    }
  }
  return 1;
}

static int count_occurrences(const char *text, const char *pattern) {
  int count = 0;
  const char *p = text;
  while ((p = strstr(p, pattern)) != NULL) {
    count++;
    p++;
  }
  return count;
}

int main(void) {
  printf("%zu %zu\n", my_strlen("Programonic"), my_strlen(""));
  printf("%d %d\n", my_strcmp("apple", "apple") == 0, my_strcmp("apple", "banana") < 0);
  printf("%d %d\n", is_palindrome("A man, a plan, a canal: Panama"), is_palindrome("hello"));
  printf("%d\n", count_occurrences("abababa", "aba"));
  return 0;
}

C dynamic programming: longest common subsequence

Fill a table of subproblem answers to find the longest sequence that two strings share.

What is the LCS length of ABC and DEF?

Reveal answer and reasoning

0, because the strings have no character in common.

Review lesson →Open compiler

Show starting example

#include <stdio.h>
#include <string.h>

int main(void) {
  const char *a = "AGGTAB";
  const char *b = "GXTXAYB";
  int n = (int)strlen(a);
  int m = (int)strlen(b);
  int table[8][9] = {{0}};

  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      if (a[i - 1] == b[j - 1]) {
        table[i][j] = table[i - 1][j - 1] + 1;
      } else if (table[i - 1][j] >= table[i][j - 1]) {
        table[i][j] = table[i - 1][j];
      } else {
        table[i][j] = table[i][j - 1];
      }
    }
  }
  printf("LCS length: %d\n", table[n][m]);

  char result[8];
  int length = table[n][m];
  result[length] = '\0';
  int i = n, j = m;
  while (i > 0 && j > 0) {
    if (a[i - 1] == b[j - 1]) {
      result[--length] = a[i - 1];
      i--;
      j--;
    } else if (table[i - 1][j] >= table[i][j - 1]) {
      i--;
    } else {
      j--;
    }
  }
  printf("LCS: %s\n", result);
  return 0;
}

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

Count comparisons to see how the cost of one algorithm depends on the input it receives.

What is the average number of comparisons for n = 100?

Reveal answer and reasoning

(100 + 1) / 2 = 50.5 comparisons when every item is equally likely.

Review lesson →Open compiler

Show starting example

#include <stdio.h>

static int comparisons = 0;

static int linear_search(const int *values, int n, int target) {
  for (int i = 0; i < n; i++) {
    comparisons++;
    if (values[i] == target) {
      return i;
    }
  }
  return -1;
}

int main(void) {
  int values[] = {7, 3, 9, 1, 5, 8, 2, 6};
  int n = (int)(sizeof values / sizeof values[0]);

  comparisons = 0;
  linear_search(values, n, 7);
  printf("best case: %d\n", comparisons);

  comparisons = 0;
  linear_search(values, n, 6);
  printf("worst case, last item: %d\n", comparisons);

  comparisons = 0;
  linear_search(values, n, 100);
  printf("absent: %d\n", comparisons);

  int total = 0;
  for (int i = 0; i < n; i++) {
    comparisons = 0;
    linear_search(values, n, values[i]);
    total += comparisons;
  }
  printf("average over present items: %.1f\n", (double)total / n);
  return 0;
}

C: amortized cost of a growing array

Double the capacity of a malloc'd array when it fills, and count the copies made.

How many copies are needed for 8 appends?

Reveal answer and reasoning

7 copies (1 + 2 + 4), which is again fewer than the number of appends.

Review lesson →Open compiler

Show starting example

#include <stdio.h>
#include <stdlib.h>

typedef struct {
  int *data;
  size_t size;
  size_t capacity;
  long copies;
} IntList;

static void add(IntList *list, int value) {
  if (list->size == list->capacity) {
    size_t bigger = list->capacity == 0 ? 1 : list->capacity * 2;
    int *grown = malloc(bigger * sizeof *grown);
    if (grown == NULL) {
      exit(1);
    }
    for (size_t i = 0; i < list->size; i++) {
      grown[i] = list->data[i];
      list->copies++;
    }
    free(list->data);
    list->data = grown;
    list->capacity = bigger;
  }
  list->data[list->size++] = value;
}

int main(void) {
  IntList list = {NULL, 0, 0, 0};
  for (int i = 1; i <= 16; i++) {
    add(&list, i);
  }
  printf("appends=16 copies=%ld\n", list.copies);
  printf("copies per append=%.4f\n", (double)list.copies / 16);
  free(list.data);
  return 0;
}

C: a hash index with chaining

Store keys in buckets of linked lists and see how collisions lengthen a lookup.

What is the load factor of this table?

Reveal answer and reasoning

7 keys in 8 buckets gives a load factor of 7 / 8 = 0.875.

Review lesson →Open compiler

Show starting example

#include <stdio.h>
#include <stdlib.h>

#define BUCKETS 8

typedef struct Node {
  int key;
  struct Node *next;
} Node;

static Node *table[BUCKETS];

static void insert(int key) {
  Node *node = malloc(sizeof *node);
  if (node == NULL) {
    exit(1);
  }
  node->key = key;
  node->next = table[key % BUCKETS];
  table[key % BUCKETS] = node;
}

static int lookup(int key, int *comparisons) {
  *comparisons = 0;
  for (Node *n = table[key % BUCKETS]; n != NULL; n = n->next) {
    (*comparisons)++;
    if (n->key == key) {
      return 1;
    }
  }
  return 0;
}

int main(void) {
  int keys[] = {3, 11, 19, 5, 13, 21, 7};
  for (int i = 0; i < 7; i++) {
    insert(keys[i]);
  }

  for (int b = 0; b < BUCKETS; b++) {
    int length = 0;
    for (Node *n = table[b]; n != NULL; n = n->next) {
      length++;
    }
    if (length > 0) {
      printf("bucket %d holds %d key(s)\n", b, length);
    }
  }

  int probes[] = {19, 3, 4, 27};
  for (int i = 0; i < 4; i++) {
    int comparisons;
    int found = lookup(probes[i], &comparisons);
    printf("lookup %d: %s after %d comparison(s)\n", probes[i], found ? "found" : "not found", comparisons);
  }

  for (int b = 0; b < BUCKETS; b++) {
    Node *n = table[b];
    while (n != NULL) {
      Node *next = n->next;
      free(n);
      n = next;
    }
  }
  return 0;
}

C: a sorted index and range queries with lower_bound

Use binary search on a sorted array to find the first key at or above a value and read a range from there.

What does lower_bound(ages, n, 100) return?

Reveal answer and reasoning

6, which is n: no key is at least 100, so the position is one past the last element.

Review lesson →Open compiler

Show starting example

#include <stdio.h>

static int lower_bound(const int *a, int n, int key) {
  int lo = 0;
  int hi = n;
  while (lo < hi) {
    int mid = lo + (hi - lo) / 2;
    if (a[mid] < key) {
      lo = mid + 1;
    } else {
      hi = mid;
    }
  }
  return lo;
}

int main(void) {
  int ages[] = {24, 29, 31, 45, 52, 60};
  int n = (int)(sizeof ages / sizeof ages[0]);

  int start = lower_bound(ages, n, 25);
  int end = lower_bound(ages, n, 46);
  printf("ages in [25, 45]:");
  for (int i = start; i < end; i++) {
    printf(" %d", ages[i]);
  }
  printf(" (%d rows)\n", end - start);

  int first_over_50 = lower_bound(ages, n, 50);
  printf("first age >= 50: %d\n", ages[first_over_50]);
  return 0;
}

C: simulating round-robin scheduling

Give each job a fixed time slice in turn and compute the turnaround time of each.

How many time slices does this schedule use?

Reveal answer and reasoning

Six slices: P1 uses 3, P2 uses 2, and P3 uses 1.

Review lesson →Open compiler

Show starting example

#include <stdio.h>

int main(void) {
  int remaining[] = {5, 3, 1};
  int finish[] = {0, 0, 0};
  int jobs = 3;
  int quantum = 2;
  int clock = 0;
  int unfinished = jobs;

  while (unfinished > 0) {
    for (int i = 0; i < jobs; i++) {
      if (remaining[i] == 0) {
        continue;
      }
      int run = remaining[i] < quantum ? remaining[i] : quantum;
      clock += run;
      remaining[i] -= run;
      printf("t=%d P%d ran %d\n", clock, i + 1, run);
      if (remaining[i] == 0) {
        finish[i] = clock;
        unfinished--;
      }
    }
  }

  double total = 0;
  for (int i = 0; i < jobs; i++) {
    printf("P%d turnaround %d\n", i + 1, finish[i]);
    total += finish[i];
  }
  printf("average turnaround %.2f\n", total / jobs);
  return 0;
}

C: protecting a shared counter with a POSIX mutex

Run two threads that increment one counter and use pthread_mutex_lock so no update is lost.

What would happen without the mutex?

Reveal answer and reasoning

The result would usually be below 200000 and would change from run to run, because updates are lost.

Review lesson →Open compiler

Show starting example

#include <pthread.h>
#include <stdio.h>

static int counter = 0;
static pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;

static void *work(void *arg) {
  (void)arg;
  for (int i = 0; i < 100000; i++) {
    pthread_mutex_lock(&lock);
    counter++;
    pthread_mutex_unlock(&lock);
  }
  return NULL;
}

int main(void) {
  pthread_t a, b;
  pthread_create(&a, NULL, work, NULL);
  pthread_create(&b, NULL, work, NULL);
  pthread_join(a, NULL);
  pthread_join(b, NULL);
  printf("counter=%d\n", counter);
  return 0;
}

C: the CRC-32 frame check sequence

Compute the cyclic redundancy check used by Ethernet and detect a single flipped bit.

Why does the receiver recompute the CRC instead of comparing messages?

Reveal answer and reasoning

The receiver has no second copy of the message to compare with. It checks that the received data is consistent with the CRC that arrived with it.

Review lesson →Open compiler

Show starting example

#include <stdint.h>
#include <stdio.h>
#include <string.h>

static uint32_t crc32(const unsigned char *data, size_t n) {
  uint32_t crc = 0xFFFFFFFFu;
  for (size_t i = 0; i < n; i++) {
    crc ^= data[i];
    for (int k = 0; k < 8; k++) {
      crc = (crc >> 1) ^ (0xEDB88320u & (0u - (crc & 1u)));
    }
  }
  return ~crc;
}

int main(void) {
  unsigned char frame[] = "123456789";
  size_t n = strlen((const char *)frame);
  printf("crc32 = %08X\n", (unsigned)crc32(frame, n));

  frame[3] ^= 0x01;
  printf("after one flipped bit = %08X\n", (unsigned)crc32(frame, n));
  return 0;
}

C: network, broadcast, and host count of a CIDR block

Use shifts and masks on a 32-bit address to describe a subnet.

How many usable hosts does a /26 contain?

Reveal answer and reasoning

2^6 − 2 = 62 usable host addresses.

Review lesson →Open compiler

Show starting example

#include <stdint.h>
#include <stdio.h>

static void print_ip(const char *label, uint32_t ip) {
  printf("%s %u.%u.%u.%u\n", label, (unsigned)(ip >> 24), (unsigned)((ip >> 16) & 255u),
         (unsigned)((ip >> 8) & 255u), (unsigned)(ip & 255u));
}

int main(void) {
  unsigned a, b, c, d;
  int prefix;
  sscanf("172.16.5.130/20", "%u.%u.%u.%u/%d", &a, &b, &c, &d, &prefix);

  uint32_t ip = (a << 24) | (b << 16) | (c << 8) | d;
  uint32_t mask = prefix == 0 ? 0u : 0xFFFFFFFFu << (32 - prefix);
  uint32_t network = ip & mask;
  uint32_t broadcast = network | ~mask;

  print_ip("mask     ", mask);
  print_ip("network  ", network);
  print_ip("broadcast", broadcast);
  printf("hosts     %u\n", (unsigned)((1u << (32 - prefix)) - 2u));
  return 0;
}

C: unit testing with a small macro

Report which checks pass and fail by printing the text of each expression.

How would you test that clamp handles low equal to high?

Reveal answer and reasoning

CHECK(clamp(7, 4, 4) == 4); with equal bounds every input must map to that single value.

Review lesson →Open compiler

Show starting example

#include <stdio.h>
#include <string.h>

static int failures = 0;

#define CHECK(cond)                      \
  do {                                   \
    if (cond) {                          \
      printf("PASS %s\n", #cond);        \
    } else {                             \
      printf("FAIL %s\n", #cond);        \
      failures++;                        \
    }                                    \
  } while (0)

static int clamp(int value, int low, int high) {
  if (value < low) return low;
  if (value > high) return high;
  return value;
}

static void reverse(char *text) {
  size_t n = strlen(text);
  for (size_t i = 0; i < n / 2; i++) {
    char tmp = text[i];
    text[i] = text[n - 1 - i];
    text[n - 1 - i] = tmp;
  }
}

int main(void) {
  CHECK(clamp(5, 0, 10) == 5);
  CHECK(clamp(-3, 0, 10) == 0);
  CHECK(clamp(99, 0, 10) == 10);

  char word[] = "stressed";
  reverse(word);
  CHECK(strcmp(word, "desserts") == 0);

  printf("failures: %d\n", failures);
  return failures != 0;
}

C: the strategy pattern with function pointers

Choose behaviour at run time by passing a function to qsort, without changing the sorting code.

How would you sort by absolute value?

Reveal answer and reasoning

Write a comparison function that compares abs(a) with abs(b), and pass it to qsort in place of the other strategies.

Review lesson →Open compiler

Show starting example

#include <stdio.h>
#include <stdlib.h>

static int ascending(const void *x, const void *y) {
  int a = *(const int *)x;
  int b = *(const int *)y;
  return (a > b) - (a < b);
}

static int descending(const void *x, const void *y) {
  return ascending(y, x);
}

static int by_last_digit(const void *x, const void *y) {
  int a = *(const int *)x % 10;
  int b = *(const int *)y % 10;
  return (a > b) - (a < b);
}

static void show(const char *label, const int *values, int n) {
  printf("%s:", label);
  for (int i = 0; i < n; i++) {
    printf(" %d", values[i]);
  }
  printf("\n");
}

int main(void) {
  int original[] = {42, 7, 19, 33, 8};
  int n = (int)(sizeof original / sizeof original[0]);
  int (*strategies[])(const void *, const void *) = {ascending, descending, by_last_digit};
  const char *names[] = {"ascending", "descending", "by last digit"};

  for (int s = 0; s < 3; s++) {
    int copy[5];
    for (int i = 0; i < n; i++) {
      copy[i] = original[i];
    }
    qsort(copy, (size_t)n, sizeof copy[0], strategies[s]);
    show(names[s], copy, n);
  }
  return 0;
}

C: preventing buffer overflows with snprintf

Copy text into a fixed buffer without writing past its end, and detect truncation.

Why compare needed with capacity using < and not <=?

Reveal answer and reasoning

The terminating zero needs one byte, so a text of length capacity would need capacity + 1 bytes in total and does not fit.

Review lesson →Open compiler

Show starting example

#include <stdio.h>

static int copy_name(char *out, size_t capacity, const char *name) {
  int needed = snprintf(out, capacity, "%s", name);
  return needed >= 0 && (size_t)needed < capacity;
}

int main(void) {
  char buffer[8];

  if (copy_name(buffer, sizeof buffer, "Ada")) {
    printf("stored: %s\n", buffer);
  }

  if (!copy_name(buffer, sizeof buffer, "Programonic")) {
    printf("rejected: 11 characters do not fit in %zu bytes\n", sizeof buffer);
    printf("buffer still holds: %s\n", buffer);
  }
  return 0;
}

C: validating numeric input with strtol

Accept only text that is entirely a number in the allowed range, and reject everything else.

Why does '80a' fail?

Reveal answer and reasoning

strtol stops at the letter a, so end does not point to the terminating zero, which means part of the text was not a number.

Review lesson →Open compiler

Show starting example

#include <ctype.h>
#include <errno.h>
#include <stdio.h>
#include <stdlib.h>

static int parse_port(const char *text, int *out) {
  if (text[0] == '\0' || isspace((unsigned char)text[0])) {
    return 0;
  }
  char *end;
  errno = 0;
  long value = strtol(text, &end, 10);
  if (*end != '\0' || errno == ERANGE || value < 1 || value > 65535) {
    return 0;
  }
  *out = (int)value;
  return 1;
}

int main(void) {
  const char *inputs[] = {"8080", "0", "70000", "80a", "", " 22", "99999999999999999999"};
  for (int i = 0; i < 7; i++) {
    int port;
    if (parse_port(inputs[i], &port)) {
      printf("'%s' -> %d\n", inputs[i], port);
    } else {
      printf("'%s' -> rejected\n", inputs[i]);
    }
  }
  return 0;
}

C: why a one-time pad key must never be reused

XOR two messages with the same key and show that the key cancels out and leaks information.

How do modern stream ciphers avoid key reuse?

Reveal answer and reasoning

They combine the key with a unique nonce for every message, so the keystream is never the same twice. Reusing a key and nonce pair is still a fatal mistake.

Review lesson →Open compiler

Show starting example

#include <stdio.h>
#include <string.h>

int main(void) {
  unsigned char p1[] = "ATTACK AT DAWN";
  unsigned char p2[] = "ATTACK AT DUSK";
  unsigned char key[] = {0x5A, 0x13, 0xC7, 0x88, 0x21, 0x6E, 0x90, 0x04, 0xB3, 0x7F, 0x42, 0xD1, 0x39, 0xEE};
  size_t n = strlen((const char *)p1);

  unsigned char c1[14], c2[14];
  for (size_t i = 0; i < n; i++) {
    c1[i] = p1[i] ^ key[i];
    c2[i] = p2[i] ^ key[i];
  }

  int cancelled = 1;
  for (size_t i = 0; i < n; i++) {
    if ((c1[i] ^ c2[i]) != (p1[i] ^ p2[i])) {
      cancelled = 0;
    }
  }
  printf("key cancels out: %d\n", cancelled);

  char recovered[15];
  for (size_t i = 0; i < n; i++) {
    recovered[i] = (char)(c1[i] ^ c2[i] ^ p1[i]);
  }
  recovered[n] = '\0';
  printf("recovered second message: %s\n", recovered);
  return 0;
}

C: splitting a sum across threads without sharing

Give each thread its own range and result slot, then combine the results after joining.

Where would you add a lock if all threads added to one shared total?

Reveal answer and reasoning

Around the update of the shared total, or better, avoid the shared total as this program does.

Review lesson →Open compiler

Show starting example

#include <pthread.h>
#include <stdio.h>

typedef struct {
  int from;
  int to;
  long sum;
} Job;

static void *work(void *arg) {
  Job *job = arg;
  job->sum = 0;
  for (int i = job->from; i <= job->to; i++) {
    job->sum += i;
  }
  return NULL;
}

int main(void) {
  Job jobs[4] = {{1, 250, 0}, {251, 500, 0}, {501, 750, 0}, {751, 1000, 0}};
  pthread_t threads[4];

  for (int t = 0; t < 4; t++) {
    pthread_create(&threads[t], NULL, work, &jobs[t]);
  }

  long total = 0;
  for (int t = 0; t < 4; t++) {
    pthread_join(threads[t], NULL);
    printf("part %d: %ld\n", t + 1, jobs[t].sum);
    total += jobs[t].sum;
  }
  printf("total: %ld\n", total);
  return 0;
}

C: the speed-up limit of Amdahl's law

Compute the best possible speed-up for a program in which only part of the work can run in parallel.

What is the limit of the speed-up if 95% of the program is parallelizable?

Reveal answer and reasoning

1 / 0.05 = 20 times, however many processors are used.

Review lesson →Open compiler

Show starting example

#include <stdio.h>

static double speedup(double parallel_fraction, int processors) {
  return 1.0 / ((1.0 - parallel_fraction) + parallel_fraction / processors);
}

int main(void) {
  double p = 0.9;
  int counts[] = {1, 2, 4, 8, 16, 1000000};
  for (int i = 0; i < 6; i++) {
    printf("%7d processors: %.2fx\n", counts[i], speedup(p, counts[i]));
  }
  printf("limit: %.2fx\n", 1.0 / (1.0 - p));
  return 0;
}

C: breadth-first search on a grid with an array queue

Find the length of the shortest path through a maze using a queue stored in a plain array.

What is dist for a cell that cannot be reached?

Reveal answer and reasoning

It stays -1, which tells the program that no path exists.

Review lesson →Open compiler

Show starting example

#include <stdio.h>

#define ROWS 3
#define COLS 4

int main(void) {
  const char *grid[ROWS] = {"S.#.", "..#.", "...G"};
  int dist[ROWS][COLS];
  for (int r = 0; r < ROWS; r++) {
    for (int c = 0; c < COLS; c++) {
      dist[r][c] = -1;
    }
  }

  int queue_r[ROWS * COLS], queue_c[ROWS * COLS];
  int head = 0, tail = 0;
  queue_r[tail] = 0;
  queue_c[tail] = 0;
  tail++;
  dist[0][0] = 0;

  int dr[] = {1, -1, 0, 0};
  int dc[] = {0, 0, 1, -1};
  while (head < tail) {
    int r = queue_r[head];
    int c = queue_c[head];
    head++;
    for (int k = 0; k < 4; k++) {
      int nr = r + dr[k];
      int nc = c + dc[k];
      if (nr < 0 || nr >= ROWS || nc < 0 || nc >= COLS) {
        continue;
      }
      if (grid[nr][nc] == '#' || dist[nr][nc] != -1) {
        continue;
      }
      dist[nr][nc] = dist[r][c] + 1;
      queue_r[tail] = nr;
      queue_c[tail] = nc;
      tail++;
    }
  }
  printf("shortest path to G: %d\n", dist[2][3]);
  printf("cells reached: %d\n", tail);
  return 0;
}

C: game search with negamax and a memo table

Solve a take-away game and count how many positions memoization saves.

Which pile sizes are losing for the player to move?

Reveal answer and reasoning

The multiples of four. Whatever the player takes, the opponent takes the complement to four and keeps the pile a multiple of four.

Review lesson →Open compiler

Show starting example

#include <stdio.h>

static long calls = 0;
static int memo[64];
static int known[64];

static int negamax(int sticks) {
  calls++;
  if (sticks == 0) {
    return -1;
  }
  int best = -1;
  for (int take = 1; take <= 3 && take <= sticks; take++) {
    int value = -negamax(sticks - take);
    if (value > best) {
      best = value;
    }
  }
  return best;
}

static int negamax_memo(int sticks) {
  calls++;
  if (sticks == 0) {
    return -1;
  }
  if (known[sticks]) {
    return memo[sticks];
  }
  int best = -1;
  for (int take = 1; take <= 3 && take <= sticks; take++) {
    int value = -negamax_memo(sticks - take);
    if (value > best) {
      best = value;
    }
  }
  known[sticks] = 1;
  memo[sticks] = best;
  return best;
}

int main(void) {
  for (int n = 1; n <= 8; n++) {
    printf("%d:%s ", n, negamax(n) == 1 ? "win" : "lose");
  }
  printf("\n");

  calls = 0;
  int plain = negamax(20);
  long plain_calls = calls;

  calls = 0;
  int cached = negamax_memo(20);
  long memo_calls = calls;

  printf("n=20 same answer: %d\n", plain == cached);
  printf("calls: plain %ld, memoized %ld\n", plain_calls, memo_calls);
  return 0;
}

C: forward chaining with bit sets

Store facts as bits of an integer and apply if-then rules with bitwise operations.

What is derived if cold is not a starting fact?

Reveal answer and reasoning

Only wet is derived, because ice needs both wet and cold.

Review lesson →Open compiler

Show starting example

#include <stdio.h>

enum { RAIN, COLD, WET, ICE, SLIPPERY, CAREFUL, FACT_COUNT };

typedef struct {
  unsigned premises;
  unsigned conclusion;
} Rule;

#define BIT(f) (1u << (f))

int main(void) {
  const char *names[FACT_COUNT] = {"rain", "cold", "wet", "ice", "slippery", "careful"};
  Rule rules[] = {
    {BIT(RAIN), BIT(WET)},
    {BIT(WET) | BIT(COLD), BIT(ICE)},
    {BIT(ICE), BIT(SLIPPERY)},
    {BIT(SLIPPERY), BIT(CAREFUL)},
  };
  unsigned facts = BIT(RAIN) | BIT(COLD);

  int changed = 1;
  while (changed) {
    changed = 0;
    for (int i = 0; i < 4; i++) {
      if ((facts & rules[i].premises) == rules[i].premises && !(facts & rules[i].conclusion)) {
        facts |= rules[i].conclusion;
        for (int f = 0; f < FACT_COUNT; f++) {
          if (rules[i].conclusion == BIT(f)) {
            printf("derived %s\n", names[f]);
          }
        }
        changed = 1;
      }
    }
  }

  printf("known:");
  for (int f = 0; f < FACT_COUNT; f++) {
    if (facts & BIT(f)) {
      printf(" %s", names[f]);
    }
  }
  printf("\n");
  return 0;
}

C: resolution refutation with clauses as bit masks

Represent each clause by two masks, one for positive and one for negative literals, and resolve until a contradiction appears.

What changes if the query is A?

Reveal answer and reasoning

The empty clause is never derived, because the knowledge base has a model with A false, so the loop ends with KB entails C: 0 for that query.

Review lesson →Open compiler

Show starting example

#include <stdio.h>

typedef struct {
  unsigned pos;
  unsigned neg;
} Clause;

#define A 1u
#define B 2u
#define C 4u

static void show(Clause c) {
  const char *names[] = {"A", "B", "C"};
  int first = 1;
  if (c.pos == 0 && c.neg == 0) {
    printf("empty");
  }
  for (int v = 0; v < 3; v++) {
    if (c.pos & (1u << v)) {
      printf("%s%s", first ? "" : " v ", names[v]);
      first = 0;
    }
    if (c.neg & (1u << v)) {
      printf("%s~%s", first ? "" : " v ", names[v]);
      first = 0;
    }
  }
}

static int same(Clause x, Clause y) {
  return x.pos == y.pos && x.neg == y.neg;
}

int main(void) {
  Clause clauses[64] = {
    {A | B, 0},
    {C, A},
    {C, B},
    {0, C},
  };
  int count = 4;

  for (int i = 1; i < count; i++) {
    for (int j = 0; j < i; j++) {
      for (int v = 0; v < 3; v++) {
        unsigned bit = 1u << v;
        int opposite = ((clauses[i].pos & bit) && (clauses[j].neg & bit)) ||
                       ((clauses[i].neg & bit) && (clauses[j].pos & bit));
        if (!opposite) {
          continue;
        }
        Clause r;
        r.pos = (clauses[i].pos | clauses[j].pos) & ~bit;
        r.neg = (clauses[i].neg | clauses[j].neg) & ~bit;
        if (r.pos & r.neg) {
          continue;
        }
        int seen = 0;
        for (int k = 0; k < count; k++) {
          if (same(clauses[k], r)) {
            seen = 1;
          }
        }
        if (seen) {
          continue;
        }
        clauses[count++] = r;
        printf("derived ");
        show(r);
        printf("\n");
        if (r.pos == 0 && r.neg == 0) {
          printf("KB entails C: 1\n");
          return 0;
        }
      }
    }
  }
  printf("KB entails C: 0\n");
  return 0;
}

C: linear regression with gradient descent

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

What value 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

#include <stdio.h>

int main(void) {
  double x[] = {0, 1, 2, 3, 4};
  double y[] = {-2, 1, 4, 7, 10};
  int n = 5;
  double w = 0.0, b = 0.0, rate = 0.05;

  for (int epoch = 0; epoch < 5000; epoch++) {
    double gw = 0.0, gb = 0.0;
    for (int i = 0; i < n; i++) {
      double error = w * x[i] + b - y[i];
      gw += 2.0 * error * x[i] / n;
      gb += 2.0 * error / n;
    }
    w -= rate * gw;
    b -= rate * gb;
  }
  printf("w=%.2f b=%.2f\n", w, b);
  printf("prediction for x=10: %.2f\n", w * 10 + b);
  return 0;
}

C: k-nearest-neighbors classification

Sort training points by distance to a query and let the k closest vote.

How would you handle three classes?

Reveal answer and reasoning

Keep a vote count per class, for example in an array indexed by label, and return the label with the largest count.

Review lesson →Open compiler

Show starting example

#include <math.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct {
  double x, y;
  char label;
  double dist;
} Point;

static int by_distance(const void *p, const void *q) {
  double a = ((const Point *)p)->dist;
  double b = ((const Point *)q)->dist;
  return (a > b) - (a < b);
}

static char classify(const Point *train, int n, double qx, double qy, int k) {
  Point copy[8];
  for (int i = 0; i < n; i++) {
    copy[i] = train[i];
    copy[i].dist = hypot(copy[i].x - qx, copy[i].y - qy);
  }
  qsort(copy, (size_t)n, sizeof copy[0], by_distance);

  int votes_a = 0, votes_b = 0;
  for (int i = 0; i < k; i++) {
    if (copy[i].label == 'A') {
      votes_a++;
    } else {
      votes_b++;
    }
  }
  return votes_a > votes_b ? 'A' : 'B';
}

int main(void) {
  Point train[] = {
    {1, 1, 'A', 0}, {1, 2, 'A', 0}, {2, 1, 'A', 0},
    {6, 6, 'B', 0}, {7, 6, 'B', 0}, {6, 7, 'B', 0},
  };
  printf("(5,5) -> %c\n", classify(train, 6, 5, 5, 3));
  printf("(2,2) -> %c\n", classify(train, 6, 2, 2, 3));
  printf("(3,3) with k=5 -> %c\n", classify(train, 6, 3, 3, 5));
  return 0;
}

C: training a perceptron until it makes no mistakes

Use integer weights and the perceptron rule to learn the AND function.

What happens if you change the targets to {0, 1, 1, 0}?

Reveal answer and reasoning

The loop never terminates, because no weights can separate the XOR cases with a single line.

Review lesson →Open compiler

Show starting example

#include <stdio.h>

int main(void) {
  int inputs[4][2] = {{0, 0}, {0, 1}, {1, 0}, {1, 1}};
  int targets[4] = {0, 0, 0, 1};
  int w1 = 0, w2 = 0, bias = 0;

  int epochs = 0;
  int mistakes = 1;
  while (mistakes > 0) {
    mistakes = 0;
    for (int i = 0; i < 4; i++) {
      int sum = w1 * inputs[i][0] + w2 * inputs[i][1] + bias;
      int output = sum > 0 ? 1 : 0;
      int error = targets[i] - output;
      if (error != 0) {
        w1 += error * inputs[i][0];
        w2 += error * inputs[i][1];
        bias += error;
        mistakes++;
      }
    }
    epochs++;
  }
  printf("epochs: %d\n", epochs);
  printf("weights: w1=%d w2=%d bias=%d\n", w1, w2, bias);
  for (int i = 0; i < 4; i++) {
    int sum = w1 * inputs[i][0] + w2 * inputs[i][1] + bias;
    printf("%d AND %d = %d\n", inputs[i][0], inputs[i][1], sum > 0 ? 1 : 0);
  }
  return 0;
}

C: softmax and why the largest score is subtracted

Convert scores to probabilities and show that the naive formula overflows for large scores.

What does softmax give for equal scores?

Reveal answer and reasoning

Equal probabilities: with four equal scores each probability is 0.25.

Review lesson →Open compiler

Show starting example

#include <math.h>
#include <stdio.h>

static void softmax_naive(const double *z, double *out, int n) {
  double total = 0.0;
  for (int i = 0; i < n; i++) {
    out[i] = exp(z[i]);
    total += out[i];
  }
  for (int i = 0; i < n; i++) {
    out[i] /= total;
  }
}

static void softmax_stable(const double *z, double *out, int n) {
  double largest = z[0];
  for (int i = 1; i < n; i++) {
    if (z[i] > largest) {
      largest = z[i];
    }
  }
  double total = 0.0;
  for (int i = 0; i < n; i++) {
    out[i] = exp(z[i] - largest);
    total += out[i];
  }
  for (int i = 0; i < n; i++) {
    out[i] /= total;
  }
}

int main(void) {
  double small[3] = {2.0, 1.0, 0.1};
  double out[3];
  softmax_stable(small, out, 3);
  printf("stable: %.3f %.3f %.3f\n", out[0], out[1], out[2]);
  softmax_naive(small, out, 3);
  printf("naive:  %.3f %.3f %.3f\n", out[0], out[1], out[2]);

  double big[2] = {1000.0, 1001.0};
  double big_out[2];
  softmax_naive(big, big_out, 2);
  printf("naive on large scores is NaN: %s\n", isnan(big_out[0]) ? "yes" : "no");
  softmax_stable(big, big_out, 2);
  printf("stable on large scores: %.3f %.3f\n", big_out[0], big_out[1]);
  return 0;
}

C: smoothing noise with a box-blur convolution

Average each 3×3 neighbourhood of a small image to reduce an isolated bright pixel.

What is the blurred value if the bright pixel were on the border instead?

Reveal answer and reasoning

Windows that include it would sum 8·10 + 100 as before, but fewer windows contain a border pixel, so fewer outputs change.

Review lesson →Open compiler

Show starting example

#include <stdio.h>

#define N 5

int main(void) {
  int image[N][N];
  for (int r = 0; r < N; r++) {
    for (int c = 0; c < N; c++) {
      image[r][c] = 10;
    }
  }
  image[2][2] = 100;

  for (int r = 1; r < N - 1; r++) {
    for (int c = 1; c < N - 1; c++) {
      int sum = 0;
      for (int kr = -1; kr <= 1; kr++) {
        for (int kc = -1; kc <= 1; kc++) {
          sum += image[r + kr][c + kc];
        }
      }
      printf("%4d", sum / 9);
    }
    printf("\n");
  }
  return 0;
}

C: grayscale histogram and a global threshold

Count how many pixels have each brightness level and separate dark from bright pixels at the mean.

How many bins would an exact 256-level histogram need?

Reveal answer and reasoning

256 bins, one for each possible 8-bit brightness value.

Review lesson →Open compiler

Show starting example

#include <stdio.h>

int main(void) {
  unsigned char image[4][4] = {
    {12, 20, 200, 210},
    {15, 25, 220, 205},
    {10, 30, 215, 230},
    {18, 22, 225, 240},
  };
  int bins[8] = {0};
  int total = 0;

  for (int r = 0; r < 4; r++) {
    for (int c = 0; c < 4; c++) {
      bins[image[r][c] / 32]++;
      total += image[r][c];
    }
  }
  int mean = total / 16;

  printf("histogram:");
  for (int b = 0; b < 8; b++) {
    printf(" %d", bins[b]);
  }
  printf("\nmean brightness: %d\n", mean);

  for (int r = 0; r < 4; r++) {
    for (int c = 0; c < 4; c++) {
      putchar(image[r][c] > mean ? '#' : '.');
    }
    putchar('\n');
  }
  return 0;
}

C Variables

C Arrays

C Pointers

C conditions, loops, and totals

C strings and null terminators

C functions and pointer parameters

C structures and records

C dynamic memory and ownership

C reading and writing text files

C bit manipulation and flags

C two-dimensional arrays

C macros versus inline functions

C array search with explicit length

C linked nodes and traversal

C array-based stacks and circular queues

C binary search and the standard bsearch

C sorting: bubble sort versus quicksort

C binary search trees with malloc and free

C string algorithms

C dynamic programming: longest common subsequence

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

C: amortized cost of a growing array

C: a hash index with chaining

C: a sorted index and range queries with lower_bound

C: simulating round-robin scheduling

C: protecting a shared counter with a POSIX mutex

C: the CRC-32 frame check sequence

C: network, broadcast, and host count of a CIDR block

C: unit testing with a small macro

C: the strategy pattern with function pointers

C: preventing buffer overflows with snprintf

C: validating numeric input with strtol

C: why a one-time pad key must never be reused

C: splitting a sum across threads without sharing

C: the speed-up limit of Amdahl's law

C: breadth-first search on a grid with an array queue

C: game search with negamax and a memo table

C: forward chaining with bit sets

C: resolution refutation with clauses as bit masks

C: linear regression with gradient descent

C: k-nearest-neighbors classification

C: training a perceptron until it makes no mistakes

C: softmax and why the largest score is subtracted

C: smoothing noise with a box-blur convolution

C: grayscale histogram and a global threshold