Algorithms Flashcards
How does binary search work
Finds the middle element in a list of data before deciding which side of the data the desired element is to be found in. The unwanted half of the data is then discarded, and the process is repeated until the desired element is found or until it is known that the desired element
doesn’t exist in the data.
What must be true about a list for binary search to be true
The list must have been sorted already
How does linear search work
You can think of it as going along a
bookshelf one by one until you come across the book you’re looking for. Sometimes the
algorithm gets lucky and finds the desired element almost immediately, while in other
situations, the algorithm is incredibly inefficient.
What is the order for post order traversal
Left right root
What is the order for breadth first traversal
from top to bottom, left to right
How does bubble sort work
The bubble sort algorithm works by repeatedly going through a list of items, comparing consecutive pairs of items and swapping the items if they are in the wrong order.
Each time the algorithm goes through the list, it is called a pass and on the final pass, it checks to see if any swaps are needed, if not the list must be sorted.
How does insertion sort work
The insertion sort algorithm works by building up a sorted sub list in the first part of the original list, while the remaining part of the list remains unsorted
At the start of the algorithm, the sorted sub list contains just a single item (the first item in the list). All of the other items belong to the unsorted sub list. The algorithm goes through the unsorted sub list, item by item. As each item is examined, it is moved into the correct position (in ascending or descending order) in the sorted sub list. This progresses until the final item is correctly inserted and the list is sorted
Explain one situation where insertion sort would be better than bubble sort
On large lists, as it usually requires less comparisons per pass making it quicker and more efficient
Describe the stack data structure
A stack is a type of FILO data structure, using a pointer to point to the element currently at the top of the stack
Describe the queue data structure
A queue is a type of FIFO data structure, using two pointers.
A front pointer to points to the first element in the queue and a back pointer which points to the next empty space at the back of the queue
Give 1 similarity and one difference between stacks and queues
Similarity: Both are often implemented as arrays
Difference: stacks use 1 pointer, queues use 2
What operation are used to add and remove elements from a queue
Add: enqueue(elementName)
remove: dequeue()
What operation are used to add and remove elements from a stack
Add: push(elementName)
remove: pop()
What happens to the pointer in a stack when the stack is popped
The pointer decrements by 1, pointing to the element below
What happens to the pointers in a queue when the queue is dequeued
The front pointer incremented by 1, pointing to the next element in the list
The back pointer remains unchanged
