Tutorials
PPTs
Lecture Notes
Objective Questions
Lab ProgramsObjective Type Questions & Answers
Design and Analysis of Algorithms MCQs - Unit-4
1. What defines a greedy algorithm?
A . An algorithm that tries every possible solution to find the best one.
B . An algorithm that makes the locally optimal choice at each step.
C . An algorithm that reconsiders previous decisions based on future choices.
D . An algorithm that uses backtracking to ensure all possibilities are covered.
2. In which scenario is a greedy algorithm guaranteed to find the global optimum?
A . When the problem has overlapping subproblems and optimal substructure.
B . When the problem exhibits the property of "greedy choice property" and "optimal substructure."
C . When the problem is NP-complete.
D . When the problem can be divided into smaller instances that can be solved independently.
3. What is the "greedy choice property" in the context of greedy algorithms?
A . A global optimal solution can be arrived at by choosing the local optimum.
B . The choice made at each step is reversible.
C . The choice depends on choices made in previous steps.
D . Multiple choices are evaluated before making a decision.
4. Why might a greedy algorithm not always produce an optimal solution?
A . Because it always makes the safest choice.
B . Because it may make a choice that seems best at the moment but is not optimal overall.
C . Because it evaluates all possible choices at each step.
D . Because it uses dynamic programming.
5. Which characteristic does a problem need to have for a greedy algorithm to be applicable?
A . The problem must be divisible into smaller independent subproblems.
B . The problem should allow a global optimal solution to be assembled from local optima.
C . The problem requires the solution to consider future consequences of current decisions.
D . The problem must be solved in polynomial time.
6. What is the primary difference between dynamic programming and greedy algorithms?
A . Dynamic programming makes use of recursion, while greedy algorithms do not.
B . Greedy algorithms solve subproblems and combine their solutions; dynamic programming does not.
C . Dynamic programming solves each subproblem once and stores the result, while greedy algorithms make decisions from the given solution set without looking back.
D . Greedy algorithms are used for optimization problems, while dynamic programming is not.
7. Which of the following is a characteristic of greedy algorithms?
A . They are always the most efficient solution.
B . They can always backtrack to find the best solution.
C . They make a series of choices that are locally optimal, aiming for a global optimum.
D . They require complete knowledge of future decisions.
8. What can be a downfall of using a greedy algorithm for a particular problem?
A . They are too slow for large datasets.
B . They may not consider the overall problem, leading to suboptimal solutions.
C . They can only solve problems that can be expressed recursively.
D . They often require more memory than other algorithms.
9. What is the main objective of the job sequencing with deadlines problem?
A . To complete all jobs within their deadlines.
B . To maximize the total number of jobs done.
C . To maximize the total profit while respecting job deadlines.
D . To minimize the total time taken to complete the jobs.
10. In the context of job sequencing, what does a deadline signify?
A . The time at which a job must start.
B . The time by which a job must be completed.
C . The total duration of a job.
D . The waiting time before a job can be started.
11. Which strategy is typically used to solve the job sequencing problem using a greedy algorithm?
A . Selecting jobs in ascending order of deadlines.
B . Selecting jobs in descending order of their profits.
C . Selecting jobs in ascending order of their duration.
D . Selecting jobs randomly.
12. Why is the greedy choice property useful in solving the job sequencing problem?
A . It helps in choosing the job with the maximum duration first.
B . It ensures that jobs with earlier deadlines are always completed first.
C . It focuses on selecting jobs that offer the highest profit first.
D . It ensures all jobs are completed without overlapping.
13. What does the feasibility check involve in job sequencing with deadlines?
A . Checking if a job can be completed before its deadline after scheduling.
B . Checking if jobs overlap with each other.
C . Checking if the total duration exceeds the total available time.
D . Checking if all jobs can be completed in a single sequence.
14. Which of the following is a true statement about the job sequencing problem?
A . It can always guarantee that all jobs will be completed within their deadlines.
B . It may not be possible to complete all jobs within their deadlines.
C . There is no need to consider deadlines as long as the profit is maximized.
D . The sequence in which jobs are selected does not affect the total profit.
15. What limitation does the greedy algorithm face when solving job sequencing problems?
A . It cannot handle jobs with identical deadlines.
B . It may not always lead to the optimum solution of sequencing all jobs.
C . It requires that all jobs have different profits.
D . It must always select jobs in order of increasing profit.
16. In a job sequencing scenario, what happens if a job cannot be completed by its deadline?
A . The job is done anyway, but the profit is not counted.
B . The job is typically not included in the sequence.
C . The deadline of the job is extended to accommodate the schedule.
D . The profit of the job is reduced proportionally to the delay.
17. Which factor is NOT usually considered while applying a greedy method to job sequencing with deadlines?
A . Profit of each job
B . Duration of each job
C . Deadline of each job
D . Number of resources needed
18. What is the ideal outcome when applying a greedy approach to job sequencing with deadlines?
A . Completing all jobs irrespective of their profit.
B . Maximizing the total profit while adhering to the deadlines of as many jobs as possible.
C . Minimizing the total time taken for job completion.
D . Ensuring no two jobs overlap in the schedule.
19. What distinguishes the Fractional Knapsack problem from the 0/1 Knapsack problem?
A . Items in the Fractional Knapsack can only be taken once.
B . Items can be divided into smaller parts in the Fractional Knapsack.
C . All items must be taken in the 0/1 Knapsack.
D . The knapsack has unlimited capacity in the Fractional problem.
20. What is the main objective of the Fractional Knapsack problem?
A . To maximize the total weight of the knapsack.
B . To minimize the total weight of the knapsack.
C . To maximize the total value of items in the knapsack.
D . To minimize the total value of items in the knapsack.
21. Which strategy is typically employed to solve the Fractional Knapsack problem using a greedy method?
A . Selecting items based on maximum weight.
B . Selecting items based on maximum value.
C . Selecting items based on maximum value-to-weight ratio.
D . Selecting items based on minimum value-to-weight ratio.
22. Why is the greedy algorithm suitable for solving the Fractional Knapsack problem?
A . It always finds the globally optimal solution.
B . It efficiently utilizes the knapsack`s capacity to maximize total value.
C . It prioritizes heavier items first.
D . It requires sorting items by their weights.
23. What does the `greedy choice` involve in the Fractional Knapsack problem?
A . Taking the smallest item to save space.
B . Taking the item with the highest value first.
C . Taking the item with the highest value-to-weight ratio first.
D . Taking the item with the lowest weight first.
24. In the context of the greedy method for the Fractional Knapsack, what must be done before making selections?
A . Items must be sorted by weight in ascending order.
B . Items must be sorted by value in ascending order.
C . Items must be sorted by value-to-weight ratio in descending order.
D . Items must be divided into equal weights.
25. What is a limitation of the greedy algorithm when applied to the 0/1 Knapsack problem instead of the Fractional Knapsack?
A . It cannot guarantee the optimum solution.
B . It takes too long to compute.
C . It requires items to be divisible.
D . It must use a different sorting criterion.
26. What happens when an item is selected for inclusion in the knapsack in the Fractional Knapsack problem?
A . The item is taken in its entirety.
B . Only a fraction of the item may be taken.
C . The remaining items are re-evaluated.
D . The knapsack`s capacity is increased.
27. Which of the following scenarios best applies the Fractional Knapsack problem`s solution method?
A . Packing a bag with whole items for a camping trip where the bag`s capacity is limited.
B . Distributing resources in parts to different departments based on urgency and importance.
C . Choosing courses to meet as many graduation requirements as possible within a limited number of slots.
D . Loading cargo of various sizes and values into a ship without exceeding the weight limit.
28. What characteristic of items is irrelevant to solving the Fractional Knapsack problem using the greedy method?
A . The weight of the items.
B . The value of the items.
C . The color of the items.
D . The value-to-weight ratio of the items.
29. The main time taking step in fractional knapsack problem is ___________
A . Breaking items into fraction
B . Adding items into knapsack
C . Sorting
D . Looping through sorted items
30. Given items as {value,weight} pairs {{60,20},{50,25},{20,5}}. The capacity of knapsack=40. Find the maximum value output assuming items to be divisible and nondivisible respectively.
A . 100, 80
B . 110, 70
C . 130, 110
D . 110, 80
31. Given items as {value,weight} pairs {{40,20},{30,10},{20,5}}. The capacity of knapsack=20. Find the maximum value output assuming items to be divisible.
A . 60
B . 80
C . 100
D . 40
32. What is the primary goal of constructing a Minimum Cost Spanning Tree (MCST) in a weighted graph?
A . To find the shortest path between two specific vertices.
B . To connect all vertices with the least total edge weight without creating cycles.
C . To find the longest possible path without repeating edges.
D . To maximize the differences in weight between consecutive edges.
33. Which algorithm is a popular greedy method used to find the MCST of a graph?
A . Dijkstra’s Algorithm
B . Kruskal’s Algorithm
C . Floyd-Warshall Algorithm
D . Bellman-Ford Algorithm
34. What is the key characteristic of Kruskal’s algorithm when forming a minimum spanning tree?
A . It starts from the highest weight edges and includes them if they don`t form a cycle.
B . It begins at a chosen vertex and explores adjacent vertices progressively.
C . It sorts all edges in ascending order by weight and includes them if they don’t close a cycle.
D . It selects edges randomly until all vertices are connected without cycles.
35. In the context of MCST, what role does a "cycle" play?
A . It helps in reducing the total cost of the spanning tree.
B . It is necessary to ensure all vertices are connected.
C . It must be avoided to ensure a valid spanning tree.
D . It represents the maximum weight edge in the graph.
36. What is the objective of the Single Source Shortest Path problem?
A . To find the shortest paths from a specific source vertex to all other vertices in the graph.
B . To determine the longest path from a single source to a destination.
C . To calculate the shortest path that visits all vertices starting from a source.
D . To find a path that maximizes the total edge weights from a source to all other vertices.
37. Which algorithm is a well-known greedy method for solving the SSSP problem in graphs without negative weight edges?
A . Kruskal’s Algorithm
B . Dijkstra’s Algorithm
C . Floyd-Warshall Algorithm
D . Bellman-Ford Algorithm
38. What is a characteristic feature of Dijkstra’s algorithm?
A . It re-evaluates the shortest path tree if a shorter path is discovered.
B . It processes all vertices and edges in a random order.
C . It requires the graph to be unweighted.
D . It uses a priority queue to choose the vertex with the smallest known distance from the source.
39. How does Dijkstra’s algorithm determine the next vertex to process?
A . By selecting the vertex closest to the source based on physical distance.
B . By selecting the vertex with the smallest tentative distance to the source.
C . By choosing vertices in alphabetical order.
D . By randomly selecting any vertex that has not been processed yet.
40. In Dijkstra’s algorithm, what happens if a shorter path to a vertex is found after it has been processed?
A . The algorithm backtracks to reconsider the best path.
B . The algorithm updates the distances for all adjacent vertices.
C . The algorithm does not allow updates; the path remains fixed.
D . The priority queue is updated with the new shorter distance.
Fill in the Blanks
41. The Greedy method is a heuristic strategy used to find __________ solutions at each step, with the hope of finding a global optimum.
42. At each step of the Greedy method, a decision is made that appears to be the __________ choice at that moment.
43. Greedy algorithms do not always guarantee an __________ solution.
44. The choice made by a Greedy algorithm is based only on the information available at the __________, without considering future consequences.
45. Greedy algorithms are often used for __________ problems where a sequence of choices needs to be made.
46. The Greedy method is particularly effective when __________ subproblems can be solved independently.
47. Greedy algorithms are well-suited for problems with _____________ choices, where the locally optimal choice also leads to a globally optimal solution.
48. However, the greedy method might not always find the _____________ solution, as it focuses on short-term gains.
49. An example of a problem where the greedy method works well is finding the minimum spanning tree of a graph, using algorithms like Prim`s or Kruskal`s. Here, choosing the _____________ edge at each step contributes to the overall goal.
50. In Job Sequencing with Deadlines, each job has a __________ and a __________ associated with it.
51. The Greedy method for Job Sequencing with Deadlines involves selecting jobs based on their __________, starting with the job that has the __________ deadline.
52. If a job cannot be scheduled due to lack of available slots within its deadline, it is __________.
Relevant Materials :
☞ Design and Analysis of Algorithms MCQs - Unit-1 - [ DAA ]
☞ Design and Analysis of Algorithms MCQs - Unit-2 - [ DAA ]
☞ Design and Analysis of Algorithms MCQs - Unit-3 - [ DAA ]
☞ Design and Analysis of Algorithms MCQs - Unit-4 - [ DAA ]
☞ Design and Analysis of Algorithms MCQs - Unit-5 - [ DAA ]
Similar Materials :
☞ R - Programming MCQs - Unit-1 - [ R-Programming ]
☞ R - Programming MCQs - Unit-2 - [ R-Programming ]
☞ R - Programming MCQs - Unit-3 - [ R-Programming ]
☞ R - Programming MCQs - Unit-4 - [ R-Programming ]
☞ R - Programming MCQs - Unit-5 - [ R-Programming ]
☞ Formal Languages and Automata Theory (FLAT) MCQs - Unit-1 - [ FLAT ]
☞ Formal Languages and Automata Theory (FLAT) MCQs - Unit-2 - [ FLAT ]
☞ Formal Languages and Automata Theory (FLAT) MCQs - Unit-3 - [ FLAT ]
☞ Formal Languages and Automata Theory (FLAT) MCQs - Unit-4 - [ FLAT ]
☞ Formal Languages and Automata Theory (FLAT) MCQs - Unit-5 - [ FLAT ]
☞ PPS MCQs - Unit-1 - [ PPS ]
☞ PPS MCQs - Unit-2 - [ PPS ]
☞ PPS MCQs - Unit-3 - [ PPS ]
☞ PPS MCQs - Unit-4 - [ PPS ]
☞ PPS MCQs - Unit-5 - [ PPS ]
☞ Object Oriented Programming through Java MCQs - Unit-1 - [ OOP_JAVA ]
☞ Object Oriented Programming through Java MCQs - Unit-2 - [ OOP_JAVA ]
☞ Object Oriented Programming through Java MCQs - Unit-3 - [ OOP_JAVA ]
☞ Object Oriented Programming through Java MCQs - Unit-4 - [ OOP_JAVA ]
☞ Object Oriented Programming through Java MCQs - Unit-5 - [ OOP_JAVA ]
☞ Software Engineering MCQs - Unit-1 - [ SE ]
☞ Software Engineering MCQs - Unit-2 - [ SE ]
☞ Software Engineering MCQs - Unit-3 - [ SE ]
☞ Software Engineering MCQs - Unit-4 - [ SE ]
☞ Software Engineering MCQs - Unit-5 - [ SE ]
☞ Data Mining MCQs - Unit-1 - [ DM ]
☞ Data Mining MCQs - Unit-2 - [ DM ]
☞ Data Mining MCQs - Unit-3 - [ DM ]
☞ Data Mining MCQs - Unit-4 - [ DM ]
☞ Data Mining MCQs - Unit-5 - [ DM ]
☞ Computer Organization and Architecture (COA) Objective Question Bank-Unit-1 - [ COA ]
☞ Computer Organization and Architecture (COA) Objective Question Bank-Unit-2 - [ COA ]
☞ Computer Organization and Architecture (COA) Objective Question Bank-Unit-3 - [ COA ]
☞ Computer Organization and Architecture (COA) Objective Question Bank-Unit-4 - [ COA ]
☞ Computer Organization and Architecture (COA) Objective Question Bank-Unit-5 - [ COA ]
☞ Data Structures Objective Type Question Bank-Unit-1 - [ DS ]
☞ Data Structures Objective Type Question Bank-Unit-2 - [ DS ]
☞ Data Structures Objective Type Question Bank-Unit-3 - [ DS ]
☞ Data Structures Objective Type Question Bank-Unit-4 - [ DS ]
☞ Data Structures Objective Type Question Bank-Unit-5 - [ DS ]
☞ Database Management System Objective Type Question Bank-Unit-1 - [ DBMS ]
☞ Database Management System Objective Type Question Bank-Unit-2 - [ DBMS ]
☞ Database Management System Objective Type Question Bank-Unit-3 - [ DBMS ]
☞ Database Management System Objective Type Question Bank-Unit-4 - [ DBMS ]
☞ Database Management System Objective Type Question Bank-Unit-5 - [ DBMS ]
☞ Cyber Forensics Objective Type Question Bank-Part-2 - [ Cyber Forensics ]
☞ Cyber Forensics Objective Type Question Bank-Part-1 - [ Cyber Forensics ]
☞ Java Programming Objective Type Question Bank - [ Java Programming ]
☞ Java Programming Objective Type Questions-Part-1 - [ Java Programming ]
☞ Java Programming Objective Type Questions-Part-2 - [ Java Programming ]