3.1 Funadmentals Of Algorithms Flashcards
Algorithm
Step by step sequence of instructions to achieve a goal.
Algorithm design
• Unambiguous. Clear, concise, not open to misinterpretation.
• Works correctly of all possible inputs and executes in a finite amount of time.
Flowcharts
• Alternative to pseudocode
• Must start/stop with the terminator
• Operation - assigning values, doing calculations etc
• Decisions - True of false only
• Connectors - help us split flowcharts into smaller sections.
Decomposition
Repeated breaking down of problems into smaller problems, or sub problems.
Benefits of decomposition?
• Coding tasks are kept small and manageable
• Coding tasks can be solved independently
• Subroutines can be tested independently
• Subroutines can be updated without affecting the wider program (providing its inputs and outputs aren’t changed)
Abstraction
Removing unnecessary details from a problem.
Subroutines allow abstraction:
• Once written they are just called by their name.
• The complex code in them is hidden. All we need to know is how to use them.
Benefits of abstraction?
• Removal of complexity.
• Easier to understand what is needed.
• Focus is on the relevant details.
Linear search
Scans each item in an unsorted collection one at a time.
Stops when the item is found or when the end of the collection is reached.
The average time for a search is:
Number of elements / 2
Binary search
Scans each item in a sorted collection one at a time.
Find the middle of the collection.
Compare the value with the value you are looking for.
If found, finish.
Otherwise, you know now which half the item you want is in.
Repeat the halving until found, or you have no values left to search.
Comparison between linear and binary search
• The binary search will be much quicker than a linear search.
• Linear search can work on unordered lists but binary can’t.
• Linear search is inefficient at searching large lists but binary is efficient.
Bubble sort
Given a list of values, the computer compares the adjacent pairs of elements and swaps them if they are not in the right order. It will make several passes of the list until the data is in sorted order.
Merge sort
1) Split the list into 2 sub-lists.
2) Repeat step 1 on each sub-list until all sub-lists only contain one item.
3) Merge pairs of sub lists back together. Each time you merge 2 sub-lists, sort the items into the right order.
Merge sort pros and cons
+ Efficient on large lists.
+ Running time unaffected by order of items in original list.
- Slower on small lists.
- Uses more memory in order to create sub-lists.
- Goes through whole process even if list is already sorted
Bubble sort pros and cons
+ Simple and easy to implement
+ Quick to check if a list is already sorted
+ Doesn’t need much memory, sorting only uses original list.
- Inefficient on large lists.
