TOPIC 1- Computational Thinking

Decomposition - The process of breaking down a larger problem into a set of smaller problems.

This makes the problem easier to solve, promotes independent testing, and can be combined to make a solution to the problem.

An example of decomposition is the making of computer games, since doing it all at once would be inefficient and difficult.

Abstraction - The process of removing unnecessary details of the problem to focus on the important features.

Computer games also require a lot of abstraction, since developers remove the elements that the suer does not need to consider during gameplay.

Subprograms are blocks of code that can be called at any point during the program.

Many benefits of subprograms include:

There are two types of subprograms.

Procedures do not return a result.

Functions return one or more results (when the code is run).

An algorithm is a set of instructions to solve a specific problem or task.

You can present an algorithm with (pseudo)code or a flowchart.

Code uses English-like phrases, while flowcharts use shapes to represent the different functions.

There are four main data types to classify data into groups:

Changing a data type in a program is called casting.

An array is an ordered set of elements. An array can only store 1 data type.

A linear search is sequential.

In a linear search algorithm, the algorithm moves through the list one-by-one until it finds the matching item or reaches the end of the list.

A binary search compares the matching item to the median value by doing the following:

Binary search is optimal for longer data sets.

Linear search is optimal for unsorted lists.

A bubble sort sorts elements in a list into ascending or descending order as follows:

Compares the first 2 values in a dataset (e.g. index 0 and 1)
If they’re not in the correct order, swap them.
Compare the next two values (e.g. new index 1 and 2).
Repeat the steps until you reach the end of the dataset. This is one ‘pass’.
If swaps were made throughout the pass, go through the list again.
If no swaps were made throughout the pass, STOP! The list is in the correct order.

A merge sort breaks a list apart then builds it up again in the right order.

This strategy is known as the ‘divide and conquer’ strategy.

Steps of merge sort:

Divide all the elements into separate lists that hold one single value.
They are then reassembled into lists with two values, however they are put into the correct order (e.g. ‘6’ and ‘2’ are assembled to make a list containing 2 and 6 respectively).
The two leftmost values are compared of the first two data-sets, and then so are all the values until they are slotted into each other to make a new list containing 4 values.
These lists are then compared (starting with the leftmost element) to make another list.
This is repeated over and over until you have one list with all your elements - ordered correctly.

There are three types of errors that can occur in programs:

Syntax errors - When the grammatical rules of a programming language is broken, e.g. grammar errors or misplaced semi-colons. Syntax errors are usually caused by the fault of the programmer.
Logic errors - Code technically ‘works’, but provides an incorrect result, e.g. incorrect use of operators, incorrect indentation, or infinite loops. Trace tables are good to help identify these.
Runtime errors - Error causes program to crash, e.g. dividing a number by 0 or indexing out of range.