600.226: Data Structures (Spring 2017)

Assignment 1: Warming Up

Overview

The first assignment is mostly a warmup exercise to refresh your knowledge of Java. But we also snuck a small ADT problem in there…

Problem 1: Unique Numbers (50%)

Your first task is to write a simple Java program Unique that analyzes the command line it is given in a peculiar way. The program accepts any number of integers as command line arguments and prints each unique integer it was presented with to standard out. For example, the invocation

java Unique 0 0 1 0 1 0 0 0 10 1

could generate the output

0
1
10

while the invocation

java Unique 1 9 2 3 1 4 9 5 3 6 0

could generate the output

1
9
2
3
4
5
6
0

instead. Note that output order doesn’t really matter as long as you print the correct set of numbers, one line per number, without any additional output!

As an added complication, you are not allowed to use any Java classes that serve as data structures, specifically not Java collection classes like ArrayList or HashMap. Of course you can use regular Java arrays, and in fact that’s probably the best way to go; the only “problem” is that we don’t specify an upper limit on the number of arguments, you’ll have to figure out how to deal with that…

Hints

Problem 2: Counter Varieties (30%)

Your second task is to write a number of “counters” that can be used interchangably (at least as far as Java is concerned). You are given the following interface Counter.java (which you can also download from Piazza):

/** The essence of any counter. */
public interface Counter {
  /** Current value of this counter. */
  int value();
  /** Increment this counter. */
  void up();
  /** Decrement this counter. */
  void down();
}

Develop the following:

All of your implementations should be “resetable”, and each should contain a main method that tests whether the implementation works as expected using assert as we did in lecture (this is a simple approach to unit testing, we’ll cover a better approach later).

Finally, make sure that your three counters work with the PolyCount.java test program we provide on Piazza; it’s probably a good idea to read and understand it…

Hints

Problem 3: Uninitialized Arrays (20%)

In lecture we derived an algebraic specifications for the abstract data type Array. I mentioned that it’s easier to specify the ADT if we make sure that instances are initialized to some known value when they are created using the new function.

Following the example specification for Array, develop a specification for uninitialized arrays. Note that even “uninitialized” arrays still need a length, but they do not have an “initial value” that gets put into every slot of the array by default; without an “initial value” it’s of course difficult to say what the get function should produce if nothing has been assigned to a slot yet.

You will have to introduce at least one new (as in not there already!) function; you’ll also have to adjust preconditions and axioms to make things work. Write up the algebraic specification for this kind of UglyArray in the format we used in lecture and comment on the differences to Array.

Even More Hints

Deliverables

You must turn in a zipped (.zip only) archive containing all source code, your README file, and any other deliverables required by the assignment. The filename should be HW##-jhed.zip with ## replaced by the 2-digit number (use leading 0s) of this assignment (see above) and jhed replaced by your Blackboard login. (For example, Peter would use HW03-pfroehl1.zip for his submission of Assignment 3.) The zip should contain no derived files whatsoever (i.e. no .class files, no .html files, etc.), but should allow building all derived files. Include a plain text README file (not README.txt or README.docx or whatnot) that briefly explains what your programs do and contains any other notes you want us to check out before grading. Your answers to written problems should be in this README file as well. Finally, make sure to include your name and email address in every file you turn in (well, in every file for which it makes sense to do so anyway)!

Grading

For reference, here is a short explanation of the grading criteria; some of the criteria don't apply to all problems, and not all of the criteria are used on all assignments.

Packaging refers to the proper organization of the stuff you hand in, following both the guidelines for Deliverables above as well as the general submission instructions for assignments.

Style refers to Java programming style, including things like consistent indentation, appropriate identifier names, useful comments, suitable javadoc documentation, etc. Many aspects of this are enforced automatically by Checkstyle when run with the configuration file available on Piazza. Style also includes proper modularization of your code (into interfaces, classes, methods, using public, protected, and private appropriately, etc.). Simple, clean, readable code is what you should be aiming for.

Testing refers to proper unit tests for all of the data structure classes you developed for this assignment, using the JUnit 4 framework as introduced in lecture. Make sure you test all (implied) axioms that you can think of and all exception conditions that are relevant.

Performance refers to how fast/with how little memory your program can produce the required results compared to other submissions.

Functionality refers to your programs being able to do what they should according to the specification given above; if the specification is ambiguous and you had to make a certain choice, defend that choice in your README file.

If your programs cannot be built you will get no points whatsoever. If your programs cannot be built without warnings using javac -Xlint:all we will take off 10% (except if you document a very good reason; no, you cannot use the @SuppressWarnings annotation either). If your programs fail miserably even once, i.e. terminate with an exception of any kind, we will take off 10% (however we'll also take those 10% off if you're trying to be "excessively smart" by wrapping your whole program into a universal try-catch).