4.5 Practice Problems
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:
Problem 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:
Problem 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...