Algorithms Flashcards
What is decomposition?
Breaking a complex problem down into smaller problems and solving each one individually
What is abstraction?
Picking out the important parts of information from the problem, ignoring the specific details that don’t matter
What is algorithmic thinking?
A logical way of getting from the problem to the solution
What are algorithms?
Sets of instructions for solving a problem
What are the advantages of pseudo-code?
1) quick to write
2) can be easily converted into any programming language
How can algorithms be shown?
1) pseudo-code
2) flowcharts
What box is used to show the beginning and the end of an algorithm?
Boxes with rounded corners
What box is used to show anything that’s put into or taken out of the algorithm?
Parallelogram boxes
What box is used to show general instructions, processes and calculations?
Rectangular boxes
What box is used to show decisions, often a ‘yes’ or ‘no’ question?
Diamond boxes
What are subroutine boxes references to?
Other flowcharts
What do the arrows in flowcharts show?
The direction you should follow
What can flowcharts show?
1) sequences
2) selections
3) iterations
What type of lists are binary searches used for?
Ordered lists
How does a binary search algorithm work?
1) find the middle item in the ordered list
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 to 3 on the smaller list to get an even smaller one. Keep going until you find the item you’re looking for
What type of lists are linear searches used for?
1) ordered lists
2) unordered lists
How does a linear search work?
A linear search checks each item of the list in turn to see if it’s the correct one. It stops when it either finds the item it’s looking for, or has checked every item
What is the bubble sort algorithm used for?
To sort an unordered list of items
How does a bubble sort algorithm work?
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 pass
5) repeat steps 1 to 4 until there are no swaps in a pass
What are the advantages of the bubble sort algorithm?
1) it’s a simple algorithm that can be easily implemented on a computer
2) it’s an efficient way to check if a list is already in order
3) doesn’t use much memory as all the sorting is done using the original list
What are the disadvantages of the bubble sort algorithm?
1) it’s an inefficient way to sort a list
2) due to being inefficient, the bubble sort algorithm is pretty slow for very large lists of items
How does the merge sort algorithm work?
1) split the list in half (the smaller lists are called sub-lists) - the second sub-list should start at the middle item
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
What are the advantages of the merge sort algorithm?
1) it’s much more efficient and quicker than the bubble sort algorithm for large lists, and has a similar running time for short lists
2) it has a very consistent running time regardless of how ordered the items in the original list are
What are the disadvantages of the merge sort algorithm?
1) even if the list is already sorted it still goes through the whole splitting and merging process, so a bubble sort may be quicker in some cases
2) it uses more memory than the bubble sort because it has to create additional lists
