Part IV: Algorithms and Problem Solving

In which we return to the heart of Wirth's vision, prove that algorithms are not abstract theory but practical tools, and discover that thinking carefully about a problem is worth more than any amount of fast typing.

Algorithms + Data Structures = Programs.

We have quoted this sentence before. Now we live it.

Parts I through III gave you the full Pascal language — procedural foundations, data structures, object-oriented design. You can write programs that are well-organized, type-safe, persistent, and robust. But there is a difference between a program that works and a program that works well. A linear search through ten thousand transactions takes ten thousand comparisons. A binary search takes fourteen. A bubble sort of Rosa's expense history takes, in the worst case, fifty million operations for ten thousand entries. A merge sort takes about a hundred and thirty thousand. These are not academic distinctions. They are the difference between software that responds instantly and software that freezes while the user stares at a spinning cursor.

Part IV teaches you to think algorithmically — to analyze problems, design solutions, measure their efficiency, and choose the right approach for the right situation. These five chapters cover the core of what computer science calls "algorithms and data structures," the subject that Wirth himself considered the intellectual center of programming.

What These Chapters Cover

Chapter 22 introduces recursion — the technique of solving a problem by solving smaller instances of the same problem. Recursion is not just a programming trick; it is a way of thinking that unlocks entire categories of problems. You will trace recursive calls on paper, understand the call stack, implement factorial and Fibonacci (and then understand why the naive Fibonacci is terrible), and build recursive solutions to real problems. Crypts of Pascalia uses recursion to generate its dungeon maps: each room can branch into sub-rooms, which can branch into sub-sub-rooms, creating a maze of arbitrary depth from a simple recursive procedure. Tomás encounters recursion when he tries to split a restaurant bill among friends who are themselves splitting sub-groups — a naturally recursive problem.

Chapter 23 covers searching and sorting — the most fundamental algorithms in computing. You will implement linear search, binary search, bubble sort, insertion sort, selection sort, merge sort, and quicksort. You will learn not just how they work, but when to use each one. Binary search requires sorted data but is logarithmically fast. Quicksort is fast on average but can degrade to quadratic time. Merge sort guarantees O(n log n) but needs extra memory. PennyWise benefits directly: Rosa's expense list can now be sorted by date, by amount, or by category, and searched by any field — operations that take milliseconds even on thousands of records.

Chapter 24 introduces trees — hierarchical data structures that model naturally hierarchical data. Binary trees, binary search trees, tree traversal (in-order, pre-order, post-order), and balanced trees all appear here. PennyWise gains a tree-based category system: "Food" contains "Groceries," "Restaurants," and "Coffee," each of which can have sub-categories. Tree traversal lets the program generate reports that show spending at any level of detail. GradeBook Pro uses a tree to represent its course hierarchy: department, course, section, student.

Chapter 25 covers graphs — the most general and powerful data structure in computer science. You will learn adjacency matrices and adjacency lists, breadth-first search, depth-first search, Dijkstra's shortest path, and topological sorting. Crypts of Pascalia's dungeon map is, at its heart, a graph — and graph algorithms let the game compute the shortest path from the player's current room to the exit, check whether the dungeon is fully connected, and detect cycles that would trap the player in an infinite loop.

Chapter 26 ties everything together with algorithm design strategies and complexity analysis. You will learn Big-O notation rigorously, understand amortized analysis, and study the major algorithm design paradigms: divide-and-conquer, greedy algorithms, and dynamic programming. A dynamic programming solution optimizes Tomás's budget allocation across spending categories — the classic knapsack problem, reframed as "how do I get the most value from a limited student budget?"

Why Pascal for Algorithms

There is a reason that Wirth wrote his algorithms textbook in Pascal, that Stanford's early CS curriculum used Pascal, and that many of the definitive algorithm illustrations in textbooks from the 1970s through the 1990s were in Pascal. The language's clarity makes algorithms visible.

Consider a linked-list insertion. In C, the operation is tangled up with pointer arithmetic, manual null checks, and malloc/free ceremonies that obscure the algorithmic logic. In Python, the operation is hidden behind list.append(), and the student never sees the pointer manipulation at all. In Pascal, the operation is explicit but clean: you allocate a new node with New, set its Data field, adjust the Next pointer, and the algorithm is right there on the page — no noise, no magic.

This transparency is not a historical accident. It is a design choice. Pascal was built to make computational thinking visible, and algorithms are where that visibility pays off most.

The PennyWise Algorithmic Upgrade

PennyWise enters Part IV as a well-designed OOP application. It leaves as an efficient one. The specific improvements:

  • Sorted transaction history using quicksort, with the ability to sort by any field via a comparator function.
  • Binary search for finding transactions by date or ID, replacing the linear scans of earlier versions.
  • Tree-based category hierarchy that lets Rosa drill down from "Living Expenses" to "Utilities" to "Electricity" — or zoom out to see the big picture.
  • Budget optimization using dynamic programming, suggesting how Tomás should allocate his monthly stipend across categories to maximize his quality-of-life function (a concept he defines, with some amusement, as a utility function over food, entertainment, and textbook purchases).

These are not toy demonstrations. They are the same algorithms that power the search bars, recommendation engines, and financial tools you use every day. The difference is that here, you build them yourself, understand how they work, and can modify them when the problem changes.

The Wirth Tradition

Niklaus Wirth believed that programming was a discipline of the mind — that the purpose of writing a program was not merely to produce a working artifact but to think clearly about a problem. Algorithms are where this belief is tested most seriously. A sorting algorithm is not just code; it is a proof that a sequence can be reordered efficiently. A graph traversal is not just a loop; it is a systematic exploration of all possibilities.

Part IV asks you to think the way Wirth thought: carefully, precisely, and with deep respect for the elegance of a well-chosen solution. The five chapters ahead are challenging. They are also, for many students, the most intellectually rewarding chapters in any programming textbook.

Sharpen your pencil. Algorithms require it — sometimes literally.

Chapters in This Part