CPT204 Online 2022 Coursework 3 Task Sheet
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 Submission Day.
Copyright By PowCoder代写 加微信 powcoder
Week 12, Wednesday, May 11, 2022
Week 14, Thursday, May 26, 2022
11.15 CST 12:15 CST
parts A, B, and C to Learning Mall for grading on the
CW3 Part A, B released
(Task Sheet, Skeleton Codes, Partial Test Cases)
CW3: Submission Day
CW3 Part A, B online submission open
CW3 Part C released, online submission open CW3 Part A, B, C online submission closed
The rest of the task sheet will describe all the three parts and the Submission Day in detail.
CPT204 Online
Erick Purwanto – May 2022
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. publicUnionFind(intN)createsaUnionFinddatastructurewithNelements:
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
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.
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.
CPT204 Online
Erick Purwanto – May 2022
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 upper-leftmost 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
InputccMatrix= [[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
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 upper-leftmost coordinate with the same score must be returned instead.
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.
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
CPT204 Online
Erick Purwanto – May 2022
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
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com