Learning path
Systems programming
Understand typed values, memory, and classes with C and C++.
- 1
C
Learn memory, pointers, and efficient systems programming.
C Variables
Declare typed values.
C Arrays
Store a fixed sequence.
C Pointers
Work with memory addresses.
C conditions, loops, and totals
Combine a counted loop with an even-number condition.
C strings and null terminators
Traverse characters without reading beyond the string.
C functions and pointer parameters
Modify caller-owned values through valid addresses.
C structures and records
Group related fields into a typed record.
C dynamic memory and ownership
Allocate, check, use, and free a heap buffer.
C reading and writing text files
Write lines to a file with fprintf, read them back with fgets, and parse each line with sscanf.
C bit manipulation and flags
Set, clear, test, and toggle bits with &, |, ^, ~, and shifts, and count set bits.
C two-dimensional arrays
Store a matrix, transpose it, and multiply it with another one.
C macros versus inline functions
See how a macro evaluates its arguments more than once and why a function is safer.
C array search with explicit length
Search only within the supplied array bounds.
C linked nodes and traversal
Connect records with pointers and follow a chain.
C array-based stacks and circular queues
Build a fixed-capacity stack and a queue that wraps around the end of its array.
C binary search and the standard bsearch
Find a value in a sorted array in logarithmic time, by hand and with the library function.
C sorting: bubble sort versus quicksort
Implement two sorts, count their comparisons, and see why O(n log n) beats O(n²).
C binary search trees with malloc and free
Allocate tree nodes dynamically, traverse them in order, and release every node.
C string algorithms
Write strlen and strcmp by hand, check palindromes, and count occurrences with strstr.
C dynamic programming: longest common subsequence
Fill a table of subproblem answers to find the longest sequence that two strings share.
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.
C: amortized cost of a growing array
Double the capacity of a malloc'd array when it fills, and count the copies made.
C: a hash index with chaining
Store keys in buckets of linked lists and see how collisions lengthen a lookup.
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.
C: simulating round-robin scheduling
Give each job a fixed time slice in turn and compute the turnaround time of each.
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.
C: the CRC-32 frame check sequence
Compute the cyclic redundancy check used by Ethernet and detect a single flipped bit.
C: network, broadcast, and host count of a CIDR block
Use shifts and masks on a 32-bit address to describe a subnet.
C: unit testing with a small macro
Report which checks pass and fail by printing the text of each expression.
C: the strategy pattern with function pointers
Choose behaviour at run time by passing a function to qsort, without changing the sorting code.
C: preventing buffer overflows with snprintf
Copy text into a fixed buffer without writing past its end, and detect truncation.
C: validating numeric input with strtol
Accept only text that is entirely a number in the allowed range, and reject everything else.
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.
C: splitting a sum across threads without sharing
Give each thread its own range and result slot, then combine the results after joining.
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.
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.
C: game search with negamax and a memo table
Solve a take-away game and count how many positions memoization saves.
C: forward chaining with bit sets
Store facts as bits of an integer and apply if-then rules with bitwise operations.
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.
C: linear regression with gradient descent
Fit y = w·x + b by repeatedly stepping the parameters against the gradient of the mean squared error.
C: k-nearest-neighbors classification
Sort training points by distance to a query and let the k closest vote.
C: training a perceptron until it makes no mistakes
Use integer weights and the perceptron rule to learn the AND function.
C: softmax and why the largest score is subtracted
Convert scores to probabilities and show that the naive formula overflows for large scores.
C: smoothing noise with a box-blur convolution
Average each 3×3 neighbourhood of a small image to reduce an isolated bright pixel.
C: grayscale histogram and a global threshold
Count how many pixels have each brightness level and separate dark from bright pixels at the mean.
- 2
C++
Build fast applications with modern types and classes.
C++ Basics
Write and run a first program.
C++ conditions and range loops
Filter a sequence while accumulating a result.
C++ functions and references
Use a reference parameter to update a caller's value.
C++ recursive factorial
Trace recursive calls and their return values.
C++ strings and string streams
Use std::string, parse text with getline and istringstream, and convert between text and numbers.
C++ references, const, and auto
Pass large objects without copying, protect them with const, and let the compiler deduce types.
C++ lambdas and the standard algorithms
Sort, search, count, transform, and remove elements with algorithms and small anonymous functions.
C++ Classes
Group data and behavior.
C++ constructors and encapsulation
Initialize private state and expose a controlled interface.
C++ abstract classes and virtual dispatch
Invoke derived behavior through a base reference.
C++ composition and RAII
Let owned members manage their resources automatically.
C++ function templates
Reuse one type-checked algorithm for different types.
C++ inheritance and virtual functions
Call the right method through a base-class pointer, and see what slicing does.
C++ operator overloading
Give a Vec2 class natural arithmetic, comparison, and output operators.
C++ smart pointers and ownership
Use unique_ptr for single ownership, shared_ptr for shared ownership, and weak_ptr to observe.
C++ vectors and iterator invalidation
Grow a dynamic array and use checked access.
C++ binary search with lower_bound
Find an insertion position and check whether it is a match.
C++ stack and queue adapters
Compare LIFO and FIFO removal on the same values.
C++ ordered maps and frequencies
Count keys and traverse them in sorted order.
C++ linked lists with unique ownership
Build a node chain with automatic destruction.
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.
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.
C++ binary search tree traversals
Insert values into a BST and visit them depth-first and level by level.
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.
C++ graphs: BFS, DFS, and connected components
Store a graph as adjacency lists, visit it breadth-first and depth-first, and count its components.
C++: best, worst, and average case of linear search
Count comparisons to see that one algorithm can have different costs on different inputs.
C++: amortized cost of a growing array
Count the copies made by a doubling array to see why push_back is amortized constant time.
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.
C++: an ordered index with std::map
Answer range and nearest-key queries with lower_bound and upper_bound.
C++: page replacement with FIFO and LRU
Count page faults for two replacement policies and see Belady's anomaly.
C++: protecting shared data with std::mutex
Run two threads that increment one counter and use a lock to keep every update.
C++: the Internet checksum
Compute the 16-bit ones'-complement checksum used by IP, TCP, and UDP, and use it to detect corruption.
C++: forwarding with longest-prefix match
Pick the most specific route that matches a destination address, as a router does.
C++: a small unit-test harness
Check results and expected exceptions with a macro and a template, and report failures.
C++: the observer pattern with std::function
Notify any number of listeners without the publisher knowing what they do.
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.
C++: validating untrusted input with std::from_chars
Parse a port number strictly and reject anything that is not exactly a number in range.
C++: splitting a sum across std::async tasks
Run two halves of a computation concurrently and combine the results with futures.
C++: lock-free counting with std::atomic
Increment a shared counter from four threads without a mutex.
C++: A* search with a Manhattan-distance heuristic
Guide a shortest-path search with an estimate of the remaining distance.
C++: minimax with alpha-beta pruning
Search a game tree and skip branches that cannot change the result.
C++: entailment by enumerating models
Test whether a knowledge base entails a query by checking every truth assignment.
C++: backward chaining from a goal
Prove a goal by finding a rule that concludes it and then proving that rule's conditions.
C++: linear regression with gradient descent
Fit y = w·x + b by repeatedly moving the parameters against the gradient of the mean squared error.
C++: k-means clustering
Group unlabeled points by alternating between assigning points to centers and moving centers to the mean.
C++: a perceptron learns OR but not XOR
Train the same neuron on two gates and compare the accuracy it can reach.
C++: stable softmax and cross-entropy loss
Turn raw scores into probabilities, measure the loss, and avoid overflow.
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.
C++: grayscale conversion and thresholding
Convert color pixels to brightness with luminance weights and split them into foreground and background.