Flashcards in Fundamentals of Algorithms Deck (10):
A set of instructions that can be followed to complete a task.
Removing unnecessary information from a problem to solve it.
Define the purpose of simple algorithms.
In simple terms, an algorithm has one or more inputs, some processing steps, and output, which is the solution to the problem.
Explain how the linear search algorithm works.
Used when the data is unsorted. The algorithm starts at the beginning of the list and goes through every item until the item being searched for is found.
Explain how the binary search algorithm works.
Used if the list is sorted. Works by repeatedly dividing the list in half that could contain the required item. This is continued until one item is left in the list.
Compare and contrast linear algorithms.
Linear search algorithm is inefficient for a large list. Key benefit: can be done on an unsorted list, so if items are added or deleted, doesn't need to reorder list.
Binary search is extremely efficient - each time an item is examined, half the list is discarded if it isn't the right one.
Explain how the merge sort algorithm works.
Stage 1: List is divided in half repeatedly until each sublist is one length long.
Stage 2: Each pair of sublists is repeatedly merged in order to produce new sorted sublists.
Explain how the bubble sort algorithm works.
Works by repeatedly going through the list and comparing each pair of adjacent elements. If elements are in the wrong order, they are swapped.
Compare and contrast the bubble and merge sort algorithms.
Bubble sort is slow and inefficient for sorting more than a few items.
Merge sort is a much more efficient process as it takes less time to execute.
- Difficult algorithm to implement for inexperienced programmers.
- Requires more memory to store sublists, problem for large lists.