JIMMA UNIVERSITY

AGARO CAMPUS

COMPUTER SCIENCE DEPARTMENT

YEAR 3 SEMESTER 2

Final Exam: Algorithm Design and Analysis

Time Allotted: 1:30 hr.

Full Name: _________________________________

ID: ____________

 Total Points: 50%

 Number of Questions: 25
 All questions are multiple choice (2 points each)
 Provide the answer on the answer sheet only
 Do not write a piece of word on question sheet

Instructions: Choose the single best answer for each question.

1. Which of the following best describes a greedy algorithm?

A. It makes the locally optimal choice at each step, hoping to find a globally minimum solution.

B. It makes the locally optimal choice at each step, hoping to find a globally optimal solution.

C. It divides the problem into independent subproblems and solves them recursively.

D. It makes the locally optimal choice at each step, hoping to find a globally maximum solution.

2. In the job scheduling problem with deadlines (each job takes 1 unit of time), what is the first step
of the greedy algorithm?

A. Sort jobs by deadline in ascending order.

B. Sort jobs by profit in descending order.

C. Sort jobs by weight in ascending order.

D. Assign each job to the earliest available time slot.

1
Use the job scheduling problem below to answer the following Q3 and Q4:

Job Deadline Profit

J1 3 50
J2 1 30
J3 2 80
J4 3 40
J5 4 60
J6 2 20
J7 4 70

3. What is the total maximum profit achievable using the greedy job scheduling algorithm?
A. 200 B. 240 C. 250 D. 260

4. For the same job set in Question 3, what is the optimal job sequence (order of execution)?

A. J3, J5, J7, J1 B. J3, J7, J5, J4

C. J3, J7, J5, J1 D. J1, J3, J5, J7

5. In Kruskal's algorithm for finding a Minimum Spanning Tree (MST), what condition must be
checked before adding an edge?

A. The edge connects to the starting vertex.

B. The edge does not create a cycle.

C. The edge has the largest weight among remaining edges.

D. The edge connects two vertices already in the tree.

6. Consider a graph with vertices {A, B, C, D, E} and edges: A-B(2), B-C(3), A-C(1), C-D(4), D-E(5),
B-E(6). What is the total weight of the MST using Kruskal's algorithm?

C B

E
D

2
A. 12 B. 15 C. 14 D. 16

7. Prim's algorithm starts from an arbitrary vertex and repeatedly adds the:

A. Heaviest edge connecting the tree to a new vertex.

B. Smallest weight edge that does not create a cycle, regardless of connection.

C. Smallest weight edge connecting the tree to a vertex not yet in the tree.

D. Longest path from the root to a leaf.

8. Dijkstra’s algorithm is used to solve:

A. The minimum spanning tree problem.

B. The single-source shortest path problem in a graph with non-negative weights.

C. The job scheduling problem.

D. The traveling salesman problem.

9. Which of the following is NOT a valid application of a Minimum Spanning Tree?

A. Designing a low-cost network of cables connecting cities.

B. Finding the shortest path between two specific cities.

C. Designing a water pipeline system for a new housing development.

D. Connecting all nodes in a cluster with minimal wiring.

10. What is the key difference between dynamic programming and the greedy approach?

A. Greedy always gives the optimal solution, but dynamic programming does not.

B. Dynamic programming considers all possible solutions (or overlapping subproblems) and picks the
best, while greedy makes local choices.

C. Greedy uses a table to store results, while dynamic programming does not.

D. Dynamic programming cannot solve optimization problems.

11. In a multistage graph shortest path problem using the forward approach, we compute:

A. The shortest path from the source to each vertex.

B. The shortest path from each vertex to the sink.

C. The longest path from source to sink.

3
D. The minimum spanning tree of the graph.

12. Breadth First Search (BFS) uses which data structure to manage unexplored vertices?

A. Stack B. Priority queue C. Queue D. Array

13. Which statement is true about Depth First Search (DFS)?

A. It explores all neighbors of a vertex before moving deeper.

B. It uses a queue to manage the traversal order.

C. It goes as deep as possible along a path before backtracking.

D. It guarantees the shortest path in an unweighted graph.

14. In the 0/1 knapsack problem, the “0/1” means:

A. Items can be taken fractionally (0 to 1 of an item).

B. Each item is either taken entirely (1) or left behind (0).

C. The knapsack can hold at most 1 item.

D. The total weight must be exactly 0 or 1.

15. Given the following items and knapsack capacity W = 7:

- Item 1: weight 1, value 1

- Item 2: weight 3, value 4

- Item 3: weight 4, value 5

- Item 4: weight 5, value 7

What is the maximum total value achievable?

A. 8 B. 9 C. 10 D. 7

16. For the same item set in Question 15, which items are selected in the optimal solution?

A. Item 1 and Item 4 B. Item 2 and Item 3

C. Item 3 and Item 4 D. Item 1, Item 2, and Item 3

17. A dynamic programming table for 0/1 knapsack has rows representing _____ and columns
representing _____.

A. items; remaining capacity B. items; total profit

C. weights; values D. subproblems; final solution

4
18. The time complexity of a standard dynamic programming solution for 0/1 knapsack with n
items and capacity W is:

A. O(n) B. O(W) C. O(n W) D. O(2^n)

19. Backtracking is best described as:

A. A greedy approach that always picks the best next step.

B. A divide-and-conquer algorithm without recursion.

C. A recursive technique that tries to build a solution incrementally and undoes choices that lead to dead
ends.

D. A dynamic programming technique that stores all subproblem results.

20. In the N-Queens problem, backtracking prunes (cuts off) a branch when:

A. A queen is placed in the first row.

B. Two queens share the same diagonal or column.

C. All queens are placed successfully.

D. The board size is odd.

21. Graph coloring using backtracking: a partial assignment is invalid if:

A. A vertex has no color assigned.

B. Two adjacent vertices share the same color.

C. The number of colors used exceeds k.

D. All vertices are colored.

22. A Hamiltonian cycle is a cycle that:

A. Uses every edge exactly once.

B. Uses every vertex exactly once and returns to the start.

C. Uses the minimum total edge weight.

D. Uses at most half the vertices.

23. Which problem is NP-hard, making backtracking practical only for small instances?

A. Job scheduling with deadlines

B. Finding an MST using Prim’s algorithm

5
C. The Traveling Salesman Problem (TSP)

D. The shortest path in a multistage graph

24. In backtracking for the 0/1 knapsack, when is a branch pruned?

A. When the current total value exceeds the best known value.

B. When the current total weight exceeds the capacity.

C. When all items are included.

D. When the current weight is zero.

Answer the 25th question based on the below Multistage Graph with 7 Stages (Stage 1 = S,
Stage 7 = T)

25. What is the shortest path cost from S to T?

A. 78 B. 82 C. 85 D. 91