Section Four - Algorithms

Question 1

What are the three KEY techniques for computational thinking?

Answer 1

Decomposition
Abstraction
Algorithmic Thinking

Question 2

What is Decomposition?

Answer 2

Breaking a complex problem down into smaller problems and solving each other individually

Question 3

What is Abstraction?

Answer 3

Picking out the important bits of information from the problem, ignoring the specific details that don’t matter

Question 4

What is Algorithmic Thinking?

Answer 4

A logical way of getting from the problem to the solution.

Question 5

What are two ways you can write algorithms?

Answer 5

Psuedocode

Flow diagrams

Question 6

What are Algorithms?

Answer 6

Sets of instructions for solving a problem

Question 7

Fill in the Gaps:

Flow diagrams use (1) for different (2)

Answer 7

(1) Different Boxes

(2) Commands

Question 8

What boxes are the BEGINNING and END of the algorithm put into?

Answer 8

Boxes with rounded corners

Question 9

What is put in a parallelogram box?

Answer 9

Inputs/Outputs -

Anything that is put into or taken out of the algorithm

Question 10

What boxes are INSTRUCTIONS, PROCESSES and CALCULATIONS put into?

Answer 10

Rectangular boxes

Question 11

What is put in a diamond box?

Answer 11

Decisions -

such as ‘yes’ or ‘no’ questions

Question 12

What is the purpose of ARROWS in flow diagrams?

Answer 12

Connect boxes and show the direction you should flow.

Question 13

True or False?

Boxes in flow diagrams can only have ONE arrow coming in or going out?

Answer 13

False

Boxes in flow diagrams can have MULTIPLE arrows coming in or going out of them

Question 14

What is the difference between BINARY searches and LINEAR searches?

Answer 14

A Binary Search looks for items in an Ordered List whereas a Linear Search can be used on an Unordered List.

Question 15

Fill in the Gaps:

A linear search is much (1) than a binary search but not as (2).

Answer 15

(1) simpler

(2) efficient

Question 16

What type of sort COMPARES pairs of items?

Answer 16

A Bubble Sort

Question 17

What is a bubble sort algorithm used for?

Answer 17

To sort an unordered list of items

Question 18

What are the advantages of a bubble sort algorithm?

Answer 18

It’s simple and can be easily implemented
It’s efficient to check if a list is already in order
Doesn’t use much memory

Question 19

What are the disadvantages of a bubble sort algorithm?

Answer 19

It’s inefficient to sort a list

It doesn’t cope well with large lists of items

Question 20

What is a merge sort algorithm an example of?

Answer 20

A divide-and-conquer algorithm

Question 21

True or False?

A Merge Sort SPLITS the list apart and then MERGES it back together

Answer 21

True

Question 22

What two facts does a merge sort algorithm take advantage of?

Answer 22

Small lists are easier to sort than larger lists

It’s easier to manage two ordered lists than two unordered lists

Question 23

What are the advantages of a merge sort algorithm?

Answer 23

More efficient and quicker than bubble sort and insertion sort
Very consistent running time

Question 24

What are the disadvantages of a merge sort algorithm?

Answer 24

Slower than other algorithms for small lists
Even if the list is already sorted it’ll go through the entire process
It uses more memory

Question 25

What programming languages is the merge sort algorithm (or variations) used in and why?

Answer 25

Java, Python and Perl

Because it’s efficient.

Question 26

How does an Insertion Sort work?

Answer 26

It takes each item in turn and puts it in the right place using the first item in the list as a starting point

Question 27

What are the advantages of an insertion sort algorithm?

Answer 27

Very intuitive way of sorting and can be easily coded
Copes well with small lists
Doesn’t require much additional memory
Quick to add items to the sorted list
Quick at checking the list is already sorted

Question 28

What is the main disadvantage of an insertion sort algorithm?

Answer 28

It doesn’t cope well with very large lists

Question 29

Order the four steps of a BINARY SEARCH algorithm:

• If not, compare the item you’re looking for to the middle item. If it comes before the middle item, get rid of the second half of the list. If it comes after the middle item, get rid of the first half of the list.
• Find the middle item in the ordered list.
• If this is the item you’ve been looking for, then stop the search - you’ve found it.
• You’ll be left with a list that is half the size of the original list. Repeat previous steps on this smaller list to get an even smaller one. Keep going until you find the item you’re looking for.

Answer 29

1-Find the middle item in the ordered list.

2-If this is the item you’ve been looking for, then stop the search - you’ve found it.

3-If not, compare the item you’re looking for to the middle item. If it comes before the middle item, get rid of the second half of the list. If it comes after the middle item, get rid of the first half of the list.

4-You’ll be left with a list that is half the size of the original list. Repeat previous steps on this smaller list to get an even smaller one. Keep going until you find the item you’re looking for.

Question 30

Order the four steps of a LINEAR SEARCH algorithm:

• Repeat steps 2-3 until you find the item you’re looking for or you’ve checked every item.
• Look at the first item in the unordered list
• If not, then look at the next item in the list
• If this is the item you’re looking for, then stop the search - you’ve found it.

Answer 30

1-Look at the first item in the unordered list

2-If this is the item you’re looking for, then stop the search - you’ve found it.

3-If not, then look at the next item in the list

4-Repeat steps 2-3 until you find the item you’re looking for or you’ve checked every item.

Question 31

Order the five steps of a BUBBLE SORT algorithm:

• Move on to the next pair of items (2nd and 3rd entries) and repeat the second step
• Repeat the third step until you get to the end of the list - this is called one pass. The last item will now be in the correct place, so don’t include it in the next pass.
• If they’re in the right order, you don’t have to do anything. If they’re in the wrong order, swap them.
• Look at the first two items in the list
• Repeat previous steps until there are no swaps in a pass

Answer 31

1-Look at the first two items in the list

2-If they’re in the right order, you don’t have to do anything. If they’re in the wrong order, swap them.

3-Move on to the next pair of items (2nd and 3rd entries) and repeat the second step

4-Repeat the third step until you get to the end of the list - this is called one pass. The last item will now be in the correct place, so don’t include it in the next pass.

5-Repeat previous steps until there are no swaps in a pass

Question 32

Order the four steps of a MERGE SORT algorithm:

• Repeat the third step until you’ve merged all the sub-lists together
• Merge pairs of sub-lists so that each sub-list has twice as many items. Each time you merge sub-lists, sort the items into the right order
• Split the list in half (the smaller lists are called sub-lists) - the second sub-list should start at the middle item
• Keep repeating the first step on each sub-list until all the lists only contain one item.

Answer 32

1-Split the list in half (the smaller lists are called sub-lists) - the second sub-list should start at the middle item

2-Keep repeating the first step on each sub-list until all the lists only contain one item.

3-Merge pairs of sub-lists so that each sub-list has twice as many items. Each time you merge sub-lists, sort the items into the right order

4-Repeat the third step until you’ve merged all the sub-lists together

Question 33

Order the three steps of an INSERTION SORT algorithm:

• Look at the second item in a list
• Repeat the second step for the third, fourth, fifth, etc. items until the last number in the list has been inserted into the correct place
• Compare it to all items before it (in this case just the first item) and insert the number into the right place

Answer 33

1-Look at the second item in a list

2-Compare it to all items before it (in this case just the first item) and insert the number into the right place

3-Repeat the second step for the third, fourth, fifth, etc. items until the last number in the list has been inserted into the correct place