Description
COMP 2402 AB 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
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.
COMP 2402 AB Assignment 2
This assignment contains two main parts:
Part 1 [50 marks]: A SuperStack is an extended stack that supports four main operations: the
standard Stack operations push(x) and pop() and the following non-standard operations:
β’ max(): returns the maximum value stored on the Stack.
β’ ksum(k): returns the sum of the top k elements on the Stack.
The zip file gives an implementation SuperSlow that implements these operations so that push(x)
and pop() each run in π(1) time, but max() and ksum(k) run in π(π) time. For this question, you
should complete the implementation of SuperFast that implements all four operations in π(1)
(amortized) time per operation.
As part of your implementation, you may use any of the classes in the
Java Collections Framework and you may use any of the source code provided with the Java version of
the textbook. Don’t forget to also implement the size() and iterator()methods.
Think carefully about your solution before you start coding. Here are two hints:
1. don’t use any kind of SortedSet or SortedMap, these all require Ξ©(log π) time per operation.
2. think about how the maximum on the stack changes as new elements are pushed.
Understanding this will help you design your data structure.
Part 2 [50 marks]: A DuperDeque is an extended Deque that supports seven operations: The standard
Deque operations addFirst(x), removeFirst(), addLast(x), and removeLast() and the
following non-standard operations:
β’ max(): returns the maximum value stored on the Deque.
β’ ksumFirst(k): returns the sum of the first k elements on the Deque.
β’ ksumLast(k): returns the sum of the last k elements on the Deque.
Again, the zip file provides an implementation DuperSlow that supports each of addLast(x) and
removeLast() operations in π(1) time per operation but requires Ξ©(π) time for the other
operations.
For this question, you should complete the implementation of DuperFast that implements all seven
operations in π(1) (amortized) time per operation. As part of your implementation, you may use any of
the classes in the Java Collections Framework and you may use any of the source code provided with the
Java version of the textbook.
Don’t forget to also implement the size() and iterator() methods.
Think carefully about your solution before you start coding. Here are two hints:
1. don’t use any kind of SortedSet or SortedMap, these all require Ξ©(log π) time per operation;
2. you can write additional functions to support your design choices; consider using one of the
techniques we’ve seen in class for implementing the Deque interface.
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 can modify the Tester class. For example you can change the β20β in
superTest(new SuperFast(), 20); to a smaller/bigger number to test less/more
operations.
β’ The Tester class provided with the assignment does a sequence of adds, followed by a
sequence of removes. This is a very basic test and far from an exhaustive one. It is strongly
recommended to modify the tester and design your own test cases. For starters, you can
interleave the add and remove operations. Take it even further by making the operation
sequence entirely random. This will help you to discover the weaknesses in your solution.
β’ You should be testing your code as you go along.
β’ Beware of integer overflow. Note that ksum is of type long – not int.
β’ Think about tricky cases. For instance, how do the operations behave when the stack/deque is
empty, or k > n or k <= 0? You can always refer to the slow implementations to answer
these questions. Although they are slow, they are correct implementations. They can also be
useful if you want to test your implementation against a reference one.
β’ int and Integer are not the same. Do not use them interchangeably.
β’ Use small tests first so that you can compute the correct solution by hand.
β’ Test for speed.
COMP 2402 AB Assignment 3
This assignment contains two main parts:
Part 1 [40 marks] β extension of the SSet interface that supports two extra operations
The IndexedSSet interface is an extension of the SSet interface described in the textbook that
supports two extra operations
β’ get(i): return the value at index i, in other words, return the value x in the set that is larger
than exactly i other elements in the set.
β’ rangecount(x, y): return the number of elements in the set that are between x and y
inclusive (x is not necessarily smaller than y).
Currently there are two identical implementations of the IndexedSSet interface using skiplists
included in the assignment called SkippitySlow and SkippityFast. Both of them are slow: each of
them has an implementation of get(i) and rangecount(x, y) that runs in πΊ(π) time, in the worst
case.
Modify the SkippityFast implementation so that the get(i) and rangecount(x, y)
implementations each run in π(ππππ) expected time and none of the other operations (add(x),
remove(x), find(x), etc.) have their running-time increased by more than a small constant factor.
Look at the SkiplistList implementation discussed in class for inspiration on how to achieve this.
Testing: For this assignment, you will have to test your own code thoroughly. The submission server will
perform a range of tests on your implementation. In case your code throws an exception, the server will
tell you which method threw the exception and what kind of exception it was.
Other than that, the
server will consume anything that you try to print to System.out or System.err, so the testing done
on the server will be almost completely opaque. It will only give you a generic error of the form “get(i)/
rangecount()/β¦ returns incorrect value”, or “Program timed out”. On the positive side, testing is
something you can do easily because SkippitySlow is a correct implementation that you can use to
test against. Be sure to test a good mix of operations that includes and interleaves add(x),
remove(x), get(i), find(x), size(), and rangecount(x, y).
Part 2 [60 marks] β Binary Tree Traversals and extra operations
For this part of the assignment, you will work with the BinaryTree class provided in the zip file. It
contains four uncompleted functions, which you are supposed to complete. For full marks, each of these
functions should run in π(π) time and must not use recursion. See the function traverse2() in
BinaryTree.java, which we also discussed in class, for an example of how to do tree traversal
without recursion. Note that this is just one example, and there could be other functions that you may
take inspiration from.
You need to implement the following:
1. The method leafAndOnlyLeaf() should return the number of leaves in the tree, or 0 if the
tree has no nodes at all. (A leaf is a node that has no left child and no right child.)
2. The method dawnOfSpring() should return the smallest depth in the tree that has leaves in it,
or -1 if the tree has no nodes.
3. The method monkeyLand() should return the number of nodes in the most populated depth
(the depth where there is the largest number of nodes). If there are multiple depths with the
maximum number of nodes, it should return the smallest of them.
4. The method bracketSequence() should return a string that gives the dot-bracket
representation of the binary tree. The dot-bracket representation of a binary tree can be
defined as follows:
β’ the dot-bracket representation of a tree with no nodes is the string “.”
β’ the dot-bracket representation of a binary tree with root node r consists of an open
bracket ( followed by the dot-bracket representation of r.left followed by the dotbracket representation of r.right followed by a closing bracket )
Some examples:
β’ the dot-bracket representation of the binary tree with only one node is (..)
β’ the dot-bracket representation of a 2-node binary tree is either ((..).) or (.(..))
depending on whether the root has no right child or no left child
β’ the dot-bracket representation of the height-1 binary tree with two leaves is ((..)(..))
Testing: The BinaryTree class implements a static method called randomBST(n) that returns a
random-looking binary tree. BinaryTree also implements the toString() method, so you can use
System.out.println(t) to view a representation of a BinaryTree that is closely related to the
method bracketSequence(). You can use this for testing your functions.
You should test your own code thoroughly since the testing done on the server will be mostly opaque.
On the server, your code will be tested on a Java virtual machine with a limited stack size. You can do
similar testing yourself by using the java -Xss argument (although you won’t have to worry about
this if you don’t use recursion).
Tips, Tricks, and FAQs
How should I approach each problem?
β’ For part 1, itβs best first to study how random access can be performed on skiplists (specifically,
ODS section 4.3) and then attempt to solve it. Also, look at the skeleton code and try to
understand how various operations work. Itβs okay if you do not understand every detail of the
code as long as you understand enough to do what you need to do.
β’ For part 2, you can look up the ODS textbook on how binary trees can be traversed in various
ways without recursion (specifically, ODS section 6.1.2).
You can find these traversals already
implemented in the skeleton code as well. If you are unsure what the operations are supposed
to do, the following figure might help you understand them better.
β’ Make sure you understand what the operations do. 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, and
then only expanding the scope once youβre sure your simplified problems are solved.
How should I test my code?
β’ You can modify the Tester class. For example, you can change the β20β in
skippityTest(20); to a smaller/bigger number to test less/more operations.
β’ The Tester class provided with the assignment does a sequence of adds, followed by a
sequence of gets and rangecounts. This is a very basic test and far from an exhaustive one. In
fact, the provided tester is meant to be more of a user guide to get started with the skeleton
code and by no means, a representative of the tests performed on the server side. Design your
own test cases, and throw in a good mix of add, remove, get, find, rangecount, and size.
Try to break your solution with the tester in every way you can think of. And, of course, donβt
forget to test with large test sizes.
β’ You should be testing your code as you go along. The slow (but correct) solutions can always be
taken as a reference when testing.
β’ Use small tests first so that you can compute the correct solution by hand.
β’ You will be dealing with pointer manipulation. Beware of null pointer exceptions.
β’ If you have print statements in your program that use System.out, the server will execute
those statements but ultimately will remove the output generated by those statements from
the response.
You probably already know by now how console output can be painfully slow.
Even worse, it could cause the testing program to crash if the output is large. So, be sure to
remove such statements you may have used for debugging or any other reason before
submitting your work.
β’ Test for speed.
COMP 2402 AB Assignment 4
The Assignment
This assignment contains only one part worth 100 marks.
A UltraStack is an extended stack that supports six main operations: the standard Stack operations push(x) and pop() and the following non-standard operations:
β’ get(i): returns the i -th element (from the bottom) on the Stack. β’ set(i, x): sets the value of the i -th element (from the bottom) on the Stack to x. β’ max(): returns the maximum value stored on the Stack. β’ ksum(k): returns the sum of the top k elements on the Stack.
The zip file gives an implementation of UltraSlow which implements these operations so that push(x), pop(), get(i) and set(i, x) each run in π(1) time, but max() and ksum(k) run in π(π) time.
You have to complete the implementation of UltraFast that implements all six operations. For UltraFast, the running time for get(i) and max() must be πΆ(π), and for push(x), pop(), set(i, x), and ksum(k) running time must not exceed πΆ(π₯π¨π π). As part of your implementation, you may use any of the classes in the Java Collections Framework and you may use any of the source code provided with the Java version of the textbook.
Don’t forget to also implement the size() and iterator() methods. The iterator() method returns an Iterator that iterates over the values in order, starting at the bottom and ending at the top of the Stack. Think carefully about your solution before you start coding.
Here are two hints:
1. Storing the partial summations and the partial maximums can save a lot of computation when you update an element in the Stack.
The following figure (on the next page) might help you better understand the idea.
2. Complete binary trees are much simpler to store implicitly using arrays. Heaps use the same idea to store the elements.