UNIT - 01

1. Define algorithm complexity.

Algorithm complexity means how much time and how much memory an algorithm
needs to complete a task.

2. What is the Greedy Method?

Greedy Method means choosing the best option at every step without thinking about future
steps.

3. Give one example of Greedy technique.

Activity Selection Problem:

Choose the activity that finishes earliest so you can do more activities.

4. What is dynamic programming?

Dynamic Programming is a method where we break a big problem into small problems,
solve them once, and store the answers so we don’t repeat work.

5. Define optimal substructure property.

A problem has this property if the best answer can be made by joining best answers of
small parts of the problem.

6. What is overlapping subproblems?

It means the same small problem repeats again and again.

DP saves the answer so we don’t solve it again.

7. What is backtracking?

Backtracking means trying one option, and if it is wrong, go back and try another option.

8. Real-life example of backtracking.

Finding the way in a maze:

If one path is wrong, you go back and try another path.

9. Define branch and bound.

Branch and Bound is a method where we divide the problem into parts and remove the
parts that cannot give the best answer.

10. Difference between backtracking and branch & bound.

  Backtracking removes wrong choices.
 Branch & Bound removes choices that are not the best.
Backtracking = correct solution
Branch & Bound = best (minimum/maximum) solution

11. What is a memory model?

A memory model shows how a computer stores and uses data in memory while running a
program.

12. What is a linked list?

A linked list is a chain of nodes.

Each node has data and address of the next node.

13. Advantages of linked lists.

 Easy to add or remove items.

 Memory is used only when needed.
 No need for continuous memory like arrays.

14. What is time complexity?

Time complexity tells how long an algorithm takes to run, based on input size.

15. What is space complexity?

Space complexity tells how much memory an algorithm uses.

UNIT – 02
1. What is Class P?

Class P contains all problems that a computer can solve quickly (in polynomial time).
These problems have fast algorithms.

2. What is Class NP?

Class NP contains problems where the answer is hard to find, but easy to check once
someone gives the solution.

3. Define NP-Hard problems.

NP-Hard problems are at least as difficult as NP problems.

They may not have a solution that we can check easily.
4. Define NP-Complete problems.

NP-Complete problems are the hardest problems in NP.

If we find a fast solution for one NP-Complete problem, all NP problems can be solved fast.

5. What is a decision problem?

A decision problem is a problem whose answer is only YES or NO.

Example: “Is this number prime?”

6. State Cook–Levin theorem.

The Cook–Levin theorem says that SAT is the first NP-Complete problem.
It proved that NP-Complete problems exist.

7. Give two examples of NP-Complete problems.

1. SAT (Boolean satisfiability)

2. Traveling Salesman Problem (TSP – decision version)

8. What is polynomial-time reduction?

Polynomial-time reduction means converting one problem into another problem quickly (in
polynomial time).
If A reduces to B, solving B helps solve A.

9. What is a heuristic algorithm?

A heuristic algorithm gives a good solution quickly, but not always the best solution.
It is used when exact methods are too slow.

10. What is a randomized algorithm?

A randomized algorithm uses random choices during execution.

Its output may change every time, but it often works fast.

11. Define verification algorithm.

A verification algorithm checks if a given answer is correct.

It must work fast (in polynomial time).

12. What is SAT problem?

SAT means Satisfiability Problem.

Given a Boolean expression, we check if there is some assignment of true/false that makes it
true.

13. What is reduction proof?

A reduction proof shows that one problem can be converted into another problem.
It is used to prove NP-Completeness.

14. What is search problem vs decision problem?

 Decision problem: output is only YES/NO.

 Search problem: we must find the actual answer, not just yes/no.
Example:
Decision: “Is there a path?”
Search: “Find the path.”

15. Why are NP-Complete problems important?

Because if we find a fast solution to any NP-Complete problem, then all NP problems will
also have fast solutions.
They help us understand limits of computing.

UNIT – 03
1. What is amortized analysis?

Amortized analysis finds the average cost per operation when we do many operations.
It shows the overall cost is small, even if some steps are expensive.

2. What is the aggregate method?

In the aggregate method, we find the total cost of all operations and then divide by the
number of operations.
This gives the average cost per operation.

3. What is the accounting method?

In the accounting method, we give extra (credit) cost to cheap operations.

This extra credit pays for future expensive operations.

4. What is the potential method?

The potential method stores “potential energy” in the data structure.

This potential helps pay for future expensive operations.

5. Define competitive analysis.

Competitive analysis compares an online algorithm with the best possible offline
algorithm.
It shows how good the online method is.

6. Define probabilistic inequalities.

Probabilistic inequalities give upper bounds on the probability that a random variable will
be very large.
They help in analyzing randomized algorithms.

7. What is Markov inequality?

Markov’s inequality says that the chance of a random variable being very large is small if its
average value is small.

8. What is Chebyshev’s inequality?

Chebyshev’s inequality says that a random variable is very unlikely to be far away from its
average value.
It uses variance to measure this.

9. Give an example where amortized analysis is used.

Amortized analysis is used in dynamic arrays.

Most insertions take O(1) time, even though resizing sometimes takes more time.

10. What is a dynamic table?

A dynamic table is a table (or array) that can grow or shrink automatically when we insert
or delete elements.

11. What is load factor in amortized analysis?

Load factor = (number of elements) / (size of table).

It shows how full the table or hash table is.

12. Define online algorithm.

An online algorithm makes decisions step-by-step without knowing the future.

Example: choosing a seat, buying something without knowing future prices.

13. What is expected running time?

Expected running time is the average time an algorithm takes, considering all random
choices.

14. What is worst-case running time?

Worst-case running time is the maximum time an algorithm will ever take, even in the worst
possible input.

15. Give one application of randomized algorithms.

Randomized algorithms are used in:

QuickSort → using random pivot makes sorting faster on average.
Other examples: randomized hashing, randomized min-cut.

UNIT – 04
1. What is point location problem?

Point location problem means finding which region or area a given point lies in, inside a
divided geometric space.

2. Define convex hull.

Convex hull is the smallest convex shape that covers all points.
Imagine stretching a rubber band around points — the shape formed is the convex hull.

3. What is a Voronoi diagram?

A Voronoi diagram divides a plane into regions so that each region contains the points
closest to one center.

4. What is graph connectivity?

Graph connectivity tells whether all nodes in a graph are connected to each other by some
path.

5. Define maximum flow.

Maximum flow is the largest amount of flow (like water or data) that can pass from a
source to a sink in a network.

6. What is a cut in a flow network?

A cut divides the graph into two sets:

one contains the source, the other contains the sink.
Cut capacity = total capacity of edges going from source side to sink side.

7. What is bipartite matching?

Bipartite matching tries to match nodes from two separate sets so that each pair is connected
and no node is repeated.
8. What is Karger’s Min-Cut algorithm?

Karger’s algorithm is a randomized algorithm that repeatedly merges (contracts) edges to

find the minimum cut in a graph.

9. What is an approximation algorithm?

An approximation algorithm gives a near-optimal solution to a hard problem in less time

than an exact algorithm.

10. Define approximation ratio.

Approximation ratio =
(best solution from algorithm) / (best possible solution).
It tells how close the answer is to the optimal one.

11. What is PRAM?

PRAM (Parallel Random Access Machine) is a model used to design and study parallel
algorithms where many processors work together.

12. What is list ranking problem?

List ranking means finding the position (rank) of each node in a linked list when processors
work in parallel.

13. What is an arrangement of lines/points?

An arrangement is the division of a plane created by lines or points.

It shows all intersections and regions formed.

14. What is multi-commodity flow?

Multi-commodity flow allows multiple types of flow (like goods, data, or water) to move
through the same network at the same time.

15. What is string matching?

String matching means finding a pattern string inside a text string.

16. Name any two string matching algorithms.

 KMP Algorithm
 Rabin–Karp Algorithm

17. What is primal-dual method?

The primal-dual method solves optimization problems by working on two related problems
(primal and dual) at the same time.
18. What is local search heuristic?

Local search heuristic starts with a solution and then keeps making small improvements
until no better solution is found.

19. Define parallel sorting.

Parallel sorting means sorting data using many processors at the same time to make sorting
faster.

20. What is network flow?

Network flow studies how something (water, data, traffic) flows through a network of nodes
and edges, usually from a source to a sink.