[Solved] ECGR3180 Assignment 2

1. Write code to implement the Karatsuba multiplication algorithm in the file linked in Assignment 2 (karatsuba.cpp) in Canvas (please do not rename file or use cout/cin statements in your solution). As a reminder, the algorithm uses recursion to produce the results, so make sure you implement it as a recursive function. Please develop your code in small

The test program (karatsuba_test.cpp) is also given. PLEASE DO NOT MODIFY THE TEST FILE. Upload only the completed karatsuba.cpp file. Make sure to double-check that you uploaded the correct file.

2. Write code for a function int sumDigits (int num) that will return the sum of the digits in an integer argument using recursion. The function must work for any integer entered. In main(), write a list of test cases (1 test per test case) and add comments for each test detailing what is being tested. Upload a single file named cpp with your code for sumDigits and main.

3. Programs A and B are analyzed and found to have worst-case running times no greater than and , respectively. Answer the following questions:
   1. Which program has the better guarantee on the running time for large values of N (N > 10,000)?
   2. Which program has the better guarantee on the running time for small values of N (N < 100)?
   3. Which program will run faster on average for N = 1000?

4. Solve the following recurrence relations using the Master theorem.a)

b)