While giving the answers to these questions consider the following:

Deliverables

Source code for each algorithm.

A report detailing the problem, algorithm, complexity analysis, and solution.

Test cases and results demonstrating the algorithms' performance.

Evaluation Criteria

Correctness and efficiency of the algorithms.

Clarity and depth of the report.

Effective demonstration of the algorithms through test cases.

Resources Academic resources on algorithms.

Programming environments C$++$

Questions

Question $1$: Greedy Algorithm Problem: Coin Change Problem Objective: Minimize the number of coins needed to make a specific amount of money. Task: Implement a greedy algorithm to determine the minimum number of coins needed for a given amount using available denominations. Constraints: Assume unlimited supply of coins for each denomination.

Question $2$: Divide and Conquer Algorithm Problem: Karatsuba Multiplication for Large Integers Objective: Multiply two large integers efficiently. Task: Implement the Karatsuba algorithm for multiplying large integers using the divide and conquer technique. Constraints: Use arrays or strings to handle the large size of the integers.

Question $3$: Brute Force Algorithm Problem: Traveling Salesman Problem $($TSP$)$ Objective: Find the shortest route that visits each city exactly once and returns to the origin city. Task: Implement a brute force algorithm to solve the TSP for a small number of cities. Constraints: Evaluate all permutations of cities to find the shortest path.