Assignment #1 Stacks and Linked Lists

Programming Assignment #1


Stacks and Linked Lists
Description:
For this programming assignment, you will implement a Stack whose size can grow as elements are
inserted into the stack. You will build three different implementations of this Stack. Two of these
implementations will be array-based. Each of these two should take an initial capacity for the stack in
the constructor. The only difference between these implementations will be what happens when the
Stack is full. For the first implementation, ArrayStack, you should increase the size of the array by a
constant amount. For the second implementation, DoublingArrayStack, you should double the size of
the array. Finally, for the third implementation, you should implement a Stack using a Linked List.
You will now time your three implementations. For each version of your stack, push a large amount of
random numbers onto the stack (e.g. 1,000,000). Time how long this takes using the StopWatch class we
provided with the assignment. However, you should measure the total time at fixed intervals (e.g. 10000
push operations). For the array-based implementations, you should start with some small capacity
significantly smaller than the maximum number of push operations. For the ArrayStack, your increment
amount should also be significantly smaller than the number of push operations. You will then graph the
times for the three implementations. This process will allow you to see how your choice of
implementation can affect performance.
Coding Portion (50 Points):
 Start with the following template: Stack.h, and create three versions of the Stack (using templates
for the type of object) filling in all of the member functions.
 For the Linked List, you will need to implement another class for the nodes in the Linked List.
 Be sure to test the correctness of your algorithms and implementations. Ensure all stack
operations of stack ADT (push, pop, top, size, isEmpty) are implemented and tested to be
working as expected.
 Your code will be graded based on whether or not it compiles, runs, produces correct output,
whether or not your experimental setup is correct, and your coding style (does the code follow
proper indentation/style and comments).
Report (50 Points):
You will write a brief report that includes theoretical analysis, a description of your experiments, and
discussion of your results. At a minimum, your report should include the following sections:
1. Introduction. In this section, you should describe the objective of this assignment.
2. Theoretical Analysis. In this section, you should provide an analysis of the complexity of a push
operation. Describe the effect of a push operation and the advantages and disadvantages of the
three strategies. What is the complexity of a push (on average) for the different implementations?
What is the worst case complexity for the different implementations? Here, you should be able to
leverage the material presented in the classroom, and also as referenced in the textbook.
3. Experimental Setup. In this section, you should provide a description of your experimental setup,
which includes but is not limited to
a. Machine specification
b. How did you generate the test inputs? What input sizes did you test? Why? What
parameters did you use for your initial Stack size and increment amount in the case of the
ArrayStack?
c. How many times did you repeat each experiment?
4. Experimental Results. In this section, you should compare the performance (running time) of the
push() operation in the three different implementations to one another and to their theoretical
complexity.
a. Make a plot showing the running time (y-axis) vs. the number of push operations (xaxis). You must use some electronic tool (matlab, gnuplot, excel, …) to create the plot.
Hand-written plots will NOT be accepted.
b. Provide a discussion of your results, which includes but is not limited to:
i. Which of the three Stack implementations performs the best? Does it depend on
the input? Provide some reasoning behind your observation.
ii. To what extent does the theoretical analysis agree with the experimental results?
Attempt to understand and explain any discrepancies you note.