Thinking procedurally

Overview

Recall questions on decomposition of large problems, components of a problem and of a solution, top-down stepwise refinement and structure charts, the order of steps, sub-procedures and their interfaces, and cohesion and coupling.

What you need to know

Answer each one before you reveal it.

Questions from this subtopic

Each one with the model answer underneath.

1. 1

   What is decomposition, and why is it the first thing to do with a large problem?

   Model answer

   Decomposition is breaking a problem into smaller sub-problems, and continuing to break those down until each piece is small enough to be understood and solved on its own. It is the first move on a large problem for several reasons. A whole system cannot be held in one person's head, but a single component can. Small pieces can be tested individually, so when something fails you know where, whereas a fault in an undivided program could be anywhere. Pieces can be worked on by different people at the same time, provided the interfaces between them are agreed first. Pieces can be reused, since a well-separated component often turns out to be useful elsewhere. And progress becomes measurable, because you can say which parts are finished. The critical discipline is that decomposition is not just chopping the problem into arbitrary chunks: the parts should each do one coherent job and should interact through as narrow an interface as possible, otherwise you have the same complexity plus the overhead of the boundaries.

2. 2

   Decompose the problem of building an online cinema seat booking system.

   Model answer

   A sensible first-level decomposition: browsing and search, letting a user find films by title, date, certificate and cinema; showing selection, presenting the times available for a chosen film at a chosen venue; seat selection, presenting the seating plan for that showing with each seat marked available, held, sold or unusable, and letting the user pick; pricing, applying adult, child, concession and member rates, meal deals and discount codes; payment, taking the money through a provider and confirming it; ticket issue, producing a booking reference and a scannable ticket by email or in an app; account management, covering registration, sign-in, booking history and cancellation; and administration, covering scheduling films into screens, setting prices, and reporting on sales. Second-level decomposition of seat selection alone: retrieve the seating plan for the screen; retrieve the current status of each seat for that showing; render the plan; validate the user's chosen set, checking adjacency rules and that a wheelchair space is not taken by a standard booking; and place a temporary hold on the chosen seats with an expiry. That last piece is the one an inexperienced decomposition misses, and it is the hardest part of the whole system: without a hold with a timeout, two users can pay for the same seat in the seconds between selection and payment.

3. 3

   Decompose the problem of taking attendance in a school, from the point of view of someone writing the software.

   Model answer

   Data preparation: maintain the roll of pupils, the timetable of classes and the assignment of pupils to teaching groups, and derive from these the register that should exist for a given class at a given period. Capture: present the correct register to the right teacher at the right time, allow each pupil to be marked present, absent, late, or absent with an authorised reason, allow a note to be attached, and allow the register to be submitted and later amended with an audit trail. Reconciliation: combine registers across the day, detect a pupil marked present in period one and absent in period two without an intervening explanation, and detect registers not submitted. Following up: generate the first-day-of-absence contact to guardians, record the responses, and convert an unexplained absence to authorised or unauthorised. Reporting: attendance percentages per pupil, group and year, persistent absence flags, and the returns required by the local authority. Access control cuts across all of it: a teacher sees their own classes, a head of year sees a year group, and an administrator sees everything. Notice that capture, the part a student would start with because it is the visible screen, is a small fraction of the problem, and that following up is where most of the real complexity and most of the value lie.

4. 4

   What is the difference between identifying the components of a problem and identifying the components of a solution?

   Model answer

   The components of a problem are the parts of the situation itself, described in the language of the domain and without deciding how anything will be done. For a car park system those are: vehicles arrive and leave, spaces are finite, drivers must pay for the time used, and the operator needs revenue reports. Nothing there mentions software. The components of a solution are the parts of the thing you are going to build, described in the language of design: an entry controller reading the loop sensor and driving the barrier motor, a ticket issuing module, a payment machine interface, a central occupancy service, a database of transactions, and a reporting module. Keeping them separate matters because jumping straight to solution components locks in a design before the problem is understood, and you end up building the first thing you thought of. It also matters because one problem component may map to several solution components, or several problem components to one, and that mapping is where the design decisions live. In practice you analyse the problem first, then design a solution, and then check every problem component is addressed by something in the solution and that every solution component exists for a reason traceable back to the problem.

5. 5

   Explain top-down stepwise refinement and describe what a structure chart for it would look like.

   Model answer

   Top-down stepwise refinement starts from a single statement of the whole task and repeatedly replaces each statement with a small number of more detailed sub-tasks, continuing until every remaining statement is simple enough to implement directly. Each level is a complete description of the task, just at a coarser or finer grain. Take producing end-of-term reports. Level one is a single box: produce reports. Level two breaks it into four boxes side by side beneath it, read from left to right in the order they happen: gather data, calculate summaries, generate documents, distribute. Level three sits beneath each of those. Under gather data: read pupil list, read subject grades, read attendance, read teacher comments. Under calculate summaries: compute subject averages, compute year position, flag concerns. Under generate documents: apply the template, insert data, produce a file per pupil. Under distribute: send by email, file a copy, print those needed on paper. On a structure chart these appear as a hierarchy of rectangles connected by lines to their parent, with the sequence running left to right at each level; small annotated arrows on the connecting lines show what data passes up and down, so gather data returns a pupil record set that calculate summaries consumes. Repetition and selection are usually marked with a loop symbol or a diamond on the relevant connection. The chart is valuable exactly because it forces the data passing between components to be stated.

6. 6

   Why does the order of steps matter? Give an example where reordering two steps breaks a solution.

   Model answer

   Because most steps depend on the results or effects of earlier ones, so a step performed before its input exists will operate on nothing, on a default value or on stale data. Take deploying an update to a website that includes a change to the database structure. The correct order is: put the site into maintenance mode, take a backup, apply the database migration, deploy the new application code, run the smoke tests, take the site out of maintenance mode. Swap the last two and users hit a live site that has not been checked. Swap the migration and the code deployment and the new code runs against the old structure, so it queries columns that do not yet exist and fails on every request. Move the backup after the migration and you have no way back if the migration is what goes wrong, which is the most likely thing to go wrong. A second, smaller example: validating a user's input after using it to look up a record means the lookup is performed with unvalidated data, and if the input was malformed the program either crashes or, worse, the unvalidated value reaches the database. Order is not stylistic; each dependency is a constraint, and the correct sequence is any ordering that respects all of them.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.