Just complete parts 5, 8, 9 and 10. You'll be provided with the skeleton code for assignment 1 as well as the input and output examples you can use for part 5, 8, 9 and 10
COMP2402 - Assignment COMP 2402AB Fall 2022 − Abstract Data Types and Algorithms Assignment 1 COMP 2402 AB - Fall 2022 Assignment #1 Due: Monday, September 26, 23:59 Submit early and often. No late submissions will be accepted. Academic Integrity You may: • Discuss general approaches with course staff and your classmates, • Use code and/or ideas from the textbook, • Use a search engine / the internet to look up basic Java syntax. You may not: • Send or otherwise share code or code snippets with classmates, • Use code not written by you, unless it is 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 Dean and be penalized. Please see Carleton University's Academic Integrity page. 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 comp2402a1 leave it there. ● Keep the package structure of the provided zip file. If you find a package comp2402a1; directive at the top of a file, leave it there. https://carleton.ca/registrar/academic-integrity/ COMP 2402AB Fall 2022 − Abstract Data Types and Algorithms Assignment 1 ● 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 Testing The submission server is ready: here. If you have issues, please post to Discord to the teaching team (or the class) and we’ll see if we can help. When you submit your code, the server runs tests on your code. 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. If the server is heavily loaded, borderline tests may start to fail. You can submit multiple times and your best score is recorded. Start by downloading and decompressing the Assignment 1 Zip File (comp2402a1.zip), which contains a skeleton of the code you need to write. You should have the files: Part0.java, Part1.java, Part2.java, Part3.java, Part4.java, Part5.java, Part6.java, Part7.java, Part8.java, Part9.java, and Part10.java. The skeleton code in the zip file compiles fine. Here's what it looks like when you unzip, compile, and run Part0 from the command line: alina@euclid:~$ unzip comp2402a1.zip Archive: comp2402a1.zip inflating: comp2402a1/Part0.java inflating: comp2402a1/Part1.java inflating: comp2402a1/Part2.java http://cglab.ca:9091/~alina/upload1.html COMP 2402AB Fall 2022 − Abstract Data Types and Algorithms Assignment 1 inflating: comp2402a1/Part3.java inflating: comp2402a1/Part4.java inflating: comp2402a1/Part5.java inflating: comp2402a1/Part6.java inflating: comp2402a1/Part7.java inflating: comp2402a1/Part8.java inflating: comp2402a1/Part9.java inflating: comp2402a1/Part10.java alina@euclid:~$ javac comp2402a1/*.java alina@euclid:~$ java comp2402a1.Part0 blue red yellow violet [Hit Ctrl-d or Ctrl-z to end the input here] blue red yellow violet Execution time: 8.128651 alina@euclid:~$ If you are having trouble running these programs, figure this out first before attempting to do the assignment. If you are stuck, ask on Discord, and course staff or another student will likely help you fairly quickly. 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!) https://docs.oracle.com/javase/8/docs/technotes/guides/collections/overview.html COMP 2402AB Fall 2022 − Abstract Data Types and Algorithms Assignment 1 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