Fundamentals of Algorithms Flashcards
What is an algorithm?
An algorithm is a sequence of steps that can be followed to complete a task.
Define decomposition.
Decomposition means breaking a problem into a number of sub-problems, so that each sub-problem accomplishes an identifiable task, which might itself be further subdivided.
Define abstraction.
Abstraction is the process of removing unnecessary detail from a problem.
What are the advantages of linear search?
~easy to understand and implement
~more versatile
~data doesn’t need to be sorted
~Can be applied to arrays, linked lists, and other data structures without modification.
What are the disadvantages of linear search?
~slow and inefficient for large datasets
~Even if the data is sorted, Linear Search doesn’t take advantage of this, resulting in potentially unnecessary comparisons.
~Requires checking each element sequentially, which can be slow
What are the advantages of binary search?
~faster than Linear Search for large datasets
~less comparisons
~Performs well on large datasets
What are the disadvantages of binary search?
~The list or array must be sorted
~More complex to implement and understand than Linear Search
~less versatile
~more storage space as harder to code
What are the advantages of bubble sort
~suitable for small amounts of data
~easy to program
~doesn’t use as much memory
what are the disadvantages of bubble sort?
~slow
~not suitable for large amounts of data
what are the advantages of merge sort
~quick
~suitable for large amounts of data
what are the disadvantages of merge sort
~unsuitable for small amounts of data
~hard to program
~uses lots of memory when a bigger list
what is linear search?
Linear search, also known as sequential search, is a simple searching algorithm that checks each element of a list in order until a match is found or the entire list has been traversed.
what is merge sort?
A sorting algorithm that repeatedly passes through a list to be sorted, comparing and swapping items that are in the wrong order. The merge sort algorithm repeatedly divides a list into two until all the elements are separated individually.
what is binary search?
A binary search is a way of looking for a piece of data in an ordered list by continually splitting the list in half. You then check the middle number and work out which half of the list the value to find it.
what is bubble sort?
It is a simple sorting algorithm that repeatedly steps through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed.
