CS302 - Part 2 - Dr. Plank

The flashcards below were created by user bendable on FreezingBlue Flashcards.

1. What is bubble sort?
A sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order.  The pass is repeated until no swaps are needed, which indicates that the list is sorted.
2. What is the runtime complexity of bubble sort?
• Best case: O(n)
• Average case: O(n2)
• Worst case: O(n2)

Bubble sort is the worst of the sorting algorithms.
3. What is the algorithm for bubble sort?
• - swap_flag = true
• - for (i = v.size()-1; swap_flag && i >= 0; i--)
• -- swap_flag = false
• -- for (j = 0; j < i; j++)
• --- if (v[j] > v[j+1])
• ---- swap(v[j],v[j+1])
• ---- swap_flag = true
4. How do you recognize bubble sort?
The largest element will be the last on line 2.  The second largest will be second to last on line 3.  Etc.
5. What is selection sort?
A sorting algorithm that works by dividing the list into two sublists: At the front is the sublist of items that have been sorted, which starts off empty. At the rear is the sublist of unsorted items, which start off being the entire list.  While the unsorted list is not empty, find the smallest element, and exchange it with the first element in the unsorted list.  Then move the boundary between sorted and unsorted one space toward the rear.
6. What is the runtime complexity of selection sort?
• Best case: O(n2)
• Average case: O(n2)
• Worst case: O(n2)

bubble sort < selection sort < insertion sort
7. What is the algorithm for selection sort?
• - for (i=0; i < v.size()-1; i++)
• -- min_index = i
• -- for (j = i+1; j < v.size(); j++)
• --- if (v[j] < v[min_index])
• ---- min_index = j
• -- swap(v[i], v[min_index])
8. How do you recognize selection sort?
The smallest element is first on line 2.  The second smallest will be second on line 3.  Search for elements that have been shifted toward the rear to differentiate between selection sort and insertion sort or insertion sort with sentinel.
9. What is insertion sort?
A sorting algorithm where by elements are taken from the unsorted list and inserted into a sorted list in it's correct position.
10. What is the runtime complexity of insertion sort?
• Best case: O(n)
• Average case: O(n2)
• Worst case: O(n2)

selection sort < insertion sort < heap sort
11. What is the algorithm for insertion sort with no sentinel?
• - for (i = 1; i < v.size(); i++)
• -- e = v[i]
• -- for (j = i; j >= 1 && e < v[j-1]; j--)
• --- swap(v[j], v[j-1])
• -- v[j] = e
12. What is the algorithm for insertion sort with a sentinel?
• - // Sentinelize
• - min_index = 0
• - for (i = 1; i < v.size(); i++)
• -- if (v[i] < v[min_index]) min_index = i;
• - swap(v[0], v[min_index])
• - // Sort
• - for(i = 1; i < v.size(); i++)
• -- e = v[i]
• -- for (j = i; e < v[j-1]; j--)
• --- v[j] = v[j-1]
• -- v[j] = e
13. How do you recognize insertion sort with no sentinel?
On line 2 the smallest element isn't first and the largest element isn't last.  Search for elements that have been shifted to the rear.
14. How do you recognize insertion sort with a sentinel?
The smallest element will be first on line 2.  Search for elements that have been shifted to the rear.
15. What is heap sort?
A sorting algorithm that first builds a heap from the unsorted data.  Then, while the heap is not empty, pop the next value off of the heap and add it to the sorted list.  In-place heap sort uses a max-heap and breaks the list into two sublists.  At the front is the list of unsorted but heapified elements, which starts off being the entire list.  At the rear of the list is the sublist of sorted items, which starts off empty.  While the unsorted sublist is not empty, pop off the next largest value, and place it at the end of the unsorted list.  Then move the boundary between unsorted and sorted sublists one space toward the front.
16. What is the runtime complexity of heap sort?
• Best case: O(n * log(n))
• Average case: O(n * log(n))
• Worst case: O(n * log(n))

insertion sort < heap sort < merge sort
17. What is the algorithm for heap sort?
• - Create a heap, Q, from unsorted vector V
• - for (i = 0; i < v.size(); i++)
• -- V[i] = Q.pop()
18. How do you recognize heap sort?
The largest element will be first on line 2.  Search for other elements that have been rearranged.  If items have merely been shifted, then this could be insertion sort no sentinel.
19. What is merge sort?
A sorting algorithm that works by repeatedly dividing the list of unsorted items into two sublists, until each sublist contains only one item.  Then repeatedly merges each sublist into a larger list until all sublists have been merged into one sorted list.
20. What is the runtime complexity of merge sort?
• Best case: O(n * log(n))
• Average case: O(n * log(n))
• Worst case: O(n * log(n))

heap sort < merge sort < quick sort
21. What is the algorithm for merge sort?
• - mergesort(vector v, vector temp, int start, int size)
• -- // Base case: We have a sublist of size 1
• -- if (size == 1) return
• -- // Divide and conquer
• -- mergesort(v, temp, start, size/2)
• -- mergesort(v, temp, start+size/2, size-(size/2))
• -- // Merge
• -- temp.clear()
• -- i = start
• -- j = start + size/2
• -- while (i < start+size/2 && j < start+size)
• --- if (v[i] < v[j]) temp.push_back(v[i++])
• --- else temp.push_back(v[j++])
• -- // Get the left-overs
• -- while (i < start+size/2)
• --- temp.push_back(v[i++])
• -- while (j < start+size)
• --- temp.push_back(v[j++])
• -- // Copy temp back to v
• -- for (i = 0; i < temp.size(); i++)
• --- v[start+i] = temp[i]
22. How do you recognize merge sort?
On line 2, v[0] and v[1] will be sorted.  On line 3, v[2] and v[3] will be sorted.  On line 4 v[0..3] will be sorted.
23. What is quick sort?
A sorting algorithm that works by repeatedly partitioning the unsorted list into two.  First a pivot is picked, then all elements less than the pivot are moved in front of the pivot, and all elements greater than the pivot are moved to the rear of the pivot.  Then the pivot is placed in it's proper location.  The process is repeated on each sub-partition until the list is sorted.
24. What is the runtime complexity of quicksort?
• Best case: O(n * log(n))
• Average case: O(n * log(n))
• Worst case: O(n2) <-- rare

merge sort < quick sort < bucket sort
25. What is the algorithm for quick sort?
• - quicksort(vector v, int start, int size)
• -- if (size == 1) return
• -- pick a pivot p, swap pivot index with v[start]
• -- L = start + 1; R = start + size - 1
• -- while (L <= R)
• --- while (v[L] < p && L <= R) L++
• --- while (v[R] > p && L <= R) R--
• --- if (L < R) swap(v[L], v[R])
• -- swap(v[start],v[R])
• -- quicksort(v, start, R - start)
• -- quicksort(v, R + 1, size - (R - start) - 1)
26. How do you recognize quicksort?
???
27. What is a graph?
A graph is a data structure made up of nodes (vertices) connected by edges.  Unlike a tree, the nodes of a graph may have any number of edges connecting it to other nodes, and nodes and edges may form cycles and loops.  Edges may have an associated cost, and edge connections may be one-way (directed graphs).
28. What is a vertex?
A fundamental unit of graphs, a vertex is a node, usually represented by a circle with a label.
29. What is an edge?
The links that connect vertices (nodes) in a graph.
30. What is adjacency?
Adjacency in a graph is a relationship between a node and one or more other nodes to which it is directly connected with an edge.  If there is an edge connecting node A to node B, then node B is said to be adjacent to node A.
31. What is a directed graph?
A directed graph is a graph with one-way edges.  An edge from A -> B means that it is possible to go from A to B, but not from B to A.
32. What is an undirected graph?
A graph with two-way edges.  An edge between nodes A and B allows travel between either node in each direction.
33. What is a path?
A path on a graph is an open, alternating sequence of nodes and edges, beginning and ending with a node, where each node is incident to both the edges that precede it and the edge that follows it in the sequence, and where the nodes that precede and follow an edge are the end nodes of that edge.  A simple path has no repeated edges or nodes.
34. What is a cycle?
A cycle is a closed path on a graph that begins and ends at the same node, but that otherwise has no repeated nodes or edges.
35. What is a loop?
A loop in a graph is an edge that begins and ends at the same node.
36. What does multiedge mean?
Two or more edges that are incident to the same two nodes.
37. What is incidence?
Incidence is a relationship between a node and the edges connected that connect to it.  Two nodes connected by an edge are said to be incident to that edge, and the edge is incident to each node.
38. What is a connected component?
A subgraph where all nodes in the subgraph are reachable by each other.
39. What is a bipartite graph?
A graph that can be partitioned into two independent sets of nodes such that all the edges on the graph connect a node from one set to a node in the other set.
40. What is an adjacency list?
In a graph node data structure, an adjacency list is a list of nodes to which this node is connected via an edge.
41. What is an incidence list?
In a graph node data structure, a list of edges to which this node is connected.
42. What is an adjacency matrix?
A two dimensional boolean matrix where rows represent nodes and columns represent adjacent nodes.  An entry in the matrix indicates whether or not a node at a row is adjacent to another node at a column.  Only used for small graphs or dense graphs.
43. What is an incidence matrix?
A two dimensional matrix where rows represent nodes and columns represent edges.  Entries in the matrix indicate whether the node at a row is incident to the edge at a column.  Only used for small graphs or sense graphs.
44. What is mathematical graph notation?
A method of representing a graph that is used mostly in papers and proofs.  The graph is represented by:

• Graph: G = { V, E }
• Vertices: V = { v0, v1, v2, ... }
• Edges: E = { (v0, v3), (v2, v6), ... }
45. What is the runtime complexity of a graph with an adjacency list?
• Add node: O(1)
• Add edge: O(1)
• Remove node: O(|E|)
• Remove edge: O(|E|)
• Query: O(|V|)
46. What is the runtime complexity of a graph with an incidence list?
• Add node: O(1)
• Add edge: O(1)
• Remove node: O(|E|)
• Remove edge: O(|E|)
• Query: O(|E|)
47. What is the runtime complexity of a graph with an adjacency matrix?
• Add node: O(|V|2)
• Add edge: O(1)
• Remove node: O(|V|2)
• Remove edge: O(1)
• Query: O(1)
48. What is the runtime complexity of a graph with an incidence matrix?
• Add node: O(|V| * |E|)
• Add edge: O(|V| * |E|)
• Remove node: O(|V| * |E|)
• Remove edge: O(|V| * |E|)
• Query: O(|E|)
49. What is depth-first search?
A method for traversing a graph.  A DFS can be used to determine whether a path exists between two given nodes, or whether a cycle exists in the graph, or to explore a connected component in a graph.  A DFS can be used to find a path between two nodes, but it is not guaranteed to be the shortest or the best path.
50. What is the runtime complexity of depth-first search?
O(|E|)
51. What is the algorithm for depth-first search?
• - Push the starting node onto a vector V
• - While V is not empty
• -- Pop the next node n from V
• -- Mark n as visited
• -- If this node is our destination, quit and return a value
• -- For each unvisited adjacent node, push onto V
• - Return "destination node not found"
52. What is breadth-first search?
A method of traversing a graph.  A BFS can be used to find the shortest path between two nodes.
53. What is the runtime complexity of breadth-first search?
O(|V| + |E|)
54. What is the algorithm for breadth-first search?
• - For all nodes in the graph
• -- Set the node's backedge to NULL
• -- Set the node's distance to -1
• - Set the source node's distance to 0
• - Push the source node into a queue Q
• - While Q is not empty
• -- Pop the next node n from Q
• -- For each adjacent node adj
• --- If distance of adj is -1, or greater than n's distance + 1
• ---- Set adj's distance to n's distance + 1
• ---- Set adj's backedge to n
• ---- Push adj onto Q

When the algorithm terminates, each node contains it's shortest distance to the source node, and the path to the path to the source node can be obtained by starting with a destination node and traversing the backedges.
55. What is Dijkstra's algorithm?
A graph search algorithm that solves the cheapest-path problem for a graph with non-negative edge costs.  Often used for routing.  It does not necessarily find the shortest path, but it will find the path with the lowest cost.
56. What is the runtime complexity of Disjkstra's algorithm's?
O(|V| + |E| * log(|V|))
57. What is the algorithm for Dijkstra's algorithm?
• - For all nodes in G
• -- Set their backedges to NULL
• -- Set their cost to -1
• -- Set their visited field to false
• - Set the source node's cost to 0
• - Add the source node to a priority queue Q keyed on it's cost (0)
• - While Q is not empty
• -- Pop the next node n from Q
• -- Set n's visited field to true
• -- For each adjacent node adj
• --- Let d be the cost of reaching n plus the cost from n to adj
• --- If adj's cost is -1, or if d < adj's cost
• ---- If adj is in Q, remove it
• ---- Set adj's cost to d
• ---- Set adj's backedge to n
• ---- Add adj to Q keyed on d

When the algorithm terminates all nodes in the graph will contain their cheapest cost to reach from the source node, and their backedges will define the cheapest path.
58. What is network flow?
A method for determining connectivity through a graph, where connectivity can be thought of as flow from a source node to a sink node.  While the source has infinite flow, each edge is only capable of carrying a certain amount of flow, and the sink may receive flow from several inbound edges.
59. What is the standard maximum flow problem?
Given a directed graph in which every edge has a certain capacity c, a starting node known as the source, and an ending node known as the sink.  We are asked to find another value, f, satisfying f < c for each edge such that for every node other than the source and sink, the sum of the values associated with the edges that enter the node must equal the sum of the values leaving the node.  We call f the flow along that edge.  We are asked to maximize the sum of the values associated with the edges leaving the source, which is the total flow in the network.
60. What is the Ford-Fulkerson algorithm?
An algorithm for computing the maximum flow in a flow network.  It works by repeatedly finding an augmenting path through the network.  For each augmenting path found, the edges along that path have their residual capacity decreased by one, and their flow capacity increased by one.  Maximum flow has been obtained when no more augmenting paths can be found.  FF does not specify which algorithm to use to find the augmenting path.
61. What is the runtime complexity of Ford-Fulkerson's?
O(|E| * f); where f is the maximum flow
62. What is the algorithm for Ford-Fulkerson?
• - Assign a flow of 0 to all edges
• - While there is an augmenting path p from source to sink
• -- For every edge e along path p
• --- Add 1 to the flow of e
• --- Remove 1 from the residual capacity of e
63. What is Edmonds-Karp?
An implementation of the Ford-Fulkerson method for computing maximum flow in a network.  It is identical to FF except that EK specifically uses a BFS search algorithm to find augmenting paths.  Unlike FF, EK guarantees termination and has a runtime independent of the maximum flow.
64. What is the runtime complexity of Edmonds-Karp?
O(|V| * |E|2)
65. What is the minimum cut?
The minimum cut is the minimum number of edges that should be removed in order to disconnect a graph.
66. What is the algorithm for finding the minimum cut?
• - Find the maximum flow along the graph
• - Beginning with the source node, flag every reachable node
• - Beginning with the source node, inspect every reachable node.  If that node originally had an edge that connected it to a node that is now unreachable, then that edge is part of the minimal cut.
67. What is bipartite matching?
A method of matching nodes in a bipartite graph from one set (A) to the other set (B).  Edges are connected from A to B, and each edge is assigned a capacity of 1.  Then a source node is attached to every node of A, with infinite capacity; and a sink node is attached to every node in B.  Maximum flow is found through the graph.  Afterwards, the flow through the graph is the maximum bipartite matching from nodes in A to nodes in B.
68. What is dynamic programming?
A method for solving complex problems by breaking them down into simpler sub-problems.

Step 1: Formulate a recursive algorithm to solve a problem.  (Runtime may be exponential.)

Step 2: Augment the recursive algorithm by caching answers.  (Reduces exponential runtime to linear.)

Step 3: Figure out how to eliminate the recursive call and populate the cache with values via loops.  (Increases efficiency of linear runtime.)

Step 4: If possible, diminish the needed cache size or eliminate the cache completely.  (Increases runtime efficiency even more, as well as decreasing memory requirements.)

Steps 3 and 4 are optional, but usually represent the best solution.
69. What is topological sort?
A sorting of the nodes of an acyclic graph such that if there is an edge from node A to node B, then node A comes before node B in the sorting.  TS's are guaranteed to exist for acyclic graphs, although it is not guaranteed to be unique.

TS's are useful for scheduling, finding the shortest path, and finding the number of distinct paths between two nodes.
70. What is the runtime complexity of topological sort?
O(|V| + |E|)
71. What is the algorithm for topological sort?
• - Make a vector V of nodes in a graph that have no incoming edges
• - Make an empty vector TS to hold topologically sorted nodes
• - While V.size() > 0
• -- Pop the next node n from V, push n onto TS
• -- For each edge coming out of n
• --- If the adjacent node adj has no more incoming edges, add adj to V
• --- Remove the edge n -> adj from the graph
72. How do you use topological sort for scheduling?
A topologically sorted graph represents dependencies.
73. How do you use topological sort to find the shortest path?
• - Start with all nodes having a distance of infinity
• - Set the source node to distance 0
• - While doing TS, when removing edge A -> B, if the distance to B is shorter by going through A, then update B's distance with the new minimum.

TS can sometimes be better than Dijkstra by not maintaining a map.
74. How do you use topological sort to find the number of distinct paths to each node?
• - Add a source with only one outbound edge
• - Set the path count of all other nodes to 0
• - While doing TS, when removing an edge from A -> B, add the number of paths to A to the number of paths to B
75. What is a minimum spanning tree?
A spanning tree of a graph is a subgraph that is a tree and connects all the nodes together.  If the edges have weights, then a minimum spanning tree is the tree that minimizes the cost of visiting each node connected in the tree.  If the edges all have unique weights then it has a unique minimum spanning tree.  Otherwise, a graph may have multiple minimum spanning trees.
76. What is Prim's algorithm?
A greedy algorithm for finding a minimum spanning tree for a connected, weighted graph.
77. What is the runtime complexity for Prim's algorithm?
• Adjacency matrix: O(|V|2)
• Heap: O(|E| * log(|V|))
78. What is the algorithm for Prim's algorithm?
• - Choose a node arbitrarily and place in vector V
• - While V is not empty
• -- Pop the next node n from V, place it in tree T
• -- Find the adjacent node with the lowest weight, push it onto V

When the algorithm terminates, T contains the a minimum spanning tree
79. What is Keuskal's algorithm?
A greedy algorithm for finding a minimum spanning tree for a connected, weighted graph.
80. What is the runtime complexity of Kruskal's algorithm?
• O(|E| * log(|V|))
• -or-
• O(|E| * log(|E|))
81. What is the halting problem?
A proof that states that it is impossible to write a general-purpose program to determine if other programs halt or loop forever.  It is an example of the theoretical limitations of computability.  The proof goes like this:

1: Suppose you have a procedure "string halt(char *program, char* input) { ... }" that runs in a finite amount of time and takes as it's arguments a program and an input for that program, and returns "halt" if the program halts on the given input, or returns "infinite loop".

2: Suppose this procedure is called from the following program "main() { if (halt(argv[1],argv[1]) == "halt") while(1); }".  Where a program file name inputed to halt() is given itself as it's input.

3: Now suppose that the program is run given itself as input.  If the program halts, then it went into an infinite loop.  If the program went into an infinite loop, then it halted.  A program cannot both go into an infinite loop and halt as this is a contradiction.
82. What is the P vs. NP problem?
The P vs NP problem is an unsolved problem in computer science that asks, "If a problem can be verified by a computer in polynomial time, can that problem also be solved by a computer in polynomial time?"  P, NP, NP-Complete, and NP-Hard are criteria for classifying a problem's complexity class.
83. In P vs. NP, what is P?
P is a set of problems whose solution can be found in polynomial time.  (Ex: Here is a graph, find a path that satisfies some criteria.)
84. In P vs. NP, what is NP?
NP is the set of problems that can be verified in polynomial time.  (Ex: Here is a graph and a path, does this path satisfy some criteria? Y|N)
85. In P vs. NP, what is NP-Complete?
A set of problems that are NP, meaning that they can be verified in polynomial time, but for whom finding the solution may not be done in polynomial time.  But if we can prove that one of them can be solved in polynomial time then all of them can.
86. In P vs. NP, what is NP-Hard?
A collection of problems that are not in NP, meaning that they cannot be verified in polynomial time, and whose solutions are at least as hard as NP-Complete problems.
87. In P vs. NP, how do you prove that a problem is NP-Complete?
Step 1: Prove that the problem is in NP, by proving that a solution can be verified in polynomial time.

Step 2: Show that you can transform a known NP-Complete problem into your problem.

If you succeed, then you have proven that your problem is NP-Complete.  Otherwise, you have proven that it is not NP-Complete.
88. Which algorithm is the best for finding the fastest driving route between two points?
Dijkstra's algorithm
89. Which algorithm is the best for sorting 1,000,000 numbers uniformly distributed between 0 and 1?
Bucket sort  (Hint: "distributed between")
90. Which algorithm is the best for sorting 1,000,000 numbers distributed as an exponential whose mean is 3.500?
Bucket sort (Hint: "distributed as")
91. Which algorithm is the best for sorting 1,000,000 numbers, where we have no idea about their distribution?
Quick sort
92. Which algorithm is the best for determining the nodes in a graph reachable from a given node?
Depth-first search or Breadth-first search.
93. Which algorithm is the best for determining whether an edge connects two unconnected components in Kruskal's algorithm?
Disjoint sets
 Author: bendable ID: 250434 Card Set: CS302 - Part 2 - Dr. Plank Updated: 2015-01-20 16:59:56 Tags: cs302 Folders: computer science Description: Everything that might be on the final for CS302 -- I think Show Answers: