Section 4 - Algorithms

Question 1

what are the 3 key techniques for computational thinking?

Answer 1

decomposition
algorithmic thinking
abstraction

Question 2

what is decomposition?

Answer 2

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

Question 3

what is abstraction?

Answer 3

picking important bits of information from a 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 follow an algorithm then they can be reused and adapted to solve similar problems in the future

Question 5

what does pseudocode do?

Answer 5

it should follow a similar structure to programming language

it should show an algorithms steps without going into to much detail.

Question 6

what are the advantages of pseudocode?

Answer 6

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

Question 7

how to carry out a binary search?

Answer 7

1. find middle item in list
2. if the item is the target, stop the search
3. if not, compare target to middle item.
   if it is too high get rid of 2nd half of list
   if too low get rid of 1st half of list
4. repeat steps 1 - 3 until item is found or until the list is gone then tell the user it is not in the list

Question 8

what does a binary search do?

Answer 8

it finds items in an ordered list

Question 9

what does a linear search do?

Answer 9

it checks each item in a list until it finds it or it has checked every item

Question 10

how to carry out a linear search?

Answer 10

1. look at 1st item and compare with target
2. if this item is the target stop the search
3. if not, look at next item
4. repeat steps 2 - 3 until the item is found or every item has been checked

Question 11

what are the advantages of a binary search over a linear search?

Answer 11

it is more efficient
it generally takes less steps than linear
it is suitable for large lists

Question 12

what are the advantages of a linear search over a binary search?

Answer 12

it is much simpler
it can be used on any type of list, it doesn’t have to be ordered
usually used on small lists because it is inefficient

Question 13

what does a bubble sort do?

Answer 13

it is used to sort an unordered list, it is simple but can take a while

Question 14

how to carry out a bubble sort?

Answer 14

1. compare first 2 items in list
2. if they are in the right order do nothing if not swap them
3. move to next pair (2 and 3) repeat step 2
4. repeat step 3 until the end of the list, the last item is now in the right place so don’t include it in the next “pass”
5. repeat steps 1-4 until there is no swaps in a pass

Question 15

what are the pros of bubble sorts?

Answer 15

simple algorithm, ca be easily implemented on a computer
its an efficient way to check if a list is in order because only 1 pass needs to be done
it doesn’t use much memory because all the sorting is done using the original list

Question 16

what are the cons of bubble sorts?

Answer 16

inefficient way of sorting a list

it doesn’t cope well with a large list

Question 17

how to conduct a merge sort?

Answer 17

1. split list in half
2. keep repeating step 1 for all sub-lists until they only contain 1 item
3. merge pairs of sub-lists, and sort the items in the right order each time they are merged
4. repeat step 3 until all the sub-lists are merged together

Question 18

what are the pros of a merge sort?

Answer 18

its faster and more efficient for large lists than other sorting algorithms
it has a consistent running time

Question 19

what are the cons of a merge sort?

Answer 19

slower than other sorts for small lists
it still does the whole process even if the list is already sorted
it uses more memory than other algorithms because it creates separate lists

Question 20

how to carry out an insertion sort?

Answer 20

1. look at 2nd item
2. compare it to all items in front of it and insert it into the right place
3. repeat step 2 for all other items in the list after the previous one until the last item has been inserted

Question 21

what are the pros of the insertion sort?

Answer 21

its intuitive and can be easily coded
its good with small lists
it doesn’t use much memory because all sorting happens in the original list
its quick to add items to an ordered list
its quick at checking a list is already sorted

Question 22

what are the cons of an insertion sort?

Answer 22

it doesn’t do well with large lists