Validation of forms is everywhere when you create a JavaScript application and a web application in general. You want to ensure that you’re getting correct and valid information from your users so that you can (for us in the future) save this information. Exercise Step 1 – Adding a new Item to our Order 1. Link your JavaScript file in the HTML, do not change any HTML otherwise. 2. Select the form with the class “new-order-form” 3. Add an event listener on the form that will handle the “submit” event. 4. Using the event object, prevent the default action from happening 5. Assign the form elements from using the “elements” property on the “event.target” to variables with appropriate names. 6. Pass the form input values to the “addOrderItem” function given. a. If you’re ever confused about a specific variable, you can always use the console to print out the variables. The output should look something like this once you click the “Add to Order” button: Exercise Step 2 – Validating Elements of the Form 1. There’s a bug in our application. We get a blank row to our order if we submit our form with nothing in it. We only want populated rows because that is what we expect in our application. 2. Create a variable named “isFormValid” that will be assigned a Boolean. Using this variable you, either execute or do not execute the “addOrderItem” with the values from the form. 3. In the following steps, use the “isFormValid” with the validation functions “isValueNotEmpty” and “isGreaterThanFive”. 4. Validate the order item name. a. If the order item name is not an empty string, then the item name is valid. i. Remove the “is-invalid” class on the order item name using the elements’ “classList.remove” function. b. If the order item name is an empty string, then the item name is invalid. i. Add the “is-invalid” class on the order item name using the elements’ “classList.add” function. ii. Set the “isFormValid” to false. 5. Validate the order item price. a. If the order item price is not an empty string, and if it’s greater than five then the item price is valid. i. Remove the “is-invalid” class on the order item price using the elements’ “classList.remove” function. b. If the order item price is an empty string, or if the price is less than five or if then the item price is invalid. i. Add the “is-invalid” class on the order item name using the elements’ “classList.add” function. ii. Set the “isFormValid” to false. 6. Validate the order size. a. If the order size is not an empty string, then it’s in valid. i. Remove the “is-invalid” class on the order item size using the elements’ “classList.remove” function. b. If the order size is an empty string, then it’s invalid. i. Add the “is-invalid” class on the order item size using the elements’ “classList.add” function. ii. Set the “isFormValid” to false 7. Execute the “addOrderItem” function only if “isFormValid” is true. There are a couple of ways to do this, and either works. 8. You reset the values of each input on a successful form submission. 9. The functionality should look like the following result. a. Successful result b. Invalid result with all of the inputs invalid. Test Cases You might need clarification and need to know what values to test here to help you out. • Test case: form invalid o Item Name: Burger o Price: o Size: • test case: form invalid o Item Name: o Price: 18 o Size: • test case: form invalid o Item Name: pop o Price: 4 o Size: small • test case: form invalid o Item Name: o Price: o Size: Small • Test case: valid form o Item Name: pop o Price: 6 o Size: small Exercise Step 4 – Push up your code to github (accepting this assignment) 1. Open the link given and accept the assignment. Your link should look something like this. Note the image will be different because you’ll accept the assignment specified. You’ll see a page like this. One you’re repo is ready the page should look like the following. 2. You should see the page below once you click on the link highlighted in blue. Click the button that says “Code.” You’ll need to select “HTTPS” unless you’ve set up “SSH” (you can also set up GitHub CLI”. Click on the copy icon once you’ve selected the proper icon. 3. Clone the repository in your console (or if you’re using GitHub Desktop) using the “git clone REPO_URL” command. And go into this folder. 4. Make your changes, then add them to staging (using “git add .”) and commit them (using “git commit -m “CHANGE THIS MESSAGE”). Once committed, push them up to GitHup (using “git push”) it should look like below. 5. If you click “Pull Requests” and then the first item called “Feedback” you should see your commit (seen at the bottom). 6. Upload the link of your repository to Moodle. Grading I’ll give full marks if: • All of the test cases pass. • The form validates each input element separately. • An invalid form submission should look like this: • A valid form submission should look this: If you don’t follow the instructions specified you’ll get a zero. There are no marks in between.
Introduction Functions are the building blocks of almost everything we will do in the course. At their core functions are collections of statements that allow us to break down more significant problems into smaller ones and will enable us to reuse code. In this exercise, we will use a combination of functions that we create and JavaScript built-in functions to create our “Multiplying Calculator,” which will take two values, multiply them and update the dom with our result. Exercise Step 1 – Create the “getElementValue” function. 1. Link your JavaScript file in your HTML, and print a console.log that prints out “javascript calculator linked.” 2. Create a function named “getElementValue” that will take one parameter named “selector.” 3. The function should return the innerText of the element selected (using the “selector” parameter) a. If you test your element it should look like the output of the following picture. (Note the console.) 4. Once you have completed this, you can move on to the next step. Exercise Step 2 – Create a “multiply” function 1. Create a function named “multiply” that will take two parameters: “firstValue” and “secondValue”. a. Note when you call this function, you’ll need to pass in numbers, not strings. 2. The function will return both numbers multiplied together. If you’re confused about how to do this and want some reference https://developer.mozilla.org/enUS/docs/Web/JavaScript/Reference/Operators/Multiplication. a. Testing your function should look like this. (Note the console) 3. Once you have completed this, you can move on to the next step. Exercise Step 3 – Updating the Result in the Dom 1. Create a function named “updateResult” that doesn’t take any parameters. 2. The first two things we want to do is get both number values that you see in the dom. a. Use the function “getElementValue” to get the values 3. Since these values from the dom are string values, we will use the built-in function “parseInt” to convert the string into a number. For reference (https://developer.mozilla.org/enUS/docs/Web/JavaScript/Reference/Global_Objects/parseInt) 4. After we convert both input values to numbers, call the “multiply” with the values from step 3 as the arguments to the function (you should pass two arguments). a. Store the result of the function in a variable named “result.” 5. Select the element with the id of “result” and update the innerText to the new value. 6. Call the “updateResult” function so that the result is updated every time you reload the page. The result of your application should look like this: Exercise Step 4 – Push up your code to github (accepting this assignment) 1. Open the link given and accept the assignment. Your link should look something like this. Note the image will be different because you’ll accept the assignment specified. You’ll see a page like this. One you’re repo is ready the page should look like the following. 2. You should see the page below once you click on the link highlighted in blue. Click the button that says “Code.” You’ll need to select “HTTPS” unless you’ve set up “SSH” (you can also set up GitHub CLI”. Click on the copy icon once you’ve selected the proper icon. 3. Clone the repository in your console (or if you’re using GitHub Desktop) using the “git clone REPO_URL” command. And go into this folder. 4. Make your changes, then add them to staging (using “git add .”) and commit them (using “git commit -m “CHANGE THIS MESSAGE”). Once committed, push them up to GitHup (using “git push”) it should look like below. 5. If you click “Pull Requests” and then the first item called “Feedback” you should see your commit (seen at the bottom). 6. The link of your repository to Moodle. Grading I’ll give full marks if: • The name of your Netlify app is renamed to your name. • All functions have the correct names and parameters. • What I see should be exactly what I see in the picture below (your numbers will be different). If you don’t follow the instructions, you’ll get a zero. There are no marks in between.
Introduction The console is a great tool to see what’s going on on the page and will also be how we debug our JavaScript throughout the course. It allows us to execute statements on the page (like we’ve seen in class) in real time! In this first lab assessment, you will try fixing typos on our page in the console first; second, you will put all of these changes in your main.js; and third, you will push it up to GitHub. How to access the console. There are a few ways to access the console: • Right-click on an element in the page and select inspect element from the context menu • Press ctrl+shift+j (Windows) or cmd+option+j (Mac) • Press F12 • From the customize menu, select More tools and then Developer tools When you open the accompanying folder with the files, you should see something like this Exercise Step 1 – fix typos in the console 1. Open the chrome web browser 2. Select the h1 with the id of “app-title” and the paragraph with the class “app-description”s using the querySelector and assign it to a variable using an appropriate name. ”. If you need help with this, please refer to your notes. 3. Modify the “innerText” or the “innerHTML” of the variables selected. To fix the typos so that it looks like the picture below. Exercise Step 2 – use a JavaScript file in your html. 1. In your “main.js” file in the accompanying files, add a “console.log” statement that says “js file successfully linked.” 2. Link your JavaScript file to your HTML using the script tag we learned in class (refer to notes if you can’t). 3. Use the work from the exercise step above (selecting the about element and fixing the typos) and add it to the JavaScript file so that when you refresh the page, the html should look like the picture below (just like the last exercise). Exercise Step 3 – Push up your code to github (accepting this assignment) 1. Open the link given and accept the assignment. Your link should look something like this. Note the image will be different because you’ll accept the assignment specified. You’ll see a page like this. One you’re repo is ready the page should look like the following. 2. You should see the page below once you click on the link highlighted in blue. Click the button that says “Code.” You’ll need to select “HTTPS” unless you’ve set up “SSH” (you can also set up GitHub CLI”. Click on the copy icon once you’ve selected the proper icon. 3. Clone the repository in your console (or if you’re using GitHub Desktop) using the “git clone REPO_URL” command. And go into this folder. 4. Make your changes, then add them to staging (using “git add .”) and commit them (using “git commit -m “CHANGE THIS MESSAGE”). Once committed, push them up to GitHup (using “git push”) it should look like below. 5. If you click “Pull Requests” and then the first item called “Feedback” you should see your commit (seen at the bottom). 6. The link of your repository to Moodle. Grading I’ll give full marks if: • When I load the page there are no errors in the console. • When page is loaded this should be exactly what I see in the picture below. Note: If you don’t follow the instructions, you’ll get a zero. There are no marks in between.
The objective of this exercise is to reconstruct/unzip a message archived with a binary-treebased algorithm. The program should receive a file name as a single command-line argument. It should then decode the message in the file and print it out to the console. The name of the compressed message file will end in .arch, e.g. “monalisa.arch”. The file consists of two or three lines: the first one or two lines contain the encoding scheme, and the second or third line contains the archived message. 2. Encoding The archival algorithm uses a binary tree. The edges of the tree represent bits, and the leaf nodes contain one character each. Internal nodes are empty. An edge to a left child always represents a 0, and an edge to a right child always represents a 1. Characters are encoded by the sequence of bits along a path from the root to a particular leaf. The below tree serves as an example. The tree on the left encodes these characters: Character Encoding a 0 ! 100 d 1010 c 1011 r 110 b 111 With the above encoding, the bit string: 10110101011101101010100 is parsed as 1011|0|1010|111|0|110|1010|100 which is decoded as: cadbard! With this encoding, we can automatically infer where one character ends and another begins. That is because no character code can be the start of another character code. For example, if you have a character with the code 111, you cannot have the codes 1 and 11, as they would be internal nodes. The following steps decode one character from the bit string: Start at root Repeat until at leaf Scan one bit Go to left child if 0; else go to right child Print leaf payload 3. Input Format The archive file consists of two lines: the first line contains the encoding scheme, and the second line contains the compressed string. For ease of development and to make the archive file human-readable, each bit is represented as the character ‘0’ or ‘1’, rather than as an actual bit from a binary file. The encoding scheme can be represented as a string. For example, the tree from section 2 can be represented as: ^a^^!^dc^rb where ^ indicates an internal node. The above code represents a preorder traversal of the tree. The cadbard! message is encoded in the following file (“cadbard.arch”): ^a^^!^dc^rb 10110101011101101010100 There are four test files in HW4S2021_Test_Files.zip. Note: the encoding scheme representations may include a space character and a newline character, thereby breaking the tree string into two lines! The newline character needs to be parsed correctly if the encoding file has three lines in total. 4. Task 4.1. Read in the first line (and possibly second line, if newline is part of the tree) of the file and construct the character tree. Convert the line input into a MsgTree structure using preorder traversal. The tree should be in a class MsgTree with the following members: public class MsgTree{ public char payloadChar; public MsgTree left; public MsgTree right; /*Can use a static char idx to the tree string for recursive solution, but it is not strictly necessary*/ private static int staticCharIdx = 0; //Constructor building the tree from a string public MsgTree(String encodingString){} //Constructor for a single node with null children public MsgTree(char payloadChar){} //method to print characters and their binary codes public static void printCodes(MsgTree root, String code){} } When building the tree, try a recursive solution where staticCharIdx tracks the location within the tree string. You can pass the same tree string during recursive calls, and update the staticCharIdx to point to the next character to be read. Note: if you decide to implement an iterative solution, you will receive a 15% bonus, as it is considerably more difficult. In that case, you cannot get the 5% bonus for printing statistics. printCodes() performs recursive preorder traversal of the MsgTree and prints all the characters and their bit codes: character code ————————- c 1011 r 110 b 111 You are allowed to print the header of the table (character, code, —-) in main(). 4.2. Write a method public void decode(MsgTree codes, String msg) to decode the message. It would print the decoded message to the console: MESSAGE: The quick brown fox jumped over the lazy dog. You are allowed to print “MESSAGE:” in main(). The overall output of the program should be the output of printCodes() followed by the output of decode(): character code ————————- c 1011 r 110 b 111 8.0 1180 MESSAGE: The quick brown fox jumped over the lazy dog. 5. Submission Put your classes in the edu.iastate.cs2280.hw4 package. Turn in the zip file and not your class files. Include the Javadoc tag @author in each class source file. Your zip file should be named Firstname_Lastname_HW4.zip. No template files will be provided other than the skeleton in Section 4.1. 6. Extra credit (5% or 15%) Print message-specific (not just encoding) statistics after the rest of the program output. STATISTICS: Avg bits/char: Total characters: Space savings: 50.0% The above numbers are not the result of a calculation. The correct space savings calculation assumes that an uncompressed character is encoded with 16 bits. It is defined as (1 – compressedBits/uncompressedBits)*100. compressedBits is the sum of all characters in the message multiplied by each character’s individual bits. To earn a 15% non-cumulative bonus (either 5% for statistics or 15%), you can create an non-recursive, iterative solution for building the tree, but be advised that it will require hours of extra effort compared to the recursive solution. The bonus for early submission will stack with the 5/15% bonus. Name your submission Firstname_Lastname_HW4_extra.zip if you completed the iterative solution.
In this assignment you will implement a somewhat peculiar-looking linked list. The list will be a doublylinked list with dummy nodes for the head and tail. An empty list has the following form: Figure 1- an empty list So far so good. Now, let M be a fixed, positive even number. The twist is that each node can store up to M data elements, so the number of linked nodes may not correspond to the number of elements. For example, after some sequence of add and remove operations, one of these lists might have the following form: Figure 2 – a possible list of size 6, where M=4 Note that there are 6 elements, and their logical indices are shown below the nodes. The number of actual linked nodes may vary depending on the exact sequence of operations. Each node contains an array of the element type having fixed length M. Therefore, each logical index within the list is represented by two values: the node n containing the element, and the offset within that node’s array. For example, the element E shown above at logical index 4 is in node at offset 2. There are special rules for adding and removing elements to ensure that all nodes, except possibly the last one, have at least elements. These rules are described in detail in a later section. Note that you can get started and make significant progress on the assignment without needing all the add and remove rules. See the section suggestions for getting started. 2. Implementation of StoutList For the implementation, you must implement the class StoutList extending AbstractSequentialList. AbstractSequentialList is a partial implementation of the List interface in which the size() and listIterator() methods are abstract. All other operations have default implementations using the list iterator. The StoutList should NOT allow null elements. Your add methods (those within the iterator as well as those implemented without the iterator) should explicitly throw a NullPointerException if a client attempts to add a null element. A skeleton of the code can be found in project3_template.zip. The skeleton code includes a constructor, an inner class Node, and two methods toStringInternal(). There is also some code in place to support logging. 2.1. Methods to override In addition to implementing the iterators described below, you must override the following methods of AbstractList without using the iterator: int size() boolean add(E item) void add(int pos, E item) E remove(int pos) Iterator iterator() ListIterator listIterator() ListIterator listIterator(int pos) The methods above must conform to the List interface, with the added restriction that the add() methods must throw a NullPointerException if the item argument is null. The purpose of asking you to override add() and remove() is primarily to help ensure that you can get partial credit for implementing the split and merge strategies even if your iterator isn’t completely correct. n1 M/2 2.2. The Node inner class A minimal Node class is provided for you. It has methods for adding an element at a given offset and removing an element at a given offset. Note that empty cells within the array (i.e., those with index >= count) should always be null. You can add additional features to this class if you find it helpful to do so. 2.3. The toStringInternal methods These methods show the internal structure of the nodes and are useful for debugging. Normally, such a method would not be public (since it reveals implementation details), but we are making it public to simplify unit testing. For example, if the list of Figure 3 contained String objects “A”, “B”, “C”, “D” and “E”, an invocation of toStringInternal() would return the string: [(A, B, -, -), (C, D, E, -)] where the elements are displayed by invoking their own toString() methods and empty cells in the array inside each node (which should always be null) are displayed as “-”. A second version takes a ListIterator argument and will show the cursor position as a character “|” according to the nextIndex() method of the iterator. For example, if iter is a ListIterator for the list above and has nextIndex() = 3, the invocation toStringInternal(iter) would return the string: [(A, B, -, -), (C, | D, E, -)] Do not modify these methods. 2.4. Finding indices Your index-based methods remove(int pos), add(int pos, E item) and listIterator(int pos) method must not traverse every element in order to find the node and offset for a given index; you should be able to skip over nodes just by looking at the number of elements in the node. For example, for the list of Figure 9, to find the node and offset for logical index 7, you can see 3 elements in the first node, plus 2 in the second node, which makes 5, plus 4 in the third node, which is 9. Since 7 is greater than 5 and less than or equal to 9, index 7 must be in the third node. You may find it helpful to represent a node and offset using a simple inner class similar to the following: private class NodeInfo { public Node node; public int offset; public NodeInfo(Node node, int offset) { this.node = node; this.offset = offset; } } Then you can create a helper method something like the following: // returns the node and offset for the given logical index NodeInfo find(int pos){…} 3. Implementation of StoutIterator and StoutListIterator You must provide a complete implementation of an inner class StoutIterator implementing Iterator and a class StoutListIterator implementing ListIterator. The StoutIterator does NOT need to implement remove() (can throw UnsupportedOperationException). Optionally, if you are confident that your StoutListIterator is correct, you can return an instance of StoutListIterator from your iterator() method and forget about StoutIterator. However, you are encouraged to keep them separate when you first start development, since the basic one-directional Iterator, without a remove operation, is relatively simple, while the add and remove operations for the full ListIterator are tricky. 4. Suggestions for Getting Started 1. Implement add(E item). Adding an element at the end of the list is relatively straightforward and does not require any split operations. (e.g. see Figures 3 – 5). You can use toStringInternal() to check. 2. Implement the hasNext() and next() methods of StoutIterator and implement the iterator() method. At this point the List methods contains(Object) and toString() should work. 3. Start StoutListIterator. Implement ListIterator methods nextIndex(), previousIndex(), hasPrevious(), and previous(). These methods are straightforward. Implement the listIterator() method. You should then be able to iterate forward and backward, and you can check your iterator position using toStringInternal(iter). The indexOf(Object obj) method of List should work now. 4. Implement the set() method of StoutListIterator. You will need to keep track of whether to act on the element before or after the cursor (and possibly throw an IllegalStateException), but the method is not complicated since it doesn’t have to change the structure of the list or reposition the cursor. 5. Implement a helper method such as the “find” method described above under finding indices. Then you can easily implement the listIterator(int pos) method. After that, the get(int pos) of List should work. 6. Implement the add(int pos, E item) method. Now you will need to carefully review the rules for adding elements. Here is a suggestion for keeping things organized. Write a helper method whose arguments include the node and offset containing the index pos at which you want to add, e.g., private NodeInfo add(Node n, int offset, E item){…} (If pos = size, the arguments should be the tail node and offset 0.) The return value should be the actual node and offset at which the new element was placed. (In some cases this will be the given node and offset, in some cases it will be the previous node, and in case of a split there might be a completely new node.) You don’t need the return value for the add method, but you will need it in the iterator. 7. Implement the remove(int pos) method. Again, you will need to carefully review the rules for removing elements and merging. 8. Implement the add() method of listIterator. This is not too bad if you have the helper method from (6). The catch is that after adding an element, you have to update the logical cursor position to the element after the one that was added. 9. Implement the remove() method of listIterator. The tricky part is that you have to update the cursor position differently depending on whether you are removing ahead of the cursor or behind the cursor, and depending on whether there was a merge operation. 5. The add and remove Rules 5.1. Adding an element (see Figures 3 – 8) The rules for adding an element X at index are as follows. Remember that adding an element without specifying an index is the same as adding at index i = size. For the sake of discussion, assume that the logical index = size corresponds to node = tail and offset = 0. Suppose that index occurs in node n and offset off. (Assume that index = size means n = tail and off = 0) if the list is empty, create a new node and put X at offset 0 otherwise if off = 0 and one of the following two cases occurs, if n has a predecessor which has fewer than M elements (and is not the head), put X in n’s predecessor if n is the tail node and n’s predecessor has M elements, create a new node and put X at offset 0 otherwise if there is space in node n, put X in node n at offset off, shifting array elements as necessary otherwise, perform a split operation: move the last M/2 elements of node n into a new successor node n’, and then if , put X in node n at offset off if , put X in node n’ at offset 5.2. Removing an element (see Figures 9 – 14) The rules for removing an element are: if the node n containing X is the last node and has only one element, delete it; otherwise, if n is the last node (thus with two or more elements) , or if n has more than elements, remove X from n, shifting elements as necessary; otherwise (the node n must have at most elements), look at its successor n’ (note that we don’t look at the predecessor of n) and perform a merge operation as follows: if the successor node n’ has more than elements, move the first element from n’ to n. (mini-merge) if the successor node n’ has or fewer elements, then move all elements from n’ to n and delete n’ (full merge) 5.3 Examples: adding some elements to a list off ≤ M/2 off > M/2 (off − M/2) M/2 M/2 M/2 M/2 Figure 3- an example list Figure 4 – after add(V) Figure 5 – after add(W) Figure 6 – after add(2, X) Figure 7 – after add(2, Y) Figure 8 – after add(2, Z) 5.4. Examples: removing some elements from a list Figure 9 – example list Figure 10 – after removing W Figure 11 – after removing Y (mini-merge) Figure 12 – after removing X (mini-merge) Figure 13 – after removing E (no merge with predecessor node) Figure 14 – after removing C (full merge with successor node) 6. Sorting Implement the following two sorting methods within the StoutList class: public void sort(); public void sortReverse(); The sort() method implements insertion sort by calling a private generic method: private void insertionSort(E[] arr, Comparator
The purpose of this assignment is to give you some experience working with inheritance and abstract classes in a realistic setting. You’ll also get some more practice with 2D arrays and lists. • Create implementations of six concrete subtypes of the Piece interface: – LShapedPiece – TeePiece – QuotesPiece – RotatingSPiece – CirclingPiece – SnakingPiece • Implement the abstract class AbstractPiece containing the common code for the concrete Piece classes above, and any other abstract classes that express general code common to two or more (but not all) of the pieces above. All your code should be in the package hw4. 1 TIPS FROM THE EXPERTS HOW TO WASTE A LOT OF TIME ON THIS ASSIGNMENT • Start the assignment the night it’s due. That way, if you have questions, the TAs will be too busy to help you and you can spend the time tearing your hair out over some trivial detail. • Don’t bother reading the rest of this document, or even the specification, especially not the “Getting started” section. Documentation is for losers. Try to write lots of code before you figure out what it’s supposed to do. • Don’t test your code. It’s such fun to remain in suspense until it’s graded! OVERVIEW In this project you will complete the implementation of a Tetris-style or “falling blocks” game. This game, which we will call BlockAddiction, is a mix of “Tetris” with a game like “Bejeweled”. If you are not familiar with such games, examples are easy to find on the internet. FIRST – PLAY THE GAME BY RUNNING THE JAR FILE PROVIDED TO YOU. Type on the command line: java -jar tetris.jar. Note that the pieces provided in the tetris.jar file are mostly different from the ones you will implement. The basic idea is as follows. The game is played on a 2D grid. Each position in this grid can be represented as a (row, column) pair. We typically represent these positions using the simple class api.Position, which you will find in the api package. At any stage in the game, a grid position may be empty (null) or may be occupied by an icon (i.e., a colored block), represented by the class api.Icon. In addition, a piece or shape made up of a combination of icons falls from the top of the grid. This is referred to as the current piece or current shape. As it falls, the current piece can be • shifted from side to side • transformed, which may rotate it or flip it or something else • cycled, which will change the relative positions of the icons within the piece, without changing the cells it occupies (that is, without changing the shape and position). TERMS: • Game Grid (Rows and columns for the game. Top Left hand corner is row 0 col 0.) • Position (represents a specific row and column) • Icon (a color) • Cell (consists of a position and a color – i.e. Icon) • Piece (Each piece is in a bounding square. For this assignment all the pieces are of size 3×3. The position of the top-left corner of the bounding square in the game grid is stored by the Piece. The piece has an array of cells. A cell is basically a (x,y) position in the matrix and a color (represented by Icon). Not all coordinates of the bounding box has a cell. See the example for a LShapedPiece in figure 3. The position IN the game grid is 2,3. The bounding square is 3×3. The squares in relative positions (0,0), (0,1), (1,1), (2,1) have cells with colors yellow, cyan, green, and red respectively. 2 Position(2, 3) Figure 1: An LShapedPiece • Invoking cycle() (changes color of the CELLS occupied by the piece) • Invoking transform() (changes the position of the CELLS of the piece within the bounding square for the piece). A user interface is provided which has the following key mappings: • left arrow – shift the current falling piece left, if possible • right arrow – shift the current piece right, if possible • down arrow – make the current piece fall faster • up arrow – apply the transform() method • space bar – cycle the blocks within the piece • ’p’ key – pause/unpause Figure 2: An LShapedPiece falling, and the collapsible set of three matching adjacent red icons disappers, and the blocks above them shift down. When the currently falling piece can’t fall any further, its icons are added to the grid, and the game checks whether it has completed a collapsible set. In BlockAddiction, a collapsible set is formed of three or more adjacent icons that match (have the same color). All icons in a collapsible set are then removed from the grid, and icons above them are shifted down an equivalent amount. (Note that there is no “gravity” and there can be empty spaces remaining below an icon in the grid.) The new icon positions may form new collapsible sets, so the game will iterate this process until there are no more collapsible sets. 3 This behavior is already implemented in the class AbstractGame, and there is also an abstract method determinePositionsToCollapse(), which finds the positions in collapsible sets. You will not have to implement this method – it will be given to you. SPECIFICATION The specification for this assignment includes • this pdf • the provided javadoc You will also be provided with some sample code to provide the api you must use as well as some UI code for you to observe your code executing. Note that your code will not be tested using the UI. The UI is just for fun/inspiration. You should depend more on tests for establishing the correctness of your code. Get the provided source code The code will be provided to you as a .zip file which contains a whole project missing the files that you need to implement. • Download and save the file Homework4Skeleton.zip file from Canvas • If your workspace is empty, create a new project in Eclipse called Homework4tmp. This is just because Eclipse will not import a zip file when there are no projects in your workspace. • At the top, choose the File menu entry then Import. • Open the General option and select Projects from Folder or Archive File in the Import dialog and click Next. • Click the Archive button to indicate you want to import from an archive. Then browse to choose the zip file from the file system and click Finish. • In the Project Explorer, you can open the newly created project and click on the src directory and you will see directories including api and examples. Be sure to read the file called SamplePiece under examples, and the file Piece under api. Those are the most important files you will be working with. You can create a new package called hw4, and that is where your own files (the six files mentioned above) should be created. You should also create any necessary abstract classes and corresponding test files in there. The Piece interface and the six concrete Piece types See the javadoc for the Piece interface. You can generate the javadoc locally by opening the Piece.java file (in the api package), and Click on Project menu then Generate Javadoc. The generated javadocs will be stored in the doc directory in your project (you must confirm this choice). Then you can browse and search for the Piece.html file and open it in your favorite browser. The currently falling piece is represented by an object that implements the Piece interface. Each piece has a state consisting of: 4 • The position in the grid of the upper-left corner of its bounding square, represented as an instance of Position (which can change as a result of calling methods such as shiftLeft(), shiftRight(), or transform()). • The icons that make up the piece, along with their relative positions within the bounding square. The position of a piece within a grid is always described by the upper left corner of its bounding square. Most importantly, there is a getCellsAbsolute() method that enables the caller to obtain the actual positions, within the grid, of the icons in the piece. The individual icons in the piece are represented by an array of Cell objects, a simple type that encapsulates a Position and an Icon. A Position is just a (row, column) pair, and an Icon just represents a colored block. For example, one of the concrete Piece classes you will implement is the LShapedPiece. One is shown below in its initial (non-transformed) configuration. The method getCells() returns four cell objects with the positions relative to the upper left corner of the bounding square, namely (0, 0), (0, 1), (1, 1), and (2, 1), in that order, where the ordered pairs represent the relative (row, column), NOT the absolute (x, y). (The colors are shown for illustration, and are normally assigned randomly by the generator for the game.) Suppose that the piece’s position (upper left corner of bounding square) is row 2, column 3 on the game grid. Then the getCellsAbsolute() method should return an array of four cell objects with positions (2, 3), (2, 4), (3, 4), and (4, 4), in that order. Position(2, 3) Figure 3: An LShapedPiece If the method shiftRight() is called on this piece, the position is updated, but getCells() would still return the same cells, since the positions are relative to the upper left corner. But the getCellsAbsolute() method would now return (2, 4), (2, 5), (3, 5), and (4, 5), as shown in figure 4. Position(2, 4) Figure 4: An LShapedPiece Each piece defines a behavior associated with the transform() operation. For the LShapedPiece, the transform() operation just flips it across its vertical centerline. The position of the bounding square does not change, but the positions of the cells within the bounding square are modified. After the modification, the getCells() method should return an array of cells with positions (0, 2), (0, 1), (1, 1), and (2, 1), and the getCellsAbsolute() method should return an array of four cell objects with positions (2, 5), (2, 4), (3, 4), and (4, 4), in that order, as shown in figure 5. Position(2, 3) Figure 5: LShapedPiece flipped (reflected) Horizontally 5 Likewise, if the cycle() method is invoked, the positions for the cells stay the same but the icons associated with the cells will change. The illustration in figure 6 shows the result of invoking cycle() on the initial configuration. Position(2, 3) Figure 6: LShapedPiece (left) with icons cycled (right) Each icon shifts forward to the next cell, and the last icon is placed in the first cell. (The ordering of the cells always the same, even if transformed.) Altogether you will need to create six concrete classes, described below, that (directly or indirectly) extend AbstractPiece and, therefore, implement the Piece interface. It is up to you to decide how to design these classes, but a portion of your grade will be based on how well you use inheritance to avoid duplicated code. Remember that in the descriptions below, an ordered pair is (row, column), NOT (x, y): 1. The one illustrated above, called the LShapedPiece. Initially the icons are at (0, 0), (0, 1), (1, 1), and (2, 1), in that order. The transform() method flips the cells across the vertical centerline. 2. The TeePiece, which has a 3 x 3 bounding square, shown below with its initial configuration on the left, with initial icon positions in the order (0, 0), (1, 0), (1, 1) and (2, 0). The transform() method flips the cells across the vertical centerline, as shown on the right (similar to the the LShapedPiece) in figure 7. Figure 7: TeePiece (left) after calling transform once (right) 3. The QuotesPiece, which has a 3 x 3 bounding square with the icons down the center in the order (0, 0), (1, 0), (0, 2) and (1, 2). This looks like a pair of ticks as in a double quote. For the QuotesPiece, the transform() method rotates the bounding square clockwise by a quarter turn, as shown in figure 8. Figure 8: QuotesPiece (left) after calling transform once (right) 4. The RotatingSPiece, also with a 3 x 3 bounding square and icons initially in positions (0, 0), (0, 1), (1, 1) and (1, 2). This looks very slightly like an S-shape. For this piece the transform() method rotates the bounding square clockwise by a quarter turn, as shown in figure 9. 6 Figure 9: RotatingSPiece (left) after calling transform once (right) 5. The CirclingPiece, has a 3 x 3 bounding square and initial cell positions (0, 0), (1, 0), (2, 0) and (2, 1) in that order from the “head” of the snake (or the leading cell) to the tail (the trailing cell). The transform() method moves the piece clockwise around the periphery (edges) of the bounding box like a snake or a train. When three transforms are applied consecutively the resulting sequence is illustrated in figure 10. Figure 10: CirclingPiece (left) showing three transforms Note that it takes eight transforms to arrive back in the original configuration. This is therefore different from rotating the bounding box right by a quarter turn, which would return to its original configuration after four transforms. 6. The SnakingPiece, which has a 3 x 3 bounding square and initial cell positions (0, 0), (1, 0), (1, 1) and (1, 2) in that order from the “head” of the snake (or leading cell) to the tail (the trailing cell). The transform() method transitions through twelve different states (like a snake or a train) and back to the original, following a snake-like pattern as shown in figure 11 (reading left-to-right and top-to-bottom): Figure 11: SnakingPiece (top left) showing all twelve states The motion of the “head” is like drawing a figure of eight (clockwise in the top loop and anticlockwise in the bottom loop) and involves travelling across the middle row twice. Special advice is given below 7 about a relatively easy way to implement this. It is recommended that you implement this first and afterwards you can implement the CirclingPiece while trying to take advantage of similar strategies, and as always trying to reduce code duplication. When you implement these six concrete types, pay careful attention to code reuse, and implement common code for the Piece interface in an abstract superclass called AbstractPiece. You will also be encouraged to notice similarities in the transform code for specific pieces, which allows you to create their transform functions in abstract classes so that the concrete classes can be a lot shorter / simpler. Part of your score will be based on how well you have taken advantage of inheritance and abstraction to reduce code duplication among the six concrete types. Each of these types has a constructor that takes an initial position and an array of Icon objects: public LShapedPiece(Position position, Icon[] icons) public QuotesPiece(Position position, Icon[] icons) public TeePiece(Position position, Icon[] icons) public RotatingSPiece(Position position, Icon[] icons) public CirclingPiece(Position position, Icon[] icons) public SnakingPiece(Position position, Icon[] icons) The given icon objects are placed in the initial cells in the order given. Each constructor should throw IllegalArgumentException if the given array is not the correct length. There are some additional notes below about implementing transform() for the SnakingPiece and for implementing clone(). Note about the clone() method TL;DR In most cases you can just copy and paste the clone() method from SamplePiece into AbstractPiece, changing the SamplePiece cast to AbstractPiece. A Piece must have a clone() operation that returns a deep copy of itself. This is actually a critical part of the implementation, since the mechanism that the AbstractGame uses to detect whether a shift or transform is possible is by cloning the shape, performing the shift or transform first on the clone, and checking whether it overlaps other blocks or extends outside the grid. The method clone() is defined in java.lang.Object as follows: protected Object clone() throws CloneNotSupportedException The default implementation of clone() makes a copy of the object on which it’s invoked, and although it is declared to return type Object, it always creates an object of the same runtime type. However, it is a “shallow” copy, i.e., it just copies the instance variables, not the objects they refer to. Therefore, in order to use it, you have to add your own code to deep-copy the objects that your instance variables refer to (for the Piece classes, you might have a Position and an array of Cells, for example). In addition, due to some technical nonsense we have to put the call to clone() in a “try/catch” block. We have not seen try/catch yet, but do not worry, you just have to follow the pattern below, as seen in examples.SamplePiece: @Override public Piece clone() { try { // call the Object clone() method to create a shallow copy… SamplePiece s = (SamplePiece) super.clone(); // …then make it into a deep copy 8 // (note there is no need to copy the position, // since Position is immutable, but we have to deep-copy // the cell array by making new Cell objects s.cells = new Cell[cells.length]; for (int i = 0; i < cells.length; ++i) { s.cells[i] = new Cell(cells[i]); } return s; } catch (CloneNotSupportedException e) { // can’t happen, since we know the superclass is cloneable return null; } } In most cases, you’ll implement AbstractPiece using instance variables for the position and cell array as in SamplePiece, and in that case you can just copy and paste the clone() method, changing the SamplePiece cast to AbstractPiece. Basically, you need to make copies of any mutable objects that your instance variables refer to, so that the original and the clone don’t share references to the same mutable objects. Immutable objects can be shared when cloning without any problem. So if you have added more reference variables to AbstractPiece, consider whether they need to be copied when you make a clone. The clone() mechanism in Java tends to be a fragile and often trouble-prone, and it only works on objects that are specifically implemented with cloning in mind. Java programmers tend to avoid using clone() unless there is a good reason. Notice that in the example above, we’re not using clone() to make a copy of the the Cell – it’s simpler just to use the copy constructor. But for the piece classes, by taking advantage of the built-in clone() mechanism you can implement clone() just once in the superclass and allow the subclasses to inherit it. (Of course, if any of your subclasses have any additional, non-primitive instance variables beyond those defined in your superclass, you’ll need to override clone() again for them in order to get a deep copy.) The Game interface and the AbstractGame class You don’t need to write any code for this section. See the javadoc for the Game interface. The class AbstractGame is a partial implementation of the Game interface. YOU DO NOT HAVE TO WRITE CODE FOR THE AbstractGame class. It is PROVIDED to you as well as a concrete implementation of BasicGame.java. A client such as the sample UI interacts with the game logic only through the interface Game and does not depend directly on the AbstractGame class or its subclasses. AbstractGame is a general framework for any number of Tetris-style games. It is specialized by implementing the abstract method: List determinePositionsToCollapse() Examines the grid and returns a list of positions to be collapsed. (Remember that List is the interface type that ArrayList implements, so your method can return an ArrayList.) The key method of Game is step(), which is called periodically by the UI to transition the state of the game. The step() method is fully implemented in AbstractGame, and it is not necessary for you to read it in detail unless you are interested. You will just need a basic understanding of how it interacts with the determinePositionsToCollapse() method that you will implement. In BlockAddiction, the task of determinePositionsToCollapse() is to identify the positions of icons in all “collapsible sets”, that is, sets of three or more adjacent icons with matching color. 9 If you are interested: The way that determinePositionsToCollapse() is invoked from AbstractGame is the following. Whenever the current shape cannot fall any further, the step() method calls determinePositionsToCollapse(). If the returned list is nonempty, then the list is stored in the state variable positionsToCollapse and the game transitions into the COLLAPSING state. On the next call to step(), the method collapsePositions() of AbstractGame is invoked to perform the modification of the grid to remove the icons and shift down the icons above them. In many of these kinds of games, collapsing some positions may create additional collapsible sets of positions, possibly starting a chain reaction, so the logic of the COLLAPSING state is basically the following: while (game state is COLLAPSING) { collapsePositions(positionsToCollapse); positionsToCollapse = determinePositionsToCollapse(); if (positionsToCollapse.size() == 0) { // generate a new current shape // change game state to NEW_SHAPE } } Remember, the class AbstractGame is fully implemented and you should not modify it. The BlockAddiction class YOU DO NOT HAVE TO WRITE CODE FOR THE BlockAddiction class You will create a subclass of AbstractGame, called BlockAddiction, that implements the game described in the introduction. The method determinePositionsToCollapse() must be declared public even though it is declared protected in AbstractGame (yes, Java allows this). This requirement is to make it easier to test your code. There are two constructors declared as follows: public BlockAddiction(int height, int width, Generator gen, int preFillRows) public BlockAddiction(int height, int width, Generator gen) (The second one is equivalent to calling the first one with zero for the fourth argument.) The height, width, and generator are just passed to the superclass constructor. If preFillRows is greater than zero, your constructor should initialize the bottom preFillRows rows in a checkerboard pattern, using random icons obtained from the generator. The checkerboard pattern should place an icon at (row, col) in the grid if both row and col are even, or if both row and col are odd. See the illustration on page 3. Implementing the method determinePositionsToCollapse() The method determinePositionsToCollapse() is potentially tricky, and you can waste a lot of time on it if you don’t first think carefully. A collapsible set is defined to be any set of three or more adjacent icons with the same color, so it could potentially contain many icons. Given an icon in a collapsible set, it is a hard problem to find just the cells that are part of that set. However, notice that you do not have to solve that problem. You have an easier problem, which is to return a list including all cells that are part of any collapsible set in the grid. What makes a cell part of a collapsible set? Well, either it has two or more neighbors that match its color, or else it must be a neighbor of such a cell. Therefore, it is enough to iterate over the grid and do the following for each array element: 10 If the element is non-null and has two or more neighbors that match, add it to the list, and also add all its matching neighbors to the list. The list may contain many duplicates, which is not hard to deal with – just create a new list, copy the positions over, but ignore any that you have already found (the list method contains() is useful here). Finally, the list needs to be sorted. Fortunately, the Position class implements the Comparable interface so you can just call Collections.sort on your list. The BasicGenerator class See the javadoc for the Generator interface YOU DO NOT HAVE TO WRITE CODE FOR THE BasicGenerator class. It is PROVIDED TO YOU. One important detail for the challenge and playability of the game is to configure what pieces are generated and the probability of getting each type. The role of the Generator interface is to make these features easy to configure. The AbstractGame constructor requires a Generator instance to be provided to its constructor. There is a partially implemented skeleton of the BasicGenerator class implementing the Generator interface. Ultimately, it should return one of the six concrete piece classes, selected according to the probabilities given in the javadoc comments. As you develop your Piece classes, you can just add statements to generate the ones you have completed and tested. (An easy way to generate pieces with varying probabilities: generate a random number from 0 to 100, and if it’s in the range 0 up to 10 return an LShapedPiece, if it’s in range 11 up to 35 return the next type of piece, and so on.) See the BasicGenerator javadoc comments for more details. The UI There is a graphical UI in the ui package. The controls are the following: • left arrow – shift the current falling piece left, if possible • right arrow – shift the current piece right, if possible • down arrow – make the current piece fall faster • up arrow – apply the transform() method • space bar – cycle the blocks within the piece • ’p’ key – pause/unpause The main method is in ui.GameMain. You can try running it. It will start up a small instance of the partly implemented class example.SampleGame. See the “Getting started” section for more details. To run the UI with your BlockAddiction game once you get it implemented, you will need to edit ui.GameMain. The UI is built on the Java Swing libraries. This code is complex and specialized, and is somewhat outside the scope of the course, but of course you are welcome to read it. It is provided for fun, not for testing your code! It is not guaranteed to be free of bugs. TESTING AND THE SPECCHECKER As always, you should try to work incrementally and write tests for your code as you develop it. For the Piece hierarchy you can create corresponding files called *something*PieceTests.java and run some basic tests on your own class. Remember for this you will not be submitting your tests, so you are welcome to share your test files with each other (but not your submitted code). 11 Do not rely on the UI code for testing! Trying to test your code using a UI is very slow, unreliable, and generally frustrating. In particular, when we grade your work we are NOT going to run the UI, we are going to verify that each method works according to its specification. We will provide a basic SpecChecker on Gradescope, but it will not perform any functional tests of your code. At this point in the course, you are expected to be able to read the specifications, ask questions when things require clarification, and write your own unit tests. Since the test code is not a required part of this assignment and does not need to be turned in, you are welcome to post your test code on Piazza for others to check, use and discuss. The SpecChecker will verify the class names and packages, the public method names and return types, and the types of the parameters. If your class structure conforms to the spec, all the tests will pass. Remember that your instance variables should always be declared private, and if you want to add any additional methods that are not specified, they must be declared private or protected. Special documentation and style requirements • You may not use protected, public , or package-private instance variables. Normally, instance variables in a superclass should be initialized by an appropriately defined superclass constructor. You can create additional protected getter/setter methods if you really need them. • Accessor methods should not modify instance variables. • Class javadoc must include the @author tag, and method javadoc must include @param and @return tags as appropriate. – Try to state what each method does in your own words, but there is no rule against copying and pasting the descriptions from this document. – When a class implements or overrides a method that is already documented in the supertype (interface or class) you normally do not need to provide additional Javadoc, unless you are significantly changing the behavior from the description in the supertype. You should include the @Override annotation to make it clear that the method was specified in the supertype. • All variable names must be meaningful (i.e., named for the value they store). • Your code should NOT be producing console output. You may add println statements when debugging, but you need to remove them before submitting the code. • Internal (//-style) comments are normally used inside of method bodies to explain how something works, while the Javadoc comments explain what a method does. (A good rule of thumb is: if you had to think for a few minutes to figure out how something works, you should probably include a comment explaining how it works.) o Internal comments always precede the code they describe and are indented to the same level. • Use a consistent style for indentation and formatting. GETTING STARTED The following high-level sequence of steps may be a good approach to completing this project. 12 1. First play the game provided to you in the tetris.jar file as described above, if you haven’t already. Type on the command line: java -jar tetris.jar. Note that the pieces provided in the tetris.jar file are mostly different from the ones you will implement. 2. At this point we expect that you know how to study the documentation for a class, write test cases, and develop your code incrementally to meet the specification. The code you’ll implement is mostly specified in the file api/Piece.java. Please read it and its javadoc to understand what each method is supposed to do. 3. Next, in the examples package you’ll find a simplified, partial implementation of the Piece interface, called SamplePiece, and a simplified, partial subclass of AbstractGame called SampleGame. Currently the ui.GameMain class is set up to create another type of game called a BasicGame. Search the code in ui/GameMain.java for the words SampleGame and enable that, while disabling the creation of a tt BasicGame. Then if you run the main class ui.GameMain, it will start up the SampleGame game and you should see a red two-block shape falling from the top. Try implementing the shiftLeft and shiftRight methods of SamplePiece to make the block shift from side to side with the arrow keys. That will be a rudimentary Tetris game. 4. There is a better version of a Game class called BasicGame in the hw4 subdirectory. BasicGame will allow you to start implementing and adding your own concrete piece implementations. Once you have played with SampleGame to understand it, you can switch ui.GameMain to invoke BasicGame instead of SampleGame. Make this change by editing the file ui/GameMain.java to comment out the SampleGame creation (search for SampleGame to find it), and instead use the next paragraph after that, which creates a BasicGame. 5. General advice about using inheritance: It may not be obvious how to decide what code belongs in AbstractPiece. A good way to get started is to forget about inheritance at first. Pick one of the required concrete types, such as LShapedPiece, and simply copy the contents of AbstractPiece to a new file called LShapedPiece, make it not abstract, declare that it implements Piece. Then search and replace AbstractPiece with LShapedPiece in just that file, and implement the methods in api/Piece.java which are not implemented yet in LShapedPiece.java. 6. When you want to run a new piece, you need to edit hw4/BasicGenerator.java to enable it by making your new Piece one of the pieces that the random generator can generate. Initially the random generator will nly generate the red block of two cells (ie. a SamplePiece). Comment out that return statement and write a return statement for an LShapedPiece instead. 7. Then, choose another concrete type (the TeePiece may be good to do next), and write all the code for that one the same way you did the previous step. When you have two or more Piece types that can be generated, then you can start using an if-statement in hw4/BasicGenerator.java to choose which Piece to generate based on the value of the random number generated. Please read hw4/BasicGenerator.java for how your if-statement could look when you have finished the project. 8. At this point you’ll notice that you had to write lots of the same code twice. Move the duplicated code into AbstractPiece, and change the declaration for LShapedPiece so it says extends AbstractPiece instead of implements Piece. Likewise, change the declaration for TeePiece so that it says extends AbstractPiece. 13 That’s a good start, and you can use a similar strategy as you implement the other piece types. Note the use of protected constructors for AbstractPiece in order to initialize it. The protected constructors are already done for you. Note that any code that is shared by all the concrete pieces should be written in the AbstractPiece. 9. Implement some more pieces, this time using the declaration extends AbstractPiece. The next two bullet items suggest how to write some of the more difficult pieces like RotatingSPiece and SnakingPiece. It is best to read the suggestions below before implementing those. 10. Implementing transform() for the RotatingSPiece: Implementing rotation can be done for any piece by focusing on the background of the piece, that is the whole bounding box, rather than the specific set of occupied cells. To see the coordinate changes that are needed, perform the following exercise: • Take a sheet of paper or an index card. It should be rectangular (not square). • Write on it the words “Hello World” to remind yourself what the original orientation was. • Draw an arrow from the top left corner, downwards along the left edge, about halfway, and label it “i = row”. • Draw an arrow from the top left corner, rightwards along the top edge, about one-third of the way, and label it “j = col”. • Draw a square or dot on the paper which is “i” rows down and “j” columns across to the right. • Now physically rotate your sheet of paper clockwise by a quarter turn (that is 90 degrees). (If you did this correctly four times you should end up back where you started, but do this only once). Now the long side and short side of the paper should have “exchanged places”. The written words “Hello World” should be downwards now if you wrote horizontally to begin with. • While staring at the paper in this new orientation note how the new value of i of the square or dot (meaning distance down the new page) depends on the old value of i and j. Also note how the new value of j ( that is, the distance to the right across the new page) depends on the old values of i and j. This shows you how the old cell at (i, j) will move (that is, the position it will move to) when the clockwise-rotation transform is done. The nice thing is that this is true not just for the square or dot, but for every position with any row i and any column j. • Use your conclusions in the previous step to write the transform code. • Test it by hand-running a small example to make sure it does what you expect. • Adjust your code so that it only rotates the actual cells you have in the Piece shape, rather than the whole background if you haven’t done so already. Note that when the code is written correctly it is much much shorter than the intuitive description above of why it works. 11. Implementing transform() for SnakingPiece: Please do not just write twelve different cases! There are a few ways to approach this, as always, but here is one idea. First, imagine that there is just one cell that starts at (0, 0) and the transform method should shift it to (0, 1), then to (0, 2), then to (1, 0), and so on (picture the red icon in the illustration above). Rather than using a bunch of if- statements, you can just create an array of Position objects in the order you want: 14 private static final Position[] sequence = { new Position(0, 0), new Position(0, 1), new Position(0, 2), new Position(1, 2), new Position(1, 1), new Position(1, 0), new Position(2, 0), new Position(2, 1), new Position(2, 2), new Position(1, 2), new Position(1, 1), new Position(1, 0), }; and then maintain a counter that goes from 0 to 11 and wraps around back to 0. At each call to transform(), update the counter and set the cell position using the counter as an index into your sequence array. How about the remaining three cells? Notice that the positions you want for them are always the three preceding ones in the sequence array, where, if your index goes down from 0 you wrap around to 11 (that is to say, 11 is the correct representation of -1 in this indexing system). 12. As you get further along, you may also notice some other opportunities to create other abstract classes which are shared by two or more Pieces, but not all the Pieces. To express this code in just one place, you should create your own abstract classes in addition to the provided AbstractPiece. You should do this whenever possible to reduce code duplication. Do you notice more than two Pieces which could use the same transform code? Can you create an abstract class to capture that commonality? 13. To run the UI with your BlockAddiction game once you get it implemented, you’ll need to edit the create method of ui.GameMain. IF YOU HAVE QUESTIONS For questions, please use Piazza. If you don’t find your question answered, then create a new post with your question. Try to state the question or topic clearly. But remember, do not post any source code for the classes that are to be turned in. It is fine to post source code for general Java examples that are not being turned in, and for this assignment you are welcome to post and discuss test code. If you have a question that absolutely cannot be asked without showing part of your source code, post it ONLY in your private channel – so that only the instructors and TAs can see it. Be sure you have stated a specific question; vague requests of the form “read all my code and tell me what’s wrong with it” will generally be ignored. Of course, the instructors and TAs are always available to help you. We do our best to answer every question carefully, short of actually writing your code for you, but it would be unfair for the staff to fully review your assignment in detail before it is turned in. WHAT TO TURN IN Please submit, on Gradescope, the following six files and any other abstract classes you created, all of which must be in the package hw4: 15 • AbstractPiece.java • LShapedPiece.java • QuotesPiece.java • TeePiece.java • RotatingSPiece.java • CirclingPiece.java • SnakingPiece.java Please make sure you upload the correct pieces! Submit the files to Gradescope using the Programming Assignment 4 submission link.
The purpose of this assignment is to give you some practice writing loops, using arrays and lists, and, most importantly, to get some experience putting together a working application involving several interacting Java classes.There are three classes for you to implement: Block, Board, and GridUtil. There is also an extra credit class Solver that is covered in a separate document. As always, your primary responsibility is to implement these classes according to the specification and test them carefully.The three classes can be used, along with some other components, to create an implementation of our version of a sliding block puzzle game.The game is played on a 2-dimensional grid of cells. Each cell may be a floor, a wall or exit. Cells that are floors or exits can be occupied by a block. Blocks are 1 cell wide by 2 or more cells long and are oriented either horizontally or vertically. A horizontal block can only move left and right and a vertical block can only move up and down. Only one block can occupy a cell at a time.The goal is to move one of the blocks to the exit. Naturally, other blocks may be in the path and need to be moved. A block can be moved by grabbing (pressing the mouse button) on any of its segments and dragging. The block is moved one cell at a time as it is being dragged. The three classes you implement will provide the “backend” or core logic for the game. In the interest of having some fun with it, we will provide you with code for a GUI (graphical user interface), based on the Java Swing libraries.The sample code includes a documented skeleton for the classes you are to create in the package hw3. The additional code is in the packages ui and api. The ui package is the code for the GUI, described in more detail in a later section. The api package contains some relatively boring types for representing data in the game, along with a utility class with methods for creating the game grid and printing out the game in text format. There are a few examples of test cases for you to start with located in the default package, along with a simple text-based user interface.The complete specification for this assignment includesSeveral constants are used to describe the state and actions of the games. To describe a blocks orientation of the board, we use two constants Orientation.VERTICAL and Orientation.HORIZONTAL. In addition, the motion of a block is described using four constants Direction.LEFT, Direction.RIGHT, Direction.UP, and Direction.DOWN. Finally, types of cells are described as CellType.FLOOR, CellType.WALL, and CellType.EXIT.All of the above constants are defined as an “enumerated” type or enum. You can basically use them as though they had been defined as public static final constants. You can’t construct instances, you just use the four names as literal values. Use == to when checking whether two values of this type are the same, e.g. if dir is a variable of type Direction, you can write things like if (dir == Direction.UP) { // do cool stuff }An enum type can also be used as the switch expression in a switch statement. Tip: add the lines import static api.Orientation.*; import static api.Direction.*; import static api.CellType.*; to the top of your file. Then you can refer to the constants without having to type, for example, “Direction.” in front of them.A Block object is described by its location on the board (first row and column), its length and its orientation (vertical or horizontal). The first row and column indicate the location of the upper-left most corner of the block. In other words, vertical blocks extend downward and horizontal blocks extend to the right of the first row and column.The move method can be used to move a horizontal block one cell right or left and a vertical block one cell up or down. Here moving simply means the first row and column of the block are updated.A reset method simply resets the first row and column to their original starting point when the object was created.A Board object maintains a 2D array of cells, a list of blocks, and other state related to the game. The user can “grab” a block on the board with the method grabBlockAtCell, which is called by the GUI when a user presses the mouse button down on any segment of a block. The grabbed block can be dragged one cell at a time either up, down, right, or left by calling moveGrabbedBlock. When moving a block, the state of the cells and the block must both be updated to be consistent. This is because the cells know what block is located over them and the blocks know their row and column location on the board. An important piece of information is the cell over which the block is being grabbed. The method getGrabbedCell is required by the GUI to determine when the block is being dragged one more cell. This means that the currently grabbed cell also moves by one in the same direction each time the grabbed block is moved. Each move is also added as a new Move object to the end of a list moveHistory. The user can end grabbing the block by calling releaseBlock.The board can be reset to the starting point when it was created by calling reset. The blocks, cells, move count, move history, and is game over status should all be returned to their original starting values.The method get getAllPossibleMoves finds all legal moves that can be made from the current position and returns it as a list. This method is used by the hint feature to suggest a random legal move that can be made. It will also be useful when implementing the game solver described below.One final method, which is useful when implementing the solver, is undo. As its name implies it undoes the most recent move, setting the blocks position and move count back to their previous values.The GridUtil class contains two static methods used for converting a string description of a board into a 2D array of cells and a list of blocks. The following is an example of a board description.* * * * * * * ** [ ] ^ ^ . . ** . . v v [ ] ** [ # # ] ^ . ** ^ [ ] . v ^ e* # ^ . [ ] # ** # v . [ ] v ** v [ # # # ] * * * * * * * * *The meaning of the symbols are:^ # # vwith zero or more #.A Solver object uses recursion to find all solutions to a board setup. Completing the class is extra credit. Suggestions on how to implement the solve method are provided in a separate document.There is also a graphical UI in the ui package. The GUI is built on the Java Swing libraries. This code is complex and specialized, and is somewhat outside the scope of the course. You are not expected to be able to read and understand it. However, you might be interested in exploring how it works at some point. In particular it is sometimes helpful to look at how the UI is calling the methods of the classes you are writing.The controls are simple: You can press down on the mouse to grab a any segment of a block and drag to move the block.The main method is in ui.GameMain. You can try running it, and you’ll see the initial window, but until you start implementing the required classes you’ll just get errors. All that the main class does is to initialize the components and start up the UI machinery. The class GamePanel contains most of the UI code and defines the “main” panel, and there is also a much simpler class ScorePanel that contains the display of the score.You can edit GameMain to use a different initial board descriptor. Alternatively, once you have GridUtil fully implemented, you can use the “Choose from file” button in the game to select one of the games from a file of descriptors.The graphical board is a representation of the 2D array of api.Cell object and the list of blocks in Board.As always, you should try to work incrementally and write tests for your code as you develop it.We will provide a basic SpecChecker, but it will not perform any functional tests of your code. At this point in the course, you are expected to be able to read the specifications, ask questions when things require clarification, and write your own unit tests.Since the test code is not a required part of this assignment and does not need to be turned in, you are welcome to post your test code on Piazza for others to check, use and discuss. The SpecChecker will verify the class names and packages, the public method names and return types, and the types of the parameters. If your class structure conforms to the spec, you should see a message similar to this in the console output:x out of x tests pass.This SpecChecker will also offer to create a zip file for you that will package up the two required classes. Remember that your instance variables should always be declared private, and if you want to add any additional “helper” methods that are not specified, they must be declared private as well. While you can use the SpecChecker on your own computer, the eventual submission of your work will be on Gradescope. You should submit the files Block.java, Board.java, GridUtil.java and (the extra credit file) Solver.java on Gradescope.The sample code includes a complete skeleton of the four classes you are writing. It is distributed as a complete Eclipse project that you can import. It should compile without errors out of the box.If you have an older version of Java or if for some reason you have problems with this process, or if the project does not build correctly, you can construct the project manually as follows:At this point we expect that you know how to study the documentation for a class, write test cases, and develop your code incrementally to meet the specification, so this getting started section will not be quite as detailed as for the previous assignments.Block block = new Block(2, 1, 2, HORIZONTAL);System.out.println(“Block is ” + block);block.move(DOWN); // horizontal blocks not allowed to move downSystem.out.println(“After move DOWN, block is ” + block);System.out.println(“Expected block at (row=2, col=1).”);block.move(RIGHT);System.out.println(“After move RIGHT, block is ” + block);System.out.println(“Expected block at (row=2, col=2).”); Before main:public static final String[][] testDescription1 = { { “*”, “*”, “*”, “*”, “*” }, { “*”, “.”, “.”, “.”, “*” }, { “*”, “[“, “]”, “.”, “e” }, { “*”, “.”, “.”, “.”, “*” }, { “*”, “*”, “*”, “*”, “*” } }; In main:Cell[][] cells = GridUtil.createGrid(testDescription1);System.out.println(“Using testDescription1, cell (2, 4) is an exit is “+ cells[2][4].isExit() + “, expected is true.”); ArrayList blocks = GridUtil.findBlocks(testDescription1);System.out.println(“Using testDescription1, number of blocks is “+ blocks.size() + “, expected is 1.”);System.out.println(“Using testDescription1, first block is length “+ blocks.get(0).getLength() + “, expected is 2.”); Before main:private static ArrayList makeTest1Blocks() { ArrayList blocks = new ArrayList(); blocks.add(new Block(2, 1, 2, HORIZONTAL)); return blocks; } In main:System.out.println(“Making board with testGrid1.”);Board board = new Board(testGrid1, makeTest1Blocks());System.out.println(board.toString()); The expected output is:Making board with testGrid1.* * * * * * . . . * * [ ] . e * . . . * * * * * * board.grabBlockAtCell(2, 1);System.out.println(“Grabbed block ” + board.getGrabbedBlock());System.out.println(“Location of grab is at (“+ board.getGrabbedCell().getRow()+ “, ” + board.getGrabbedCell().getCol()+ “), expected (2, 1).”); board.moveGrabbedBlock(RIGHT);System.out.println(“After moving block right one time game over is “+ board.isGameOver() + “, expected is false.”);System.out.println(board.toString());System.out.println(); board.moveGrabbedBlock(RIGHT);System.out.println(“After moving block right two times game over is “+ board.isGameOver() + “, expected is true.”);System.out.println(board.toString()); The expected output is:Using testGrid1, after moving block right one time game over is false, expected is false.* * * * * * . . . * * . [ ] e * . . . * * * * * * Using testGrid1, after moving block right two times game over is true, expected is true.* * * * * * . . . * * . . [ e * . . . * * * * * *By now there should be enough functionality implemented that the GUI is mostly working. You can start it from ui/GameMain.java. Several example games are provided with the project skeleton code in games.txt. Keep in mind the warning above that a GUI can’t replace test cases when debugging and testing code, but it can be helpful to visualize the game. board.reset();System.out.println(“After reset:”);System.out.println(board.toString());System.out.println(); ArrayList moves = board.getAllPossibleMoves();System.out.println(“All possible moves: ” + Arrays.toString(moves.toArray())); The expected output is:After reset:* * * * * * . . . * * [ ] . e * . . . * * * * * * All possible moves: [(2, 1) one cell RIGHT] You can find the SpecChecker on Canvas. Import and run the SpecChecker just as you practiced in Lab 1. It will run a number of functional tests and then bring up a dialog offering to create a zip file to submit. Remember that error messages will appear in the console output. There are many test cases so there may be an overwhelming number of error messages. Always start reading the errors at the top and make incremental corrections in the code to fix them. When you are happy with your results, click “Yes” at the dialog to create the zip file. See the document “SpecChecker HOWTO”, if you are not sure what to do. The SpecChecker is being provided for local testing only, in case that is more convenient. Your work will be submitted on Gradescope for credit. Gradescope will also run other functional tests not included in the SpecChecker (you may or may not see the results of these).Roughly 10% of the points will be for documentation and code style. The general guidelines are the same as in homework 2. However, since the skeleton code has the public methods fully documented, there is not quite as much to do. Remember the following:For questions, please see the Piazza Q & A pages and click on the folder hw3. If you don’t find your question answered, then create a new post with your question. Try to state the question or topic clearly in the title of your post, and attach the tag hw3. But remember, do not post any source code for the classes that are to be turned in. It is fine to post source code for general Java examples that are not being turned in, and for this assignment you are welcome to post and discuss test code. (In the Piazza editor, use the button labeled “code” to have the editor keep your code formatting. You can also use “pre” for short code snippets.)If you have a question that absolutely cannot be asked without showing part of your source code, change the visibility of the post to “private” so that only the instructors and TAs can see it. Be sure you have stated a specific question; vague requests of the form “read all my code and tell me what’s wrong with it” will generally be ignored.Of course, the instructors and TAs are always available to help you. See the Office Hours section of the syllabus to find a time that is convenient for you. We do our best to answer every question carefully, short of actually writing your code for you, but it would be unfair for the staff to fully review your assignment in detail before it is turned in.Any announcements on Piazza that are labeled “Official Clarification” are considered to be part of the spec, and you may lose points if you ignore them. Such posts will always be placed in the Announcements section of the course page in addition to the Q&A page. (We promise that no official clarifications will be posted within 24 hours of the due date.)Note: You will need to complete the “Academic Dishonesty policy questionnaire,” found on the Assignments page on Canvas, otherwise you will not get any credit for doing this homework!. Please submit, on Gradescope, the zip file that is created by the SpecChecker. The file will be named SUBMIT_THIS_hw3.zip. and it will be located in whatever directory you selected when you ran the SpecChecker. It should contain one directory, hw3, which in turn contains four files, Block.java, Board.java, GridUtil.java, and Solver.java. Please LOOK at the file you upload and make sure it is the right one!Submit the zip file on Gradescope using the Programming Assignment 3 submission link and VERIFY that your submission was successful.We recommend that you submit the zip file as created by the specchecker. If necessary for some reason, you can create a zip file yourself. The zip file must contain the directory hw3, which in turn should contain the three required files. You can accomplish this by zipping up the src directory of your project. Do not zip up the entire project. The file must be a zip file, so be sure you are using the Windows or Mac zip utility, and NOT a third-party installation of WinRAR, 7-zip, or Winzip.If for any reason submitting the zipfile SUBMIT_THIS_hw3.zip does not work on Gradescope, then please submit the four files listed above individually as in previous Gradescope assignments.
The purpose of this assignment is to give you lots of practice working with conditional logic and managing the internal state of a class. You’ll create one class, called Tennis, that is a simplified model of the scoring system for the game of Tennis. Although there is a strong resemblance to the game of Tennis, it’s probably best if you forget everything you know about Tennis from the real world as you read these instructions. Your job is to implement the rules of the game that is specified in this document even if that conflicts with your understanding of any other Tennis rules. The following rules for scoring a tennis match are adapted from the USTA Scoring Rules at www.usta.com. https://www.usta.com/en/home/improve/tips-and-instruction/national/ tennis-scoring-rules.html 2 You may read that page for additional clarity, but when there is a substantive difference, prefer this document for the purposes of doing this programming assignment. For our purposes, Tennis is a two-player sport. The aim of tennis is to win enough points to win a game, enough games to win a set, and enough sets to win a match. Scoring a Match – the point system Tennis has two ways of counting things. Normal counting by using the numbers 0, 1, 2, . . . is used for games, sets and points in tiebreaks, but most of the time the points in a game are counted using the following nonconsecutive numbers: 0 when no points have been won, 15 when one point has been won, 30 when two points have been won, and 40 when three points have been won. When the score is 0, this is read aloud as “Love”. Generally when two players have won the same number of points, we say “(the score)-All”, with the exception that when players are tied at 40, we say “Deuce”. When the score is “Deuce”, a player must win two more points than the opponent in order to win. When the player has won one point more than the opponent, we say that player has an “Advantage” (and this is called out as “Advantage playerName”). If the player wins an additional point, they win the game, otherwise, the score returns to “Deuce”. Who Wins? A player can win a game by winning a point after getting a score of 40 provided the opponent has not yet obtained a score of 40. If both players get a score of 40, then the rules discussed for “Deuce” above are observed. Other than “Deuce”, if the players have the same number of points, or the same number of games, we use the word “All” to call out the score. For example the score could be “Thirty-All”, or “Fifteen-All”. Types of Tennis Sets A player needs to win enough games to win a set, and must have a minimum margin of victory in terms of games. There are two systems for winning a set, and during a tennis match we only use one of them throughout the match. 3 Advantage Set To win a set under the Advantage system, a player must win at least six games, and lead by a margin of at least two games in order to win the set. This can lead to long sets when players are tied after every other game. Tiebreak Set When playing under the Tiebreak system, a player can win a set with six or seven games when leading by a margin of at least two. If the game score gets to 6-all, then a tiebreak game is played. During a tiebreak game, points are counted normally (using 0, 1, 2, 3, . . . ), and a player must win the game by at least 7 points with a point-margin of at least two in order to win the last game of the set and with it, the set. Grand Slam Matches Grand Slam Matches were inconsistent in the past in terms of how their final set is completed when the score is six games all. It used to be the case that Advantage Sets were played, and as a result, the longest match in tennis history took three days to complete! Recently Grand Slam matches have been standardized to a tie-break format where a player needs to win at least 10 points by a margin of at least two, in order to win a Grand Slam match. This latter rule is what we will model in our program. Implementation Details Your goal is to implement a class called Tennis. The players are called playerA and playerB. The match will begin with playerA serving, and after that they toggle the role of serving at the end of every game (with an exception for tiebreaking which is explained later). This class will have methods that are called to indicate the following: public void winPoint(boolean playerAWins); Calling winPoint with a true argument means that playerA wins a point, and that must trigger a scoreboard update, and a new callout. Calling it with a false argument means playerB wins the point. This function will be called repeatedly to reflect the sequence in which points are won by the players. 4 When this method is called, it should determine whether winning the point implied that they also won the game. If they did win the game as well, it should also determine whether that means they also won the set. If they won the set, as well, it should also determine whether that means they won the match. We also want to be able to model the match at a higher level in terms of games won by making repeated calls to the following method (as if someone were telling you who won each game, but not telling you who won each point): public void winGame(boolean playerAWins); Calling it with a true argument means playerA won a game, while a false argument means playerB won a game. This method only tracks the numbers of games won, the number of sets won and the conclusion of the match. If a game is won, the method should determine whether that means a set was won, and if so, whether the match was won. Finally the simplest case of modelling is by making repeated calls to public void winSet(boolean playerAWins) Here too, we use the convention is that a true argument means playerA won a set, and a false argument means playerB won a set. This just counts the sets, and determines who wins the match by comparing the number of sets won. In this case you determine the sequence of calls to make by pretending someone is only telling you who won each set, but not telling you who won each game or point. Scoring This homework will separately track how scores are announced orally (which we will refer to as “callouts”), and how scores are updated on a scoreboard (which we call “scoreboard”). For oral scores, we assume the callouts are done in English, and use the following words: • 0 points = Love • 1 point = Fifteen (the word, not the number) • 2 points = Thirty 5 • 3 points = Forty • Tied score = All • 40-40 = Deuce • If playerX wins deuce point = Advantage So the following are examples of valid callouts: Fifteen-Forty Deuce Thirty-All Forty-Love Advantage while the following are not: Forty-Forty Forty-All The exception is when a tiebreaker is being played, in which case we use normal counting numbers to announce the scores, like 2-1, 2-2 and so on. Valid callouts list the higher score first, a dash, the lower score, a space and then the name of the leading player. If the scores are equal, then we simply callout the score followed by “-All”. Examples of valid callouts during tiebreaks are: 2-1 Alice 2-All 3-2 Betty We will also assume that at the end of a Game and before the next one, the callout announces the winner of the previous Game instead of the starting score of the next game, so the following are valid callouts: Game: Game and Set: Game, Set and Match: where is the name of the player that won that part of the match. For this reason, the following are not valid callouts (for the purposes of this assignment): 6 Love-Love Love-All We note in passing that all or most of these words would be different if playing in a non-English speaking country like France for example. But we expect the scoreboard to look substantially the same. For Updating the Scoreboard during a game that is not a tiebreaker, we only use natural counting numbers for sets and games, and use the numbers {0, 15, 30, 40} for scoring within a game. The only exception is that when one player has an advantage, their score will be “AD”, and the other player’s score will be “–“. The count of the games and sets will be done with ordinary counting numbers 0, 1, 2, 3, . . . A method called toString() will be provided in your skeleton code for printing out the scoreboard in a very precise format. This will enable us to compare the correct output the output you generate. The player serving next will be indicated by preceding their name with the string “S>”. A scoreboard could look like any of the following: S> Alice 0 0 0 Betty 0 0 30 This means Alice is serving and Betty has a score of 30, so the corresponding callout would be “Love-Thirty” (note that there is a convention to always announce the score of the person serving first). For the following scoreboard Alice 0 1 0 S> Betty 0 0 0 it must be the case that Alice just won a game, so the callout would be “Game: Alice”. Note that it is not always possible to determine a callout by looking at the scoreboard, such as the following situation: S> Alice 0 1 0 Betty 0 1 0 There are two possibilities: Either Alice won before Betty or Betty won before Alice, and we don’t know which one holds. However knowing the history of the points won enables us to make the correct callout, and the scoreboard is also determined by the history of the points won. 7 Specification The specification for this assignment includes this document, the online Javadoc, and any “official” clarifications announced on Piazza. Where’s the main() method? There isn’t one! Like most Java classes, this isn’t a complete program and you can’t “run” it by itself. It’s just a single class, that is, the definition for a type of object that might be part of a larger system. To try out your class, you can write a test class with a main method like the examples below in the getting started section. There will also be an automated test suite running on Gradescope for this assignment, which will perform a lot of functional tests, but when you are developing and debugging your code at first you’ll always want to have some simple test cases of your own, as in the getting started section below. Suggestions for getting started Smart developers don’t try to write all the code and then try to find dozens of errors all at once; they work incrementally and test every new feature as it’s written. Here is example of some incremental steps you could take in writing this class. • Create a new, empty project and then add a package called hw2. Be sure to choose “Don’t Create” at the dialog that asks whether you want to create module-info.java. • Create a package named hw2. Download the skeleton code version of Tennis.java and copy it into your project. The easiest way to do this is by drag-and-dropping the file into src/hw2 in Eclipse. • At this point, the Tennis class will not even compile. Getting the code to compile should be your top priority. While reading the javadoc, add stubs for all the required methods and the constructor. Document each one. For methods that need to return a value, just return a “dummy” value (e.g., 0 or false) as a placeholder for now. Continue until there are no compile errors in the project. At this point your code should pass all the tests that begin with testL0. • Try a very simple test like this: 8 public class SimpleTests { public static void main(String[] args) { Tennis game = new Tennis(“Alice”, “Betty”, false, false, false); System.out.println(game); } } You should see an output string similar to this, produced by the toString() method: S> Alice 0 0 0 Betty 0 0 0 Note that in printing the variable game, the println method automatically invokes the method game.toString(). The toString method just calls your other accessor methods to get the values to put in the string. • Think about the constructor specified in the javadoc. They need to “memorize” the names of the players (we recommend Alice and Betty or Allan and Bobby). The constructors also need to specify three parameters which determine what kind of tennis match is being played. – isBestOfFive is a boolean which, if true, means we are playing a best-of-five sets match, and if false, means we are playing a best of three sets match. This has implications for how many sets one needs to win in order to win the match. – isPlayingTiebreaks is a boolean which determines whether we are using the Advantage system in which one must win a set by two games, or the Tiebreak system in which we play a tiebreak game if the score gets to 6-6. – isGrandSlam is a boolean which only has an effect when isPlayingTiebreaks is true, and in that case it determines whether the final game of the final set needs 7 points to win, or at least 10. If true, we need 10 sets to win the final set of a grand slam game. Otherwise we need only 7. These booleans should be stored in your class. Make sure playerA always serves first in any match (this is a rather arbitrary choice which holds for this assignment but not in real life). 9 • Next you could think about counting the sets, games and points. You’ll need three instance variables for these three values, per player, and their values (or a string that depends on their value) should be returned by the corresponding accessor methods: – public int getPlayerASets() – public int getPlayerAGames() – public int getPlayerAScore() and a similar set of methods for playerB. Remember that accessor methods never modify instance variables, they only observe them and return information. You’ll also need a method getPlayerAServing() which returns a boolean which is true when playerA is serving next. • The mutator methods for this project are – public void winPoint(boolean playerAWins) – public void winGame(boolean playerAWins) – public void winSet(boolean playerAWins) These cause the scores to change according to the rules discussed above. • Familiarize yourself with the naming system for tests. The test names begin with the prefix testLN where N is 0, 1, 2, 3 or 4. This is followed by three letters that are either T or F, and the first one indicates true or false for isBestOfFive, the second one isPlayingTiebreaks and the third one isGrandSlam. Finally there is a number (optionally followed by a letter) for distinguishing tests. – testL0 tests have to do with checking that you got the structure of the class correct, including the public method names and access modifiers, and just ensuring that your code compiles. – testL1 tests check that your code can count sets correctly and determine the winner of the match based on tracking sets alone. – testL2 tests have to do with checking that your code can count games correctly and use them to decide correctly when a set has been won, under the Advantage system. If a set has been won one needs to also determine whether the match has been won. Your code should not need to handle any tiebreaking rules in order to pass the testL2 tests. 10 – testL3 tests have to do with checking that your code can count points correctly within a non-tiebreaking game, and use them to decide correctly when a game has been won, and if so, whether a set has been won, and if so, whether the match has been won. – testL4 tests introduce the concept of tiebreaking, and require your winGame and winSet methods to become aware of what tiebreaking means, and when to use tiebreaking. It also introduces the concept of a Grand Slam. This just allows your code to be aware of whether a grand slam match is being played and if so, correctly handle the final game in the final set according to the rules for grand slam tiebreaking. • Writing your own tests and using TDD is a great idea, however we are not requiring you to submit a file containing your tests. Three methods have been provided in the skeleton file to make testing easier for you. – runSets(“a”); – runGames(“abb”); – runPoints(“abab”); The argument to each of these is a string containing lowercase a’s and b’s, each of which indicates which player (playerA or playerB) won the corresponding unit of play. For example, the call to runSets with an argument of “a” means playerA won a set. The call to runGames with an argument of “abb” means that playerA won the first game, and the next two games were won by playerB. Finally, the call to runPoints with the argument “abab” means that playerA won a point, then playerB won the next point, then playerA won the third point, and playerB the fourth. It is easy to set up a scenario in a tennis match by calling runSets with a suitable argument, then calling runGames to reflect the situation in a set, and then calling runPoints to create a scoreline. Then you can call getCallOut() and toString() to see whether they print what you expect the score to be. • First implement the winSet method, and then test your code, and then run your code on the autograder to verify that you’re passing all the testL1 tests. The winSet method should adjust the values of the scores. It should also determine whether the match has been won, and this condition will depend on whether it is a best-of-three sets match or a best-of-five sets match. One more thing to look out for is to make 11 sure the generated callout says “Game and Set: playerName” if the match has not be won, but says “Game, Set and Match: playerName” when the match has been won. • Next, implement the winGame method (assuming that tiebreaks do not exist), and then run your code on the autograder to verify that you’re passing all the testL1 and testL2 tests. The winGame method should adjust the values of the scores, and determine whether the set has been won. Pay attention to the rules for winning a set when we are playing Advantage Sets (but not Tiebreaker Sets). The winGame method should also change the indication of who is serving next. Finally it should generate a callout which says the game has been won, like “Game: playerName”, but it should only do so if winning the game in this particular case does not mean the set has been won. This is because if the set has been won, winSet will generate a more informative message. • Next, implement the winPoint method, and then run your code on the autograder to verify that you’re passing all the testL1, testL2 and testL3 tests. Obviously the winPoint method should change the scores, and then check whether the game has been won. It should also generate callouts, stating the score of the server first, unless the game is a tiebreaker, in which case a different callout system is used. • Fourth, we want to introduce the concept of tiebreaks. We need to include code in winGame that detects when a tiebreak should be played (whether the next game should be a tiebreaker). A tiebreaker should be played when the score is 6-6 and the boolean isPlayingTiebreaks is true. Then while playing a tiebreak game, one must win by attaining 7 points with a leading margin of 2, unless it is the final game of a grand slam, in which case one must win by attaining 10 points with a leading margin of 2. When a tiebreak game is being played, a few things work differently, such has how the scores are called (using normal numbers instead of nonconsecutive numbers), and also the fact that the serving player changes every two points, with the exception that the starting server serves only one point. That is, if player B serves first, then the service order will be: B A A B B A A B B A A . . . and so on. And if A serves first, then the service order will be 12 A B B A A B B . . . and so on. Also the conditions for winning a tiebreak game are different from those of a normal game. Please note that the alternation of the person serving during a tiebreaker game does not in any way affect the person who starts serving the game after the tiebreaker. If one player serves first in the tiebreaker, the other player should serve first in the game following the tiebreaker, regardless of what happens during the tiebreaker. Also for the purposes of this assignment, assume that the person serving is never changed by calling winSet. That is, if we assume someone won a set by directly calling winSet, we are effectively assuming that they won the set with an even number of games played in that set, so that the set does not change who is serving. • In all cases when a match has been won, the class should “lock up” and refuse to make any further changes to the scores. After the match is won, the three methods winPoint, winGame and winSet should not have any effect. Requirements The requirements for the class are embodied in the public API, so it is not mandatory that you use the ideas above. But they could be very helpful! And, of course, if you end up with a lot of unnecessarily duplicated code the grader may take off some points for style. The autograder will be available on Gradescope. There are many test cases so there may be an overwhelming number of error messages. Always start reading the errors at the top and make incremental corrections in the code to fix them. More about grading This is a “regular” assignment so we are going to read your code. Your score will be based partly (about two thirds) on the autograder’s functional tests and partly on the TA’s assessment of the quality of your code. This means you can get partial credit even if you have errors, and it also means that even if you pass all the autograder tests you can still lose points. Are you doing things in a simple and direct way that makes sense? Are you defining redundant instance variables? 13 General principles to observe: • Use instance variables only for the “permanent” state of the object, use local variables for temporary calculations within methods. • You will lose points for having unnecessary instance variables • All instance variables should be private. • Accessor methods should not modify instance variables. See the “Style and documentation” section below for additional guidelines. We reserve the right to add more tests by the autograder other than the ones you see before the deadline. Restrictions on Java Features For this Assignment There are no restrictions on the Java features you can use to implement this assignment, except that you may not write any loops, and you may not write more than the one class specified in the javadoc. Also, see above the above section about using good programming practices. You may not use any outside libraries (i.e., external libraries such as Apache Commons; otherwise, we won’t be able to compile your code when grading. Style and documentation Roughly 15% of the points will be for documentation and code style. Here are some general requirements and guidelines: • Each class, method, constructor and instance variable, whether public or private, must have a meaningful javadoc comment. The javadoc for the class itself can be very brief, but must include the @author tag. The javadoc for methods must include @param and @return tags as appropriate. • Try to briefly state what each method does in your own words. There is no rule against copying the descriptions from the online documentation. However: do not literally copy and paste from this pdf! This leads to all kinds of weird bugs due to the potential for sophisticated document formats like Word and pdf to contain invisible characters. 14 • Run the javadoc tool and see what your documentation looks like! (You do not have to turn in the generated html, but at least it provides some satisfaction 🙂 All variable names must be meaningful (i.e., named for the value they store). Your code should not be producing console output. You may add println statements when debugging, but you need to remove them before submitting the code. Internal (//-style) comments are normally used inside of method bodies to explain how something works, while the Javadoc comments explain what a method does. (A good rule of thumb is: if you had to think for a few minutes to figure out how something works, you should probably include an internal comment explaining how it works.) • Internal comments always precede the code they describe and are indented to the same level. • Use a consistent style for indentation and formatting. • Note that you can set up Eclipse with the formatting style you prefer and then use Ctrl-Shift-F to format your code. To play with the formatting preferences, go to Window>Preferences->Java->Code Style- >Formatter and click the New button to create your own “profile” for formatting. If you have questions For questions, please see the Piazza Q&A pages and click on the folder hw2. If you don’t find your question answered, then create a new post with your question. Try to state the question or topic clearly in the title of your post, and attach the tag hw2. But remember, do not post any source code for the classes that are to be turned in. It is fine to post source code for general Java examples that are not being turned in. (In the Piazza editor, use the button labeled “pre” to have Java code formatted the way you typed it.) If you have a question that absolutely cannot be asked without showing part of your source code, make the post “private” so that only the instructors and TAs can see it. Be sure you have stated a specific question; vague requests of the form “read all my code and tell me what’s wrong with it” will generally be ignored. Of course, the instructors and TAs are always available to help you. See the Office Hours section of the syllabus to find a time that is convenient for you. We do our best to answer every question carefully, 15 short of actually writing your code for you, but it would be unfair for the staff to fully review your assignment in detail before it is turned in. Any announcements from the instructors on Piazza are considered to be part of the official spec, and you may lose points if you ignore them. Such posts will always be sent as an announcement on Piazza. (We promise that no official clarifications will be posted within 24 hours of the early due date.) What to turn in Note: You will need to complete the “Academic Dishonesty policy questionnaire,” found on the Assignments page on Canvas, before you are given credit for this assignment. Please submit, on Gradescope, just the Tennis.java file.
The aim of this lab is to implement the reduction algorithm we learned in class. You are required to write a full CUDA program to compute the sum of a 1D float array with 224 elements. In this assignment, you need to implement and time four versions of the kernel that will do the reduction: • Version (1) uses the shared memory but has more divergence within the warps. This version is similar to the example on page 46 in the lecture notes “05G_CUDA_BestPractices”. • Version (2) uses the shared memory and has less divergence. This is similar to the example on page 49 in the lecture notes. • Version (3) is similar to version (1) but it does not use the shared memory (writes directly to the global memory). • Version (4) is similar to version (2) but it does not use the shared memory. In the host code (the main function), create a 1D array with 2 24 random float numbers from 0 to 255. Then, launch each of the above four kernels, one at a time. The output should similar to one below: Reducing an array of 16777216 floats on a grid of(32768,1,1) blocks, each block with (512,1,1) threads Using shared memory, More divergence: GPU time: 227.364 ms GPU sum: 2139115520.00 Using shared memory, Less divergence: GPU time: 37.777 ms GPU sum: 2139115520.00 Using global memory, More divergence: GPU time: 234.256 ms GPU sum: 2139115520.00 Using global memory, Less divergence: GPU time: 45.022 ms GPU sum: 2139115520.00 In addition, choose any of the four kernels and compare its execution time: (i) once using the ‘multiplication’ operator (*) to compute the ‘stride’, and (ii) another time using the ‘shift’ operator (
The purpose of this assignment is to give you some practice with the process of implementing a class from a specification and testing whether your implementation conforms to the specification. You’ll also get some practice with modular arithmetic.For this assignment you will implement one class, called Printer, that models pages being printed from a simple printer. The printer has a paper tray that can hold up to some maximum number of sheets of paper. The tray can be removed (in which case there are no sheets of paper available for printing) and replaced (making the sheets available for printing). Paper can be removed from and added to the tray. The printer receives a print job that is associated with a document of n pages, where the number n is specified by calling the method startPrintJob. Pages are numbered 0 through (n-1). Each time a page is printed the printer advanced by one page in the document. The print job is “circular”, in the sense that after page (n-1) is printed the printer begins printing another copy of the document starting at page 0. The basic operation of the printer is provided by the method printPage, whose behavior is:At any time, the paper tray may be removed from the printer. Doing so makes the sheets available to the printer zero. The sheets available may also be zero when the sheets in the tray run out. When this is the case printPage should print no pages and should not advance to the next page.You are not allowed to use conditional statements in this homework. That meansspecifically you will lose some manual grading points if you use “if” or “if-else” statements, loops of any sort, or ternary operators (don’t worry if you don’t know what those are yet). But why? The purpose of this assignment is to give you practice using variables and mathematical expressions. Wouldn’t it be just as easy to use conditionals to solve this particular assignment? Perhaps, but that won’t always be the case. Professional programmers use mathematical expression every day to simplify code, make it more readable, and make it more efficient. You’re not ready yet to write code for the Linux kernel or the InnoDB database engine or the javac compiler… So, we decided to give you an easier programming assignment and artificially tie your hands (so to speak) by forcing you to implement the logic with only variables and mathematical expressions. Some day when you are adding a patch to the Linux kernel you might thank us for the practice. Hints: To solve this assignment you will need to declare instance and local variables, that part of the program design is up to you. There will be a couple of places where you need to choose the larger or smaller of two numbers, which can be done with the methods Math.max() or Math.min(). For example, the Printer has a minimum and maximum allowable number of pages in the tray, from empty to full. These functions can be used to enforce the tray capacity boundaries if needed. For the wrapping (circular) behavior, you can use the mod (%) operator. Yes, it is possible to solve this assignment very neatly with just what we have learned so far in class, and the challenge of doing so will make you a better programmer! You will be penalized slightly for using conditional statements, keep in mind that if you really can’t figure it out, it’s better to turn in something working than nothing at all.This is a “regular” assignment so we are going to read your code. Your score will be based partly (about 2/3) on Gradescope’s functional tests and partly on the TA’s assessment of the quality of your code. This means you can get partial credit even if you have errors, but it also means that even if you pass all the Gradescope tests you can still lose points. Are you doing things in a simple and direct way that makes sense? Are you defining redundant instance variables? Are you using a conditional statement when you could just be using Math.min? Are you using a loop for something that can be done with integer division? Some specific criteria that are important for this assignment are:See the “Style and documentation” section below for additional guidelines.Roughly 15% of the points will be for documentation and code style. Here are some general requirements and guidelines:A significant portion (but not all) of the points for this assignment are based on the gradescope autograder tests. It is not advised to wait until the last day to run the gradescope on your code. You have an unlimited number of submissions, and unless we receive complaints from gradescope, we will not restrict the rate at which you can submit.Do not try to “cheat” the tests by “hardcoding” your code to pass specific tests. You are expected to implement a solution that meets the specifications described in this document, the tests are only provided to gain confidence that your solution is correct. We reserve the right to add new “hidden” tests during grading and the graders will look for “hardcoding” during the manual part of the grading.You can find the autograder for this Assignment on gradescope. Please see the last section of this document for more information on how to submit to Gradescope.The specification for this assignment includes this pdf along with any “official” clarifications announced on Canvas.There is one public constructor: public Printer(int trayCapacity)Constructs a new printer with the given maximum tray capacity of the number of paper sheets it can hold. Initially the tray is empty and the printer has not printed any pages.There are the following public methods: public void startPrintJob(int documentPages)Starts a new print job to make copies of a document that is a specified page length (documentPages). Updates the next page to print as page 0 (denotes the first page of the document). public int getSheetsAvailable()Returns the number of sheets available for printing. public int getNextPage()Returns the next page number of the document that will be printed. public int getTotalPages()Returns the count of all pages printed by the printer since its construction. public void printPage()Simulates the printer printing a page. The number pages printed is either one or zero depending on whether there is at least one sheet of paper available to the printer. Increments the total page count of the printer by the number of pages printed. Advances the next page to print by the number of pages printed (possibly wrapping around to page zero). The number of pages available to the printer and in the tray are also updated accordingly. public void removeTray()Removes the paper tray from the printer; that is, makes the sheets available to the printer zero. public void replaceTray()Replaces the tray in the printer; that is, makes the sheets available to the printer the same as the number of sheets in the tray. public void addPaper(int sheets)Simulates removing the tray, adding the given number of sheets (up to the maximum capacity of the tray), and replacing the tray in the printer. public void removePaper(int sheets)Simulates removing the tray, removing the given number of sheets (but not allowing the sheets to go below zero), and replacing the tray in the printer.There isn’t one! Like most Java classes, this isn’t a complete program and you can’t “run” it by itself. It’s just a single class, that is, the definition for a type of object that might be part of a larger system. To try out your class, you can write a test class with a main method like the examples below in the getting started section.Gradescope (see below) will perform a lot of functional tests, but when you are developing and debugging your code at first you’ll always want to have some simple test cases of your own (for example in a file you can create called PrinterTests.java), as in the getting started section below.Smart developers don’t try to write all the code and then try to find dozens of errors all at once; they work incrementally and test every new feature as it’s written. Since this is our first assignment, here is an example of some incremental steps you could take in writing this class. public static void main(String[] args) { // create a printer Printer p = new Printer(100); System.out.println(p.getSheetsAvailable()); System.out.println(“Expected 0”); p.addPaper(1); System.out.println(p.getSheetsAvailable()); System.out.println(“Expected 1”); }(Tip: you can find code for the simple test case above, along with the others discussed in this section, in the class SimpleTests.java linked from the assignment page on Canvas.) Printer p = new Printer(100);p.startPrintJob(5); System.out.println(p.getNextPage()); System.out.println(“Expected 0”); Printer p = new Printer(100); p.addPaper(1); p.startPrintJob(5); p.printPage(); System.out.println(p.getNextPage()); System.out.println(“Expected 1”); System.out.println(p.getTotalPages()); System.out.println(“Expected 1”); Printer p = new Printer(100); p.addPaper (1); p.startPrintJob(5); p.printPage(); // try to print a page with no paper available p.printPage(); System.out.println(p.getTotalPages()); System.out.println(“Expected 1”); // add paper and try to print again p.addPaper(200); System.out.println(p.getSheetsAvailable()); System.out.println(“Expected 100”); p.printPage(); System.out.println(p.getTotalPages()); System.out.println(“Expected 2”); System.out.println(p.getNextPage()); System.out.println(“Expected 2”);For questions, please see the Piazza Q & A pages and click on the folder hw1. If you don’t find your question answered, then create a new post with your question. Try to state the question or topic clearly in the title of your post, and attach the tag hw1. But remember, do not post any source code for the classes that are to be turned in. It is fine to post source code for general Java examples that are not being turned in. (In the Piazza editor, use the button labeled “pre” to have Java code formatted the way you typed it.)If you have a question that absolutely cannot be asked without showing part of your source code, make the post “private” so that only the instructors and TAs can see it. Be sure you have stated a specific question; vague requests of the form “read all my code and tell me what’s wrong with it” will generally be ignored.Of course, the instructors and TAs are always available to help you. See the Office Hours section of the syllabus to find a time that is convenient for you. We do our best to answer every question carefully, short of actually writing your code for you, but it would be unfair for the staff to fully review your assignment in detail before it is turned in.Any announcements from the instructors on Canvas that are labeled “Official Clarification” are considered to be part of the spec, and you may lose points if you ignore them. Such posts will always be posted in the Announcements section of Piazza (and emailed directly to you). (We promise that no official clarifications will be posted within 24 hours of the due date.)Note: You will need to complete the “Academic Dishonesty policy questionnaire,” found on the Assignments page on Canvas, before the submission link will be visible to you. Assignments are turned in by Gradescope, there is nothing to submit on Canvas. The assignment will be called “Assignment 1” on Gradescope, and will have a deadline of 20th September for normal submission and 22nd September for a late penalty. It will run a number of functional tests and report how many (and which) tests your code passed. There are many test cases so there may be an overwhelming number of error messages. Always start reading the errors at the top and make incremental corrections in the code to fix them. Please submit just the file called Printer.java, and at the top, there should be a line that puts it in the hw1 package, that is, “package hw1;”. Do not create or submit any zipfiles with Gradescope even though gradescope may offer you the chance to submit a zipfile. Zipfiles created by speccheckers (just in case that is what you have) are not in the format that Gradescope expects. So just submit the Printer.java file as is, by itself. Please note that any 5% bonus for early submission or 10% penalty for late submission will not be calculated by Gradescope itself. Instead, it will be calculated by a separate script later. So you will only see your raw score once the Teaching Assistants have graded your work.
[10 marks] Repeat question Q1 from Assignment A3 using OpenMP parallel for loop(s). Check the output image to make sure your algorithm works correctly.Would it be better to use nested parallel for loops (i.e., to parallelize both for x and for y loops)? Test using your code and explain.Marking guide: +7 for code, +3 for the question about nested parallelismSearch online for information about how to do matrix multiplication, e.g., here.Include the following C statements near the beginning of your program (you may change the numbers).#define NRA 20 /* number of rows in A */#define NCA 30 /* number of columns in A = number of rows in B */#define NCB 10 /* number of columns in matrix B */Marking guide: +6 for correct code, +4 for proper parallelization (up to 4 marks may be deducted for not ‘reusing’ the same threads)a[0] = 0;for(i=1; i
Q1. [+3] Querying your GPU: In this question, you will run a simple query code to know the properties and limits of your NVIDIA card. Locate the “CUDA Samples” folder on your hard disk (e.g., c:ProgramDataNVIDIA CorporationCUDA Samples). Navigate to “1_UtilitiesdeviceQuery” subfolder. Then, Open the solution file (.sln) that matches your Visual Studio version. Once opened, compile and run project (Ctrl + F5). Then, capture your answers and submit them as an image file named A5_Q1.png. While the above sample project provide detailed information, a simpler code (with less information) is given below. Use the below code if you cannot find or run the CUDA sample project. Note: When creating a new project, make sure to choose CUDA template. The file extension for your CUDA program should be “cu”. Marking guide: +3 for a screenshot with the required info #include “cuda_runtime.h” #include “device_launch_parameters.h” #include int main(){ cudaDeviceProp prop; int count; cudaGetDeviceCount(&count); for (int i = 0; i < count; i++) { cudaGetDeviceProperties(&prop, i); printf(“—– General Information for device %d — ”, i); printf(“Name: %s ”, prop.name); printf(“Compute capability: %d.%d ”, prop.major, prop.minor); printf(“Clock rate: %d ”, prop.clockRate); printf(“Device copy overlap: “); printf(prop.deviceOverlap ? “Enabled ” : “Disabled ”); printf(“Kernel execution timeout: “); printf(prop.kernelExecTimeoutEnabled ? “Enabled ” : “Disabled ”); printf(“—– Memory Information for device %d — ”, i); printf(“Total global mem: %lu ”, prop.totalGlobalMem); printf(“Total constant Mem: %ld ”, prop.totalConstMem); printf(“Max mem pitch: %ld ”, prop.memPitch); printf(“Texture Alignment: %ld ”, prop.textureAlignment); printf(“—– MP Information for device %d — ”, i); printf(“Multiprocessor count: %d ”, prop.multiProcessorCount); printf(“Shared mem per mp: %ld ”, prop.sharedMemPerBlock); printf(“Registers per mp: %d ”, prop.regsPerBlock); printf(“Threads in warp: %d ”, prop.warpSize); printf(“Max threads per block: %d ”, prop.maxThreadsPerBlock); printf(“Max thread dimensions: (%d, %d, %d) ”, prop.maxThreadsDim[0], prop.maxThreadsDim[1], prop.maxThreadsDim[2]); printf(“Max grid dimensions: (%d, %d, %d) ”, prop.maxGridSize[0], prop.maxGridSize[1], prop.maxGridSize[2]); printf(“ ”); } return 0; } Q2. [+7] Simple CUDA code: consider this loop for initializing an array a: conts int n = 10000000; //10 millions for (i = 0; i < n; i++) a[i] = (double)i / n; Submit: a) The serial implementation running on the CPU. b) The CUDA implementation (1 thread per array element). Hint: Remember the limit on the number of threads per each CUDA block. In both cases, add code to print the first and last 5 elements of the array to verify your code. (not that you need to use the placeholder %.7f to print 7 digits after the decimal point. Sample output: a[0]: 0.0000000 a[1]: 0.0000001 a[2]: 0.0000002 a[3]: 0.0000003 a[4]: 0.0000004 … a[9999995]: 0.9999995 a[9999996]: 0.9999996 a[9999997]: 0.9999997 a[9999998]: 0.9999998 a[9999999]: 0.9999999 Marking guide: +2 for measuring the time of the parallel and serial code +2 for the kernel function +3 for launch configuration and properly calling the kernel Submission Instructions For this assignment, you need to do the following: 1- Compress the PNG file from Q1 and the source code file (i.e. the .cu file, not the whole project) from Q2 into one zip folder and give a name to the zipped file that matches your ID (e.g., 1234567.zip). 2- Submit the zipped file to Canvas. Note that you can resubmit an assignment, but the new submission overwrites the old submission and receives a new timestamp.
[10 marks] Download zip file from Canvas. Unzip and copy contents to a new C project. Read the “readme.txt” for copyright info and for some background about the library used. The first three statement in the main function define the input and output images and the required processing. Play with the values of these constants and check the output. Your goal is to reduce the processing time by dividing the workload among several threads (e.g., 4 threads) using OpenMP (but don’t use parallel for: i.e., neither #pragma omp parallel for nor #pragma omp for). To verify the correctness of your code, check the output image as well as the processing time (printed out in the console). Report the processing times for 2, 4, 8, 16 threads as a comment in your code. For both (a) and (b), compare the execution time of the parallel block using omp_get_wtime() which returns the number of seconds that have passed since some time in the past. For details on taking timings, see Section 2.6.4 of the textbook PACHECO-11. For this assignment, you need to do the following:Note that you can resubmit an assignment, but the new submission overwrites the old submission and receives a new timestamp. C command line arguments in EclipseThe omp_trap_1.c program in Q2 above requires passing an argument when running the program (see Usage in the comments part). In order to pass an argument, you can either use command line (i.e. the one in Usage), or you can do this in Eclipse IDE as seen below. Other IDEs usually have a similar way of passing arguments to the execution statement.
[12 marks] Write a C function that sequentially adds 2 vectors A and B as . Use this function header: void addVec(int* C, int* A, int* B, int size), where size is the number of elements in a vector. You should not create any additional local variables in the function (hint: use pointers and pointer expressions).Test your function with two vectors, each having 50 million integers, all initialized to 0 (hint: calloc). Note that memory allocation for A, B, and C is done within your test code (the main function). Print the first 10 elements of C as well as the total time the function took to complete. Report the results as a comment in your code.Sample run 1: (successful)0 0 0 0 0 0 0 0 0 0Execution time: 281.0 msSample run 2: (unsuccessful memory allocation)Not enough memory.Marking: +6 for the function, +5 for the test code (2 marks for error checking), +1 for the comment) Marking: +6 for the function (2 for error checking), +5 for the test code(2 for error checking), +1 for the comment Marking: +4 for running code int* vecCreate (int size)int* vecCreateOpenMP(int size, int num_thread)Here, you will try to speed up the vector initialization by dividing the work among several threads where each thread will initialize a segment of the vector. For example, if num_thread = 2 and size = 10, thread 0 will initialize elements 0 to 4 and thread 1 will initialize elements 5 to 9. Using #pragma omp parallel num_threads( num_thread ). Your code should be similar to Version1 of the Trapezoid Area Calculation example from the lecture notes. Your function should only work if the vector size is divisible by the number of threads. If not, your function should display an error message and return NULL. Test both functions with a 50-million element vector (and 4 threads for the second function). Your test code should print the value of the last element in the vector along with the time taken for each function to complete. Report the results as a comment in your code.Sample run 1: (successful)Using serial codev[49999999] = 49999999Time: 144.00 ms Using OpenMP with 4 threads:v[49999999] = 49999999Time: 59.00 ms Sample run 2: (num_thread not divisible by size)Using serial codev[49999999] = 49999999Time: 144.00 ms Using OpenMP with 3 threads: Error: number of threads must be divisible by vector size. Sample run 3: (unsuccessful memory allocation)Not enough memory.Not enough memory.Marking: +5 for serial code, +10 for parallel code, +5 for the test code. Up to -4 marks for not handling errors. For this assignment, you need to do the following:Note that you can resubmit an assignment, but the new submission overwrites the old submission and receives a new timestamp.
The objective of the assignment is to: (1) explore advanced data structures, and (2) benchmark algorithms. Consider the list of advanced data structures provided at https://iq.opengenus.org/list-ofadvanced-data-structures/, and https://www.geeksforgeeks.org/advanced-data-structures/ and at https://en.wikipedia.org/wiki/List_of_data_structures. Other considerable advanced data structures could be Fibonacci Heaps, Van Emde Boas Priority Queues, Dynamic Data Structures for Graph Connectivity/Reachability, Splay Trees/Suffix Trees/Tries. And Persistent Data Structures. Section V of the Introduction to Algorithms book, 3rd edition, by Cormen, Leiserson, Rivest, and Stein (available online and free through UBC Library) contains explanations of four advanced data structures that can be helpful. Select 3 comparable advanced data structures. Submission To complete the assignment, submit the following: 1. A concise pdf report including o Explanation of the selected data structure briefly and their potential applications, o The time and space computational complexity of your data structures, o A table summarizing the measured performance, o Plots showing the run time complexity for large enough data. You can generate synthetic dataset using Python functions. Aim for at least ten million data points. Then, run your program with different implementations and compare their run time in a plot. Include this analysis in your pdf file and explain if it supports your analysis. If the plots contradict your analysis, analyze them carefully: double check your implementation and review your analysis, provide justifications, and explain your thoughts of why this is happening. Remember to upload your dataset on the web and include a link to the dataset in the pdf file. o An explanation of why you selected those data structures (what attracted them; this is totally subjective and personal).Use appropriate parameters to describe the complexity. You need to justify the complexity briefly; and explain each parameters used and provide the formula with appropriate references. 2. Python code comparing the data structures selected. You are responsible for generating appropriate data sets for the performance profile. Provide any justification of your choices in the report. Do not hesitate to contact the instructor (a quick email can save you hours for misguided work!). Add the GitHub link of your implementations in the pdf file. As for Assignment 1, your code should o Be well documented and clean. o Include unit tests. o follow common practises: ▪ appropriate class/variable/method names (not too long and meaningful), ▪ appropriate comments ▪ comments for each method should indicate input, output, and a short explanation of the method ▪ clear setup and running instructions. How to submit: Submit your PDF file to Canvas, which should also include the links to your GH repository and the dataset you used for testing. Use the Association for Computing Machinery (ACM) – Small Standard Format Template (Overleaf) for your report. Remove the ACM, journal, and copyright information. The report should be between 5-10 pages, including plots and references. Usage of GenAI: The use of GenAI is discouraged. However, if you still decide to use online sources or GenAI to generate your code, first, make sure it is correct and executable. Second, make sure to include the resources you have used and/or mention that you used GenAI in your report. There is no penalty of using available code, the only drawback can be that you might not be engaged as writing the code yourself for your future references. Grading rubric Weights SubtotalsReport 30 Explanation of the data structures and applications/usage 10 Complexity analysis 10 Plots and comparisons 8 References 2 Code static 30 naming 5 comments 5 running instructions 5 code design 15 Code execution 30 syntax-error free, runs 10 unit tests run 10 convincing demo 5 performance 5 Cross-Check** 10Examining and running one of your classmate’s assignment and grade it based on the above criteria. It will be assigned to you by the instructor. 10 Total 100 100 **Cross-Check needs to be submitted within one week of the assignment submission deadline. Other than just checking, use it as a learning opportunity. Include a rationale and degradation feedback and submit it through email to the instructor: [email protected].
The objective of the assignment is to: (1) review hash tables, (2) explore advanced data structures, and (3) numerically compare the algorithms. The login checker problem is to quickly check that a login name has not been already taken so that all logins are unique. Assume you have millions of logins (aka usernames), and a user creates a new account. You need to ensure the new login is not a duplicate of an existing one. Using your existing knowledge of algorithms and data structures you can 1. store all logins in a list, and check existence using linear search; 2. store all logins in a sorted array, and check existence using binary search; 3. store logins in a hash table, and check existence by hashing. The assignment explores 2 more advanced data structures that scale better than the above. Assume the number of logins is n=1 billion (you may use a smaller value of n depending on your computer memory and speed as long as you justify the value of n used to validate your approach). • Read about bloom filters and look at examples. • Read about Cuckoo filters and how they compare to Bloom filters. Submission To complete the assignment, submit the following: 1. A concise pdf file listing the time and space computational complexity of: linear search, binary search, hashing, Bloom filter, and Cuckoo filter. Use appropriate parameters to describe the complexity, e.g., Bloom filter uses n (estimated number of elements/logins), m (bit array of m bits), and k (number of hash functions). You need to justify the complexity; explain each parameters used and provide the formula with appropriate references. 2. Plots showing the run time complexity for large enough data. Aim for 1 billion (you may use a smaller value of n depending on your computer memory and speed as long as youjustify the value of n used to validate your approach). You can generate strings dataset using synthesized functions. Then, run your program with different implementations using linear search, binary search, hashing, Bloom filter, Cuckoo filter, and compare their run time in a plot. Include this analysis in your pdf file and explain if it supports your analysis. Remember to upload your dataset on the web and include a link to the dataset in the pdf file. 3. Python code comparing the hashing, Bloom filter, and Cuckoo filter. Add the link of your GitHub repository for this assignment to the pdf file. Your code should o Be well documented and clean. o Include unit tests. o follow common practises: ▪ appropriate class/variable/method names (not too long and meaningful), ▪ appropriate comments ▪ comments for each method should indicate input, output, and a short explanation of the method ▪ clear setup and running instructions. How to submit: Submit your PDF file to Canvas, which should also include the links to your GH repository and the dataset you used for testing. Use the Association for Computing Machinery (ACM) – Small Standard Format Template (Overleaf) for your report. Remove the ACM, journal, and copyright information. The report should be between 5-10 pages, including plots and references. Usage of GenAI: The use of GenAI is discouraged. However, if you still decide to use online sources or GenAI to generate your code, first, make sure it is correct and executable. Second, make sure to include the resources you have used and/or mention that you used GenAI in your report. There is no penalty of using available code, the only drawback can be that you might not be engaged as writing the code yourself for your future references. Grading rubric Weights SubtotalsReport 20 Complexity analysis 10 Comparisons 8 References 2 Code static 35 naming 5 comments 10 running instructions 5 code design 15 Code execution 35 syntax-error free, runs 10 unit tests run 5 convincing demo 5 performance 5 comparison of the data structures (item 2 in the above list) 10 Cross-Check ** 10Examining and running one of your classmate’s assignment and grade it based on the above criteria. It will be assigned to you by the instructor. 10 Total 100 100 **Cross-Check needs to be submitted within one week of the assignment submission deadline. Other than just checking, use it as a learning opportunity. Include a rationale and degradation feedback and submit it through email to the instructor: [email protected]. Bonus Extra points are 15% of your assignment mark and are added to the assignment grade. 1. Suggest an alternative competitive method; explain its data structure, how it works, and its complexity with appropriate reference. Note that receiving the bonus mark depends on the approval of instructor [15% bonus]. 2. Discuss your alternative method with the instructor, and if the instructor considers your method competitive, implement it and benchmark it vs. Bloom and Cuckoo [15% bonus].
For this assignment, you will need to understand components, props, JSX, state, and HTTP requests. Barstool Archive Erika Nardini from Barstool Sports wants to make a throwback site from late 2020/early 2021. Your goal is to display a few of the articles in a list for some of the readers of the website to reference. You will find the data here: https://www.jalirani.com/files/barstool.json Requirements Your job is grab this remote article data via a HTTP request and display these articles in a list. Each article needs to have: • An article title (this should be clickable and take the user to the article on the actual Barstool Sport’s website) • The article thumbnail/image • The author • The author’s avatar/image • The number of comments for the article Use the small thumbnail image (this must render nicely). A few of the articles have a .gif for a thumbnail 1 Figure 1: Example Article Notes • Your website does not need to minic my screenshot, it just needs to have the data mentioned above. • All five items needed for each article is contained inside of the JSON objects. • *Wink Wink* For article thumbnail it is image.location + image.thumbnail.small (the url is broken up into two parts) • Test the data in your browser to ensure it works. i.e. copy and paste image.location + image.thumbnail.small and put it in the address bar in your browser to ensure you can see an image. • If the article thumbnail/image has a .gif instead of a .png/.jpg you can look at this article for guidance ttps://stackoverflow.com/questions/44371716/addanimated-gifs-to-react-web-apps or I will allow you to substitute it for an image of your choice since we don’t cover how to display .gif’s (even though it’s easy, just try it). • Here is a simple example of a HTTP request in React: https://jasonwatmore.com/post/2020/07/17/react-axios-http-get-requestexamples • Don’t worry about adding CSS, fonts, etc. Just focus on displaying the five items for each article listed above. Submission Please submit the following on Blackboard: • barstool.zip
The goal of this project is to integrate multiple topics in the course to create a web scraper. If you use the ES6 import statement instead of the CommonJS require for node modules taught during lecture, you will lose 10%. Specifications For this assignment, you will need to understand the requests/Axios, cheerio, and nodemailer modules to parse an HTML webpage and email specific parts to an end-user. Artist Email-Scraper Create a file called artists.js (or a node project) that will scrape the provided url: http://www.popvortex.com/music/charts/top-rap-songs.php and send an email of all artists & songs that are sung by the specified artists given via the command line. Requirements: • You must read in the ‘from‘, ‘to‘, ‘sender email‘, and ‘sender password‘ from the credentials.json file. This does not need to be submitted in Bb, but when grading, I should be able put in my own credentials.json file and should run smoothly. You will lose points you do not use the correct JSON keys or if it does not read the values from credentials.json • The specified artists must be read in via the command line • If no artist(s) are specified do not send an email • If the specified artist(s) are not found on the website, do not send an email • If the specified artist(s) are found on the website: – Send an email from an email account of your choice, to an email account of your choice (when I am testing this, I will input my own accounts for this portion) 1 – The subject will be: “Your artist(s) are: ” followed by a list of the artist(s). Be sure to format this portion correctly i.e. if the user specifies node artists Drake Migos xxxtentacion your subject should be: Your artists are: Migos, Drake, and xxxtentacion – The email format should be the artist in bold and the song name in italics. Features may be in the song name, so that is fine to leave artists that are featured there, see below 2 Things to note: • Be careful when making too many requests to a website, there is a possibility of being rate-limited • Only worry about the top 25 songs, the website is dynamic and sometimes has more or less songs depending on the day. • Don’t worry about case, it’s up to the user to ensure spelling and proper casing • Don’t worry about artists that have more than one word in their name i.e. Cardi B and Post Malone. Although we love them, it makes it tricky when reading from the command line • If the artist is included as a feature, please include that as a song i.e. if searching for Migos, please include the track – Gucci Mane: I Get The Bag ft. Migos • Feel free to create a test Gmail account as a sender, it makes life much easier just so you don’t have to fiddle with your security settings • Remember to enable 2-factor for the email, generate an app password (name it whatever you’d like), and use that app password as the sender password in your file Submission Please submit the following on Blackboard: • artists.js 3 Figure 1: example credentials.json being read in Figure 2: For Input: node artists.js DaBaby Drake Figure 3: If no artist is specified
