Reference no: EM132592557

CSC2401 Algorithms and Data Structures - University of Southern Queensland

Question 1

Task 2.1 demonstrates how to create a recursive function factorial(int n).
Task 2.6 demonstrates how to perform Tail Optimization to the recursive function square(int n) and transform it to a tail recursive function.
We can follow the example and apply Tail Optimization to change factorial(int n) to a tail recursive function.

Write a C++ program which
• Prompts user to input an integer n smaller than 10;
Please enter an integer n less than 10:

• Uses a Tail Recursive version of factorial(int n) to calculate factorial n;
• Outputs (e.g. n= 7) before terminating the program:
Factorial 7 = 5040

Submit your C++ program as <StudentID>Q1.cpp.

Question 2 - Merge Sort Pseudocode:
void merge_sort(vector<int>& a, int from, int to){ if (from == to) return;
int mid = (from + to) / 2; merge_sort(a, from, mid); merge_sort(a, mid + 1, to); merge(a, from, mid, to);
}
C++ code:
void merge(vector<int>& a, int from, int mid, int to){ int n = to - from + 1;
vector<int> b(n); int i1 = from; int i2 = mid + 1; int j = 0;
while (i1 <= mid && i2 <= to) { if (a[i1] < a[i2]) {
b[j] = a[i1]; i1++;
} else {
b[j] = a[i2]; i2++;
} j++;
}
while (i1 <= mid) { b[j] = a[i1]; i1++;
j++;
}
while (i2 <= to) { b[j] = a[i2]; i2++;
j++;
}
for (j = 0; j < n; j++) { a[from + j] = b[j];
}
}

Analyze Merge sort listed above and express its time complexity in Big O notation. You have to show your working and reasoning.
Submit your answer as <StudentID>Q2.pdf.

Question 3
Task 3C.5 uses Linear Search to perform searching. Task 3C.6 uses Binary Search to perform searching. Write a C++ program which
• Prompts user to input an integer n larger than 100 and less than nmax = 1,000,000 as shown below
Please enter an n (100 < n < 1,000,000):

• Generates a vector V of n random integers between 1 and imax =100,000,000;
• (nmax and imax may have to be adjusted according to the capability of your PC.)
• Calculate int T:
o X =((V.at(n/4) + V.at(n/2) + V.at(3n/4))) mod n
o T = V.at(X)
o Example:
o n = 1,000,000
o imax = 100,000,000
o V.at(n/4) = V.at(250,000) = 123,456
o V.at(n/2) = V.at(500,000) = 987,654,321
o V.at(3n/4) = V.at(750,000) = 67,584,220
o X = (123,456 + 987,654,321 + 67,584,220 ) mod 1,000,000
= 361,997
o T = V.at(361,997)
• Use the random number (determined at run time) at position X of the vector as the value T for searching i.e. T = V.at(X); (we cannot use V.at(X-1) in case X
=0).
• Search the same vector for T using Linear Search, and Binary Search;
• Time the two searches;
• Repeat with the same n a number of time to get an average time.
• Repeat with six different values of n;
• Show the search result in two tables, one for each search;
• Plot the two tables in one graph using n as x-axis and time as y-axis similar to the graphs shown below:

• You have to provide proper labelling and units for the graph

a) Submit your program as <StudentID>Q3.cpp
b) Submit your graph as <StudentID>Q3.pdf

Attachment:- Algorithms and Data Structures.rar