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
For both stacks and queues, what must be checked before trying to remove elements
The stack or queue has to be checked to see if its empty, if not then an element can be removed
What happens to the back pointer in a queue if an element is added
The back pointer increments by one
What is meant by time complexity
Time complexity is the amount of time it takes an algorithm to solve a particular problem
What is meant by constant time complexity
The amount of time taken to complete an algorithm is independent from the number of elements inputted
O(1)
What is meant by linear time complexity
The amount of time taken to complete an algorithm is directly proportional to the number of elements inputted
O(n)
What is meant by polynomial time complexity
The amount of time taken to complete an algorithm is directly proportional to the square of the elements inputted
O(n^2)
What is meant by exponential time complexity
The amount of time taken to complete an algorithm will double with every additional item
O(2^n)
What is meant by logarithmic time complexity
The time taken to complete an algorithm will increase at a smaller rate as the number of elements inputted
What is meant by space complexity
Space complexity is the amount of storage the algorithm takes up
What is the worst and best case time complexity of linear search
worst: O(n)
best: O(1)
What is the worst and best case time complexity of binary search
worst: O(log n)
best: O(1)
What is the worst and best case time complexity of bubble sort
worst: O(n^2)
best: O(n)
What is the worst and best case time complexity of insertion sort
worst: O(n^2)
best: O(n)
What is the worst and best case time complexity of merge sort
worst: O(nlogn)
best: O(nlogn)
What is the worst and best case time complexity of quick sort
worst: O(n^2)
best: O(nlogn)
Describe the tree data structure
A tree is a connected, undirected graph with no cycles.
What is meant by a tree being undirected
Undirected means that there is no direction associated with an edge.
What is meant by a tree being connected
Connected means that there is a path from any node to any other node, and there is no node, or set of nodes, that is disconnected from the others
What is a ‘root’ in the tree data structure
The root of a tree is the start node for traversals. If the tree has a root, it is called a rooted tree.
What is a ‘branch’ in the tree data structure
A branch is a path from the root to an end point. The end point is called a leaf.
In a rooted tree data structure, what is a leaf
A leaf is a node with no children.
Describe the structure of a binary tree
A binary tree is a rooted tree where every node has at most two child nodes.
Describe the structure of a linked list
A linked list is a dynamic database structure.
Each element in a linked list is called a node. Each node stores The data relating to the element and a pointer to the next node
What does the last elements pointer in a linked list point to
null
