fundamentals of algorithms Flashcards
define the term algorithm
An algorithm is a sequence of steps that can be followed to complete a task.
define the term decomposition
breaking a large problem into smaller sub problems that are easier to understand and solve
define the term abstraction
Abstraction is the process of removing unnecessary detail from a problem.
what are the different symbols on a flowchart and what do they mean?
The oval represents the start and end.The rectangle represents any step in the process, like tasks or actions.The diamond symbol indicates a decision. parralellogram represents input/output
what is meant by the efficiency of a program?
Efficiency looks at how much time it takes to run a particular algorithm and how much space is needed
explain how linear search works
identify a search term.
Look at the first item in the list.
Compare the item with the search term.
Is the current item the same as the search term? If so, the item has been found. If not, move to the next item.
Repeat from step two until the last item in the list has been reached.
If the end of the list has been reached and the search term has not been found, then the search term is not in the list and the algorithm can stop
when do we use linear search?
is mainly usedto find the element from an unordered list.
how does binary search work?
Start by setting the counter to the middle position in the list.
If the value held there is a match, the search ends.
If the value at the midpoint is less than the value to be found, the list is divided in half, the lower half of the list is ignored and the search keeps to the upper half of the list.
Otherwise, if the value at the midpoint is greater than the value to be found, the upper half of the list is ignored and the search keeps to the lower half of the list.
The search moves to the midpoint of the remaining items. Steps 2 through 4 continue until a match is made or there are no more items to be found
what is the disadvantage of binary search?
the data has to be ordered
what are the advantages of binary search
fast
how does merge sort work
The instructions for executing a merge sort in full can be written as:
Take a list of data to be sorted.
Repeatedly split the list in half until each item is in a list of its own.
Repeat steps a-d until all lists have been merged.
Take two lists of data to be merged.
Create a new empty list for the merged items.
Repeat steps i-ii until one of the lists of items is empty:
Compare the first items of the two lists.
Place the item that is lower into the merged list in the next available position.
Then place each item from the remaining list into the merged list in order.
how does bubble sort work
Take a list of data to be sorted.
Repeat step 1 (the pass) until no swaps are made:
Repeat steps a-c for all the items in the list, starting from the first one:
Compare the item at the current position to the one next to it.
If the item at the current position is greater than the one next to it, swap the items within the list.
Go to the next item in the list.
compare merge sort to bubble sort
When comparing sorting algorithms, merge sort will generally perform much faster than a bubble sort on a list of data especially on large data sets.
Bubble sort is one of the slowest algorithms for sorting data and performs poorly in real world use, especially on large collections of data.
The downside to merge sort is that it requires more memory, often due to the new lists that need to be created.
The merge sort algorithm is also more complex to implement than bubble sort.
how can you improve the efficiency of bubble sort
Stopping once no swaps were made during a single pass
Reducing the number of comparisons by 1 after each pass
