Menu iconMenu iconAlgorithms and Data Structures with Python
Algorithms and Data Structures with Python

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: 6

Exercise 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: 6

Exercise 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: 6

Exercise 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: 6

Exercise 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)]