2 Mark Answers for Remaining 2 Marks
1. How do you measure the efficiency of an algorithm? Mention its types.
○ Time complexity
○ Space complexity
○ Input/Output complexity
2. Solve: If f(n) = a_mn^m + ... a_1n + a_0, then prove that f(n) = O(n^m)
○ Proof:
■ Let's assume that |a_m| is the largest coefficient.
■ Then, |f(n)| <= |a_m| * |n^m|
■ Since |n^m| is O(n^m), we have f(n) = O(n^m).
3. Define indegree, outdegree in a graph and list graph applications
○ Indegree: The number of edges entering a vertex.
○ Outdegree: The number of edges leaving a vertex.
○ Graph applications:
■ Social networks
■ Transportation networks
■ Computer networks
■ Circuit design
4. Define Bipartite Graphs. What do you meant by perfect matching in bipartite
graph?
○ Bipartite graph: A graph whose vertices can be divided into two disjoint sets
such that every edge connects a vertex in one set to a vertex in the other set.
○ Perfect matching: A matching in which every vertex is matched to exactly one
other vertex.
5. What are the differences between dynamic programming and divide and conquer
approaches?
○ Dynamic programming:
■ Breaks down a problem into subproblems
■ Stores the solutions to the subproblems to avoid recomputation
○ Divide and conquer:
■ Divides a problem into smaller subproblems
■ Recursively solves the subproblems
■ Combines the solutions to the subproblems to solve the original problem
6. What is the purpose of Huffman's tree? Mention its applications.
○ Purpose:
■ To create an optimal prefix code for a set of symbols
○ Applications:
■ Data compression
■ Error correction
7. Differentiate backtracking and Exhaustive search.
○ Backtracking:
■ Explores all possible solutions to a problem
■ Backtracks when a solution is infeasible
○ Exhaustive search:
■ Tries all possible solutions to a problem
■ Does not backtrack
8. Write an algorithm for sum of subset problem.
○ Input: A set of integers S and a target sum T
○ A subset of S that sums to T
○ Algorithm:
■ Let f(i, s) be the number of ways to choose a subset of the first i elements
of S that sum to s.
■ Then, f(i, s) = f(i - 1, s) + f(i - 1, s - S_i), where S_i is the i-th element of S.
■ The solution to the sum of subset problem can be found by computing f(n,
T), where n is the number of elements in S.
9. List any three problems that have polynomial time algorithms. Justify your
answer.
○ Sorting: Can be solved in O(n log n) time using merge sort or heap sort.
○ Finding the minimum spanning tree of a graph: Can be solved in O(E log V)
time using Prim's or Kruskal's algorithm.
○ Finding the shortest path between two vertices in a graph: Can be solved in
O(V + E) time using Dijkstra's algorithm.
10. What are the tractable and non-tractable problems?
● Tractable problems:
○ Problems that can be solved in polynomial time
● Non-tractable problems:
○ Problems that cannot be solved in polynomial time
