2.1 Computational Thinking

Question 1

What are the three types of computational thinking? [3]

Answer 1

Abstraction [1] Decomposition [1] Algorithmic thinking [1]

Question 2

What is abstraction? [2]

Answer 2

Removing unnecessary detail [1] to focus on the important parts of a problem [1]

Question 3

What is decomposition? [2]

Answer 3

Breaking a large problem down into smaller problems [1] until the problems are small enough to solve [1]

Question 4

What is algorithmic thinking? [2]

Answer 4

Structuring a problem so it can be solved by a computer [1] usually by making it quantitative [1]

Question 5

What are the three programming constructs? [3]

Answer 5

Sequence [1] Selection [1] Iteration [1]

Question 6

What is programming in sequence? [2]

Answer 6

Instructions in order [1] processed one after the other [1]

Question 7

What is programming using iteration? [2]

Answer 7

Repeating sections of code [1] until conditions are met [1]

Question 8

What is programming using selection? [2]

Answer 8

Choosing which code to run [1] based on a decision [1]

Question 9

When writing an input in an algorithm what must we remember to do? [1]

Answer 9

Assign the input to a variable [1]

Question 10

What is a structure diagram? [3]

Answer 10

A diagram that shows the problem you’re solving at the top [1] then breaks the problem down into smaller problems below [1] then breaks those problems down into smaller problems etc [1]

Question 11

Describe the steps a linear search would use to look for an item in a list [4]

Answer 11

Look at each item in order [1] starting at the beginning [1] until the item is found and the position of the item is returned [1] or the end of the list is reached and the search returns not found. [1]

Question 12

What is the prerequisite for binary search data? [1]

Answer 12

It must be in order [1]

Question 13

Describe the steps a binary search would use to look for an item in a list [5]

Answer 13

Find the middle of a list (round down if it would be a decimal) [1]

If it’s the number searched for, return the index of the number [1]

If it is higher than the number, discard the middle number and lower half of list and repeat [1]

If it is lower than the number, discard the middle number and the upper half of list and repeat. [1]

If only one value is left and it’s not the number we’re looking for, the number is not in the list [1]

Question 14

Complete a binary search for the number 7 in this data:

2 4 6 7 8

Answer 14

2 4 6 7 8 # Find middle number - 6.
# 6 is lower than 7 so discard 6 and lower half of list.
7 8 # Find middle number - between 7 and 8, so go left
# Middle number is 7. Return index of 7.

Question 15

Describe the steps a merge sort would take to sort a list [4]

Answer 15

Split the list in half, then split the sub lists in half [1] until all numbers are in a list of length 1 [1]

Combine the lists in pairs, in order [1] and repeat until all lists have been combined into a sorted list [1]

Question 16

Complete a merge sort on this list: [2, 9, 1, 7, 3, 6]

Answer 16

[2, 9, 1] , [7, 3, 6] #Split the list in half.
[2] [9,1] [7] [3,6] #Split again
[2] [9] [1] [7] [3] [6] # Split again. All now on their own.
[2,9], [1,7], [3,6] #Combine in pairs, in order.
[1, 2, 7, 9], [3, 6] #Combine pairs, two at a time.
[1, 2, 3, 6, 7, 9] #Sorted list

Question 17

Describe the steps an insertion sort would take to sort a list [4]

Answer 17

Look at the second item of the list. [1] If it’s smaller than the number to its left, move it left until it isn’t [1]. Repeat with each other item in the list in order [1] until all items have been sorted. [1]

Question 18

Complete an insertion sort on this list: [9, 3, 6, 2, 4]

Answer 18

9, 3, 6, 2, 4 #Initial list
3, 9, 6, 2, 4 # 3 moved left as it’s smaller than 9.
3, 6, 9, 2, 4 # 6 moved left as it’s smaller than 9, but stops as it’s not smaller than 3.
2, 3, 6, 9, 4 # 2 moved left until it hits the start as it’s smaller than 3, 6 and 9.
2, 3, 4, 6, 9 # 4 moved left as it’s smaller than 9 and 6, but stops as it’s not smaller than 3.

Question 19

Describe the steps a bubble sort would take to sort a list [4]

Answer 19

Look at items 1 and 2 in the list. [1]
If they’re not in order, swap them. [1]
Repeat the process, moving along by 1 each time until the end of the list is reached. [1]
If any swaps have been made, go back to the start of the list and repeat. [1]

Question 20

Show the steps a bubble sort would take to sort this list: 4, 5, 2, 3

Answer 20

We made some swaps, so repeat the process. We don’t need to look at the last number this time.

4, 5, 2, 3 # Initial list
(4, 5), 2, 3 # 4 and 5 are in order, so don’t swap.
4, (2, 5), 3 # 5 and 2 are not in order, so swap.
4, 2, (3, 5) # 5 and 3 are not in order, so swap.

(2, 4), 3, 5 # 4 and 2 are not in order, so swap.
2, (3, 4), 5 # 4 and 3 are not in order, so swap.

(2, 3), 4, 5 # 2 and 3 are in order, so don’t swap.

List is sorted.

Question 21

Which algorithm is this?

counter = 0
swapped = True
swaps = 0
length = list.length
while swapped == True
while counter < length-1
if list[counter] > list[counter+1] then
temp = list[counter]
list[counter] = list[counter+1]
list[counter+1] = temp
swaps = swaps + 1
endif
counter = counter + 1
endwhile
if swaps == 0 then
swapped = False
else:
swaps = 0
counter = 0
endif
endwhile

Answer 21

Bubble sort

Question 22

Which algorithm is this?

find = 11
found = False
length = list.length
lowerBound = 0
upperBound = length

while (lowerBound <= upperBound)
midpoint = int((upperBound + lowerBound))/2
if list[midPoint] == find then
print(‘Found at’ , midpoint)
found = True
endif
if list[midpoint]> find then
upperBound = midpoint-1
else
lowerBound = midpoint+1
endif
endwhile

if found == False then
print(‘Not found’)
endif

Answer 22

Binary search