Data and Information Structures

CS 3304 – Data and Information Structures
Assignment 3
Due: 10/23/2022, 23:59
Submission: Submit your solutions as a single .zip file through Blackboard. .zip file will contain
– (Q1.) Class file for linked queue and a driver file for handling job requests.
– (Q2.) One cpp file that contains two functions and the main function.
– (Q3.) One pdf file that contains your solutions.
Q1 (30 pts). Write a linked queue class as a template class. You can use the linked queue class
given in your textbook (Figure 8.3A and Figure 8.3B). You can find the code on Blackboard
under “Course Content / Code Samples / Chapter 8”. You only need to convert this class to a
template. You can keep all the data and function components.
Write a program that reads a file named “jobs.txt” containing job requests that will be stored in
two queues. One queue will store high-priority jobs and the other one will store low-priority
jobs. The first letter in each line is the code for operation. E: Enqueue (Add to back), D:
Dequeue (Remove element from front), P: Print (Print all elements), S: Shift (Move the front
element to back). The second letter in each line is the letter for queue. H: High-Priority and L:
Low-Priority. For enqueue operation, the third value in the line is the id of the job. For instance,
“E H 12” should add Job 12 to the end of the queue. You need to read each line and perform
the requested operation. An example “jobs.txt” and console output is given below:
jobs.txt
E H 13
E H 9
E L 8
D H
E H 25
E H 34
P H
E L 13
E L 19
D L
P L
S H
E L 12
S L
E H 15
P L
D H
P H
Output
9 25 34
13 19
19 12 13
34 9 15
Note that, different input file (jobs.txt) will be used for
evaluation.
Q2 (30 pts). Write the following two functions and call those functions in the main function to
print the result.
a. (15 pts) Write a recursive C++ function named recursiveProductEven that accepts an
integer array and its length as parameters and returns the product of the even numbers
in the array using recursion without using iteration. For instance,
recursiveProductEven(a,5) will return -24 if array a contains {1,-2,3,6,2}. Hint: the
product of the even elements is equal to “first element * the product of the even
elements starting from the second element” if the first element is even. Otherwise, it is
equal to “the product of the even elements starting from the second element”.
b. (15 pts) Write a recursive C++ function named countLetters that accepts a String
parameter and returns the number of letters using recursion without using iteration. For
instance, countLetters(“CS 3304 – Data and Information Structures”) will return 30.
Q3 (40 pts).
a. (10 pts) Prove that if T(n) = 15n2 + 9n + 10, then T(n) = O(n2). Hint: You need to find two
positive constant values c and n0 such that T(n) ≤ cn2 for all n ≥ n0.
b. (10 pts) Suppose the running time of an algorithm is 2n2 + 13m2 + 6nm + 3m + 100,
where n and m are positive integers such that n ≥ m. Prove that this algorithm is O(n2).
c. (20 pts) Give an analysis of the running time (Big-Oh notation) for the following
algorithms:
int *arr = new int(n);
sum = 0;
i = 0;
while(i < n){ cin >> arr[i];
i+=2;
}
i = 1;
while(i < n){ cin >> arr[i];
i+=2;
}
i = 0;
while(i < sqrt(n)*10){ sum+=i; i++; } i = 8*n; while(i > 0){
sum-=i;
i–;
}
print(sum);
sum = 0;
i = 0;
while (i < 100000) { sum += i; i++; } i = 1; while (i