Overview

Resit Coursework (RCW), the only resit assessment component this semester, consists of 3 parts:  Part A,  B  and  C.   It contributes to 100% of your final marks.

In Part A (100 marks), you will implement a data structure called Union Find with Path Compression 2. You will then use this data structure to solve a problem called Connect Coins 2 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

Resit Reading Week

Friday, July 29, 2022 18:00 CST

18:15 CST

19:15 CST

RCW Part A, B released

(Task Sheet,  Skeleton Codes, Partial Test Cases)

RCW:  Submission Day

RCW Part A, B  online submission open – closed

RCW Part C released

RCW Part C online submission open – closed

Outline

The rest of the task sheet will describe all the three parts and the Submission Day in detail.

Resit Coursework – Part A

Union Find with Path Compression 2

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.

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 2

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. The path compression operation is applied in this method to reduce the finding root's running time.

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 q's root to p's root. It throws an IllegalArgumentException if p or q  is not a valid index. The path compression operation is applied in this method to reduce the finding root's running time.

The total marks of all the implementations in part A is 100 points,  for passing all the test cases.

Advice and Additional Notes

Please follow these advice and additional notes 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.

Resit Coursework – Part B

Connect Coins 2

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 these

directions:                      left, right,               or         upper-left diagonal.

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.

You will have to implement in 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.

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   upper-leftmost coordinate. If there is no place for a new coin, return [-1, -1].

3.   public int maxConnCoins().  The method returns the maximum number of newly connected coins after placing a new coin. If there is no place for a new coin, return -1.

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, T, F, T, F],  [T, F, F, T, F],  [F, F, T, F, F],  [F, T, T, F, T],  [F, F, F, T, F]] Output of placeMaxConnCoins = [1, 1]

Output of maxConnCoins = 5

[1, 1]

[2, 1] [3, 3]

Explanation:

Placing a coin at coordinate [1, 1] will connect 5 coins, which is the maximum number of newly connected coins in this instance of the game.

Placing a coin at coordinate [2, 1] or [3, 3] will also connect 5 coins, but the upper- leftmost coordinate with the same score must be returned instead.

Additional Notes

Here are some additional notes:

1.   The correct implementation of the Union Find data structure in Part A will be

provided in the automatic grader system for you readily to use.       More specifically, you can call all 5 methods in Part A Page 2-3, and isSameGroup.

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.

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, Friday, July 29, 2022, 18: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

The submission day is on  Friday, July 29, 2022, 18:00-19:15 CST.

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 Quiz Section

Part A, B quizzes will be accessible on Friday, July 29, 2022, 18:00 CST, followed by Part C on 18:15 CST. All quizzes will be closed on 19: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.

Learning Mall Quiz Submission

When the quizzes open starting at 18:00/18:15 CST, 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  19: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 10% penalty, cumulatively for each incorrect Check.