CSCI 3400 Homework 2
1. (25 Points) Write a C++ program that calculates the frequency of each number in the input number a
ay. In other words, you will count how many times each number appears in the a
ay.
For example, if the a
ay is
A = [-12, 3, -12, 4, 1, 1, -12, 1, -1, 1, 2, 3, 4, 2, 3, -12]
Then the output of your program should be
N Count
4 2
3 3
2 2
1 4
-1 1
-12 4
a) (20 Points) What is the complexity of your solution? What is the best-case or worst-case scenario for this problem?
) (5 Points) Can this problem be solved in (nlogn) time? How?
Please note that I am asking a C++ function generating this output. You do not have submit a source code. You can print the code and attach to your solutions.
2. (15 Points) Apply the merge sort to the following a
ay. Show how the a
ay is divided and then merged step by step.
A = [64, 19, 26, 14, 63, 40, 80, 75]
3. (10 Points) Find the complexity of T(n) = 3T(n/3) + n using the recursion tree method (expand the T(n) into sub function calls and count additional costs).
4. (10 Points) Find the complexity of T(n) = 4*T(n/2) + 1 using master theorem.
5. (10 Points) Find the complexity of T(n) = 4*T(n/3) + using master theorem.
6. (15 Points) Answer following questions.
True / False
Reason
7. (15 Points) Fill the following table, show your work.
Expression
Dominant Term
(?)