section 5 - algorithms Flashcards
the beginning and the end of the algorithm are put in boxes with rounded corners - they are sometimes called terminals
anything that’s put into or taken out of the algorithm goes into a parallelogram box
general instructions processes and calculations go into rectangular boxes
decisions often yes and no questions are put into diamond boxes
sub programmes reference other flow charts
arrows connect boxes and show the direction you should follow some boxes might have multiple Arrows coming in or going out of them
flowcharts
can show sequences, selections, iterations or a combination of them
sequence flowchart to calculate salary of worker after 10% pay increase
selections flowchart to check if a password is valid - has more than six characters & is different from the username
iterations flowchart - linear search
binary search
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.
binary search example
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
Linear Search
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
linear search example
7, 21, 52, 9, 68, 92, 94, 99, 133
linear vs binary search
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.
Bubble sort
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.
bubble sort example
Merge Sort
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.
Merge Sort example
bubble sort pros
- 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.
bubble sort cons
- 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.
merge sort pros
- 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.
merge sort cons
- 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.
insertion sort
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
insertion sort example
insertion sort pros
- 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.
insertion sort cons
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.
3 Techniques for computational thinking
decomposition
abstraction
algorithmic thinking
Decompsition
breaking a complex problem down into smaller problems and solving each one individually
Abstraction
picking out the important bits of information from the problem, ignoring the specific details that don’t matter
Algorithmic Thinking
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
example of computational thinking
use of computational thinking in computer science
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.
