1. (30 pts) Implement a stack ADT using STL vector to support the operations: push(), pop(), top(), empty(). 2. (10 pts) Test the operations of the stack class for correctness. What is the running time of each operation? Express it using the Big-O asymptotic notation. 3. Stack Application Use the implemented stack class as an auxiliary data structure to compute spans used in the financial analysis, e.g. to get the number of consecutive days when stack was growing.

Definition of the span: Given a vector X, the span S[i] of X[i] is the maximum number of consecutive elements X[j] immediately preceding X[i] such that X[j] X[i] Spans have applications to financial analysis, e.g., stock at 52-week high 1. Example of computing the spans S of X. X 6 3 4 5 2 S 1 1 2 3 1 2. Compute the spans based on the definition above: Algorithm spans1(x) Input: vector x of n integers Output: vector s of spans of the vector x for i = 0 to n-1 do j = 1 while (j <= i ^ x[i-j] <= x[i]) j = j + 1 s[i] = j return s

1. Test the algorithm above for correctness using at least three different input vectors. 2. What is the running time function of the algorithm above? The function should define the relation between the input size and the number of comparisons perform on elements of the vector. How can you classify the algorithms using the Big-O asymptotic notation and why? 3. Compute the spans using a stack as an auxiliary data structure storing (some) indexes of x. Algorithm spans2: (a) We scan the vector x from left to right (b) Let i be the current index (c) Pop indices from the stack until we find index j such that x[i] < x[j] is true (d) Set s[i] = i j (e) Push i onto the stack 4. Test the second algorithm (spans2) for correctness using at least three different input vectors. Your program should run correctly on TAs input. 5. What is the running time function of the second algorithm? The function should define the relation between the input size and the number of comparisons perform on elements of the vector. How can you classify the algorithms using the Big-O asymptotic notation and why? Compare the performance of both the algorithms. 6. Programming style, and program organization and design: naming, indentation, whitespace, comments, declaration, variables and constants, expressions and operators, line length, error handling and reporting, files organization.