section 5 - algorithms

Question 1

Answer 1

the beginning and the end of the algorithm are put in boxes with rounded corners - they are sometimes called terminals

Question 2

Answer 2

anything that’s put into or taken out of the algorithm goes into a parallelogram box

Question 3

Answer 3

general instructions processes and calculations go into rectangular boxes

Question 4

Answer 4

decisions often yes and no questions are put into diamond boxes

Question 5

Answer 5

sub programmes reference other flow charts

Question 6

Answer 6

arrows connect boxes and show the direction you should follow some boxes might have multiple Arrows coming in or going out of them

Question 6

flowcharts

Answer 6

can show sequences, selections, iterations or a combination of them

Question 7

sequence flowchart to calculate salary of worker after 10% pay increase

Answer 7

Question 8

selections flowchart to check if a password is valid - has more than six characters & is different from the username

Answer 8

Question 9

iterations flowchart - linear search

Answer 9

Question 10

binary search

Answer 10

1) Find the middle item in the ordered list - in a list of n items do (n + 1) ÷ 2
and round up if necessary to find middle item
2) If this is the item you’re 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 steps 1) - 3) on this smaller list to get an even smaller one. Keep going until you find the item you’re looking for.

Question 11

binary search example

Answer 11

Use the binary search algorithm to find the number 99 in the following list.
7, 21, 52, 59, 68, 92, 94, 99, 133

There are 9 items in the list so the middle item is the (9+1) ÷ 2 = 5th item. The 5th item is 68 and 68 < 99 so get rid of the first half of the list to leave:
92, 94, 99, 133

There are 4 items in the list so the middle item is the (4+1) ÷ 2 = 3th item (rounded up). The 3th item is 99

Question 12

Linear Search

Answer 12

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 that you’re looking for or you’ve checked every item

Question 13

linear search example

Answer 13

7, 21, 52, 9, 68, 92, 94, 99, 133

Question 14

linear vs binary search

Answer 14

A linear search is much simpler than a binary search but not as efficient. A linear search can be used on any type of list, it doesn’t have to be ordered. Due to it being inefficient, a linear search is often only used on small lists.

Once the list has been ordered, a binary search is much more efficient than a linear search. In general a binary search takes fewer steps to find the item you’re looking for, which makes it more suitable for large lists of items.

Question 15

Bubble sort

Answer 15

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 (the 2nd and 3rd entries) and repeat step 2). 4) Repeat step 3) 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 steps 1) - 4) until there are no swaps in a pass.

Question 16

bubble sort example

Answer 16

Question 17

Merge Sort

Answer 17

1) Split the list in half (the smaller lists are called sub-lists) the second sub-list should start at the middle item (see p.69).
2) Keep repeating step 1) 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 step 3) until you’ve merged all the sub-lists together.

Question 18

Merge Sort example

Answer 18

Question 19

bubble sort pros

Answer 19

• It’s a simple algorithm that can be easily implemented on a computer.
• It’s an efficient way to check if a list is already in order. For a list of n items you only have to do one pass of n - 1 comparisons to check if the list is ordered or not.
• Doesn’t use very much memory as all the sorting is done using the original list.

Question 20

bubble sort cons

Answer 20

• It’s an inefficient way to sort a list - for a list of n items, the worst case scenario would involve you doing n(n-1) / 2 comparisons
• Due to being inefficient, the bubble sort algorithm does not cope well well with a very large list of items.

Question 21

merge sort pros

Answer 21

• In general it’s much more efficient and quicker than the bubble sort (p.70) and insertion sort algorithms (p.72) for large lists.
• It has a very consistent running time regardless of how ordered the items in the original list are.

Question 22

merge sort cons

Answer 22

• It’s slower than other algorithms for small lists.
• Even if the list is already sorted it still goes through the whole splitting and merging proces
• It uses more memory than the other sorting algorithms in order to create the separate lists.

Question 23

insertion sort

Answer 23

1) Look at the second item in a 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, etc. items until the
last number in the list has been inserted into the correct place

Question 24

insertion sort example

Answer 24

Question 25

insertion sort pros

Answer 25

• It’s an intuitive way of sorting things and can be easily coded.
• It copes very well with small lists - for this reason, an insertion/merge hybrid sort is often used to take advantage of the strengths of each algorithm.
• All the sorting is done on the original list so, like the bubble sort, it doesn’t require very much additional memory.
• It’s very quick to add items to an already ordered list.
• It’s also very quick at checking that a list is already sorted.

Question 26

insertion sort cons

Answer 26

However, like the bubble sort, its main disadvantage is that it doesn’t cope well with very large lists. For a list containing n items:
* Best case scenario (when the list is already ordered) requires n − 1 comparisons.
* n(n-1) Worst case scenario requires comparisons.

Question 27

3 Techniques for computational thinking

Answer 27

decomposition
abstraction
algorithmic thinking

Question 28

Decompsition

Answer 28

breaking a complex problem down into smaller problems and solving each one individually

Question 29

Abstraction

Answer 29

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

Question 30

Algorithmic Thinking

Answer 30

a logical way of getting from the problem to the solution. If the steps you take to solve a problem follow an algorithm then they can be reused and adapted to solve similar problems in the future

Question 31

example of computational thinking

Answer 31

Question 32

use of computational thinking in computer science

Answer 32

Computer scientists rely on decomposition, abstraction and algorithmic thinking to help chem turn a complex problem into small problems that a computer can help them to solve.

Imagine the task is to sort a list of product names into alphabetical order:

• One part of the decomposition might decide what alphabetical order means - letters are straightforward but what if some entries in the list contain numbers and punctuation?
• Another part of the decomposition might look at comparing the entries - this could be decomposed further into how you could compare two entries, three entries, etc.
• Abstraction will help the programmer focus on the important bits - it doesn’t matter what the entries are and what they mean. The important information is the order of the characters in each entry.

Algorithmic thinking will put the tasks into a step by step process. For example, you might compare the first two entries and order them, then compare the third entry to each of the first two and put it in the correct place, then compare the fourth entry to each of the first three, etc.