Problem 1. (10 points): Specify a minimal set of operations for the stack ADT. Answer example: ---------------- CreateStack () // Create an Empty Stack DestroyStack () // Destroy a Stack StackIsEmpty () // Determine whether a stack is empty Push (newItem, Succes) // Adds newItem to the top of a stack\\ // Success indicates whether the insertion was successful Pop (Item, Success) // Retrieve into Item and then removes the top of the stack\\ // Success indicates whether the insertion was successful Top (Item, Success) // Retrieve into Item and does not change the stack\\ // Success indicates whether the insertion was successful Problem 2. (20 points): Reverse elements in a linked list, without creating a new list. Implement the reverse function as a method for a $List$ class: class List { Node *Front; public: ... bool Reverse (); }; Answer example: --------------- bool List::Reverse () { Node *Prev1, *Prev2; if (Front == NULL) return true; // List is empty Prev2 = Front; Prev1 = Front->next; // Set initial value for Prev2 and Prev1 if (Prev1 == NULL) return true; // List has only one element Front = Prev1->next; // Set initial value for Front Prev2->next = NULL; // Set the new end of the list while (Front != NULL) { // while the end is not reached Prev1->next = Prev2; // Change the pointer direction Prev2 = Prev1; Prev1 = Front; // Advance Front = Front->next; // Advance (2) } Prev1->next = Prev2; // The last set Front = Prev1; // Set the new Front of the list return true; } Problem 3. (20 points): A palindrom is a string of characters that reads the same from left to right as it does from right to left. Use both a queue and a stack to determine whether a string is a palindrome. You have to implement the following function: bool isPalindrom (char S[]); Note: Consider the $Queue$ and the $Stack$ defined on page 8. Answer Example: bool isPalindrom (char w[]) { Queue Q; Stack S; // Enter the string in both a Queue and a Stack for (int i = 0; w[i] != 0; i++) { Q.Enqueue (w[i]); S.Push (w[i]); } // Compare elements while both of them are not empty while (!S.isEmpty ()) { char sp, sp; S.Pop (sp); Q.Dequeue (qp); if (sp != qp) return false; } // Because both have the same number of elements no other // tests are needed return true; } Problem 4. (10 points): Compare SelectionSort and MergeSort in terms of running times for best, average and worst cases. State complexities for each case/algorithm. void SelectionSort (int A[], int N) { for (int Last = N-1; Last >=1; --Last) { int L = Largest (A, Last+1); Swap (A[L], A[Last]); } } void MergeSort (int A[], int Left, int Right) { if (Left < Right) { int Center = (Left + Right) / 2; MergeSort (A, Left, Center); MergeSort (A, Center+1, Right); Merge (A, Left, Center+1, Right); } } Answer Example: --------------- & Best Case & Average & Worst Case Selection Sort: & $O(N^2)$ & $O(N^2)$ & $O(N^2)$ Merge Sort: & $O(N*log(N))$ & $O(N*log(N))$ & $O(N*log(N))$ MergeSort is performing better than SelectionSort for some n $>$ $n_0$ (see Table \ref{tab:visconst}). The constant $n_0$ depends on the implementation of the two algorithms (number of basic operations used in each case). Problem 5. (10 points): Write advantages and disadvantages of using {\it pointers} instead of an {\it array} to implement the ADT List. Answer Example: --------------- Pointers Advantages: Expandable (does not impose a fixed maximum length) Insert and Delete are done without shifting items Arrays Advantages: Find$K$th takes constant time Disadvantages: Limited size (and waste when not all space is used) Shift items during Insertion and Deletion Problem 6. (20 points): Transform the following recursive implementation for QuickSort in an iterative one. Is your solution maintaining the running time complexity for the worst case? Argument your answer. void QuickSort (int A[], int L, int R) { int PivotIndex = 0; if (R > L) { Partition (A, L, R, PivotIndex); QuickSort (A, L, PivotIndex - 1); QuickSort (A, PivotIndex + 1, R); } } Answer Example: --------------- void QuickSortI (int A[], int N) { Stack S; int PivotIndex, L, R; // Enter first interval S.Push (0); S.Push (N-1); // While there are intervals to be solved while (!S.isEmpty ()) { // Get an interval S.Pop (R); S.Pop (L); // If this interval is already closed try others if (R <= L) continue; // Partition this interval Partition (A, L, R, PivotIndex); // Enter its sub-interval for further processing S.Push (L); S.Push (PivotIndex-1); // QuickSrt (A, L, Pivot-1) S.Push (PivotIndex+1); S.Push (R); // QuickSrt (A, Pivot+1, R) } } Problem 7. (OPTIONAL - 15 points): Write the QuickSort partioning function for a double linked list, using the strategy presented in class. bool Partition (Node\& Front, Node\& Rear, Node\& Pivot); Consider that Swap function is given: void Swap (Node* A, Node* B) Answer Example: (see implementations formoredetails) --------------- bool Partition (Node& Front, Node& Rear, Node& Pivot) { int direction = 0; Node *L = &Front, *R = &Rear; while (L != R) { if (L->data > R->data) { direction = 1 - direction; Swap (L, R); } if (direction) R = R->prev; else L = L->next; } Pivot = *L; Pivot.next = NULL; Pivot.prev = NULL; } The Node defintion for problems 1-6: class Node { public: itemType value; Node* next; }; The Node defintion for problem 7: class Node { public: itemType value; Node *next, *prev; }; Queue definition for problem 3: class Queue { Node *Front, *Rear; public: Queue (); Queue (const List& L); ~Queue (); bool Enqueue (itemType); bool Dequeue (itemType&); bool isEmpty (); int Length (); }; Stack definition for problems 3 and 6: class Stack { Node *Front; public: Stack (); Stack (const Stack& L); ~Stack (); bool Push (itemType); bool Pop (itemType&); bool isEmpty (); };