CS20 : How to solve it - better!


In this topic, we are learning how to solve problems. We will formalise the techniques used by computer scientists to help them to automate the solutions to, often complex, problems in the real world.

We are learning ...
  • How to solve and check the solutions to logic problems
  • How to Implement representation, generalisation, categorisation, procedural, functional, data and composition abstraction techniques to problem solving
  • To decompose problems into smaller, more manageable chunks
  • How algorithms are put into practice to solve problems
  • How to describe and apply algorithms and techniques in practical situations
So that we can ...
  • Develop and check solutions to logic problems
  • Describe the techniques of abstraction
    - Representation
    - Generalisation / categorisation
    - Functional
    - Divide and conquer
  • Discuss the concept of Information hiding
  • Describe the technique of decomposition / composition
  • Design interfaces
  • Understand the need for automation.
  • Apply patterns for problem solving
    Backtracking
    Data mining
    Heuristics
    - Caching
    Performance modelling
    Pipelining
    Visualisation to solve problems (mental models)

Computer science is about building clean, abstract models (abstractions) of messy, noisy, complex, real world objects of phenomena. Computer scientists have to choose what to include in models and what to discard, to determine the minimum amount of detail necessary to model in order to solve a given problem to the required degree of accuracy.

Computer science deals with putting the models into actions to solve problems. This involves creating algorithms for performing actions on, and with, the data that has been modelled.

Logic Puzzles

Computer science is mainly concerned with solving problems. Sometimes the problems are hard, sometimes not. In any event, solving logical puzzles and learning the strategies you can use is extremely valuable. Before we even talk about problem solving, I'm going to give you some tricky challenges.

http://www.amazon.co.uk/Raymond-M.-Smullyan/e/B000AQ1NF0/ref=sr_ntt_srch_lnk_2


Further steps, not assessed, but quite interesting (to me at least).

Problem solving, in it's current form, dates back to about 800AD when Alcuin of York published 'Propositiones ad Acuendos Iuven', roughly translated as 'Problems to sharpen the young'. If you fancy stepping back in time, there is a beautiful copy in the lesson resources. Have a look.

More recently, the father of modern problem solving, George Pólya, published a famous book called 'How to solve it'. I have a copy of this wonderful book if you want a look. Read the first bit, the rest is quite educational.

Lastly (but by no means exhaustively), how about a Rubik's cube, the mechanical puzzle invented by Ernő Rubik in 1974? It originally took him a month to solve it but now you can learn from the best on YouTube.

At the time of writing, the current human record is 4.90s (set by Lucas Etter in autumn 2015). Impressive, but not as impressive as this ...



Activity 1 Problem Solving Techniques 

Most intelligent people (i.e. not cats) accept that there is generally better ways of solving logic problems that thrashing about. Poor Preparation Prevents Proper Performance - known as the 5P's (there are 6P's in some versions ...)


Let's consider each step in a formal problem solving strategy ...

STEP 1 : Understand the problem

What is the unknown? What are the data? What is the condition? Is it possible to satisfy the condition? Is the condition sufficient to determine the unknown? Or is it insufficient? Or redundant? Or contradictory? Draw a figure. Introduce suitable notations. Separate the various parts of the condition. Can you write them down?


When a problem is well defined, we can identify ...

Given   Where you are starting from? What is the initial situation?
Resources   What you have to work with, resources, time, people, skills.
Constraints   What boundaries are in place which will restrict what you can achieve?
Ownership   Who owns the problem, or the solution? Who has a vested interest in making sure it's solved?
Goal   Where am I heading? What is the ultimate aim of what I am trying to achieve?

... which taken together give us access to and understanding of the problem domain.


Task 1.1
 Apollo 13
Web browser

Visit the NASA homepage for the (almost) doomed 1970 Apollo 13 mission to the moon.


Read, summarise the problem and try to identify and record the 'given', the 'resources' and 'constraints', the 'ownership' and goal' of this problem.

OUTCOME : Lovely, colourful summary of what went wrong, what they had available to solve the problem, any boundaries imposed by their rather serious situation, who was ultimately responsible for sorting it out, what they finally managed to sort out.


STEP 2 : Devise a plan

How shall we move from the given to the goal?

  • Have you seen a problem like this before? How did you solve it?
  • Have you met a situation with similar resources / constraints?
  • Could you change the problem to look like one you have seen before?
  • Is there anything you need to do before you solve the problem? Are there any auxiliary problems?
  • Do you have or indeed need all the information you have gathered? Could some be ignored?
Often, breaking down a problem in to smaller, interdependent parts makes solving the problem more manageable. The technique often used is called Top Down Design with Stepwise Refinement. Often, these are stated as separate strategies but they are interdependent ...

https://drive.google.com/file/d/0B83yXMOilskab0F2dE54Q3lmMms/view?usp=drive_web
Click to view

There are no hard and fast rules to drawing diagrams like this. They are often called Hierarchy diagrams. There many be a series of sequential steps necessary to complete each subtask. In this case, we could draw a structure table - a list of instructions. Normally, we draw a hybrid diagram which involves both.

For instance, this website is structured like this ...

https://drive.google.com/file/d/0B83yXMOilskaczJDb2twMHVQOU0/view?usp=drive_web
Click to view

... whilst a folder based directory structure in a computer filing system might have this structure ...

https://drive.google.com/file/d/0B83yXMOilskaMm1BVkg1akJOSTQ/view?usp=drive_web
Click to view

This incorporates the features of a hierarchy diagram and that of a structure table. As long as it works and everyone can tell what it means, it's OK! We will learn more about this strategy in 'Break it down' ...

Task 1.2 Break it down
This website

Might seem like an odd thing to ask, but I would like you to create a Hierarchy chart for the last topic you studied, "Round and Round". I took a natural approach to writing this where I firstly broke the topic down into smaller sections and then in each section, took a sequential approach to leading you through the content. Use the example above to help you.

OUTCOME : A hybrid hierarchy diagram and structure table for the last topic.


Clearly, the remaining step to a working solution is composition where simple procedures / functions / data abstractions are combined to produce a complex working system.

The outcome of Step 2 should be an algorithm.

STEP 3 : Execute your plan

Carrying out your plan of the solution, checking each step. Can you see clearly that each step is correct? Can you prove that it is correct? How easy is the plan to follow? Could it be improved? So many questions!

Task 1.3 Origami
Square piece of paper - it has to be square.

Your first challenge is to make a square piece of paper! The paper has to be square. Square, not rectangular. Clear?Next, following these instructions to create your very own origami lotus flower.

https://drive.google.com/file/d/0B83yXMOilskaaXF4TDE2NkhBaHc/view?usp=drive_web
Click to view

How easy were the stepwise instructions to follow? What helped or hindered?

OUTCOME : A beautiful origami lotus flower and an evaluation in your notebooks about the process.


STEP 4 : Evaluate the answer

Time to crack open the bubbly! Ah, but wait - are you sure you did it?

Go back to the original problem. Forget the way you solved it and the steps you took during that journey. Go through the requirements of the problem and check that your solution works.

Task 1.4 Copying
Nothing

Running out of ideas - just copy the diagram above into your notebooks (including a nice likeness of Carol).

OUTCOME : Nice copy of the 'Evaluate the answer' diagram in your notebooks.


Activity 2 Abstraction 

Human beings have developed an extremely powerful technique for dealing with complexity. Unable to master the entirety of a complex object, we ignore it's inessential detail, dealing instead with a generalised, idealised model of the object which suits our needs as a user. We abstract the object.

Consider a complex object like a cat. Depending on the viewpoint, the user abstracts away all the inessential detail to leave a simpler object which is suited to their need ...


Deciding on what to leave out is a central problem in programming and object oriented design (which we'll meet later on in the course).

Abstraction is ...
  • process : Performing an abstraction on a problem
  • technique : For identifying what information should be hidden
  • An entity : Picasso's final bull is an abstraction of the first


You may be more familiar with the term abstraction in the context of art. Abstract art "seeks to break away from traditional representation of physical objects. It explores the relationships of forms and colours, whereas more traditional art represents the world in recognizable images."


Picasso's Bulls. Notice the persistence of the 'essential' features (ahem!)

Task 2.1
 London Underground
Web browser

Harry Beck is attributed with designing the current layout of the London Underground map. Read the article about his work on Wikipedia, especially the section on 'Beck's concept' which explains why he drew the map in the way he did ...


  1. Why did Harry Beck prefer to represent the Tube Map in this way? What benefits did it have?
  2. How is this an example of abstraction?
There are now many different representations of the London Tube map available. Perform a quick Google Image Search and find 5 different representations. Why are they different?

OUTCOME : Answer to the questions plus 5 different image representations of the London tube map and an explanation of why they are needed.


Representation abstraction

Sometimes, the goal of abstraction is to reach a common representation of a problem. This common representation may allow us to use a previously successful algorithm to solve this new problem.

Task 2.2
 Floodfill
Floodfill.zip, extracted and double clicked upon.

Play this game! How far can you get? What strategy do you adopt in order to solve it?

OUTCOME : Fun!


Problems of this type can be solved using one algorithm. They are classically map colouring problems which are solved using the general vertex colouring algorithm your teacher has shown you.


Task 2.3
 Problems
Battling Students
Mobile Phone Masts
The Ichthyophiles Problem

There is no point trying this activity if you haven't taken part in the teacher led activity in class. If you haven't (or can't remember), you will want to speak to your teacher first before continuing.

If you haven't already, attempt these problems from the Logic Problem section at the top of the lesson. They all use the vertex colouring algorithm to produce a solution, although the solution may not always be optimal.

OUTCOME : Solutions to the problems using the vertex colouring algorithm. Working out must be shown!


Generalisation abstraction

If we can group problems by common characteristics to arrive at a hierarchical relationship of the 'is a kind of' type, we may be able to design behaviours for the more abstract objects that apply to the more specific. For instance ...

Click to view

Designing a behaviour for 'animals' which all animals perform reduces the amount of work I have to do in order to model the behaviour of snakes or tigers. This method of abstraction is used extensively in Object Oriented Design. Notice that the abstract concept of 'Animal' is an example of high abstraction whereas the Bear is low abstraction (closer to reality).

Task 2.4
 Plant classifications
Web browser
Pen and paper

Using suitable research, draw (by hand) a suitable portion of the classification diagram for plants.

OUTCOME : A hand drawn portion of a classification structure for plants. What behaviours do the more abstract plants to which all plants do?


Functional abstraction

Classically used in maths but applied to all sorts of other problems, functional abstraction takes away the actual values used in a computation leaving behind a computational pattern or method. Functional abstraction leads to the development of functions (obviously) - sub programs which take parameters in and return results.

Mathematicians use functions all the time - sin(), cos() and tan() for instance. Programmers use functions all the time as well - print(), open(), input(). Mathematicians and programmers can design user-defined functions if there is no function available which perform some action either independently or using combinations of existing functions.

As the user of the function, I need not be aware of how the function works. For instance, do any of you actually know how the sin() function works in maths or actually know how the print() function works in Python?

Do I care?

Task 2.5
Functional abstraction
Web browser

Visit the following website and use it to write notes on functional abstraction (even though it's called procedural abstraction). Make sure your note include ...
  • Definition
  • Examples
  • Advantages
OUTCOME : Notes on functional abstraction including examples, in your books. Written by hand.


Procedural abstraction

Sometimes, problems lend themselves immediately to solutions using the same basic steps - the procedure. The classic Fox, Chicken Grain problem is one of a group of problems which can be solved using the same procedure. Procedural abstraction naturally follows from the representation abstraction method which we saw earlier with the graph colouring problem where initially dissimilar problems are boiled down to similar representations to which can be applied the same procedures.

Task 2.6
 Similar problems
'Propositiones ad Acuendos Iuvenes' from the lesson resources

The Fox, Chicken, Grain problem is one of a class of problems which can be solved using the same procedure. There are other examples in 'Propositiones ad Acuendos Iuvenes' which is available from the lesson resources.

See problems 171819 and 20.

Whilst you solve your problems, come up with a pictorial method of representing the solutions. Do not simply write down a list of steps. Try to indicate with your diagrams where each resource in the problem is at each step.

OUTCOME : Pictorial representation of solution to at least one of the supplementary problems.


Data abstraction

Computers can only store data in the form of binary digits. Yet, we can create such abstract data structures as arrays (or lists), graphs, trees, stacks and queues.  Data abstraction takes the complexity of how these data structures are actually stored and manipulated in the computer and hides it, providing a simple functional interface to it's use.

Task 2.7
 Practical applications of abstract data structures
Web browser
Imagination?

If you are not clear about arrays, graphs, trees, stacks and queues, perform some Internet research into their applications. HINT : Google 'Applications of .......... in Computer Science'.

OUTCOME : Practical examples for the use of each of the 5 data structures in Computer Science.


Activity 3 Information hiding, encapsulation and interfaces

However, the systems that are produced must be usable by people, so what exactly is it that needs to be hidden or kept secret?  It is the internal design of such systems - the way they operate - that is kept secret. Looking an an abstraction from the inside, as the implementer, you'd be concerned with what it's composed of and how it works. Looking at it from the outside, as the user, you are only concerned with what it is and what it does. You can look past the detail and think solely in terms of the role that the function performs.

The 'machine' provides a green ball.
I don't care where the green ball comes from.
I know I always get a green ball.
The green ball machine can change.
I still get a green ball.

Information hiding is a technique which is used to obfuscate (or hide) the inner workings of a procedure / abstraction from the outside world whilst providing an interface to allow it's operation - related to functional abstraction.

The interface is very similar but the implementation is very different.


It matters not which car you drive - a Bugatti or a Fiat - the basic operation of the machine is the same. It is the implementation that varies.


Two objects with the same interface can implement the action in completely different ways

Taking an object, hiding the implementation and providing an interface is called encapsulation. Encapsulation ensures that the object remains useable (as it's interface remains static) whilst it's implementation can change.


Encapsulation hides the details of the 
implementation of an object and provides
an interface for interaction with it.

Task 3.1
 Definitions
Brain

Write definitions in your notes for the following key terms. Use the text above to help you. Try not to look on the Internet for the answers ...
  • Information hiding
  • Encapsulation
  • Interface
  • Implementation
OUTCOME : Definitions for key words in your book.


Information hiding in practice - The Enigma Machine

Keeping the operation of a machine secret from the outside world was vital for the operation of the German Enigma Machine - the primary method of encrypted communication in use during the latter part of the Second World War by the German military.


The Enigma Machine

Task 3.2
 Investigating Enigma
Web browser
  • Visit the Public Enigma website and read about the various Enigma machines used by the Germans in the Second World War. There is a copy of the simulator in the 'Resources' directory of this section for you to download and practice with or you can get it from the Public Enigma website.
  • Visit Cryptomuseum website and research the operation of the Enigma Machine. You can also download a simulator from the links at the bottom of the page. Try out the Enigma Simulator on your own computer.
  • You can even make one using paper tubes - the instructions are available in the resources for the lesson.
OUTCOME : A greater working knowledge of the power of the Enigma Machine. No written outcome required.

In programming terms, it is API's (Application Programming Interfaces) which provide the interface to the implementation. We will learn much more about interfaces when we study Object Oriented Design later on in the course.

Activity 4 Modelling techniques / Automation 

Computer science deals with putting abstractions into action to solve problems. This involves creating algorithms for performing actions on, and with, the data that has been modelled.
  • Creating algorithms
  • Implementing models as data structures
  • Implementing algorithms in code
  • Executing the code

Task 4.1
 Automation gone mad!
Breathcube.zip
Names.zip

There are two rather strange pieces of software in the Resources directory called 'Breathcube' and 'Names'. There are in Zip folders but you should be able to download them and run them on your computer. Do you think this is the future?

OUTCOME : The strange realisation that the world is weirder than you first thought. No written outcome.


Activity 5 Patterns

Problem solving strategies / patterns commonly in use include ...
  • Backtracking
  • Data mining
  • Heuristics
  • Caching
  • Performance modelling
  • Pipelining
  • Visualisation

Task 5.1
 Research and presentation

Download the presentation template, 'Patterns', which is really dull, and complete it. On each slide, include the following information ...
  • Definition of the technique
  • Example of it in use
Please feel free to download the 'Computational Methods' help sheet, however, you should use this information in your presentation to make it exciting and engaging - don't just copy and paste!

OUTCOME : Completed, enticing, engaging presentation, obviously.


Extension Activities 

Try the following activities to stretch and challenge.
  • Use the vertex colouring algorithm to colour in the map of South America which is in the lesson resources.

  • Investigate a possible method of applying the vertex colouring algorithm (representation abstraction) to the problem of solving a game of Sudoku. You could come up with your own problem which could be represented using the vertex colouring algorithm and share this as a challenge with your friends.

  • Learn to solve a Rubik's cube.

What's next?

Before you hand your book in for checking, make sure you have completed all the work required and that your book is tidy and organised. Your book will be checked to make sure it is complete and you will be given a spicy grade for effort.

END OF TOPIC ASSESSMENT