Choose Your Own Project!Lab Objectives Take what you’ve learned in this class and design and implement a fun/cool project that utilizes the DE1SoC board and peripherals.Project Requirements Be creative! You are required to use: 1) A VGA display (building off of Lab 5). 2) Some form of significant memory storage (e.g., pixel data, audio clip, other game data). You can refer to Labs 2–4 for a refresher on initializing and using memory. 3) Some form of user input, which could be the switches and push buttons or some of the peripherals listed below. You can, and are encouraged to, use additional peripherals. All drivers you will need for this lab can be found in the folder on Canvas within the folder. Unfortunately, we are limited to the currently available interfaces on LabsLand, but these include: • Sound output from a speaker (building off of Lab 3). • A virtual 360-degree joystick. • An “N8” controller, shown in the form of an old controller from the Nintendo Entertainment System (4 directional pad, Select, Start, A, B).Notes for using a VGA display:Notes for using audio output: Recall that LabsLand does not allow you hear your audio live. Unfortunately, this means you can’t do things like producing sounds/noises at certain events as they would only be heard in the recording afterward. However, it would be acceptable to produce an audio output as a final artifact based on the user input (e.g., a beat or drum generator).Project Ideas You are allowed to take inspiration and code from elsewhere (e.g., a software implementation, your 271/369 project), but make sure that you cite your sources. However, these portions will not count towards the overall difficulty of your project – we care about what you will be implementing this quarter. Category 1: Games • Side-scrolling: The player(s) move through a level, avoiding or destroying obstacles or enemies. • Combat: Two or more players compete to collect points and/or defeat the others, maybe with projectiles or by growing their own body as an obstacle. • Tile-matching: Tetris, Bust-a-Move, Candy Crush, or something of similar complexity. • Card: Blackjack, Solitaire, Set, or something of similar complexity. Category 2: Audiovisual • Paint: Allow the user to draw on the VGA or otherwise change an image output. • Audio Visualization: Use an audio input file to display some sort of reactive visualization. • Music Generation: Take in user input to generate sound, e.g., music notation/composition. Basic pixel-by-pixel painting is not complex enough to be used as the sole feature of a project – this will need to be extended with other, more complex features. Category 3: Create Your Own Come up with your own idea that satisfies the list of requirements above and submit a proposal to the course staff! Past class video with other examples: https://youtu.be/3J6ZwsfqRKQ Do note that that video is from when the course was using DE1-SoC lab kits, so there were different peripherals available. Project Explanation Video This quarter will not require a video demo. The links below are left as examples. Here are some links (UW login required) to past project videos that earned full scores on the video (i.e., not necessarily on the project itself): • Flood Fill Algorithm: https://drive.google.com/file/d/1wQ0kaWS5sYTW_nqx97thSxf5XRjbGFSy/view?usp=sharing • Red Light, Green Light Game: https://drive.google.com/file/d/17OUh_Y5rUIQt0QEx2tVa1pa4yn0tr5e/view?usp=sharing Project Demonstration/Turn-In Requirements In-Person Demo • Demonstrate your completed project working on LabsLand. • Be prepared to answer questions on both the theoretical and practical parts of the project. Project Report (submit as PDF on Gradescope) • Include the required Design Procedure, Results, and Experience Report sections. o If you worked with a partner, include a partner work summary in your Experience Report. • Don’t forget to also submit your SystemVerilog files ( ), including testbenches!Lab 6 Rubric Grading Criteria Points Name, student ID, lab number 2 pts Design Procedure 20 pts Results 14 pts Experience Report 14 pts SystemVerilog code uploaded 5 pts Code Style 5 pts PROJECT DEMO 70 pts ▪ Bonus points available for particularly impressive projects (10 pts) 140 pts
Lab Objectives In this lab, you will use Algorithmic State Machine with Datapath (ASMD) charts to implement algorithms as hardware circuits.Introduction – ASMD Review The implementation of algorithms in hardware is often performed by separating the data storage and manipulation components (the datapath circuit) from an FSM for the routing logic (the control circuit).Task #1 – Bit-Counting Algorithm The ASMD chart shown in Figure 1 represents a circuit that counts the number of bits set to in an -bit input (i.e., =an−1an−2…a1a0).Implement the bit-counting circuit given by the ASMD chart in Figure 1 in SystemVerilog to run on the DE1-SoC board, combining the necessary datapath components and a control circuit FSM. • The inputs to your circuit should consist of an 8-bit input () connected to switches , a synchronous connected to , and a start signal () connected to KEY3. • Use the 50 MHz clock signal provided on the board as the clock input for your circuit. Be sure to handle metastability properly in your input. • Display the number of ’s counted in on the 7-segment display , and signal that the algorithm is finished by lighting upTask #2 – Binary Search Algorithm Implement a binary search algorithm, which searches through an unsigned array to locate an 8-bit value once the user presses . A block diagram for the circuit is shown in Figure 2. The binary search algorithm works on a sorted array. Rather than comparing each value in the array to the one being sought, we first look at the middle element and compare the sought value to the middle element. If the middle element has a greater value, then we know that the value we seek would be in the first half of the array. Otherwise, the value we seek would be in the second half of the array. By applying this approach recursively, we can complete our search in many fewer steps. By default, is an unsigned data type in SystemVerilog (i.e., the stored bits are interpreted by their non-negative binary value). Comparisons such as and are unsigned comparisons on values, regardless of what radix you are using to display their value in ModelSim. For example, if , it turns out that returns false, because -1 is stored as , which is interpreted as 255 in unsigned.In this circuit, the array, which you can assume has a fixed size of 32 elements, is stored in a memory module that is implemented inside the FPGA. A diagram of the memory module that we need to create is depicted in Figure 3. This memory should contain a sorted collection of 8-bit unsigned integers. The input should be specified on switches – , on , and on . Your circuit should produce a 5-bit output , which specifies the address in the memory where the number is located, a signal Done indicating that the algorithm is finished, and a signal that should be high if was found and low otherwise. Display , if found, in hex on – , Done on , and Perform the following steps: 1) Create an ASMD chart for the binary search algorithm. Keep in mind that the memory has registers on its input ports – when would you expect to see the output associated with new inputs? 2) Implement the control FSM and the datapath for your circuit as separate modules. 3) Create a memory that is eight-bits wide and 32 words deep in a similar fashion to Lab 2 Task #1 and then connect it to your FSM and datapath to the memory block as indicated in Figure 2. Use the DE1-SoC board’s 50 MHz clock signal as the Clock input and be sure to synchronize the input to the clock (i.e., handle metastability). 4) Create a memory initialization file called (refer to Lab 2 Task #3 Step 2) and fill it with an ordered set of 8-bit unsigned integers of your choice. Make sure that this file is saved in the same folder as the Quartus project. 5) Make sure that your design works in simulation and on the DE1-SoC board. 6) After you have Tasks 1 and 2 working, add the ability to switch between them in the same program usingLab Demonstration/Turn-In Requirements In-Person Demo • Demonstrate your working Task #1 bit-counting algorithm on different inputs. • Explain what your Task #1 reset signal does in your code. • Demonstrate your working Task #2 binary search algorithm for found and not found inputs. • Explain what your Task #2 reset signal does in your code. Lab Report (submit as PDF on Gradescope) • Include the required Design Procedure, Results, and Experience Report sections. o Notice that Figure 1 does not currently include your control signals or ASM blocks. Also notice that Figure 2 does not currently include your control or status signals. • Don’t forget to also submit your SystemVerilog files ( ), including test benches! Lab 4 Rubric Grading Criteria Points Name, student ID, lab number 2 pts Design Procedure 16 pts Results 16 pts Experience Report 6 pts SystemVerilog code uploaded 5 pts Code Style 5 pts LAB DEMO 50 pts 100 pts
Digital Signal ProcessingLab Objectives In this lab, you will use the audio coder/decoder (CODEC) on the DE1-SoC board to generate and filter noise from both an external source and an internal memory. Using audio with the DE1-SoC via LabsLand involves some special instructions so make sure to reference the document before you do any testing on the hardware! Introduction Sounds, such as speech and music, are signals that change over time. The amplitude of a signal determines the volume at which we hear it. The way the signal changes over time determines the type of sounds we hear. For example, an “ah” sound is represented by a waveform shown in Figure 1. The waveform is an analog signal, which can be stored in a digital form by using a relatively small number of samples that represent the analog values at certain points in time. The process of producing such digital signals is called sampling. The points in Figure 2 provide a sampled waveform. All points are spaced equally in time and they trace the original waveform.Figure 1: An example waveform for an “ah” sound. Figure 2: Sampled waveform of Figure 1. The DE1-SoC board is equipped with an audio CODEC capable of sampling sound from a microphone and providing it as an input to a circuit. By default, the CODEC provides 48000 samples per second (48 kHz), which is sufficient to accurately represent audible sounds (by the Nyquist-Shannon sampling theorem). To simplify this lab, a system that can record and play back sounds on the board is provided as a “starter kit.” The system comprises a Clock Generator, an Audio CODEC Interface, and an Audio/Video Configuration module (Figure 3). For this lab, we will assume that our audio will be split into two channels, left and right, that are intended to be played from multiple speakers (e.g., left and right earbuds/headphones). The left column of signals in Figure 3 are the inputs and outputs of the system. These I/O ports supply the clock inputs and connect the Audio CODEC and Audio/Video Configuration modules to the corresponding peripheral devices on the DE1-SoC board. The right column of signals connects the Audio CODEC Interface module to your circuit and allows your circuit to record sounds from a microphone and play them back via speakers.Figure 3: The audio system used in Lab 3. The system works as follows (this interface is also detailed in the starter kit files): • Upon reset, the Audio/Video Configuration begins an auto-initialization sequence. The sequence sets up the audio device to sample microphone input at a rate of 48 kHz and produce output through the speakers at the same rate. • Once the auto-initialization is complete, the Audio CODEC begins reading the data from the microphone once every 48,000-th of a second and sends it to the Audio CODEC Interface core in the system. Note that this is significantly SLOWER than the DE1-SoC’s onboard 50 MHz clocks. • Once received, a sample is stored in a 128-element buffer in the Audio CODEC Interface core. The first element of the buffer is always visible on the and outputs (i.e., 2 channels for 1 sample), but the data is only valid when the signal is asserted. When you assert the signal, the current sample is replaced by the next element one or more clock cycles later, indicated by being reasserted. • The procedure to output sound through the speakers is similar. Your circuit should monitor the signal. Only when the Audio CODEC is ready for a write operation should your circuit assert the signal to write a sample from the and signals. This operation stores a sample in a buffer inside of the Audio CODEC Interface, which will then send the sample to the speakers at the right time.Figure 4: Connections between the FPGA and the Audio CODEC. Task #1 – Passing Music Through the FPGA In this task, you will play a music file into the audio input of the DE1-SoC, which will simultaneously be played through the audio output of the device. 1) Modify the provided starter kit circuit to pass the audio input to audio output only when the CODEC is ready. Hint: BOTH the audio input and audio output have to be ready for data passing! 2) In LabsLand, upload an audio file (either the provided or your own – see for restrictions) alongside your synthesized circuit and verify that the preview of the audio file matches your recorded output sample. Recall that in LabsLand, you must record while playing the audio file into the DE1-SoC. It is critical that you get the code for this task correct, as your understanding of the communication protocol with the audio CODEC will affect your ability to do the rest of the lab correctly. Once you have completed this task, you can post privately on Ed Discussion or drop by an office hour and a staff member will be happy to verify your setting of the and signals. Task #2 – Play a Tone from Memory In this task, you will produce a static tone from memory. By storing the samples from a sound’s waveform, you can play back those samples later to re-produce the sound. We have provided a Python script which generates MIF files for a desired tone, which can then be loaded into memory. Information on how to use this Python script can be found in the tutorial document 1) Follow the tutorial on using the python script to create a MIF file with your desired tone. Create a ROM that initializes to the values stored in the MIF file using Quartus’ built in library modules: a. Open the IP Catalog in the Quartus menu by clicking on → “ ”. In the IP Catalog window, expand “ ”, then “ ”, then “ ”. Then double-click “ ”. b. Give the file an appropriate name, select “ ” as the file type, then click “ ” to open the configuration wizard. c. In the first window specify 24-bits as the word width. You will need to check your generated MIF file to find the number of words, as this will vary. select “ ” for memory block type and “ ” for the clocking method, then click “ ”. d. Click “ ” past the “ ” window keeping the default selections. e. In the next window, under “ ”, select “ ” and specify your MIF file. Click “ ” to use the rest of the default settings, then click “ ” again at the summary page to exit the wizard. If prompted, add the new Quartus Prime IP File to your project by clicking “ 2) Output the values stored in your ROM sequentially to the Audio CODEC, looping back to the start when you reach the end. Make sure to increment the address only once each time you write. 3) Compile and download your overall design to the DE1-SoC board, record the generated tone in LabsLand and then listen to the generated tone played from the FPGA. 4) Combine your Task #1 and Task #2 by instantiating them in a single top-level module that plays the input audio (Task #1) when and your tone from memory (Task #2) when . While testing, you should switch between the tasks about halfway through your recording. Task #3 – FIR Filter Size In this task, you will learn a basic signal processing technique known as filtering. Filtering is a process of adjusting a signal (e.g., removing noise). Noise in a sound waveform is represented by small, but frequent changes to the amplitude of the signal. A simple logic circuit that achieves the task of noise-filtering is an averaging Finite Impulse Response (FIR) filter. An averaging filter removes noise from a sound by averaging the values of adjacent samples. Conceptually, a basic FIR filter uses registers as delay blocks and computes the moving average from their outputs, as shown in Figure 5.Figure 5: A Finite Impulse Response (FIR) filter that takes a moving average of 8 samples. While this is conceptually what we want to achieve in Task #3, we will use a different implementation, as shown in Figure 6. However, we can achieve the same result using a FIFO buffer and accumulator (i.e., a register whose input is the sum of the next incoming data value and its current stored value), as shown in Figure 6.Figure 6: N-sample averaging FIR filter using a FIFO buffer and accumulator that you will implement in Task #3. To compute the average of the last samples, this circuit first divides the input sample by . Then, the resulting value is stored in a First-In First-Out (FIFO) buffer of length and added to the accumulator. To make sure the value in the accumulator is the average of the last samples, the circuit subtracts the value that comes out of the FIFO, which represents the (+1)th sample. Arithmetic can cause strange behaviors when synthesized onto your board, particularly because are, by default, unsigned data types but we are using them for signed arithmetic: • The most robust way to divide by a power of two is using an arithmetic right shift. The following code snippet uses the replication and concatenation operators to divide the -bit signal by 2 : • Please pay attention to Figure 6 and make sure that you adding multiplied by instead of subtracting. Task #3 is by far the most difficult part of this lab. Here are some tips to help you out: • Carefully consider how to ensure that your FIR filter updates when it is supposed to. As a single system, the FIFO buffer and accumulator should be synchronized together (i.e., at any clock trigger, either both or neither should update). But when should they update based on the CODEC signals? • The description below Figure 6 is accurate once the FIFO buffer is full. However, you should carefully consider what your buffer will do while the first -1 samples are read (i.e., at the beginning or after a reset) and make sure that the value of the accumulator also matches the buffer behavior during this time period. 1) Implement the -sample averaging FIR filter. Use to select between filtered ( ) and unfiltered ( ) audio to output; this filtering should be able to interact with both Task #1 ( ) and Task #2 ( ). 2) Compile and download your overall design to a DE1-SoC board in LabsLand and use to generate your recorded output. 3) Experiment with different values of to see what happens to the noisy audio sample. Use the switch to tell what kind of effect the filter is having on the audio. a) When you change , remember to adjust both the FIFO buffer length and the circuit divisor. We recommend experimenting with values of that are powers of 2 for easier division.Lab Demonstration/Turn-In Requirements In-Person Demo • Demonstrate all working Tasks using , with your FIR filter size set to the “best” length that you found. You will need uploaded. Lab Report (submit as PDF on Gradescope) • Include the required Design Procedure, Results, and Experience Report sections. o You only need to include simulations for modules you have written, you can assume all of the provided files work without simulation. o Task #1: The design can be a short description and/or a small circuit diagram. No simulation needed. o You should omit top-level simulations for this lab, as mimicking the AUD and I2C signals is unreasonable. However, you should still include a top-level block diagram and description. Do not just include Figure 3 – we need to see/know what happens in “Your Circuit”! • Don’t forget to also submit your SystemVerilog files ( ), including testbenches! Lab 3 Rubric Grading Criteria Points Name, student ID, lab number 2 pts Design Procedure ▪ Top-level block diagram can build off of Figure 3 but should include connections between your defined modules. 14 pts Results ▪ No simulations needed for provided/reused modules, Task #1, or top-level module 14 pts Experience Report 6 pts SystemVerilog code uploaded 5 pts Code Style 5 pts LAB DEMO 54 pts 100 pts
Parking Lot Occupancy CounterLab Objectives This lab is a refresher on finite state machines (FSMs) that you learned about and designed in EE271 or CSE369. Task #1 – Parking Lot Occupancy Counter Consider a parking lot with a single gate for both entry and exit. To keep track of the occupancy of the lot, we decide to use two photosensors to track when cars enter or exit, as shown in Figure 1. For example, the following sequence indicates that a car entered: 1) Initially, both sensors are unblocked (i.e., ) 2) Sensor becomes blocked (i.e., ) 3) Both sensors are blocked (i.e., ) 4) Sensor becomes unblocked (i.e., ) Figure 1: The parking lot photosensor 5) Both sensors are unblocked (i.e., ) setup.Your task is to design a parking lot occupancy counter as follows: 1) Design and implement an FSM for the car detection with two input signals, and two output signals, and . The and signals assert true for one clock cycle when a car enters or exits the lot, respectively. b) Make sure that your FSM does not detect pedestrians (how would the input pattern differ?). 2) Design and implement a car counter with two control signals, and , which increment and decrement the counter, respectively, when asserted. a) Assume that the maximum capacity of the parking lot is 16 spots. 3) Design and implement a module for the parking lot occupancy, which combines the car detection and the counter. Your system should have the following properties: a) Use off-board switches (i.e., not the s) to mimic the two photosensor outputs. b) Display the current car count on the seven-segment displays and , with the following exceptions: i. If the counter reaches , display “ ” on – . ii. When the lot is empty, display “ ” on – and the number “ ” on . c) Use 2 off-board LEDs (i.e., not your LEDRs) to indicate the values of the and signals. i. A logical should turn the corresponding LED on and a logical should turn it off. Connecting off-board components requires the use of the GPIO pins of the DE1-SoC board. Please refer to the document “ ” for information on their usage in LabsLand. a) Wire the anodes of 2 LEDs to FPGA output ports. b) Wire the middle pins of the 3 switches to FPGA input ports of your choosing as your three inputs (Figure 2: LabsLand GPIO headers (from GPIO_Guide.pdf) for your reference. Lab Demonstration/Turn-In Requirements Make sure that you read the document “ ” for details about what to expect during the lab demo and what we expect to be in your submitted lab report and SystemVerilog code. You can also read “ ” for more detailed examples.In-Person Demo • Demonstrate your working parking lot occupancy counter on the DE1-SoC. • Demonstrate your reset functionality. Lab Report (submit as PDF on Gradescope) • Include the required Design Procedure, Results, and Experience Report sections. • Don’t forget to also submit your commented SystemVerilog files ( ), including testbenches!Lab 1 Rubric Grading Criteria Points Name, student ID, lab number 2 pts Design Procedure ▪ System block diagram and diagrams for car detection and counting 12 pts Results ▪ Simulations for top-level and car detection (none needed for car counting) ▪ Present state included in all FSM simulations 10 pts Experience Report 6 pts SystemVerilog code uploaded 5 pts Code Style 5 pts LAB DEMO 20 pts 60 pts
Lab Objectives In computer systems it is necessary to provide a substantial amount of memory. If a system is implemented using only FPGA technology, it is possible to provide some amount of memory by using the memory resources that exist in the FPGA device. In this lab, we will examine the general issues involved in implementing such memory. Remember to start the tasks in this lab by either following the first steps from the Warmup Task from Lab 1 or by making a copy of an existing Quartus project folder. Introduction The FPGA included on the DE1-SoC board provides dedicated memory resources and has M10K blocks, each of which contains 10240 memory bits. The M10K blocks can be configured to implement memories of various sizes. A common term used to specify the size of a memory is its aspect ratio, which gives the depth (in words) and the width (in bits) as depth × width. In this lab, we will use an aspect ratio of 32 × 3. There are two important features of the M10K blocks: 1) They include registers to synchronize all the input and output signals to a clock input. 2) They have separate ports for writing data to the memory and reading data from the memory. A conceptual diagram of the Random-Access Memory (RAM) module that we want implement is shown in Figure 1a. It contains 32 three-bit words (i.e., rows) that are accessed using a five-bit port, a three-bit bidirectional port, and a control input. However, given the properties of the M10K blocks, we will instead implement the modified 32 x 3 RAM module shown in Figure 1b. It includes registers for the address, data input, and write ports, and uses a separate unregistered data output port.Figure 1: 32 x 3 RAM module for Lab 2. Task #1 – Memory Using Library Modules Commonly used logic structures, such as adders, registers, counters, and memories, can be implemented in an FPGA chip by using prebuilt modules that are provided in libraries. In this exercise, we will use such a module to implement the memory shown in Figure 1b. 1) Create a new Quartus project. 2) Get a library RAM module from the IP Catalog: a) Open the IP Catalog in the Quartus menu by clicking on b) In the IP Catalog window, expand “ ”, then “ ”. Then double-click “ ”. c) In the “ ” dialog box that opens, append the text “ ” to the end of the file name and select “ ” as the file type. Then click “ ” to open the configuration wizard. d) In the configuration window, specify 3-bit width for the output bus and 32 words of memory. Then select the “ ” radio button for memory block type and “ ” for the clocking method before clicking “ ”. e) Now, deselect the check box for registering (i.e., placing a register on) the “ ”. This creates a RAM module that matches the structure in Figure 1b. Click “ to accept the defaults for the rest of the settings in the Wizard. f) You will have to click “ ” one more time at the Summary page to exit the Wizard. If prompted, add the new Quartus Prime IP File to your project by clicking “ ” in the Project Navigator window and open (nested under ) to examine it. It defines the following module: module ram32x3 (address, clock, data, wren, q); input [4:0] address; // Address input clock; input [2:0] data; // DataIn input wren; // Write output [2:0] q; // DataOut // … Check above the definition of this module. If you see a line that looks like the following:“… does not have a timeunit/timeprecision specification in effect, but other modules do.” 4) Create a new SystemVerilog file called that instantiates the module, using appropriate input and output signals for the memory ports as shown in Figure 1b. a) Once you compile your circuit, various parts of the Compilation Report will indicate that the RAM circuit is implemented using 96 bits in one of the FPGA memory blocks.5) Create a suitable testbench to verify that you can read and write to the memory in simulation. You will likely encounter the following simulation error at first: “Instantiation of ‘altsyncram’ failed. The design unit was not found.” Solution: In the ModelSim menu, select → “ ” and then go to the tab and add under “ ”. Then, go to the tab, select your testbench module, and click . If you are using files to run your simulations, you can also add the text “ ” to the end of line where you specify your testbench module.Task #2 – Memory Using SystemVerilog Instead of creating a memory module by using the IP Catalog, we can implement the required memory by specifying its structure in SystemVerilog code as a multidimensional array. A 32 × 3 array, which has 32 words with 3 bits per word, can be declared by the statement: logic [2:0] memory_array [31:0];On the FPGA, such an array can be implemented either by using flip-flops found in each logic cell or, more efficiently, by using the built-in memory blocks. In general, arrays with asynchronous reads (i.e., not registered) will be mapped to flip-flops and arrays with synchronous reads (i.e., registered) will be mapped to memory blocks. 1) Write a SystemVerilog module in a new file that provides the necessary functionality as Task #1 but using a multidimensional array. You should be able to use the same testbench as Task #1. 2) Create a top-level SystemVerilog module in a new file that instantiates your new module and uses the inputs and outputs on the DE1-SoC as specified: a. Use switches – to specify and switches – to specify b. Use as the signal and as the input. c. Display the value (in hex) on – , the value on on . A basic 7-segment driver module has been provided for you, which you can freely change; describe any changes you make, but no testbench or waveforms are needed for this module. 3) Synthesize the circuit and download it to a DE1-SoC on LabsLand to test its functionality. In LabsLand, make sure that you select the “Standard” user interface, as opposed to the “Breadboard” that we used in Lab 1:Task #3 – Library Memory with Independent Read and Write The RAM blocks in Figure 1 have a single port for both read and write operations. For this task you will create a different type of memory module that has separate ports for the addresses of read and write operations. You will also learn how to create and use a memory initialization file (MIF). 1) Generate the desired memory module from the IP Catalog by using the “ ” module ”, select “ b) Configure the memory size, clocking method, and registered ports the same way as in Task #1. ”, select “ i. This setting specifies that it does not matter whether the memory outputs the new data being written, or the old data previously stored, in the case that the write and read addresses are the same during a write operation.i. This memory initialization file (MIF) allows us to initialize our RAM to specific values that are loaded when the circuit is programmed into the FPGA chip. You will create this MIF file in Step 2. e) Finish the Wizard and then examine the generated memory module in 2) Create your MIF file a) In the Quartus menu, go to → and then select “ b) Specify 32 words and word size of 3. c) Manually fill the grid with the values you want to place in each memory address. i. If helpful, the menu will let you adjust the number of cells per row displayed and the address and memory radices. d) Save the MIF file as . You can also manually edit this file in a text editor. 3) Augment the top-level module (and its testbench) from Task #2 to use to toggle between the memories of Task #2 ( ) and Task #3 ( ). The following requirements are purposefully similar to Task #2 but pay attention to the differences. Any significant, new modules should have testbenches and simulations; you should mention the source for any provided or reused modules. a) Use – and – to specify the write address and write data, respectively. Display (in hex) the write address on – and the write data on b) Use a counter to cycle through read addresses about one per second (no verification needed). Display (in hex) the read address on – and the 3-bit word content on . c) Use the 50 MHz clock, , to synchronize the system and use as a reset signal. Make sure that you properly handle metastability issues for asynchronous inputs. d) Make sure that the memories from Task #2 and Task #3 are independent of each other (i.e., writing to one memory should not be reflected in the other memory)! 4) Test your circuit and verify that the initial contents of the memory match your file. Make sure that you can independently write data to any address by using the switches and move between the Task #2 and Task #3 memories using Lab Demonstration/Turn-In Requirements In-Person Demo • Briefly show and explain your SystemVerilog memory implementation from Task #2. • Briefly show and your file from Task #3. • Demonstrate your working Task #3 memory circuit (which includes the Task #2 circuit) on the DE1SoC. Lab Report (submit as PDF on Gradescope) • Include the required Design Procedure, Results, and Experience Report sections. o The designs for basic or provided modules like the 7-segment driver and counter should be briefly mentioned, but you do not need to include state diagrams or simulations for these. • Don’t forget to also submit your SystemVerilog files ( ), including testbenches!Lab 2 Rubric Grading Criteria Points Name, student ID, lab number 2 pts Design Procedure ▪ System block diagram for your finished Task #3 (this includes Tasks #2) 6 pts Results ▪ Waveforms & explanations of Tasks #1 & 2 memories (recommended combined into a single simulation) ▪ Waveforms & explanations of top-level module for Task #3 ▪ Waveforms & explanations of any other significant and new modules for Task #3 12 pts Experience Report 6 pts SystemVerilog code uploaded 5 pts Code Style 5 pts LAB DEMO 26 pts 62 pts
Preliminaries 1. You can reuse and build upon your previous code for this assignment. 2. We provide you with the following additional functions that help to handle BJT elements. a) npnBJT.m is function that adds the element BJT to the list of the BJTs. It serves a similar functionality as the diode.m function. b) fvect.m is the function that adds the nonlinear stamp to the vector (). You can use this function to fill the () vector. b. nljacobian.m is the function that creates/ updates the Jacobian for the nonlinear elements. Similar, to diode add the Jacobian for the BJT in this function.3. For adding the AC sources to the circuit, use the function named vol_ac.m. The vol_ac.m function creates a global variable bac. The variable bac contains the contribution of DC sources. The addition of DC sources to the circuit can be done using the vol.m function. 4. In your submission please provide all code in a zip file in a way that allows us to run the testbenches ourselves (include all code, not just the recent one). 4. Also submit a pdf file containing the answers to the questions, the output plots and the code for functions you have written for this assignment. Question I Write a matlab function dcsolvealpha.m that finds the dc solution of the augmented system: + () = The functions is defined as follows: function Xdc = dcsolvealpha(Xguess,alpha,maxerr) % Compute dc solution using newtwon iteration for the augmented system % G*X + f(X) = alpha*b % Inputs: % Xguess is the initial guess for Newton Iteration % alpha is a paramter (see definition in augmented system above) % maxerr defined the stopping criterion from newton iteration: Stop the % iteration when norm(deltaX)
Assignment #2 Preliminaries 1. You can reuse and build upon your previous code for this assignment. 2. We provide you with the following additional functions that help handle time domain sources. a. volsine.m and cursine.m are two functions that add time domain sinusoidal voltage and current sources respectively. They are used in the netlist. The netlists used in the questions below should provide examples. Also read the comments in the functions for the required syntax. b. BTime.m is a function that evaluates and returns the time domain value of the right hand side vector b(t) as a function of time. 3. In your submission please provide all code in a zip file in a way that allows us to run the testbenches ourselves (include all code, not just the recent one). 4. Also submit a pdf file containing the answers to the questions, the output plots and the code for functions you have written for this assignment.Question I: Backward Euler Write a function called transient_beuler.m with the following header:function [tpoints,r] = transient_beuler(t1,t2,h,out) % [tpoints,r] = beuler(t1,t2,h,out) % Perform transient analysis for LINEAR Circuits using Backward Euler % assume zero initial condition. % Inputs: t1 = starting time point (typically 0) % t2 = ending time point % h = step size % out = output node % Outputs tpoints = are the time points at which the output % was evaluated % r = value of the response at above time points % plot(tpoints,r) should produce a plot of the transient responseYour function should use Backward Euler with a constant step size to compute the transient response of a linear circuit.1. Test your function by running the provided Testbench_Question1.m file. This file simulates the netlists Circuit_chebychev_filter_TD.m (provided in the assignment) in the time domain (transient) and Circuit_chebychev_filter (also provided – this is the same circuit you used before to test your fsolve) in the frequency domain using your fsolve.m function which you developed in past assignments. In your submission, include the code for the new function transient_beuler.m as well as the output plot of the testbench function. 2. Explain the relation between the two plots in the output figure.Question II Trapezoidal Rule Write a function transient_trapez.m with the following header: function [tpoints,r] = transient_trapez(t1,t2,h,out) % [tpoints,r] = Transient_trapez(t1,t2,h,out) % Perform Transient Analysis using the Trapezoidal Rule for LINEAR % circuits. % assume zero initial condition. % Inputs: t1 = starting time point (typically 0) % t2 = ending time point % h = step size % out = output node % Outputs tpoints = are the time points at which the output % was evaluated % r = value of the response at above time points % plot(tpoints,r) should produce a plot of the transient response Your function should use Trapezoidal Rule with a constant step size to compute the transient response of a linear circuit.1. Test your function by running the provided Testbench_Question2.m file. This scripts also runs your code from Question 1 and compares BE to TR. In your submission, provide the code for the function you wrote as well as the plot from the testbench. 2. By examining the plot, what can you deduce about the BE and TR methods?Question III Forward Euler Write a function transient_feuler.m with the following header:function [tpoints,r] = transient_feuler(t1,t2,h,out) % [tpoints,r] = Transient_feuler(t1,t2,h,out) % Perform Transient analysis for LINEAR circuit using Forward Euler % This function assumes the C matrix is invertible and will not work % for circuits where C is not invertible. % assume zero initial condition. % Inputs: t1 = starting time point (typically 0) % t2 = ending time point % h = step size % out = output node % Outputs tpoints = are the time points at which the output % was evaluated % r = value of the response at above time points % plot(tpoints,r) should produce a plot of the transient response1. In order to test your code, run the provided test bench script Testbench_Question3.m which simulates the circuit in the provided netlist Q3BEcircuit.m. 2. Examine and comment on what you learn from the output files. 3. It can be shown that, when the C matrix is invertible, the poles of the circuit are the eigenvalues of the matrix −−1 (note the negative sign). Determine the stability condition of the forward euler method for this circuit and experimentally verify your results by running simulations (note the eig function in matlab computes the eigenvalues of a matrix).Question IV Nonlinear Circuits TransientWrite a function nl_transient_beuler.m with the following header: function [tpoints,r] = nl_transient_beuler(t1,t2,h,out) % [tpoints,r] = beuler(t1,t2,h,out) % Perform transient analysis for NONLINEAR Circuits using Backward Euler % Assume zero initial condition. % Inputs: t1 = starting time point (typically 0) % t2 = ending time point % h = step size % out = output node % Outputs tpoints = are the time points at which the output % was evaluated % r = value of the response at above time points % plot(tpoints,r) should produce a plot of the transient responseYour function should use Backward Euler with a constant step size to compute the transient response of a nonlinear circuit. For now, you only need to support diodes and you can reuse the code you wrote before and that we have supplied to you.Test your circuit by running the provided script Testbench_Question4 which simulates the rectifier circuit in netlist Circuit_Rectifier.m also provided.
Assignment #1In order to simplify parsing, we will use our own netlist format in ECSE59. For example consider the following netlist.% CIR1.M % Description of Circuit 1 % % Comment lines start with % just like in matlab (this is in fact a matlab % script). global G C %define global variables global b;G = zeros(4,4); % Define G, 4 node circuit (do not include additional variables) C = zeros(4,4); % Define C, 4 node circuit (do not include additional variables) b = zeros(4,1); % Define b, 4 node circuit (do not include additional variables) % Try changing zeros(4,4) with sparse(4,4) for sparse routines. % See matlab help for info about sparse matrix support.vol(1,0,1); % add voltage source between nodes 0 and 1 (value =1) res(1,2,50); % add 50 ohm resistor between nodes 1 and 2 res(4,0,50); cap(2,0,0.319e-6); cap(3,4,64.72e-12); cap(4,0,0.319e-6); ind(2,0,0.317e-6); ind(2,3,1.59e-6); ind(4,0,0.317e-6);The above netlist corresponds to the following circuit which has 4 nodes.You will find on myCourses the following functions: cap.m, res.m, cur.m, vol.m, and diode.m which allow you to generate the MNA equations for circuits containing capacitors, resistors, current sources, voltage sources and diodes. You will also find the function f_vector.m which computes the nonlinear vector of the MNA, f(x), as a function of x. The file Circuit_diodeckt1.m is the netlist of a simple diode circuit. nlJacobian.m and dcsolve.m are the definitions of functions that you will need to write. Finally, Test_bench_diode1.m is the test bench that you should be able to run once you complete the assignment.Questions: 1. Draw the circuit in the netlist Circuit_diodeckt1.m. 2. Write a matlab function nlJacobian.m (see function definition provided). This function should compute and return the Jacobian of the nonlinear vector f(x) 3. Write a matlab function dcsolve.m (see function definition provided). This function should use the Newton-Raphson method to compute the dc solution. It should also return the interim values of detlaX for each iteration (see function definition for details). 4. Run the script Test_bench_diode1.m to test your code for dcsolve.m. 5. Write the following matlab functions: ind.m adds an inductor to the MNA equations vcvs.m adds a voltage controlled voltage source to the MNA equations vccs.m adds a voltage controlled current source to the MNA equations fsolve.m performs a frequency domain analysis to obtain the frequency response.See the attached matlab files with the same names for more precise definitions of these functions.6. Run all Benchmark functions provided in order to test your simulator.Deliverables: 1. A pdf file containing a) the schematic of the circuit in Circuit_diodeckt1.m, b) dc values computed after running test bench, c) the figure that was plotted when you ran the test bench, and d) the matlab code for nlJacobian.m and dcsolve.m. 2. The matlab m files for nlJacobian.m and dcsolve.m 3. A pdf file containing the results of all benchmark functions (all plots), as well as the matlab code for the functions your have written. 4. The matlab m files for ind.m, vcvs.m, vccs.m, fsolve.m
Assignment 31. You are given a list of measured BH points for M19 steel (Table 1), with which to construct a continuous graph of B versus H.(a) Interpolate the first 6 points using full-domain Lagrange polynomials. Is the result plausible, i.e. do you think it lies close to the true B versus H graph over this range? (b) Now use the same type of interpolation for the 6 points at B = 0, 1.3, 1.4, 1.7, 1.8, 1.9. Is this result plausible? (c) An alternative to full-domain Lagrange polynomials is to interpolate using cubic Hermite polynomials in each of the 5 subdomains between the 6 points given in (b). With this approach, there remain 6 degrees of freedom – the slopes at the 6 points. Suggest ways of fixing the 6 slopes to get a good interpolation of the points. Test your suggestion and comment on the results. (d) The magnetic circuit of Figure 1 has a core made of Ml9 steel, with a cross-sectional area of 1 cm2. Lc = 30 cm and La = 0.5 cm. The coil has N = 800 turns and carries a current I = 10 A. Derive a (nonlinear) equation for the flux in the core, of the form f() = 0. (e) Solve the nonlinear equation using Newton-Raphson. Use a piecewise-linear interpolation of the data in Table 1. Start with zero flux and finish when | f() / f() | < 10-6. Record the final flux, and the number of steps taken. (f) Try solving the same problem with successive substitution. If the method does not converge, suggest and test a modification of the method that does converge.Page 1 of 22. For the circuit shown in Figure 2 below, the DC voltage E is 200 mV, the resistance R is 512 , the reverse saturation current for diode A is IsA = 0.8 A, the reverse saturation current for diode B is IsB = 1.1 A, and assume kT/q = 25 mV.(a) Derive nonlinear equations for a vector of nodal voltages, vn, in the form f(vn) = 0. Give f explicitly in terms of the variables IsA , IsB , E, R and vn.(b) Solve the equation f = 0 by the Newton-Raphson method. At each step, record f and the voltage across each diode. Is the convergence quadratic? [Hint: define a suitable error measure k].Figure 23. Write a program that accepts as input the values for the parameters x0, xN, and N and integrates a function f(x) on the interval x = x0 to x = xN by dividing the interval into N equal segments and using one-point Gauss-Legendre integration for each segment.(a) Use your program to integrate the function f(x) = sin(x) on the interval x0 = 0 to xN = 1 for N = 1, 2,…, 20. Plot log10(E) versus log10(N) for N=1,2,…,20, where E is the absolute error in the computed integral. Comment on the result.(b) Repeat part (a) for the function f(x) = ln(x), only this time for N = 10, 20,…, 200. Comment on the result.(c) Repeat part (b) for the function f(x) = ln(0.2sin(x)). Comment on the result.(d) An alternative to dividing the interval into equal segments is to use smaller segments in more difficult parts of the interval. Experiment with a scheme of this kind, and see how accurately you can integrate f(x) in part (b) and (c) using only 10 segments. Comment on the results. Page 2 of 2
ECSE 543A NUMERICAL METHODS IN ELECTRICAL ENGINEERING Assignment 21) Figure 1 shows two first-order triangular finite elements used to solve the Laplace equation for electrostatic potential. Find a local S-matrix for each triangle and a global S-matrix for the mesh, which consists of just these two triangles. The local (disjoint) and global (conjoint) node-numberings are shown in Figure 1(a) and (b), respectively. Also, Figure 1(a) shows the (x, y)-coordinates of the element vertices in meters.(0.00, 0.02) (0.02, 0.02) 1 4(0.00, 0.00) (0.02, 0.00) 2 3(a) (b) Figure 12) Figure 2 shows the cross-section of an electrostatic problem with translational symmetry: a rectangular coaxial cable. The inner conductor is held at 110 volts and the outer conductor is grounded. (This is similar to the system considered in Question 3, Assignment 1.)(a) Use the two-element mesh shown in Figure 1(b) as a “building block” to construct a finite element mesh for one-quarter of the cross-section of the coaxial cable. Specify the mesh, including boundary conditions, in an input file following the format for the SIMPLE2D program as explained in the course notes. (Hint: Your mesh should consist of 46 elements.)(b) Use the SIMPLE2D program with the mesh from part (a) to compute the electrostatic potential solution. Determine the potential at (x,y) = (0.06, 0.04) from the data in the output file of the program.(c) Compute the capacitance per unit length of the system using the solution obtained from SIMPLE2D.Note: The SIMPLE2D program and related utility programs are available from the myCourses page for this course or on the World-Wide-Web at: http://www.cambridge.org/ca/academic/subjects/engineering/engineeringmathematics-and-programming/finite-elements-electrical-engineers-3rd- edition?format=PB?format=PB (Click on “Resources” tab.) Please read the file README.1ST before using the software.(Continued on reverse…)yFigure 2.(a) Test your matrix using your Choleski decomposition program that you wrote for Question 1 of Assignment 1 to ensure that it is positive definite. If it is not, suggest how you could modify the matrix equation in order to use the conjugate gradient method for this problem. (b) Once you have modified the problem, if necessary, so that the matrix is positive definite, solve the matrix equation first using the Choleski decomposition program from Assignment 1, and then the conjugate gradient program written for this assignment. (c) Plot a graph of the infinity norm and the 2-norm of the residual vector versus the number of iterations for the conjugate program. (d) What is the potential at (x,y) = (0.06, 0.04), using the Choleski decomposition and the conjugate gradient programs, and how do they compare with the value you computed in Question 2(b) above. How do they compare with the value at the same (x,y) location and for the same node spacing that you computed in Assignment 1 using SOR. (e) Suggest how you could compute the capacitance per unit length of the system from the finite difference solution.
NUMERICAL METHODS IN ELECTRICAL ENGINEERINGAssignment 1 (Note: Please comment your program listings and explain how they are structured in your report.)1. (a) Write a program to solve the matrix equation Ax=b by Choleski decomposition. A is a real, symmetric, positive-definite matrix of order n.(b) Construct some small matrices (n = 2, 3, 4, …,10) to test the program. Remember that the matrices must be real, symmetric and positive-definite. Explain how you chose/created the matrices.(c) Test the program you wrote in (a) with each small matrix you built in (b) in the following way: invent an x, multiply it by A to get b, then give A and b to your program and check that it returns x correctly.(d) Write a program that reads from a file a list of network branches (Jk, Rk, Ek) and a reduced incidence matrix, and finds the voltages at the nodes of the network. Use the code from part (a) to solve the matrix problem. Explain how the data is organized and read from the file. Test the program with a few small networks that you can check by hand. Compare the results for your test circuits with the analytical results you obtained by hand. Cleary specify each of the test circuits used with a labeled schematic diagram.2. Take a regular N by N finite-difference mesh and replace each horizontal and vertical line by a 10 kW resistor. This forms a linear, resistive network.(a) Using the program you developed in question 1, find the resistance, R, between the node at the bottom left corner of the mesh and the node at the top right corner of the mesh, for N = 2, 3, …, 15. (You will probably want to write a small program that generates the input file needed by the network analysis program. Constructing the incidence matrix by hand for a 225-node network can be tedious.)(b) In theory, how does the computer time taken to solve this problem increase with N, for large N. Are the timings you observe for your practical implementation consistent with this? Explain your observations.(c) Modify your program to exploit the sparse nature of the matrices to save computation time. What is the half-bandwidth b of your matrices? In theory, how does the computer time taken to solve this problem increase now with N, for large N. Are the timings you observe for your practical sparse implementation consistent with this? Explain your observations.(d) Plot a graph of R versus N. Find a function R(N) that fits the curve reasonably well and is asymptotically correct as N tends to infinity, as far as you can tell. 3. Figure 1 shows the cross-section of an electrostatic problem with translational symmetry: a coaxial cable with a square outer conductor and a rectangular inner conductor. The inner conductor is held at 110 volts and the outer conductor is grounded.Figure 1.(a) Write a computer program to find the potential at the nodes of a regular mesh in the air between the conductors by the method of finite differences. Use a five-point difference formula. Exploit at least one of the planes of mirror symmetry that this problem has. Use an equal node-spacing, h, in the x and y directions. Solve the matrix equation by successive overrelaxation (SOR), with SOR parameter w. Terminate the iteration when the magnitude of the residual at each free node is less than 10-5. (b) With h = 0.02, explore the effect of varying w. For 10 values of w between 1.0 and 2.0, tabulate the number of iterations taken to achieve convergence, and the corresponding value of potential at the point (x, y) = (0.06, 0.04). Plot a graph of number of iterations versus w. (c) With an appropriate value of w, chosen from the above experiment, explore the effect of decreasing h on the potential. Use values of h = 0.02, 0.01, 0.005, etc, and both tabulate and plot the corresponding values of potential at (x, y) = (0.06, 0.04) versus 1/h. What do you think is the potential at (0.06, 0.04), to three significant figures? Also, tabulate and plot the number of iterations versus 1/h. Comment on the properties of both plots. (d) Use the Jacobi method to solve this problem for the same values of h used in part (c). Tabulate and plot the values of the potential at (x, y) = (0.06, 0.04) versus 1/h and the number of iterations versus 1/h. Comment on the properties of both plots and compare to those of SOR. (e) Modify the program you wrote in part (a) to use the five-point difference formula derived in class for non-uniform node spacing. An alternative to using equal node spacing, h, is to use smaller node spacing in more “difficult” parts of the problem domain. Experiment with a scheme of this kind and see how accurately you can compute the value of the potential at (x, y) = (0.06, 0.04) using only as many nodes as for the uniform case h = 0.01 in part (c).
Introduction to Computer Vision (ECSE 415) Assignment 3: Advanced Computer Vision1. Submit a single Jupyter notebook consisting of the solution of the entire assignment. 2. Comment your code appropriately. 3. Give references for all codes which are not written by you. (Ex. the code is taken from an online source or from tutorials) 4. Do not forget to run Markdown (’Text’) cells. 5. Do not submit input/output images. Output images should be displayed in the Jupyter notebook itself. 6. Make sure that the submitted code is running without error. Add a README file if required. 7. If external libraries were used in your code please specify their name and version in the README file. 8. We are expecting you to make a path variable at the beginning of your codebase. This should point to your working local (or google drive) folder. Ex. If you are reading an image in the following format: img = cv2.imread ( ’/content/drive/MyDrive/Assignment1/images/shapes.png’ ) Then you should convert it into the following:path = ’/content/drive/MyDrive/Assignment1/images/’ img = cv2.imread(path + ’shapes.png’)Your path variable should be defined at the top of your Jupyter notebook. While grading, we are expecting that we just have to change the path variable once and it will allow us to run your solution smoothly. Specify, your path variable in the README file. 9. Answers to reasoning questions should be comprehensive but concise. 1 Image Classification with Convolution Neural Network (CNN) and Naïve Bayes [53 points] 1. Use Pytorch class torchvision.datasets.MNIST to (down)load the dataset. Use batch size of 32. [3 points] 2. Implement a CNN with the layers mentioned below. [5 points] • A convolution layer with 32 kernels of size 3×3. • A ReLU activation. • A convolution layer with 64 kernels of size 3×3. • A ReLU activation. • A maxpool layer with kernels of size 2×2. • A convolution layer with 64 kernels of size 3×3. • A ReLU activation. • A convolution layer with 64 kernels of size 3×3. • A ReLU activation. • A flattening layer. (This layer resizes 2D feature map to a feature vector. The length of this feature vector should be 4096.) • A Linear layer with output size of 10. 3. Create an instance of SGD optimizer with learning rate of 0.001. Use the default setting for rest of the hyperparameters. Create an instance of categorical cross entropy criterion. [1 point] 4. Train the CNN for 10 epochs. Display loss and accuracy in each training step.[5 points] 5. Predict labels of the test images using the above trained CNN. Report classification accuracy. [3 points] 6. Show the effect of batch size on the classification accuracy of test images. Use a minimum of 4 different batch sizes (i.e. batch size = 4, 8, 12, 16). (you will need to re-train the model) [4 points] 7. Mention 2 other activation functions other than ReLU. Re-train the model using these activation functions instead of ReLU (throughout the network) and report the test classification accuracies. Discuss the results. [4 points] 8. Now, use the CNN developed above to recognize the digit in the test images (see Figure 1) –(a) test1.png (b) test2.png (c) test3.png Figure 1: Three-handwritten test images 9. Implement a probabilistic classifier that makes a Naïve Bayes assumption for the likelihood. Assume that you have a uniform prior. Now using this classifier, infer (i.e. mention the posterior probability for each class) on the handwritten test image in figure 1. (You can use the numpy library to answer this sub-question (only for this sub-question)) [7 points] 10. Show the effect of using class probability of the training sample ( probability of a class is the ratio of the frequency of occurrence of a class to the total number of outcomes) as prior in Naïve Bayes on the same test data. Report the posterior class probabilities after using this prior. [4 points] 11. Using the trained CNN, detect (i.e., you have to display two digits in each image) the digits in 64×64 pixeled images (see figure 2) -‘detect1.png’, ‘detect2.png’ and ‘detect3.png’. Explain your results. [10 points](a) detect1.png (b) detect2.png (c) detect3.png Figure 2: Samples of 64×64 pixel images 12. Discuss the limitations of your CNN in the context where you CNN will fail to recognize digits. Show any one example. [3 points] 2 Stereo Vision – Epipolar Geometry [25 points] Use a stereo image-pair shown in figure 3 for the following questions. You can use functions from OpenCV and matplotlib for this question.(a) im0.png (b) im1.png Figure 3: Stereo-image pair 1. Compute matching SIFT keypoints from a stereo image pair. [5 points] 2. Compute and display the epipolar lines for both images. [5 points] 3. Pick any one keypoint in the left image which has a correct match in the right image, and is on the corresponding epipolar line. Extract a patch of size (5 × 5) around this keypoint in the left image. [2 points] 4. Match the extracted patch to every 5 × 5 patch along the corresponding epipolar line in the right image. Use normalized cross-correlation metric for matching. [7 points] 5. Plot normalized cross-correlation values (on the y-axis) against an index of the patch in the left image (on the x-axis). Find the matching points with the maximum normalized cross-correlation value. Display found matching points in both images. [4 points] 6. Are the matching points you found the correct ones? Explain. [2 points] 3 Motion Algorithm [12 points] Use the given two video frames ‘frame1.png’ and ‘frame2.png’ shown in Figure 4 for this question. You can use functions from OpenCV and matplotlib for this question.(a) frame1.png (b) frame2.png Figure 4: Video frames be used for testing motion algorithm Multi-resolution Lucas-Kanade optic flow detection 1. Extract good points to track from ‘frame1.png’ using Harris corner detection algorithm. Use openCV function goodFeaturesToTrack and set parameter value maxCorners=500. Search optimal values for the rest of the parameters. Let us call the detected set of points: p1. [2 points] 2. Compute the optical flow between ‘frame1.png’ and ‘frame2.png’ at the points in p1. Use the openCV function calcOpticalFlowPyrLK. Search for optimal values for the parameters. [3 points] Note that the function calcOpticalFlowPyrLK returns nextPts (a set of shifted positions of each point in p1 which we refer as p2), status (whether the search of shifted position is successful or not) and err (error measure between p1 and p2). Please read the manual for more details .) 3. Display the optical flow image. [1 point] 4. Vary the maximum pyramid level from 0 to 10 (in steps of 1) in the function calcOpticalFlowPyrLK. For each setting, compute the mean of the error at those points whose correspondence search is successful i.e. returned status is 1. Plot the mean (on y-axis) vs. pyramid level (on the x-axis). Discuss the trends you observe in the plot. [4 points] 5. Display the optical flow for each setting of the maximum pyramid level. Comment on the quality of the results. [2 points] References [1] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278–2324, 1998.
Introduction to Computer Vision (ECSE 415) Assignment 2: Image Matching and Face Detection1. Submit a single Jupyter notebook consisting of the solution of the entire assignment. 2. Comment your code appropriately. 3. Give references for all codes which are not written by you. (Ex. the code is taken from an online source or from tutorials) 4. Do not forget to run Markdown (’Text’) cells. 5. Do not submit input/output images. Output images should be displayed in the Jupyter notebook itself. 6. Make sure that the submitted code is running without error. Add a README file if required. 7. If external libraries were used in your code please specify their name and version in the README file. 8. We are expecting you to make a path variable at the beginning of your codebase. This should point to your working local (or google drive) folder. Ex. If you are reading an image in the following format: img = cv2.imread ( ’/content/drive/MyDrive/Assignment1/images/shapes.png’ ) Then you should convert it into the following:path = ’/content/drive/MyDrive/Assignment1/images/’ img = cv2.imread(path + ’shapes.png’)Your path variable should be defined at the top of your Jupyter notebook. While grading, we are expecting that we just have to change the path variable once and it will allow us to run your solution smoothly. Specify, your path variable in the README file. 9. Answers to reasoning questions should be comprehensive but concise. 1 Image Classification using HoG (10 points) Supposing that a company hires you to build a logo classification system that can automatically identify logos of different food brands. The company provides you with some images of different logos as training data, and you are asked to test your classification system on test images. You recall this can be solved using Histogram of Gradient (HoG) features. 1.1 Build a classifier with training images For this task, you are given a set of training images: five ‘Kraft’ logos and five ‘McDonald’s’ logos. These can be found here: ‘Q1/training’ folder. Examples are found in Figures 1 and 2.Figure 1: Example of Kraft logo Figure 2: Example of McDonald’s logo 1. Resize the training images to 128 x 128. 2. Compute HoG features of size (32, 32, 8) for all training images. 3. Apply blocknorm in 4×4 cell neighborhoods. 4. Fit a nearest neighbor classifier with three neighbors. Use KNeighborsClassifier from sklearn library. 1.2 Classify test images You are given a set of test images: two ‘Kraft’ logos and two ‘McDonald’s’ logos. These can be found here: Q1/test’ folder. Examples can be seen in Figures 3 and 4. You are now asked: 1. Compute HoG features for all test images. 2. Display the HoG features for all test images. 3. Classify the test images using the classifier you built above. 4. Does the classifier work on all test images? Discuss which properties of HoG features help to classify the images. Which computer vision methods will you use for classifying logos under rotation.Figure 3: Example of Kraft test logo Figure 4: Example of McDonald’s test logo 2 Image stitching (10 points) You are given three different views of the same scene (check ‘Q2’ folder): image1.jpeg, image2.jpeg and image3.jpeg (see Figure 5).Figure 5: Flower taken from different views 1. Compute the SIFT keypoints and corresponding descriptors for image1 and image 2. 2. Find matching keypoints in image 1 and image 2, and display the 20 best pairs. 3. Using RANSAC method, find the homography that best describes matches the keypoints, and apply the resulting transformation to image 1. Image 2 should not be transformed. 4. Stitch the transformed image 1 and the original image 2 together using pyramid image blending. Let us call it image 12, and display it. 5. Compute the SIFT keypoints and corresponding descriptors for images 12 and 3. 6. Find matching keypoints in image 12 and image 3, and display the 20 best pairs. 7. Find the homography using the RANSAC method, and apply the resulting transformation to image 3. Image 12 should not be transformed. 8. Stitch the transformed image 3 and image 12 together using linear image blending. Display the resulting image. 9. Discuss which method you prefer for stitching – pyramid blending or linear blending, and why? 3 Face detection (10 points) You are given a set of celebrity faces (check ‘Q3/celeb_faces’ folder). Load all images as training dataset and convert to grayscale image data.Figure 6: Example of faces 3.1 Eigenface representation 1. Display the mean face of the training dataset. 2. Find corresponding eigenvectors and eigenvalues, sort in descending order. 3. Print out the first 4 eigenvalues. 4. Let k be the first k eigenvectors. Try k = 20, 10, 5, and report the reconstruction error in each case. Note : you are NOT allowed to use built-in PCA function from online packages, implement your own instead. 3.2 Face detection Using a sliding window, detect face(s) for any test image of your choice. The test image should have at least one face it in. It can also have several faces: 1. Set k = 10, and display the test image with bounding boxes around all detected face(s) for the best threshold value. 2. Describe how well the method works.
Introduction to Computer Vision (ECSE 415) Assignment 1: Image FilteringSubmission Instructions 1. Submit a single Jupyter notebook consisting of the solution of the entire assignment. 2. Comment your code appropriately. 3. Give references for all codes which are not written by you. (Ex. the code is taken from an online source or from tutorials) 4. Do not forget to run Markdown (’Text’) cells. 5. Do not submit input/output images. Output images should be displayed in the Jupyter notebook itself. 6. Make sure that the submitted code is running without error. Add a README file if required. 7. If external libraries were used in your code please specify their name and version in the README file. 8. We are expecting you to make a path variable at the beginning of your codebase. This should point to your working local (or google drive) folder. Ex. If you are reading an image in the following format: img = cv2.imread ( ’/content/drive/MyDrive/Assignment1/images/shapes.png’ ) Then you should convert it into the following:path = ’/content/drive/MyDrive/Assignment1/images/’ img = cv2.imread(path + ’shapes.png’)Your path variable should be defined at the top of your Jupyter notebook. While grading, we are expecting that we just have to change the path variable once and it will allow us to run your solution smoothly. Specify, your path variable in the README file. 9. Answers to reasoning questions should be comprehensive but concise. 1 Denoising (20 points) You are not allowed to use OpenCV/Scikit-image functions for this section. For this question, you are expected to write your own code in NumPy for convolution. Note: For this question, you should work with grayscale images. DO NOT forget to convert your images to GrayScale from RGB images. Note 2: This question is worth 20 points: • 10 points for correct analysis and displaying desired outputs. • 10 points for correct, complete, and clean code. Do not forget to implement Convolution with NumPy, it has the biggest impact on your grade. 1.1 Gaussian Noise You are given a clean image named ’messi.png’ (Figure 1) and an image corrupted by additive white Gaussian noise (Figure 2). Apply the following filtering operations: 1. Filter the noisy image using a 3 × 3 Gaussian filter with variance equal to 3. Display the filtered image along with the original image (you can use openCV/scikit-learn function only for computing the gaussian filter). 2. Filter the noisy image using a box filter of the same size. Display the filtered image along with the original image. 3. Compare the Peak-Signal-to-Noise-Ratio (PSNR) of both of the denoised images to that of the clean image and state which method gives the superior result. Use the PSNR function provided by opencv/scikit-image. 1.2 Salt and Pepper Noise You are also given an image corrupted by salt and pepper noise (Figure 3). Apply the following filtering operations: 1. Filter the noisy image using the same Gaussian filter as used in the previous question. Display the filtered image along with the original image. 2. Filter the noisy image using a median filter of the same size. Display the filtered image along with the original image. 3. Compare the PSNR of both of the denoised images to that of the clean image and state which method gives a better result. You are allowed to use the PSNR function provided by opencv/scikit-image. 4. Describe the discrepancies between the two reference corrupted images: How are Gaussian noise and salt and pepper noise different? What is the best denoising method for these two types of noisy images? (You can use your findings and materials discussed in the classroom)Figure 1: Clean reference image (source)Figure 2: Image corrupted with Gaussian noise.3 Figure 3: Image corrupted with salt and pepper noise. 2 Canny Edge Detection (20 points) For this question, you will experiment with the Canny edge detection algorithm that was described in class. Experiments will be performed on the ’cntower.jpg’, Figure 4 image. Your goal is to develop an output like Figure 5. Note: Do not forget to convert the reference image into grayscale format. Also note that Figure 5 is probably not the best answer to the question. Note 2: This question is worth 20 points: • 10 points for correct analysis and displaying desired outputs. • 10 points for correct, complete, and clean code. 2.1. Briefly describe the 4 main steps of Canny edge detection. 2.2. Canny edge detection has three main parameters, as described in the tutorials. The Gaussiansmoothing Kernel size (K), the Lower (L), and the Higher (H) thresholds are used for Hysteresis. You will study the effects of changing these parameters in this part. You should run your experiments with this setup: ( K = 3, 5, 13; L = 10, 30, 50; H = 80, 100, 150). Note that you should vary the values of each parameter while keeping the other parameters constant. Repeat this procedure for all combinations of parameters mentioned above. This should result in a total of 27 triplets of parameters. Run the Canny edge detection algorithm (cv2.GaussianBlur and cv2.Canny) on the input image for each of these triplets and display the results. 2.3. Describe how changing values of each parameter (K, L, U) affects the overall edge detectionresults. Is there any relationship between parameters? 2.4. Combine parameters in such a way that edges related to the CN tower are detected (removeother edges related to clouds, etc.) The best solution will not necessarily be found in the values listed above, but you can report the best possible option from the 27 combinations that you have already experimented with. Both approaches are acceptable.Figure 4: Reference image for Question 2 (source) Figure 5: Sample output showing edges3 Harris Corner Detection (20 points) 1. Compute the image derivatives (optionally, blur first). 2. Compute the square of the derivatives. 3. Apply Gaussian Filtering on the output of Step 2. 4. Compute the cornerness function response: Determinant(H) − kTrace(H)2), where k=0.05. 5. Perform non-maximum suppression. Note 1: note that you can use OpenCV functions for gaussian filtering and computing image derivatives. Note 2: This question is worth 20 points: • 10 points for correct analysis and displaying desired outputs. • 10 points for correct, complete, and clean code. Apply the algorithm to three different images: 1. Maze image (Left part of Figure 6): Change the value of the threshold to attain detected corners that are similar to those in the right part of Figure 6. Observe and report the effect of changing the threshold values. 2. Shape image (Figure 7): Explore the different thresholds and report your observations. 3. Building image (Figure 8): Explore the different thresholds and report your observations. Figure 6: Maze input image and the expected Harris corner detector output. (red dots represent the detected Harris Figure 7: Image depicting different shaped blocks. (source) corners) (source)Figure 8: Image of a building. (source) 4 Invariance of SIFT Features (30 points) Note 1: This question is worth 30 points: • 10 points for correct analysis and displaying desired outputs for section 4.1 and 4.2. • 10 points for correct analysis and displaying desired outputs for section 4.3. • 10 points for correct, complete, and clean code. You are given a reference image of a Trevi Fountain in Rome as shown in Figure 9. Verify the invariance of SIFT features under changes in image scale and rotation. You are allowed to use inbuilt OpenCV/Scikit-Image functions for this question. 4.1 SIFT in a nutshell Briefly describe the 4 main actions/steps of SIFT method. 4.2 Invariance Under Scale 1. Compute SIFT keypoints for the reference image. 2. Scale reference image using scaling factors of (0.25, 0.6, 3, 5). This should result in a total of 4 different transformed images. Display scaled images. 3. Compute SIFT keypoints for all (total 4) transformed images. 4. Match all keypoints of the reference image to the transformed images using a brute-force method. 5. Sort matching keypoints according to the matching distance. 6. Display the top ten matched keypoints for each pair of the reference image and a transformed image. 7. Plot the matching distance for the top 100 matched keypoints. Plot indices of keypoints on the x-axis and corresponding matching distance on the y- axis. 8. Discuss the trend in the plotted results. What is the effect of increasing the scale on the matching distance? Explain. 4.3 Invariance Under Rotation 1. Rotate reference image at the angle of (30, 75, 90, 180). Display rotated images. 2. Compute SIFT keypoints for all (total 4) transformed images. 3. Match all keypoints of the reference image to the transformed images using a brute-force method. 4. Sort matching keypoints according to the matching distance. 5. Display the top ten matched keypoints for each pair of the reference image and a transformed image. 6. Plot the matching distance for the top 100 matched keypoints. Plot indices of keypoints on the x-axis and corresponding matching distance on the y-axis. 7. Discuss the trend in the plotted results. What is the effect of increasing the angle of rotation on the matching distance? Explain.Figure 9: Reference image for Question 4 (source)
ECSE 324 – Computer Organization Introduction In this lab will use the high level I/O capabilities of the DE1-SoC computer with a simultor. In particular, the tasks will: • Use the VGA controller to display pixels and characters. • Use the PS/2 port to accept input from a keyboard You will learn how to perform the aforementioned tasks on virtual DE1-SoC computer using online Computer System Simulator. A small tutorial on how to use the simulator is given in Section 3. 1 VGA For this part, it is necessary to refer to section 4.2 (pp 40-43) of the De1-SoC Computer Manual. Brief overview of the De1-SoC computer VGA interface The VGA controller hardware has already been introduced in the ECSE 222 labs. The De1-SoC computer has a built in VGA controller, and the data displayed to the screen is acquired from two sections in the FPGA on-chip memory – the pixel buffer and the character buffer – which are described in sufficient detail in section 4.2.1 and 4.2.3 of the De1-SoC Computer Manual. For this lab, it is not required to make use of the double buffering feature described in the manual. VGA driver Create an assembly files VGA.s where you will write the required subroutines and functions. You are required to write 5 subroutines: 1. VGAclearcharbuffASM 2. VGAclearpixelbuffASM 3. VGAwritecharASM 4. VGAwritebyteASM 5. VGAdrawpointASM The subroutines VGAclearcharbuffASM and VGAclearpixelbuffASM should clear (set to 0) all the valid memory locations in the character buffer and pixel buffer, respectively. Note that these two subroutine do not have any input/output arguments. The subroutine VGAwritechar ASM should write the ASCII code passed in the third argument (R2) to the screen at the (x,y) coordinates given in the first two arguments (R0andR1). Essentially, the subroutine will store the value of the third argument at the address calculated with the first two arguments. The subroutine should check that the coordinates supplied are valid (i.e. x = [0,79] and y = [0,59]). The subroutine VGAwritebyteASM should write the hexadecimal representation of the value passed in the third argument to the screen. This means that this subroutine will print two characters to the screen! (For example, passing a value of 0xFF in byte should result in the characters ’FF’ being displayed on the screen starting at the (x,y) coordinates passed in the first two arguments). Again, check that the (x,y) coordinates are valid, taking into account that two characters will be displayed. Hint: Both the above subroutines should only access the character buffer memory. Finally, the VGAdrawpointASM subroutine will draw a point on the screen with the colour as indicated in the third argument, by accessing only the pixel buffer memory. This subroutine is very similar to the VGAwritecharASM subroutine. NOTE-1: Use suffixes ‘B’ and ‘H’ with the assembly memory access instructions in order to read/modify the bytes/half-words of the memory contents. NOTE-2: You must follow the conventions taught in the class. NOTE-3: None of the subroutines has output arguments. Only the last three subroutines have three arguments (i.e., the (x,y) coordinates and the data to be stored in the character/pixel buffers.) Simple VGA application Build an assembly based application to test the functionality of the VGA subroutines. Translate the three functions shown in Figure 1 (in C) in assembly.Figure 1: C functions used to test the VGA driver You need to use the push-buttons to perform the following functions: • PB0 is pressed: call the testbyte() function. • PB1 is pressed: call the testchar() function. • PB2 is pressed: call the testpixel() function. • PB3 is pressed: clear both the character and pixel buffers. Note that this application relies on the push-buttons subroutines that you wrote in Lab 3. If you are unable to use these drivers, you will not be able to score fully on this part of the lab. However, in such case, we will give you some points if you are able to write a test program that calls the different functions above (without using the push-buttons) to demonstrate that they are fully working. NOTE: You must write all the functions in the same file that you write the subroutines (i.e., VGA.s). In other words, you are only required to write all the subroutines and functions in the same file named VGA.s. 2 Keyboard For this part, it is necessary to refer to section 4.5 (pp 45-46) in the De1-SoC Computer Manual. Brief overview of the PS/2 Keyboard Protocol For the purpose of this lab, a very high level description of the PS/2 keyboard protocol is given. A more detailed description can be found in the document named PS2 Keyboard. The PS/2 bus provides data about keystroke events by sending hexadecimal numbers called scan codes, which for this lab will vary from 1-3 bytes in length. When a key on the PS/2 keyboard is pressed, a unique scan code called the make code is sent, and when the key is released, another scan code called the break code is sent. The scan code set used in this lab can be found in the document named PS2 Keyboard under the Keyboard Scan Codes: Set 2 section (pages 21–22). Two other important parameters involved are the typematic delay and the typematic rate. When a key is pressed, the corresponding make code is sent, and if the key is held down, the same make code is repeatedly sent at a constant rate after an initial delay. The make code will stop being sent only if the key is released or another key is pressed. The initial delay between the first and second make code is called the typematic delay, and the rate at which the make code is sent after this is called the typematic rate. The typematic delay can range from 0.25 seconds to 1.00 second and the typematic rate can range from 2.0 cps (characters per second) to 30.0 cps, with default values of 500 ms and 10.9 cps respectively.(a) Key ’a’ is pressed and released(b) Key “a” is pressed, held down, and then released Figure 2: Example of data received on the PS/2 bus PS/2 keyboard driver Create an assembly file and name it ps2keyboard.s. For this lab, simply implement a subroutine with the following specifications: • Name: readPS2data ASM • Input argument (R0): A memory address in which the data that is read from the PS/2 keyboard will be stored (pointer argument) • output argument (R0): Integer that denotes whether the data read is valid or not • Description: The subroutine will check the RVALID bit in the PS/2 Data register. If it is valid, then the data from the same register should be stored at the address in the pointer argument, and the subroutine should return 1 to denote valid data. If the RVALID bit is not set, then the subroutine should simply return 0. Simple keyboard application Create a simple application that uses the PS/2 keyboard and VGA monitor. The application should read raw data from the keyboard and display it to the screen if it is valid. Only the VGAwritebyteASM subroutine is needed, and the input byte is simply the data read from the keyboard. Note: In the program, keep track of the x,y coordinates where the byte is being written. For example, write the first byte at (0,0) and the second byte at (3,0) and so on until the first line on the screen is full, and then start writing bytes at (0,1), (3,1), (6,1) etc. A gap of 3 x co-ordinates is given since each byte will display two characters, and one more for a space between each byte. 3 CPUlator: Computer System Simulator In this section, we provide a simple tutorial on how you can use the online simulator for this Lab. 1- Open the Computer System Simulator using this link: https://cpulator.01xz.net. 2- select ARMv7 architecture and ARMv7 DE1-SoC (v16.1) system and click on Go (see Figure 3).Figure 3: ARMv7 DE1-SoC (v16.1) 3- In the Editor panel select ARMv7 language (see Figure 4). Write all of your subroutines and functions in the Editor panel and save it with the desired name as specified in this Lab instruction.Figure 4: ARMv7 DE1-SoC (v16.1) 5- If for some unknown reason you encounter errors during debugging your code, you can simply ignore these errors by deselecting the features from the Debugging Checks in the Settings panel. Pay attention to the errors you are receiving. The simulator has a powerful documentation that you can access it by clicking on the errors. Read the documentation carefully before deselecting any features from the Debugging Checks. 6- You only need to interact with the Push buttons, VGA pixel buffer and PS/2 keyboard from the Device panel. The Device panel is located on the rightmost of your screen. Only use the PS/2 keyboard with the 0xFF200100 base address (see Figure 5).(a)(b)(c) Figure 5: (a) Push buttons (b) VGA and (c) PS/2 keyboard panels 4 Grading • VGA (50%) • P/2 Keyboard (30%) Your final submission should be a single compressed folder that contains all the code files, correctly organized (.c, .h and .s). For this lab, there is no report to write.
Learning Objectives This assignment is meant for you to practice what we have learned in class in the past few weeks. Several of the design decisions have been completed for you, but it is important for you to ask yourself why each choice has been made and whether there could be a better way of doing it. Some of our choices were influenced by the intention of having you practice most of what you have learned in class. Others, were dictated by our need to be able to fully test your assignments. Finally, we will not be grading your work on efficiency for the first assignment, but your implementation decisions can affect how efficient the code for this assignment is. Try to keep this in mind while coding. Make sure to ask yourselves why certain modifiers (private, public, static,…) were used and if you would have made the same decisions. We hope that the assignment will help you appreciate the importance of class design. We suggest you take the time to draw out the UML diagram. This should help you develop a clear picture of the relationship between all these classes. A New Store McGill has decided to unveil a new convenience store in Trottier that sells various food and drink items! You have been asked to program an AI assistant that monitors and handles all the store’s purchases. You have learned objectoriented programming and data structure. The store’s future is in your hands! • We need to represent various products available in the store. Can we use OOD to reduce the amount of copy-and-paste and re-use our implementations as much as possible? • We need to maintain a list of inventory, so we can add, remove, and retrieve items. Can we use a data structure for this? General Instructions • Your first late penalty is waved automatically at the end of the semester. There is no need to make an extra request. • Do not submit any other files, especially .class files and the tester files. Any failure to comply with these rules will give you an automatic 0. • Whenever you submit your files to Ed, you will see the results. If you do not see the results, your assignment is not submitted correctly. If your assignment is not submitted correctly, you will get an automatic 0. If your submission does not compile on ED, you will get an automatic 0. • In addition to the required methods, you are free to add as many other private methods and classes as you want (granted that all of the classes and methods listed below have been made). Unless otherwise specified, no other non-private fields or methods are allowed. • You can also add public toString() methods in each class to help with the debugging process, if you find it helpful. Submission Instructions • These are the files you should be submitting on Ed: – StoreItem.java – Drink.java – FizzWiz.java – SnoozeJuice.java – Snack.java – MyDate.java – ItemList.java – Store.java • You will have to create all the above classes from scratch. You are NOT allowed to import any other class (including for example ArrayList or LinkedList). Any failure to comply with these rules will give you an automatic 0. • Never make copies (neither shallow, nor deep) of any of the objects the methods return or receive as input, unless specified in the instructions. STEP 1: Building in Pieces Let’s start by writing a few abstract classes. These classes should be part of a package named items which is a subpackage of assignment1. StoreItem Write an abstract class StoreItem. • The class StoreItem has the following private fields: – A double indicating the price of the item. – An int representing the happiness index associated with this item. This is what measure of how much joy the item brings when consumed. • The StoreItem class will also have the following public methods: – A constructor that takes as input a double for the price and an int for the happiness index. The constructor uses its inputs to initialize the corresponding fields. If either of the values provided is negative, then an IllegalArgumentException should be thrown. To make the program raise the exception, write the following statement: throw new IllegalArgumentException(errMsg); where errMsg is a String containing an error message of your choice. – A final getPrice() method that retrieves the price of this item. – A getHappinessIndex() method that retrieves the happiness index of this item. – An equals() method that takes an Object as input and returns true if and only if it matches this in type, price, and happiness index. Be careful when comparing double: you do not want to compare values of type double directly! Instead you should consider the two values to be the same if their difference is very small, i.e. less than 0.001. Drink Now, we will write an abstract class called Drink in the same package which extends StoreItem. • The Drink class includes the following public static fields: – An int MAX PACK SIZE representing the maximum number of bottles a drink pack can contain. The default value is 6. – An int BUZZY HAPPINESS BOOST indicating the amount by which the happiness index of a drink will be increased if the drink is buzzy. Set the default value to 1. • The class should also have the following non-static fields: – A protected int representing the number of bottles available in this pack. – A private boolean indicating whether or not this drink is buzzy. Buzzy drinks generate extra excitement when consumed. • The class must also have the following public methods: – A constructor that takes as input a double for the price, an int for the happiness index, an int for the number of bottles, and boolean for the buzziness. The method updates the corresponding fields. Note that the happiness index and price provided for a drink are representative of a single bottle, and not of the entire pack. – A getNumOfBottles() method that retrieves the number of bottles of this drink. – An equals() method that takes an Object as input and returns true if and only if it matches this in type, price, happiness index, and buzziness. You should not be comparing the number of bottles! Note that you do not want to rewrite code that you have already written in the superclass. How can you access methods from the superclass that have been overridden? – A getHappinessIndex() method that overrides the one from StoreItem. For buzzy drinks, their happiness index should be boosted by the amount stored in the appropriate class variable. – A combine() method that takes another Drink as input and, if the input drink is considered equal to the current drink, combines as many bottles from the input drink as possible with this one. The number of bottles for both drinks should be updated to reflect the combination. The method returns true if the drinks were successfully combined (i.e., their number of bottles changed), and false otherwise. Note that no drink can exceed the MAX PACK SIZE number of bottles. For example, assume MAX PACK SIZE is 4, Drink A has 3 bottles in its pack, Drink B has 3 bottles in its pack, and the two drinks are equivalent. Then after executing A.combine(B), A has 4 bottles, B has 2 bottles, and the method returns true. On the other hand, if A had 4 bottles in its pack, A.combine(B) would return false. – An abstract getPortion() method that takes as input an int and returns a Drink. STEP 2: Expanding the Collection Now that we have built some abstract classes, we can construct classes that rely on them! Inside the same package (i.e. items) create the following classes: MyDate • The class has the following private fields: – An int representing the day – An int representing the month – An int representing the year • The class should also include two public static fields: • Finally, the class includes the following public methods – getDay(), getMonth(), getYear() methods that take no argument and return the corresponding field. – An equals() method which takes as input an Object and returns true if it matches this in type, day, month and year. Otherwise, the method returns false. – You can add a toString() method to get it in that lovely YYYY-MM-DD format. Snack We begin by writing a class called Snack which extends StoreItem • The Snack class has the following private fields: • The Snack class also has the following public methods: – A getHappinessIndex() method that overrides the one from StoreItem. For obvious reasons, the happiness gained from consuming a snack plummets when the snack in question tastes a little stale. Hence, if the snack is expired, its happiness index should be halved. FizzWiz Next, we’ll focus on drinks and write a class called FizzWiz, which extends Drink. This class represents a carbonated drink, famous for its bubbly and fizzy quality. • The FizzWiz class should include the following public methods: – A constructor that takes as input a double for the price, an int for the happiness index, and anther int for the number of bottles. Note that FizzWiz is a very buzzy drink! – An equals() method that takes an Object as input and returns true if and only if it matches this in type, price, happiness index, and buzziness. – A getPortion() method that takes as input an int indicating the number of bottles desired. If enough bottles are available in this drink, it returns a new FizzWiz with the specified number of bottles, while also updating the number of bottles in this drink accordingly. The drink returned should be equivalent to this FizzWiz. If there are not enough bottles available, the method should return null. SnoozeJuice Let’s now add another subclass of Drink named SnoozeJuice. This represents a relaxing drink like herbal tea, designed to help someone unwind or sleep – just the right beverage our students need before an intense study session! Like herbal teas, this beverage can be served hot or cold, so we should include a private double field to track its temperature (in Celsius). • The class should have the following private field. – A double representing the temperature in Celsius. • The class should also have the following public methods: – A constructor that takes as input a double for the price, an int for the happiness index, anther int for the number of bottles, and one more double for the temperature. As you can guess, snooze juices are not buzzy at all! – An equals() method that takes an Object as input and returns true if and only if it matches this in type, price, happiness index, buzziness, and temperature. Remember that when comparing doubles you should look at their difference and ensure it is smaller than 0.001. – A getPortion() method that takes as input an int indicating the number of bottles desired. If enough bottles are available in this drink, it returns a new SnoozeJuice with the specified number of bottles, while also updating the number of bottles in this drink accordingly. The SnoozeJuice returned should be equivalent to this one. If there are not enough bottles available, the method should return null. STEP 3: Adding a Data Structure Before we create our store, it would be nice to dynamically adjust the type and size of our offerings. To do this, we will create our own ItemList class. • The class will be part of the assignment1 package. We want to stress once again that you are not allowed to import any external classes for this assignment. You will have to import at least one class from assignment1.items. • The ItemList class should have the following private field: – An array of StoreItems which will be used to store the items that are part of the ItemList. • The class should also have the following public methods: – A getSize() method that takes no inputs and returns the number of items that are in the ItemList – A getAllItems() method that takes no input and returns all the items in the ItemList (in any order) in a StoreItem array. This array should not contain any unnecessary duplicates or null elements and should be exactly the size returned by this.getSize(). – A removeItem() method that takes a StoreItem as input and returns a StoreItem. The method removes the first occurrence of an item in the list that is equivalent to the specified item. The removed item is then returned by the method. If no such item exists, the method returns null. – A findEqualItems() method that takes as input a StoreItem and returns an array of StoreItems containing all of the items from this list that are equivalent to the specified one. If no equivalent items are found, the method returns an array of size 0. • In this class, you are permitted to add additional private fields, along with any private methods you find necessary. STEP 4: Finalizing the Store Now that the basis is complete, it is time to create our store! • The Store class belongs to the package assignment1. Inside it, you can import all classes from assignment1.items. • The class has the following private fields: – An ItemList, representing the items available at the store – A double representing the total revenue of the store • The Store also has the following public methods: – A constructor that takes as input an ItemList, and updates the corresponding fields. Note that the store will initially have zero revenue. – Two get methods getRevenue() and getItems() to retreive the values stored in the respective fields. – A cleanUp() method that takes no inputs and returns no value. The method goes through the store’s inventory and tosses out any snacks that have gone stale – nobody likes expired goodies! – A refillDrinkInventory() method that takes an array of Drinks as input and helps restock the store. But watch out – space at McGill is limited, so every bottle counts! If we already have some bottles of the same drink in stock, be sure to squeeze them together as efficiently as possible. Only add a new drink to the shelves if there’s really no more room. Note that, you cannot make any assumptions about the number of bottles in each drink item. Rubric Here is a description that outlines what you need to demonstrate to achieve a particular competency level (Proficiency, Approaching Mastery, Mastery). • Proficiency: At this level, you are expected to demonstrate a good understanding of basic object-oriented programming (OOP) concepts. The tasks at this level involve a straightforward application of what has been covered in class. This includes implementing constructors, getters, and simple methods to handle core functionality, such as managing the price and happiness index of store items, adding items to an ItemList, and overriding equals() where needed to ensure proper comparison of store items. Achieving proficiency means you are able to apply these fundamental concepts correctly and confidently, even if the problems are simple and familiar. • Mastery: At this level, you are expected to demonstrate a deep understanding of objectoriented programming by combining various pieces of what you’ve learned to solve new problems. You will need to design simple algorithms that weren’t directly presented in class, applying your knowledge in real-world scenarios. This includes creating methods like completeSale() and refillDrinkInventory(), where you manage dynamic changes to inventory and handle partial sales. These tasks require not only method overriding but also thoughtful interaction between objects, demonstrating your ability to handle polymorphism, dynamic object manipulation, and more advanced OOP techniques effectively. Mastery also involves recognizing and handling edge cases, ensuring that your solutions are robust. Successfully achieving mastery shows that you can think creatively, combine existing tools and knowledge in new ways, and design algorithms that address the complexities of real-world situations.
Learning Objectives In this assignment, you will get some experience working with linked lists and stacks. You will implement a data structure for a fun application. Starting with this assignment we will start to focus also on the efficiency of your algorithms. You will learn to look at code with a more critical eye, without only focusing on the correctness of your methods. General Instructions For this assignment need to download the files provided. Your task is to complete and submit the following files: Caterpillar.java • Please make sure that the file you submit is part of a package called assignment2. • You are NOT allowed to use any class other than those that have already been imported for you. Any failure to comply with these rules will give you an automatic 0. • Do NOT start testing your code only after you are done writing the entire assignment. It will be extremely hard to debug your program otherwise. If you need help debugging, feel free to reach out to the teaching staff. When doing so, make sure to mention what is the bug you are trying to fix, what have you tried to do to fix it, and where have you isolated the error to be. • Read through the description of all of the methods before starting to code. This will give you an idea of the general assignment and might help you decide on how to better organize your code (e.g. what could be a good private helper method to add?) Submission Instructions • Your first late penalty is waved automatically at the end of the semester. There is no need to make an extra request. • Do not submit any other files, especially .class files and the tester files. Any failure to comply with these rules will give you an automatic 0. • Whenever you submit your files to Ed, you will see the results. Your assignment is not submitted correctly if you do not see the results. If your assignment is not submitted correctly, you will get an automatic 0. If your submission does not compile on ED, you will get an automatic 0. • In addition to the required methods, you are free to add as many other private methods and classes as you want (granted that all of the classes and methods listed below have been made). Unless otherwise specified, no other non-private fields or methods are allowed.The Very Hungry Caterpillar Once upon a time, in a lush colorful meadow nestled between the rolling hills of MunchGill Valley, there lived a peculiar caterpillar named Gus. Now, Gus was no ordinary caterpillar. He had an insatiable appetite and an adventurous spirit that was as boundless as its stomach was bottomless. Gus’s favorite pastime was munching on delectable delicacies, and he had a particular fondness for trying new foods. One fine day, as he slithered along the meadow, he stumbled upon a magical patch of food that seemed to have an endless variety of treats – from succulent strawberries to Swiss cheese, and even shimmering stardust-infused snacks! This enchanted patch of food, however, came with a twist. Each time Gus indulged in a new treat, he magically transformed – he’d grow longer, shrink down, or hilariously flipFigure 1: Gus. An AI generated image from Canva’s Magic Media tool, created from the prompt ‘Gus, a colorful caterpillar with a big appetite and an adventurous spirit’.himself upside down. It didn’t matter though; Gus loved the adventure of it all and kept munching away. The students, eager to prove their skills, were thrilled by the task. They knew that, like Gus, they’d need to navigate some tricky twists and turns. They would need to use their knowledge of linked lists to represent Gus’s ever-changing body, ensuring that each segment of its wiggly form reflected its latest delicious bite. With wands (or rather, keyboards) in hand, the students set out to turn Gus’s gluttonous journey into a whimsical and hilarious game. As they coded, they knew they weren’t just crafting a program—they were bringing Gus’s unpredictable world to life, one bite at a time. What’s more, they began to realize that this journey, much like Gus’s, would teach them lessons beyond just data structures—lessons of efficiency, logic, and, of course, how to have fun with their code. And so, the fate of Gus’s gluttonous escapades was left to these budding computer scientists. Armed with their knowledge of singly linked lists, they embarked on their coding adventure, determined to craft a game worthy of Gus’s boundless appetite. Starter code Completed class You will need to understand how to use the following classes, but you should not modify them. • assignment2 package – A EvolutionStage.java, representing 4 different stages of the caterpillar with java enumeration. An enumeration is a special data type that represents a fixed set of constants. All you need to know for this assignment is that you can compare enumeration values using == and !=. For instance, EvolutionStage stage == EvolutionStage.FEEDING STAGE is a valid boolean expression. – A GameColors.java, representing 5 different colours that the caterpillar can have. – A Position.java, representing the position, defined by the x and y coordinates, in a 2-dimensional world. – A MyStack.java implements a stack with Java generic types. • assignment2.food package – This package contains all the classes representing the possible food items the caterpillar might encounter while slithering along the meadow. You can look inside these files to see what can be useful to you, but you should not modify them! The Caterpillar class You need to modify the Caterpillar.java in order to complete this assignment. A caterpillar will be represented as a singly linked list of Segments. A nested class Segment is in Caterpillar.java, A Segment stores the following information: • A Position, representing where this segment is (see Position.java). Throughout this pdf, we will represent such objects using the ordered pair (x, y). • A Color, representing the color of this specific segment. The colors of the segments will mostly depend on what the caterpillar has eaten in order to have gained those segments. • A Segment, representing the next segment in the body of the caterpillar. If this is the last body segment, then this field will be null. Each caterpillar is defined by the following fields: • Segment head : a reference to the head of the caterpillar • Segment tail : a reference to the last segment in the caterpillar’s body • int length : the number of segments in the caterpillar’s body • EvolutionStage stage : the stage in which the caterpillar finds itself. EvolutionStage is an enumeration. • MyStack positionsPreviouslyOccupied : all the positions previously occupied by the caterpillar with the most recent one on the top of the stack (this will become more clear once you read the description of the methods below). We will represent the stack as a list of elements between square bracket: the element at the top of the stack will be the right most one, while the element at the bottom of the stack will be the left most. • int goal : the number of segments the caterpillar aspires to in order to be able to become a wonderful butterfly. • int turnsNeededToDigest : the number indicating how many turns are left before the caterpillar is ready to take its next bite (see the method definitions below for more information). • static Random randNumGenerator : To use it, you must follow the following guidelines: – Do NOT assign a new reference to this variable. In fact, you should never in your code create a new Random object. – If asked to generate a random number you must use randNumGenerator. – You should generate random numbers only when it is strictly necessary. If in your code you fail to respect the guidelines above, your methods will probably not behave how we expect them to, leading to some tests possibly failing. Each caterpillar is defined by the following methods: • toString(): it has been implemented to make debugging a little easier for you. The method returns a string representing a caterpillar. The string contains the positions of each of the segments. The right most pair of coordinates represents the position of the head, while the left most represents the position of the tail. The color of the segment is used to color the text. So, for example, if we have a caterpillar with a red head in position (3,1), a second yellow segment in position (2,1), and its last blue segment in position (2,2), then toString() will return the following string: (2,2) (2,1) (3,1) • move(): the method that you need to implement in order to move the caterpillar. • eat(): this method has been overloaded for various food. You will need to provide the implementation. The methods are listed in the order of difficulty, but you don’t need to implement them in that order. Note that, all the fields of the Caterpillar class as well as the nested class Segment have been left public just to make testing easier on our side. As discussed in class, in general, you would want to keep as much as you can private and instead provide public getters/setters when needed. Step 1: Growing the Basics In this section, you’ll start by laying down the groundwork for your caterpillar, Gus. The tasks here will focus on implementing the foundational methods that allow Gus to grow, move, and interact with its surroundings. These basic operations are essential for understanding how linked lists function in Java, and they will provide you with the building blocks to handle more complex tasks later on. Take your time understanding how to implement this part carefully! • Caterpillar(Position p, Color c, int goal) : creates a caterpillar with one single segment of the given color, in the given position. The input goal is used to set the number of segments the caterpillar needs to acquire before becoming a butterfly. Whenever a caterpillar is first created, it finds itself in a feeding stage, ready to devour every delicacy within its reach. This method runs in O(1). • getSegmentColor(Position p) : returns the color of the segment in the given position. If the caterpillar, does not have a segment placed upon the given position, then the method returns null. This method runs in O(n), where n is the number of segments. • eat(Fruit f) : this foundational food group is the basis of growth for our wiggly friend. With each fruit bite, the caterpillar grows longer by getting a new segment added matching the color of the fruit ingested. The new segment should be added at the tail of the caterpillar, and its position should be the most recent position previously occupied by the caterpillar. Make sure to update all relevant fields to represent this growth. This method runs in O(1). • move(Position p) : if possible the caterpillar moves its head (and all its body) to the input position. If the input position is out of reach, i.e. if when seen as a point on a Cartesian plane it is not orthogonally connected to the head’s position, then an IllegalArgumentException should be raised. If the position is within reach, but it is already occupied by a segment of the caterpillar’s body, then moving will generate a collision leading to the caterpillar being in an ENTANGLED stage (unfortunately, caterpillars do not recover from this stage and the game will end.). If on the other hand, the position is reachable and moving to it would not lead to a collision, then the body of the caterpillar should be updated accordingly: all the positions in the segments should be updated to represent the caterpillar moving forward to the input position, while the colors remain the same. For example, below is the representation of a caterpillar before and after the move to the position (4,1): (2,2) (2,1) (3,1) (2,1) (3,1) (4,1) Or, using the representation with the Cartesian plane, this is how the caterpillar would change:The method should update the stack keeping track of the previously occupied positions accordingly (e.g., in the example above, the top of the stack would have become (2,2)). This method runs in O(n), where n is the number of segments. Safe Assumptions Throughout the assignment you can always assume the following: • The caterpillar will always move before attempting to eat. • The caterpillar will eat only when it is in a feeding stage. • The methods will be tested only on valid inputs: null is not a valid input for any of the methods! • The goal will always be initialized with a value greater than 1. • None of the methods will be called if the caterpillar is in a butterfly or entangled stage. Step 2: Tricky Treats Now that Gus is up and running, it’s time to deal with the more peculiar foods he encounters on its journey. In this section, you’ll implement methods to handle the quirky consequences of Gus eating pickles, lollipops, and ice cream. Each food brings its own challenge, requiring you to manipulate Gus’s body in more complex ways. • eat(Pickle p) : the sourness of the pickle makes the caterpillar retrace its steps. This method updates its segments accordingly. Note that the position where the pickle was found should not be added to the stack of previously occupied positions. For instance, suppose we have the following caterpillar: (2,2) (2,1) (3,1) And suppose that the most recent position previously occupied by this caterpillar is (2,3). Then, after eating a pickle the caterpillar will have the following segments: (2,3) (2,2) (2,1) It might be easier to picture those segments in a Cartesian plane. If you do so, this is how the caterpillar would change in the example above:This method runs in O(n), where n is the number of segments. • eat(Lollipop lolly) : this swirl of colors makes our caterpillar longing for a playful makeover. Shuffle all the caterpillar’s colors! There are different ways of doing this, but for this assignment you will need to implement the method using the Fisher–Yates shuffle algorithm. The algorithm runs in O(n) using O(n) space, where n is the number of segments. To perform a shuffle of the colors follow the steps: – Copy all the colors inside an array – Shuffle the array using the following algorithm: for i from n-1 to 1 do j
GitHub: https://classroom.github.com/a/v-VpEy-O General Instructions For this assignment, we provided starter code. Your task is to complete and submit the following files: – Deck.java – SolitaireCipher.java You will see these files when you successfully clone the assignment from GitHub. • Do not change any of the starter code that is given to you. Add code only where instructed, namely in the “ADD YOUR CODE HERE” block. This includes: – If you found that you have to change the folder structure to make it work in IntelliJ, there are probably problems with you IntelliJ setup for the “root of the source code”. Make sure IntelliJ recognizes the src folder as the root for your source code. You can check for more information at this link: https://www.jetbrains.com/help/idea/ content-roots.html#configure-folders. – Do not change any given code (e.g., names of the classes or methods, return types or parameters, etc). – Do not add any additional import statements. • You are NOT allowed to use any class other than those that have already been imported for you. • Any failure to comply with the above rules will give you an automatic 0. • You will get 0 if your code does not compile. Starting from this assignment, we are not fixing compilation errors for you! Make sure that your code is compilable. Don’t miss any semi-colon! • Do NOT wait until you are done writing the entire assignment to start testing your code. It will be extremely hard to debug your entire program. A good practice is to do unit tests: test each unit (a method) whenever you finish writing one. If you need help with debugging, feel free to reach out to the teaching staff. When doing so, make sure to mention what is the bug you are trying to fix, what have you tried to do to fix it, and where have you isolated the error to be. Submission instructions • All your work must be submitted on GitHub. Similar to the previous assignments, you can begin by accepting the assignment at https://classroom.github.com/a/v-VpEy-O. Subsequently, a repository naming assignment-1-*** will be created for you (*** is your GitHub username). You can then clone the repository, and work on it. If you want to recap the instructions to setup GitHub, clone your repository and submit your code, you can refer to the instructions of weekly assignment 1 (https://classroom.github.com/a/8qHfdL6n). • Don’t worry if you realize that you made a mistake after you submitted: you can git push multiple times but only the latest submission will be graded. Regularly pushing your work with well-documented commits is an encouraging practice to stay on track with your changes. You will be using the following commands. – git add * – git commit –m “update yyyy method in xxxx.java.” – git push • Do not submit any other files, especially .class files and the tester files. You are welcome to share your tester code with other students on Ed. Try to identify tricky cases. Do not hand in your tester code. • If you have any questions related to your grade, you can request a regrade within 7 days after the release of the grade by posting a private post on Ed and including your McGill ID. Learning Objectives There are several learning goals for this assignment. Firstly, this assignment aims to provide exposure to simple cryptography concepts. You will be introduced to the fundamental idea of a one-time pad and tasked with implementing an example of a stream cipher. Secondly, you will gain practical experience working with linked lists. Specifically, you will implement a data structure to represent a deck of cards. This implementation will utilize a circular doubly linked list. Thirdly, the assignment will emphasize the importance of algorithm efficiency. You will learn to evaluate and improve the efficiency of your code, moving beyond mere correctness to consider performance. Lastly, this assignment offers an opportunity for further practice in Java programming. While ECSE 250 primarily focuses on core computer science principles, programming remains an integral aspect. The more practice you engage in, the more proficient you will become. Introduction As the winter chill fades away and students scatter far and wide for the upcoming reading week, your friend – a recent computer science graduate – embarks on a mission: ‘Java.util.RemoteConnect,’ a venture aimed at facilitating secure communication among students, regardless of their physical location. In a stroke of creative genius (or perhaps just delirium from too many late-night coding sessions), they conceive of a plan involving a deck of cards and a sprinkle of cryptographic chaos. Inspired by the intrigue of Neal Stephenson’s ‘Cryptonomicon’, they aim to empower ECSE 250 students with a secret language, a digital code that transcends the ordinary. At the core of their endeavor lies a noble goal: to provide students with a means of communication that fosters trust and confidentiality, whether they’re collaborating on projects or simply catching up with classmates from afar during the break. Recognizing the importance of maintaining privacy in an increasingly digital world, they aim to create a virtual sanctuary where students can connect without fear of surveillance. Taking a cue from the novel’s clandestine communications via playing cards and the Solitaire encryption algorithm (thanks, Bruce Schneier!), your friend enlists your help in bringing their vision of a safer and more connected student community to life. The novel includes the description of the algorithm, but you can also find a revised version on the web . With the countdown to reading week ticking away faster than your friend can say ‘NullPointerException’, the pressure’s on to crack the code before the students disperse. Can you help your friend turn ‘Java.util.RemoteConnect’ into a digital lifeline for reading week, or will it end up being more of a ‘byte’-sized disaster? A bit of Crypto Background In 1917, Vernam patented a cipher now called one-time pad encryption scheme. The point of an encryption scheme is to transform a message so that only those authorized will be able to read it. One-time pad was later (in 1949) proved to be perfectly secret. The idea behind one-time pad is that given a plaintext message of length n, a uniformly random stream of digits of length n (which is the key) is generated and then used to encode the message. The message is concealed by replacing each character in the plaintext, with a character obtained combining the original one with one of the digits in the given key. Of course the message can be retrieved by performing the inverse operation on the characters of the encoded message (the ciphertext). Only those with access to the key can encode and decode a message. One-time pad is perfectly secret, but it has a number of drawbacks: for it to be secure, the key is required to be as long as the message, and it can only be used once! This clearly makes the cipher not a convenient one to use. Unfortunately, it was also proven that the limitations of one-time-pad are inherent to the definition of perfect secrecy. This means that to overcome those limitations the security requirements have to be relaxed. Stream ciphers use the same idea of one-time pad encryption scheme except that a pseudorandom sequence of digits is used as the pad instead of a random one. The idea is to use what are called ‘pseudorandom generators’ which given a smaller key can generate streams of pseudorandom digits. The Solitaire encryption algorithm is an example of a stream cipher. The key in this case is the deck of cards in its initial configuration. If two parties, Alice and Bob, share the same deck, following the Solitaire encryption algorithm they will be able to communicate by encoding and decoding messages. Of course, the deck and its configuration (i.e. the key) has to be kept secret to achieve secrecy. To encode and decode messages, Alice and Bob use the deck to generate a pseudorandom keystream which is then used as the “pad”. Encode/Decode with Solitaire Given a message to encode, we need to first remove all non–letters and convert any lower–case letters to upper–case. We then use the keystream of values and convert each letter to the letter obtained by shifting the original one a certain number of positions to the right on the alphabet. This number is the one found in the keystream in the same position as the character we are encoding. Decryption is just the reverse of encryption. Using the same keystream that was used to generate the ciphertext, convert each letter to the letter obtained by shifting the original one the given number of positions to the left on the alphabet. For example, let’s say that Alice wants to send the following message: Is that you, Bob? Then she will first remove all the non-letters and capitalize all the remaining ones obtaining the following: ISTHATYOUBOB She will then generate a keystream of 12 values. We’ll talk about the keystream generation in the next section, so let’s assume that the keystream is the following: 11 9 23 7 10 25 11 11 7 8 9 3 Finally, she can generate the ciphertext by shifting each letter the appropriate number of positions to the right in the alphabet. For example, the ‘I’ shifted 11 positions to the right, becomes a ‘T’. The ‘S’ shifted 9 positions to the right becomes a ‘B’. And so on! The final ciphertext will be: TBQOKSJZBJXE Bob, upon receiving the message, will need to generate the keystream. If Alice and Bob shared the same key and used it to generate the same number of pseudorandom values, then the keystream generated in this moment by Bob will be equal to that used by Alice to encrypt the message. All there’s left for Bob to do is convert all the letters by shifting them the appropriate number of position to the left. In our assignment, the “key” is a deck of cards in a specific configuration from which we can generate the keystream as explained in the next section. Generating a Keystream Using a Deck of Cards The harder part of the Solitaire encryption algorithm is generating the keystream. The idea is to use a deck of playing cards plus two jokers (a red one and a black one). Each card is associated with a value which depends on its rank and its suit. Cards in order from Ace to King have value 1 to 13 respectively. This value can increase by a multiple of 13 depending on the suit of the card. For this section let’s assume we’ll use the Bridge ranking for suits: clubs (lowest), followed by diamonds, hearts, and spades (highest). So, for instance, the Ace of clubs has value 1, while the 5 of diamonds has value 18, and the Queen of spades has value 51. The jokers have a value that depends on the number of cards in the deck. If the deck has a total of 54 cards (the 52 playing cards plus the two jokers), then the jokers have value 53. If the deck has total of 28 cards, then the jokers have value 27. That is, the jokers have both the same value and this value is equal to the total number of cards in the deck minus one. The keystream values depend solely on the deck’s initial configuration. We will implement the deck as a circular doubly linked list with the cards as nodes. This means that the first card (the one on the top of the deck) is linked to the last card (the one at the bottom of the deck) and the last card is linked to the first one. As an example, let’s consider a deck with 28 cards: the 13 of both clubs and diamonds, plus the two jokers. Let’s also consider the following initial configuration : AC 4C 7C 10C KC 3D 6D 9D QD BJ 3C 6C 9C QC 2D 5D 8D JD RJ 2C 5C 8C JC AD 4D 7D 10D KD The cards are represented with their rank, followed by their suit. For example, 6C denotes the 6 of clubs, JD the Jack of diamonds, and RJ the red joker. The cards are also listed in order from the top of to the bottom of the deck. Here are the steps to take to generate one value of the keystream: 1. Locate the red joker and move it one card below. (That is, swap it with the card beneath it.) If the joker is the bottom card of the deck, move it just below the card on the top of the deck. Note that, there is no way for the joker to become the top card as a result of this operation. After this step, the deck above will look as follows: AC 4C 7C 10C KC 3D 6D 9D QD BJ 3C 6C 9C QC 2D 5D 8D JD 2C RJ 5C 8C JC AD 4D 7D 10D KD 2. Locate the black joker and move it two cards below. If the joker is the bottom card of the deck, move it just below the second card from the top. If the joker is one up from the bottom card, move it just below the top card. As before, there is no way for the joker to become the top card as a result of this operation. After this step, the deck above will look as follows: AC 4C 7C 10C KC 3D 6D 9D QD 3C 6C BJ 9C QC 2D 5D 8D JD 2C RJ 5C 8C JC AD 4D 7D 10D KD 3. Perform a “triple cut”: that is, swap the cards above the first joker with the cards below the second joker. Note that here we use “first” and “second” joker to refer to whatever joker is nearest to, and furthest from, the top of the deck. Their colors do not matter. Note that the jokers and the cards between them do not move! If there are no cards in one of the three sections (either the jokers are adjacent, or one is on top or the bottom of the deck), just treat that section as empty and move it anyway. The deck will now look as follows: 5C 8C JC AD 4D 7D 10D KD BJ 9C QC 2D 5D 8D JD 2C RJ AC 4C 7C 10C KC 3D 6D 9D QD 3C 6C 4. Perform a “count cut”: look at the value of the bottom card. Remove that number of cards from the top of the deck and insert them just above the last card in the deck. The deck will now look as follows: 10D KD BJ 9C QC 2D 5D 8D JD 2C RJ AC 4C 7C 10C KC 3D 6D 9D QD 3C 5C 8C JC AD 4D 7D 6C 5. Finally, look at the value of the card on the top of the deck. Count down that many cards (Count the top card as number one) and look at the next card. If you hit a joker, ignore it and repeat the keystream algorithm (i.e. go back to step 1.). Otherwise, use the value of the card you counted to as the next keystream value. Note that this step does not modify the state of the deck. In our example, the top card is a 10 of diamonds which has value 23. By counting down to the 24th card we find the Jack of clubs which has value 11. Hence, 11 would be the first keystream value generated by our deck. To generate the next keystream value repeat the algorithm from step 1 using the current deck configuration. Instructions and Starter Code As mentioned in the section before we will use a circular doubly linked list to represent a deck of cards. The starter code contains two files with five classes which are as follows: • Deck – This class defines a deck of cards. Most of your work goes into this file. This class contains three nested classes: Card, PlayingCard, and Joker. • SolitaireCipher – This class represents a stream cipher that uses the Solitaire algorithm to generate the keystream and then encode/decode messages. Methods you need to implement For this assignment you need to implement all of the methods listed below. See the starter code for the full method signatures. Your implementations must be efficient. For each method below, we indicate the worst case run time using O() notation. • Deck.Deck(int numOfCardsPerSuit, int numOfSuits) : creates a deck with cards from Ace to numOfCardsPerSuit for the first numOfSuits in the class field suitsInOrder. The cards should be ordered first by suit, and then by rank. In addition to these cards, a red joker and a black joker are added to the bottom of the deck in this order. For example, with input 4 and 3, and suitsInOrder as specified in the file, the deck contains the following cards in this specific order: AC 2C 3C 4C AD 2D 3D 4D AH 2H 3H 4H RJ BJ The constructor should raise an IllegalArgumentException if the first input is not a number between 1 and 13 (both included) or the second input is not a number between 1 and the size of the class field suitsInOrder. Remember that a deck is a circular doubly linked list so make sure to set up all the pointers correctly, as well as the instance fields. • Deck.Deck(Deck d) : creates a deck by making a deep copy of the input deck. Hint: use the method getCopy from the class Card. Disclaimer: this is not the correct way of making a deep copy of objects that contain circular references, but it is a simple one and good enough for our purposes. • Deck.addCard(Card c) : adds the input card to the bottom of the deck. This method runs in O(1). • Deck.shuffle() : shuffles the deck. There are different ways of doing this, but for this assignment you will need to implement an algorithm that uses the Fisher–Yates shuffle algorithm. The algorithm runs in O(n) using O(n) space, where n is the number of cards in the deck. To perform a shuffle of the deck follow the steps: – Copy all the cards inside an array – Shuffle the array using the following algorithm: for i from n-1 to 1 do j
