Great Deal! Get Instant \$10 FREE in Account on First Order + 10% Cashback on Every Order Order Now

# CSCI 3400 Homework 2 1. (25 Points) Write a C++ program that calculates the frequency of each number in the input number array. In other words, you will count how many times each number appears in the...

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
(?)
Answered Same Day Jul 07, 2021

## Solution

Riya answered on Jul 08 2021
1. #include using namespace std;
int main()
{
int n,c;
cout
"Input the number of elements in the a
ay";
cin
n;
int a[n];bool vis[n];
for(int i=0;i vis[i]=false;
for(int i=0;i cin
a[i];
cout
"N"
" "
"COUNT"
endl;
for(int i=0;i {
if(vis[i]==false)
{
vis[i]=true;
c=1;
for(int j=i+1;j {
if((a[i]==a[j])&&(vis[j]==false))
{
vis[j]=true;
c++;
}
}
cout
a[i]
" "
c
endl;
}
}
}
a.The Time complexity of this solution is O(n
2
) and space complexity is O(n) where n is the number of
elements in the a
ay.
Best case: When the a
ay is sorted and duplicate element are found next to each other.
Worst case: When the a
ay is unsorted and duplicate elements are at maximum distance to each other.
.The problem can be solved in O(nlogn) time by using merge sort to sort the a
ay which has a time
complexity of O(nlogn) and then print the frequency of each element linearly.
Function freq(int a[])
{
function to perform merge sort
Mergesort();
int c=1;
for(int i=0;i{...
SOLUTION.PDF