Algorithms

Question 1

Where does backtracking work best?

Answer 1

Backtracking works best where solution is a sequence of choices and each choice restraints subsequent choices. It identifies as soon as possible the choices you made cannot give you solution, so you can sooner step back and try something else. Fail fast, fail often.

Question 2

What is heuristic method or heuristic?

Answer 2

A heuristic method is a method that leads to solution without guaranteeing that its the best or optimal one. This method helps when brute force or backtracking are too slow.

Question 3

What is Greedy algorithm?

Answer 3

Greedy algorithm is a common type of heuristic method. It consists of never coming back to the previous choices. It is the opposite of backtracking. Try to make best choice at each step and don’t question it later.

Question 4

Essence of Greedy algorithm

Answer 4

Try to make the best move at each step and don’t question it later. Like the burglar will fill the knapsack with highest valued items that fill his bag and don’t look at other items or combinations that may have given higher value.

Question 5

Greedy algorithm is inverse of?

Answer 5

Backtracking, where we come back to previous moves and try to make better move. Like 8 chess queens problem

Question 6

Greedy Travelling Salesman

Answer 6

At each city, visit the unvisited city that is nearest

and repeat until all cities are visited.

Question 7

Greedy power line question: How to connect unconnected cities with least cable? Power can be transmitted from one connected location to other.

Answer 7

1) From all that don’t have power, choose the one that is closest to the settlement that has power. Connect those two.
2) Repeat till all the settlements are connected.

This is the best solution to this problem.