ECGR 3180
Assignment 2
1. (60 pts) 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. (20 pts) 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 main.cpp with your code for sumDigits and main.
3. (12 pts) Programs A and B are analyzed and found to have worst-case running times no greater than and , respectively. Answer the following questions:
a) Which program has the better guarantee on the running time for large values of N (N 10,000)?
b) Which program has the better guarantee on the running time for small values of N (N < 100)?
c) Which program will run faster on average for N = 1000?
4. (8 pts) Solve the following recurrence relations using the Master theorem. a)
b)
