Algorithms

Question 1

When should you use Backtracking?

Answer 1

Use backtracking when you need to find all or some solutions to a problem that incrementally builds candidates to the solutions, and abandons a candidate as soon as it determines that this candidate cannot possibly lead to a valid solution.

For example - Classic problems include the N-Queens puzzle, Sudoku, crossword puzzles, and combinatorial problems like generating permutations and combinations

Question 2

How does Backtracking differ from brute-force?

Answer 2

While brute-force tries out all possible solutions without discrimination, backtracking eliminates paths that are clearly not leading to a solution (pruning), which makes it more efficient.

Question 3

What are some classic problems solved by Backtracking?

Answer 3

Classic problems include the N-Queens puzzle, Sudoku, crossword puzzles, and combinatorial problems like generating permutations and combinations

Question 4

Describe the general steps in a Backtracking algorithm.

Answer 4

The general steps are:

• Make a choice that seems like a step towards a solution.
• Given the choice, explore the next step (recurse).
• If the choice leads to a non-solution or violates constraints, undo the choice and make another (backtrack).

Question 5

What is Breadth-First Search (BFS)?

Answer 5

BFS is a tree or graph traversal algorithm that explores neighbors before children. It’s ideal for finding the shortest path in unweighted graphs.

Question 6

What are the key characteristics of BFS?

Answer 6

• BFS uses a queue to track which node to visit next.* It visits all nodes at the current depth before moving to the next depth level.* BFS is often used to determine the level of each node from the root node.

Question 7

What is the time complexity of BFS?

Answer 7

The time complexity of BFS for tree is O(n) where n is the number of node and for graph, O(V + E), where V is the number of vertices and E is the number of edges in the graph.

Question 8

What are common applications of BFS?

Answer 8

• Finding the shortest path in an unweighted graph.* Level order traversal of a tree.* Finding all connected components in an undirected graph.

Question 9

How is BFS implemented in Python?

Answer 9

def bfs_tree(root):
    if root is None:
        return    queue = deque()  # Use deque for efficient queue operations    

queue.append(root)    
while queue:
        node = queue.popleft()  # Dequeue the next node
        # Process the node here (e.g., print node value)
        print(node.value)
        if node.left:
            queue.append(node.left)  # Enqueue left child
        if node.right:            queue.append(node.right)  # Enqueue right child