2.1 Algorithms Flashcards
Decomposition
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/set of instructions to solve a problem -> as an algorithm
What do computer systems do?
Input -> process -> output
Flowcharts
Visually represent an algorithm
Flowchart: Arrow
Connects boxes
Shows flow of data through program
Flowchart: Rectangle
Process
General instructions, processes and calculations
Flowchart: Parallelogram
Input/output
Flowchart: Diamond
Decision -> YES or NO
Flowchart: Curved cornered rectangle
Terminal -> Start/Stop
Flowchart: rectangle with lines
Sub program - refers to other flowcharts
Pseudocode
Shows the outline of an algorithm without worrying about fine details (syntax)
Trace Tables
Give a simple way of testing a piece of code is working correctly
What do columns in trace tables represent?
Variables
What do rows in trace tables represent?
Values that the variable can take at a particular point in an algorithm
Standard searching algorithms
Binary
Linear
Binary Search
- Find middle term in ordered list
- If this is the item you are looking for, stop search
- If not, compare item being looked for with middle term
- If it is before the middle term, get rid of the second half of the list
- If it is after the middle term, get rid of the first half of the list
- Repeat with the smaller list until the item is found
Advantage of Binary Search
Efficient
Disadvantage of Binary Search
only works with ordered/sorted lists
Linear Search
Check each term in a sequence sequentially until the item being looked for is found
Disadvantage of Linear Search
inefficient, only can be used for small list
Standard sorting algorithms
Bubble
Merge
Insertion
Bubble Sort
- Look at first 2 terms
- If ordered move on to next pair
- If not ordered, swap them
- Repeat until you get through all the terms once = 1 pass
- Repeat until there are no swaps in a pass
Advantage of Bubble Sort
Simple algorithm, efficient to check if a list is in order, little memory used
Disadvantage of Bubble Sort
Inefficient to sort a list, doesn’t work well with large lists
Merge Sort
- Split list in half (creates 2 sub lists)
- Repeat until all the sub lists contain only 1 term
- Merge 2 sub lists together and sort into right order
- Repeat step 3 until all the sub lists have been merged together
Advantage of Merge Sort
More efficient than bubble sort and insertion sort for large lists
Disadvantage of Merge Sort
Even if the terms are already sorted, it goes through the whole process, uses lots of memory
Insertion Sort
- Look at 2nd term in list
- Compare it to the terms before it and insert number in right place
- Repeat step 2 for all terms
Advantage of Insertion Sort
Easily coded, good with small lists, quick
Disadvantage of Insertion Sort
Doesn’t cope with large lists