Data Abstraction and Problem Reduction

Overview

Recall questions on what data abstraction is, the stack as a worked example and how new data objects are built from existing ones.

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 data abstraction?

   Model answer

   Data abstraction separates the way a compound data object is used from the way it is built. The details of how the data are actually represented are hidden, so fresh kinds of data object can be assembled out of ones already defined.

2. 2

   Use a stack to give a worked example of data abstraction.

   Model answer

   How a stack is used is fixed by its operations: push adds an item, pop removes and returns the most recently added item, peek looks at it without removing it, and isEmpty reports whether there is anything there — last in, first out. How it is constructed is a separate matter: a stack could be implemented as an array together with a pointer holding the index of the top of the stack, where push increments the pointer and stores the item and pop returns the item at the pointer and decrements it. Data abstraction is the separation of those two things, so that code using the stack calls push and pop and never mentions the array or the pointer.

3. 3

   That stack is built as an array plus a pointer. What does data abstraction let you do afterwards, and what would break if it were absent?

   Model answer

   It lets you replace the whole construction — say with a linked list where push adds a node at the front — and every program that uses the stack goes on working unchanged, because those programs only ever used push, pop, peek and isEmpty. Without data abstraction, code elsewhere would refer directly to the array and to the top-of-stack index; changing the representation would then mean finding and rewriting every such reference, and any code that had, for example, assumed a fixed array size would silently be wrong.

4. 4

   How does data abstraction let new kinds of data objects be constructed from previously defined ones?

   Model answer

   Once a type has been defined by how it is used, it can be treated as a single building block in the definition of another type without its internals mattering. A queue of customers can be defined in terms of a previously defined Customer record; a graph can be defined as a set of vertices and a set of edges, each edge being a pair of previously defined vertices; a priority queue can be built on top of an existing heap. At each level the new object is described by its own operations, and the level below is used only through its operations.

5. 5

   What is problem abstraction, also called problem reduction?

   Model answer

   Problem abstraction means paring a problem back, dropping detail after detail, until what remains is a problem that has already been solved — at which point the existing solution can simply be applied. Reducing a real road network to a weighted graph, for instance, turns 'find the quickest route between two towns' into the shortest-path problem, for which well-known algorithms are already available.

6. 6

   Give a worked example of a real problem being reduced to one that is already solved.

   Model answer

   A satnav must find the quickest route across a city. Strip away the street names, the shop fronts, the traffic lights, the road surfaces and the geography, and keep only junctions, the roads joining them and a number on each road for how long it takes to travel. What remains is a weighted graph, and 'find the quickest route' has become 'find the shortest path between two vertices in a weighted graph' — a problem for which known algorithms already exist. No new algorithm has to be invented; the work was in the abstraction.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.