Computational Thinking, Problem-Solving, and Programming

Computer science is sometimes defined as the study of algorithms and their efficient implementation in a computer. The focus now is their role in problem solving, strategies for developing the, techniques for following and testing them. Because algorithms operate on data, we examine ways to structure data so that it can be more efficiently processed.

General principles

Thinking procedurally

4.1.1 Identify the procedure appropriate to solving a problem.

Generally speaking, all problems begin with an idea. Finding the connection between this information and the solution lies at the heart of problem solving. To do this, the following strategies can be utilised.

Ask questions

When given a problem or task verbally, one typically asks questions until what is needed is known fully and clear. Generally, when, why, and where are asked until the task is completely specified. If the instructions are written, one might put question marks in the margin; underline a word, a group of words, or a sentence; or in some other way indicate the parts of the task that are not clear. Perhaps the questions might be answered in a later paragraph, or one might have to discuss them with the person giving the task. If the task is one that it self-set, this sort of questioning might not be verbal, but instead takes place on the subconscious level.

• In this case, some typical questions that one should consider are:
• What should I know about the problem?
• What does the solution look like?
• What sort of special cases exist?
• How will I recognise that I have found the solution?

Look for Familiar Things

Don't reinvent the wheel. Exploit the similarities between previous problems solved. This is a form of pattern recognition.

Testing the Algorithm

4.1.2 Evaluate whether the order in which activities are undertaken will result in the required outcome.

We constantly break up a large problem into smaller units that we can handle. The task of cleaning the house or apartment may seem overwhelming. The task composed of cleaning the living room, the dining room, the kitchen, the bedrooms, and the bathroom seems more manageable. This principle is especially relevant to computing.

4.1.3 Explain the role of sub-procedures in solving a problem.

Do not reinvent the wheel. If a solution exists, use it. If you have solved the same or a similar problem before, just repeat the successful solution. We usually do not consciously think, "I have seen this before, and I know what to do" - we just do it. Humans are good at recognising similar situations. We do not have to learn how to go to the store and buy milk, then to buy eggs, then to buy candy. We know that going to the store is always the same and only what we buy is different.

Recognising familiar situations is particularly useful in computing. In computing, you see certain problems again and again in different guises. A good programmer sees a task, or perhaps part of a task (a subtask), that has been solved before and plugs in the solution. For example, finding daily high and low temperatures in a list of temperatures is exactly the same problem as finding the highest and lowest grades in a list of test scores. You want to the largest and smallest values in a set of numbers.

Thinking logically

4.1.4 Identify when decision-making is required in a specified situation.

4.1.5 Identify the decisions required for the solution to a specified problem.

4.1.6 Identify the condition associated with a given decision in a specified problem.

4.1.7 Explain the relationship between the decisions and conditions of a system.

4.1.8 Deduce logical rules for real-world situations.

Thinking ahead

4.1.9 Identify the inputs and outputs required in a solution.

4.1.10 Identify pre-planning in a suggested problem and solution.

4.1.11 Explain the need for pre-conditions when executing an algorithm.

4.1.12 Outline the pre- and post-conditions to a specified problem.

4.1.13 Identify exceptions that need to be considered in a specified problem solution.

Thinking concurrently

4.1.14 Identify the parts of a solution that could be implemented concurrently.

4.1.15 Describe how concurrent processing can be used to solve a problem.

4.1.16 Evaluate the decision to use concurrent processing in solving a problem.

Concurrent processing allows for faster computation, as multiple tasks are run simultaneously. However, concurrent processing is a lot more difficult to program.

Thinking abstractly

4.1.17 Identify examples of abstraction.

4.1.18 Explain why abstraction is required in the derivation of computational solutions for a specified situation.



4.1.19 Construct an abstraction from a specified situation.

4.1.20 Distinguish between a real-world entity and its abstraction.

Connecting computational thinking and program design

Searching algorithms

Sequential search



4.2.1 Describe the characteristics of standard algorithms on linear arrays.

There are numerous algorithms that exist in the realm of computer science, however, sorting and searching are two of the most important types.

Sequential, or linear, search is the simplest search algorithm; it is a special case of brute-force search. Its worst case cost is proportional to the number of elements in the list; and so is its expected cost, if all list elements are equally likely to be searched for. Therefore, if the list has more than a few elements, other methods (such as binary search or hashing) will be faster, but they also impose additional requirements.

Binary Search

This relies upon the linear array being sorted into order. Assume we want to find X.

1. Start at the middle element.
2. Is X greater than or equal to that element?
3. If yes, remove all lower than that from the population.
4. Move to the middle of the new population and repeat.

Note the 'middle' is always the larger element when you have an even set.

Bubble Sort

Assuming we are sorting a list of numbers from lowest to highest.

1. Starting from the left, compare that number X to the one on its right Y.
2. Ix X>Y then swap X and Y around.
3. Repeat through the entire list.
4. Repeat whole process until nothing needs to switch on a full pass through.

Selection Sort

The simplest way to sort from low to high.

1. Go through entire population and find the lowest.
2. Shift the lowest to the farthest left.
3. Ignore the sorted element(s), go through the remainder of the population in the same manner.

4.2.2 Outline the standard operations of collections.

4.2.3 Discuss an algorithm to solve a specific problem.

4.2.4 Analyse an algorithm presented as a flow chart.

4.2.5 Analyse an algorithm presented as pseudocode.

4.2.6 Construct pseudocode to represent an algorithm.

4.2.7 Suggest suitable algorithms to solve a specific problem.

4.2.8 Deduce the efficiency of an algorithm in the context of its use.

4.2.9 Determine the number of times a step in an algorithm will be performed for given input data.

Introduction to programming

Nature of programming languages

4.3.1 State the fundamental operations of a computer.

4.3.2 Distinguish between fundamental and compound operations of a computer.

4.3.3 Explain the essential features of a computer language.

4.3.4 Explain the need for higher level languages.

4.3.5 Outline the need for a translation process from a higher level language to machine executable code.

Use of programming languages

4.3.6 Define the terms: variable, constant, operator, object.

4.3.7 {{{2}}}

4.3.8 Analyse the use of variables, constants and operators in algorithms.

4.3.9 Construct algorithms using loops, branching.

4.3.10 Describe the characteristics and applications of a collection.

4.3.11 Construct algorithms using the access methods of a collection.

4.3.12 Discuss the need for sub-programmes and collections within programmed solutions.

4.3.13 Construct algorithms using pre-defined sub-programmes, one-dimensional arrays and/or collections.