Quiz 3

Question 1

What are the two main components of a graph data structure?

Answer 1

Vertices (V) and edges (E)

Question 2

How is a sparse graph defined compared to a dense graph?

Answer 2

A sparse graph has E = O(V) edges while a dense graph has E = O(V^2) edges.

Question 3

What is the runtime complexity of Kruskal’s algorithm to find the minimum spanning tree?

Answer 3

O(E log E) or O(E log V)

Question 4

What is Prim’s algorithm and how does it differ from Kruskal’s algorithm?

Answer 4

Prim’s grows a MST starting from a single root vertex, adding minimum weight edges. Kruskal’s builds up a MST by adding edges in increasing weight order without cycles.

Question 5

What is the greedy method and what are its pros and cons?

Answer 5

It optimizes locally without regard for long-term consequences. Pros: simple, efficient. Cons: often suboptimal.

Question 6

When can greedy algorithms lead to optimal solutions?

Answer 6

For problems exhibiting optimal substructure like shortest paths, minimum spanning trees.

Question 7

What is the optimal coin change problem an example of?

Answer 7

A greedy algorithm for optimization.

Question 8

What is the goal of scheduling problems like minimizing time in system?

Answer 8

To schedule jobs/tasks to optimize an objective like average completion time.

Question 9

What is the 0/1 knapsack problem?

Answer 9

Packing the most valuable set of items without exceeding a weight capacity.

Question 10

How do you select objects for the knapsack problem using the greedy method?

Answer 10

In decreasing order of value per unit weight.

Question 11

What is the purpose of backtracking and branch and bound algorithms?

Answer 11

To search a solution space represented as a tree.

Question 12

How do backtracking and branch and bound differ in traversing a state space tree?

Answer 12

Backtracking uses depth-first search while branch and bound uses breadth-first search.

Question 13

What is the optimal substructure property needed for dynamic programming?

Answer 13

Optimal solutions are built from optimal solutions to subproblems.

Question 14

What is the divide and conquer algorithm strategy?

Answer 14

Break a problem into subproblems, solve subproblems, and combine solutions.

Question 15

When is divide and conquer most useful?

Answer 15

For problems that can be recursively broken down into smaller instances like sorting, matrix multiplication.

Question 16

What is the principle of optimality for dynamic programming?

Answer 16

Optimal solutions to a problem contain optimal solutions to subproblems.

Question 17

What is the specialized principle of optimality?

Answer 17

The optimal sequence of decisions leaves subproblems optimal.

Question 18

What is the problem with greedy method on the sequential storage problem?

Answer 18

It fails if objects have different access probabilities.

Question 19

How do you optimally order files for sequential storage?

Answer 19

In increasing order of cost/probability ratio.

Question 20

What is the goal of scheduling problems like maximizing profit?

Answer 20

To schedule jobs to maximize objectives like profit within constraints.

Question 21

How do you select jobs using the greedy method for scheduling with deadlines?

Answer 21

Select the most profitable remaining job that meets its deadline.

Question 22

What is the fractional knapsack problem?

Answer 22

A knapsack problem where fractions of items can be taken.

Question 23

How do you prove the greedy method optimally solves knapsack problems?

Answer 23

By showing the residual after swapping items is always nonnegative.

Question 24

What are the different selection methods for the knapsack problem?

Answer 24

Maximum value, minimum weight, maximum value/weight ratio.

Question 25

What is the runtime complexity to implement knapsack using greedy?

Answer 25

O(n log n) for sorting + O(n) for greedy selection.

Question 26

What are the main operations for Kruskal’s algorithm?

Answer 26

Sort edges, find connected components, merge components.

Question 27

What is the A* search algorithm related to?

Answer 27

Branch and bound with a least cost heuristic.

Question 28

What is alpha-beta pruning in game trees?

Answer 28

Pruning subtrees that cannot improve the minimax value.

Question 29

What are heuristics and how are they used in backtracking and branch and bound?

Answer 29

Estimates of cost to guide tree search, like with A* algorithm.

Question 30

What is the complexity class of problems like TSP that dynamic programming can solve?

Answer 30

NP-hard

Question 31

What are the differences between top down and bottom up dynamic programming?

Answer 31

Top down uses recursion, bottom up iteratively solves subproblems.

Question 32

What problems exhibit optimal substructure for dynamic programming?

Answer 32

Problems like shortest paths, text editing distance.

Question 33

What is memoization and how does it help dynamic programming?

Answer 33

Caching results of solved subproblems to avoid re-computation.

Question 34

What are the differences between greedy and dynamic programming?

Answer 34

Greedy optimizes locally, DP globally by combining subsolutions.

Question 35

What heuristic does Dijkstra’s algorithm use to find shortest paths?

Answer 35

Minimum distance from source vertex.

Question 36

What are some examples of problems where a greedy approach finds optimal solutions?

Answer 36

Minimum spanning trees, shortest paths, Huffman coding.

Question 37

How does parallelism help overcome performance issues with dynamic programming?

Answer 37

Subproblems can be solved concurrently at each stage.

Question 38

What is the runtime complexity of Floyd-Warshall algorithm for all pairs shortest paths?

Answer 38

O(V^3)