Algorithm and Problem Solving Quiz

What is the main goal of the Traveling Salesman Problem?

• To find the fastest route to a destination

• To find the cheapest way to travel between cities

• To find the shortest tour that visits all cities exactly once

• To find the longest path through all cities

In the Knapsack Problem, what is being optimized?

• The total cost of items

• The total value of items within a weight limit

• The total number of items

• The total weight of items

What does a greedy algorithm do?

• It explores all possible solutions

• It divides the problem into smaller subproblems

• It makes the best local choice at each step

• It uses backtracking to find solutions

Which algorithm is used to find a minimum spanning tree?

• Dijkstra's Algorithm

• Prim's Algorithm

• A* Algorithm

• Kruskal's Algorithm

What is the purpose of backtracking in problem-solving?

• To divide problems into smaller parts

• To eliminate infeasible solutions quickly

• To make decisions based on the best current option

• To find the optimal solution by exploring all paths

In the context of the subset-sum problem, what is the goal?

• To find the largest subset of numbers

• To find all possible subsets of a set

• To find a subset whose sum equals a given integer

• To maximize the sum of all elements

What is the main characteristic of divide-and-conquer algorithms?

• They use a greedy approach to find solutions

• They always find the optimal solution

• They rely on randomization to find solutions

• They break a problem into smaller instances and solve them

Which of the following is an example of a problem that can be solved using backtracking?

• Finding the shortest path in a graph

• The N-Queens problem

• Sorting an array

• Calculating the Fibonacci sequence

What is the output of a greedy algorithm when making change for 24 cents using the largest coin values?

• 24, 0

• 20, 4

• 5, 5, 5, 5, 4

• 10, 10, 1, 1, 1, 1

What does the Hamiltonian Circuit Problem involve?

• Finding the shortest path in a weighted graph

• Finding the longest path in a graph

• Finding a cycle that visits all vertices exactly once

• Finding the minimum spanning tree of a graph