Design and Analysis of Algorithms · Unit 6 · 5 hrs
Backtracking
Exam-focused notes for Backtracking (Design and Analysis of Algorithms, CSC325): what the TU syllabus asks and how it has actually been tested, with 9 solved past questions from this unit.
What this unit covers
- Concept of Backtracking, Recursion vs Backtracking
- Backtracking Algorithms: Subset-sum Problem, Zero-one Knapsack Problem, N-queen Problem and their Analysis
Backtracking Algorithms
Find all possible subsets of the integers that sum to 21 in the array {5, 6, 10, 11, 15} using back tracking technique. [5]
- Set of integers: $W = \{5, 6, 10, 11, 15\}$ (already in ascending order) - Number of elements: $n = 5$ - Target sum: $M = 21$ Goal: find all subsets whose elements sum to exactly $21$. --- For the sum-of-subsets backtracking algorithm, keep track of: - $s...
Full solved answer →Given a set $A={5,7,10,12,15,18,20}$, find the subset that sum to 35 using backtracking. [5]
- Set $A = \{5, 7, 10, 12, 15, 18, 20\}$ (sorted in increasing order) - Target sum $M = 35$ - Number of elements $n = 7$ Total of all elements = $5+7+10+12+15+18+20 = 87$. --- Backtracking explores a binary state-space tree. At element $i$ we branch: - Left...
Full solved answer →Does backtracking give multiple solution? Trace subset sum algorithm for the set $(3, 5, 2, 4, 1)$ and sum = 8. [5]
- Set $S = \{3, 5, 2, 4, 1\}$ - Target sum $X = 8$ - Number of elements $n = 5$ Yes. Backtracking systematically explores the entire state-space tree using depth-first search. It does not necessarily halt at the first feasible solution; if we ask for all so...
Full solved answer →What do you mean by Backtracking? Explain the backtracking algorithm for solving knapsack problem and find the solution for the problem given below and capacity of knapsack is 10 kg.
$$\begin{bmatrix} \text{Items} & 1 & 2 & 3 & 4 \ \text{Weight (w}_i\text{)} & 2 & 3 & 4 & 5 \ \text{Profit (P}_i\text{)} & 3 & 5 & 6 & 10 \end{bmatrix}$$
[10]
Backtracking is a systematic algorithmic technique that builds a solution incrementally, one component at a time, and abandons a partial candidate ("backtracks") as soon as it determines that this candidate cannot lead to a valid or optimal complete solutio...
Full solved answer →Explain in brief the Backtracking approach for algorithm design. How it differs with recursion? Explain the N-Queen problem and algorithm using backtracking and analyze its time complexity.[10]
--- Backtracking is an algorithmic design technique used to solve problems by building a solution incrementally, one step at a time, and abandoning (backtracking) a partial solution as soon as it is determined that it cannot lead to a valid complete solutio...
Full solved answer →Concept of Backtracking, Recursion vs Backtracking
Distinguish between recursion and backtracking. Using Miller-Rabin primality test, check whether 53 is prime or not? [5+0]
Feature Recursion Backtracking --------- Definition A technique where a function calls itself directly or indirectly to solve a problem An algorithmic strategy that builds a solution incrementally and abandons a partial candidate as soon as it fails the con...
Full solved answer →Discuss about recursion and backtracking. Analyze the complexity of Miller Rabin Randomized Primality test. [5]
--- Definition: Recursion is the process of defining a problem in terms of itself. It is a process in which a function calls itself directly or indirectly to solve a problem. Key Points: - Complex problems are divided into smaller sub-problems, solved recur...
Full solved answer →Explain the concept of backtracking. How it differ with recursion? [5]
Backtracking is a general algorithmic technique that considers searching every possible combination in order to solve a computational problem. "We have a set of several choices. If one choice from the set of choices proves incorrect, computation backtracks ...
Full solved answer →Write short notes on: a. Backtracking strategy b. Tractable and Intractable Problem [5]
--- Definition: Backtracking is a general algorithmic technique that considers searching every possible combination in order to solve a computational problem. It is used for finding solutions to computational problems where we have a set of several choices....
Full solved answer →Make Unit 6 stick
Practice CSC325 with flashcards & quizzes