Scribd
Upload
6 views2 pages

Backtracking Assignment Answers

The document discusses various algorithmic concepts including Subset Sum using backtracking, the 4-Queens problem, and the definitions of P, NP, and NP-Complete problems. It also covers the Knapsack problem using branch and bound techniques, and the Hamiltonian Circuit problem with backtracking. Each section provides a brief explanation and example of the respective algorithm or problem.

Uploaded by

icegameacc1
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
6 views2 pages

Backtracking Assignment Answers

The document discusses various algorithmic concepts including Subset Sum using backtracking, the 4-Queens problem, and the definitions of P, NP, and NP-Complete problems. It also covers the Knapsack problem using branch and bound techniques, and the Hamiltonian Circuit problem with backtracking. Each section provides a brief explanation and example of the respective algorithm or problem.

Uploaded by

icegameacc1
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

1.

Subset Sum using Backtracking:

Given S = {1, 3, 4, 5} and D = 11

Try all subsets using backtracking. Check sum = 11.

Checked: {1,3,4,5}=13 (Invalid), {1,3,4}=8 (Invalid), {3,4,5}=12 (Invalid)

No subset adds to 11. So, No valid subset found.

2. What is Backtracking + 4-Queens Problem:

Backtracking is trying possible solutions step-by-step and backtrack if fails.

4-Queens: Place 4 queens so no two attack each other.

One solution: Q at (1,2), (2,4), (3,1), (4,3)

Board:

_Q__

___Q

Q___

__Q_

3. Short Notes:

i. P and NP:

P = Solvable in polynomial time.

NP = Verifiable in polynomial time.

ii. NP-Complete:

Problems that are both in NP and as hard as any NP problem. If one is solved fast, all NP problems

can be.

4. Knapsack using Branch and Bound:

W = 16, Items: (10,100), (7,63), (8,56), (4,12)


Use value/weight ratio to sort: Item1:10, Item2:9, Item3:7, Item4:3

Select Item1 (10), Item2 (7) -> total weight = 17 (Too much)

Try: Item2 (7) + Item3 (8) = 15 (Valid) -> Value = 63+56=119

Best value = 119

5. Hamiltonian Circuit with Backtracking:

Start at any node. Try visiting all nodes once and return to start.

Backtrack if path repeats node or leads to dead-end.

Continue until full cycle is found.

You might also like