Welcome to the Algorithm Design Exercises section. This part of the course is designed to help you apply the concepts and strategies you've learned in the previous modules. You'll find a series of exercises that will challenge your understanding and help you develop your algorithm design skills.
Exercise 1: Divide and Conquer
Problem Statement
Implement a function to find the maximum element in an array using the Divide and Conquer strategy.
Steps to Solve
- Divide: Split the array into two halves.
- Conquer: Recursively find the maximum element in each half.
- Combine: Compare the maximum elements from both halves to find the overall maximum.
Example
def find_maximum(arr, low, high):
# Base case: Only one element
if low == high:
return arr[low]
# Find the middle point
mid = (low + high) // 2
# Recursively find the maximum in both halves
max1 = find_maximum(arr, low, mid)
max2 = find_maximum(arr, mid + 1, high)
# Return the maximum of the two halves
return max(max1, max2)
# Test the function
array = [1, 5, 3, 9, 2, 8, 4]
print("Maximum element:", find_maximum(array, 0, len(array) - 1))Solution Explanation
- The function
find_maximumis called recursively to divide the array into smaller subarrays. - The base case is when the subarray has only one element, which is the maximum by default.
- The middle point is calculated to split the array.
- The maximum elements of the left and right subarrays are found recursively.
- Finally, the maximum of these two elements is returned.
Exercise
Implement a function to find the minimum element in an array using the Divide and Conquer strategy.
Exercise 2: Greedy Algorithms
Problem Statement
Given a set of activities with their start and finish times, select the maximum number of activities that can be performed by a single person, assuming that a person can only work on a single activity at a time.
Steps to Solve
- Sort: Sort the activities based on their finish times.
- Select: Select the first activity and then select the next activity that starts after the previous one finishes.
Example
def activity_selection(activities):
# Sort activities based on finish time
activities.sort(key=lambda x: x[1])
# The first activity always gets selected
selected_activities = [activities[0]]
# Consider the rest of the activities
for i in range(1, len(activities)):
if activities[i][0] >= selected_activities[-1][1]:
selected_activities.append(activities[i])
return selected_activities
# Test the function
activities = [(1, 3), (2, 5), (4, 6), (6, 7), (5, 8), (8, 9)]
print("Selected activities:", activity_selection(activities))Solution Explanation
- The activities are sorted based on their finish times.
- The first activity is always selected.
- For each subsequent activity, it is selected if its start time is greater than or equal to the finish time of the last selected activity.
Exercise
Implement a function to find the minimum number of coins needed to make a given amount using a greedy algorithm.
Exercise 3: Dynamic Programming
Problem Statement
Implement a function to find the length of the longest common subsequence (LCS) of two strings using Dynamic Programming.
Steps to Solve
- Define Subproblems: Define the subproblems in terms of the indices of the two strings.
- Recurrence Relation: Use the recurrence relation to build the solution.
- Memoization: Store the results of subproblems to avoid redundant calculations.
Example
def lcs(X, Y):
m = len(X)
k = len(Y)
# Create a 2D array to store the lengths of LCS
L = [[0] * (k + 1) for _ in range(m + 1)]
# Build the LCS table in bottom-up fashion
for i in range(m + 1):
for j in range(k + 1):
if i == 0 or j == 0:
L[i][j] = 0
elif X[i - 1] == Y[j - 1]:
L[i][j] = L[i - 1][j - 1] + 1
else:
L[i][j] = max(L[i - 1][j], L[i][j - 1])
return L[m][k]
# Test the function
X = "AGGTAB"
Y = "GXTXAYB"
print("Length of LCS:", lcs(X, Y))Solution Explanation
- A 2D array
Lis created to store the lengths of LCS for different subproblems. - The table is filled in a bottom-up manner using the recurrence relation.
- The final value in
L[m][k]gives the length of the LCS.
Exercise
Implement a function to find the minimum number of operations required to convert one string into another using Dynamic Programming.
Exercise 4: Backtracking
Problem Statement
Implement a function to solve the N-Queens problem using Backtracking.
Steps to Solve
- Place Queens: Place queens one by one in different columns.
- Check Safety: Check if placing a queen in a particular cell is safe.
- Backtrack: If placing the queen leads to a solution, return true. If not, backtrack and try the next position.
Example
def is_safe(board, row, col):
for i in range(col):
if board[row][i] == 1:
return False
for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
if board[i][j] == 1:
return False
for i, j in zip(range(row, len(board), 1), range(col, -1, -1)):
if board[i][j] == 1:
return False
return True
def solve_n_queens_util(board, col):
if col >= len(board):
return True
for i in range(len(board)):
if is_safe(board, i, col):
board[i][col] = 1
if solve_n_queens_util(board, col + 1):
return True
board[i][col] = 0
return False
def solve_n_queens(n):
board = [[0] * n for _ in range(n)]
if not solve_n_queens_util(board, 0):
return "No solution exists"
return board
# Test the function
n = 4
solution = solve_n_queens(n)
for row in solution:
print(row)Solution Explanation
- The
is_safefunction checks if placing a queen in a particular cell is safe. - The
solve_n_queens_utilfunction places queens one by one and backtracks if a solution is not found. - The
solve_n_queensfunction initializes the board and calls the utility function to solve the problem.
Exercise
Implement a function to solve the Sudoku puzzle using Backtracking.
Conclusion
In this section, you have practiced various algorithm design strategies through hands-on exercises. These exercises are designed to reinforce your understanding and help you apply the concepts in practical scenarios. Make sure to attempt the exercises on your own before referring to the solutions. Happy coding!