You've learned this already. ✅
Click here to view the next lesson.
Chapter 7: Mastering Algorithmic Techniques
Chapter 7: Practical Exercises of Mastering Algorithmic Techniques
Here are some practical exercises centered around the Greedy approach and Backtracking, complete with their solutions.
These exercises aim to offer you direct experience with both the Greedy method and Backtracking. They are crafted to deepen your grasp of these influential algorithmic strategies. As you tackle these exercises, you'll acquire hands-on skills in utilizing these techniques to address complex challenges.
Exercise 1: Implement a Greedy Algorithm for the Coin Change Problem
- Given a set of coin denominations and a total amount, write a function to compute the minimum number of coins needed to make up that amount.
- Example denominations:
[1, 5, 10, 25]and amount:63.
Solution:
def min_coins(coins, amount):
coins.sort(reverse=True)
total_coins = 0
for coin in coins:
total_coins += amount // coin
amount %= coin
return total_coins if amount == 0 else -1
# Test the function
print(min_coins([1, 5, 10, 25], 63)) # Output: 6Exercise 2: Implement Backtracking for the N-Queens Problem
- Write a function to solve the N-Queens puzzle for a given value of N.
- Example N:
4.
Solution:
def is_safe(queens, row, col):
for i in range(row):
if queens[i] == col or \\
queens[i] - i == col - row or \\
queens[i] + i == col + row:
return False
return True
def place_queens(N, row, queens, solutions):
if row == N:
solutions.append(queens[:])
return
for col in range(N):
if is_safe(queens, row, col):
queens[row] = col
place_queens(N, row + 1, queens, solutions)
def solve_n_queens(N):
solutions = []
place_queens(N, 0, [-1] * N, solutions)
return solutions
# Test the function
for solution in solve_n_queens(4):
print(solution)Exercise 3: Greedy Algorithm for Activity Selection Problem
- Given a list of activities with their start and end times, implement a greedy algorithm to select the maximum number of activities that don't overlap.
- Example activities:
[(0, 6), (3, 4), (1, 2), (5, 7), (8, 9)].
Solution:
def activity_selection(activities):
activities.sort(key=lambda x: x[1])
selected = [activities[0]]
for i in range(1, len(activities)):
if activities[i][0] >= selected[-1][1]:
selected.append(activities[i])
return selected
# Test the function
print(activity_selection([(0, 6), (3, 4), (1, 2), (5, 7), (8, 9)]))
# Output: [(1, 2), (3, 4), (5, 7), (8, 9)]Chapter 7: Practical Exercises of Mastering Algorithmic Techniques
Here are some practical exercises centered around the Greedy approach and Backtracking, complete with their solutions.
These exercises aim to offer you direct experience with both the Greedy method and Backtracking. They are crafted to deepen your grasp of these influential algorithmic strategies. As you tackle these exercises, you'll acquire hands-on skills in utilizing these techniques to address complex challenges.
Exercise 1: Implement a Greedy Algorithm for the Coin Change Problem
- Given a set of coin denominations and a total amount, write a function to compute the minimum number of coins needed to make up that amount.
- Example denominations:
[1, 5, 10, 25]and amount:63.
Solution:
def min_coins(coins, amount):
coins.sort(reverse=True)
total_coins = 0
for coin in coins:
total_coins += amount // coin
amount %= coin
return total_coins if amount == 0 else -1
# Test the function
print(min_coins([1, 5, 10, 25], 63)) # Output: 6Exercise 2: Implement Backtracking for the N-Queens Problem
- Write a function to solve the N-Queens puzzle for a given value of N.
- Example N:
4.
Solution:
def is_safe(queens, row, col):
for i in range(row):
if queens[i] == col or \\
queens[i] - i == col - row or \\
queens[i] + i == col + row:
return False
return True
def place_queens(N, row, queens, solutions):
if row == N:
solutions.append(queens[:])
return
for col in range(N):
if is_safe(queens, row, col):
queens[row] = col
place_queens(N, row + 1, queens, solutions)
def solve_n_queens(N):
solutions = []
place_queens(N, 0, [-1] * N, solutions)
return solutions
# Test the function
for solution in solve_n_queens(4):
print(solution)Exercise 3: Greedy Algorithm for Activity Selection Problem
- Given a list of activities with their start and end times, implement a greedy algorithm to select the maximum number of activities that don't overlap.
- Example activities:
[(0, 6), (3, 4), (1, 2), (5, 7), (8, 9)].
Solution:
def activity_selection(activities):
activities.sort(key=lambda x: x[1])
selected = [activities[0]]
for i in range(1, len(activities)):
if activities[i][0] >= selected[-1][1]:
selected.append(activities[i])
return selected
# Test the function
print(activity_selection([(0, 6), (3, 4), (1, 2), (5, 7), (8, 9)]))
# Output: [(1, 2), (3, 4), (5, 7), (8, 9)]Chapter 7: Practical Exercises of Mastering Algorithmic Techniques
Here are some practical exercises centered around the Greedy approach and Backtracking, complete with their solutions.
These exercises aim to offer you direct experience with both the Greedy method and Backtracking. They are crafted to deepen your grasp of these influential algorithmic strategies. As you tackle these exercises, you'll acquire hands-on skills in utilizing these techniques to address complex challenges.
Exercise 1: Implement a Greedy Algorithm for the Coin Change Problem
- Given a set of coin denominations and a total amount, write a function to compute the minimum number of coins needed to make up that amount.
- Example denominations:
[1, 5, 10, 25]and amount:63.
Solution:
def min_coins(coins, amount):
coins.sort(reverse=True)
total_coins = 0
for coin in coins:
total_coins += amount // coin
amount %= coin
return total_coins if amount == 0 else -1
# Test the function
print(min_coins([1, 5, 10, 25], 63)) # Output: 6Exercise 2: Implement Backtracking for the N-Queens Problem
- Write a function to solve the N-Queens puzzle for a given value of N.
- Example N:
4.
Solution:
def is_safe(queens, row, col):
for i in range(row):
if queens[i] == col or \\
queens[i] - i == col - row or \\
queens[i] + i == col + row:
return False
return True
def place_queens(N, row, queens, solutions):
if row == N:
solutions.append(queens[:])
return
for col in range(N):
if is_safe(queens, row, col):
queens[row] = col
place_queens(N, row + 1, queens, solutions)
def solve_n_queens(N):
solutions = []
place_queens(N, 0, [-1] * N, solutions)
return solutions
# Test the function
for solution in solve_n_queens(4):
print(solution)Exercise 3: Greedy Algorithm for Activity Selection Problem
- Given a list of activities with their start and end times, implement a greedy algorithm to select the maximum number of activities that don't overlap.
- Example activities:
[(0, 6), (3, 4), (1, 2), (5, 7), (8, 9)].
Solution:
def activity_selection(activities):
activities.sort(key=lambda x: x[1])
selected = [activities[0]]
for i in range(1, len(activities)):
if activities[i][0] >= selected[-1][1]:
selected.append(activities[i])
return selected
# Test the function
print(activity_selection([(0, 6), (3, 4), (1, 2), (5, 7), (8, 9)]))
# Output: [(1, 2), (3, 4), (5, 7), (8, 9)]Chapter 7: Practical Exercises of Mastering Algorithmic Techniques
Here are some practical exercises centered around the Greedy approach and Backtracking, complete with their solutions.
These exercises aim to offer you direct experience with both the Greedy method and Backtracking. They are crafted to deepen your grasp of these influential algorithmic strategies. As you tackle these exercises, you'll acquire hands-on skills in utilizing these techniques to address complex challenges.
Exercise 1: Implement a Greedy Algorithm for the Coin Change Problem
- Given a set of coin denominations and a total amount, write a function to compute the minimum number of coins needed to make up that amount.
- Example denominations:
[1, 5, 10, 25]and amount:63.
Solution:
def min_coins(coins, amount):
coins.sort(reverse=True)
total_coins = 0
for coin in coins:
total_coins += amount // coin
amount %= coin
return total_coins if amount == 0 else -1
# Test the function
print(min_coins([1, 5, 10, 25], 63)) # Output: 6Exercise 2: Implement Backtracking for the N-Queens Problem
- Write a function to solve the N-Queens puzzle for a given value of N.
- Example N:
4.
Solution:
def is_safe(queens, row, col):
for i in range(row):
if queens[i] == col or \\
queens[i] - i == col - row or \\
queens[i] + i == col + row:
return False
return True
def place_queens(N, row, queens, solutions):
if row == N:
solutions.append(queens[:])
return
for col in range(N):
if is_safe(queens, row, col):
queens[row] = col
place_queens(N, row + 1, queens, solutions)
def solve_n_queens(N):
solutions = []
place_queens(N, 0, [-1] * N, solutions)
return solutions
# Test the function
for solution in solve_n_queens(4):
print(solution)Exercise 3: Greedy Algorithm for Activity Selection Problem
- Given a list of activities with their start and end times, implement a greedy algorithm to select the maximum number of activities that don't overlap.
- Example activities:
[(0, 6), (3, 4), (1, 2), (5, 7), (8, 9)].
Solution:
def activity_selection(activities):
activities.sort(key=lambda x: x[1])
selected = [activities[0]]
for i in range(1, len(activities)):
if activities[i][0] >= selected[-1][1]:
selected.append(activities[i])
return selected
# Test the function
print(activity_selection([(0, 6), (3, 4), (1, 2), (5, 7), (8, 9)]))
# Output: [(1, 2), (3, 4), (5, 7), (8, 9)]