## Description

## The Assignment

This assignment is about using the Java Collections Framework to accomplish some basic text-processing

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.

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. You should not need to modify Part0.java, it is a template.

You can download some sample input and output files for each question as a zip file (a1-io.zip). If

you find that a particular question is unclear, you can probably clarify it by looking at the sample files for

that question.

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!)

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.

1. [10 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, but with consecutive duplicates removed.

2. [10 marks] Read the input one line at a time and output the current line if and only if it is strictly

larger than all other lines read so far or strictly smaller than the previously outputted line. If this

is the first nonempty line you read, it is considered larger than anything you’ve read so far.

(Here, larger is with respect to the usual order on Strings, as defined by String.compareTo()).

3. [10 marks] Read the input one line at a time. If you read less than 1000 lines, then do not output

anything. If you read less than 2402 lines, then output the 1000th line in sorted order of the

input lines. If you read 2402 or more lines, then consider only the last 2402 lines, and output the

1000th line in sorted order from the last 2402 lines. For full marks, your code should be fast and

should never store more than 2403 lines.

4. [10 marks] Read the input one line at a time and output the current line ℓ if and only if none of

the previous lines starts with ℓ.

5. [10 marks] Read the input one line at a time until you have read all lines. Output all the lines in

sorted order (as defined by String.compareTo(s)).

6. [10 marks] For this question, you may assume that every input line is distinct. Read the entire

input one line at time. If the input has less than 901 lines, then do not output anything.

Otherwise, output the line ℓ that has exactly 900 lines greater 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 901 lines.

7. [10 marks] The input contains special lines: “***reset***”. Read the entire input and break it

into blocks of consecutive lines 𝐵1, … , 𝐵𝑘, where 𝐵1 is a block that contains one line, 𝐵2 – two

lines, 𝐵3 – three lines, … 𝐵𝑘 contains 𝑘 lines (or less). When you read the “reset” line, you add it

to the current block and reset the size of the next block to 1.

So that following strings are

broken into blocks of size 1, 2, 3, … lines, until you read another “reset” string and reset the size

again. And so on. When you are done reading all the strings, output the blocks in reverse order

𝐵𝑘,𝐵𝑘−1, … , 𝐵3, 𝐵2,𝐵1 but preserving the order of the lines within each block.

8. [10 marks] Assume your input consists of 𝑛 lines. Read the input one line at a time until you

have read all lines.

Treat the lines as if they are numbered 0, … , 𝑛 − 1. Note, there can be

duplicates. Output a permutation 𝜋0, 𝜋1, … , 𝜋𝑛−1 of {0, … , 𝑛 − 1} so that 𝜋0 is the number of

the smallest line, 𝜋1 is the number of the second smallest line, … , and 𝜋𝑛−1 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 𝑖 ∈

{0, … , 𝑛 − 1}. The numbers for duplicates should be outputted in the same order in which the

lines were read.

9. [10 marks] Read the input one line at a time and output the current line if and only it has

appeared at least 3 times before.

10. [10 marks] For this problem you may assume that every input line is distinct. Read the input one

line at a time and assume that the lines are numbered 0, … , 𝑛 − 1. Your output should begin

with the largest line in the input.

Assume its number is 𝑖. Next, output the largest line among the

lines numbered 𝑖 + 1, … , 𝑛 − 1. Assume its number is 𝑗, where 𝑗 > 𝑖. Next, output the largest

line among the lines numbered 𝑗 + 1, … , 𝑛 − 1. And so on. The last line of your output will be

the last line of the input. (Here, largest is with respect to the usual order on Strings, as defined

by String.compareTo()). (Hint: Do not store all the lines. This problem can be solved very

efficiently with an ArrayList. Think about your solution before you start coding.)

## Tips, Tricks, and FAQs

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.

• Use small tests first so that you can compute the correct solution by hand.

• For testing, replace big numbers (like 1000 or 2402 lines in Part 3) with small (3 or 5). Don’t

forget to change them back before submitting to the server.

• Think about edge cases, e.g. empty lists, lists of different lengths, duplicates, etc.

• Think about large inputs, random inputs.

• Test for speed.