"Having to solve a particular problem, we might ask: How difficult is it to solve? and What’s the best way to solve it? Computer science rests on solid theoretical underpinnings to answer such questions precisely.
...In solving a problem efficiently, we might further ask whether an approximate solution is good enough, whether we can use randomization to our advantage, and whether false positives or false negatives are allowed. Computational thinking is reformulating a seemingly difficult problem into one we know how to solve, perhaps by reduction, embedding, transformation, or simulation." (Jeannette Wing)
"There are many approaches to problem solving, depending on the nature of the problem and the people involved in the problem. The more traditional, rational approach is typically used and involves, e.g., clarifying description of the problem, analyzing causes, identifying alternatives, assessing each alternative, choosing one, implementing it, and evaluating whether the problem was solved or not.
Another, more state-of-the-art approach is appreciative inquiry. That approach asserts that "problems" are often the result of our own perspectives on a phenomenon, e.g., if we look at it as a "problem," then it will become one and we'll probably get very stuck on the "problem." " (Wikipedia)
The article in Wikipedia makes it clear that problem solving is a psychological issue: just how do our brains proceed from a state of not knowing the solution to one where we do? How do we work things out? Why can one person solve a problem, see its solution, when someone else cannot? Clearly there is something neurological at work here. Can we teach problem solving? Will daily fish oil help? Is it one of those things that you are either good at or absolutely hopeless? How does general problem solving ability relate to computer science?
Five stages (four in some models e.g. here)
If there is a problem then the goal (solution) is not understood.
Knowing what you have to find and the key pieces of information that must be put together to obtain the answer. It will nearly always be necessary to go over the problem a number of times before it is fully understood. Even then, aspects of the problem may be revealed at later stages such that the earlier ones must be revisited. Need some knowledge of the problem domain, a set of skills to tackle the problem.
Make an ill-defined problem well-defined.
Four components: initial situation; goal; resources and constraints; ownership. Resources may help you move from initial situation to goal. There may be constraints on resources such as rules (as in a computer game) or regulations (as in real life). Solving a problem will require commitment of one's own intellectual resources. If working in a team you need to be clear on who does what: who owns which parts of the problem.
Constraints: time, resources, money. Challenge assumptions, establish facts.
Top-down or bottom-up? Break problem into small parts. Work from the top of the solution (a general overview: vision) towards the smaller parts; or work from the smaller parts towards an overall solution. Sub-problems may form part of a hierarchy.
Top-Down Design: hierarchy chart; separate modules; assemble the pieces of a solution;
Stepwise Refinement: define the major steps in a problem then break them down into smaller sub-steps; proceed to the level of abstraction where you understand the problem; going beyond the level of abstraction where you understand a problem will be tedious ("OK, OK, I get it!"); not reaching the level of abstraction required for understanding means you still don't really understand as you haven't broken it down sufficiently. Think about this in relation to teachers and lessons: sometimes you understand quickly and you want the teacher to move on; sometimes you don't get it and you want the teacher to keep breaking down the problem or finding new ways to describe and analyse it e.g. pictures, analogies, similar problems.
Try out the solution with a range of test data and different scenarios to make sure it works.
You are in a land of two tribes, one that always tells the truth and the other that always lies. It is impossible to recognise members of the tribes so you don't know who tells the truth and who lies. You come to a junction with no sign and a citizen standing close by. What single question can you ask to determine the correct route? Remember that you do not know whether this person is a truth-teller or a liar.
Later you meet three citizens of this strange land. Citizen A tells you that some of the three men are liars; citizen B tells you that citizen A would call C my tribal brother; citizen C is mute and says nothing. Which of these men is a liar and which is telling the truth? With three citizens and two tribes how many combinations of liar and truth-teller are there? What method might you use to evaluate the possible choices?
Still in the land of liars and truth tellers, you meet two more citizens. One tells you that the other citizen is a liar; the second citizen tells you that they are from the same tribe. What tribes are they from?
Four children are playing together when a window is broken. Child A says that B broke the window; child B says that C broke it; child C and child D say they saw nothing. Assuming that the child who broke the window is not telling the truth, who broke the window?
See here.
This game features nine words: spit, not so as, if, in, pan, fat, fop. Each of two players chooses a word in turn and attempts to collect all three words with a common letter: as, pain, fat, for example. Each player also tries to prevent the other player from collecting a set of three cards. What is the underlying model for this game? How can one play with the certainty of never losing? How can the words be arranged to provide a crib that will ensure a game is never lost?
Simplest: 1 + 1. How do we know the answer? What about 2+2? Or 87 + 136? Brains and memory.
How does a computer work out the answer? Computer is an electronic machine, it doesn't know in the same sense. No more than an analogue machine does (abacus). The brain does not calculate in the same way but brains invented machines.
We have to figure out how to move a problem from brain domain to machine domain. Computers can easily solve problems like 1 + 1 or 87 + 136 and much harder ones as well. But how about if neither humans nor computers could add or subtract by more than 1 unit at a time? What would addition (and subtraction) look like then?
Describe how you would add two numbers, e.g. 5 + 5 with no additions or subtractions greater than 1. Convert your account into pseudo-code or structured English with one action per line. Could you convert the pseudo-code to code that a computer could read?
How do we know that 4 x 5 = 20? What if we had never learned our tables? Why did we learn multiplication tables? Why did we stop at 12? Did we learn computer numbers like 2^10? Could we work out the answers to multiplication problems without knowledge of tables?
Assume no knowledge of multiplication. Devise a way of multiplying two numbers e.g. 4 x 5 that would work on a machine that has no knowledge of multiplication. Convert your account into pseudo-code or structured English with one action per line. Could you convert the pseudo-code to code that a computer could read?
Describe how your brain processes pairs of numbers to produce the Fibonacci sequence. How would you get on processing sequences of 5 numbers instead of 2? Or 10? Is there a limit that your brain imposes?
Describe how a computer can produce a Fibonacci sequence. Is there a limit to the length of a sequence that the computer could process? Convert your account into pseudo-code or structured English with one action per line. Could you convert the pseudo-code to code that a computer could read?
How many beans make up a triangle with side 2? How many make up a triangle with side 5? Find a way to automate the process of generating triangle numbers. Derive a formula for finding triangle numbers by combining two triangles e.g. how many beans in a triangle of side 100?
What is a factor? How do you know whether a number is a factor of another number? e.g. is 7 and 131? e.g. 87 and 4047? What about the numbers on this page?
Once again, focus on how your brain solves the problem and then convert this to a solution that a computer might understand.
What are prime factors? Given a number such as 42, what are its prime factors? Devise a method for finding the prime factors of a number and describe it in prose. Convert this to pseudo-code.
What is a perfect number? One whose factors add up to the number. What is the smallest perfect number? How do you discover if a number is 'perfect'? Devise a method and convert it to pseudo-code so it can be converted to a program.
A group of friends are on holiday together. They keep a record of who has paid for what and settle the differences at the end of the holiday. Given a series of total expenditures for each person what is the smallest amount of money that must change hands to ensure that everyone pays the same?
Given a start time and a finish time in format HH:MM, find the length of time between them. Give the result in hours: minutes and minutes.
Voters give each candidate a preference of 1, 2...n, where n is the number of candidates. With reference to a list of votes cast by n voters, describe how this voting method works. Convert your description to pseudo-code.
Given two integers of equal length work out how many carries will be involved in adding them together.
Problems on a grid are common e,g. word search, Battleships, Minesweeper, Sudoku, Noughts and Crosses, the Game of Life, Draughts, Chess, Go, Hexapawn. Graphic images are composed of pixels in a grid and there are many algorithms that operate on them.
Find solutions to a 3 x 3 and a 4 x 4 magic square. Note all the rules that apply to these square. Devise a method for solving a magic square such that you can apply to find a solution to a 5 x 5 square.
How many combinations of 9 digits in 9 squares are there? How many in a 4 x 4 square? A 5 x 5 square? What is the Big O value for the number of combinations? How practical is it to use a computer to find solutions to magic squares by brute force? How long would it take on a modern computer to solve a 5 x 5 square? A 7 x 7 square?
There is an algorithm for placing numbers in a magic square. Can this be translated into a computer program?
Describe how the game of mine sweeper is played. Describe how, given a description of the board as either blanks or mines the values of squares around the mines are determined. For a given board explain how you would determine where to place the values of 1, 2 and 3. Declare the size of board you are using.
Convert your account into pseudo-code or structured English with one action per line. Could you convert the pseudo-code to code that a computer could read?
Imagine your hands are one key to the right when typing so the text comes out wrong. Take a given line of text and decode it. Or encode a line of text one position to the right.
Explain how a Caesar shift encrypts text. Convert your description to pseudo-code.
Explain how a substitution cipher encrypts text. Convert your account to pseudo-code.
Explain how a substitution cipher can be broken. Convert your account to pseudo-code. How would a computer program know when it has found a valid word? How would a computer know when it had found the correct key? How would a computer know that decrypted text made sense?
Given 8 random letters, what is the longest word that you can make? How does your brain go about solving this problem? How would a computer program solve it? What is the big O value for your algorithm?