Student’s Name………………………………… Roll No.
VIVEKANANDA COLLEGE OF TECHNOLOGY AND MANAGEMENT, ALIGARH
QUIZ NO. IV set A
Course with Branch: B.Tech (CSE/IT) Session: 2024-25 Year/Semester: 3rd/5
Subject with Code: BCS 503 Time: 20 min. Max. Marks: 10
1. What is the main purpose of the Knapsack problem in dynamic programming?
A) To find the shortest path B) To maximize the total value in a knapsack
C) To color a graph D) To solve Hamiltonian cycles
2. Which algorithm is used to find the shortest paths between all pairs of nodes?
A) Dijkstra’s Algorithm B) Floyd-Warshall Algorithm
C) Prim’s Algorithm D) Kruskal’s Algorithm
3. What does the Travelling Salesman Problem aim to solve?
A) Finding the shortest path in a graph B) Visiting each city exactly once with minimum cost
C) Maximizing profit in resource allocation D) Coloring a graph with minimum colors
4. Which of the following is a backtracking problem?
A) Knapsack Problem B) Hamiltonian Cycle C) Floyd-Warshall D) Resource Allocation
5. What is the time complexity of the Floyd-Warshall algorithm?
A) O(V^2) B) O(V^3) C) O(V log V) D) O(V^4)
6. In the context of backtracking, what does the n-Queens problem involve?
A) Placing n queens on a chessboard B) Finding Hamiltonian cycles
C) Coloring a graph D) Solving the knapsack problem
7. Which of the following is NOT a characteristic of dynamic programming?
A) Optimal substructure B) Overlapping subproblems
C) Greedy choice property D) Memoization
8. What is the main goal of the Resource Allocation Problem?
A) Maximizing the total value B) Minimizing the cost
C) Allocating resources efficiently D) Finding the shortest path
9. Which algorithm is commonly used for graph coloring?
A) Dijkstra’s Algorithm B) Backtracking C) Floyd-Warshall D) Kruskal’s Algorithm
10. What is the Sum of Subsets problem?
A) Finding the maximum subset sum B) Finding subsets that sum to a specific value
C) Maximizing profit in knapsack D) Coloring a graph
1 2 3 4 5 6 7 8 9 10
Marks Obtained…………………….. Signature of Teacher………………………………..
