Notes on how things work.
Short explanations of ideas I enjoy, written in plain language. Most of them go with an experiment in the Engineering Lab, so you can read the idea and then try it.
Start here
- Operating Systems · 1 min readWhen more memory causes more page faultsWith FIFO page replacement, giving a program more frames can sometimes make it fault more, not less. Here's a small example you can run yourself.Read post
- Operating Systems · 1 min readFirst fit, best fit and worst fit: what actually changesThe same request can land in three different places depending on the strategy. A small example shows what each one picks and what it leaves behind.Read post
- Sorting · 1 min readSame result, different work: comparing sorting algorithmsEvery sorting algorithm gives the same sorted list. What changes is how much work it does to get there, and that is what the step-by-step view makes visible.Read post
Operating Systems15 posts
- FIFO page replacementThe simplest page replacement rule: when memory is full, the page that has been there longest leaves first.2 min
- LRU page replacementLRU removes the page that has not been used for the longest time, based on the idea that the recent past predicts the near future.2 min
- Optimal page replacementOptimal replacement removes the page that will not be needed for the longest time. It cannot be built for real, but it shows the best possible result.1 min
- First Come First Served (FCFS) schedulingFCFS runs processes in the order they arrive. It is fair in a simple way, but one long process can make everyone else wait.1 min
- Shortest Job First (SJF) schedulingSJF always runs the waiting process with the shortest burst time next. It lowers the average waiting time, but long processes may wait a long time.1 min
- Shortest Remaining Time First (SRTF) schedulingSRTF is the preemptive version of SJF. A newly arrived process can take the CPU if it needs less time than what the running process has left.1 min
- Round Robin (RR) schedulingRound Robin gives every process a short turn on the CPU, called a time quantum, and then sends it to the back of the queue.1 min
- Non-preemptive priority schedulingEvery process has a priority. When the CPU is free, the waiting process with the highest priority goes next and runs until it finishes.1 min
- Preemptive priority schedulingA process with a higher priority can interrupt a running process with a lower priority as soon as it arrives.1 min
- Highest Response Ratio Next (HRRN) schedulingHRRN favours short jobs but also rewards waiting, so long processes are not left behind forever.1 min
- First fit memory allocationFirst fit gives a request the first free gap that is big enough, then stops searching.1 min
- Best fit memory allocationBest fit picks the smallest gap that is big enough, so the leftover space is as small as possible.1 min
- Worst fit memory allocationWorst fit always takes the largest gap, hoping the leftover piece is still big enough to be useful.1 min
Sorting10 posts
- Bubble sortBubble sort repeatedly compares neighbouring items and swaps them if they are in the wrong order, so the largest values slowly rise to the end.1 min
- Selection sortSelection sort finds the smallest remaining value and moves it to the front, one position at a time.1 min
- Insertion sortInsertion sort builds a sorted list one item at a time, like sorting playing cards in your hand.1 min
- Merge sortMerge sort splits the list in halves, sorts each half and then merges them back together.1 min
- Quick sortQuick sort picks a pivot, puts smaller values on one side and bigger values on the other, then sorts each side.1 min
- Heap sortHeap sort turns the list into a heap, then repeatedly takes the largest value out and puts it at the end.1 min
- Counting sortCounting sort does not compare items at all. It counts how many times each value appears and rebuilds the list from the counts.1 min
- Radix sortRadix sort sorts numbers one digit at a time, starting from the last digit, using a stable sort at each step.1 min
- Shell sortShell sort is insertion sort with a head start: it first sorts items that are far apart, then gets closer and closer.1 min
Searching4 posts
- Linear searchLinear search checks every item from the start until it finds the target or reaches the end. It works on any list, sorted or not.1 min
- Binary searchBinary search needs a sorted list. It checks the middle item and throws away the half that cannot contain the target.1 min
- Jump searchJump search skips ahead in fixed-size blocks, then scans one block in order. It sits between linear and binary search.1 min
- Interpolation searchInterpolation search guesses where the target should be, based on its value, like looking for a name near the end of a phone book.2 min
Graphs8 posts
- Breadth-first search (BFS)BFS explores a graph level by level, visiting everything one step away before anything two steps away.1 min
- Depth-first search (DFS)DFS goes as deep as it can along one path before backing up and trying another.1 min
- Dijkstra's algorithmDijkstra's algorithm finds the shortest route from one node to all the others when edge weights are never negative.1 min
- The Bellman-Ford algorithmBellman-Ford finds shortest paths even when some edges have negative weights, and it can detect a negative cycle.1 min
- The Floyd-Warshall algorithmFloyd-Warshall finds the shortest distance between every pair of nodes at once.1 min
- Prim's algorithmPrim's algorithm grows a minimum spanning tree from one node, always adding the cheapest edge that reaches a new node.1 min
- Kruskal's algorithmKruskal's algorithm builds a minimum spanning tree by taking the cheapest edges first and skipping any edge that would form a loop.1 min
- Topological sortTopological sort puts the nodes of a directed graph in an order where every edge points forward, like a valid order for tasks that depend on each other.1 min