(A) In the first part of this assignment you will investigate the claim in Theorem 12.4 that a randomly built binary search tree on n distinct keys has expected height O(log n).In addition, you will investigate the time taken to build and destroy binary search trees. (i) Code up the Tree-Insert and Tree-Delete algorithms from Chapter 12 of the textbook (in C, C++ or Java).(ii) Run experiments to build binary search trees from randomly shuffled lists of keys by repeatedly calling Tree-Insert. Record the height of each tree built. Run experiments for different values of n (the number of keys) to illustrate the asymptotic growth of the height as n increases. To get the ‘expected height’ of a randomly built binary search tree, repeat the experiment a number of times for each value of n and take the average height. Plot the growth of the avergae height of the randomly built binary search trees.(iii) For each binary search tree constructed in part (ii), record also the time taken to build the tree and plot your results on a graph. (iv) For each binary search tree constructed in part (ii), destroy the tree by repeatedly calling Tree-Delete on the root node, until the tree is empty. Record the time taken to destroy the binary search trees and plot your results on a graph.(B) In the second part of this assignment, you will code up the operations on an order-statistic tree. The order-statistic trees will be based on binary search trees (not Red-Black Trees). (i) Code up the Tree-Insert, Tree-Delete, OS-Search and OS-rank algorithms on a binary search tree whose nodes are augmented with the size attribute. (Use C, C++ or Java.) Make sure your Tree-Insert and Tree-Delete algorithms maintain the size attribute of all nodes in the tree. Part of your assignment is to explain the changes to Tree-Insert and Tree-Delete that are required to maintain the size attribute of the nodes.Note that there are some small changes required to OS-Search and OS-rank in the textbook since the tree is not a Red-Black tree.You must submit the following to the AA Moodle page by Sunday 6 October at 23h00: (1) Your source code for all the algorithms in (A) and (B) (coded in C, C++ or Java). (2) A document with: (i) all the graphs required in (A) and a description of how the graphs were obtained (range of dimensions, key values, number of trees of each size, etc.). (ii) An explanation, using pseudocode and sentences, of the changes to Tree-Insert and Tree-Delete that are required to maintain the size attribute of the nodes.
Your assignment is to code up the three different algorithms for square matrix multiplication that are described in Chapter 4 of the textbook (3rd edition) and to run simulations of your algorithms to get empirical evidence for the asymptotic running time of each algorithm.The three algorithms are: (1) Square-Matrix-Multiply on page 75 (running time Θ(n 3 )). (2) Square-Matrix-Multiply-Recursive on page 77 (running time Θ(n 3 )). (3) Strassens-Method as described on pages 79 – 82 (running time Θ(n 2.81)).The algorithms must be coded in either Java, C, or C++. The algorithms must be coded from scratch and should not use any packages. You must test your algorithms on square input matrices over a range of different dimensions. The run-times of the algorithms on each of the inputs should be recorded.The results must be plotted on graphs. Choose a good range of values for the dimensions of the input matrices so that the graphs clearly illustrate the asymptotic growth of the algorithms’ running times. Don’t use only matrices with dimension 2k . (See Exercise 4.2-3 for how to deal with other dimensions).For each matrix dimension that you use, you should run your algorithm on a number of randomly generated matrices of that dimension and then take the average running time over these matrices.You must submit the following: (1) Your source code for the three algorithms (using Java, C or C++). (2) A document with the following: (i) Graphs illustrating and comparing the running times of the three algorithms. (ii) A description of how the graphs were obtained (e.g., range of dimensions, number of randomly generated matrices of each dimension, types of matrices, etc.). You must submit your files to the AA Moodle page by Friday 16 August at 23h00.
The objective of this exercise is to reconstruct/unzip a message archived with a binary-treebased algorithm.The program should ask for a single filename at the start: “Please enter filename to decode: “, 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.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 payload3. 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.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.cs228.hw3 package. Turn in the zip file and not your class files. Please follow the guideline in submission_guide.pdf. Include the Javadoc tag @author in each class source file. Your zip file should be named Firstname_Lastname_HW3.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 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_HW3_extra.zip if you completed the iterative solution.
The purposes of this assignment are to practice working with a linked data structure to become intimately familiar with the List and ListIterator interfaces This assignment will also provide many opportunities to practice your debugging skills.1.1. Summary of Tasks Implement a class StoutList that extends AbstractSequentialList along with inner classes for the iterators. A skeleton is provided. See the implementation and suggestions for getting started sections for details.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.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/22.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){…}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.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 offset5.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: • using interfaces and abstract classes • reusing code through inheritance (“is-a”) relationship • reusing code through association (“has-a”) relationshipA portion of your grade on this assignment (roughly 15% to 20%) will be determined by your logical organization of classes in a class hierarchy and by how effectively you have been able to use inheritance and composition to minimize duplicated code. Be sure you have done and understood Lab 8 checkpoint 2!In this project you will complete the implementation of a hierarchy of classes representing various types of elements in a video game. Your task is to implement these eight concrete classes: SimpleElement AttachedElement FlyingElement FollowerElement LiftElement MovingElement PlatformElement VanishingElementAll eight of these classes must directly or indirectly extend the given abstract class api.AbstractElement. In implementing them, you may put them into a class hierarchy that contains one or more additional abstract classes you create on your own to a) avoid duplicating common code between the eight types, and b) avoid having redundant code or attributes in any type.All your code (the 8 required classes, and any extra classes you create) goes in the hw4 package.Part of your grade for this assignment (e.g. 15-20%) will be based on how effectively you are able to implement the eight required concrete types with a minimum of code duplication. Here are some specific restrictions; see page 13 for more details. • You may not use public, protected or package-private variables. (You can provide protected accessor methods or constructors when needed.) • You may not modify the AbstractElement class itself (or anything else in the api package).A 2D video game may include elements such as players, enemies, projectiles, PlatformElements, walls, and so on, each with slightly different behavior, but with many attributes in common as well. For example, at any given time, a game element has a position (x, y) within a window, where x and y are floating point values, (0, 0) is the upper left corner of the window, and the positive y- direction is downwards. It also has a width and height, forming a bounding rectangle. This rectangle is used for actually drawing the graphics on the screen, and also for detecting collisions between elements.The capabilities needed for doing the actual drawing are represented by the simple interface api.Drawable, with these six methods: void draw(Graphics g) – draws this object using the given graphics context int getXInt() – returns the x-coordinate, rounded to the nearest integer int getYInt() – returns the y-coordinate, rounded to the nearest integer| int getWidth() – returns the width int getHeight() – returns the height Rectangle getRect() – returns the bounding rectangle (an instance of java.awt.Rectangle) (These capabilities are isolated in this interface so that the graphical portion of applications need not be concerned with any of the details of our specific type hierarchy for game elements.)Your starting point will be the abstract class api.AbstractElement, which is declared to implement the Drawable interface but leaves five of its methods abstract, and also declares seven additional abstract methods. The important point is that the AbstractElement class provides the implementation of the draw method, so that in your own code you do not ever need to be concerned with the graphical aspects of the application. To allow for customizing the way that a given game element is rendered on the screen, we define an interface api.Renderer, and a AbstractElement always has an attribute of type Renderer.The api package includes various examples of renderers that are used in the demo applications, such as the BasicRenderer that fills in an element’s bounding rectangle with a solid color, or the ImageRenderer that displays an image in the bounding rectangle. Again, you will not need to be concerned with the graphical aspects of the implementation, except to the extent that you want to experiment with the demo applications and try things out.The general design of the game framework is based on a timer that periodically triggers a callback method, say, 25 times per second (the so-called frame rate). You would, in practice, implement a game by setting up the game elements and then customizing the callback method to update element positions, handle collisions, generate new enemies, keep score, etc.The most fundamental operation in the callback is to invoke the update() method on each element. In the simplest case of something like SimpleElement that never actually moves or changes, the update method does nothing except increment a counter. In a (slightly) more interesting element type such as MovingElement, the update method might also change the element’s position by adding a “velocity” (deltaX, deltaY) to the x and y coordinates of the position.Here is a brief overview of the eight concrete types, in alphabetical order. Each one must directly or indirectly extend AbstractElement. For detailed method specifications, see the Javadoc. SimpleElement: Simplest concrete subclass of the AbstractElement type. The update method just increments a frame counter.AttachedElement: An element that is always associated to another “base” element such as a PlatformElement or LiftElement. It only moves with the associated base object, remaining a fixed distance above it. In addition to the methods specified in Drawable and AbstractElement, it has a method setBase.FlyingElement: An element whose position is updated each frame according to its vertical velocity. Additionally, to simulate gravity, the vertical velocity is adjusted each frame by a gravitational constant. In addition to the methods specified in Drawable and AbstractElement, it has the methods setVelocity, setGravity, setGrounded, getDeltaX, and getDeltaY.FollowerElement: An element that is always associated to another “base” element such as a PlatformElement or LiftElement. Optionally, it can be configured with a nonzero horizontal velocity and it will oscillate back and forth between the left and right edges of the base element it is associated to, while remaining directly above it. In addition to the methods specified in Drawable and AbstractElement, it has methods setVelocity, getDeltaX, getDeltaY, setBounds, getMax, getMin, and setBase.LiftElement: An element with two distinctive behaviors: First, it can be configured to move vertically within a fixed set of boundaries. On reaching a boundary, the y-component of its velocity is reversed. Second, it maintains a list of elements that are associated with it (see AttachedElement and FollowerElement) whose basic motion all occurs relative to the LiftElement. Invoking update on a LiftElement updates the LiftElement’s position, adjusts the velocity as necessary, and then invokes update on each associated element. In addition to the methods specified in Drawable and AbstractElement, it has the methods setVelocity, getDeltaX, getDeltaY, setBounds, getMax, getMin, addAssociated, deleteMarkedAssociated, and getAssociate.MovingElement: An element in which the update method adjusts the position each frame with a velocity vector (deltaX, deltaY). The units of velocity are “pixels per frame”. In addition to the methods specified in Drawable and AbstractElement, it has the methods setVelocity, getDeltaX, and getDeltaY.PlatformElement: An element with two distinctive behaviors: First, it can be configured to move horizontally within a fixed set of boundaries. On reaching a boundary, the x-component of its velocity is reversed. Second, it maintains a list of elements that are associated with it (see AttachedElement and FollowerElement) whose basic motion all occurs relative to the PlatformElement. Invoking update on a PlatformElement updates the PlatformElement’s position, adjusts the velocity as necessary, and then invokes update on each of its associated elements. In addition to the methods specified in Drawable and AbstractElement, it has the methods setVelocity, getDeltaX, getDeltaY, setBounds, getMax, getMin, addAssociated, deleteMarkedAssociated, and getAssociated.VanishingElement: An element that does not move, but it has an internal counter that is decremented each frame. When the counter reaches zero, the element marks itself for deletion.Note that the Javadoc was generated under the simple assumption that each concrete class was a direct extension of AbstractElement, i.e., that no inheritance was being used within these eight classes. So when you see in the Javadoc the line “extends api.AbstractElement”, please do not take that literally as part of the spec! In a wellwritten implementation of the hierarchy, it is extremely unlikely, for example, that the FlyingElement class would directly extend AbstractElement.The Demo applications There are some sample graphical applications to try out in the demo package. These are highly experimental and almost certainly have bugs. As always, these are just for fun, do not rely on the GUI to accurately test your code! • PigsExample – requires only that you have implemented SimpleElement • MazeExample – requires SimpleElement and MovingElement, use arrow keys to move • JumpExample1 – requires SimpleElement and FlyingElement, use arrow keys, and ‘a’ key to jump • VanishingElementExample – requires VanishingElement • WhenPigsFly – requires SimpleElement, MovingElement, FlyingElement, and • PlatformExample – requires PlatformElement, LiftElement, AttachedElement, and FollowerElement • JumpExample2 – requires PlatformElement, LiftElement, AttachedElement, • FollowerElement, and FlyingElement, use arrow keys and ‘a’ key to jump • SuperPigsExample – requires everything! use arrow keys, and ‘a’ key to jumpAs always, you should try to work incrementally and write tests for your code as you develop it. Do not rely on the UI demo code for testing! Trying to test your code using a UI is very slow, unreliable, and generally frustrating. The UI code is complex and not guaranteed to be free of bugs. In particular, when we grade your work we are NOT going to run any of the demo programs, we are going to test that each method works according to its specification.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 everything in your hw4 package. Please check this carefully. In this assignment you may be including one or more abstract classes of your own, in addition to the 8 required classes, so make sure they have been included in the zip file.Importing the sample code The sample code is distributed as a complete Eclipse project that you can import. However, the packages sample_tests and demo are posted separately, to keep you from getting a ton of compile errors at first. The hw4 package includes a basic skeleton for each required class, including only the class and constructor declarations.1. Download the zip file sample_code.zip. You don’t need to unzip it. 2. In Eclipse, go to File -> Import -> General -> Existing Projects into Workspace, click Next. 3. Click the radio button for “Select archive file”. 4. Browse to the zip file you downloaded and click Finish. 5. When you want to try something from sample_tests or demo, create the package in your project, download the respective zip file, extract it, and drag the file(s) you want into the appropriate package. If you have an older version of Java or if for some reason you have problems with the process above, or if the project does not build correctly, you can construct the project manually as follows:6. Extract the zip file containing the sample code (Note: on Windows, you have to right click and select “Extract All” – it will not work to just double-click it) 7. In Windows Explorer or Finder, browse to the src directory of the zip file contents 8. Create a new empty project in Eclipse 9. In the Eclipse Package Explorer, navigate to the src folder of the new project. 10. Drag the hw4 and api folders from Explorer/Finder into the src folder in Eclipse. Getting started 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. You’ll find that the code is not terribly difficult – other than the inheritance aspects, most of these classes could have been given as a pretty easy homework 2.Step 1: Most importantly – be sure you have done and understood the second checkpoint of lab 8. Sometimes the best way to start on an inheritance hierarchy is to, initially, forget about inheritance. That is, if you have two classes A and B that might be related, just implement both of them completely from scratch. Then look at what they have in common. Does it make logical sense for one to extend the other? Should the common code be factored into a common, abstract superclass?2. It looks like SimpleElement is just a direct implementation of all the abstract methods specified in AbstractElement, so that would seem a likely place to start. As always begin by writing a simple test case so you know what you are expecting to happen, for example (see BasicTest.java in the sample_tests package): SimpleElement e = new SimpleElement(2.3, 4.5, 10, 20); System.out.println(e.getXReal()); // expected 2.3 System.out.println(e.getXInt()); // expected 2 System.out.println(e.getYReal()); // expected 4.5 System.out.println(e.getYInt()); // expected 5 System.out.println(e.getWidth()); // expected 10 System.out.println(e.getHeight());// expected 20 System.out.println(e.getRect()); // expected java.awt.Rectangle[x=2,y=5,width=10,height=20] System.out.println(e.isMarked()); // expected false Then try out some mutator methods too… // setting position e.setPosition(42, 137); System.out.println(e.getXReal()); // expected 42 System.out.println(e.getYReal()); // expected 137 // update should increment the frame count e.update(); e.update(); System.out.println(e.getFrameCount()); // expected 2 // mark e.markForDeletion(); System.out.println(e.isMarked()); // expected true // intersections e = new SimpleElement(10, 0, 10, 10); SimpleElement e2 = new SimpleElement(1, 5, 10, 10); System.out.println(e.collides(e2)); // expected true e2.setPosition(0, 5); System.out.println(e.collides(e2)); // expected false (Tip: the java.awt.Rectangle class includes a method intersects that might be useful!) 3. You might next try MovingElement, FlyingElement, and VanishingElement, which appear to be fairly similar to SimpleElement. Write some simple tests as above for all the methods. For example, how does gravity work? (See FlyingElementTest.java in the sample_tests package.) FlyingElement p = new FlyingElement(0, 0, 0, 0); p.setGrounded(false); p.setVelocity(2, 3); p.update(); System.out.println(p.getYReal()); // expected 3 System.out.println(p.getDeltaY());// expected 3 p.update(); System.out.println(p.getYReal()); // expected 6 System.out.println(p.getDeltaY());// expected 3 p.setGravity(5); p.update(); System.out.println(p.getYReal()); // 6 + 3 = 9 System.out.println(p.getDeltaY()); // 3 + 5 = 8 p.setGrounded(true); p.update(); System.out.println(p.getYReal()); // 9 + 8 = 17 System.out.println(p.getDeltaY()); // 8 (grounded) p.update(); System.out.println(p.getYReal()); // 17 + 8 = 25 System.out.println(p.getDeltaY()); // 8 (grounded) 4. Maybe the next thing to tackle is PlatformElement. Sketch out a couple of examples by hand to be sure you can see how to update the position and velocity when reaching the min or max position. Try creating some test cases, for example (see PlatformElementTest.java): // left side at x = 50, width 10, right side at 60 PlatformElement p = new PlatformElement(50, 200, 10, 10); p.setBounds(40, 70); p.setVelocity(6, 0); p.update(); System.out.println(p.getXReal() + “, ” + (p.getXReal() + 10)); // [56, 66] System.out.println(“Velocity ” + p.getDeltaX()); // 6.0 p.update(); System.out.println(p.getXReal() + “, ” + (p.getXReal() + 10)); // [60, 70] System.out.println(“Velocity ” + p.getDeltaX()); // -6.0 p.update(); System.out.println(p.getXReal() + “, ” + (p.getXReal() + 10)); // [54, 64] System.out.println(“Velocity ” + p.getDeltaX()); // -6.0 p.update(); System.out.println(p.getXReal() + “, ” + (p.getXReal() + 10)); // [48, 58] System.out.println(“Velocity ” + p.getDeltaX()); // -6.0 p.update(); System.out.println(p.getXReal() + “, ” + (p.getXReal() + 10)); // [42, 52] System.out.println(“Velocity ” + p.getDeltaX()); // -6.0 p.update(); System.out.println(p.getXReal() + “, ” + (p.getXReal() + 10)); // [40, 50] System.out.println(“Velocity ” + p.getDeltaX()); // 6.0 5. You can’t complete the implementation of PlatformElement without checking its behavior with associated elements. It looks like AttachedElement is quite a bit simpler than FollowerElement, so we could start with that. See PlatformWithAttachedTest.java. // left side at x = 50, width 10, right side at 60 PlatformElement p = new PlatformElement(50, 200, 10, 10); p.setBounds(40, 70); p.setVelocity(6, 0); // size 5 x 5, offset 2 units from left of PlatformElement, 15 above AttachedElement c = new AttachedElement(5, 5, 2, 15); // this should automatically make p the base of c p.addAssociated(c); // x position should be the base position + 2 = 52 // y position should be base y – AttachedElement height – hover = 180 System.out.println(c.getXReal()); // expected 52 System.out.println(c.getYReal()); // expected 180 p.update(); System.out.println(c.getXReal()); // expected 58 System.out.println(c.getYReal()); // expected 180 p.update(); System.out.println(c.getXReal()); // expected 62 System.out.println(c.getYReal()); // expected 180 // calling update on p should update associated elements too System.out.println(c.getFrameCount()); // expected 2 6. Time to think about FollowerElement, maybe? It has the same oscillating behavior as a PlatformElement, but all motion is relative to the PlatformElement it’s on. First think about what it should do when the PlatformElement isn’t moving, that should be the easiest case. See PlatformWithFollowerTest.java. // first try an example where the base doesn’t move // left side at x = 50, width 10, right side at 60 PlatformElement p = new PlatformElement(50, 200, 10, 10); p.setBounds(40, 70); // size 5 x 5, initial offset 2 units from left of PlatformElement FollowerElement e = new FollowerElement(5, 5, 2); e.setVelocity(2, 0); // this should automatically make p the base of e // and the left and right sides of p the boundaries of e p.addAssociated(e); System.out.println(e.getMin()); // 50 System.out.println(e.getMax()); // 60 // x position should be the base position + 2 = 52 // y position should be base y – FollowerElement height = 195 System.out.println(e.getXReal()); // expected 52 System.out.println(e.getYReal()); // expected 195 // PlatformElement doesn’t move here, but FollowerElement does p.update(); System.out.println(e.getXReal() + “, ” + (e.getXReal() + 5));//expected 54,59 System.out.println(e.getDeltaX()); // expected 2.0 p.update(); // this should hit the right boundary System.out.println(e.getXReal() + “, ” + (e.getXReal() + 5));//expected 55,60 System.out.println(e.getDeltaX()); // expected -2.0 System.out.println(); 7. How about if PlatformElement is moving, but the FollowerElement isn’t? // next, what if PlatformElement is moving, but FollowerElement velocity 0? // left side at x = 50, width 10, right side at 60 p = new PlatformElement(50, 200, 10, 10); p.setBounds(40, 70); p.setVelocity(3, 0); // size 5 x 5, initial offset 2 units from left of PlatformElement e = new FollowerElement(5, 5, 2); p.addAssociated(e); System.out.println(e.getXReal() + “, ” + (e.getXReal() + 5));//expected 52,57 // when p moves, the boundaries of e should shift p.update(); System.out.println(“bounds ” + e.getMin() + “, ” + e.getMax());// 53, 63 // but e is still 2 units from left side System.out.println(e.getXReal() + “, ” + (e.getXReal() + 5));//expected 55,60 System.out.println(); 8. The trickiest bit is when both the PlatformElement and FollowerElement are both moving. For example: // next, what if PlatformElement is moving, and FollowerElement velocity is nonzero? // left side at x = 50, width 10, right side at 60 p = new PlatformElement(50, 200, 10, 10); p.setBounds(40, 70); p.setVelocity(3, 0); // size 5 x 5, initial offset 2 units from left of PlatformElement e = new FollowerElement(5, 5, 2); e.setVelocity(2, 0); p.addAssociate(e); System.out.println(e.getXReal() + “, ” + (e.getXReal() + 5));//expected 52,57 p.update(); // e is now 4 units from left bound, since its velocity is 2 System.out.println(“bounds ” + e.getMin() + “, ” + e.getMax());// 53, 63 System.out.println(e.getXReal() + “, ” + (e.getXReal() + 5)); // 57, 62 p.update(); // p has moved to [56, 66], e attempts to move another 2 units // relative to p, to [62, 67], but hits the right boundary at 66 // and reverses direction System.out.println(“bounds ” + e.getMin() + “, ” + e.getMax());// 56, 66 System.out.println(e.getXReal() + “, ” + (e.getXReal() + 5)); // 61, 66 System.out.println(“velocity ” + e.getDeltaX()); // expected -2 You should be able to further develop the test cases above (for example, does your code work when the FollowerElement hits the left boundary?) 9. Try working on similar tests for LiftElements with AttachedElements and FollowerElements. Requirements and guidelines regarding inheritance A generous portion of your grade (maybe 20%) will be based on how well you have used inheritance, and possibly abstract classes, to create a clean design with a minimum of duplicated code. Please note that there is no one, absolute, correct answer – you have design choices to make. You will explain your design choices in the class Javadoc for BaseElement.You are not allowed to use non-private variables. Call the superclass constructor to initialize its attributes, and use superclass accessor methods to access them. If your subclass needs some kind of access that isn’t provided by public methods, you are allowed to define your own protected methods or constructors.Other general guidelines You should not use instanceof or getClass() in your code, or do any other type of runtime type-checking, to implement correct behavior. Rely on polymorphism. • No class should contain extra attributes or methods it doesn’t need to satisfy its own specification. • Do not ever write a method like this (it is redundant): public void foo() { super.foo() } There is almost never any reason to declare and implement a method that is already implemented in the superclass unless you need to override it to change its behavior. That is the whole point of inheritance!Style and documentation Special documentation requirement: you must add a comment to the top of the SimpleElement class with a couple of sentences explaining how you decided to organize the class hierarchy for the elements. Roughly 10 to 15% of the points will be for documentation and code style. Some restrictions and guidelines for using inheritance are described above. When you are overriding a superclass or interface method, it is usually NOT necessary to rewrite the Javadoc, unless you are really, really changing its behavior. Just include the @Override annotation. (The Javadoc tool automatically copies the superclass Javadoc where needed.) The other general guidelines are the same as in homework 3. Remember the following: • You must add an @author tag with your name to the javadoc at the top of each of the classes you write. • You must javadoc each instance variable and helper method that you add. Anything you add must be private or protected. • Keep your formatting clean and consistent. • Avoid redundant instance variables • Accessor methods should not modify instance variables If you have questions It is extremely likely that the specification will not be 100% clear to you. Part of your job as a developer is to determine what still needs to be clarified and to formulate appropriate questions. In particular, since you are not required to turn in any test code for this assignment, your tests and test cases can be freely shared and discussed on Piazza. It is your responsibility to make sure that you correctly understand the specification and get clarifications when needed.For questions, please see the Piazza Q & A pages and click on the folder hw4. If you don’t find your question answered already, 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 hw4. 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 buttons labeled “code” or “tt” 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 posts from the instructors 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.) Acknowledgement This project was inspired by the quirky and wonderful book, Program Arcade Games With Python and Pygame, http://programarcadegames.com/ , written by Paul Craven, who teaches at Simpson College in Indianola.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. Please submit, on Canvas, the zip file that is created by the SpecChecker. The file will be named SUBMIT_THIS_hw4.zip and it will be located in whatever directory you selected when you ran the SpecChecker. It should contain one directory, hw4, which in turn contains the eight required classes along with any others you defined in the hw4 package. Please LOOK at the file you upload and make sure it is the right one and contains everything needed! Submit the zip file to Canvas using the Assignment 4 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 hw4, which in turn should contain everything in your hw4 directory. You can accomplish this by zipping up the hw4 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.
The purpose of this assignment is to give you 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: LizardGame, Lizard, and GameFileUtil. 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 a game we call Lizards, which is a mix between the classic snake game1 and a sliding blocks puzzle game.The game is played on a 2-dimensional grid of “cells”. Each cell may contain a wall, an exit, or the body segment of a lizard. Cells are located by column and row. Figure 1 The user presses down the left mouse button and drags lizards to move them around with the goal of getting all the lizards to the exit. A lizard’s body is multi-segmented and the user can press and drag any segment. The lizard moves in a snake-like fashion, that is, each segment must follow in the path of the segments in front or behind of them when the lizard moves forward or backward respectively. The only exception is when the user clicks and drags the head or tail 1 https://en.wikipedia.org/wiki/Snake_(video_game_genre) segments, which can move in any direction. There are only four possible directions of movement: up, down, right, left (never diagonally).To illustrate the movement, Figure 2 shows four different scenarios: 1) the user selects the head segment and drags it in some forward direction 2) the user selects the tail segment and drags it in some backward direction 3) the user selects one of the inner segments and drags it in a forward direction 4) the user selects an inner segment and drags it in a backward direction. It is also possible, but not shown, that the user pushes the head segment in a backward direction or the tail segment in a forward direction. Figure 2The lizard may not move off the grid and may not move onto a wall. When it moves onto an exit, the lizard is removed from the grid. When all of the lizards have been removed, the player wins. 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. The api package contains some classes for representing data in the game. There are some simple tests for you to start with located in the default package. Figure 3 You may not modify the code in the ui or api packages. Specification The complete specification for this assignment includes • this pdf, • the online Javadoc, and • any “official” clarifications posted on Canvas and/or PiazzaThe GameFileUtil class is a simple utility class with a single static method to load a game file. public static void load(String filePath, LizardGame game); Game files are in plain text and have a particular format. There are three main sections to the file: the dimensions of the grid, a representation of the grid’s cells, and a description of the lizards. The table below gives an example of these three segments. 8×8 Number of columns by number of rows, can be any integers larger than 0. W WW . WWW W. . WWWWWW . E. WWWWW W. W W. W W . A representation of the grid’s cells, showing the location of walls “W” and exits “E”. Each row ends with a dot. L 5,1 6,1 6,2 5,2 4,2 3,2 2,2 L 1,2 0,2 0,3 0,4 1,4 2,4 3,4 4,4 5,4 6,4 6,5 6,6 5,6 4,6 Each line represents a lizard. The pairs of numbers represent the location of segments, starting from the tail (left most pair) of the lizard and ending with the head (right most).Coordinates are specified as (column, row) pairs. As shown in Figure 1, the columns are numbered from left to right starting at zero and the rows are numbered from top to bottom starting at zero. We use column before row consistently throughout this document and the API because it matches with the convention of specifying coordinates as (x, y), however, it conflicts with the convention of arrays being rows of columns. How you implement internal data structures such as arrays does not need to match with the API, all that matters is that you are consistent in your usage of the data structures. Finally, note that load does not return anything. It is passed a LizardGame object and it is expected that the method calls mutator methods on the object to update the state of the game.The Lizard class models a lizard as a collection of body segments (see the class api.BodySegment). The class contains several accessor and mutator method that can be used by other parts of the program, for example LizardGame. The segments are provided to the object with a call to setSegments(ArrayList segments), where the segments are expected to be ordered from tail to head. In other words, you can assume the first element of the list is always the tail.The LizardGame class models the game and its methods are called by classes in the ui package to create a complete game. For example, the UI calls move() every time the user presses and drags the mouse over the graphical representation of the gird. Also, LizardGame is responsible for keeping track of the grid of cells. Each cell is represented as a Cell object. The grid is specified by (column, row), as shown in Figure 1 and described in GameFileUtil above, however you can store the cells any way you want as long as the public methods produce the correct results.The GUI 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 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 classes GamePanel and GridViz contain most of the UI code.Importing the sample code The sample code includes a complete skeleton of the three 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. 1. Download the zip file. You don’t need to unzip it. 2. In Eclipse, go to File -> Import -> General -> Existing Projects into Workspace, click Next. 3. Click the radio button for “Select archive file”. 4. Browse to the zip file you downloaded and click Finish. 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: 1. Extract the zip file containing the sample code (Note: on Windows, you have to right click and select “Extract All” – it will not work to just double-click it) 2. In Windows Explorer or Finder, browse to the src directory of the zip file contents 3. Create a new empty project in Eclipse 4. In the Eclipse Package Explorer, navigate to the src folder of the new project. 5. Drag the hw3, ui, and api folders from Explorer/Finder into the src folder in Eclipse. 6. Copy the remaining top-level files (SimpleTest.java, etc) into the src folder. Testing and the SpecChecker As always, you should try to work incrementally and write tests for your code as you develop it. Do not rely on the UI code for testing! Trying to test your code using a UI is very slow, unreliable, and generally frustrating. The code for the UI itself is more complex than the code you are implementing, and it is not guaranteed to be free of bugs. In particular, when we grade your work we are NOT going to run the UI, we are going to test that each method works according to its specification.We will provide a SpecChecker, it will contain many tests to help you get started, but do not expect that it will test for every possible mistake you might make. 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 tests. The SpecChecker we use for grading may have more tests added. 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.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. You can find the example test cases below in the default package of the sample code. Don’t try to copy/paste from the pdf.Please remember that these are just examples to get you started and you will need to write many, many more tests to be sure your code is working correctly. (You can expect that the functional tests we run when grading your work will have something like 100 test cases, for example.)Don’t rely on the GUI for testing your code. Doing so is difficult and frustrating because the GUI itself is so complex. Rely on simple, focused test cases that you can easily run in the debugger. A good starting point is the Lizard class. A lizard is modeled as a collection of body segments (see the class api.BodySegment). A lizard can be constructed for test like this. Lizard liz = new Lizard(); Cell cell0 = new Cell(1, 1); Cell cell1 = new Cell(2, 1); Cell cell2 = new Cell(2, 2); ArrayList segments = new ArrayList(); segments.add(new BodySegment(liz, cell0)); segments.add(new BodySegment(liz, cell1)); segments.add(new BodySegment(liz, cell2)); There are several methods to implement in Lizard. Right now, these methods may not seem to be that important. But when you implement LizardGame, you may find many uses for these methods, so take note of what they do. Here are some simple tests for the methods in Lizard. liz.setSegments(segments); System.out.println(“The lizard has ” + liz.getSegments().size() + ” segments, expected 3.”); BodySegment headSegment = liz.getHeadSegment(); Cell headCell = headSegment.getCell(); System.out.println(“The head segment is at ” + headCell + “, expected (2,2,Ground,Lizard).”); BodySegment tailSegment = liz.getTailSegment(); Cell tailCell = tailSegment.getCell(); System.out.println(“The tail segment is at ” + tailCell + “, expected (1,1,Ground,Lizard).”); BodySegment middleSegment = liz.getSegmentAt(cell1); Cell middleCell = middleSegment.getCell(); System.out.println(“The middle segment is at ” + middleCell + “, expected (2,1,Ground,Lizard).”); BodySegment aheadSegment = liz.getSegmentAhead(middleSegment); Cell aheadCell = aheadSegment.getCell(); System.out.println(“The segment ahead of the middel is at ” + aheadCell + “, expected (2,2,Ground,Lizard).”); BodySegment behindSegment = liz.getSegmentBehind(middleSegment); Cell behindCell = behindSegment.getCell(); System.out.println(“The segment behind the middel is at ” + behindCell + “, expected (1,1,Ground,Lizard).”); Direction aheadDir = liz.getDirectionToSegmentAhead(middleSegment); System.out.println(“From the middle segment, ahead is ” + aheadDir + “, expected DOWN.”); Direction behindDir = liz.getDirectionToSegmentBehind(middleSegment); System.out.println(“From the middle segment, behind is ” + behindDir + “, expected LEFT.”); Direction headDir = liz.getHeadDirection(); System.out.println(“The head is pointing ” + headDir + “, expected DOWN.”); Direction tailDir = liz.getTailDirection(); System.out.println(“The tail is pointing ” + tailDir + “, expected LEFT.”); The class GameFileUtil is used to load saved game files. You are provided with a couple of sample files in the examples directory. // Example tests for GameFileUtil class // (requires some implementation of LizardGame) LizardGame game = new LizardGame(0, 0); GameConsole gc = new GameConsole(); game.setListeners(gc, gc); System.out.println(); GameFileUtil.load(“examples/game1.txt”, game); System.out.println(“Expected a message saying the number of lizards is now 1.”); System.out.println(“DO NOT print this message in GameFileUtil, the ScoreListener needs to be called in LizardGame.”); System.out.println(); System.out.println(“The grid with is ” + game.getWidth() + “, expected 8.”); System.out.println(“The grid height is ” + game.getHeight() + “, expected 4.”); System.out.println(“The cell at (0,0) is empty (” + game.getCell(0, 0).isEmpty() + “), expected true.”); System.out.println(“The cell at (1,1) has a wall (” + (game.getCell(1, 1).getWall() != null) + “), expected true.”); System.out.println(“The cell at (7,2) has an exit (” + (game.getCell(7, 2).getExit() != null) + “), expected true.”); System.out.println(“The cell at (2,2) has a lizard (” + (game.getCell(2, 2).getLizard() != null) + “), expected true.”); The LizardGame class models the game and its methods are typically called by the UI. Write simple tests to take place of the UI. The main interaction with the user happens when the user selects and drags the body segment of a lizard. These mouse events result in calls to the method move().Without a doubt, move() is the most complex of the methods you need to implement. Read the javadocs, review Figures 1 and 2 of this document, review the many methods available to help with the logic in Lizard and LizardGame and finally, break the problem into smaller parts and possibly create helper methods of you own. Many of the other methods in LizardGame are designed to help move() do its job, but you will also probably want to implement your own helper methods, which is allowed as long as they are private. Here are some simple tests for LizardGame. // Example tests for LizardGame // (assuming previous tests worked and the game is loaded) segments = new ArrayList(); segments.add(new BodySegment(liz, game.getCell(1, 0))); segments.add(new BodySegment(liz, game.getCell(2, 0))); segments.add(new BodySegment(liz, game.getCell(3, 0))); liz = new Lizard(); liz.setSegments(segments); System.out.println(); game.addLizard(liz); System.out.println(“Expected a message saying the number of lizards is now 2.”); System.out.println(); game.removeLizard(liz); System.out.println(“Expected a message saying the number of lizards is now 1.”); System.out.println(); liz = game.getLizards().get(0); Cell adjCell = game.getAdjacentCell(1, 1, RIGHT); System.out.println(“Right of cell (1,1) is ” + adjCell + “, expected cell (2,1,Ground,Empty)”); System.out.println(“Cell (5,2) is available (” + game.getCell(5, 2) + “), expected true.”); System.out.println(“Moving head of lizard one RIGHT.”); game.move(4, 2, RIGHT); System.out.println(“Cell (5,2) is available (” + game.isAvailable(5, 2) + “), expected false.”); System.out.println(“The head of the lizard is in cell (5,2) (” + (liz.getHeadSegment().getCell() == game.getCell(5, 2)) + “), expected true.”); More about grading This is a “regular” assignment so we are going to read your code. Your score will be based partly (about a two thirds) on the specchecker’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 specchecker 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 %? Are you using a loop for something that can be done with integer division? Additionally, you should not take this to mean that your only job is it pass the specchecker’s test by any means possible, such as hard-coding return values. The version of the specchecker we use for grading may be modified to use different inputs and test the methods in different ways than the speccecker you are given for testing. Bottom line, you job is to correctly implement algorithms that meet the specifications. Some specific criteria that are important for this assignment are: • Use instance variables only for the “permanent” state of the object, use local variables for temporary calculations within methods. o You will lose points for having unnecessary instance variables o All instance variables should be private. • Accessor methods should not modify instance variables. See the “Style and documentation” section below for additional guidelines. Restrictions on Java Features For this Assignment There are no restrictions on the Java features you can use to implement this assignment. However, 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 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: • You must add an @author tag with your name to the javadoc at the top of each of the classes you write (in this case the classes in the hw3 package). • You must javadoc each instance variable and helper method that you add. Anything you add must be private. • Since the code includes some potentially tricky loops to write, you ARE expected to add internal (//-style) comments, where appropriate, to explain what you are doing inside the longer methods. A good rule of thumb is: if you had to think for a few minutes to figure out how to do something, you should probably include a comment explaining how it works. Internal comments always precede the code they describe and are indented to the same level. • Keep your formatting clean and consistent. • Avoid redundant instance variables • Accessor methods should not modify instance variables If you have questions 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 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, before the submission link will be visible to you. Please submit, on Canvas, 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, LizardGame.java, GameFileUtil.java, and Lizard.java. Please LOOK at the file you upload and make sure it is the right one! Submit the zip file to Canvas using the 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.
You are required to create a Python program that implements the k-means Algorithm. Your Python submission to moodle will be a .py file in which: (1) The number of clusters is set to 3. (2) The dataset below on page 3 is hard-coded into the algorithm. Your algorithm must then: (3) Read in from standard input a list of 6 numbers, such as 0.45 0.55 0.70 0.71 0.11 0.67The first 2 values are the initial values for cluster centre 1, so µ 1 = (0.45, 0.55). The next 2 values are the initial values for cluster centre 2, so µ 2 = (0.70, 0.71). The last 2 values are the initial values for cluster centre 3, so µ 3 = (0.11, 0.67).(4) Run k-means Algorithm using the hard-coded dataset and starting with cluster centres from step 3. (5) Halt the algorithm when the centres have converged – that is, there are no changes to the cluster centres from one iteration to the next.(6) Compute the sum-of-squares error on the dataset with respect to the final cluster centres, using the formula sum-of-squares error = X 3 j=1 X x∈cluster j d(x, µ j ) 2 .(7) The following value must be output using standard output: the sum-of-squares error with respect to the final cluster centres. Round off to 4 decimal places. Samples: (i) For the input values given above, the output is: 1.1053 (ii) For the following input values, the output is given below: 0.85 0.14 0.32 0.76 0.21 0.36 Output: 0.4379Use the following dataset consisting of datapoints in R 2 : 0.22, 0.33 0.45, 0.76 0.73, 0.39 0.25, 0.35 0.51, 0.69 0.69, 0.42 0.41, 0.49 0.15, 0.29 0.81, 0.32 0.50, 0.88 0.23, 0.31 0.77, 0.30 0.56, 0.75 0.11, 0.38 0.81, 0.33 0.59, 0.77 0.10, 0.89 0.55, 0.09 0.75, 0.35 0.44, 0.55
In this assignment you are required to create a Python program that does the following: (Note: You may not use any Python machine learning libraries other than numpy.) (a) Implement a neural network with 3 layers with the following specifications: the input layer has 4 nodes the hidden layer has 8 nodes the output layer has 3 nodes all nodes in the hidden layer and output layer use sigmoid activation function all weights are initialised to 1 all bias values are initalised to 1(b) You need to implement the feedforward step to compute the output of the network for some given inputs.(c) You need to implement the sum-of-squares loss computation between the output and target.Recall: sum-of-squares loss is L(y, t) = 1 2 Pk j=1(yj − tj ) 2 .(d) You need to implement the backpropagation method for updating the weights and biases of the network. Use a learning rate of 0.1.Your Python submission to moodle will be a .py file that does the following: (1) Read in from standard input a list of seven numbers, such as −2 1 0.5 −1 0 0 1The first 4 values are the input to the network and the last 3 are the corresponding targets. (2) Feedforward the input values to obtain output values and compute the sum-of-squares loss with respect to the target values. (3) Perform one iteration of backpropagation.(4) After that, feedforward the same input values into the updated network to get new output values, and compute a new loss value. (5) The following values must be output using standard output: the loss before training and the loss after training, rounded to 4 decimal places. Only round off at the end of the computation.For the above input, the output should be: 0.9652 0.9647 Here is another example: input 1.4 0 −2.5 −3 0.4 0.6 0 output 0.4107 0.4072
Let’s revisit the motion planning problem for a mobile planar robot with a circular body of radius r operating in a 2D rectangular workspace, as previously described in Homework 3.As before, the robot is modeled as a rigid body with a circular base of radius r. The robot can move in two ways: • Translation T(d): The robot can move along the direction specified by its current orientation, where d ∈ R is the distance parameter. A positive distance d > 0 indicates forward movement, while a negative distance d < 0 indicates backward movement.• Rotation R(θ): The robot can rotate in place by an angle θ around its center, where θ ∈ R is the rotation parameter.The workspace, where the robot operates, is a rectangular area defined by the set [0, Xmax] × [0, Ymax], with the bottom-left corner at (0, 0) and the top-right corner at (Xmax, Ymax). The world contains a set O of circular obstacles, each defined by a tuple o = (xo, yo, ro) ∈ R 2 × R>0, where (xo, yo) is the position of the obstacle’s center and ro is its radius.The robot initial configuration is qI = (xI , yI , θI ). Unlike in Problem 3 of Homework 3, the robot’s initial position (xI , yI ) is not restricted to grid points; it can be located anywhere within the workspace. Additionally, collisions must be considered at all times during the robot’s movement.The goal configuration qG = (xG, yG, θG) includes both position and orientation, and the robot is considered to have reached the goal only when its configuration exactly matches qG, not just when its center is at (xG, yG).The objective of this problem is to determine a sequence of robot’s center positions p = (x0, y0)(x1, y1). . .(xn, yn), where (x0, y0) = (xI , yI ) and (xn, yn) = (xG, yG), along a path τ : [0, 1] → Cfree such that when projecting τ onto the xy-plane, it forms a sequence of line segments l1l2 . . . ln with each segment li connecting (xi−1, yi−1) and (xi , yi). Here, Cfree = C Cobs, where C = R 2 × S is the configuration space and Cobs is the configuration space obstacle as defined in class. In other words, the sequence of line segments corresponding to p must ensure that the robot remains entirely within the workspace and avoid collisions with any obstacle through its motion.1. (15 points for COM S 4760, 10 points for COM S 5760) Can the problem of computing the sequence of positions p be formulated as a discrete planning problem? Explain your reasoning by addressing the following points:• Provide a formal, mathematical definition of the free configuration space C p free. Here, the superscript p indicates that the focus is solely on computing the sequence p of positions rather than the full path τ . So C p free is not necessarily the same as Cfree defined earlier. If your definition of C p free differs from Cfree, explain the reasons for this difference.• Specify whether C p free is countable, and if so, whether they are finite. • Describe how to obtain the sequence p = (x0, y0)(x1, y1). . .(xn, yn) once a path τ p : [0, 1] → Cp free is found, assuming that when projecting τ p onto the xy-plane, it corresponds to a sequence of line segments.2. (15 points for COM S 4760, 10 points for COM S 5760) Solve the planning problem using RRT: Use the single-tree search outlined in Section 5.5.3 to compute a path p within C p free, starting from q p I and ending at q p G. Here, q p I and q p G are the projection of qI and qG, respectively, on the xy-plane.You should check periodically if the tree can be connected to q p G. This can be easily done by setting α(i) as q p G with a certain probability pr.For example, the book recommends pr = 0.01. You should have this as a parameter in your code. Once q p G is successfully added to the tree, quit the loop and compute the path p from q p I to q p G.Implementation Requirements: You are required to implemented a class named CircularMobileRobotPathPlanning with the following methods in a file called midterm.py. • constructor: __init__( self, robot_radius: float, Xmax: float, Ymax: float, circular_obstacles: list ) – robot radius is the radius r of the robot. – Xmax and Ymax define the boundaries of the workspace, corresponding to Xmax and Ymax, respectively.– circular obstacles is a list of circular obstacles, each specified as a tuple (xo, yo, ro), where xo, yo, ro represent the obstacle’s center coordinates xo, yo and radius ro, respectively. • plan method: plan( self, 2 qI: tuple, qG: tuple )Here, qI and qG are tuples of three elements representing the initial and goal configurations, i.e., qI = (xI, yI, tI) and qG = (xG, yG, tG) where xI, yI, tI, xG, yG, tG are floats corresponding to xI , yI , θI , xG, yG, θG, respectively.This method should return a tuple (G, p) where: – G is a graph with a draw(self, ax) function that draws the graph on the specified axis ax – p is the computed path p = (x0, y0)(x1, y1). . .(xn, yn), represented as a list of tuples [p[0], p[1], …, p[n]], where each p[i] is a tuple (xi, yi), corresponding to the position (xi , yi) in p.An example main.py file is provided, along with a file draw cspace.py containing the plotting functionalities. Your implementation should be compatible with these files, so that when running python main.py a plot similar to that in Figure 1 is generated. Additionally, your implementation will be tested with different obstacle configurations and varying values of r, Xmax, Ymax, qI , qG.Figure 1: The result of RRT planning with p = 0.1, showing the tree and the path from xI to xG.3. (COM S 5760 only, 10 points) Consider a scenario where two robots b1 and b2, each with a radius r, operates within this 2D rectangular workspace.In addition to finding individual paths for each robot, we must ensure that their paths are collision-free, meaning that the robots must not collide with each other at any point during their execution.Discuss the potential coordination challenges that arise in multi-robot motion planning by addressing the following points: • Provide a formal, mathematical definition of the configuration space C2 for this multi-robot motion planning problem, where the subscript 2 indicates the setup involving two robots.• Provide a formal, mathematical definition of the free configuration space Cfree,2 ⊆ C2 that excludes the configurations where any robot collides with circular obstacles, workspace boundaries, or the other robot.• Identify assumptions that enable the formulation of a discrete motion planning problem for this two-robot setup. Describe the resulting state space X, the set of actions U, the action space U(x) for each state x ∈ X, and the state transition function f : X × U → X.Unlike in Problem 3 of Homework 3, you are explicitly NOT allowed to assumed that collisions—whether with the workspace boundaries, circular obstacles, or the other robots—can only occur when the robot’s center is precisely at a grid point. Collisions must be checked continuously throughout the robot’s execution, including when the robots move between grid points.Note: A path for a robot may be represented either as a full path τ : [0, 1] → Cfree,1, where Cfree,1 ⊂ R 2 × S 2 is the free configuration space for a scenario where there is a single robot within this 2D rectangular workspace, or as a sequence of robot’s center positions, as described before. When answering the above points, specify how you will represent the paths.
In this assignment, you will develop a path planning algorithm for systems with differential constraints, specifically a car-like system. Dubins car: Recall that the configuration of a simple car is given by q = (x, y, θ), where (x, y) is the position of the center of its rear axle and θ is its orientation. Let s and φ denote the speed and the steering angle (negative when the front wheel is turned to the right and positive when it is turned to the left). See Figure 1, taken from the textbook.The motion of the car can be described by the following configuration transition equation x˙ = s cos θ y˙ = s sin θ ˙θ = s L tan φ Figure 1: The simple car with three degrees of freedom.Consider the Dubins version of the simple car. We assume that the car moves at constant speed s = 1 and φ ∈ [−φmax, φmax], where φmax ∈ (0, π/2). The minimum turning radius is ρmin = L/ tan φmax = 0.5.It can be shown that the shortest path between any two configurations can always be characterized by a Dubins curve, which is one of the following types: LRL, RLR, LSL, LSR, RSL, RSR. Here, L and R corresponds to turning as sharply as possible to the left and right, respectively, while S corresponds to driving the car straight.The world and obstacle region: The car is operating in a 2D world W = [−3, 3] × [−1, 1] with obstacle region O shown in Figure 2. The obstacle region is defined by two half circles centered at (0, −1) and (0, 1), respectively, both having radius 1 − dt, where dt = 0.2. Anything within the two half circles are considered obstacle regions. (This is similar to Homework 4 except that Homework 4 defines the C-space rather than the world and dt is larger in this assignment.)The initial configuration is qI = (−2, −0.5, 0) and the goal configuration is qG = (2, −0.5, π/2). Figure 2: The world and obstacles. The red half-circles are the obstacles. The blue and red arrow represent the initial and goal configurations, respectively.1. (20 points for COM S 4760, 10 points for COM S 5760) Path planning with RRT: Use the single-tree search outlined in Section 14.4.3. You should check periodically if the tree can be connected to qG. This can be easily done by setting α(i) as qG with a certain probability p. For example, the book recommends p = 0.01. You should have this as a parameter in your code. Once qG is successfully added to the tree, quit the loop and compute the path from qI to qG. Plot both the resulting tree and path. The result should be similar to Figure 3, which uses p = 0.1.Figure 3: The result of RRT planning with p = 0.1. The black curves are the edges in the tree. The black arrows are the configurations of the vertices. The blue curve is the path from qI to qG extracted by RRT.Hint: (a) Sampling: As opposed to Homework 4, a configuration in this assignment includes 3 values x, y and θ. Make sure you provide an appropriate range for all of them.(b) Dubins curves: There are existing libraries for computing the shortest paths between any configurations for a Dubins car. Feel free to use any of them. For example, if your code is in python, you may consider the dubins library (https://pypi.org/project/dubins/). OMPL also includes the ompl::base::DubinsStateSpace class (https://ompl.kavrakilab.org/classompl_ 1_1base_1_1DubinsStateSpace.html), which allows you to compute the shortest Dubins path between SE(2) configurations.(c) Collision checking: Besides checking for collisions with the 2 half-circle obstacles, for this assignment, you also need to check that each Dubins curve remains within the world W = [−3, 3] × [−1, 1]. In Homework 4, this check is not necessary because an edge between any 2 configurations are simply a straight line and the configuration space is convex, so as long as all the samples are within the configuration space, any line segment between them is also within the configuration space.(d) Approximate solutions for finding nearest points: For each edge, discretize the corresponding Dubins curve such that consecutive points are not further than ∆q from each other. When finding the nearest point in the swath S of G to α(i), you can simply go through these discretized states and select one that is closest to α(i).2. (COM S 5760 only, 10 points) Path planning with PRM: Use the PRM algorithm described in Figure 5.25 in the textbook to solve the same planning problem given above. As for the number of nodes N, try a different value until you can solve the problem. When connecting to the nodes in the neighborhood, use Nearest K and set K = 15.Hint: As opposed to Homework 4, in this assignment, an edge from configuration q2 to configuration q1 may not simply be the reverse of an edge from q1 to q2. This is because a Dubins car can only move forward so it cannot simply traverse an edge from q1 to q2 backward to obtain an edge from q2 to q1. The CONNECT function for PRM, therefore, needs to perform collision checking for both the forward and reverse edges.Submission: Please submit a single zip file on Canvas containing the followings • your code (with comments, explaining clearly what each function/class is doing), • the plots from each task, similar to Figure 3, and • a text file explaining clearly how to compile and run your code.
Consider the C-space C = [−3, 3] × [−1, 1] and C-space obstacles shown in Figure 1. The C-space obstacles are defined by two half circles centered at (0, −1) and (0, 1), respectively, both having radius 1−dt, where dt = 0.02. (I suggest making dt a parameter in your code. We will consider a similar configuration but with a different value of dt in the next assignment.) Anything within the two half circles are considered obstacle regions.The initial configuration is qI = (−2, −0.5) and the goal configuration is qG = (2, −0.5). Figure 1: The C-space and C-space obstacles.1. (10 points for COM S 4760, 7 points for COM S 5760) Exploring the C-space using RRT: Neglect the goal configuration. Use the Euclidean distance as the distance metric. Explore the C-space using RRT and plot the resulting tree in the C-space for the following cases.The result should be similar to Figure 2. (a) Neglect the obstacle and assume that Cfree = C. (b) Take into account the obstacles. Use a step size of 0.1 for collision checking.2. (10 points for COM S 4760, 7 points for COM S 5760) Solve the planning problem using RRT: Use the single-tree search outlined in Section 5.5.3. You should check periodically if the tree can be connected to qG. This can be easily done by setting α(i) as qG with a certain probability p. For example, the book recommends p = 0.01.You should have this as a parameter in your code. Once qG is successfully added to the tree, quit the loop and compute the path from qI to qG. Plot both the resulting tree and path. The result should be similar to Figure 3, which uses p = 0.1.Figure 2: The result of RRT exploration. The black lines are the edges in the tree. The blue cross and the blue dots are the initial and goal configuations, respectively. (top)Problem 1(a), and (bottom) Problem 1(b).3. (COM S 5760 only, 6 points) Solve the planning problem using PRM: Use the algorithm described in Figure 5.25 in the textbook. As for the number of nodes N, try a different value until you can solve the problem. When connecting to the nodes in the neighborhood, use Nearest K and set K = 15. Figure 4 shows a solution using N = 1000, including the roadmap and the path.Submission: Please submit a single zip file on Canvas containing the followings • your code (with comments, explaining clearly what each function/class is doing), • the plots from each of the problems, similar to Figure 2-4, and • a text file explaining clearly how to compile and run your code.Figure 3: The result of RRT planning with p = 0.1 as described in Problem 2, showing the tree and the path from qI to qG. Figure 4: The roadmap and the path from qI to qG using PRM with N = 1000.
Problem 3.1 (5 points) Define a semi-algebraic model that removes a triangular “nose” from the region shown in Figure 3.4.Problem 3.4 (5 points) An alternative to the yaw-pitch-roll formulation from Section 3.2.3 is considered here. Consider the following Euler angle representation of rotation (there are many other variants). The first rotation is Rz(γ), which is just (3.39) with α replaced by γ.The next two rotations are identical to the yawpitch-roll formulation: Ry(β) is applied, followed by Rz(α). This yields Reuler(α, β, γ) = Rz(α)Ry(β)Rz(γ). (a) Determine the matrix Reuler. (b) Show that Reuler(α, β, γ) = Reuler(α − π, −β, γ − π).Problem 3.7 (5 points) Consider the articulated chain of bodies shown in Figure 3.29. There are three identical rectangular bars in the plane, called A1, A2, A3. Each bar has width 2 and length 12. The distance between the two points of attachment is 10. The first bar, A1, is attached to the origin. The second bar, A2, is attached to A1, and A3 is attached to A2. Each bar is allowed to rotate about its point of attachment.The configuration of the chain can be expressed with three angles, (θ1, θ2, θ3). The first angle, θ1, represents the angle between the segment drawn between the two points of attachment of A1 and the x-axis. The second angle, θ2, represents the angle between A2 and A1 (θ2 = 0 when they are parallel).The third angle, θ3, represents the angle between A3 and A2. Suppose the configuration is (π/4, π/2, −π/4). (a) Use the homogeneous transformation matrices to determine the locations of points a, b, and c. (b) Characterize the set of all configurations for which the final point of attachment (near the end of A3) is at (0, 0) (you should be able to figure this out without using the matrices).Problem 3.14 (5 points) Develop and implement a kinematic model for a 2D kinematic chain A1, . . . , Am. Each link has the following properties: • W: The width of each link. • L: The length of each link. • D: The distance between the two points of attachment.Write a script named chain.py that takes above properties and the configuration of the chain and display the arrangement of links in the plane. The script should be executed using the following command: chain.py -W -L -D where = W, = L, = D, and specifies the angles that define the chain configuration.
Consider a mobile robot operating in a 2D world. The robot is modeled as a rigid body with a circular base of radius r. The robot can move in two ways:• Translation T(d): The robot can move along the direction specified by its current orientation, where d ∈ R is the distance parameter. A positive distance d > 0 indicates forward movement, while a negative distance d < 0 indicates backward movement.• Rotation R(θ): The robot can rotate in place by an angle θ around its center, where θ ∈ R is the rotation parameter. 1. (10 points for COM S 4760, 7 points for COM S 5760) Configuration Space: (a) Define the placement of the robot’s body frame and use it to derive a semialgebraic model of the robot.(b) Suppose the robot starts with its center at position (xi , yi) ∈ R 2 in the world frame, with orientation θi ∈ [0, 2π), measured with respect to the world frame. It then rotates counterclockwise by an angle θ using R(θ) and moves forward along the resulting orientation by distance d using T(d). Determine the region in the world occupied by the robot after this transformation.(c) Suppose the robot starts with its center at position (xi , yi) ∈ R 2 in the world frame, with orientation θi ∈ [0, 2π), measured with respect to the world frame. Now, suppose we want to move the robot so that its center is at (xg, yg) ∈ R 2 with an orientation θg ∈ [0, 2π) relative to the world frame.Describe a sequence of transformations T(d) and R(θ) that the robot can perform to achieve this, determining the values for the parameters d and θ in terms of xi , yi , θi , xg, yg, θg for each translation and rotation. Note that multiple translations and/or rotations may be required.(d) Describe the configuration space C of the robot and identify the mathematical structure (group) associated with C. Describe how each configuration is represented, i.e., identify the key parameters that uniquely define a configuration of the robot.2. (10 points for COM S 4760, 7 points for COM S 5760) C-Space Obstacles: The workspace, where the robot operates, is a rectangular area defined by the set [0, Xmax] × [0, Ymax], with the bottom-left corner at (0, 0) and the top-right corner at (Xmax, Ymax). The world contains a set O of circular obstacles, each defined by a tuple o = (xo, yo, ro) ∈ R 2 × R>0, where (xo, yo) is the position of the obstacle’s center and ro is its radius.(a) Describe the configuration space obstacle Cobs,o corresponding to each circular obstacle o = (xo, yo, ro) by identifying a closed form expression for a function f : C × R 2 × R>0 → R such that Cobs,o can be expressed as Cobs,o = {q ∈ C | f(q, xo, yo, ro) ≤ 0}.(b) Consider the area outside the workspace boundaries as an obstacle. Determine the complete configuration space obstacle Cobs, incorporating both the workspace boundaries and the circular obstacles within the workspace.3. (COM S 5760 only, 6 points) Discretized Workspace: Suppose Xmax and Ymax are natural numbers, and the workspace is discretized into a finite number of grid points, defined as W = {(x, y) | x ∈ {0, 1, . . . , Xmax}, y ∈ {0, 1, . . . , Ymax}}.The robot’s initial position and goal are always located at one of these grid points. Furthermore, the robot can only move between these points, transitioning only to directly neighboring points in the grid—either horizontally or vertically (but not diagonally)–using a combination of translation T(d) and rotation R(θ), where d, θ ∈ R.For example, suppose the robot is located at (1, 1) with orientation 0 (i.e., its heading aligns with the x-axis), it can move to (2, 1) or (1, 2), using the sequence of transformations derived in Problem 1c.For simplicity, when computing the configuration space C and the configuration space obstacle Cobs, consider only the configurations of the robot when its center is at a grid point.Although the robot moves continuously between these points, we will disregard its intermediate configurations and assume that collisions—whether with the workspace boundaries or circular obstacles—can only occur when the robot’s center is precisely at a grid point.(a) Assume that the robot is considered to have reached the goal as soon as its center is located at the goal grid point, regardless of its orientation. Given the described setup, is it possible to formulate a discrete motion planning problem for the robot? If so, describe the resulting state space X, the set of actions U, the action space U(x) for each state x ∈ X, and the state transition function f : X × U → X.(b) Given the following parameters: • Workspace dimensions: Xmax = 6 and Ymax = 5. • Robot radius: r = 0.5. • Set of circular obstacles: O = {o1, o2}, where – o1 = (3.0, 1.5, 1.12) represents an obstacle centered at (3.0, 1.5) with a radius of 1.12.– o2 = (2.5, 3.0, 0.5) represents an obstacle centered at (2.5, 3.0) with a radius of 0.5. List all the grid points in the workspace that the robot can safely occupy without causing a collision with either the workspace boundaries or circular obstacles. (c) Consider the same setup as in part (b). The robot’s initial position is (1, 1) with an orientation of π(i.e., 45 degree relative to the x-axis). Write a script main.py to compute a sequence of grid points for the robot to reach the goal located at (5, 3). You should be able to run the script with the following command: python main.pyThis should print out the sequence of grid points visited by the robot, starting at (1, 1) and ending at (5, 3).
1. (8 points) Consider a robot navigating a grid-like warehouse, represented as a 2D grid. Each location in the warehouse is identified by a coordinate (x, y), where x ∈ {0, 1, . . . , Xmax} represents the horizontal position (x-axis) and y ∈ {0, 1, . . . , Ymax} represents the vertical position (y-axis) for some natural numbers Xmax and Ymax.The robot can move in the following directions: • Up: This corresponds to adding 1 to the y-coordinate, • Down: This corresponds to subtracting 1 from the y-coordinate,• Left: This corresponds to subtracting 1 from the x-coordinate, or • Right: This corresponds to adding 1 to the x-coordinate.Some locations may contain obstacles, making them inaccessible to the robot. The goal is to compute an optimal path for the robot from a given starting location li = (xi , yi) to a given target location lg = (xg, yg), ensuring that the path is collision-free.The definition of “optimal” can vary depending on the criteria used. For each of the following criteria, your task is to• Identify the elements of the planning problem, including the state space X, the set U of actions, the action space U(x) for each state x ∈ X, the state transition function f, and if applicable, the transition cost.• Determine the most efficient algorithm for solving the problem based on the given criteria. Provide the time complexity of your chosen algorithm, and clearly state any assumptions made to derive the runtime.Criteria: (a) Minimizing the Number of Moves: Find a path that minimizes the total number of moves (or steps) required to reach the target location from the starting location.(b) Minimizing the Total Time: Find a path that minimizes the total time taken to reach the target location, considering that the time required for each move may vary depending on both the move and the location where it is made.(c) Minimizing the Total Cost: Each move has associated time and energy costs. Given a location l and a move m, let ctime(l, m) and cenergy(l, m) represent the time and energy, respective, for making a move m at location l. For a sequence of moves m1m2 . . . mk that leads the robot through the corresponding path p = l1l2 . . . lk+1, the total cost of the path is defined as c(p) = wtimeX k i=1 ctime(li , mi) + wenergyX k i=1 cenergy(li , mi), 1 where ctime and cenergy are non-negative functions and wtime, wenergy ∈ R≥0 are weights representing the relative importance of time and energy in the cost function.(d) (COM S 5760 only) Minimizing the Hierarchical Cost: In this scenario, time is considered to be strictly more important than energy. Therefore, you need to select a path that has the least energy consumption among all paths that achieve the minimum total time. Specifically, let Ptime denote the set of paths that minimize the total time taken to reach the target location. Then, select the one with the least energy consumption among all paths in Ptime.Hint: You do not need to explicitly identify the set Ptime. Instead, compute the optimal path directly by considering both time and energy costs in a hierarchical manner, where minimizing time is the primary objective and minimizing energy is the secondary objective among those time-optimal paths.2. (8 points) Implement 2 variants of forward search algorithm: breadth-first and A*.These algorithms will be used to solve discrete planning problems specified by classes that are derived from the following abstract base classes: • StateSpace Class: – Represents the set of all possible states in the problem. – Key methods: Let X be an instance of a class derived from StateSpace. ∗ x in X: Returns a boolean indicating whether the state x is in the state space X.∗ X.get distance lower bound(x1, x2): Returns a float representing the lower bound on the distance between the states x1 and x2• ActionSpace Class: – Defines the set of all possible actions at each state. – Key methods: Let U be an instance of a class derived from ActionSpace. ∗ U(x): Returns the list of all the possible actions that can be taken from the state x.• StateTransition Class: – Describes how the system transitions from one state to another based on an action. – Key methods: Let f be an instance of a class derived from StateTransition. ∗ f(x, u): Returns the new state obtained by applying action u at state x.Below is the implementation of these abstract base classes. Your implementation of the search algorithms should work with any derived classes that fully implement these methods.class StateSpace: “””A base class to specify a state space X””” def __contains__(self, x) -> bool: “””Return whether the given state x is in the state space””” raise NotImplementedError def get_distance_lower_bound(self, x1, x2) -> float: “””Return the lower bound on the distance between the given states x1 and x2 “”” return 0 class ActionSpace: “””A base class to specify an action space””” def __call__(self, x) -> list: “””Return the list of all the possible actions at the given state x “”” raise NotImplementedError class StateTransition: “””A base class to specify a state transition function””” def __call__(self, x, u): “””Return the new state obtained by applying action u at state x””” raise NotImplementedErrorTask: Implement the function fsearch(X, U, f, xI, XG, alg) where • X is an instance of a class derived from StateSpace and represents the state space. • U is an instance of a class derived from ActionSpace and specifies the action space.• f is an instance of a class derived from StateTransition and specifies the state transition function. • xI is an initial state such that the statement xI in X returns true.• XG is a list of states that specify the goal set. You can assume that for each state x in XG, the statement x in X returns true. However, XG may be empty. • alg is a string that specifies the discrete search algorithm to use ( “bfs” or “astar”).The function fsearch(X, U, f, xI, XG, alg) should return a dictionary with the following structure: {“visited”: visited states, “path”: path} where visited states is a list of states visited during the search, in the order they were visited and path is a list of states representing a path from xI to a state in XG.• Do NOT implement each algorithm as a separate function. Instead, you should implement the general template for forward search (See Figure 2.4 in the textbook). Then, implement the corresponding priority queue for each algorithm.Hint: The only difference between different algorithms is how an element is inserted into the queue. So at the minimum, you should have the following classes (You can name them differently):– Queue: a base class for maintaining a queue, with pop() function that removes and returns the first element in the queue. You may also want this class to maintain the parent of each element that has been inserted into the queue so that you trace back the parent when computing the path from xI to a goal state in XG.– QueueBFS and QueueAstar: classes derived from Queue and implement insert(x, parent) function for inserting an element x with parent parent into the queue.With the above classes, you can implement a function get queue(alg, X, XG) that returns an appropriate queue Q for the given search algorithm alg and containing insert and pop functions (and possibly some other functions, e.g., for computing a path). Note that X and XG may be needed to construct the queue for “astar” algorithm since X provides the get distance lower bound function. Together with XG, you can implement a function to compute the lower bound on the distance between any given state x to a state in the goal set XG. You can then use this Q in the fsearch function.• Following the previous bullet, there should be only one conditional statement for the selected algorithm (“bfs”, “dfs”, or “astar”)) in the entire program. Points will be deducted for each additinoal conditional statement.• For A*, assume that the cost of each transition is 1, i.e., cost-to-come to state x 0 is given by C(x 0 ) = C(x) + 1 where x is the parent of x 0 .• Your implementation should work for any classes derived from StateSpace, ActionSpace, and StateTransition, provided that all the abstract methods are correctly implemented in these derived classes. So you should not assume, e.g., that a state will be of any particular form.• Your implementation should be able to handle corner cases, including but not limitted to the case where XG is empty, in which case “visited” may be either the entire state space or empty.• Please feel free to use external libraries, e.g., for heap, queue, stack or implement them yourself.3. (4 points) Let’s revisit Problem 1. Suppose the grid is of size 5 × 5, i.e., Xmax = Ymax = 4. The robot starts at location li = (0, 0) and needs to reach the target location at lg = (4, 4). The obstacles are located at the following coordinates: • (1, 3) • (2, 3) • (1, 2) • (1, 1) • (2, 1) • (3, 1)Task: • Implement the derived classes of StateSpace, ActionSpace, and StateTransition for this warehouse navigation problem. • Write a script main.py that uses these derived classes, along with your implementation from Problem 2, to compute a path that minimizes the number of moves. You should be able to run the script with the following command: python main.py This should print out the required path.
5/5 - (1 vote) Implement the PERT algorithm discussed in class. Starter code (PERT.java) provided.Implement all the methods in the starter code. Write additional methods if needed.Driver code (P4Driver) and test cases are all also provided. (See project 4 folder in the shared box folder.)Do not change the name of the class.Do not modify Graph class other than changing the netid.Do not change the signatures of public methods in the starter code.If you need additional classes, define them as nested classes of PERT.You must write the DFS-based algorithm for finding a topological order.Your code should be well structured and commented properly. Please follow format specified in Javadoc.Follow the submission below.IF YOU DID NOT FOLLOW THE SUBMISSION PROCEDURE, 10 POINTS WILL BE DEDUCTEDSubmission procedure:* Create a folder whose name is your netid (Nid). The name should be in lower case.* Place PERT.java, and Graph.java in that folder.* Use “package Nid;” in all your java files. Nid should be in lower case* package name and folder name should exactly match* Zip the contents into a single zip file.* If the zip file is bigger than 1 MB, you have included unnecessary files.* Delete them and create the zip file again.* Upload the zip file on elearning.* Submission can be revised before the deadline.* The final submission before the deadline will be graded.Rubric:Code review: 50 pointsTest cases: 40 pointsStyle: 10 points
Implement the following operations. Starter code is provided. Do not change the name of the class. Do not change the signatures of public methods in the starter code. Few testcases and verbose output for some of the testcases are also provided. Check ‘P3’ folder in the shared box folder.Multi-dimensional search: Consider the web site of a seller like Amazon. They carry tens of thousands of products, and each product has many attributes (Name, Size, Description, Keywords, Manufacturer, Price, etc.). The search engine allows users to specify attributes of products that they are seeking, and shows products that have most of those attributes. To make search efficient, the data is organized using appropriate data structures, such as balanced trees. But, if products are organized by Name, how can search by price implemented efficiently?The solution, called indexing in databases, is to create a new set of references to the objects for each search field, and organize them to implement search operations on that field efficiently. As the objects change, these access structures have to be kept consistent.In this project, each object has 3 attributes: id (int), description (zero or more ints), and price (int). The following operations are supported:a. Insert(id,price,list): insert a new item whose description is given in the list. If an entry with the same id already exists, then its description and price are replaced by the new values, unless list is null or empty, in which case, just the price is updated. Returns 1 if the item is new, and 0 otherwise.b. Find(id): return price of item with given id (or 0, if not found).c. Delete(id): delete item from storage. Returns the sum of the ints that are in the description of the item deleted (or 0, if such an id did not exist).d. FindMinPrice(n): given an integer, find items whose description contains that number (exact match with one of the ints in the item’s description), and return lowest price of those items. Return 0 if there is no such item.e. FindMaxPrice(n): given an integer, find items whose description contains that number, and return highest price of those items. Return 0 if there is no such item.f. FindPriceRange(n,low,high): given int n, find the number of items whose description contains n, and in addition, their prices fall within the given range, [low, high].g. RemoveNames(id, list): Remove elements of list from the description of id. It is possible that some of the items in the list are not in the id’s description. Return the sum of the numbers that are actually deleted from the description of id. Return 0 if there is no such id.Implement efficiently the above operations using data structures that are best suited for the problem.Input specification: Initially, the store is empty, and there are no items. The input contains a sequence of lines (use test sets with millions of lines). Lines starting with “#” are comments. Other lines have one operation per line: name of the operation, followed by parameters needed for that operation (separated by spaces). Lines with Insert operation will have a “0” at the end, that is not part of the name. The output is a single number, which is the sum of the following values obtained by the algorithm as it processes the input.Sample input: Insert 22 19 475 1238 9742 0 # New item with id=22, price=”$19″, name=”475 1238 9742″ # Return: 1 # Insert 12 96 44 109 0 # Second item with id=12, price=”96″, name=”44 109″ # Return: 1 # Insert 37 47 109 475 694 88 0 # Another item with id=37, price=”47″, name=”109 475 694 88″ # Return: 1 # FindMaxPrice 475 # Return: 47 (id of items considered: 22, 37) # Delete 37 # Return: 1366 (=109+475+694+88) # FindMaxPrice 475 # Return: 19 (id of items considered: 22) # EndOutput: 1435
There are two parts in this project1. Implement binary search trees. Starter code BinarySearchTree.java is in the shared folder. The methods you need to implement are: contains(), add(), remove(). Other methods are optional. Do not define parent field in Entry class. IMPLEMENT the single pass algorithm discussed in the class.2. Extend BST to AVL tree. Starter code: AVLTree.java is in the shared folder. Driver code is also provided. The methods you need to implement are: add(), verify.Implement remove() for extra credits (20 points). Do not rewrite the code for find(), add(), and remove(). Inherit the methods from BinarySearchTree class.The number of rotations required during deletion could be O(log n). We may have to do rotation at every level. For more details, check this https://webdocs.cs.ualberta.ca/~holte/T26/tree-deletion.htmlStarter code BinarySearchTree.java, AVLTree.java, AVLTreeDriver.java, Timer.java are in folder project2 which is in the shared box folder. Some testcases are also provided. You should also write your own testcases. We may test your code with additional testcases.Rubric: Code review: 40 points Testcases: 50 points Style: 10 points If you do not follow the submission procedure, we will deduct 10 points.
5/5 - (1 vote) In this project, you will be using stacks to parse/evaluate arithmetic expressions.This is an individual project. Do not share your work with others. Do not refer or use any material from external sources other than the materials provided in the class and in the references below..ANY ACT OF PLAGIARISM WILL BE REPORTED.Read this project specification carefully.Algorithms to parse infix expressions was discussed in the class. Algorithms to evaluate postfix expressions, and to evaluate expression tree will be discussed in the class next week.Use ArrayDeque from the Java library for the stacks. Do not code your own stack.Starter code Expression.java and few testcases are provided in the box folder.Add additional fields, methods, classes as needed.Do not change the name of the class or signatures of public methods.Your code should be well structured and commented properly. Please follow format specified in Javadoc.10 points are allocated for style and comments.The following methods need to be completed. No error checking is required.If the expressions passed are valid, then the methods should work correctly.Given invalid expressions, your program can return wrong values, print error messages,or throw exceptions.Method to convert String to a Token:The string holds exactly one token, with no extra spaces before or after the token.Possible tokens are: Operators: PLUS (“+”), TIMES (“*”), MINUS (“-“), DIV (“/”), MOD (“%”), POWER (“^”) Parentheses: OPEN (“(“), CLOSE (“)”) Number: NUMBER (any valid string that represents an integer) Assume that if a token is not an operator or a parenthesis, then it is a number. Use Long.parseLong(tok) to convert string to long. Signature: static Token getToken(String tok) { … } Tokens have a field “priority” that can be used to store precedence of operators during parsing. Precedence: {^} > {*, /, %} > {+, -}. Assume that all operators are left associative. Assign your own values to priority of tokens. Field “number” is used to store the value of NUMBER token. A token “NIL” is defined for internal use and it does not correspond to any token in the expressions. It is a convenient token to mark bottom of stack.Method to convert an infix expression given as a list of tokens into an expression tree: Given an infix expression as a list of tokens, return its corresponding expression tree. Signature: public static Expression infixToExpression(List exp) { … }Method to convert an infix expression into a postfix expression: Given an infix expression as a list of tokens, return its equivalent postfix expression. Signature: public static List infixToPostfix(List exp) { … }Method to evaluate a postfix expression: Given a postfix expression, evaluate it and return its value. Signature: public static long evaluatePostfix(List exp) { … }Method to evaluate an expression tree: Given an expression tree, evaluate it and return its value. Signature: public static long evaluateExpression(Expression tree) { … }Submit the completed Expression.java file on elearning.References:1. https://docs.oracle.com/en/java/javase/20/docs/api/java.base/java/util/ArrayDeque.html2. https://docs.oracle.com/javase/tutorial/collections/index.html3. https://en.wikipedia.org/wiki/Javadoc
