## Description

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.