COMP 2402 Winter 2021

Assignment 3

Due: Sunday February 28 23:55pm

Topics: Lec 1-8

no lates accepted

submit early and often

15% of final grade

Academic Integrity

You may:

● Discuss general (high-level) approaches with course staff and your classmates,

● Use code and/or ideas from the textbook and previous assignments (including solutions)

● Use a search engine / the internet to look up basic Java syntax,

● Send your code / screen share your code with course staff (although it is unlikely the course staff has the bandwidth to look at individuals’ code, unfortunately.)

You may not:

● Send or otherwise share code or code snippets or detailed algorithms with classmates,

● Use code not written by you, unless it is starter code or code from the textbook (and you should cite it in comments),

● Use a search engine / the internet to look up approaches to the assignment,

● Use code from previous iterations of the course, unless it was solely written by you,

● Use the internet to find source code or videos that give solutions to the assignment.

If you ever have any questions about what is or is not allowable regarding academic integrity, please do not hesitate to reach out to course staff. We will be happy to answer. Sometimes it is difficult to determine the exact line, but if you cross it the punishment is severe and out of our hands. Any student caught violating academic integrity, whether intentionally or not, will be reported to the Associate Dean and be penalized as follows:

● First offence: F in the course.

● Second offence: One-year suspension from program.

● Third offence: Expulsion from the University.

These are standard penalties. More-severe penalties will be applied in cases of egregious offences. For more information, please see Carleton University's Academic Integrity Policy.

How to Get Help

Workshop

● As with assignment 2, Alexa will hold a (totally optional, and yes, recorded) workshop to help you get started on this assignment. It will be on Thursday, February 11th 1:30-3pm (replacing much of Alexa’s office hours that day.) It will be on zoom, the usual lecture link. Come with paper to draw on!

Piazza

● Good for getting a quick response, since it goes to a wider audience than email.

● Good for viewing questions that other students have. Chances are, if you have the question, so does someone else. If tagged correctly (e.g. “a3” for assignment 3), you can easily see all questions relating to a particular subject.

● Good for general questions that don’t divulge your approach (e.g. “Am I allowed to use standard JCF data structures in my solution?” “Does anyone else get this strange “file not found” error when submitting?” etc.)

● Good for asking specific-to-you questions of the course staff, which you can ask “privately” to the Instructors on piazza. This gets you the benefits of a wider audience yet keeps your personal details private to course staff. (You can and should also contact Alexa this way.)

Office Hours

● Good for quick questions that may have some back and forth.

● Good for clarifications.

● Good for “tips and tricks”.

● Not good for debugging sessions. The person holding the office hour may have many people waiting, and as such cannot spend 20 minutes helping you debug, unfortunately. They may give you a push in the right direction, then ask you to go back in line while you work with that push, while they help someone else.

Discord

● Good for light social interactions and commiseration.

● Please remember that this discord is an official class discord, and as such you should keep your behaviour “professional”. Please be respectful. Jokes are great, just not at the expense of an individual or a specific group.

● This is not a good place for asking questions, as the course staff will be spending most of their time monitoring piazza. Piazza has a better system for tracking open questions and answers, and so it is more time efficient for the course staff to spend their time there instead of discord.

Grading

This assignment will be tested and graded by a computer program (and you can submit as many times as you like, your highest grade is recorded). For this to work, there are some important rules you must follow:

● Keep the directory structure of the provided zip file. If you find a file in the subdirectory comp2402a3 leave it there.

● Keep the package structure of the provided zip file. If you find a package comp2402a3; directive at the top of a file, leave it there.

● Do not rename or change the visibility of any methods already present. If a method or class is public leave it that way.

● Do not change the main(String) method of any class. Some of these are setup to read command line arguments and/or open input and output files. Don't change this behaviour. Instead, learn how to use command-line arguments to do your own testing.

Submit early and often. The submission server compiles and runs your code, and gives you a mark. You can submit as often as you like and only your latest submission will count. There is no excuse for submitting code that does not compile or does not pass tests.

● Write efficient code. The submission server places a limit on how much time it will spend executing your code, even on inputs with a million lines. For some questions it also places a limit on how much memory your code can use. If you choose and use your data structures correctly, your code will easily execute within the time limit. Choose the wrong data structure, or use it the wrong way, and your code will be too slow for the submission server to grade (resulting in a grade of 0).

Submitting and Server Tests

The submission server is now available here. If you have any issues please post on piazza with a clear description of the problem (the text of the error message) and we’ll help you as soon as we can.

When you submit your code, the server runs tests on your code similar to how the local tests work. These are bigger and better tests than the small number of tests provided in the “Local Tests” section further down this document. They are obfuscated from you, because you should try to find exhaustive tests of your own code. This can be frustrating because you are still learning to think critically about your own code, to figure out where its weaknesses are. But have patience with yourself and make sure you read the question carefully to understand its edge cases.

Warning: Do not wait until the last minute to submit your assignment. There is a hard 5 second limit on the time each test has to complete. If the server is heavily loaded, borderline tests may start to fail. You can submit multiple times and your best score is recorded.

Changes from Assignment 2’s Server:

● For Part C, it will now continue running tests even if you fail an earlier one. We were doing this for Part B already.

● For all parts, each test is now annotated with its purpose (correctness, edge case, or performance.)

● Generally, less than half the tests are for correctness (including edge cases). The remaining half is for performance, that is, are you using a good data structure for time and space? Remember, this course’s focus is on improving performance so to pass the part, you have to show you are using some of the concepts we are talking about in this course.

● The error messages try to guess what is going on a bit more, and tries to make suggestions on how you might improve based on the information it has. The script only has so much information, though, so it can only do so much (and sometimes it guesses wrong, as you’ve seen.)

The Assignment

Purpose & Goals

Generally, the assignments in this course are meant to give you the opportunity to practice with the topics of this course in a way that is challenging yet also manageable. At times you may struggle and at others it may seem more straight-forward; just remember to keep trying and practicing, and over time you will improve.

Specifically, assignment 3 aims to improve your understanding of the linked-list data structures we’ve been talking about by:

● Encouraging you to think about how you need to use and access data in your algorithm before choosing the data structure(s) for your data, with a focus on thinking about which of a List or a SSet is more appropriate, in a variety of problems,

● Seeing the value of ListIterators for linked lists, and

● Implementing parts of the List interface using DLList and SkiplistList as the backing data type, using some of the concepts we’ve been learning about. Hopefully you will contrast these solutions with the array-based data types to see where they must be different.

Setup

Start by downloading and decompressing the Assignment 3 Zip File (comp2402a3.zip), which contains a skeleton of the code you need to write. You should have the files: Part1.java, Part2.java, Part3.java, Part4.java, MyList.java, DLList.java, SkiplistList.java and Tester.java.

As with assignments 1 and 2, you can test Part B using the command line or input/output files. You can test Part C with the Tester class included in the zip file. As before, you’ll want to add your own tests as this is just given as a basis on which you should build. The submission server will do thorough testing; it is your job to read the specifications as carefully as possible, and to examine your own code for potential problems and test those cases.

If you are having trouble running these programs, figure this out first before attempting to do the assignment. Check the assignment 3 FAQ on piazza and ask a question there if you are stuck and course staff or another student will likely help you fairly quickly.

Part A: The Warmup

0.   [5 marks] Do at least 1 of the drills on cuLearn from Lec 8, 9, 10, or 11.

(Usually this is just part of your overall grade and you can do them at your leisure, but I want you to do at least one per assignment to move you towards the 10 required by end-of-semester.)

Part B: The Interface

As with assignments 1 and 2, you will be filling in the doIt method in each of the appropriate PartX classes. You can go back to assignments 1 and 2 as reference, and you may use the sample solutions as a starting point if you like.

You can download some (very limited) sample input and output files for each question as a zip file (a3-io.zip). If you find that a particular question is unclear, you can possibly clarify it by looking at the sample files for that question. Note that these are very limited tests; you can and should add to them to test your code more thoroughly as the server tests are much more extensive.

Unless specified otherwise, "sorted order" refers to the natural sorted order on Strings, as defined by String.compareTo(s).

1. [5 marks] (Assignment 2.3 Redux) Read the input one line at a time, and output the last x distinct lines in sorted order, where x>=0 is a parameter to the doIt method. If there are fewer than x lines, print the

2. [7 marks] Read in the input one line at a time and output a line if it is the maximum over the last x lines, where x>=0 is a parameter to the doIt method. That is, output a line if there are at least x lines total, and this line is the maximum of the x-1 lines previous to the current one and the current one. For example, input lines “y”, “a”, “b”, “p”, “p” with x=3 would output “p”, “p” since p is the maximum of {a, b, p} and p the second p is the maximum of {b, p, p}. We don’t print out y because there are not 2 other elements to compare it to when we read it in. Note that with this definition, when x=0 every line is a maximum. As another example, input lines “x”, “e”, “b”, “e”, “c”, “d” with x=3 would output “e”. To get full points, try to use as little extra space and time as possible.

3. [8 marks] Read in the input one line at a time and output a new line if it is a prefix of some previous line. For example, input lines “abc”, “def”, “abc”, “de”, “ef”, “efg” would output “abc”, “de” because they are prefixes of lines that come before them. The String startsWith method may be helpful here. To get full points, try to use as little extra space and time as possible.

4. [10 marks] Read in the input one line at a time and output a new line if it is a substring of some previous line. To get full points, try to use as little extra space and time as possible. For example, input lines “abc”, “def”, “abc”, “de”, “ef”, “efg” would output “abc”, “de”, “ef” because they are all substrings of lines that come before them. To get full points, try to use as little extra space and time as possible.

Hint: A string u is a substring of string s if it is a prefix of some suffix of s.

Note: Getting full points here may be challenging! A string of length k has k+1 suffixes (including the empty suffix), that combine to have lengths 0+1+2+...+k=O(k2). To pass the last performance test, you will have to think of a better way of storing suffixes.

Note: the JCF SortedSet interface doesn’t have an explicit find(x) method; rather, you have to combine the tailSet(x) and first() methods.

Note: You can use more than one data structure to store your data. As long as you’re not increasing the space by more than a constant factor, you should be fine. (As in, having two data structures of size s is still asymptotically the same as having one data structure of size s.)

Part C: The Implementation

Files Provided

The starter code contains the DLList and SkiplistList classes, which are implementations of the provided MyList interface. Part C involves you completing implementations of 5 methods within these two classes, most of which will be familiar to you. These are described in more detail below.

Your Tasks

5. [5 marks] (Assignment 1.4 Redux) In the DLList class, implement

public MyList shuffle(MyList other)

Return a new DLList that results from alternating individual elements from this and other, as with the shuffle on assignment 1.

If the given lists are not of equal length, just place the extra elements onto the end of the returned DLList.

6. [ 5 marks] (Assignment 2.C Redux) In the DLList class, implement

public void shrink()

that “shrinks” the DLList by repeatedly removing pairs of consecutive duplicates. For example, if the list is [c,a,c,c,a,b,b,b]then shrink will make the list be [c,b].

7. [10 marks] In the DLList class, implement

public MyList chop(int i)

that chops our list into two parts at index i. The DLList this contains elements from indices 0,…,i-1, and the returned list is a DLList that contains elements from indices i, …, n-1. This should work for all indices from 0 to n, where n is the size of this.

For example, suppose list=[0,1,2,3]. Then list.chop[3] returns [3] and list becomes [0,1,2].

Note: The DLList class provides a built-in ListIterator that iterates through a DLList. You can instantiate such an Iterator with code like:

// get an iterator that initially is at index 0

ListIterator it1 = new Iterator(this, 0);

// get an iterator over the DLList variable, initially at index i

ListIterator it2 = new Iterator(, i);

8. [10 marks] (Assignment 1.6 Redux) In the SkiplistList class, implement

public void reverse()

Reverse the SkiplistList without using recursion or too much extra space.

Hint: How would you reverse a SLList? Start there then build up.

Note: To get all the points and glory, try to implement this in O(1) space and O(n) time.

9. [15 marks] In the SkiplistList class, implement

public MyList chop(int i)

that chops our list into two parts at index i, as in 7.

Note: The SkiplistList class provides a built-in Iterator that iterates through a SkiplistList. You can instantiate such an Iterator with code like:

Iterator it = this.iterator();


Local Tests

For Part B, you can download some sample input and output files for each question as a zip file (a3-io.zip). Once you get a sense for how to test your code with these input files, write your own tests that test your program more thoroughly (the provided tests are not exhaustive!)

For Part C (DLList, SkiplistList), a Tester class is provided with some tests of the provided methods. I recommend you add tests to Tester.java to test your DLList and SkiplistList locally (as opposed to on the server).

Testing suggestions:

● Test incrementally, that is, bit-by-bit,

● Test edge cases, e.g. empty files, empty lists, parameters of odd or even sizes,

● Use small test cases at first, then go bigger only when necessary,

● Test individual methods as you write them, even. As in: you can test an incomplete method to make sure it’s doing what you’re expected thus far.

Server Tests

See the “Submitting and Server Tests” section further up this document.

Tips, Tricks, and FAQs

This section may be updated as the assignment progresses, but for the most up-to-date FAQ, please see the Assignment 3 FAQ post on piazza (and the a3 filter.)

How should I approach each problem?

● Make sure you understand it. Construct small examples, and compute (by hand) the expected output. If you aren’t sure what the output should be, go no further until you get clarification.

● Now that you understand what you are supposed to output, and you’ve been able to solve it by hand, think about how you solved it and whether you could explain it to someone. How about explaining it to a computer?

● If it still seems challenging, what about a simpler case? Can you solve a similar or simplified problem? Maybe a special case? If you were allowed to make certain assumptions, could you do it then? Try constructing your code incrementally, solving the smaller or simpler problems, then, only expanding scope once you’re sure your simplified problems are solved.

How should I test my code?

● You should be testing your code as you go along.

● Start small so that you can compute the correct solution by hand.

● Edge cases.

● Large inputs. Random inputs. For time.