Have you ever played the card game called “patience†(also known as “solitaireâ€)? In this homework you will use the same idea of that famous card game to help you sort a list of numbers in ascending order. The pile of cards will be replaced by the input array with the numbers to be sorted. Below is an example that shows how the “patience sort†algorithm works. Basically it uses stacks of numbers in descending order. In case there isn’t a stack available, the algorithm creates a new stack. |Stack|Input Array| |—–|—–| ||[13, 12, 84, 79, 10, 77, 56, 1, 34, 27, 3]| |13|[12, 84, 79, 10, 77, 56, 1, 34, 27, 3] | |13 12|[84, 79, 10, 77, 56, 1, 34, 27, 3] | |13 84 12|[79, 10, 77, 56, 1, 34, 27, 3] | |13 84 12 79|[10, 77, 56, 1, 34, 27, 3] | |13 84 12 79 10|[77, 56, 1, 34, 27, 3] | |13 84 12 79 10 77|[56, 1, 34, 27, 3] | |13 84 12 79 10 77 56|[1, 34, 27, 3] | |13 84 12 79 10 77 1 56|[34, 27, 3] | |13 84 12 79 10 77 1 56 34|[27, 3] | |13 84 12 79 10 77 1 56 34 27|[3] | |13 84 12 79 10 77 1 56 34 27 3|[]| Once the algorithm finishes reading the input array, it just needs to merge the stacks in order to generate the final output. That part of the code is given to you. Get the code template from our GitHub repository and finish the TO-DO’s. Submission You only need to submit the PatienceSort.java source code this time.
In this lab activity you will work in pairs. One of you will be responsible for implementing the Bee class, while the other will write the code for the BeeDriver class. Bee Class a Bee has a type, which can be 0 (for workers), 1 (for drone), and 2 (for queen); define class constants for the type of bees; a Bee always belongs to a beehive identified by a name; a Bee has a location defined by two integers x and y; there should be two ways to create a Bee object: one that takes a beehive name and another one that takes a beehive name and a type; if the type of a bee is not specified (or invalid), assume that the bee is a worker bee; bees are always created at location (0, 0), which means that they are created inside the beehive; define getter methods for your Bee class; create a private helper method called getTypeAsString that returns the type of the bee as a String; use this method in toString; define a move method that accepts new coordinates for the bee; define a isInsideHive method that returns true/false depending on whether the bee is inside the hive (x = 0 and y = 0) or outside, respectively; override the toString method returning an appropriate String from the object; see example output below for * two bees from the “Crazy for Nectar†beehive (as you can see, if the bee is inside the beehive its coordinates should not be displayed): worker from “Crazy for Nectar” is outside the hive @ (150, 200) drone from “Crazy for Nectar” is inside the hive! BeeDriver Class Note that you are NOT supposed to implement the Bee class! Just ignore the errors you will get saying that the Bee class is not defined. You can take a look at the Bee class definition to figure it out the interface you should expect (i.e., which method should be available for you to use). If in doubt, ask your teammate for clarification. Next, move all bees to random locations in the square defined by the left upper corner [-10, 10] and the right bottom corner [10, -10]. Right after you moved each bee, print information about it using the toString method implicit call. When you are done, ask your partner to share their Bee class code so you can incorporate it in your program. You and your teamate should work together and make any necessary adjustments so the BeeDriver application works properly.Rubric +2 Bee class meets the specifications +2 BeeDriver class meets the specifications +1 BeeDriver class works with the Bee class according to the specfications
Although the sorting algorithms discussed in class all used collection of numbers, any type of objects can also be sorted. For that to be possible, there should be a way to determine how 2 given objects should be compared. Java has an interface called Comparable that defines the following method: public int compareTo(Object other); compareTo should be overriden by the user-defined class in the following way: a.compareTo(b) returns < 0 if a < b a.compareto(b) returns 0 if a = b a.compareTo(b) return > 0 if a > b In this assignment you are asked to override compareTo in InstagramUser. Then adapt quick sort so it would work with an array of objects. Follow the TO-DOs in the given source code and submit InstagramUser class when you are done.
Objective: This objective of this laboratory experiment is to design and construct an Arithmetic and Logic Unit (ALU) in VHDL environment and implement it on an FPGA board. • Design and build all functions of the ALU. • Design, simulate the ALU using VHDL (Based on Functional Simulation in Quartus Simulator). Procedure: This unit consists of different parts that would come together to create a functional ALU. A processing unit is usually divided to 4 distinct components. The control unit performs the fetching of instructions and signals. The bus controls access to data values throughout the processing unit – these registers act as temporary storage units. The ALU Core performs the arithmetic and logical operations on desired inputs and produces the required outputs. This project focuses on all four components of a typical ALU. Part I: Procuring input data The ALU is to perform a set of arithmetical and logical functions on two 8-bit inputs A and B. These inputs are first utilized in simulation phase through waveform editor on Quartus II, Inputs A and B are procured using the last four digits of your student ID. For instance, if the student ID is 500864395, then translating toFigure 1. The Block Diagram of the GPU Part II: Storage Unit (Register) The storage units which are sometimes called Registers are utilized to temporary store the input values and then pass them to the following components in the system. As portrayed in Figure 1, two 8-bit register units are utilized in the ALU to store inputs A and B. The register reads the bit values on its input on the rising edge of the clock signal and passes those bit values to the output port on the next rising edge of the clock signal. Write the VHDL code using Figure 2 for a register unit and confirm its functionality with the help of a truth table. Thereafter, create a symbol of your design to be utilized in the final circuit design. Next, import the symbol to the GPU project. Import the same symbol twice as the system needs one register unit for each respective 8-bit input.Figure 2. Code template for implementing Register Storage Unit. Part III: Control Unit The Control unit decides the microcode that is to be delivered to the ALU core and will act as the operations-selector for the ALU core. The Control Unit produces an output OP, which is passed to ALU core as the operations selector. This component consists of two sub-components – the FSM and a 4 to 16 decoder. Part III (a): Finite State Machine (FSM) In the initial design of the Control unit, the current state of the FSM is to be passed to the decoder unit. In other words, the FSM sub-component in the initial Control unit design will only act as an up-counter, cycling through states 0 to 8 consecutively (modification required for consecutive state transition) and back to state 0 while the student_id will be displayed on a 7segment. The FSM takes the clock signal as the input, and produces the 4-bit output current_state and passes it to the decoder sub-component. Upon completing the FSM design, create a symbol representing the FSM sub-component which is to be used in the final design. Part III (b): 4 to 16 Decoder (4×16 Dec) The decoder is tasked with receiving the signal current_state from FSM and decoding it to the operation-selector microcode. In the initial design of the Control unit, the Decoder unit passes the signal OP to the ALU core, which will then translate to operations selector for the ALU core and follow the functions enlisted in Table 1. A 3×8 decoder design has been designed and utilized in the previous labs. You can import the same design and extend it to the 4×16 decoder following the schematics portrayed in Figure 2. When the decoder design is completed, create a symbol of the sub-component to be utilized in the final circuit design.Figure 3. Implementation of 4×16 Decoder using 3×8 decoders Part IV: Description of the ALU core The heart of every GPU unit is the ALU core where all arithmetic and logical operations are to be implemented and applied as required. In this part students are required to implement all functionalities and operations using VHDL syntax compatible with Altera FPGA boards. The ALU core will take two 8-bit inputs (A and B) and a 16-bit input from Control unit. The microcode input from controller unit is the operation-selector signal, deciding the operation that is to be applied on the inputs A and B. Although the microcode received from the Control unit is 16 bits, only 9 distinct operations are to be implemented. The functionalities of the ALU core and their corresponding microcode are listed in Table 1. The microcode is delivered from the Control unit and will decide what operation the inputs would undergo. Operations listed in Table 1 are to be implemented in the ALU core by writing the proper VHDL code for the ALU core. The 8-bit output (Result) of the ALU Core is to be displayed on two 7segment display or LEDs. When the ALU Core design is completed, create a symbol to represent this component in the final design.Table 1. ALU Core Operations for Problem 1Figure 4. Code Template for ALU Core. Part V: Displaying the Output The ALU core produces an 8-bit output called Result, which is the result of the operations applied on A and B. In the simulation phase of the design, the output Result is to be displayed in bit-value format in the waveform editor window. In implementation phase where the design is programed on the FPGA board, this output is to be displayed on two 7-segment displays in hexadecimal format. For example, if then the 7-segment combined unit displays as illustrated in Figure 4.Figure 5. Typical 8-bit Seven Segment Display Part VI: Final Design As the designs for different components (Register, ALU Core, FSM and Decoder units) are completed, they should all be ported to one final circuit design. 1. Open a new schematic design and import all the required units. When importing is completed, you should have the following components: two Registers (one per input), one ALU Core, one FSM, Decoder, three 7-segment displays (one for student_id and two for the output Result from the ALU). 2. Create the 8-bit input ports A and B, 8-bit output port Result and the single-bit input Clock port. 3. Connect all the components using single and multi-bit data buses. Follow the schematics portrayed in Appendix A. Figure 6. 4. Name the data buses to represent the proper signals, for e.g. OP and A. Part VIII: Problem Sets Problem 1: Initial Design Implement the initial design of the General Processor Unit (GPU). In this design, the FSM output current_state follows an up-counting pattern, which will then dictate the operation selector signal to the ALU core. Thus, the output of the ALU core, Result, will represent the outputs of operations shown in Table 1 and following the same order. Problem 2: Modified ALU Core Function # Operation / Function 1 Increment A by 2 2 Shift B to right by two bits, input bit = 0 (SHR) 3 Shift A to right by four bits, input bit = 1 (SHR) 4 Find the smaller value of A and B and produce the results ( Min(A,B) ) 5 Rotate A to right by two bits (ROR) 6 Invert the bit-significance order of B 7 Produce the result of XORing A and B 8 Produce the summation of A and B, then decrease it by 4 9 Produce all high bits on the output b) Function # Operation / Function 1 Swap the lower and upper 4 bits of A 2 Produce the result of ORing A and B 3 Decrement B by 5 4 Invert all bits of A 5 Invert the bit-significance order of A 6 Find the greater value of A and B and produce the results ( Max(A,B) ) 7 Produce the difference between A and B 8 Produce the result of XNORing A and B 9 Rotate B to left by three bits (ROL) c) Function # Operation / Function 1 Produce the difference between A and B 2 Produce the 2’s complement of B 3 Swap the lower 4 bits of A with lower 4 bits of B 4 Produce null on the output 5 Decrement B by 5 6 Invert the bit-significance order of A 7 Shift B to left by three bits, input bit = 1 (SHL) 8 Increment A by 3 9 Invert all bits of B d) Function # Operation / Function 1 Shift A to right by two bits, input bit = 1 (SHR) 2 Produce the difference of A and B and then increment by 4 3 Find the greater value of A and B and produce the results ( Max(A,B) ) 4 Swap the upper 4 bits of A by the lower 4 bits of B 5 Increment A by 1 6 Produce the result of ANDing A and B 7 Invert the upper four bits of A 8 Rotate B to left by 3 bits (ROL) 9 Show null on the output e) Function # Operation / Function 1 Replace the odd bits of A with odd bits of B 2 Produce the result of NANDing A and B 3 Calculate the summation of A and B and decrease it by 5 4 Produce the 2’s complement of B 5 Invert the even bits of B 6 Shift A to left by 2 bits, input bit = 1 (SHL) 7 Produce null on the output 8 Produce 2’s complement of A 9 Rotate B to right by 2 bits (ROR)f) Function # Operation / Function 1 Decrement B by 9 2 Swap the lower and upper 4 bits of B 3 Shift A to left by 2 bits, input bit = 0 (SHL) 4 Produce the result of NANDing A and B 5 Find the greater value of A and B and produce the results ( Max(A,B) ) 6 Invert the even bits of B 7 Produce null on the output 8 Replace the upper four bits of B by upper four bits of A 9 Show A on the output g) Function # Operation / Function 1 Invert the bit-significance order of A 2 Shift A to left by 4 bits, input bit = 1 (SHL) 3 Invert upper four bits of B 4 Find the smaller value of A and B and produce the results ( Min(A,B) ) 5 Calculate the summation of A and B and increase it by 4 6 Increment A by 3 7 Replace the even bits of A with even bits of B 8 Produce the result of XNORing A and B 9 Rotate B to right by 3 bits (ROR) h) Function # Operation / Function 1 Rotate A to right by 4 bits (ROR) 2 Produce the result of XORing A and B 3 Invert the bit-significance order of B 4 Calculate the summation of A and B and decrease it by 2 5 Rotate B to left by 2 bits (ROL) 6 Invert the even bits of B 7 Swap the lower 4 bits of B with lower 4 bits of A 8 Shift B to right by 2 bits, input bit = 0 (SHR) 9 Invert lower four bits of A Problem 3: Modified Control Unit (FSM) a) For each microcode instruction, display ‘y’ if the FSM output (student_id) is odd and ‘n’ otherwise b) For each microcode instruction, display ‘y’ if the FSM output (student_id) is even and ‘n’ otherwise c) For each microcode instruction, display ‘y’ if the FSM output (student_id) had an odd parity and ‘n’ otherwise d) For each microcode instruction, display ‘y’ if the FSM output (student_id) had an even parity and ‘n’ otherwise e) For each microcode instruction, display ‘y’ if one of the 2 digits of A are greater than FSM output (student_id) and ‘n’ otherwise. Use the microcode instruction from part 1 of the lab. f) For each microcode instruction, ‘y’ if one of the 2 digits of A are less than FSM output (student_id) and ‘n’ otherwise. Use the microcode instruction from part 1 of the lab. g) For each microcode instruction, ‘y’ if one of the 2 digits of A are equal to FSM output (student_id) and ‘n’ otherwise. Use the microcode instruction from part 1 of the lab. h) For each microcode instruction, display ‘y’ if one of the 2 digits of B are greater than FSM output (student_id) and ‘n’ otherwise. Use the microcode instruction from part 1 of the lab. i) For each microcode instruction, ‘y’ if one of the 2 digits of B are less than FSM output (student_id) and ‘n’ otherwise. Use the microcode instruction from part 1 of the lab. j) For each microcode instruction, ‘y’ if one of the 2 digits of B are equal to FSM output (student_id) and ‘n’ otherwise. Use the microcode instruction from part 1 of the lab. Appendix AFigure 6. Typical Block Schematic for Problem 1 Figure 7. Typical Block Schematic for Problem 3
1 Objectives To construct combinational circuits and circuits with basic storage elements using VHDL 2 Pre-Lab Preparation 1. Start-up Quartus II. This window gives you access to an integrated suite of CAD tools 2. To save files for this lab, create subdirectories mux, decode, encod, and johns in your work directory. 3. Enter the name of the first project, mux, by clicking on File then Project on the pull down menu and then Name on the subsequent pull down menu. Type the Project Name, and click OK. 4. Open Text Editor and type the VHDL file from Figure 6.28 of the textbook. Save the file as mux.vhd. 5. Start the compiler. Fix any errors and re-compile. Once the file compiles without errors, go to the next step. Copy the file mux.vhd to a usb drive 6. Repeat steps 3-5 for the remaining examples. Use files from the following figures accordingly (see textbook): i. decod – Figure 6.30 ii. encod – Figure 6.41 iii. johns – Figure 2 (In this Manual) 7. The last example shows one of the ways of implementing the Johnson counter. The last six digits of the student identification number must be represented by a four-bit vector variable STUDENT_ID which will be displayed cyclically in sequence with Johnson counter output. Qreg is an internal signal which can be fed back to the D’s or fed out to Q. 8. Prepare a Truth Table for Johnson Counter for 6 clock cycles. 3 Laboratory Work 1. Create the subdirectory lab4 in your work directory, and copy the all the subdirectories created as part of pre-lab to this subdirectory. 2. Compile your designs and create symbols for respective projects (mux, decode, encod, and johns) and save them. 3. Create new subdirectories inside lab4 folder of your working directory with names muxModified and decodModified. 4. Start-up Quartus II. This window gives you access to an integrated suite of CAD tools 5. Enter the name of the project, muxModified, by clicking on File then Project on the pull down menu and then Name on the subsequent pull down menu. Type the Project Name at top, and click OK. 6. Create a block schematic file muxModified.bdf for the project defined in (12) and implement a 4:1 multiplexer using two 2:1 multiplexer (mux symbols) as shown in Figure 6.3 of the text book. 7. Repeat the steps 11-13 for the project decodModified and implement a 3:8 decoder using two 2:4 decoders (decode symbols) as outlined in Figure 6.17 of the text book. 8. The circuit design must handle non-valid states and non-valid student identifier cases by displaying an “E” in the seven segment display on your simulated waveforms. 9. Consider the last 6 digits of the student identifier D = {d1, d2, d3, d4, d5, d6} in its general representation. Then, as an example, a student with identifier: 500435429 will follow the display sequence as 435429.LIBRARY ieee; USE ieee.std_logic_1164.all; ENTITY johns IS PORT (Clrn, E, Clkn : IN STD_LOGIC; –clrn is your reset button STUDENT_ID : out std_logic_vector(3 downto 0); Q : OUT STD_LOGIC_VECTOR (0 TO 2)); END johns; ARCHITECTURE Behavior OF johns IS signal Qreg : STD_LOGIC_VECTOR (0 TO 2); BEGIN PROCESS (Clrn, Clkn) BEGIN IF Clrn = ‘0’ THEN Qreg
1 Objectives • To design and build a 4-bit Adder/Subtractor unit (ASU) using an Altera CPLD chip. • To design the Adder/Subtractor unit that multiplexes add and subtract operations with a common Cin input. • To implement the 4-bit ASU using VHDL coding. • To design a Combinational Circuit that takes the decoded output of ASU as input. This Combinational Circuit will have the design logic to output individual digits of the Student Identification number of the student performing laboratory work. Pre-Lab Preparation 2 1. Modify the VHDL code from Figure 5.28 (see course text) to implement the ASU represented in Figure 5.13 (see course textbook). Create a file ASU.vhd to accomplish this task. Note: change ieee.std_logic_signed.all to ieee.std_logic_unsigned.all. 2. Copy the code that implements a 4 bit-to-7-segment converter from Figure 6.47 (course textbook) into a file sseg.vhd. 3. Modify the code in file sseg.vhd to represent the sequence 0-F on a seven segment display. It must also be able to show the sign ( – ) in case of negative numbers. 4. Minimize the logic expressions for your customized L3, L2, L1 and L0 -signals. These minimized logic expressions are to be implemented as outputs of the combinational circuit C in Figure 2 (shown below). 5. Create a new VHDL file C.vhd to implement the minimized logic expressions for the L3, L2, L1 and L0 signals that correspond to a 4-bit representation of your student identification number. The minimized logic expressions for these signals can be generated using K-Maps and converting each of the resulting expressions to VHDL code. 6. Using the Functional Simulator (waveforms), verify the circuit described by the VHDL file obtained in step 3. By setting values for X3, X2, X1, X0, Y3, Y2, Y1, Y0 and Cin, observe the following signals: S3, S2, S1, S0and Cout. This ensures that two displays will show the signed sum. 3 Laboratory Work The procedure is divided into two parts: Part A. 1. This part must be completed during the week 1 of this lab experiment. 2. Compile your modified 4-bit Adder/Subtractor unit (ASU) file ASU.vhd and create a symbol file ASU.bsf 3. Compile your seven segment code sseg.vhd as a separate project and create a symbol file sseg.bsf 4. Start a new Project CombinedASU1 and create a block schematic file CombineASU1.bdf. 5. Import the symbols ASU and sseg into the block schematic file CombinedASU1.bdf. 6. Complete the wiring and pin assignments by following the connections described inthe Figure 1 (Typical Schematic generated using Quartus II depicted in ).Table 1. . 4-bit Student ID generated by combinatorial logicFigure 1. Block Diagram for PART A implementation Part B. 1. This part must be completed during the week 2 of this lab experiment. 2. Consider the 9 digits of the student identifier D = {d1, d2, d3, d4, d5, d6, d7, d8, d9} in its general representation. Write a table that represents each digit of your student ID in four bits. For example, if a student’s ID is: 111726015, it will likely follow a 4-bit sequence {0001, 0001, 0001, 0111,……, 0101} as depicted in Table 1. 3. Compile your customized Combinatorial Unit C.vhd and create a symbol file c.bsf 4. Start a new Project CombinedASU2 and create a block schematic file CombineASU2.bdf.Figure 2. Block Diagram for PART B implementation 5. Import the symbols ASU, combinatorial and sseg (refer Part A) into the block schematic file CombinedASU2.bdf. 6. Complete the wiring and pin assignments by following the connections described in the Figure 2 (Typical Schematic generated using Quartus II depicted in ). Appendix AFigure 3. Typical Block schematic for PART A & B implementation using Quartus II
1 Objectives • To simulate and verify the operation of a sequential circuit. • To learn the difference between Mealy and Moore machines and express the FSMs with different state assignments. 2 Pre-Lab Preparation 3. Design the logic equations for each of the Flip-Flop inputs described in Figure 3. 5. Create a file lab5.vhd. 3 Laboratory Work 1. Create the subdirectory lab5 in your work directory, and copy the file lab5.vhd to the subdirectory. 2. Consider the 9 digits of the student identifier D = {d1, d2, d3, d4, d5, d6, d7, d8, d9} in its general representation. Then, as an example, a student with identifier: 500435429 will follow the sequence as in Table 1. 3. The corresponding Mealy/Moore machine state diagrams for representing student ID in Table 1 is depicted as in Figure 2. Your circuit design must handle non-valid states and non-valid student identifier cases by displaying an “E” in the seven segment display. 4. Modify and compile your design (Figures 4 and 5). NOTE: Re-use the 7-segment module from Lab3 to display states and student identifier digits. 2 | P a g e student_id_digit_1 d1 5 student_id_digit_2 d2 0 student_id_digit_3 d3 0 student_id_digit_4 d4 4 student_id_digit_5 d5 3 student_id_digit_6 d6 5 student_id_digit_7 d7 4 student_id_digit_8 d8 2 student_id_digit_9 d9 9 Table 1 Digits Representing Student Identification numberFigure 1 State Diagram AssignmentsFigure 2 FSM Types for Representing Student Identification NumberFigure 3 Finite State MachineFigure 4 VHDL Code Template An example of the connections in the block diagram is represented in Figure 5Figure 5 Block Diagram for FSM
Overview The setting for this project is that an e-puck robot is navigating a maze to find a traffic sign. You are provided code that will determine whether the traffic sign is in the camera feed of the robot. Your task will be to determine: 1. The depth (not the distance) and angle to the sign using the 2-cameras method 2. The distance and angle to the sign using camera+lidar method In the second part, you will leverage the lidar on the robot to determine the distance and heading, using both the point cloud of the lidar, and one image captured by the robot. The lidar data is composed of an array of 360 distance values around the robot, one for each degree for 0 to 359 deg.Webots Simulator We will be employing the Webots simulator in this project (and in some of the future projects in this course). You will need to install it using the following installation procedure (this includes documentation for Linux, Windows, and Mac). You will be provided with a series of world files and a controller for the e-puck robot. The assignment will then require finding the distance/depth and heading of a traffic sign, relative to the robot, in each world file. The code structure and respective functions is described in the next section. To test out your scripts in the Webots simulator, open a world file (named either as proj2_world_vision_lidar_#.wbt or as Vision_only_world#.wbt), and run the simulation. The first few (typically 3) iterations running the controller might have blank images, however it should then allow you to see the required distance/ depth and angle values print on the Webots console.Requirements Installation You can use the requirements.txt file to install all necessary packages by running pip install -r requirements.txtAssignment Preliminaries The field of view is the range of the world (in this project, defined in radians) in the horizontal plane that is visible.We provide the following formula that can be used to include the field of view in the calculation of focal length for both parts 1 and 2. focal_length = image_width / (2 * math.tan(fov / 2))Part 1: Determine depth and angle using stereo vision To complete part 1, you will need to fill out the vision_only_depth_calculation(image1, image2, fov, camera_translation) function in proj2_vision_only_controller/vision_only_calculation.py The vision_only_depth_calculation(image1, image2, fov, camera_translation) function takes in two images, camera field of view, camera translation (distance between the 2 cameras) and returns the depth (perpendicular distance from the traffic sign to the line joining the cameras) and angle from the robot to the traffic sign in the images.Hint: try using trigonometry to calculate the angle, using the parameters mentioned in the diagram above.Part 2: Determine distance and angle using vision and lidar To complete part 2, you will need to fill out the vision_lidar_distance_calculation(image, lidar_range_array, fov) function in proj2_vision_lidar_controller/vision_lidar_calculation.py The vision_lidar_distance_calculation(image, lidar_range_array, fov) function takes in an image and the point cloud returned from a lidar, and returns the distance and angle from the robot to the traffic sign in the images.Functions Provided To complete the above two parts, you are provided with the contour.py file, which contains a function box_measure(image) that calculates the pixel values of the centroid of the identified traffic sign in the image. This file (identical copies) can be found in both the proj2_vision_lidar_controller and the proj2_vision_only_controller folders. Submission Instructions The files you will submit to Gradescope are vision_lidar_calculation.py and vision_only_calculation.py To test your solution locally, you can employ the provided local_tests.py files.– NumPy – OpenCVRubric for Vision Component Your solution for part 1 (stereo vision) will be evaluated in 5 world files. Each world will be worth 10 points for a total of 50 points possible. Depth Evaluation For each world, you will receive a number of points based upon how close your detected depth is from the true depth. The difference between your depth and the true depth will be evaluated as a percentage of the true depth. For example, if the true depth is 10 cm and you say that the depth is 9 cm, then the difference is 1 cm. This is 10% of the true 10 cm, so the grade would be 8 out of 10 for that world file. Percentage difference in distance Point Count
A priority queue is like a traditional queue but with an additional feature: the elements carry a priority and higher priority elements should be put in front of lower priority ones. The example below illustrates how a priority queue works using Disney duck characters. | Action | State of Priority Queue | | —— | ———————– | | None | (front) (rear) | | Daisy arrives with “default†priority | (front) {Daisy,0} (rear) | | Donald follows Daisy also with “default†priority | (front) {Daisy,0} {Donald,0} (rear) | | Scrooge shows up with priority = 3 | (front) {Scrooge,3} {Daisy,0} {Donald,0} (rear) | | Huey shows up with priority = 2 | (front) {Scrooge,3} {Huey,2} {Daisy,0} {Donald,0} Your goal on this homework is to finish the implementation of the push method in the PriorityQueue class implementing the TO-DO’s and passing all the tests. Submission You only need to submit the PriorityQueue.java source code this time.
In this assignment you are asked to implement a linked list reverse method with a caveat: the reverse must be done “in-place”. In other words, your solution must NOT be based on copying the elements to another collection to later recreate the list. The “in-place” reversal of a linked list is possible. The algorithm is explained using an example. Step 1: Initial Setup The suggested solution uses three Node references: previous, current, and next. Check the cases when nothing needs to be done: the list is empty of it has only one element (you can check if the list has only one element without calling size). Initialize previous and current the way it is explained in the picture below.Step 2: Loop to Change References Figure out when your changing references loop should end. At each iteration, you should save current’s next using another Node reference variable, let’s say next.Then, your next step should make current’s next point to previous.Then, assign current to previous and next to current, setting the stage for next loop iteration.Let’s run one more iteration. First set current’s next to reference variable next.Then, your next step should make current’s next point to previous.Then, assign current to previous and next to current, setting the stage for next loop iteration.Let’s now run what should be the last iteration. First set current’s next to reference variable next.Then, your next step should make current’s next point to previous.Then, assign current to previous and next to current, setting the stage for next loop iteration, which won’t happen because current is null.Step 3: Update the “head” Node After your loop is done, you still need to update the head node using previous. The final configuration is illustrated below. Well, not quite final yet… Note the never ending loop between spots and sparky.Removing that reference is left for you to figure out. Improving the Solution Now that you have one solution that works, try to improve it by initializing previous to null and current to head. See if you can write the loop that changes the references in a way that works for all cases and that also updates head as the reverse list is built. Submission Zip LinkedList.java and LinkedListDriver.java into hwk_04.zip and upload the file to Canvas. hwk_04.zip |__LinkedList.java |__LinkedListDriver.java Grading +3 for the algorithm that reverses the linked list (TODO #1) +2 for the use of reverse in LinkedListDriver (TODO #2) -1 if you were not able to remove the reference loop described above
Using the ArrayList implementation discussed in class, finish the 3 TO-DOs. TODO #1 Method contains should return true if the given value is in the array list (false otherwise). Since the elements of the array are object, make sure that you compare them using the equals method (don’t use the equality operator). Referece variables should be compared by structure using equals. TODO #2 Method reverse should do what its name suggests: reverse the order of the elements in the array list. For example, if the array list contains “1 4 10 5 8” then after a call to reverse the array should have the same elements but in the order “8 5 10 4 1”. You solution should NOT create a new static array (instead it should swap elements from outside to inside). For example: 18 and 45. TODO #3 Method clear should recreate the array list (with its initial capacity), essentially wiping out all of its elements. Submission Just submit the ArrayList.java. There is no need to submit ArrayListTest.java. Rubric Pass all the tests and you are guarantee a 5 on this assignment. Each test that you fail you lose 1 point.
Consider the abstract class Progression that sets an initial value and defines a way to compute its next value. Based on that class, define 3 specializations: ArithmeticProgression, GeometricProgression, and FibonacciProgression. Arithmetic Progression An arithmetic progression computes the next value by adding difference to the current value. For example, to create the arithmetic progression 0, 2, 4, 6, … the initial value is 0 and the difference is 2. ArithmeticProgression defines 2 constructors: one that takes both the initial value and the difference, and another one that takes no value at all, setting the initial value to 0 and the difference to 1. Geometric Progression A geometric progression computes the next value by multiplying ratio to the current value. For example, to create the geometric progression 1, 2, 4, 8, … the initial value is 1 and the ratio is 2. GeometricProgression defines 2 constructors: one that takes both the initial value and the ratio, and another that takes no value at all, setting the initial value to 1 and the ration to 2. Fibonacci Progression A fibonacci progression computes the next value by adding both previous numbers. For example, to create the fibonacci progression 1, 1, 2, 3, 5, 8, 13, … the previous value is initially set to 0 and the value to 1. This should be done automatically by the fibonacci’s default constructor (parameterless constructor). Submission Just submit a single file this time: Progression.java which should contain: the preamble comment with your name using the provided format classes Progression, ArithmeticProgression, GeometricProgression, and FibonacciProgression. There is no need to submit ProgressionTest.java. Rubric Pass all the tests and you are guarantee a 5 on this assignment. Each test that you fail you loose 1 point.
In this assignment you are asked to design a simple class to model a die, according to the following specifications. A die is defined by its number of sides (at least 2) and a value that keeps the die’s current value (set to 1 upon initialization). Users should be able to create a die given its number of sides. If the informed number of sides is less than 2, it should be set to 2. Users should also be able to create a die without informing its number of sides (in that case, the number of sides should be set to 6). Remember, the current value of a die should always be set to 1 upon object instantiation. Create a method called “getValue†that returns the die’s current value. Also, define a method called “roll†to randomly pick another value for the die, based of course on the number of sides. Write a DieDriver program to illustrate how the Die class can be used. This program should create an 8-sided die. After showing the information about the die, the program should roll it 10 times, displaying its current value at each iteration. Below is an example output for your reference. Die{sides=8, value=1} 4 7 8 8 6 7 1 1 6 4 Submission Zip Die.java and DieDriver.java in a file called die.zip. You must use the zip format! Inside the zip file there should be only the 2 java files and nothing else (no other folders or unnecessary files). You will loose points if you don’t follow these instructions. Rubric +1 Die’s member variables +1 Die’s constructors +1 Die’s methods (getValue, roll, and toString) +2 DieDriver’s implementation -1 zip file not submitted according to the format that was asked -1 source files didn’t identify the student’s name in the comments section -1 Die class implementation didn’t use the provided class variables when appropriate Total: 5 points
Write a program that reads an arithmetic expression (as a String) from the standard input and then checks if the parentheses in the expression are balanced (i.e., for every opening parenthesis there should be another one closing). Use the dynamic stack implementation discussed in class and available online in our GitHub repository. Test your code using the following expressions: ( 5 – 2 ) * 3 / ( 8 + 5 ) ( 5 – 2 ) * 3 / ) 8 + 5 ( 3 + 2 – 4 ( ( ( ( ( 1 + 1 ) – 1 ) – 1 ) – 1 ) – 1 ) ( ( 4 + 2 ) – ( 7 – 3 ) )
Draw the “search tree†for all of the possible solutions of the problem “search for all of the combinations of the letters a, b, and c with a size 3â€. Draw two search trees, one using a queue and another one using a stack. Write a sequential number next to a letter every time you push it to the queue/stack, respectively. Write a check mark next to a letter every time you pop it from the queue/stack, respectively. Remember that the letters get reversed when they are pushed onto the stack. At the end, describe how different the two implementations are and which one do you think is preferable? When you are done, finish the implementation of the exhaustive search program.
Recursion is beautiful… To prove that, in this activity you will write an implementation for the Koch’s snowflake curve. Read about this curve from the Wikipedia article available here. Complete the implementation of the KockSnowflake class following the instructions below. Get the initial code from our GitHub’s repository. Constructor The KochSnowflake’s constructor accepts the starting point of the drawing as (xPixel, yPixel), a value for the depth, a size, and a color (object). Use parameters(xPixel, yPixel) to initialize the correspondent instance variables. Make sure these coordinate values are non-negative as they are defined in a graphical coordinate system. Parameter depth should be greater than or equal zero; parameter size should be at least 10; finally, parameter direction defines an angle in degrees and it should be set initially to zero degrees. Helper Methods The first helper method you should implement is drawLine. This method draws a line from (xPixel, yPixel) to (xPixelNew, yPixelNew), a new coordinate defined as: xPixelNew = xPixel + cosine(direction) ⨉ size yPixelNew = yPixel + sine(direction) ⨉ size VERY IMPORTANT: make sure you convert direction from degrees to radians; hint: use the Math.toRadians function. Use drawLine from Java’s Graphics object to actually draw the line once you have computed the coordinates of the end point.Don’t forget to assign (xPixelNew, yPixelNew)to (xPixel, yPixel)once you are done drawing the line. The rotate method is straightforward: just add the degrees parameter to direction. There is no need to worry about direction becoming negative or greater than 360 degrees. Koch’s Curve The drawCurve method implements the Koch’s curve. It takes a Graphic’s object and a depth. The drawCurve method is recursive: the base-case happens when the depth is equal to zero, resulting in drawCurve drawing a line using drawLine. If depth is greater than zero, drawCurve recursively calls itself FOUR times, each time using depth – 1 as the depth and rotating the direction using the pattern: no rotation; rotate clockwise 60o rotate anti-clockwise 120o rotate clockwise 60o Below are the results of calling drawCurve with depth = 0 and depth = 1.To help you understand how drawCurve with depth = 1 is drawn, study the picture below that shows the effect of rotating direction between calls to drawCurve.Below are the results of calling drawCurve with depth = 2, 3, and 4.Koch’s Snowflake You get Koch’s snowflake simply by calling drawCurve three times, making 120 degrees rotation between calls. The figure below explains the process when calling drawSnowflake using depth = 1.
In this activity you are asked to design simple classes based on a given specification. Start by creating a new project. Then, create classes to model each of the functionalities described next. Write a driver classes to illustrate that your designs work. Account A bank account is defined by a number (integer), the name of the owner, and a balance. Users should have the ability to create an account by specifying its number and owner. Balance is always initialized to zero. The class should provide methods to allow deposit (amount informed as parameter), withdraw (amount informed as parameter; balance cannot become negative). You should also implement the “toString†method. Sandwich A sandwich is defined by a name, number of calories (integer is fine), and price. Users should be able to create a sandwich given its name, number of calories, and price. If informed number of calories or price is negative, make sure those values are initialized to zero. Define “toString†and a method called “isHealthy†that returns true if the number of calories is less than 250, false otherwise. Die A die is defined by a number of sides (at least 2) and a value that keeps the die’s current value (always set to 1 upon initialization). Users should be able to create a die given its number of sides. If the informed value (as in number of sides) is < 2, set it to 2. Users should also be able to create a die without informing its number of sides (in that case, set the number of sides to 6). Remember, the current value of a die should always be set to 1 upon creation. Create a method called “getValue†that returns the die’s current value. Also, define a method called “roll†to randomly pick another value for the die, based of course on the number of sides.
In this activity you will practice turning loops into recursive calls. For that to work, you will need to define functions and work on the base case of your recursion. For example, consider the following loop that performs a simple 1-n summation. int sum = 0; int n = 10; for (int i = 1; i
