CPT204 Online
Erick Purwanto – May 2022
CPT204 Online 2022
Coursework 3 Task Sheet
Overview
Coursework 3 (CW3), the final assessment component this semester, consists of 3
parts: Part A, B and C. It contributes to 80% of your final marks.
In Part A (100 marks), you will implement a data structure called Union Find with Path
Compression. You will then use this data structure to solve a problem called Connect
Coins in Part B (100 marks). Finally, in Part C (300 marks), you will have to solve
three problems of various data structures, problem-solving and object-oriented
techniques that are derived from Lecture and Lab 1 – 13.
Submit all your answers for parts A, B, and C to Learning Mall for grading on the
Submission Day.
Timeline
Week 12, Wednesday, CW3 Part A, B released
May 11, 2022 (Task Sheet, Skeleton Codes, Partial Test Cases)
Week 14, Thursday, CW3: Submission Day
May 26, 2022
11.00 CST CW3 Part A, B online submission open
11.15 CST CW3 Part C released, online submission open
12:15 CST CW3 Part A, B, C online submission closed
Outline
The rest of the task sheet will describe all the three parts and the Submission Day in
detail.
Coursework 3 – Part A
Union Find with Path Compression
Recall that in Lecture 9 and Lab 9, we have constructed a Union Find data structure
called Weighted Quick Union, and achieved O(log N) time for union, find and
isSameGroup operations. It turns out that we can do even better, to get almost
constant time for both operations!
In part A, you are to improve your Lab 9: Weighted Quick Union data structure with
Path Compression.
Idea of Path Compression
Consider the connectivity tree below. It is one of the possible valid trees of 16 items
in a Weighted Quick Union data structure, resulting from some series of operations.
Now imagine you call isSameGroup(10, 11). That will involve finding the root of 10
and 11, and will be preceded by finding the parent of the elements in blue.
The key idea is this: since we have found the root of the elements in blue while
climbing the tree, whose root is 0, we want to change and set the parents of those
blue elements directly to the root.
CPT204 Online
Erick Purwanto – May 2022
The result is the following tree:
Notice that this changes nothing about which group each element belongs to. They
are still in the tree where 0 is the root.
The additional cost of this path compression operation to isSameGroup is still in the
same order of growth, but now the future operations that require finding the root
will be faster! We are going to use the same path compression idea on the other
operations as well.
Note that this path compression results in amortized running time on N operations of
union/isSameGroup/size of O(α(N)), where α is the inverse Ackermann function,
of which the value, for practical purposes, is always less than 5.
Part A: Weighted Quick Union with Path Compression
In part A, your task is to complete an implementation of the Union Find data structure
using Weighted Quick Union of Lab 9 with Path Compression.
You will have to implement the following methods to complete the data structure:
1. public UnionFind(int N) creates a Union Find data structure with N elements:
0 through N-1. Initially, each element is in its own group.
2. public void validate(int p) checks whether p is a valid element. It throws
an IllegalArgumentException if p is not a valid index.
3. public int sizeOf(int p) returns the size of the group the element p belongs
to.
CPT204 Online
Erick Purwanto – May 2022
CPT204 Online
Erick Purwanto – May 2022
4. public int find(int p) returns the group identity number which is the root
of the tree element p belongs to. Assume p is a valid element. The path
compression operation is applied in this method to reduce the finding root's
running time.
Note that now, the given method public boolean isSameGroup(int p, int
q) is then implemented by simply calling validate on p and q, and then
checking whether find(p) is the same as find(q).
5. public void union(int p, int q) connects two elements p and q together,
by combining the groups containing them, connecting the root of the smaller size
tree to the root of the larger size tree. If the sizes of the trees are equal, break the
tie by connecting p's root to q's root. It throws an IllegalArgumentException if p
or q is not a valid index.
The total marks of all the implementations in part A is 100 points, for passing all the
test cases.
Advice
The following advice may be found useful in implementing Part A:
1. Use the same Automated Regression Unit Testing and Integration Testing strategy
that you have been using in Lab 9. Note that with the use of the Path Compression
strategy, the output may be different from the result in Lab 9.
2. Add more test cases, and create a good suite of test cases and practice the
Partitioning/Boundary, Black-box/White-box, and Coverage testing.
3. Debug with the help of Java Visualizer plugin in IntelliJ IDEA.
4. You may define your own private helper methods. Include them in each of your
submissions.
5. Do not define your own instance variables. They are not going to be used in the
hidden test cases and may cause unpredictable errors in the grading system.
Coursework 3 – Part B
Connect Coins
In part B, you are going to use the data structure you have developed in part A to
solve an interesting computational problem efficiently in a simple game. The game
involves connecting gold coins in a 2-Dimensional space.
Connect Coins Problem
What's better than gold coins? More gold coins! In your game, a number of gold coins
are placed on a 2-D space. The players can place a new gold coin by specifying a series
of 2-D coordinates.
We say that two coins are connected if the coins are next to each other in one of the
4 directions: left, right, up or down.
Consider a particular step in that game, when a player wants to place a new coin. We
are interested in finding out where to place the new coin so that the resulting
connected coins are as many as possible.
2-D Space and Coins Representation
We represent the 2-D space as a 2-D boolean array of true (T) and false (F) values
called boolean[][] ccMatrix.
A T in a coordinate indicates that there is a coin at that position in the 2-D space, while
an F indicates an empty space.
The location of the new coin that would maximally connect the coins is specified by a
2-element integer array int[] representing the coordinates in [row, column]
format.
The number of newly connected coins will be returned as an int.
Part B: Connect Coins Task
In part B, your task is to complete a skeleton code of the ConnectCoins class in order
to figure out where to place a coin to maximally connect them, and how many coins
can be maximally connected.
CPT204 Online
Erick Purwanto – May 2022
You will have to implement the following methods to complete the class:
1. public ConnectCoins(boolean[][] ccMatrix). Each ConnectCoins instance
is bound to a single 2-D space, which is passed in through its constructor. You may
assume this space is valid, i.e., there is at least one empty coordinate to place a
new coin.
2. public int[] placeMaxConnCoins(). The method returns a 2-element integer
array that represents the coordinate in [row, column] so that a coin that is placed
in that coordinate will give the maximum number of newly connected coins. If
there are multiple possible such placements, return the left-and-topmost
coordinate.
3. public int maxConnCoins(). The method returns the maximum number of
newly connected coins after placing a new coin.
The total marks of all the implementations in part B is 100 points, for passing all the
test cases.
Test Case 1
Input ccMatrix = [[T, F, T, T], [T, F, T, F], [T, F, T, F], [F, T, F, T], [F, T, F, T],
[T, F, F, T]]
Output of placeMaxConnCoins = [2, 1]
Output of maxConnCoins = 10
[2, 1]
[3, 2]
Explanation:
Placing a coin at coordinate [2, 1] will connect 10 coins, which is the maximum number
of newly connected coins in this instance of the game.
Placing a coin at coordinate [3, 2] will also connect 10 coins, but the left and topmost
coordinate with the same score must be returned instead.
CPT204 Online
Erick Purwanto – May 2022
CPT204 Online
Erick Purwanto – May 2022
Additional Notes
Here are some additional notes:
1. The correct implementation of the Union Find data structure will be provided in
the automatic grader system for you readily to use.
2. You have to use the Union Find data structure in your implementation and
computation. Failing to do so will result in 0 marks.
3. The number of rows and columns in the 2-D space will be in the range [1, 1000].
In particular, it means that the smallest valid array is 1-by-1.
Advice
The following advice may be found useful in implementing Part B:
1. Use the Automated Regression Unit Testing with your correct Weighted Union
Find (without Path Compression) of Lab 9, that is guaranteed correct, if you have
not completely finished Part A.
2. Add more test cases, and create a good suite of test cases and practice the
Partitioning/Boundary, Black-box/White-box, and Coverage testing.
3. Debug with the help of Java Visualizer plugin in IntelliJ IDEA.
4. You may define your own private helper methods. Include them in each of your
submissions.
5. Do not define your own instance variables. They are not going to be used in the
hidden test cases and may cause unpredictable errors in the grading system.
CPT204 Online
Erick Purwanto – May 2022
Coursework 3 – Part C
In part C, you are going to solve 3 questions, closely related to the works you have
done throughout the semester in Lab 1 – Lab 13. The questions could be found in a
Learning Mall quiz. Note that you could still access the course materials similar to an
open-book exam setting.
Relative to the programming questions in the Lab Exercises, there will be 2 easy and
1 hard coding questions. There are multiple possible candidate questions for each
question with the same difficulty, you will be given one of them randomly.
While the specific questions are not going to be revealed here, the range of topics will
be given below. You can also practice by reviewing all your works in Lab 1 – Lab 13.
You will be able to access the questions in the respective Learning Mall Quizzes on the
Submission Day: Thursday, May 26, 11:15 CST.
The marks for each question in part C is 100 points, for a total of 300 points.
Data Structure
List, ArrayList, MyList, SLList, DLList, ARList
Deque, LLDeque, ARDeque
Map, HashMap, HAMap
Set, ARSet, HASet
MinPQ, ARBinHeap
Union Find, Quick Find, Quick Union, Weighted Quick Union
Generic Data Structure of the above and their subclasses
Object-oriented Features and Problem-solving Techniques
Empty Constructor, Default Constructor, Copy Constructor, Deep Copy
Iterative, Recursive, Recursion with Helper Method
Mutates, Not Mutate, Immutable
Resizing Array, Table Doubling/Halving
Checked/Unchecked Exception, Assertion
Iterator, Iterable, Enhanced For Loop, ToString
Interface, ADT, Interface Inheritance, Implementation Inheritance, Casting
Static/Dynamic Type, Dynamic Method Selection, Overloading, Overriding
Equality, Higher Order Functions, Comparator, Comparable, HashCode
Coursework 3 – Submission Day
The submission day is on Thursday, May 26, 2022.
Prepare your laptop, with all necessary software installed. Make sure you have a good
Internet connection. Have Learning Mall ready in your browser, preferably Chrome or
Firefox.
Connect into a Zhumu Room (meeting ID to be announced later) with your official
student account. The password to access the quizzes will be shared in that room.
Learning Mall Submission Day 14 Quiz Section
Part A, B quizzes will be accessible on Thursday, May 26, 2022, 11:00, followed by
Part C on 11.15. All quizzes will be closed on 12.15 CST.
You will see a similar section as shown below.
Additionally for Part C, you will also see a problem description and class/method
specification outlining each problem, similar to our lab sheets.
Some may include a skeleton code (in a java or zip files) as well. You may want to copy
and paste the skeleton code into your coding environment, so please have it ready.
CPT204 Online
Erick Purwanto – May 2022
Learning Mall Quiz Submission
When Part A, B quizzes open at 11:00 CST (Part C, 11:15), you will see some additional
test cases. You may want to check your code against those test cases in your IDE first,
not in the Learning Mall Quiz.
You have 60-75 minutes to test, debug — if needed, and submit your code. Submit
your code before the closing time at 12:15 CST. It is highly recommended to submit
a few minutes earlier to account for network transmission delay.
For each question, you have to complete the method or the class, as specified in the
problem description and specification. You may use Check against the test cases
multiple times.
In addition, you may include your private helper methods in the submission box.
Adding another elements, such as importing libraries, will result in 0 marks.
The first Check will have no penalty if failing the test cases. The subsequent Checks,
however, will each incur an additional 15% penalty (changed to 10% penalty due to
student requests in feedback questionnaire), cumulatively for each incorrect Check.
CPT204 Online
Erick Purwanto – May 2022
Useful Tips for Submitting Your Work
1. If you copy and paste code from your IDE, please double check the parenthesis,
class/method headers, etc., before clicking the Check or Finish Attempt button.
2. For Part C Quiz, do not go to the next page before completing your submission.
You cannot go back after clicking Next.
3. Test your code intensively before submitting your work.
4. Familiarize yourself with the error messages of the autograder systems that we
have seen throughout the semester.
Academic Integrity
This Coursework 3 assignment is individual work. Plagiarism (e.g. copying materials
from other sources without proper acknowledgement) is a serious academic offence.
Plagiarism and collusion will not be tolerated and will be dealt with in accordance with
the University Code of Practice on Academic Integrity. Individual students may be
invited to explain parts of their code in person, and if they fail to demonstrate an
understanding of the code, no credit will be given for that part of the code.
CPT204 Online
Erick Purwanto – May 2022