DS and Algorithms Exercises

Coding

1. Given the Queue.h and Queue.cpp files from iLearn. For this question you are required to write a driver/tester function in a separate file. Make any changes you feel necessary to the Queue.h and Queue.cpp files.

• Declare three queues q1, q2 and q3.
• Enqueue integers 10, 20, 30, 40 and 50 in order into q1. You must use a loop.
• Enqueue integers 30, 60, 90, 12 and 15 in order into q2. You must use a loop.
• Dequeue the integers from q1, multiply them by 4 and enqueue them into q3. You must use a loop.
• Dequeue the integers from q2, divide them by 2 and enqueue them into q3. You must use a loop.
• Output the values stored in q3.

2. Given the Linked List.h and LinkedList.cpp files given to you. Write a function in "LinkedList.cpp" called Minimum that determines the minimum value of the integers in the linked list and return that value to the caller. In addition, write a driver/tester function in a separate file to insert the following integers (15, 40, 30, 7, 8, 1) into the linked list. Call the Minimum function from the main to determine the minimum integer in the linked list and output the minimum value.

Written

1. What is output of the following code? A brief explanation of how you arrived at the answer is necessary.

int values = [17, 3, 5, 8, 9, 11, 13, 15, 1];

Stack s;
for (int i = 0; i < 9; i++)
s.push( values[ i ] );

int n = 25;
for (int i = 0; i < 4; i++)
{
n += s.pop( );
}

for (int i = 0; i < 2; i++)
{
n -= s.pop( );
}
cout << n;

2. Write the output value (displayed by "cout" steatement) of the following code and outline how you get the output value

myQueue.enqueue(200);
myQueue.enqueue(100);
myQueue.enqueue(500);
cout << myQueue.front() << endl;
// the function front() prints the element at the front of the queue.
myQueue.dequeue();
cout << myQueue.front() << endl;

3. What is the complexity of the following code (in big O notation), assuming that the cout statement has O(1) complexity and n > 2)? Explain your answer.

for (int i = 1; i < n ; i++)
for (int j = i; j < n ; j++)
cout << i + j;

4. Rank the following in order of increasing complexity O(N), O(N loglogN), O(2/N), O(N log(N²)), O(2^N).

5. Consider two stacks each of size 6. When you pop an element from the first stack you multiply it by 3 and add it to the second stack (if the second stack is not full). When you pop an element from the second stack you multiply it by 4 and add it to the first stack (if the second stack is not full).

Push numbers 1 to 5 to the first stack in order (i.e., push 1 first, then 2 and so on). Push numbers 6 to 10 to the second stack in order. First pop two numbers from the first stack (remember when you pop a number it is going to be added to the second stack). Then pop three numbers from the second stack (remember when you pop a number it is going to be added to the first stack).

a) What is the value in the top of the first stack?
b) What is the value at the top of the second stack?
c) What is the current size of the first stack?
d) What is the current size of the second stack?

6. Solve the following recurrence relation. Explain how you derive the solution.

x(n) = 4x(n-1) for n > 1, x(1) = 1