What are examples of NP-Complete Problems? (Multiple Choice)

You are a graduate computer science student who came up with a new brute-force algorithm that can provide an optimal answer to a complex problem.  Your advisor asks you to validate if your new algorithm is NP-Complete.  

What do you need to do?

From the graph below, use the Ford-Fulkerson algorithm to determine the maximum flow obtained from vertex 0 to vertex 4 after the analysis of the following paths: {0,2,4},{0,2,3,1,4}

Below graph set of edges is defined by E = [(0,1),(1,3),(3,4),(0,2),(2,3)].  If you used Bellman-Ford's algorithm using Vertex 0 as source vertex, what is the iteration that changes the path from vertex 0 to vertex 4 to its final value?

A single iteration means a run across all edges.  Assume the first iteration starts at one (1).

The below table is the result of Dijkstra's algorithm.   Select one possible graph that can represent the original graph where the below table is obtained.  Assume the algorithm starts from vertex a.

From the chart below, what will be one of the correct traversals after conducting a Depth-First Search starting at vertex 1?

From the chart below, what will be one of the correct traversals after conducting a Breadth-First Search starting at vertex 0?

Using the below graph, show the Minimum Cost Spanning Tree resulting using Prims's algorithm after 2 iterations

Using the below graph, show the Minimum Cost Spanning Tree resulting using Kruskal's algorithm.

Based on your understanding of the algorithms discussed in class, formulate your own hypothesis for each algorithm under each scenario:

• Random arrays

• Already sorted arrays

• Reverse sorted arrays

• Arrays with many duplicate values

Rules:

• Must be written in your own words

• Must reference algorithm structure, not just Big-O

• Cannot quote or paraphrase the LLM input on stage 1

Example guidance you can give:

• Pivot selection

• Recursion depth

• Comparisons vs swaps

• Input sensitivity