computational thinking - topic one

what is computational thinking

the process used to solve complex problems -formulating a problem and expressing a solution the way a computer can carry it out

what are the two stages involved in computational thinking ?

decomposition

abstraction

what is abstraction

abstraction involves identifying the key parts of the problem and removing and unnecessary detail so it becomes easier to solve e.g importing random to shuffle a deck of cards

what is decomposition

decomposition is the braking down a complex problem into a smaller, manageable parts which are easier to solve

what are the three steps of decomposition

• identifying the main problem

• list the main sub problems,functions or tasks

• break down into smaller sub-problems or sub tasks which can they be complete separately

what is a subroutine

are small programs that are written within a larger, main program. The purpose of a subprogram is to perform a specific task.

what are the two types of subprograms

• procedures

• functions

benefits of a subroutine

• making debugging and maintaining the program is easier as subroutines are usually short and separate form the main code

• subroutines can be tested separately and shown to be correct

• a particular subroutine can be called several times in the same program and may also be saved to a subroutine library to be used in other programs

what is a procedure ?

procedure is a subprogram that performs a specific task. When the task is complete, the subprogram ends and the main program continues from where it left off.

how do you call a procedure

ogrammers use the procedure name and include any parameter values that the procedure needs

what is a function

function works in the same way as a procedure, except that it processes data and returns a result back to the main program.

how do you call a function

programmers use the function's identifier, the parameter value to be passed into the function, and a variable for the function to return and assign a value into

what are some in built functions

• int - converts strings or floats into integers

• str - converts a number into a string

• asc - finds the ASCII number of a character

advantages of flow charts

• it is easy to see how a program flows

• flowcharts follow an international standard

disadvantages of flowcharts

• with a large program, the diagrams can become huge and therefore difficult to follow

• any changes to the design may mean a lot of the diagram has to be redrawn

symbol for input output

parallelogram

symbol for decision

diamond

symbol for process

rectangle

symbol for subroutine

rectangle with a lines both sides

symbol for terminal (start/end)

oval

what is a problem with flowcharts to develop an algorithm

it doesn’t translate into progam code very easily

whats is pseudo code

a method of writing up a set of instructions for a computer program using plain English.

benefit of pseudo code

• it can be quickly and easily converted into an actual programming language as it is similar to a programming language

• it is fairly easy to understand, even for non-programmers

• it does not matter if there are errors in the syntax - it is usually still obvious what is intended

• changes to the design can be incorporated quite easily

disadvantages of pseudocode

• It can be hard to see how a program flows

• It can be time consuming to produce.

what are the three basic programming constructs

• sequence

• selection

• iteration

what is a sequence

is the order in which instructions occur and are processed.

what is iteration

Iteration is the repeated execution of a section of code when a program is running.

what are the 2 types of iteration

• count-controlled

• condition-controlled

what is count-controlled iteration

repeatedly executes a section of code a fixed number of predetermined times- using a FOR loop, which uses a control variable to determine what code is repeatedly executed and how many times.

what is condition controlled iteration

epeatedly executes a section of code until a condition is met - or no longer met. The two most common types of condition-controlled iteration are:

• while loops, which use the statements WHILE and END WHILE

• repeat loops, which use the statements REPEAT and UNTIL

what is selection

determines which path a program takes when it is running

what is an algorithm

a sequence of steps that can be followed in order to complete a task e.g recipes

what is the diffidence between a computer program and an algorithm

a computer program is one way of implementing an algorithm in a particular language but its the series of the instructions and the order of those instructions that are the basis of any algorithm

what is nested selection

its where a decision has a decision nested inside it

what is a list?

a collection of variables of the same or different types, enclosed in square brackets

how is a list referenced ?

using an index starting at 0 for the first item

how would you refer to lennie in the list ?

playername =[“corrie”,”ben”,”gordon”,”lennie”,”pete”]

playername[3]

what is a trace table ?

is used to show how variables change during execution of a program

what are three types of error?

• syntax

• logic

• runtime

what is a syntax error ?

prevent program from running due to spelling/grammar mistake in your code

what is a logic error ?

a mistake in a program's code that causes it to behave unexpectedly or produce incorrect results, without generating an error message. e.g x>5 rather than x>=5

what is a runtime error?

it will be detected when the program is running -may be caused by a logic error or by the program not allowing for condition such as user inputting 0 or entering no data at all

what is a binary search?

a search that can be used to search a list that is in numerical or alphabetical order -works by repeatedly dividing in half portion of the list that could require one data item

what are the advantages and disadvantages of binary search

• list needs to be ordered

• more efficient than linear search

what is a linear search

each item will be checked one by one in the list

what are the advantages and disadvantages of linear search

• if list is large it will take a very long time

• list does not need to be ordered

what is bubble sort ?

bubble sort works by repeatedly going through a list to be sorted swapping adjacent elements if they are in the wrong order

disadvantage of bubble sort

• not efficient for large lists

what is merge sort

list is repeatedly divided into two until all the elements are separated individually. Pairs of elements are then compared, placed into order and combined. The process is then repeated until the list is recompiled as a whole.

describe the two stages of merge sort

• stage 1 : the list is successively divided in half , forming two sunsets , until each sub list is one length

• stage 2:Each pair of subs lists is repeatably merged to produce new sorted sub lists until there is only one list remaining-the sorted list

what type of algorithm is merge sort

recursive algorithm which means the subroutine calls itself

what type of algorithm is bubble sort

iterative algorithm meaning that it uses WHILE and/ for loops repeating the same sets many times

which algorithm is more efficient bubble sort or merge sort

merge sort

how can the efficiency of algorithms be measured ?

• by the time it takes to execute

• amount of memory required for given data set

what is a transistor ?

Microscopic devices that open and close circuits to communicate electrical signals. CPUs contain millions of transistors.

what two states do a computer have ?

• on - a current is flowing through the component (1)

• off - a current is not flowing through the component(0)

what is a logic gate ?

a logic gate is a series of transistors connected together to give one or more outputs. Each output is based on the input or combination of inputs supplied to it.

what are the three types of logic gates ?

• AND gate

• OR gate

• NOT gate

what is a AND gate

An AND gate uses two inputs to generate one output. The output is 1 (TRUE) only if both of the inputs are 1 (TRUE).

what is an OR gate ?

An OR gate uses two inputs to generate one output. The output is 1 (TRUE) only if either or both of the inputs are 1 (TRUE).

what is a NOT gate ?

a NOT gate uses one input to generate one output. A NOT gate inverts the input. The output is 1 (TRUE) if the input is 0 (FALSE), and the output is 0 (FALSE) if the input is 1 (TRUE).