SOLVED COMP 2402AB Assignment #1

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 COMP 2402AB  − Abstract Data Types and Algorithms Assignment 1 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 COMP 2402AB  − Abstract Data Types and Algorithms Assignment 1 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.