paper 2 - section 4

Question 1

what are the three key techniques for computational thinking?

Answer 1

1. decomposition
2. abstraction
3. algorithmic thinking

Question 2

what is decomposition?

Answer 2

breaking a complex problem down into smaller problems and solving each one 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. 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 5

how might you use decomposition to sort a list of product names into alphabetical order?

Answer 5

1. 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?
2. 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.

Question 6

how would abstraction help to sort a list of product names into alphabetical order?

Answer 6

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

Question 7

how will algorithmic thinking help to sort a list of product names into alphabetical order?

Answer 7

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.

Question 8

what is pseudocode?

Answer 8

pseudocode is not an actual programming language but it should follow a similar structure and roughly read like one. The idea is that pseudocode clearly shows an algorithm’s steps without worrying about the syntax of any particular programming language

Question 9

what are the advantages of pseudocode?

Answer 9

it is quick to write and can be easily converted into any programming language

Question 10

in a flowchart, what does an oval box mean?

Answer 10

start/stop - they’re used at the beginning and end of the algorithm

Question 11

in a flowchart, what does a parallelogram box mean?

Answer 11

inputs/outputs

Question 12

what do you use a rectangular box for in a flowchart?

Answer 12

processes

Question 13

what do you use a diamond box for in a flowchart?

Answer 13

decisions - often ‘yes’ or ‘no’ questions

Question 14

what does a shorter rectangle within a longer rectangle mean in a flowchart?

Answer 14

sub-routines

Question 15

what are arrows used for in fllowcharts?

Answer 15

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

Question 16

what are the 4 steps to a binary search algorithm?

Answer 16

1. find the middle item in the ordered list
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 17

what is the formula to find the middle item in a list of n items?

Answer 17

(n+1)/2

Question 18

what does a linear search do?

Answer 18

it checks each item of the list in turn to see if it’s the correct one. It stops when it either finds the item it’s looking for, or has checked every item.

Question 19

what are the 4 steps to a linear search algorithm?

Answer 19

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 20

what are the pros and cons of a linear search?

Answer 20

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

Question 21

what is the bubble sort algorithm used for?

Answer 21

it’s used to sort an ordered list of items

Question 22

what are the pros of the bubble sort algorithm?

Answer 22

• it’s a simple algorithm that can be easily implemented n 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 23

what are the 5 steps to the bubble sort algorithm?

Answer 23

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 (each pass will have one less comparison than the one before it.)

Question 24

what are the cons of the bubble sort algorithm?

Answer 24

• 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 with a very large list of items

Question 25

what do you always need to remember to do when completing a bubble sort algorithm?

Answer 25

you should always show a pass when nothing changes to complete the algorithm

Question 26

what are the 4 steps to a merge sort algorithm?

Answer 26

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 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 27

what are the pros of a merge sort?

Answer 27

• in general it’s much more efficient and quicker than the bubble sort and insertion sort algorithms for larger lists
• it has a very consistent running time regardless of how ordered the items in the original list are

Question 28

what are the cons of the merge sort algorithm?

Answer 28

• 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 process
• it uses more memory than the other sorting algorithms in order to create the separate lists

Question 29

give three examples of programming languages where the merge sort algorithm or variations of it is used as the primary sorting algorithm? Why is this?

Answer 29

due to its efficiency the merge sort algorithm or variations of it are used in many programming languages such as Java, Python or Perl as the primary sorting algorithm

Question 30

what is it important that you remember to show when doing a merge sort?

Answer 30

it’s important that you show the splitting process AND the merging process - if you only show the merging process then you’ve only shown half the algorithm

Question 31

what are the three steps to the insertion sort algorithm?

Answer 31

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 step 2 for the third, fourth, fifth, etc. items until the last number in the list has been inserted into the correct place.

Question 32

what are the advantages of an insertion sort?

Answer 32

• 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 33

what is the main disadvantage of an insertion sort?

Answer 33

it doesn’t cope well with very large lists

Question 34

in an insertion sort, in terms of the number of comparisons, what is the best and worse case scenario for a list of n items?

Answer 34

• best case scenario (when the list is already ordered) requires n - 1 comparisons
• worst case scenario requires (n(n-1))/2 comparisons