Dynamic Programming, Graph Algorithms, and NP-Completeness

Question 1

NP (complexity class)

Answer 1

“Nondeterministic Polynomial time”

• Set of all decision problems for which the instances where the answer is “yes” have efficiently verifiable proofs of the fact that the answer is indeed “yes”
• NP is the set of decision problems where the “yes”-instances can be accepted in polynomial time by a non-deterministic Turing machine

Question 2

NP-hard

Answer 2

• Class of problems which are at least as hard as the hardest problems in NP
• Problems in NP-hard do not have to be elements of NP, indeed, they may not even be decision problems

Question 3

NP-complete

Answer 3

• Class of problems which contains the hardest problems in NP
• Each element of NP-complete has to be an element of NP

Question 4

P

Answer 4

• Contains all decision problems that can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time

Question 5

Depth-First Search (DFS)

Answer 5

(top to bottom, backtrack, …)
O(|E| + |V|)
- algorithm for traversing or searching tree or graph data structures. One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking.

Question 6

Breadth-First Search (BFS)

Answer 6

(top to bottom, left to right – zig-zag)
O(|E| + |V|)
- strategy for searching in a graph when search is limited to essentially two operations: (a) visit and inspect a node of a graph; (b) gain access to visit the nodes that neighbor the currently visited node. The BFS begins at a root node and inspects all the neighboring nodes. Then for each of those neighbor nodes in turn, it inspects their neighbor nodes which were unvisited, and so on.

Question 7

Prim’s Algorithm

Answer 7

• a greedy algorithm that finds a minimum spanning tree for a connected weighted undirected graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized

Question 8

Dijkstra’s Algorithm

Answer 8

• a graph search algorithm that solves the single-source shortest path problem for a graph with non-negative edge path costs, producing a shortest path tree
• For a given source vertex (node) in the graph, the algorithm finds the path with lowest cost (i.e. the shortest path) between that vertex and every other vertex

Question 9

Kruskal’s Algorithm

Answer 9

O(|E|log|V|)
- greedy strategy is to continually select the edges in order of smallest weight and accept an edge if it does not cause a cycle

Question 10

Adjacency List

Answer 10

Space: O(|V|+|E|) (GOOD for sparse graphs)
- representation of a graph is a collection of unordered lists, one for each vertex in the graph. Each list describes the set of neighbors of its vertex
Add Vertex: O(1)
Add Edge: O(1)
Remove Vertex: O(|V| + |E|)
Remove Edge: O(|E|)
Query: O(|V|)

Question 11

Adjacency Matrix

Answer 11

Storage: O(|V|^2) (BAD for sparse graphs)
- representing which vertices (or nodes) of a graph are adjacent to which other vertices
Add Vertex: O(|V|^2)
Add Edge: O(1)
Remove Vertex: O(|V|^2)
Remove Edge: O(1)
Query: O(1)

Question 12

Topological Sort

Answer 12

O(O|V|^2) — (|V| + |E|) (efficient) using queue to store vertex w/ indegree of 0
- Defined for directed graphs
- Not unique
- Does not exist if graph has at least one cycle
- Algorithm:
1. Compute indegree of all vertices
2. Choose a vertex with indegree = 0
3. Remove vertex and edges pointing to it
4. Update indegree of vertices
5. Go to 2
Stop when all vertices are considered
Throw exception if there is a cycle (how is it detected?)