Algorithms - 2.1

Question 1

What are the 3 key techniques for computational thinking?

Answer 1

Decomposition
Abstraction
Algorithmic thinking

Question 2

What is decomposition (2)?

Answer 2

Breaking a complex problem down into smaller problems
Solving each one individually

Question 3

What is abstraction (2)?

Answer 3

Picking out the important details from a problem
Ignoring the specific details

Question 4

What is algorithmic thinking (2)?

Answer 4

A logical way of getting the answer to a problem
Sequence of instructions which are followed step-by-step

Question 5

What are the different searches?

Answer 5

Binary search
Linear search

Question 6

What is an algorithm?

Answer 6

Set of instructions for solving a problem

Question 7

What are the different ways an algorithm can be written?

Answer 7

Pseudocode
Flowcharts

Question 8

What is pseudocode (4)?

Answer 8

Not an actual programming language but follows a similar structure
Clearly shows an algorithm’s steps without worrying about the finer details of a programming language e.g. syntax
Quick to write
Easily converted

Question 9

What is a flowchart (2)?

Answer 9

Used to represent an algorithm
Can represent sequences, selections and interations

Question 10

What does a flowchart do (4)? How is it presented (2)?

Answer 10

Shows the data that is input and output
Shows the processes
Shows the decisions
Shows the repetitions
Arrows show the flow of control, each shape has a different function

Question 11

What are the 5 different shapes and functions?

Answer 11

Start/stop - beginning or end of program = box with rounded corners (terminals)
Inputs/outputs - anything that’s put into or taken out of the algorithm = parallelogram
Processes - general instructions, calculations = rectangle
Decisions - yes/no = diamond
Sub program - reference to other flowcharts = box with lines

Question 12

What are the searching algorithms?

Answer 12

Binary search
Linear search

Question 13

When is a binary search used? How is it performed (4)?

Answer 13

With an ordered list
1. Look for middle term (n+1/2)
2. If this is the wanted item stop the search
3. If not, compare the middle value and see if it comes before or after the wanted item. If before remove second half if after remove first half
4. Repeat steps 1-4 with smaller list

Question 14

How is a linear search done?

Answer 14

Looks at each time on the list, stops when it’s found the term or has checked every item
1. Look at first item
2. If this is the item then stop the search
3. If not look at the next item
4. Repeat steps 2 - 3 until item is found or every item is checked

Question 15

Pros (2) & cons (1) of binary search:

Answer 15

More efficient
Suitable for larger lists

List needs to be ordered

Question 16

Pros (2) & cons (2) of a linear search:

Answer 16

Simpler
Can be done on any type of list

Inefficient
Suitable for only smaller lists

Question 17

What are the different sorts?

Answer 17

Bubble sort
Insertion sort
Merge sort

Question 18

How does a bubble sort work?

Answer 18

1. Look at first two items in list
2. If they’re in the right order keep the same
   If they’re in the wrong order, swap them
3. Move onto the next pair of items (2nd and 3rd) and repeat step 2
4. Repeat steps 3 until you reach the end of the list, this is called one pass
5. Repeat steps 1-4 until there are no swaps

Example:
66 21 38 15 89 49
21 66 38 15 89 49
21 38 66 15 89 49
21 38 15 66 89 49
21 38 15 66 89 49
21 38 15 66 49 89
End of first pass

Question 19

Pros (3) & cons (2) of bubble sort:

Answer 19

Simple algorithm to implement on computer
Efficient way to check, if list is already in order
Doesn’t use much memory

Inefficient way to sort a list
Not good for long lists

Question 20

How does an insertion sort work?

Answer 20

1. Look at second item in the list
2. Compare it to all items before it and insert the number into the right place
3. Repeat step 2 for the third, fourth, fifth until last number has been inserted

5|3412
35|412
345|12
1345|2
12345|

Question 21

Pros (4) & cons (1) of an insertion sort:

Answer 21

Easily coded
Copes well with small lists
Doesn’t require much memory
Quick to add items and check

Not good with larger lists

Question 22

How does a merge sort work?

Answer 22

Splits a list apart then merges it back together
1. Split the list in half
2. Keep repeating step 1 until all lists only contain 1 item
3. Then merge pairs of one by one so each list has twice the amount
4. Repeat step 3 until all lists are merged back together

Question 23

Pros (2) & cons (3) of a merge sort:

Answer 23

More efficient
Good for larger list

Slower than algorithms for smaller lists
Even if list is sorted it will still do the merge sort
Uses more memory to separate lists