CSE210 Online Erick Purwanto – June 2020
CSE210 Online 2020
Coursework 3 Task Sheet
Overview
This coursework consists of 3 parts: A, B and C.
In part A, you will implement a data structure called Weighted Quick Union with Path
Compression. You will then use this data structure to solve a problem called Bursting
Bubbles in part B. Finally, in part C, you will have to solve five problems of various
data structures, problem-solving and object-oriented techniques that are derived
from Coursework 1 and Coursework 2.
Submit all your answers for parts A, B, and C to ICE Quiz CodeRunner for grading on
the Submission Day.
Timeline
Week 1 – Week 15 Coursework 1 (Online Programming Exercises) and
Coursework 2 (Online Programming Assignments)
Week 16 Coursework 3 Part A, B released
8 June 2020 (Task Sheet, Skeleton Codes, Partial Test Cases, Additional
Exercises)
19 June 2020 Submission Day
17.30 – Coursework 3 Part C released, submission open
19.30 Coursework 3 Part A, B, C submission closed
Outline
The rest of the task sheet will describe all the three parts and the Submission Day in
detail.
CSE210 Online Erick Purwanto – June 2020
Coursework 3 – Part A
Weighted Quick Union with Path Compression
Recall that in Lecture and Lab 12, we have constructed a Disjoint Sets data structure
called Weighted Quick Union using implementation strategy 4.2, and achieved O(log
N) time for connect and isConnected 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 12 Weighted Quick Union data structure with
Path Compression.
Idea of Path Compression
Consider the tree below. It is one possible tree in a Weighted Quick Union data
structure. Now imagine you call isConnected(10, 15). That will involve finding the
root of 10 and 15, 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 set the parents of those elements
directly to the root.
CSE210 Online Erick Purwanto – June 2020
The result is the following tree:
Notice that this changes nothing about which set each element belongs to. They are
still in the tree where 0 is the root.
The additional cost of this path compression operation to isConnected 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.
It can be shown that this path compression results in amortized running time on N
operations of connect/isConnected/sizeOf of O(α(N)), where α is the inverse
Ackermann function that for practical purposes is always less than 5.
Part A: Weighted Quick Union with Path Compression Task
In part A, your task is to complete an implementation of Disjoint Sets data structure
using Weighted Quick Union 4.2 with Path Compression.
You will have to implement the following methods to complete the data structure:
1. public DisjointSets(int N) creates a Disjoint Sets data structure with N
elements: 0 through N-1. Initially, each element is in its own set.
2. public void validate(int p) validates that p is a valid index/element. It
throws an IllegalArgumentException if p is not a valid index.
3. public int sizeOf(int p) returns the size of the set the element p belongs
to.
CSE210 Online Erick Purwanto – June 2020
4. public boolean isConnected(int p, int q) returns true if elements p and
q are connected, and false otherwise. It throws an IllegalArgumentException if p
or q is not a valid index.
5. public void connect(int p, int q) connects two elements p and q together,
by combining the sets 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 for all the methods in part A is 100 points.
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 12. Note that with the use of the Path
Compression strategy, the output may be different from the result in Lab 12.
2. Create a good suite of test cases and practice the Partitioning/Boundary,
Blackbox/Whitebox and Coverage testing.
3. Debug with the help of Java Visualizer.
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.
CSE210 Online Erick Purwanto – June 2020
Coursework 3 – Part B
BurstBubble Game Development
In part B, you are going to use the data structure you have developed in part A to
solve an interesting problem that arises when your game development team wants to
create a puzzle game. The game involves bursting bubbles in a 2-Dimensional space.
BurstBubble Problem
Bubbles are sticky objects. In your game, some bubbles are sticking to the top of the
2-D space, while others stick to each other. The player bursts the bubbles by specifying
a series of 2-D coordinates. If it matches and bursts a bubble, it may also cause some
other bubbles to fall. Your specific task in the game development team is to figure out
how many bubbles will fall as the player bursts them.
2-D Space, Bubbles, and Bursting Representation
We represent the 2-D space as a 2-D array of true (T) and false (F) values called
boolean[][] bbMatrix.
A T in a coordinate indicates that there is a bubble at that position in the 2-D space,
while an F indicates an empty space.
A bubble will not fall if and only if 1) it is in the topmost row directly stuck to the top
of the space, or 2) it is orthogonally adjacent to another bubble that is not falling.
A player will do the bursting sequentially: the bubble in the first coordinate is burst, if
any, causing some other bubbles to fall, and then next coordinate, and so on. The
coordinates are specified in an array of 2-element arrays int[][] bursts.
If a player bursts a bubble, the targeted bubble will not fall and disappear. If a player
bursts an empty space, nothing happens.
The number of bubbles that will fall after each bursting in sequence is returned as an
array int[] scores.
Part B: Bubble Burst Task
In part B, your task is to complete a skeleton code of the BurstBubble class in order
to figure out how many bubbles will fall as the player bursts them.
CSE210 Online Erick Purwanto – June 2020
You will have to implement in the following methods to complete the class:
1. public BurstBubble(boolean[][] bbMatrix). Each BurstBubble instance is
bound to a single 2-D space, which is passed in through its constructor. You may
assume this space is valid, for example, no floating unstuck bubbles.
2. public int[] burstBubble(int[][] bursts). The input parameter bursts is
an array of 2-element arrays representing the coordinates (in [row, column]
format) which the player chose in sequence, e.g. the first burst is at position
bursts[0]. You may assume all elements of bursts are unique, valid coordinates
within the space. It returns an array where the i-th element is the number of
bubbles that fall after the i-th bubble at coordinate bursts[i] is burst, if any.
The total marks for all the methods in part B is 100 points.
Test Case 1
Input:
bbMatrix = [[T, T, F, T], [T, F, F, F], [T, T, F, F], [T, T, T, F]]
bursts = [[2, 2], [2, 0]]
Output:
scores = [0, 4]
Explanation:
bursts[0] at coordinate [2, 2] misses any bubbles and causes no falling bubbles.
bursts[1] at coordinate [2, 0] bursts one bubble and causes 4 other bubbles to fall.
bursts[0]
bursts[1]
CSE210 Online Erick Purwanto – June 2020
Additional Notes
Here are some additional notes:
1. You have to use Disjoint Sets data structure in your implementation and
computation. Failing to do so will result in 0 marks.
2. The number of rows and columns in the 2-D space will be in the range [1, 200].
3. The number of bursts will not exceed the area of the space.
CSE210 Online Erick Purwanto – June 2020
Coursework 3 – Part C
In part C, you are going to solve 5 questions, closely related to the works you have
done throughout the online semester in Coursework 1 and Coursework 2.
Relative to the programming questions in both Coursework 1 and Coursework 2, there
will be 2 very-easy, 1 easy, 1 medium and 1 hard coding questions. There will be
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 Coursework 1
and Coursework 2. You will be able to access the questions in the respective ICE
CodeRunner Quizzes on the Submission Day.
The marks for each question in part C is 100 points, for a total of 500 points.
Data Structure
List, ArrayList, MyList, SLList, DLList, ARList
Deque, LLDeque, ARDeque
Map, HashMap, HAMap
Set, ARSet, HASet
Disjoint Sets, 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, 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
CSE210 Online Erick Purwanto – June 2020
Coursework 3 – Submission Day
The submission day is on 19 June 2020, at 17.30 – 19.30.
At that time, open your course page CSE210 on ICE.
ICE Quiz Autograders
The quiz will be accessible on 19 June 2020 at 17:30.
You will see a similar section 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 as well. You may want to copy paste the skeleton
code into your coding environment, so please have it ready.
CSE210 Online Erick Purwanto – June 2020
Online Submission
You have to complete the method or the class, as specified in the problem description
and the specifications.
In addition, you may include the helper methods.
Adding another elements, for example import 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 25% penalty, cumulatively for each incorrect
check.
Useful Tips for Submitting Your Work
1. If you are copy paste from your IDE, do double check the parenthesis,
class/method headers, etc, before clicking the Check button.
2. Test your code intensively before submitting your work.
3. Familiarize yourself with the error messages of the autograder systems that we
have seen throughout the semester.