Final Exam

Question 1

Descibe selection sort

Answer 1

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

Question 1

Describe bubble sort

Answer 1

run thru elements from smallest idx to largest

At each iteration, if the element that your inspecting is greater than the next, swap

Question 2

Describe insertion sort

Answer 2

At iteration i, make sure that the first i+1 values in the vector are sorted

Question 3

What is the run time of bubble sort

Answer 3

O(n^2)

Question 4

What is the run time of selection sort

Answer 4

O(n^2)

Question 5

What is the run time of insertion sort

Answer 5

O(n^2). However, with a “nearly” sorted vector, this can be O(n)

Question 6

What is the run time of sorting with the STL’s multiset

Answer 6

O(n log n)

Question 7

Describe heap sort

Answer 7

Uses a priority queue to sort in place

Question 8

What is the run time of heap sort

Answer 8

O(n log n)

Question 9

Describe merge sort

Answer 9

Split the vector into two equal parts, and recursively sort both parts. Merge the two sorted sub vectors as the recursion returns

Question 10

What is the run time of merge sort

Answer 10

O(n log n)

Question 11

Describe quick sort

Answer 11

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

Question 12

What is the run time of quick sort

Answer 12

O(n log n)

Question 13

Describe bucket sort

Answer 13

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.

Question 14

What is the run time of bucket sort

Answer 14

Average case: O(n)

Question 15

Describe DFS

Answer 15

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

Question 16

What is the run time of a DFS

Answer 16

O(V+E)

However, if there are more vertices than edges, O(V)
If there are more edges than vertices, O(E)

Question 17

Describe BFS

Answer 17

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

Question 18

What is the run time of a BFS

Answer 18

O(V+E)

Depends on the number of vertices and edges in a graph

Question 19

Describe Dijkstra’s algorithm

Answer 19

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.

Question 20

What is the run time of Dijkstra’s algorithm

Answer 20

O(E log V)

Question 21

List the steps of dynamic programming

Answer 21

1. Implement a recursive solution
2. Memoize recursive answers, cache them, recall when repeat recursive calls occur
3. Eliminate recursive calls, usually do this by using for loops instead
4. Eliminate or reduce the cache.

Question 22

Describe Prim’s algorithm

Answer 22

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.

Question 23

What is the run time of Prim’s algorithm

Answer 23

O(E log V)

Question 24

What is the prerequisite for using topological sort

Answer 24

Graph must be a DAG

Question 25

What is the run time of Topological sort

Answer 25

O(V+E)

Question 26

Describe the halting problem

Answer 26

Write the procedure: string halt(char *program, char *input)

The first parameter is a C++ program which when compiled will execute, reading from stdin

Halt must return in a finite amount of time, and what it returns depends on what happens when program is compiled and executes on the contents of the file input as stdin. If program finishes in a finite amount of time, halt should return ‘halt’. Otherwise, halt should return ‘infinite loop’ and exit.

This is impossible.

Question 27

Describe Kruskal’s algorithm

Answer 27

Builds the spanning tree edge by edge instead of node by node.

Start with a disjoint sets with |V| nodes. Sort all edges from min weight to max weight. Process the edges; if the edge connects two disconnected components, then add the edge to the spanning tree. Repeat until there is only 1 connected component remaining. The edges you have added to that point makes up the min spanning tree

Question 28

What is the runtime of Kruskal’s algorithm

Answer 28

O(E log E)

Question 29

What data structure is used for Prim’s algorithm

Answer 29

A multimap that is keyed on edge weight

Question 30

What data structure is used for Kruskal’s algorithm

Answer 30

Disjoint sets, and a vector of the sorted edges

Question 31

Why is Dijkstra’s algorithm potentially faster than Topological sort

Answer 31

Topological sort will process ALL edges, where Dijkstra’s won’t necessarily process all edges