Topic 1: Computational thinking

Question 1

Decomposition

Answer 1

breaking down problems and solutions into smaller parts

Question 2

Abstraction

Answer 2

the process of removing or hiding unnecessary details (so you can focus on the important poins)

Question 3

Algorithms

Answer 3

a step-by-step procedure for solving a problem or carrying out a task.

Question 4

Reason for decomposing problems

Answer 4

to reduce the size of the problem

Question 5

Subprogram

Answer 5

block of code that performs a specific task

Question 6

Pre-existing subprograms in python

Answer 6

• print()
• len()
• random.randint()
• math.floor()

Question 7

Subprograms are useful to:

Answer 7

• break down a complex program into less complicated parts
• make program logic clearer
• make it easier to maintain code
• code can be used as many times as needed, avoiding repetition
• be stored in libraries and reuse them in other programs
• enable a team of programmers to work together at the same time

Question 8

2 ways subprograms speeds up program development

Answer 8

1) the programmer can use pre-existing subprograms so that they can use them to perform common tasks
2) a group of programmers can work in different subprograms because different subprograms can be allocated to different programmers.

Question 9

Algorithms : flowcharts

Answer 9

Be able to draw flowcharts

Question 10

Algorithms: selection

Answer 10

used to choose between two or more options

Question 11

Selection in flowcharts

Answer 11

Diamond symbol; has 2 output arrows, one for yes and the other for no.

Question 12

Selection in python

Answer 12

If… elif… else… statement

Question 13

Algorithms : repetition

Answer 13

the process of repeating a set of instructions until there is a desired outcome

Question 14

2 types of repetition

Answer 14

Condition-controlled repetition
Count-controlled repetition

Question 15

Condition-controlled repetition

Answer 15

when the number of times a loop is executed is not known before the loop is started

Question 16

Count-controlled repetition

Answer 16

when the number of times a loop is executed is known before the loop is started

Question 17

Condition controlled in python

Answer 17

while statement

Question 18

Count- controlled in python

Answer 18

for…in range() statement

Question 19

Reason why loops do not need dedicated symbol in flowcharts

Answer 19

In a selection symbol (rhombus), you can have an arrow pointing at the begining of the choice, therefore that creates autmatically a loop

Question 20

Reason why loops do not need dedicated symbol in flowcharts

Answer 20

In a selection symbol (Diamond), you can have an arrow pointing at the begining of the choice, therefore that creates autmatically a loop

Question 21

Algorithms: iteration

Answer 21

Repeating a set of instructions for every item in a data list.

Question 22

2 features in a flowchart that indicate iteration is used

Answer 22

• A data list
• A backward pointing arrow to a selection symbol

Question 23

Arrays

Answer 23

data structure that can store multiple elements from the SAME DATA TYPE

Question 24

2D arrays

Answer 24

[[…],[…],[…]]

Question 25

Record

Answer 25

• a collection of data objects
• can be of DIFFERENT DATA TYPES

Question 26

How are elements called in a record

Answer 26

a field

Question 27

Arithmetic operators

Answer 27

used to perform calculations

Question 28

Relational operators

Answer 28

used to compare different items of data

Question 29

Examples of arithmetic operators:

Answer 29

+, -, *, /, %, // (returns integer part of division), **(exponentiation powers of)

Question 30

Examples of relational operators:

Answer 30

==, !=, <, <=, >, >=

Question 31

Difference between (%) and (//)

Answer 31

%(Modulus) returns the remainder after the division, whereas //(integer division) returns the integer part after division

Question 32

AND operator

Answer 32

Overall statement is true if ALL individual statements are true

Question 33

OR operator

Answer 33

Overall statement is true if ANY OF THE individual statements are true

Question 34

NOT operator

Answer 34

used to reverse the logical state

Question 35

TRACE TABLES

Answer 35

Page 12,13 R.Guide

Question 36

Types of errors that can be found in algorithms

Answer 36

Syntax error
Runtime error
Logic error

Question 37

Logic error

Answer 37

• Hardest to detect
• will produce an incorrect or unexpected result

Question 38

Linear search

Answer 38

it is sequential starting at the begining and moves through item by item

Question 39

Problem of linear search

Answer 39

Uses raw computing power
It is not an efficient method
- search starts at the begining
- until item found
- or reaches the end

Question 40

Describe in words an algorithm for carrying out a linear search (6 marks)

Answer 40

1) If the length of list is 0, stop
2) Start at the beginning of the list.
3) Compare the list item with the search criterion.
4) If they are the same, then stop.
5) If they are not the same, then move to the next item.
6) Repeat steps 3 to 5 until the end of the list is reached

Question 41

Binary search

Answer 41

compares the search item with the median item in a list, repeatedly splitting the list in half until the item is found or there are no more items left to search

Question 42

Describe the stages of applying binary search to find 17:
3,5,9,14,17,21,27,31,35,37,39,40,42

Answer 42

Step 1: The median is 27 but is higher than search item
Step 2: The sub-list to the left is used: 3,5,9,14,17,21
Step 3: The median is 9 but is too low. The sub-list 14,17,21 is used.
Step 4: The median is 17 which is the search item.

Question 43

Binary search requirement

Answer 43

needs to be sorted: alphabetically or numerically

Question 44

Bubble sort ———

Answer 44

Page 17 in revision guide

Question 45

Merge sort

Answer 45

is an algorithm that breaks a list into its components and then builds it up again IN the correct ORDER

Question 46

Describe how data is sorted into ascending order using the merge sort algorithm

Answer 46

The list is divided into two repeatedly
- until each list has only one item.
The lists are then progressively merged
- with the items in ascending order.

Question 47

Merge sort vs Bubble sort

Answer 47

For large numbers of items, a merge sort is far more efficient than a bubble sort as the problem is broken down into smaller and smaller problems, which are easier to solve

Question 48

Choose Linear search when:

Answer 48

• unsorted list
• a short list
• a list that is not going to be searched very often

Question 49

Choose Binary search when:

Answer 49

• a long list
• a list that will be searched often

Question 50

Advantages of linear search:

Answer 50

• Linear search algorithms are simple

Question 51

Advantages of Binary search:

Answer 51

• Divide and conquer (breaks the list into smaller lists and performs the same operation on each).
• Binary searches execute quickly

Question 52

Disadvantages of linear search:

Answer 52

• Brute force (tries out every possibility until a solution is found or all possibilities are exhausted

Question 53

Disadvantages of binary search:

Answer 53

• Initial list must be sorted
• Binary search algorithms are complex and user recursion (that is, where a function calls itself).

Question 54

Choose bubble sort for:

Answer 54

• a list with a smaller number of items

Question 55

Choose Merge sort for:

Answer 55

• a long list

Question 56

Advantages of bubble sort:

Answer 56

• A simple algorithm to code
• No extra storage used to make copies of data.

Question 57

Advantages of merge sort:

Answer 57

• Divide and conquer approach
• Longer lists add only a little bit more execution time

Question 58

Disadvantages of bubble sort

Answer 58

• brute force
• longer lists use much more time to sort

Question 59

Disadvantages of merge sort:

Answer 59

• uses additional memory for copies of lists.
• The splitting phase must happen, even for very short lists
• Complex algorithm, usually involving recursion.

Question 60

Trace tables vs Truth tables

Answer 60

Truth tables are used for AND, OR, NOT whereas trace tables are used for showing how a program works.