2.1 Computational Thinking Flashcards
What are the three types of computational thinking? [3]
Abstraction [1] Decomposition [1] Algorithmic thinking [1]
What is abstraction? [2]
Removing unnecessary detail [1] to focus on the important parts of a problem [1]
What is decomposition? [2]
Breaking a large problem down into smaller problems [1] until the problems are small enough to solve [1]
What is algorithmic thinking? [2]
Structuring a problem so it can be solved by a computer [1] usually by making it quantitative [1]
What are the three programming constructs? [3]
Sequence [1] Selection [1] Iteration [1]
What is programming in sequence? [2]
Instructions in order [1] processed one after the other [1]
What is programming using iteration? [2]
Repeating sections of code [1] until conditions are met [1]
What is programming using selection? [2]
Choosing which code to run [1] based on a decision [1]
When writing an input in an algorithm what must we remember to do? [1]
Assign the input to a variable [1]
What is a structure diagram? [3]
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]
Describe the steps a linear search would use to look for an item in a list [4]
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]
What is the prerequisite for binary search data? [1]
It must be in order [1]
Describe the steps a binary search would use to look for an item in a list [5]
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]
Complete a binary search for the number 7 in this data:
2 4 6 7 8
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.
Describe the steps a merge sort would take to sort a list [4]
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]
Complete a merge sort on this list: [2, 9, 1, 7, 3, 6]
[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
Describe the steps an insertion sort would take to sort a list [4]
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]
Complete an insertion sort on this list: [9, 3, 6, 2, 4]
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.
Describe the steps a bubble sort would take to sort a list [4]
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]
Show the steps a bubble sort would take to sort this list: 4, 5, 2, 3
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.
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
Bubble sort
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
Binary search
