Final Exam Flashcards
Descibe selection sort
At iteration 0, find the smallest element in the vect, swap it with the element at idx 0
At iteration 1, find the second smallest element, swap it with the element at idx 1
Repeat until sorted
Describe bubble sort
run thru elements from smallest idx to largest
At each iteration, if the element that your inspecting is greater than the next, swap
Describe insertion sort
At iteration i, make sure that the first i+1 values in the vector are sorted
What is the run time of bubble sort
O(n^2)
What is the run time of selection sort
O(n^2)
What is the run time of insertion sort
O(n^2). However, with a “nearly” sorted vector, this can be O(n)
What is the run time of sorting with the STL’s multiset
O(n log n)
Describe heap sort
Uses a priority queue to sort in place
What is the run time of heap sort
O(n log n)
Describe merge sort
Split the vector into two equal parts, and recursively sort both parts. Merge the two sorted sub vectors as the recursion returns
What is the run time of merge sort
O(n log n)
Describe quick sort
Partition the vector. Keep a left and a right pointer. Increment the left pointer until you have a value greater than or equal to the pivot, decrement the right pointer until you have a value less than or equal to the pivot. Swap the two elements, then repeat until sorted
What is the run time of quick sort
O(n log n)
Describe bucket sort
Approximate where we think each element should be in the vector. Once we have a vector that is almost sorted, use insertion sort to finish the job.
What is the run time of bucket sort
Average case: O(n)
Describe DFS
Maintain a visited field for each node. For each node on n’s adjacency list, if the next node hasn’t been visited, check its children. Continue for all nodes that appear. In a connected graph, every node will be visited.
Can be done either recursively or with a queue
What is the run time of a DFS
O(V+E)
However, if there are more vertices than edges, O(V)
If there are more edges than vertices, O(E)
Describe BFS
Use a stack. Pop a node off of the stack, do some processing on the node, push all of the node’s children onto the stack in reverse order. Repeat until the stack is empty.
BFS visits all nodes and edges, but does so in order of distance from the starting node
Use for finding the shortest hop distance between nodes
What is the run time of a BFS
O(V+E)
Depends on the number of vertices and edges in a graph
Describe Dijkstra’s algorithm
A modification to BFS. Uses a multimap, keyed on the distance from the starting node.
For all nodes, set their back links to NULL, their distances to -1, and their visited field to false. Set node 0’s distance to 0, put it on the multimap. Repeat the following:
Remove a node n from the front of the multimap, set its visited field to true. For each edge from n to n2 that hasn’t been visited, push n2 onto the multimap, set its distance, set its back link.
What is the run time of Dijkstra’s algorithm
O(E log V)
List the steps of dynamic programming
- Implement a recursive solution
- Memoize recursive answers, cache them, recall when repeat recursive calls occur
- Eliminate recursive calls, usually do this by using for loops instead
- Eliminate or reduce the cache.
Describe Prim’s algorithm
A modification of Dijkstra’s algorithm. Builds the minimum spanning tree node by node. Maintain a current spanning tree. Find the minimum edge weight from a node in the current spanning tree to a node not in it. Add that node and edge to the current tree. Keep doing this until all nodes are added to the tree.
Uses a multimap of edges, but keyed on weights of edges instead.
What is the run time of Prim’s algorithm
O(E log V)
