- June 13, 2020
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. 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 at coordinate [2, 2] misses any bubbles and causes no falling bubbles. bursts at coordinate [2, 0] bursts one bubble and causes 4 other bubbles to fall. bursts bursts 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.