Chapter 9: Algorithm Design Techniques
9.5 Practical Problems of Chapter 9: Algorithm Design Techniques
We are excited to offer some practice problems that allow you to apply the techniques we've discussed in this chapter. These problems will help you test your understanding and apply the knowledge you've gained.
1. Recursion: Fibonacci Series
Write a recursive function that generates the nth number in the Fibonacci series. Remember, the Fibonacci sequence is a series of numbers in which each number is the sum of the two preceding ones, usually starting with 0 and 1.
def fibonacci(n):
if n <= 0:
return "Input should be a positive integer."
elif n == 1:
return 0
elif n == 2:
return 1
else:
return fibonacci(n-1) + fibonacci(n-2)2. Iterative Approach: Factorial
Write an iterative function that computes the factorial of a given number. The factorial of a non-negative integer n is the product of all positive integers less than or equal to n.
def factorial(n):
if n < 0:
return "Input should be a non-negative integer."
else:
result = 1
for i in range(2, n+1):
result *= i
return result3. Backtracking: N-Queens Problem
The N Queens puzzle is the problem of placing N chess queens on an N×N chessboard so that no two queens threaten each other. Thus, a solution requires that no two queens share the same row, column, or diagonal.
def solveNQueens(n):
def can_place(pos, ocuppied_positions):
for i in range(len(ocuppied_positions)):
if ocuppied_positions[i] == pos or \\
ocuppied_positions[i] - i == pos - len(ocuppied_positions) or \\
ocuppied_positions[i] + i == pos + len(ocuppied_positions):
return False
return True
def place_queens(n, index, ocuppied_positions):
if index == n:
return [ocuppied_positions]
else:
result = []
for pos in range(n):
if can_place(pos, ocuppied_positions):
result += place_queens(n, index + 1, ocuppied_positions + [pos])
return result
result = place_queens(n, 0, [])
return [["." * i + "Q" + "." * (n - i - 1) for i in pos] for pos in result]4. Branch and Bound: Travelling Salesman Problem
The travelling salesman problem (TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?"
TSP is an NP-hard problem in combinatorial optimization, important in operations research and theoretical computer science. Although it's hard to provide an optimal solution for large inputs, it is a good practice to understand the branch and bound method.
Note: Writing an efficient code for TSP using branch and bound can be quite complex and may not be suitable as an initial exercise for learning branch and bound. It's recommended to go through the theoretical aspects of this problem and try to understand how branch and bound can help prune the search space.
These problems should give you a good practice to understand these techniques. Do try to solve them, and if you face any issue, feel free to look up solutions and explanations. The goal is to learn, and learning takes its own time and pace. Don't rush, enjoy the process of solving these problems. Happy coding!
9.5 Practical Problems of Chapter 9: Algorithm Design Techniques
We are excited to offer some practice problems that allow you to apply the techniques we've discussed in this chapter. These problems will help you test your understanding and apply the knowledge you've gained.
1. Recursion: Fibonacci Series
Write a recursive function that generates the nth number in the Fibonacci series. Remember, the Fibonacci sequence is a series of numbers in which each number is the sum of the two preceding ones, usually starting with 0 and 1.
def fibonacci(n):
if n <= 0:
return "Input should be a positive integer."
elif n == 1:
return 0
elif n == 2:
return 1
else:
return fibonacci(n-1) + fibonacci(n-2)2. Iterative Approach: Factorial
Write an iterative function that computes the factorial of a given number. The factorial of a non-negative integer n is the product of all positive integers less than or equal to n.
def factorial(n):
if n < 0:
return "Input should be a non-negative integer."
else:
result = 1
for i in range(2, n+1):
result *= i
return result3. Backtracking: N-Queens Problem
The N Queens puzzle is the problem of placing N chess queens on an N×N chessboard so that no two queens threaten each other. Thus, a solution requires that no two queens share the same row, column, or diagonal.
def solveNQueens(n):
def can_place(pos, ocuppied_positions):
for i in range(len(ocuppied_positions)):
if ocuppied_positions[i] == pos or \\
ocuppied_positions[i] - i == pos - len(ocuppied_positions) or \\
ocuppied_positions[i] + i == pos + len(ocuppied_positions):
return False
return True
def place_queens(n, index, ocuppied_positions):
if index == n:
return [ocuppied_positions]
else:
result = []
for pos in range(n):
if can_place(pos, ocuppied_positions):
result += place_queens(n, index + 1, ocuppied_positions + [pos])
return result
result = place_queens(n, 0, [])
return [["." * i + "Q" + "." * (n - i - 1) for i in pos] for pos in result]4. Branch and Bound: Travelling Salesman Problem
The travelling salesman problem (TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?"
TSP is an NP-hard problem in combinatorial optimization, important in operations research and theoretical computer science. Although it's hard to provide an optimal solution for large inputs, it is a good practice to understand the branch and bound method.
Note: Writing an efficient code for TSP using branch and bound can be quite complex and may not be suitable as an initial exercise for learning branch and bound. It's recommended to go through the theoretical aspects of this problem and try to understand how branch and bound can help prune the search space.
These problems should give you a good practice to understand these techniques. Do try to solve them, and if you face any issue, feel free to look up solutions and explanations. The goal is to learn, and learning takes its own time and pace. Don't rush, enjoy the process of solving these problems. Happy coding!
9.5 Practical Problems of Chapter 9: Algorithm Design Techniques
We are excited to offer some practice problems that allow you to apply the techniques we've discussed in this chapter. These problems will help you test your understanding and apply the knowledge you've gained.
1. Recursion: Fibonacci Series
Write a recursive function that generates the nth number in the Fibonacci series. Remember, the Fibonacci sequence is a series of numbers in which each number is the sum of the two preceding ones, usually starting with 0 and 1.
def fibonacci(n):
if n <= 0:
return "Input should be a positive integer."
elif n == 1:
return 0
elif n == 2:
return 1
else:
return fibonacci(n-1) + fibonacci(n-2)2. Iterative Approach: Factorial
Write an iterative function that computes the factorial of a given number. The factorial of a non-negative integer n is the product of all positive integers less than or equal to n.
def factorial(n):
if n < 0:
return "Input should be a non-negative integer."
else:
result = 1
for i in range(2, n+1):
result *= i
return result3. Backtracking: N-Queens Problem
The N Queens puzzle is the problem of placing N chess queens on an N×N chessboard so that no two queens threaten each other. Thus, a solution requires that no two queens share the same row, column, or diagonal.
def solveNQueens(n):
def can_place(pos, ocuppied_positions):
for i in range(len(ocuppied_positions)):
if ocuppied_positions[i] == pos or \\
ocuppied_positions[i] - i == pos - len(ocuppied_positions) or \\
ocuppied_positions[i] + i == pos + len(ocuppied_positions):
return False
return True
def place_queens(n, index, ocuppied_positions):
if index == n:
return [ocuppied_positions]
else:
result = []
for pos in range(n):
if can_place(pos, ocuppied_positions):
result += place_queens(n, index + 1, ocuppied_positions + [pos])
return result
result = place_queens(n, 0, [])
return [["." * i + "Q" + "." * (n - i - 1) for i in pos] for pos in result]4. Branch and Bound: Travelling Salesman Problem
The travelling salesman problem (TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?"
TSP is an NP-hard problem in combinatorial optimization, important in operations research and theoretical computer science. Although it's hard to provide an optimal solution for large inputs, it is a good practice to understand the branch and bound method.
Note: Writing an efficient code for TSP using branch and bound can be quite complex and may not be suitable as an initial exercise for learning branch and bound. It's recommended to go through the theoretical aspects of this problem and try to understand how branch and bound can help prune the search space.
These problems should give you a good practice to understand these techniques. Do try to solve them, and if you face any issue, feel free to look up solutions and explanations. The goal is to learn, and learning takes its own time and pace. Don't rush, enjoy the process of solving these problems. Happy coding!
9.5 Practical Problems of Chapter 9: Algorithm Design Techniques
We are excited to offer some practice problems that allow you to apply the techniques we've discussed in this chapter. These problems will help you test your understanding and apply the knowledge you've gained.
1. Recursion: Fibonacci Series
Write a recursive function that generates the nth number in the Fibonacci series. Remember, the Fibonacci sequence is a series of numbers in which each number is the sum of the two preceding ones, usually starting with 0 and 1.
def fibonacci(n):
if n <= 0:
return "Input should be a positive integer."
elif n == 1:
return 0
elif n == 2:
return 1
else:
return fibonacci(n-1) + fibonacci(n-2)2. Iterative Approach: Factorial
Write an iterative function that computes the factorial of a given number. The factorial of a non-negative integer n is the product of all positive integers less than or equal to n.
def factorial(n):
if n < 0:
return "Input should be a non-negative integer."
else:
result = 1
for i in range(2, n+1):
result *= i
return result3. Backtracking: N-Queens Problem
The N Queens puzzle is the problem of placing N chess queens on an N×N chessboard so that no two queens threaten each other. Thus, a solution requires that no two queens share the same row, column, or diagonal.
def solveNQueens(n):
def can_place(pos, ocuppied_positions):
for i in range(len(ocuppied_positions)):
if ocuppied_positions[i] == pos or \\
ocuppied_positions[i] - i == pos - len(ocuppied_positions) or \\
ocuppied_positions[i] + i == pos + len(ocuppied_positions):
return False
return True
def place_queens(n, index, ocuppied_positions):
if index == n:
return [ocuppied_positions]
else:
result = []
for pos in range(n):
if can_place(pos, ocuppied_positions):
result += place_queens(n, index + 1, ocuppied_positions + [pos])
return result
result = place_queens(n, 0, [])
return [["." * i + "Q" + "." * (n - i - 1) for i in pos] for pos in result]4. Branch and Bound: Travelling Salesman Problem
The travelling salesman problem (TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?"
TSP is an NP-hard problem in combinatorial optimization, important in operations research and theoretical computer science. Although it's hard to provide an optimal solution for large inputs, it is a good practice to understand the branch and bound method.
Note: Writing an efficient code for TSP using branch and bound can be quite complex and may not be suitable as an initial exercise for learning branch and bound. It's recommended to go through the theoretical aspects of this problem and try to understand how branch and bound can help prune the search space.
These problems should give you a good practice to understand these techniques. Do try to solve them, and if you face any issue, feel free to look up solutions and explanations. The goal is to learn, and learning takes its own time and pace. Don't rush, enjoy the process of solving these problems. Happy coding!