Chapter 4: Basic Algorithm Types
4.5 Practice Problems of Chapter 4: Basic Algorithm Types
Problem 1: Binary Search (Divide and Conquer)
Given a sorted list of n integers and a target integer x, write a function that finds the position of x in the list using a binary search algorithm. Remember, binary search operates by effectively dividing the problem in half with each step.
Solution:
def binary_search(list, x):
low = 0
high = len(list) - 1
while low <= high:
mid = (high + low) // 2
if list[mid] < x:
low = mid + 1
elif list[mid] > x:
high = mid - 1
else:
return mid
return -1Problem 2: Coin Change (Greedy Algorithm)
Given a list of denominations of coins and a value n, write a function that calculates the minimum number of coins needed to make change for n. Use a greedy algorithm that always selects the largest denomination less than or equal to the remaining amount to be changed out. Test your function with various coin sets, like the standard US or Euro denominations.
Solution:
def coin_change(coins, n):
coins.sort(reverse=True)
count = 0
for coin in coins:
while n >= coin:
n -= coin
count += 1
if n == 0:
return count
return countProblem 3: Fibonacci Series (Dynamic Programming)
Write a function to calculate the nth Fibonacci number. The Fibonacci series is defined as: F(0) = 0, F(1) = 1, and F(n) = F(n-1) + F(n-2) for n > 1. First, implement this using simple recursion, then optimize your function using dynamic programming to store and re-use computed values.
Solution:
def fibonacci(n, computed = {0: 0, 1: 1}):
if n not in computed:
computed[n] = fibonacci(n - 1, computed) + fibonacci(n - 2, computed)
return computed[n]Problem 4: Sum of Natural Numbers (Recursive Algorithm)
Write a function that computes the sum of all natural numbers from 1 to n using a recursive algorithm. Compare the recursive solution with an iterative solution and discuss the differences.
Solution:
def recursive_sum(n):
if n <= 1:
return n
else:
return n + recursive_sum(n - 1)
def iterative_sum(n):
return n * (n + 1) // 2Problem 5: QuickSort (Divide and Conquer)
Implement the QuickSort algorithm which sorts an array of integers. QuickSort is a Divide and Conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot.
Solution:
def quicksort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quicksort(left) + middle + quicksort(right)Problem 6: Implementing a Stack using Recursion (Recursive Algorithm)
Implement a stack data structure using recursion. Your stack should have push, pop, and peek functions.
Solution:
class Stack:
def __init__(self):
self.stack = []
def push(self, item):
self.stack.append(item)
def pop(self):
if len(self.stack) < 1:
return None
return self.stack.pop()
def peek(self):
if self.stack:
return self.stack[-1]
return NoneRemember, the aim of these practice problems is to get a hands-on understanding of the different algorithm types, how they work, and where they can be applied. Try to solve all the problems and compare the solutions to see the difference between these algorithm types. Good luck!
In the next chapter, we will explore more advanced algorithm types and their applications in real-world problem-solving. Stay tuned!
4.5 Practice Problems of Chapter 4: Basic Algorithm Types
Problem 1: Binary Search (Divide and Conquer)
Given a sorted list of n integers and a target integer x, write a function that finds the position of x in the list using a binary search algorithm. Remember, binary search operates by effectively dividing the problem in half with each step.
Solution:
def binary_search(list, x):
low = 0
high = len(list) - 1
while low <= high:
mid = (high + low) // 2
if list[mid] < x:
low = mid + 1
elif list[mid] > x:
high = mid - 1
else:
return mid
return -1Problem 2: Coin Change (Greedy Algorithm)
Given a list of denominations of coins and a value n, write a function that calculates the minimum number of coins needed to make change for n. Use a greedy algorithm that always selects the largest denomination less than or equal to the remaining amount to be changed out. Test your function with various coin sets, like the standard US or Euro denominations.
Solution:
def coin_change(coins, n):
coins.sort(reverse=True)
count = 0
for coin in coins:
while n >= coin:
n -= coin
count += 1
if n == 0:
return count
return countProblem 3: Fibonacci Series (Dynamic Programming)
Write a function to calculate the nth Fibonacci number. The Fibonacci series is defined as: F(0) = 0, F(1) = 1, and F(n) = F(n-1) + F(n-2) for n > 1. First, implement this using simple recursion, then optimize your function using dynamic programming to store and re-use computed values.
Solution:
def fibonacci(n, computed = {0: 0, 1: 1}):
if n not in computed:
computed[n] = fibonacci(n - 1, computed) + fibonacci(n - 2, computed)
return computed[n]Problem 4: Sum of Natural Numbers (Recursive Algorithm)
Write a function that computes the sum of all natural numbers from 1 to n using a recursive algorithm. Compare the recursive solution with an iterative solution and discuss the differences.
Solution:
def recursive_sum(n):
if n <= 1:
return n
else:
return n + recursive_sum(n - 1)
def iterative_sum(n):
return n * (n + 1) // 2Problem 5: QuickSort (Divide and Conquer)
Implement the QuickSort algorithm which sorts an array of integers. QuickSort is a Divide and Conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot.
Solution:
def quicksort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quicksort(left) + middle + quicksort(right)Problem 6: Implementing a Stack using Recursion (Recursive Algorithm)
Implement a stack data structure using recursion. Your stack should have push, pop, and peek functions.
Solution:
class Stack:
def __init__(self):
self.stack = []
def push(self, item):
self.stack.append(item)
def pop(self):
if len(self.stack) < 1:
return None
return self.stack.pop()
def peek(self):
if self.stack:
return self.stack[-1]
return NoneRemember, the aim of these practice problems is to get a hands-on understanding of the different algorithm types, how they work, and where they can be applied. Try to solve all the problems and compare the solutions to see the difference between these algorithm types. Good luck!
In the next chapter, we will explore more advanced algorithm types and their applications in real-world problem-solving. Stay tuned!
4.5 Practice Problems of Chapter 4: Basic Algorithm Types
Problem 1: Binary Search (Divide and Conquer)
Given a sorted list of n integers and a target integer x, write a function that finds the position of x in the list using a binary search algorithm. Remember, binary search operates by effectively dividing the problem in half with each step.
Solution:
def binary_search(list, x):
low = 0
high = len(list) - 1
while low <= high:
mid = (high + low) // 2
if list[mid] < x:
low = mid + 1
elif list[mid] > x:
high = mid - 1
else:
return mid
return -1Problem 2: Coin Change (Greedy Algorithm)
Given a list of denominations of coins and a value n, write a function that calculates the minimum number of coins needed to make change for n. Use a greedy algorithm that always selects the largest denomination less than or equal to the remaining amount to be changed out. Test your function with various coin sets, like the standard US or Euro denominations.
Solution:
def coin_change(coins, n):
coins.sort(reverse=True)
count = 0
for coin in coins:
while n >= coin:
n -= coin
count += 1
if n == 0:
return count
return countProblem 3: Fibonacci Series (Dynamic Programming)
Write a function to calculate the nth Fibonacci number. The Fibonacci series is defined as: F(0) = 0, F(1) = 1, and F(n) = F(n-1) + F(n-2) for n > 1. First, implement this using simple recursion, then optimize your function using dynamic programming to store and re-use computed values.
Solution:
def fibonacci(n, computed = {0: 0, 1: 1}):
if n not in computed:
computed[n] = fibonacci(n - 1, computed) + fibonacci(n - 2, computed)
return computed[n]Problem 4: Sum of Natural Numbers (Recursive Algorithm)
Write a function that computes the sum of all natural numbers from 1 to n using a recursive algorithm. Compare the recursive solution with an iterative solution and discuss the differences.
Solution:
def recursive_sum(n):
if n <= 1:
return n
else:
return n + recursive_sum(n - 1)
def iterative_sum(n):
return n * (n + 1) // 2Problem 5: QuickSort (Divide and Conquer)
Implement the QuickSort algorithm which sorts an array of integers. QuickSort is a Divide and Conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot.
Solution:
def quicksort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quicksort(left) + middle + quicksort(right)Problem 6: Implementing a Stack using Recursion (Recursive Algorithm)
Implement a stack data structure using recursion. Your stack should have push, pop, and peek functions.
Solution:
class Stack:
def __init__(self):
self.stack = []
def push(self, item):
self.stack.append(item)
def pop(self):
if len(self.stack) < 1:
return None
return self.stack.pop()
def peek(self):
if self.stack:
return self.stack[-1]
return NoneRemember, the aim of these practice problems is to get a hands-on understanding of the different algorithm types, how they work, and where they can be applied. Try to solve all the problems and compare the solutions to see the difference between these algorithm types. Good luck!
In the next chapter, we will explore more advanced algorithm types and their applications in real-world problem-solving. Stay tuned!
4.5 Practice Problems of Chapter 4: Basic Algorithm Types
Problem 1: Binary Search (Divide and Conquer)
Given a sorted list of n integers and a target integer x, write a function that finds the position of x in the list using a binary search algorithm. Remember, binary search operates by effectively dividing the problem in half with each step.
Solution:
def binary_search(list, x):
low = 0
high = len(list) - 1
while low <= high:
mid = (high + low) // 2
if list[mid] < x:
low = mid + 1
elif list[mid] > x:
high = mid - 1
else:
return mid
return -1Problem 2: Coin Change (Greedy Algorithm)
Given a list of denominations of coins and a value n, write a function that calculates the minimum number of coins needed to make change for n. Use a greedy algorithm that always selects the largest denomination less than or equal to the remaining amount to be changed out. Test your function with various coin sets, like the standard US or Euro denominations.
Solution:
def coin_change(coins, n):
coins.sort(reverse=True)
count = 0
for coin in coins:
while n >= coin:
n -= coin
count += 1
if n == 0:
return count
return countProblem 3: Fibonacci Series (Dynamic Programming)
Write a function to calculate the nth Fibonacci number. The Fibonacci series is defined as: F(0) = 0, F(1) = 1, and F(n) = F(n-1) + F(n-2) for n > 1. First, implement this using simple recursion, then optimize your function using dynamic programming to store and re-use computed values.
Solution:
def fibonacci(n, computed = {0: 0, 1: 1}):
if n not in computed:
computed[n] = fibonacci(n - 1, computed) + fibonacci(n - 2, computed)
return computed[n]Problem 4: Sum of Natural Numbers (Recursive Algorithm)
Write a function that computes the sum of all natural numbers from 1 to n using a recursive algorithm. Compare the recursive solution with an iterative solution and discuss the differences.
Solution:
def recursive_sum(n):
if n <= 1:
return n
else:
return n + recursive_sum(n - 1)
def iterative_sum(n):
return n * (n + 1) // 2Problem 5: QuickSort (Divide and Conquer)
Implement the QuickSort algorithm which sorts an array of integers. QuickSort is a Divide and Conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot.
Solution:
def quicksort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quicksort(left) + middle + quicksort(right)Problem 6: Implementing a Stack using Recursion (Recursive Algorithm)
Implement a stack data structure using recursion. Your stack should have push, pop, and peek functions.
Solution:
class Stack:
def __init__(self):
self.stack = []
def push(self, item):
self.stack.append(item)
def pop(self):
if len(self.stack) < 1:
return None
return self.stack.pop()
def peek(self):
if self.stack:
return self.stack[-1]
return NoneRemember, the aim of these practice problems is to get a hands-on understanding of the different algorithm types, how they work, and where they can be applied. Try to solve all the problems and compare the solutions to see the difference between these algorithm types. Good luck!
In the next chapter, we will explore more advanced algorithm types and their applications in real-world problem-solving. Stay tuned!