Problem solving and abstraction

Specific and general problems

Problems can be specific (e.g. How many paving stones are needed for this 3 m X 4 m patio?) or general (e.g. How many paving stones are needed for a x m X y m patio?)

A general problem abstracts away the actual values to define the problem for a variety of different input values.

Problem solving methods

An exhaustive search involves trying every possible solution to a problem e.g. Searching an array one ofter the next to see if the array contains a certain value.

A divide and conquer strategy attempts to split the problem into smaller sub-problems, solve those sub-problems often using recursion and combine the sub-problems to get the final solution of the whole problem e.g. a binary search where half the list is eliminated at each search.

Abstraction

Abstraction is a core part of computational thinking alongside decomposition and algorithmic thinking. It involves removing building abstract models of real world secnarios ad objects.

There are a number of types of abstraction for you to be familiar with:

* Representational abstraction * Abstraction by generalisation * Procedural abstraction

* Functional abstraction * Data abstraction * Problem abstraction * Compositional abstraction

Representational abstraction

This involves removing unnecessary detail from a problem. A commonly referred to example is the London Tube Map which omits details. For instance, the actual routes of the lines is ignored and distances between stations are not to scale. Instead the artist has favoured straight lines and spacing that allows the names to be easily placed. In doing so the important information of which lines connect to which is made easier to see so commuters can more easily find there way around the network.

Abstraction by generalisation

Abstraction by generalisation or categorisation is a grouping by common characteristics to arrive at a hierarchical relationship of the 'is a kind of' type. In developing an algorithm for loading passenger ferries, we may consider the transport of vehicles. A truck would be a type of vehicle as would a car. Cars could be further broken down e.g. a hatchback is a type of car.

Procedural abstraction

Procedural abstraction represents a computational method. The result of abstracting away the actual values used in any particular computation is a computational pattern or computational method - a procedure. All that needs to be known is the interface i.e. what values need to be passed to it, as what data type and in what order.

Functional abstraction

In functional abstraction the computation method is hidden. To get a function requires another abstraction beyond procedural abstraction, which disregards the particular computation method and concerns itself only with returning the result.

Data abstraction

This refers to the creation of abstract data types based on primitive data types by defining the methods they can work with. Examples of abstract data types include stacks and queues which might be implemented using arrays and pointers and rules for stack/queue size. However, the programmer using the abstract data type need only know what operations can be performed on the abstract data type such as enqueue or dequeue and not how it has been implemented.

Problem abstraction

Problem abstraction is where details are removed until the problem is represented in a way that is possible to solve because the problem reduces to one that has already been solved. If you consider a maze, the solution can be obtained by representing the maze as a graph with each decision point in the maze becoming a node and the paths between them the edges.

Compositional abstraction

Composition includes bringing together a series of procedures to complete more complex tasks. You can build data abstractions by combining data objects to form compound data, for example the binary tree data structure can be represented as a list of lists.

Knowledge check

Questions:

Correct:

Question text