2.1 - Algorithms Flashcards
What is an algorithm?
An unambiguous set of instructions for solving a problem or completing a task.
What is abstraction?
Removing unnecessary detail from a problem so that you can focus on the essential components.
What is decomposition?
Breaking down a large and complex problem into smaller and more manageable sub-manageable sub-problems.
What is algorithmic thinking?
A way of getting to the solution by identifying the individual steps needed.
What is a structure diagram used for?
Showing how a problem is broken down, along with its subsections and their links to other subsections.
How does a linear search algorithm work?
It checks each item of the list in turn to see if it is the item that’s being searched for. It stops when it find the item it’s looking for or it has checked every item in the list.
How does a binary search algorithm work?
Finds the middle item in a list (length + 1 // 2). If this is the item being searched for the search ends. If not, compare the item being searched for with the middle item. If it comes before the middle item, discard the middle item and all the items that come after it in the list. If it comes after the middle item, discard the middle item and all the items that come before it in the list. Repeat the above steps until the item is found or there are no more items to check.
How does a bubble sort work?
Look at the first two items in the list. Unless they’re in the right order, swap them. Repeat with the next pair of items in the list. Continue until you get to the end of the list (a pass). The last item should be sorted, so don’t included it in the next pass. Repeat until there are no swaps in a pass.
How does a merge sort work?
Split the list in half into sub-lists. Keep splitting each sub-lift in half until they only contain 1 item. Merge pairs of sub-lists so they have twice as many items. As you merge the sub-lists, compare the first item of each sub-list and depending on the instruction move the smallest/biggest item from the smaller list to the merged list. Repeat until the two sub-lists have merged into a sorted sub-list containing twice the number of items. Repeat until you have 1 fully sorted list.
How does an insertion sort work?
Look at the second item in a list. Compare it to all the items before it and insert the numbers into the right place. Repeat with the next item until the list until the last item has been inserted onto the correct place.
