Assignment #1 - Stack basics, Time & space complexity, and CS2321 style

Objectives:

The main objectives of this assignment are:
• Provide an example of what programming assignments for this course should look like. In particular, you should pay attention to the style and types of comments and the additional program annotations that are used like @SpaceComplexity and @TimeComplexity.
• Review previous data structures and concepts (stacks: See here and here).
• Provide you with a data structure implemented two different ways which will be used for empirical comparisons in Assignment #2.
• Introduce time and space complexity (See: here and here).
• Make sure everyone is well prepared for the remaining assignments. For some of you this assignment may require review or study of Java components that you haven't used before. The assignment includes links to references that will help you understand basic features. It is vital that you have a solid understanding of these topics for this class. In particular, it will review (or introduce you to) generics, interfaces and iterators.
• Create a new stack with O(1) amortized costs (See: here).

The Assignment:

1. Getting Started: First, you should download and study the Assignment1.zip file. In particular, you should look at the actual data structure in MinSpaceStack.java. Here is a brief guide to help you understand all the important features without getting overwhelmed:
   1. Download and import the following zip file: Assignment1.zip. For Eclipse:
      1. Open Eclipse
      2. Choose "File → Import".
      3. Select the "General" category.
      4. Pick "Existing Projects into Workspace"
      5. Click on "Next"
      6. Select the button for "Select Archive File" and browse to/select the zip file.
      7. Click on "Finish"
      8. Two new projects have been added to the workspace: MinSpaceStack, which provides a complete implementation of a stack, and DynamicStack, which you will need to complete for the first assignment.
   2. First, look at the completed example in the MinSpaceStack project. You should start with the MinSpaceStack class, which is in the src folder's cs2321 package. Look at the fields used in the class (data and size), then look at and try to understand the most significant methods (push, pop, top, size, and isEmpty). Try to answer the following questions:
      • What is used to store the elements on the stack?
      • Where/what is the "top" of the stack?
      • Can you hypothesize why this is a "MinimumSpace" stack?
      • Is there any relationship between the size field and data's length?
      • What do each of the methods do?
      • Are all the methods correct?
   3. Make sure you understand generic types (the E and <E>) in the source code. These will be/were explained in class, but Sun's tutorial may also help: Generics.
   4. Make sure you understand the basics of interfaces. This class supports the Stack interface and the Iterable interface. Stack is defined in the net.datastructures package that is used throughout our text book. Iterable just means that the class can create an object that has the Iterator interface. The choice of implementation is explained in the source code.
   5. Notice the special annotations to indicate the space used by the data structure (@SpaceComplexity) and the time taken by methods (@TimeComplexity). These are essential for full credit on programming assignments.
   6. Pay attention to the special comments with TCJ and SCJ.
   7. Look at the main method's test cases. There are many different ways to perform testing, but these serve as a simple example of some tests that help demonstrate that the structure works. They also include some "empirical" tests that run simple experiments and measure the performance of the code. The second assignment will require that you run more of these tests.
2. You need to complete the DynamicStack class It will differ from the MinSpaceStack in the following details:
   • When more space is needed, the array size will be doubled.
   • Adding an item will, on average, take a constant amount of time (amortized O(1)). The worst case time taken by an insert will still be O(n). You should clearly indicate this in the algorithms by using two "annotations" about time complexity. There are annotations for worst case time, @TimeComplexity; amortized time, @TimeComplexityAmortized; and expected time, @TimeComplexityExpected.

Submission:

First, look at the following checklist:
1. Does the program compile on CS machines? (Programs that don't compile for us will not be graded)
2. Do you ever import from java.util. If so, be sure you only import allowed components (like Iterator, Exceptions, etc.). Unless the assignment specifically mentions it is permissible, you should never include any of java's native data structures.
3. Does the program meet all required interfaces?
4. Do all your methods have a @TimeComplexity indicator?
5. If any methods have a good amortized or expected cost, do they have both the @TimeComplexity and either @TimeComplexityAmortized or @TimeComplexityExpected
6. Do all your data structures (and other classes like iterators) have a @SpaceComplexity indicator?
7. Do you provide adequate TCJ and SCJ comments to prove your time and space complexity?
8. Is the indentation easily readable? You can have Eclipse correct indentation by highlighting all code and select "Source → Correct Indentation".
9. Have you removed any of the "cs2321" comments (/*#) that you may have accidentally copy/pasted?
10. Are comments well organized and concise?
If you have reviewed your code and all the criteria on the checklist are acceptable, follow the submission procedure.

Grading Criteria:

• A DynamicStack that correctly implements all the required interfaces and both push and pop have amortized cost of O(1): 60 points.
• Use of appropriate tags on all methods and classes to indicate complexities (@TimeComplexity and either @TimeComplexityAmortized or @TimeComplexityExpected): 20 points.
• Clear concise code with good commenting: 20 points.