Section 4 - Algorithms Flashcards
What are the three techniques for computational thinking?
Decomposition, algorithmic thinking, abstraction
What is decomposition?
Breaking down a complex problem into smaller problems and solving each one individually.
What is 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.
What is abstraction?
Picking out the important bits of information from the problem, ignoring the specific details that don’t matter.
What is an algorithm?
A set of instructions for solving a problem, that can be in the from of pseudocode or flow charts
Advantages of pseudocode?
- Quick to write
- Easy to convert into any programming language
What is the oval for in pseudocode?
Beginning/end
What is the parallelogram for in pseudocode?
Inputs/outputs
What is the rectangle for in pseudocode?
General instructions, processes and calculations
What is the diamond for in pseudocode?
Decisions
What is the rectangle with lines for in pseudocode?
Sub routines - reference to other flow diagrams
What is the arrow for in pseudocode?
Connecting boxes and showing direction
What is a sequence?
A set of instructions in a specific order
What is selection?
A section of code that is only run if certain conditions are met
What is iteration?
Repeating steps or instructions in a loop until certain conditions are met
How does a binary search work?
- Find the middle item in the list
- If this is what you are looking for, you’ve found it, stop
- If not, compare the middle item with the desired number. If it’s larger than the middle, get rid of the first half. If it’s smaller than the middle, get rid of the second half.
- Keep repeating until you find the item that you are looking for
Disadvantages of a binary search?
- Must be in an ordered list
Different types of search algorithms?
- Binary search
- Linear search
Disadvantages of linear search?
- Very slow as every value must be checked
Advantages of linear search?
- Can be done on an unordered list
- Simpler than a binary search
How does a linear search work?
- Look at the first item in the list
- If this is the right item, stop.
- If not, look at the next item in the list
- Repeat step 2-3 until you have checked every item
Types of sort algorithms?
- Merge sort
- Bubble sort
- Insert sort
Advantages of the bubble sort?
- Simple algorithm that can be easily implemented
- Does not use much memory as sorting is done using the original list
Disadvantages of the bubble sort?
- Inefficient
- Does not cope with larger lists
How does a bubble sort work?
- Look at the first two items in the list
- If they are in the wrong order, swap them
- Move onto the next pair and repeat step 2
- Repeat these until you get to the end of the list, this is called one pass
- Repeat until there are no swaps
How does a merge sort work?
- Split the list in half
- Keep splitting each sub-list until each sub-list only has one item
- Merge pairs of sub-lists so each one has twice as many items
- Sort the items into the right order when you merge one
- Repeat until they are all merged together in the right order
Advantages of the merge sort?
- Efficient and quick for large lists
- Very consistent running time regardless of how they are originally ordered
Disadvantages of the merge sort?
- Slower than other algorithms for small lists
- Even if the list is sorted, it goes through the process
- Uses more memory because it creates separate files
How does an insertion sort work?
- Look at the second item in the list
- Compare it to all items before it and insert the number into the right place.
- Repeat for all the values until they are in the correct place
Advantages of insertion sort?
- Can be easily coded
- Copes well with small lists
- Needs no additional memory as done on the original list
- Quick to add items to an already ordered list
- Quick at checking that a list is already sorted
Disadvantage of insertion sort?
- Not good with bigger lists
