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.