Assignment 2: Arrays Unlimited – 600.226: Data Structures (Spring 2017) 600.226: Data Structures (Spring 2017) General 600.226 Syllabus Schedule Course Policies Ethics Policies Piazza People Joanne Peter Staff Homework Assignment 1 Assignment 2 Assignment 3 Assignment 4 Assignment 5 Assignment 6 Assignment 7 Assignment 8 Assignment 9 Assignment 2: Arrays Unlimited Out on: Wed, February 8, 2017 Due by: Fri, February 17, 2017 before 10:00 pm Collaboration: None Grading: Packaging 10%, Style 10% (where applicable), Performance 10% (where applicable), Functionality 70% (where applicable) Overview The second assignment is mostly about arrays, notably our own array specifications and implementations, not just the built-in Java arrays. Of course we also once again snuck a small ADT problem in there… Note: The grading criteria now include 10% for programming style. Make sure you use Checkstyle with the correct configuration file from Piazza! Problem 1: Flexible Arrays (20%) Develop an algebraic specification for the abstract data type FlexibleArray which is like our original (bounded, initialized) Array ADT for the most part except that both its lower and its upper index bound are set when the array is created. Lower as well as upper bound can be any integer, provided the lower bound is less than or equal to the upper bound. The bounds are both inclusive. Write up the specification for FlexibleArray in the format we used in lecture and comment on the design decisions you had to make. Also, tell us what kind of array you prefer and why. Remember that written assignment parts should be submitted in your README plain text file. Note: Some programming languages, notably Pascal and Ada, support arrays of this kind instead of the zero-based arrays that are dominant in C and Java. Hints A FlexibleArray for which the lower bound equals the upper bound has exactly one slot. Your FlexibleArray is not the Array ADT we did in lecture; it doesn’t have to support the exact same set of operations. Feel free to add and remove operations based on the expected functionality of this variation. Problem 2: Revenge of Unique (40%) You wrote a small Java program called Unique for Assignment 1. The program accepted any number of command line arguments (each of which was supposed to be an integer) and printed each unique integer it received back out once, eliminating duplicates in the process. For this problem, you must start from the example solution we will post on Piazza for you. You will make two major changes to Unique as given: First, you’re going to modify the program to use our Array interface and our SimpleArray implementation (the Iterable versions, also available on Piazza for you), instead of basic Java arrays. In other words, you must not use any Java built-in array variables. Second, you’re going to modify the program to read the integers from standard input instead of processing command line arguments. So the resulting Unique program is invoked as java Unique with no further arguments. The program then waits for input from the user, who could for example type 1 9 2
3
1 4
9 5 3
6 0 and then hit the end-of-file key (that’s CTRL-D on Unix and CTRL-Z on Windows). At this point the program should output the unique numbers that were present in the input one per line, just like before: 1
9
2
3
4
5
6
0 Again, the files Unique.java, Array.java, and SimpleArray.java (as well as all necessary exception classes) will be available on Piazza by 2/11. Please use those official files, not your own versions of them. (Obviously Unique.java is not covered by the “do not modify provided files” rule, you must modify it in order to solve this problem.) Hints Reading numbers from standard input can be accomplished using a java.util.Scanner object that has been initialized with System.in which is Java’s name for the standard input stream. Make sure you hit return one last time at the end of your input and only then signal end-of-file with the appropriate key-combination for your operating system (this restriction doesn’t apply when you use I/O redirection to give input to the program, a highly recommended practice for testing). You will have to process an unbounded number of inputs, which requires that you keep track of how “full” the array is. When nothing fits into the array anymore, you’ll have to “grow” it somehow. The best approach is to make a new array that is double the size of original array when you are out of space. (We’ll talk about the reasons for doubling the size in lecture next week.) Do not try to change everything at once, there are too many “moving parts” to get things right that way. Instead, choose one thing to change, for example just the way input is given to the program, finish that, test it, and only then move on to the next thing. Remember: Baby steps, incremental development and testing! Problem 3: Sparse Arrays (40%) A sparse array is an array in which relatively few positions have values that differ from the initial value set when the array was created. For sparse arrays, it is wasteful to store the value of all positions explicitly since most of them never change. Instead, we want to store values only for the positions that have actually been changed. For this problem, you’re supposed to write a class SparseArray that implements the iterable Array interface we discussed in lecture (the same interface you use for Problem 2 above). Do not modify the Array interface in any way! Instead of using a plain Java array like we did for SimpleArray, your SparseArray should use a linked list of Node objects to store values, similar to the ListArray from lecture. However, your nodes no longer store just the data at a certain position, they also store the position itself! Here’s a rough outline of how your implementation could work: Start with an empty list (instead of the complete list we built in the constructor of ListArray). For put, check if the relevant position has been modified before (meaning a Node object exists for that position); if not, add a Node to the list for the position and its new value; otherwise update the correct Node to the new value. For get, check if the relevant position has been modified before; if not, return the default value; otherwise, return the value found in the relevant Node object. Important: Your Node class must be nested inside your SparseArray class with private visibility! Clients should not be able to “touch” Node objects in any way! (Don’t forget to add proper javadoc comments for your SparseArray class; in particular, include advice for clients trying to decide between the regular SimpleArray implementation and your new sparse implementation.) Testing As part of Assignment 1, we gave you a program called PolyCount that could be used to test the basic operation of a number of different Counter implementations. For this assignment, we’re giving you a similar program called PolyArray that can be used to test array implementations (some of the details are a bit more complex for technical reasons, but you don’t need to understand those for now). However, PolyArray is far from complete regarding test cases: the code in testNewLength and testNewGet only covers the first two axioms of the specification the code in testNewLengthWrong only covers the first precondition of the specification You need to modify PolyArray.java to add more test cases so that all axioms and preconditions will be tested. Of course, you should also use PolyArray to test your new SparseArray code: Once you’re done with PolyArray all three implementations should be fully tested when the program is run. Hints Your iterator for SparseArray doesn’t have to be particularly efficient; indeed, it’s rather tricky to make it work fast; don’t try. (Or rather: Only try if you’re bored!) Think about this: Someone creates a SparseArray with an initial value of 1. Then they put a few numbers different from 1 into the array. For example, the value of slot 4 might be 18. Now what should happen for put(4, 1)? What should the state of the sparse array be if all elements got changed to something other than the initial value, and then changed back again? Testing a precondition means testing that the correct exception is thrown when a bad parameter is provided. Note that the PolyArray we gave you doesn’t test iterators at all; it probably should since all array implementations (the ones we gave you and the one you wrote yourself) support iterators… Even More Hints Ensure that the version of your code you hand in does not produce any extraneous debugging output anymore! Any output not explicitly required by the assignment should always be written to System.err. Pay attention to edge cases in the input your classes and programs are expected to handle! For example, make sure that you handle the empty input in a reasonable way for Problem 2. 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).
