UNIT - I: Notation of an Algorithm

1. Define an algorithm.
An algorithm is a step-by-step procedure to solve a specific problem in a finite amount of
time.
2. What is algorithmic problem solving?
It involves designing and analyzing methods to solve computational problems efficiently.
3. What is the importance of analyzing algorithm efficiency?
To evaluate the performance of algorithms in terms of time and space complexity.
4. Define order notation (Big-O notation).
Big-O notation describes the upper bound of an algorithm's growth rate as input size
increases.
5. List any two properties of order notations.

6. What is the time complexity of the Towers of Hanoi problem?

O(2n)O(2^n)O(2n), where nnn is the number of disks.
7. Differentiate between recursive and non-recursive algorithms.
Recursive algorithms call themselves; non-recursive algorithms use iterative approaches.
8. Define the divide-and-conquer technique.
It solves a problem by dividing it into smaller subproblems, solving them independently, and
combining their solutions.
9. State the Master’s Theorem.

10. Give one example of a divide-and-conquer algorithm.

Merge Sort.
11. What is binary search used for?
To efficiently search for an element in a sorted array.
12. Mention one application of Strassen’s matrix multiplication.
It is used in computational geometry and computer graphics.
13. How many comparisons are required to find the maximum and minimum in an array?
3n/2−23n/2 - 23n/2−2 comparisons for nnn elements.
UNIT - II: Greedy Method
1. What is the greedy method?
A problem-solving technique that makes the locally optimal choice at each step.
2. Define control abstraction in the greedy method.
It refers to the general framework for implementing greedy algorithms.
3. Give one application of the greedy method.
Minimum-cost spanning tree.
4. What is the objective of the knapsack problem?
To maximize the total value of items placed in a knapsack without exceeding its capacity.
5. Define job sequencing with deadlines.
It schedules jobs to maximize profit within their respective deadlines.
6. Name two algorithms used for finding minimum-cost spanning trees.
o Prim's Algorithm
o Kruskal's Algorithm.
7. State Dijkstra's algorithm.
It finds the shortest path from a source vertex to all other vertices in a graph with non-
negative weights.
8. What is the purpose of a minimum-cost spanning tree?
To connect all vertices of a graph with the minimum total edge cost.
9. Differentiate between Prim's and Kruskal's algorithms.
o Prim's starts from a vertex and grows the MST.
o Kruskal's considers edges in ascending order of weight.
10. Which algorithm is used for the single-source shortest path problem?
Dijkstra’s algorithm.

UNIT - III: Dynamic Programming

1. What is dynamic programming?
A technique to solve problems by breaking them into overlapping subproblems and storing
their solutions.
2. Define control abstraction in dynamic programming.
It provides a general structure for implementing dynamic programming solutions.
 3. List one difference between dynamic programming and the greedy method.
Dynamic programming solves subproblems optimally, while greedy may not always lead to
the optimal solution.
4. What is the objective of the traveling salesperson problem?
To find the shortest possible route that visits each city once and returns to the origin city.
5. What is an optimal binary search tree?
A binary search tree that minimizes the total search cost.
6. Define reliability design.
It ensures that systems are designed to achieve maximum reliability under given constraints.
7. What is the chained matrix multiplication problem?
It finds the optimal way to parenthesize a sequence of matrices to minimize the number of
scalar multiplications.
8. State Bellman-Ford’s algorithm.
It computes shortest paths from a single source in a weighted graph, even with negative
edge weights.
9. Name one algorithm for solving the all-pairs shortest path problem.
Floyd-Warshall algorithm.
10. What is the significance of the 0/1 knapsack problem?
It models decision-making scenarios where items must be chosen entirely or left out.

UNIT - IV: Backtracking

1. What is backtracking?
A method to solve problems by exploring all possible solutions and abandoning those that
fail to satisfy constraints.
2. Define control abstraction in backtracking.
It outlines a framework for recursive exploration of solution spaces.
3. State the 8-queens problem.
Place 8 queens on a chessboard such that no two queens threaten each other.
4. What is the sum of subsets problem?
Find subsets of a set whose elements sum up to a given value.
5. Define graph coloring.
Assign colors to vertices of a graph so that no two adjacent vertices share the same color.
6. Mention one use case for Hamiltonian cycles.
Route optimization in transportation networks.
7. What is the basic principle behind backtracking algorithms?
It explores all possible solutions recursively and abandons infeasible ones.
 8. Differentiate between forward search and backtracking.
Forward search only expands paths, while backtracking explores and retracts as needed.
9. What is a feasible solution in backtracking?
A solution that satisfies all constraints.
10. Which technique is used to solve the N-queens problem?
Backtracking.

UNIT - V: Branch and Bound & NP-Hard/NP-Complete

1. What is branch and bound?
A method for solving optimization problems by dividing them into smaller subproblems.
2. Define control abstraction in branch and bound.
It outlines the process of systematically exploring solution spaces using bounding functions.
3. What is the 15-puzzle problem?
A sliding puzzle where tiles are rearranged to achieve a target configuration.
4. Differentiate between LC and FIFO branch-and-bound solutions.
o LC uses a priority queue to explore promising solutions first.
o FIFO explores solutions in the order they were generated.
5. What is an NP-hard problem?
A problem for which no polynomial-time solution exists unless P=NPP = NPP=NP.
6. Define an NP-complete problem.
A problem that is both NP-hard and verifiable in polynomial time.
7. State Cook’s theorem.
It states that the Boolean satisfiability problem (SAT) is NP-complete.
8. What is a non-deterministic algorithm?
An algorithm that can explore multiple computational paths simultaneously.
9. What is the relationship between NP-hard and NP-complete problems?
All NP-complete problems are NP-hard, but not all NP-hard problems are NP-complete.
10. What is the purpose of proof by reduction?
To show that solving one problem can solve another problem efficiently.