Computer Science · Ch 4 — Introduction to Problem Solving
Decomposition
Decomposition
Some problems are complex in the sense that their solution is not directly derivable — no single algorithm obviously produces it. For such problems the strategy is decomposition: break the complex problem down into simpler parts, solve the parts, and assemble the answers.
The railway reservation system, revisited
Recall the railway reservation system from the start of the chapter. Designing a good reservation system is far too large to attack as one lump; instead it is treated as designing the different components of the system and then making those components work with each other effectively. Figure 4.12 shows one such breakdown into sub-problems, including:
- trains' information — days, timings, stations, classes and berths;
- reservation information — whether booking is open or closed, availability or waiting list, cancellation and refund;
- information about staff, security and railway infrastructure;
- food service;
- billing service;
- other details about railways.
How decomposition works
The basic idea of solving a complex problem by decomposition:
- Decompose — break the complex problem down into smaller sub-problems. Each sub-problem is relatively easier to solve than the original.
- Solve the sub-problems — each one can be examined in detail and solved on its own.
- Combine — finally, the sub-problems are put together in a logical way to obtain the solution of the bigger, main problem.
Why decomposing helps teams
Breaking a problem into sub-problems brings organisational advantages as well:
- each sub-problem can be examined in detail individually;
- each can be solved independently, and by different persons or teams;
- having different teams on different sub-problems lets specific sub-problems be assigned to teams who are experts at solving problems of that kind.
Where decomposition applies …
Drawn by us to help you understand the concept clearly, and verified to make sure it's accurate. For exams, practice from your textbook's own diagram.
Figure 4.12 is a block diagram, not a flowchart: it depicts the decomposition of a railway reservation system into its sub-problems. One large teal rounded rectangle represents the whole system, and inside it sit six light-green rounded-corner boxes arranged in a 3×2 grid — one box per sub-problem. No arrows connect the boxes.
The six sub-problems shown:
Top row, left to right
- Trains' information — days, timings, stations, classes and berths (the book's caption prints the misprint "births" for "berths").
- Reservation information — whether booking is open or closed, availability or waiting list, cancellation and refund.
- Information about staff, security, railway infrastructure.
Bottom row, left to right
- Food service.
- Billing service.
- Other details about railways.
The figure's geometry carries its meaning. The containment — six boxes inside one enclosing rectangle — says that the dauntingly complex problem "build a railway reservation system" is really the sum of six far more manageable pieces: solve each piece, then combine the pieces logically, and the big problem is solved. The absence of arrows is equally deliberate: this diagram is not describing an order of execution or a flow of control, only a structural breakdown. The sub-problems are largely independent — which is exactly what lets each be examined in detail, solved separately, and even assigned to a different team of specialists (the food-service module need not wait for the billing module). …