Description
One-Day Assignment 2 – Sort of Sorting
• Need to use stable sort
• Thankfully, Java’s Arrays.sort() is stable by default
• Just write a custom comparator to compare by first 2 characters, instead of
the entire string
// the overridden compare method
public int compare(String a, String b) {
return a.substr(0, 2).compareTo(b.substr(0, 2));
}
Take-Home Assignment 1a – Card Trading
• Start by assuming all cards Anthony owns are sold
• This would result in the highest possible profit, if no other restrictions exist
• Then, determine the cost for keeping a certain card type as a combo
• For a card type which Anthony has none of, he needs to buy 2 cards (2 * buy)
• For a card type which Anthony has one of, he cannot sell that card, and has to
buy one more (1 * sell, and 1 * buy)
• For a card type which Anthony has two of, he cannot sell both cards (2 * sell)
• Sort the cost for all card types, and pick the K smallest elements as
the card types to keep. Subtract the sum of these elements from the
profit (derived earlier) to get the final answer
Take-Home Assignment 1b – Best Relay Team
• Use a custom class to represent a Runner
• Contains the 1st leg timing, subsequent leg timings and name
• Use 2 arrays to store the Runners
• Sort one by 1st leg timing
• Sort the other by subsequent leg timings
• Pick the first runner A from the 1st leg timing array
• Pick the first 3 runners from the subsequent leg timing array, that are not
the same as runner A(since it is possible for the same runner to appear in
the front of both arrays
• Repeat the above for the second/third/fourth runner from the 1st leg
timing array
• Output the team that gives the best timing among the 4 possible options
Lab 4 – Generics
• Most Java API usage from this point on requires the use of generics
• Essentially a way to define the data type being used, much like arrays
• Eg. String[] versus ArrayList
• Can also be used for your own custom classes
• Eg. Student[] versus ArrayList
• Note that primitive data types (eg. int, double) cannot be used as
generics; you will need to use their relevant Java classes instead
• Eg. ArrayList, ArrayList
Lab 4 – Lists
• Two kinds of lists tend to be more frequently used in Java
• ArrayList and LinkedList (is a doubly linked list with tail reference)
• Main differences:
• Accessing elements within the list
• ArrayList offers O(1) time to access any element in the list
• LinkedList offers O(1) time to access elements at the front and back of the list only
• Inserting/deleting elements from the list
• ArrayList offers O(1) time to insert and delete from the back of the list only
• LinkedList offers O(1) time to insert and delete from the front or the back of the list
• Inserting/deleting from other positions (apart from the ones mentioned
above) runs in about O(n) time on average for both ArrayList and LinkedList
• For LinkedList accessing any position other than front and back result in
O(n) on average
Lab 4 – Lists
• For arrays, a Java class called Vector exists
• This is similar to the ArrayList class, but is “synchronised”
• Ie. used for multi-threading, by ensuring that only one thread can modify the
Vector at a given time
• However, performing this check makes it slightly slower as a result
• For this module, just the use of ArrayList is sufficient, as we do not
cover multi-threading
CS 2040 Lab 4 – ArrayList
Method name Description Time
.add(YourClass element) Adds element to the end of the list O(1)
.add(int index, YourClass element) Adds element to the position at index O(size() – index)
.clear() Empties the list O(n)
.contains(Object o) Checks if o is in the list, based off the object’s equals()
method
O(n)
.get(int index) Gets the element at index O(1)
.remove(int index) Removes the element at index O(size() – index)
.size() Returns the number of elements in the list O(1)
O(size() – index) is due to the need to shift all elements to the right of index when inserting/deleting
Lab 4 – LinkedList
Method name Description Time
.add(YourClass element) Adds element to the end of the list O(1)
.add(int index, YourClass element) Adds element to the position at index O(size() – index) or
O(index), whichever is
smaller
.clear() Empties the list O(n)
.contains(Object o) Checks if o is in the list, based off the object’s
equals() method
O(n)
.get(int index) Gets the element at index O(size() – index) or
O(index), whichever is
smaller
.remove(int index) Removes the element at index O(size() – index) or
O(index), whichever is
smaller
.size() Returns the number of elements in the list O(1)
Lab 4 – Stacks/Queues
• Special kinds of lists
• Stacks only allow inserting, accessing and deleting from the top of the stack in
O(1) time (first-in last-out)
• Queues only allow accessing and deleting from the front of queue, and
inserting from the back of the queue in O(1) time (first-in first-out)
Lab 4 – Stacks/Queues
• Queue is an interface, so you cannot initialize it using new Queue()
• Instead, use a LinkedList: Queue queue = new
LinkedList();
• Stack is not an interface, so you can use new Stack() directly
• Stack stack = new Stack();
• Note that the Stack class in Java extends the Vector class, so the use
of methods such as get(index), and add(index, element) is possible;
however, these methods should not be used in a pure stack
implementation
Lab 4 – Stack
Method name Description Time
.empty() Checks if the stack is empty O(1)
.peek() Retrieves the element at the top of the stack O(1)
.push(YourClass element) Adds element to the top of the stack O(1)
.pop() Removes and retrieves the element at the top of the
stack
O(1)
Lab 4 – Queue (using LinkedList)
Method name Description Time
.isEmpty() Checks if the queue is empty O(1)
.offer(YourClass element) Adds element to the end of the queue O(1)
.peek() Retrieves the element at the head of the queue O(1)
.poll() Removes and retrieves the element at the head of the
queue
O(1)
CS 2040 Lab 4 – LinkedList (again)
• Note that LinkedList supports operations from both Stack (excluding
the .empty() method) and Queue
• However, LinkedList does not extend Stack, so the following is not possible:
• Stack stack = new LinkedList();
• As such, it’s entirely possible to declare LinkedLists anytime you need
a stack or a queue:
• The top of the stack is the head of the LinkedList
• The front of the queue is the head of the LinkedList, while the back is the tail
of the LinkedList
• The .peek() method is consistent with both definitions (returns the element at
the head of the list)
Lab 4 – LinkedList (again)
Take-Home Assignment 2a – Join Strings
• Given a list of strings, concatenate them together, and output the
final string
• Main emphasis of the question is on concatenating strings together
• Concatenating strings (via str.concat() or the + operator) takes O(k) time,
where k is the length of the resulting string (see Tutorial 1, problem 2e)
• Using StringBuilder/StringBuffer’s .append() is slightly better (takes O(m)
time, where m is the length of the string that is added on), but still too slow
• Therefore, simply using the default string methods will not be fast enough
• Need to find a way to do so in O(1) time when handling queries
Take-Home Assignment 2b – Teque
• Create a custom data structure to support the push_back, push_front,
push_middle, and get operations
• Need to ensure all operations run in O(1) time
• This problem will also require the use of buffered IO methods
(covered in Lab 2 slides), due to the large input/output sizes (up to
1M lines!)
One-Day Assignment 3 – Coconut Splat
• Simulate a counting-out game
• A player’s hand has 4 possible states:
• 1. Both hands folded together (initial state)
• 2. Fist
• 3. Palm down
• 4. Behind back
• A player’s hand moves from state n to state (n + 1) if that hand is
touched last
• A player is out of the game if both hands are behind their back
• Find out which player will be the last player standing
One-Day Assignment 3 – Coconut Splat
• State 1 (folded), initial state:
• Counts as a set of hands (ie. only one syllable) in this form instead of two individual
hands
• State 1 (folded) -> State 2 (fist)
• Split folded hands into 2 fists; counting begins with the first fist on the next round (so
it goes to the player’s first fist, followed by the player’s second fist, followed by the
hand of the next player)
• State 2 (fist) -> State 3 (palm down)
• Change fist into palm down; counting begins with the next hand after this (which
could be the player’s other hand, or the next player’s hand)
• State 3 (palm down) -> State 4 (behind back)
• Hand is moved behind back; this hand will no longer be counted in subsequent
rounds. Counting begins with the next hand after this (which could be the player’s
other hand, or the next player’s hand)
One-Day Assignment 3 – Coconut Splat
• The following 2 slides contain an example of the game simulated for 3
players, with 3 syllables in the rhyme
• The last person standing in this example should be player 2
• In the example, each round starts from the underlined hand/fist/palm
Move Player 1 Player 2 Player 3
Initial State Folded Hands Folded Hands Folded Hands
Round 1 Folded Hands Folded Hands Folded Hands
After R1 Folded Hands Folded Hands Fist Fist
Round 2 Folded Hands Folded Hands Fist Fist
After R2 Fist Fist Folded Hands Fist Fist
Round 3 Fist Fist Folded Hands Fist Fist
After R3 Fist Fist Fist Fist Fist Fist
Round 4 Fist Fist Fist Fist Fist Fist
After R4 Fist Fist Fist Fist Palm Down Fist
Round 5 Fist Fist Fist Fist Palm Down Fist
After R5 Fist Palm Down Fist Fist Palm Down Fist
Round 6 Fist Palm Down Fist Fist Palm Down Fist
After R6 Fist Palm Down Fist Fist Behind Back Fist
Round 7 Fist Palm Down Fist Fist Behind Back Fist
After R7 Fist Behind Back Fist Fist Behind Back Fist
Hand is touched Hand is touched (last) Hand changes state Hand is out of play
Move Player 1 Player 2 Player 3
After R7 Fist Behind Back Fist Fist Behind Back Fist
Round 8 Fist Behind Back Fist Fist Behind Back Fist
After R8 Fist Behind Back Fist Fist Behind Back Palm Down
Round 9 Fist Behind Back Fist Fist Behind Back Palm Down
After R9 Fist Behind Back Fist Palm Down Behind Back Palm Down
Round 10 Fist Behind Back Fist Palm Down Behind Back Palm Down
After R10 Fist Behind Back Palm Down Palm Down Behind Back Palm Down
Round 11 Fist Behind Back Palm Down Palm Down Behind Back Palm Down
After R11 Palm Down Behind Back Palm Down Palm Down Behind Back Palm Down
Round 12 Palm Down Behind Back Palm Down Palm Down Behind Back Palm Down
After R12 Palm Down Behind Back Palm Down Palm Down Behind Back Behind Back
Round 13 Palm Down Behind Back Palm Down Palm Down Behind Back Behind Back
After R13 Palm Down Behind Back Palm Down Behind Back Behind Back Behind Back
Round 14 Palm Down Behind Back Palm Down Behind Back Behind Back Behind Back
After R14 Behind Back Behind Back Palm Down Behind Back Behind Back Behind Back
<- X_X
X_X ^_^
Hand is touched Hand is touched (last) Hand changes state Hand is out of play
