Description
The Assignment
Start by downloading the Assignment 1 Zip File, which contains a skeleton of the code you need
to write. The file Part0.java in the zip file actually does something. You can use its doit()
method as a starting point for your solutions. Compile it. Run it. Test out the various ways of
inputting and outputting data.
This assignment is about using the Java Collections Framework to accomplish some basic textprocessing tasks. These questions involve choosing the right abstraction (Collection, Set,
List, Queue, Deque, SortedSet, Map, or SortedMap) to efficiently accomplish the task at
hand. The best way to do these is to read the question and then think about what type of
Collection is best to use to solve it. There are only a few lines of code you need to write to solve
each of them.
Here is a directory containing sample input and output files for each question. You can also
download all these files as a zip file. If you find that a particular question is unclear, you can
probably clarify it by looking at the sample files for that question.
Unless specified otherwise, “sorted order” refers to the natural sorted order on Strings, as defined
by String.compareTo(s).
Caution: It is always better to use c.isEmpty() than c.size()==0 to check if a collection is
empty. In some cases (and one that you may encounter in this assignment) c.size() is slow but
c.isEmpty() is always fast.
Assignment 1: Using the JCF 2020-12-12, 2:59 PM
https://cglab.ca/~morin/teaching/2402/assn/assn1.html Page 4 of 5
1. [5 marks] Read the input one line at a time until you have read all lines. Now output these
lines in the opposite order from which they were read.
2. [5 marks] Read the input one line at a time and output the current line if and only if it is
larger than any other line read so far. (Here, smaller is with respect to the usual order on
Strings, as defined by String.compareTo().
3. [5 marks] Read the input one line at a time and output only the last 5000 lines in the order
they appear. If there are fewer than 5000 lines, output them all. For full marks, your code
should be fast and should never store more than 5001 lines.
4. [5 marks] Read the input one line at a time and output the current line if and only if it is
different from every previous line.
5. [5 marks] Read the input one line at a time. When you are done, output all the lines in
reverse sorted order (so that “zebra” will appear before “apple”).
6. [5 marks] For this question, you may assume that every input line is distinct. Read the entire
input input one line at time. If the input has lines then don’t output anything.
Otherwise, output the line that has exactly 4000 lines smaller than . (Again, greater than
and less than are with respect to the ordering defined by String.compareTo().) For full
marks, you should do this without ever storing more than 4001 lines.
7. [5 marks] The input is broken into chunks of consecutive lines, where each pair of
consecutive chunks is separated by a line containing “—-snip—-“. Read the entire input and
break it into chunks . Then output the chunks in reverse order but
preserving the order of the lines within each chunk.
8. [5 marks] For this question, you are going to make a permutation array. Read the entire
input file. You may assume that each input line is distinct. If the file has lines, treat them
as if they are numbered . Now output a permutation of
so that is the number of the smallest line, is the number of the second
smallest line, … , and is the number of the largest line. (Again, smaller and larger refer
to the natural ordering on strings). Your output should consist of lines, where line
contains (the string representation of) , for each .
9. [5 marks] Read the input one line at a time and output the current line if and only if it is not
a prefix of some previous line. For example, if the some line is “zoodles” and some
subsequent line is “zoo”, then the line containing “zoo” should not be output.
10. [5 marks] For this problem you may assume that every input line is distinct. Your output
n < 4001
ℓ ℓ
C1 ,…, Ck Ck,…, C1
n
0,…, n − 1 π0 ,…, πn−1
{0,…, n − 1} π0 π1
πn−1
n i
πi i ∈ {0,…, n − 1}
Assignment 1: Using the JCF 2020-12-12, 2:59 PM
https://cglab.ca/~morin/teaching/2402/assn/assn1.html Page 5 of 5
should begin with the largest line in the input. Next should be the largest line that
appears after in the input. In general, line of your output should be the largest line that
appears after in the input. (Hint: You can do this very efficiently and easily with an
ArrayList. Think about your solution before you start coding.)
ℓ0 ℓ1
ℓ0 ℓi
ℓi−1
