2.1 Algorithms

Question 1

What are the 3 principles of computational thinking?

Answer 1

Abstraction, decomposition, algorithmic thinking

Question 2

What is abstraction and why is it used?

Answer 2

Abstraction is the process of removing unnecessary details and including only relevant details.

Abstraction is used because it simplifies a problem to make it less complex. This makes it more straightforward to understand the problem and create a solution.

Question 3

What is decomposition and why is it used?

Answer 3

Decomposition is the breaking down of a complex problem into smaller, more manageable parts.

Each individual problem can be separately tested and solved. Decomposition also enables different people to work on different parts of a larger problem that can later be recombined to produce a full solution.

Question 4

What is algorithmic thinking and why is it used?

Answer 4

Algorithmic thinking is a way of getting to a solution by identifying the individual steps needed.

By creating a set of rules, an algorithm that is followed precisely, leads to an answer. Algorithmic thinking allows solutions to be automated.

Algorithmic thinking is the final stage as logical steps are followed to solve the problem.

The problem is broken down using decomposition into smaller problems. The required data and relevant structures are considered using abstraction.

Question 5

What is an algorithm?

Answer 5

An algorithm is a set of instructions, presented in a logical sequence.

Programmers create algorithm designs as a method of planning a program before writing any code. This helps them ot consider the potential problems of the program and makes it easier to start creating source code.

There are two main methods of defining algorithms: pseudocode and flowcharts.

Question 6

Write the following in OCR pseudocode:
annotations (comments)
assignment
constants and global variables
input/output
casting
random number

Answer 6

Annotations:
//

Assignment:
name = “Gregory”
age = 62

Constants and global variables:
constant tax = 15
global name = “Admin”

input/output
name = input(“enter name”)
print(“Transaction complete”)

Casting
str(“Greg”)
int(34)
float(30)
bool(“False”)

Random number
num = random(1,100)

Question 7

Write the following in OCR Pseudocode:
Selection:
IF statements
Switch Case

Answer 7

if firstname == “steven” then
print(“hello”)
elseif firstname == “hannah” then
print(“hiya”)
else
print(“who are ya”)
endif

Selection (case select)
switch day:
case “Sat”:
print(“It is Saturday”)
case “Sun”:
print(“It is Sunday”)
default:
print(“It is a Weekday”)
endswitch

Question 8

Write the following in OCR pseudocode:
iteration:
for loop
while loop
do while loop

Answer 8

Iteration (for loop)
for i = 1 to 10 step 1
input item
next i

Iteration (while loop)
while firstname != “Steven”
firstname = input(“Try again:”)
endwhile

Iteration (do while loop)
do
firstname = input(“Guess name:”)
until firstname == “Steven”

Question 9

Write the following in OCR pseudocode:
String Handling:
length of a string
substring
concatenation
string cases
ASCII conversion

Answer 9

Length of a String
word = “dictionary”
print(word.length) outputs 10

Substrings
word = “dinosaurs”
print(word.substring(2,3)) outputs nos
print(word.left(3)) outputs din
print(word.right(4)) outputs aurs

Concatenation
name = “Penelope”
surname = “Sunflower”
print(name + surname)

String Cases
phrase = “The Cat Sat On The Mat”
print(phrase.lower)
print(phrase.upper)

ASCII Conversion
ASC(“C”) returns 67
CHR(100) returns “d”

Question 10

Write the following in OCR pseudocode:
File handling:
Read
Write

Answer 10

File Handling - Reading Lines
myFile = openRead(“sample.txt”)
x = myFile.readLine()
myFile.close()

File Handling - Reading Lines
myFile = openRead(“sample.txt”)
while NOT myFile.endOfFile()
print(myFile.readLine())
endwhile
myFile.close()

File Handling - Writing to a (New) File
myFile = openWrite(“sample.txt”)
myFile.writeLine(“Hello World”)
myFile.close()

Question 11

What is concatenation, nesting, and slicing?

Answer 11

Connecting strings together using the + symbol is called concatenation.

Extracting certain parts of a string (e.g. using .substring()) is called slicing.

An if statement within an if statement or a loop within a loop is called nesting.

Question 12

What is a flowchart used for?

Answer 12

flowchart can be used to visually represent an algorithm.

Question 13

What are the different flowchart symbols and what are they used for?

Answer 13

arrow: direction of flow
rectangle with curved corners: start/stop terminator
rectangle: process (eg calculation)
parallelogram: input/output
rectangle with two lines: subroutine
diamond: decision (if statement, loops)

Question 14

What is a structure diagram?

Answer 14

Structure diagrams display the organisation (structure) of a problem in a visual format, showing the subsections to a problem and how they link to other subsections.

Question 15

What is a trace table used for?

Answer 15

Trace tables are used to track the value of variables as a program is run.

They can be used to manually track the values in order to investigate why the program isn’t working as intended.

Each row in the trace table represents another iteration. Each column stores the value of a variable as it changes.

Question 16

How does a binary search work?

Answer 16

1. Take the middle point of the data and compare it to the value being searched for. If the midpoint matches the value, the search can be stopped.
2. If the item is lower than the midpoint, the midpoint and all the values to the right of it are discarded and you repeat with the next midpoint.
3. If the item is greater than the midpoint, the midpoint and all the vlaues to the left of it are discarded and you repeat with the next midpoint.
4. Repeat until the item is found or there is only 1 value left and the value doesn’t match and no value is returned.

Question 17

What is an advantage of binary search over linear search?

Answer 17

Binary search is generally much more efficient than linear search, especially for larger data sets, as it usually requires fewer passes than a linear search.

Question 18

What is a disadvantage of binary search over linear search?

Answer 18

Binary search has a prerequisite - it only works if the data is already sorted.

Question 19

What are the key features of a binary search?

Answer 19

1. A midpoint, lowpoint and highpoint are calculated.
2. A whileloop is used to repeatedly compare the midpoint to a target value.
3. The upper half or the lower half of the data is ignored if the midpoint does not equal the target.

Question 20

What is a linear search - how does it work?

Answer 20

starting from the beginning of a data set, each item is checked in turn to see if it is the one being searched for.

Question 21

What is an advantage of linear search (over binary search)?

Answer 21

It doesn’t require the data to be in a set order
Will work on any type of storage device
Can be efficient for smaller data sets

Question 22

What is a disadvantage of linear search?

Answer 22

Can be inefficient for larger data sets

Question 23

What are the key features of a linear search?

Answer 23

A loop is used to check the first value in a list and increment by 1, checking each value for a match to the target.
Reaching the last element of a list without finding a match means the value is not included.

Question 24

What is a bubble sort and how does it work?

Answer 24

A bubble sort sorts an unordered list of items.
It compares each item with the next one and swaps them if they are not in order.
The algorithm finishes when no swaps need to be made.
This is the most inefficient of the sorting algorithms but is easy to implement.
Very popular choice for small data sets.
Not suitable for large data sets.

Question 25

What are the key features of a bubble sort?

Answer 25

Uses an outer while loop (condition controlled) to check no swaps have been made. Uses an inner for loop (count controlled) to repeat through the length of the data set. Uses a flag (a boolean value) to track if a swap has been made and uses a temporary value to help correctly swap elements.

Question 26

What is an insertion sort and how does it work?

Answer 26

The list is logically split into sorted values (on the left) and unsorted values (on the right). Starting from the left, values from the unsorted part are checked and inserted at the correct position in the sorted part. This continues through all the elements of the list until the last item is reached, and sorted. Insertion sorts are efficient for small data sets but would be slow to sort large sets, compared to alternatives such as a merge sort. The insertion sort inserts each item into its correct position in a data set one at a time.

Question 27

What are the key features of an insertion sort?

Answer 27

Uses an outer for loop (count controlled) to iterate through each value in the list. Uses an inner while loop (condition controlled) to find the current value's correct position in the sorted part of the list. An insertion sort "moves backwards" to find the correct position of each value, by decreasing the index within the while loop.