Topic 4 - Computational thinking - Student Booklet

Computational thinking, problem-solving and programming

by M Brooke

Identify the procedure appropriate to solving a problem.

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

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

Thinking procedurally involves having the decomposed parts of a problem available. Following that you are going to look at how these can be ordered procedurally in order to create a program or algorithm. The outcome of thinking procedurally is to:

- Identify the components of a problem.
- Identify the components of a solution to a problem.
- Determine the order of steps needed to solve a problem.
- Identify sub-procedures necessary to solve a problem.

Step 1 - Identify the components of a problem

I need to make a cup of tea.

Step 2 - Identify the components of the solution to the problem

Pour water into teapot

Pour tea into cup

Turn off tap

Add tea bags to teapot

Fill kettle

Add milk

Turn on tap

Warm teapot

Heat kettle

Step 3 - Determine the order of steps needed to solve the problem

Turn on tap

Fill kettle

Turn off tap

Heat kettle

Warm teapot

Add teabags to teapot

Pour water into teapot

Pour tea into cup

Add milk

Step 4 - Identify any sub procedures

The process of filling and heating the water in a kettle is a procedure that could be considered a subroutine. It is a procedure that is called on in a number of situations and can be effectively reused. Designing methods like this that can be reused in a variety of circumstances can speed up software development and reduce testing time as the method is already tested and working and can simply be “plugged in” to the required solution.

We could make a subprocedure that we can plug in

Procedure boilKettle ()

Turn on tap

Fill kettle

Turn off tap

Turn on kettle

And the final solution would be:

boilKettle ()

Warm teapot

Add teabags to teapot

Pour water into teapot

Pour tea into cup

Add milk

Notice that many of these procedures can be broken down into further sub-procedures. The level of decomposition will depend on the type of program required. The design of a device driver for a piece of hardware for example may require some low level programming. This level of decomposition may lead to further and more complex logical thinking which is covered below.

This is one of the fundamental parts of computational thinking. Computers process data logically but this is not “thinking”. In order for the computer to work it needs to be given instructions. In order for these instructions to work then the programmer must think logically in order to design the program. Logical thinking is also fun and there are a great many ways for you to develop your logical thinking skills such as Suduko^{[1]} and Kakuro^{[2]} or Lightbot^{[3]}.

In many cases the steps required to solve a problem such as the example given above require no decision making and are linear solutions. However if we may have simple situations that require a decision to be made and there are two alternative decisions to be made.

EG A system that automatically grades exam papers. Part of the program will involve a decision. This can be expressed using a flowchart:

Or alternatively in pseudocode:

if GRADE>50 then

Output "Pass"

else

Output "Fail"

Endif

In this case the decisions that need to identified in order to solve the problem is the logical condition determining if the exam is a pass or fail.

Boolean logic is named after George Boole, a famous 19th Century mathematician. In this logic all values are expressed as either true or false. This fits well with binary systems which can be expressed as either 0 or 1.

Boolean operators exist that can be used to manipulate the basic true false values. Examples of operators are as follows

Operator | Meaning |

= | Is equal to |

> | Greater than |

< | Less than |

>= | Greater than or equal to |

<= | Less than or equal to |

≠ | Not equal to |

AND | The output is true if both inputs are true |

OR | The output is true if one of the inputs is true |

NOT | The output is true if the input is false |

NAND | The output is true if either or both inputs are false. |

NOR | The output is true if both inputs are false |

XOR | The output is true if only one of the inputs is true and only one is false. Known as exclusive OR. |

These may be expressed in a logic table where 0 is FALSE and 1 is TRUE.

AND

Input A | Input B | Output Z |

0 | 0 | 0 |

0 | 1 | 0 |

1 | 0 | 0 |

1 | 1 | 1 |

OR

Input A | Input B | Output Z |

0 | 0 | 0 |

0 | 1 | 1 |

1 | 0 | 1 |

1 | 1 | 1 |

NOT

Input A | Output Z |

0 | 1 |

1 | 0 |

NAND

Input A | Input B | Output Z |

0 | 0 | 1 |

0 | 1 | 1 |

1 | 0 | 1 |

1 | 1 | 0 |

NOR

Input A | Input B | Output Z |

0 | 0 | 1 |

0 | 1 | 0 |

1 | 0 | 0 |

1 | 1 | 0 |

XOR

Input A | Input B | Output Z |

0 | 0 | 0 |

0 | 1 | 1 |

1 | 0 | 1 |

1 | 1 | 0 |

These can be used to create logic table to find the solution to problems. For example a student is only allowed to play computer games if their homework is done and their room is tidy. The solution to this can be illustrated in a logic table as follows:

Homework done | Room tidy | Output Z |

0 | 0 | 0 |

0 | 1 | 0 |

1 | 0 | 0 |

1 | 1 | 1 |

More details of how to solve logic problems is covered in Section 2.1.11.

Iteration in computing is the repetition of a block of statements within a computer program. In practice this repetition can take place a set number of times or can repeat based on a set of logical criteria that change over time.

There are two main ways this is achieved in programming which are a for loop and a while loop.

In the IB pseudocode document the syntax for a for loop is a from to loop. In most programming languages the syntax of a for loop is

for (INITIALIZATION; CONDITION; AFTERTHOUGHT)

{

// Code for the for-loop's body goes here.

}

This may be expressed in a flowchart as:

In JAVA the syntax would be

For (int x= 0; x<5;x++){

//do something

}

In IB psueudocode it would be as follows:

loop X from 0 to 4

//do something

end loop

A while loop is an iteration but in this case the loop must repeat until a certain condition is met. This can be programmed in JAVA in the following way

while (COUNT<5) {

COUNT = COUNT + 1

}

In IB pseudocode this would look like this:

loop while COUNT<5

COUNT = COUNT +1

end loop

A variation of the while loop is the do while loop in which a condition is first run before the check is made. The difference is that the evaluation of the expression is done at the end of the loop:

do {

//Statements

}

while (condition)

In computing conditional statements are features which perform different computations depending on whether a boolean expression evaluates as true or false. The basic structure of this statements using IB pseudocode is as follows:

if (condition) then

//Do something

else

//Do something else

end if

This can be used in a number of contexts in computer programming.

In computer science, linear search or sequential search is a method for finding a particular value in a list, that consists of checking every one of its elements, one at a time and in sequence, until the desired one is found.^{[4]}

For example consider the following array of integers:

Let us imagine we are searching for the number 21. First go to the first element of the array.

Is it equal to 21? No. Then move to the next element.

Is it equal to 21? No. Then move to the next element.

Is it equal to 21? Yes.

Here is an example of a linear search in pseudocode:

N=0

loop while ARRAY.hasNext()

if ARRAY[N] == SEARCHTERM then

output N

end if

N=N+1

end loop

output -1

The method returns the position of the search term if it is found otherwise it returns a -1.

In computer science, a binary search or half-interval search algorithm finds the position of a specified input value (the search "key") within an array sorted by key value. In each step, the algorithm compares the search key value with the key value of the middle element of the array. If the keys match, then a matching element has been found and its index, or position, is returned. Otherwise, if the search key is less than the middle element's key, then the algorithm repeats its action on the sub-array to the left of the middle element or, if the search key is greater, on the sub-array to the right. If the remaining array to be searched is empty, then the key cannot be found in the array and a special "not found" indication is returned.^{[5]}

For example consider we are searching the following sorted array of integers for the number 27.

First find the middle position

Is 16<33? Yes. Discard the right hand half.

Next find the middle position

Is 16<24. Yes. Discard the right hand half.

Next find the middle position

Is 27<27? No

Is 27>27? No

Then we have found the term.

There are several variations of this method but it can be written in an iterative way as (IB sample algorithms):

public int binarySearchA(int target, int[] nums, int size)

{

// An iterative binary search. Size = size of num array.

// If found, returns position. Else returns -1.

int middle, low, high;

boolean found = false;

low = 0;

high = size-1;

middle = -1;

while (high >= low && !found)

{ middle = (low + high) / 2;

if (target < nums[middle])

{ high = middle - 1; }

else if (target > nums[middle])

{ low = middle + 1; }

else

{ found = true; }

}

if (found)

{ return middle; }

else

{ return -1; }

}

Bubble sort, sometimes incorrectly referred to as sinking sort, is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. The algorithm gets its name from the way smaller elements "bubble" to the top of the list. Because it only uses comparisons to operate on elements, it is a comparison sort. Although the algorithm is simple, most of the other sorting algorithms are more efficient for large lists.^{[6]}

There are several variations of this method but it can be written in an iterative way as (IB sample algorithms):

public void bubbleSortB(int[] nums, int size)

{

// An ascending bubble sort, but this does not perform a

// specific number of passes. Instead, it stops if an entire pass

// completes WITHOUT any swaps occurring.

int current, temp;

boolean done;

do

{

done = true ;

for(current = 0; current < size-1 ; current = current + 1)

{ if (nums[current] > nums[current + 1])

{

temp = nums[current];

nums[current] = nums[current+1];

nums[current+1] = temp;

done = false;

}

}

} while (!done);

}

In computer science, selection sort is a sorting algorithm, specifically an in-place comparison sort. It has O(n2) time complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is noted for its simplicity, and it has performance advantages over more complicated algorithms in certain situations, particularly where auxiliary memory is limited.

The algorithm divides the input list into two parts: the sublist of items already sorted, which is built up from left to right at the front (left) of the list, and the sublist of items remaining to be sorted that occupy the rest of the list. Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right.^{[7]}

There are several variations of this method but it can be written in an iterative way as (IB sample algorithms):

public void selectionSortB(int[] nums,int size)

{

int first, current, least, temp;

for(first = 0; first < size; first = first + 1)

{

least = first;

for(current = first+1; current < size; current = current + 1)

{ if (nums[current] < nums[least])

{ least = current; }

}

temp = nums[least];

nums[least] = nums[first];

nums[first] = temp;

}

}

4.2.2 Outline the standard operations of collections.

Addition and retrieval of data.

Binary search requires the data to be sorted linear search does not.

Comparing the two we find that the efficiency of the linear search is O(n) whereas the efficiency of the binary search is O(log2n).

Array Size | Efficiency | |

n | Linear Search O(n) | Binary Search O(logn) |

10 | 10 | 3 |

100 | 100 | 7 |

1000 | 1000 | 10 |

10000 | 10000 | 13 |

Binary search requires random access to the data whereas linear search does not. Because of this binary search will not work on linked lists for example. Linear search only requires sequential access.

^{[8]}

An algorithm is a detailed sequence of steps that are needed to solve a problem. A flowchart is a graphical representation of an algorithm.

4.2.3 Analyse an algorithm presented as pseudocode.

Make sure that you have read the two documents from the IB “Pseudocode in examinations” and “Approved notation for developing pseudocode”. See assignments on elearning.

4.2.4 Construct pseudocode to represent an algorithm.

Make sure that you have read the two documents from the IB “Pseudocode in examinations” and “Approved notation for developing pseudocode”. See assignments on elearning.

4.2.5 Suggest suitable algorithms to solve a specific problem.

See assignments on elearning.

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

Lesson 39….. Complexity Analysis (Big O). See assignments on elearning.

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

See assignments on elearning.

A fundamental operation could be something like , multiply two numbers, store a number, move a number to another location etc. These are operations that do not require the processor to go through a large number of sub operations to reach a result.

For example, find the largest is a compound operation.

A compound operation is an operation that involves a number of stages/other operations. Think of it as a group of operations that combine together to form an operation.

- All languages are subject to a set of rules governing the set of valid characters that can be used

- word construction
- sentence construction

- The rules of sentence construction are called syntax
- To use a language correctly you need to know about these and

- vocabulary - the set of valid words
- semantics - ensuring that what is written makes sense

- You need to be able to recognize language 'tokens'

- English language descriptions of language rules can be very cumbersome, and lead to ambiguity
- Syntax diagrams are a neat way of expressing language rules

- they should be completely unambiguous
- they usually involve other syntactic elements (tokens)

- What would a syntax diagram look like for

- a word
- a sentence
- prose

- Syntax - the grammatical arrangement of words to show their connection and relation; the set of rules governing this arrangement.
- Semantics - relate to meaning in language
- A sentence in English may be syntactically correct

- it obeys the language rules

- But not necessarily semantically correct

- it has no valid meaning

- Both syntax and semantics are important

- A computer program is like a set of instructions
- Each instruction is termed a statement
- Each program statement has a terminating character
- Translate into syntax diagrams

In computer science, a high-level programming language is a programming language with strong abstraction from the details of the computer. In comparison to low-level programming languages, it may use natural language elements, be easier to use, or may automate (or even hide entirely) significant areas of computing systems (e.g. memory management), making the process of developing a program simpler and more understandable relative to a lower-level language. The amount of abstraction provided defines how "high-level" a programming language is.

Examples of high-level programming languages include Java, Lisp, R, Python and Ruby.^{[9]}

Interpreted languages are read and then executed directly, with no compilation stage. A program called an interpreter reads each program statement following the program flow, decides what to do, and does it. A hybrid of an interpreter and a compiler will compile the statement into machine code and execute that; the machine code is then discarded, to be interpreted anew if the line is executed again. Interpreters are commonly the simplest implementations, compared to the other two variants listed here.

Compiled languages are transformed into an executable form before running. There are two types of compilation:

Some compilers compile source code directly into machine code. This is the original mode of compilation, and languages that are directly and completely transformed to machine-native code in this way may be called "truly compiled" languages. See assembly language.

Scanning

Parsing

Optimise

Code generation

When a language is compiled to an intermediate representation, that representation can be optimized or saved for later execution without the need to re-read the source file. When the intermediate representation is saved, it is often represented as byte code. The intermediate representation must then be interpreted or further compiled to execute it. Virtual machines that execute bytecode directly or transform it further into machine code have blurred the once clear distinction between intermediate representations and truly compiled languages.

^{[10]}

Java uses a two step compilation process. Java source code is compiled down to "bytecode" by the Java compiler. The bytecode is executed by Java Virtual Machine (JVM). The current version of Sun HotSpot JVM uses a technique called Just-in-time (JIT) compilation to compile the bytecode to the native instructions understood by the CPU on the fly at run time.

In computing a variable relates to a name or identifier which relates to a value at a particular memory storage location.

In computing a constant is an identifier whose associated value cannot typically be changed by the program during runtime as opposed to a variable whose value can be altered.

Programming languages support a range of operators which behave like functions. Operators are special symbols that perform specific operations on operands, and then return a result. For example operators from JAVA can be seen below ^{[11]}:

Operators | Precedence |

postfix | expr++ expr-- |

unary | ++expr --expr +expr -expr ~ ! |

multiplicative | * / % |

additive | + - |

shift | << >> >>> |

relational | < > <= >= instanceof |

equality | == != |

bitwise AND | & |

bitwise exclusive OR | ^ |

bitwise inclusive OR | | |

logical AND | && |

logical OR | || |

ternary | ? : |

assignment | = += -= *= /= %= &= ^= |= <<= >>= >>>= |

Operator | Definition |

= | Assignment operator eg int age = 18 This assigns the value of 18 to the variable age |

≠ | Not equal to |

< | Less than |

<= | Less than or equal to |

> | Greater than |

>= | Greater than or equal to |

mod | Modulus operator which will give a remainder of a division. . eg 5 mod 2 = 1 In JAVA the operator is % eg to find if a number is odd or even the following code can be used: boolean isEven if ( (a % 2) == 0) { isEven = true } else { isEven = false } |

div | Integer part of quotient. eg 15 div 7 = 2 |

Collections store a set of elements. The elements may be of any type (numbers, objects, arrays,

Strings, etc.).

A collection provides a mechanism to iterate through all of the elements that it contains. The

following code is guaranteed to retrieve each item in the collection exactly once. ^{[12]}

// STUFF is a collection that already exists

STUFF.resetNext()

loop while STUFF.hasNext()

ITEM = STUFF.getNext()

// process ITEM in whatever way is needed

end loop

http://www.google.com/edu/computational-thinking/what-is-ct.html

http://www.cs4fn.org/computationalthinking/

http://csta.acm.org/Resources/sub/ResourceFiles/CompThinking.pdf

[1] "Web Sudoku - Billions of Free Sudoku Puzzles to Play Online." 2005. 17 Mar. 2016 <http://www.websudoku.com/>

[2] "Kakuro.com, the home of Kakuro (cross sums) on the internet." 2002. 17 Mar. 2016 <http://www.kakuro.com/>

[3] "Lightbot." 2015. 17 Mar. 2016 <https://lightbot.com/>

[4] "Linear search - Wikipedia, the free encyclopedia." 2004. 13 Jan. 2014 <http://en.wikipedia.org/wiki/Linear_search>

[5] "Binary search algorithm - Wikipedia, the free encyclopedia." 2005. 13 Jan. 2014 <http://en.wikipedia.org/wiki/Binary_search_algorithm>

[6] "Bubble sort - Wikipedia, the free encyclopedia." 2003. 13 Jan. 2014 <http://en.wikipedia.org/wiki/Bubble_sort>

[7] "Selection sort - Wikipedia, the free encyclopedia." 2004. 13 Jan. 2014 <http://en.wikipedia.org/wiki/Selection_sort>

[8] "xkcd: Good Code." 2011. 13 Jan. 2014 <http://xkcd.com/844/>

[9] "High-level programming language - Wikipedia, the free encyclopedia." 2003. 14 Jan. 2014 <http://en.wikipedia.org/wiki/High-level_programming_language>

[10] "About the Java Technology (The Java™ Tutorials > Getting Started ..." 2011. 15 Jan. 2014 <http://docs.oracle.com/javase/tutorial/getStarted/intro/definition.html>

[11] "Operators (The Java™ Tutorials > Learning the Java Language ..." 2011. 15 Jan. 2014 <http://docs.oracle.com/javase/tutorial/java/nutsandbolts/operators.html>

[12] “Pseudocode in Examinations.” IBO. PDF.