1 Introduction In this lab you will learn how to describe finite state machines (FSMs) in VHDL. Specifically, you will design a special kind of a 4-bit counter using an FSM. This counter is not a regular up-counter. In addition to being bi-directional, i.e., it counts up and down, it goes through the following sequence of numbers: 1 ↔ 2 ↔ 4 ↔ 8 ↔ 3 ↔ 6 ↔ 12 ↔ 11 ↔ 5 ↔ 10 ↔ 7 ↔ 14 ↔ 15 ↔ 13 ↔ 9 (↔ 1 ↔ 2 ↔ 4…) Note that the right-arrow (i.e., →) denotes the upward direction whereas the left-arrow (i.e., ←) denotes the downward direction of the counter. See Section 8.7.5 of the textbook for a similar counter. Pushbuttons, slide switches and 7-segment LEDs will be used during this lab to control the counters when running on the Altera DE1-SoC board. 2 LearningOutcomes After completing this lab you should know how to: • Design an FSM for a counter • Perform functional simulation of the FSM using ModelSim • Test the FSM on the Altera board 3 FiniteStateMachine Similar to the previous lab, the FSM circuit works when the enable signal is high. The direction signal denotes the counting direction. Note that the counter should be initialized according to their direction when the asynchronous active-low reset signal is asserted. Use the leftmost value (1) in the counting sequence for the upward direction and the rightmost value (9) for the downward direction. First, draw the state diagram for the counter. Then using the state diagram describe the counter in VHDL. Use the following entity declaration to describe a Moore-style FSM implementing the above counter: l i b r a r y IEEE; use IEEE.STD_LOGIC_1164.ALL; use IEEE.NUMERIC_STD.ALL; e n t i t y gNN_FSM i s Port (enable : in s t d _ l o g i c ; direction : in s t d _ l o g i c ; reset : in s t d _ l o g i c ; clk : in s t d _ l o g i c ; count : out s t d _ l o g i c _ v e c t o r (3 downto 0)); end gNN_FSM; See Section 8.4 of the textbook for a discussion on how to design FSMs using VHDL. Once you have your circuit described in VHDL, you should simulate it. Write a testbench code and perform a functional simulation for your VHDL description of the FSM. 4 Multi-ModeCounter In this part, you will test your FSM circuit on the DE1-SoC FPGA board using the clock divider and 7-segment decoder circuits from the previous labs. You will also use pushbuttons, slide switches to control the functionality of the FSM. Pressing pushbuttons PB0, PB1 and PB2 starts/resumes, stops/pauses and resets the counter, respectively. When these buttons are released, the circuit has to remain at the new state denoted by their corresponding function. For example, when PB1 is pushed and then released, the FSM circuit pauses the count until told otherwise by pushing other pushbuttons. Therefore, you need a memory to hold the state imported by the pushbuttons. Note that the output of a pushbutton is high when the button is not being pushed, and is low when the button is being pushed. The counter direction is entered from one of the slide switches on the board. The first two 7-segment displays (i.e., HEX1-0) are used to show the count in decimal format. Use the clock divider circuit from the previous lab to show the current count on the 7-segment displays at every 1 second. TotesttheFSMcircuitontheFPGAboard,youwillneedtocreateinstancesofyourgNN_clock_dividerandgNN_7_segment_decoder to display the current value of the counter after each 1 second. Describe the system testing the FSM circuit on the FPGA board, which is hereafter referred to as multi-mode counter, in VHDL using the following entity declaration: l i b r a r y IEEE; use IEEE.STD_LOGIC_1164.ALL; use IEEE.NUMERIC_STD.ALL; e n t i t y gNN_multi_mode_counter i s Port (start : in s t d _ l o g i c ; stop : in s t d _ l o g i c ; direction : in s t d _ l o g i c ; reset : in s t d _ l o g i c ; clk : in s t d _ l o g i c ; HEX0 : out s t d _ l o g i c _ v e c t o r (6 downto 0); HEX1 : out s t d _ l o g i c _ v e c t o r end gNN_multi_mode_counter; (6 downto 0)); 5 DeliverablesandGrading 5.1 Demo • fully explain how the HDL code works, • perform functional simulation using ModelSim, and • demonstrate that the FSM circuit is functioning properly using the pushbuttons, slide switches and 7-segment LEDs on the DE1-SoC board. 5.2 Written report You are also required to submit a written report and your code on myCourses. Your report must include: • The state diagram of your FSM. • A description of the FSM circuit. • A discussion of how the FSM circuit was tested, showing representative simulation plots. How do you know that these circuits work correctly? • A description of the multi-mode counter circuit. • A discussion of how the multi-mode counter circuit was tested on the FPGA board. • AsummaryoftheFPGAresourceutilization(fromtheCompilationReport’sFlowSummary)andtheRTLschematic diagram for the multi-mode counter circuit. Clearly specify which part of your code maps to which part of the schematic diagram. Finally, when you prepare your report have in mind the following: • The title page must include the lab number, name and student ID of the students, as well as the group number. • All figures and tables must be clearly visible. • The report should be submitted in PDF format. • It should document every design choice clearly. • The grader should not have to struggle to understand your design. That is, – Everything should be organized for the grader to easily reproduce your results by running your code through the tools. – The code should be well-documented and easy to read.
1 Introduction In this lab you will learn how to describe sequential logic circuits in VHDL. You will design a stopwatch measuring time every 10 milliseconds. Also, you will use pushbuttons and 7-segment LEDs to control the stopwatch when running on the Altera DE1-SoC board. 2 LearningOutcomes After completing this lab you should know how to: • Design a counter in VHDL • Perform functional simulation of the counter using ModelSim • Design a stopwatch measuring time at every 10 milliseconds • Test the stopwatch on the Altera board 3 Counters A counter is a special sequential circuit. When counting up (by one), we require a circuit capable of “remembering” the currentcountandadding1thenexttimewerequestacount. Whencountingdown(byone),werequireacircuitcapable of “remembering” the current count and subtracting 1 the next time we request a count. Counters use a clock signal to keep track of time. In fact, each increment occurs (or decrement) occurs when one clock period has passed. Since countersarethemainbuildingblocksofstopwatches,wewillfirstdesignan4-bitup-counterwithanasynchronousreset (which should be active low) and an enable signal. The counter counts up when the enable signal is high. Otherwise, the counter holds its previous values. Use the following entity declaration for your VHDL description of the counter: l i b r a r y IEEE; use IEEE.STD_LOGIC_1164.ALL; use IEEE.NUMERIC_STD.ALL; e n t i t y gNN_counter i s Port (enable : in s t d _ l o g i c ; reset : in s t d _ l o g i c ; clk : in s t d _ l o g i c ; count : out s t d _ l o g i c _ v e c t o r (3 downto 0)); end gNN_counter; Note that the up-counter that you have designed in this section will be used later in Section 5 to build a stopwatch. Once you have your circuit described in VHDL, you should simulate it. Write a testbench code and perform a functional simulation for your VHDL description of the counter. 4 ClockDivider A clock divider is a circuit that generates a signal that is asserted once every T clock cycles. This signal can be used as a condition to enable the counters in the stopwatch circuit. An example of the clock and output (i.e., “enable”) waveforms for T= 4 is:Implementing the clock divider circuit requires a counter counting clock periods. The counter counts down from T − 1 to 0. Upon reaching the count of 0, the clock divider circuit outputs/asserts 1 and the count is reset to T − 1. For other values of the counter, the output signal of the clock divider circuit remains 0. In this lab, we want to design a stopwatch counting in increments of 10 milliseconds. In other words, we need to assert an enable signal every 10 milliseconds. First, find the value of T for the clock divider circuit to generate an enable signal every 10 milliseconds. Note that the PLL, the device which supplies the clock for your design on the DE1-SoC board, works at a frequency of 50 MHz. Then, describe the clock divider circuit in VHDL using the following entity declaration: l i b r a r y IEEE; use IEEE.STD_LOGIC_1164.ALL; use IEEE.NUMERIC_STD.ALL; e n t i t y gNN_clock_divider i s Port (enable : in s t d _ l o g i c ; reset : in s t d _ l o g i c ; clk : in s t d _ l o g i c ; en_out : out s t d _ l o g i c ); end gNN_clock_divider; Hint: the following figure shows an example of the clock divider circuit. Also, note that the down-counter inside the clock divider circuit is different from the up-counter that you designed in Section 3.Once you have your circuit described in VHDL, write a testbench code and perform a functional simulation for your VHDL description of the clock divider. 5 Stopwatch Inthispart,youwilldesignasimplestopwatchusingthecounterandclockdividercircuits. Youwillusethepushbuttons to control the stopwatch and 7-segment displays to display the elapsed time in decimal. Pushbuttons PB0, PB1 and PB2 are used to start (or resume), pause and reset the stopwatch, respectively. When these buttons are released, the circuit has to remain at the new state denoted by their corresponding function. For example, when PB1 is pushed and then released, the stopwatch circuit pauses the count until told otherwise by pushing pne of the other pushbuttons. Therefore, you need a memory element to hold the operating state (e.g., running, paused) of the stopwatch. Note that theoutputofapushbuttonishighwhenthebuttonisnotbeingpushed,andislowwhenthebuttonisbeingpushed. The first two 7-segment displays (i.e., HEX1-0), the second two 7-segment displays (i.e., HEX3-2) and the last two 7-segment displays (i.e., HEX5-4) are used to show time in centiseconds, seconds and minutes, respectively. You will need to create six instances of your gNN_counter and gNN_7_segment_decoder you created in Lab Assignment #1 for each decimal digit in the stopwatch. Since we measure time in increments of 10 milliseconds, the counter measuring time in centiseconds increments only when the output signal of the clock divider circuit becomes high. The following figure shows the high-level architecture of the stopwatch circuit.Note that counters #0, #1, #2, and #4 count from 0 to 9, while counters #3 and #5 count from 0 to 5. Describe the stopwatch circuit in VHDL using the following entity declaration: l i b r a r y IEEE; use IEEE.STD_LOGIC_1164.ALL; use IEEE.NUMERIC_STD.ALL; e n t i t y gNN_stopwatch i s Port (start : in s t d _ l o g i c ; stop : in s t d _ l o g i c ; reset : in s t d _ l o g i c ; clk : in s t d _ l o g i c ; HEX0 : out s t d _ l o g i c _ v e c t o r (6 downto 0); HEX1 : out s t d _ l o g i c _ v e c t o r (6 downto 0); HEX2 : out s t d _ l o g i c _ v e c t o r (6 downto 0); HEX3 : out s t d _ l o g i c _ v e c t o r (6 downto 0); HEX4 : out s t d _ l o g i c _ v e c t o r (6 downto 0); HEX5 : end gNN_stopwatch; out s t d _ l o g i c _ v e c t o r (6 downto 0)); 6 DeliverablesandGrading 6.1 Demo • fully explain how the HDL code works, • perform functional simulation using ModelSim, and • demonstratethatthestopwatchcircuitisfunctioningproperlyusingthepushbuttonsand7-segmentLEDsonthe DE1-SoC board. 6.2 Written report You are also required to submit a written report and your code on myCourses. Your report must include: • Adescriptionofthecounterandclockdividercircuits. Explainwhythesetwocircuitsareconsideredassequential designs. • Explain why even though we could build a clock divider using an up-counter it is easier to build the divider using a down-counter. • A discussion of how the counter and clock divider circuits were tested, showing representative simulation plots. How do you know that these circuits work correctly? • A description of the stopwatch circuit. Explain why you created six instances of the counter circuit in your design and why? • A discussion of how the stopwatch circuit was tested. • AsummaryoftheFPGAresourceutilization(fromtheCompilationReport’sFlowSummary)andtheRTLschematic diagram for the stopwatch circuit. Clearly specify which part of your code maps to which part of the schematic diagram. Finally, when you prepare your report have in mind the following: • The title page must include the lab number, name and student ID of the students, as well as the group number. • All figures and tables must be clearly visible. • The report should be submitted in PDF format. • It should document every design choice clearly. • The grader should not have to struggle to understand your design. That is, – Everything should be organized for the grader to easily reproduce your results by running your code through the tools. – The code should be well-documented and easy to read.
1 Introduction In this lab you will learn the basics of the Altera Quartus II FPGA design software through following a step-by-step tutorial, and use it to implement combinational logic circuits described in VHDL. You will also learn the basics of digital simulation using the ModelSim simulation program. 2 LearningOutcomes After completing this lab you should know how to: • Run the Intel Quartus software • Create the framework for a new project • Design and perform functional simulation of a Binary-to-7-segment LED decoder circuit • Design a 5-bit adder using VHDL • Test the adder on the Altera board 3 RunIntelQuartus In this course you will be using commercial FPGA design software: the Intel Quartus Prime program and the Mentor Graphics ModelSim simulation program. Quartus Prime and ModelSim are installed on the computers in the lab. You can also obtain a slightly restricted version, the Quartus Lite edition, from the Intel web site . The program restrictions will not affect any designs you will be doing in this course. You can (and you should) install the applications on your personal computer to work on your project outside of the lab. You should use version 18.0 of the program, as this is the latest version that supports the prototyping board (the Altera DE1-SoC board) that you will be using. To begin, start Quartus Prime by selecting it in the Windows Start menu:IntelQuartusPrimeemploysaproject-basedapproach. ThegoalofaQuartusprojectistodevelopahardwareimplementation of a specific function, targeted to an FPGA (Field Programmable Gate Array) device. Typically, the project will involve a (large) number of different circuits, each designed individually, or taken from circuit libraries. Project management is therefore important. The Quartus Prime program aids in the project management by providing a project framework that keeps track of the various components of the project, including design files (such as schematic block diagrams or VHDL descriptions), simulation files, compilation reports, FPGA configuration or programming files, project specific program settings and assignments, and many others. The first step in designing a system using the Quartus Prime approach is therefore to create the project framework. The program simplifies this by providing a “Wizard” which guides you through a step-by-step setting of the most important options. To run the Project Wizard, click on the File menu and select the New Project Wizard entry.4 CreatingaNewProject The New Project Wizard involves going through a series of windows. The first window is an introduction, listing the settings that can be applied. After reading the text on this window, click on “Next” to proceed.In the second window, you should give the project the following name: gNN_lab1 where NN is your 2-digit group number. The working directory for your project will be different than that shown in the screenshot below. Use your network drive for your project files.We don’t have a project template at this point, so select Empty project and proceed.You will add files later, so for now, just click on “Next”.In this lab, you will be downloading a design to an FPGA device on the DE1-SoC board. These devices belong to the Cyclone V family of FPGAs, with the following part number: 5CSEMA5F31C6. To ensure proper configuration of the FPGAs, select this device as shown below.The dialog box in the next window permits the designer to specify 3rd-party tools to use for various parts of the design process. We will be using a 3rd-party Simulation tool called ModelSim-Altera, so select this item from the Simulation drop-down menu.The final page in the New Project Wizard is a summary. Check it over to make sure everything is OK (e.g., the project name, directory, and device assignment), then click Finish.Your project framework is now ready. In File, click on New, and then select VHDL file from the list as shown below.You should have a VHDL editor opened in your framework. You will write and edit your code from this editor.5 DesignaBinaryto7-SegmentLEDDecoder A 7-segment LED display has 7 individual LED segments, as shown below. By turning on different segments at any one time we can obtain different characters or numbers. There are six of these on the DE1-SoC board, which you will use later in your full implementation of the adder to display the result.In this part of the lab, you will design a circuit that will be used to drive the 7-segment LEDs on the DE1 board. It takes a 4-bit binary code representing the 16 hexadecimal digits between 0 and F (see figure below) as input, and generates the appropriate 7-segment display associated with the input code. Note that the outputs should be made active-low. This is convenient, as many LED displays, including the ones on the DE1 board, turn on when their segment inputs are driven low. Note that active low means “1” is off and “0” is on.To implement the 7-segment LED decoder, write a VHDL description using a single selected signal assignment statement. Use the following entity declaration, replacing the NN in gNN_7_segment_decoder with your group’s number (e.g., g08). l i b r a r y IEEE; use IEEE.STD_LOGIC_1164.ALL; use IEEE.NUMERIC_STD.ALL; e n t i t y gNN_7_segment_decoder i s Port ( code : in s t d _ l o g i c _ v e c t o r (3 downto 0); segments : out end gNN_7_segment_decoder; s t d _ l o g i c _ v e c t o r (6 downto 0)); 6 SimulationofthecircuitusingModelSim Once you have your circuit described in VHDL you should simulate it. The purpose of simulation is generally to determine: 1. if the circuit performs the desired function, and 2. if timing constraints are met. In the first case, we are only interested in the functionality of our implementation. We do not care about propagation delays and other timing issues. Because of this, we do not have to map our design to a target hardware. This type of simulation is called functional simulation. This is the type of simulation we will learn about in this lab. In this course, you will be using the ModelSim simulation software, created by the company Mentor Graphics (actually you will use a version of it specific to Quartus, called Modelsim-Altera). The Modelsim software operates on an Hardware Description Language (HDL) description of the circuit to be simulated, written either in VHDL, Verilog, or System-Verilog. You will use VHDL. Double-click on the ModelSim desktop icon to run the ModelSim program. A window similar to the one shown below will appear.Select FILE>New>Project and, in the window that appears, give the project the name gNN_lab1.Once you click OK, another dialog box will appear allowing you to add files to the project. Click on “Add Existing File” and select the VHDL file that was generated earlier (gNN_7_segment_decoder). You can also add files later.The ModelSim window will now show your VHDL file in the Project pane.To simulate the design, ModelSim must analyze the VHDL files, a process known as compilation. The compiled files are stored in a library. By default, this is named “work”. You can see this library in the “library” pane of the ModelSim window.The compiled VHDL files will now appear in the library “work”.Since all of the inputs are undefined, if you ran the simulation now, the outputs would be undefined. So you need to have a means of setting the inputs to certain patterns, and of observing the outputs’ responses to these inputs. In ModelSim, this is done by using a special VHDL entity called a Testbench. A testbench is special VHDL code that generates different inputs that will be applied to your circuit so that you can automate the simulation of your circuit and see how its outputs respond to different inputs. Note that the testbench is only used in Modelsim for the purposes of simulating your circuit. You will eventually synthesize your circuits into a real hardware chip called an FPGA. However, you will NOT synthesize the testbench into real hardware. Because of its special purpose (and that it will not be synthesized), the testbench entity is unique in that it has NO inputs or outputs, and uses some special statements that are only used in test benches. These special statements are not used when describing circuits that you will later synthesize to a FPGA. The testbench contains a single component instantiation statement that inserts the module to be tested (in this case the gNN_7_segment_decoder module), as well as some statements that describe how the test inputs are generated. After you gain more experience you will be able to write VHDL testbenches from scratch. However, Quartus has a convenient built-in process, called the Test Bench Writer, which produces a VHDL template from your design that will get you started. To get the template, go back to the Quartus program, making sure that you have the gNN_7_segment_decoder project loaded. Then, in the Processing toolbar item, select “Start/Start Test Bench Template Writer”. This will generate a VHDL file named gNN_7_segment_decoder.vht and place it in the simulation/modelsim directory. There are 24 or 16 possible patterns in the gNN_7_segment_decoder circuit, so complete testing of the circuit will require you to simulate all of these patterns. In order to run through all possible 16 cases, we use a FOR LOOP that increments the value of code signal in the loop. This is done in the testbench shown below. generate_test : PROCESS BEGIN FOR i IN 0 to 15 LOOP — loop over all code values code Add to Project > Existing File…. Once the testbench file has been added to the project, you should select the testbench file in the Project pane, and click on CompileSelected from the Compile toolbar item. This will compile the testbench file. Now everything is ready for you to actually run a simulation! Select “Start Simulation” from the Simulate toolbar item in the ModelSim program. The window shown below will appear.Select the gNN_7_segment_decoder_tst entity and click on OK. The ModelSim window should now look like the figure below.At first, the “Wave” window will not have any signals in it. You can drag signals from the “Objects” window by click on a signal, holding down the mouse button, and dragging the signal over to the Wave window. Do this for all the signals. The Wave window will now look like the one shown in Figure 1.Figure 1: Signal waveform in ModelSim. Now, to actually run the simulation, click on the “Run all” icon in the toolbar. Check the output of your implementation for every single case. If you get an incorrect output waveform, you will have to go back and look at your design. If you make a correction to your VHDL code, you will have to re-run the compilation of the changed files in ModelSim. Finally, to rerun the simulation, first click on the “Restart” button, then click on the “Run all” button. 7 Designa5-bitAdder In this part of the lab, you will design a circuit performing addition on two 5-bit inputs A and B. It also displays inputs and the result of the addition in hexadecimal format on the 7-segment LEDs on the DE1-SoC board. Note that you should use the binary-to-7-segment LED decoder to obtain appropriate 7-segment display code. Moreover, each signal requires two hexadecimal digits for representation. Therefore, you will need to use all the six 7-segment LEDs on the aboard in this lab. UsethefollowingentitydeclarationtowriteaVHDLdescriptionoftheaddercircuit. Notethatyouhavetoinstantiate from the gNN_7_segment_decoder circuit in you VHDL description. l i b r a r y IEEE; use IEEE.STD_LOGIC_1164.ALL; use IEEE.NUMERIC_STD.ALL; e n t i t y gNN_adder i s Port ( A, B : in s t d _ l o g i c _ v e c t o r (4 downto 0); decoded_A : out s t d _ l o g i c _ v e c t o r (13 downto 0); decoded_B : out s t d _ l o g i c _ v e c t o r (13 downto 0); decoded_AplusB end gNN_adder; : out s t d _ l o g i c _ v e c t o r (13 downto 0)); 8 TestingtheAdderontheAlteraBoard You will now test the adder circuit you designed in Section 7. Compile the decoder in the Quartus software. Once you have compiled the adder circuit, it is time to map it onto the target hardware, in this case the Cyclone V chip on the Altera DE1-SoC board. Please begin by reading over the DE1-SoC userâA˘Zs manual, which can be found on the myCourses lab´ experiments page. Since you will now be working with an actual device, you have to be concerned with which device package pins the variousinputsandoutputsoftheprojectareconnected. Inparticular, youwillwanttoconnecttheLEDsegmentoutputs from the instances of the gNN_7_segment_decoder circuit (i.e., the outputs of the adder circuit) to the corresponding segments of one of the six 7-segment LED displays on the board. The mapping of the board’s 7-segment LEDsâA˘Z´ segments to the pins on the Cyclone FPGA device is listed in Table 3-9 on page 24 of the DE1-SoC Development and Education Board Users Manual. You will also want to connect, for testing purposes, 5 of the slide switches on the DE1-SoC board to the input A and the rest to the input B of the gNN_adder circuit. The mapping of the slide switches to the FPGA pins is given in Table 3-6 on pages 23 of the DE1 userâA˘Zs manual.´ YoucantellthecompilerofyourchoicesforpinassignmentsforyourinputsandoutputsbyopeningthePinPlanner, which can be done by choosing the Pins item in the Assignments menu, as shown below.Next, double-click the FPGA device (5CSEMA5), and from the window that opens add the .sof file created by Quartus. Finally, check the “Program/configure” box beside the 5CSEMA5 device, and then click “Start”. Now, you should be able to use slide switches to insert values for inputs A and B. The 7-segment LEDs should also display inputs and outputs in hexadecimal format. 9 DeliverablesandGrading 9.1 Demo • fully explain how the HDL code works, • perform functional simulation using ModelSim, and • demonstrate that the adder circuit is functioning properly using the slide switches and 7-segment LEDs on the DE1-SoC board. 9.2 Written report You are also required to submit a written report and your code on myCourses. Your report must include: • A description of the 7-segment decoder circuit. Explain why you used the selected signal assignment instead of the conditional signal assignment. • A discussion of how the 7-segment decoder circuit was tested, showing representative simulation plots. How do you know that the circuit works correctly? • A description of the adder circuit. How many 7-segment decoder instances did you use in your design and why? • A discussion of how the adder circuit was tested. • AsummaryoftheFPGAresourceutilization(fromtheCompilationReport’sFlowSummary)andtheRTLschematic diagram for both the 7-segment decoder and the adder circuits. Clearly specify which part of your code maps to which part of the schematic diagram. Finally, when you prepare your report have in mind the following: • The title page must include the lab number, name and student ID of the students, as well as the group number. • All figures and tables must be clearly visible. • The report should be submitted in PDF format. • It should document every design choice clearly. • The grader should not have to struggle to understand your design. That is, – Everything should be organized for the grader to easily reproduce your results by running your code through the tools. – The code should be well-documented and easy to read.
Rate this product
CSED342 – Artificial Intelligence This assignment has been developed in Python 3.8, so please use Python 3.8 to implement your code. we recommend using Conda environment. You should modify the code in submission.py between # BEGIN_YOUR_ANSWER and # END_YOUR_ANSWER You can add other helper functions outside the answer block if you want, but do not import other libraries and do not make changes to files other than submission.py. Your code will be evaluated on two types of test cases, basic and hidden, which you can see in grader.py. Basic tests, which are fully provided, do not stress your code with large inputs or tricky corner cases. Hidden tests are more complex and do stress your code. The inputs of hidden tests are provided in grader.py, but the correct outputs are not. To run all the tests, type python grader.py This will tell you only whether you passed the basic tests. The script will alert you if your code takes too long or crashes on the hidden tests, but does not say whether you got the correct output. You can also run a single test (e.g., 2a-0-basic) by typing python grader.py 2a-0-basic We strongly encourage you to read and understand the test cases, create your own test cases, and not just blindly run grader.py. Introduction This assignment is a modified version of the Driverless Car assignment written by Chris Piech. A study by the World Health Organisation found that road accidents kill a shocking 1.24 million people a year worldwide. In response, there has been great interest in developing autonomous driving technology that can drive with calculated precision and reduce this death toll. Building an autonomous driving system is an incredibly complex endeavor. In this assignment, you will focus on the sensing system, which allows us to track other cars based on noisy sensor readings. Getting started. Let’s start by trying to drive manually: python drive.py -l lombard -i none You can steer by either using the arrow keys (↑, ←, →) or ’w’, ’a’, and ’d’, and quit drive.py by using ’q’. Note that you cannot reverse the car or turn in place. Your goal is to drive from the start to finish (the green box) without getting in an accident. How well can you do on crooked Lombard street without knowing the location of other cars? Don’t worry if you aren’t very good; the staff was only able to get to the finish line 4/10 times. This 60% accident rate is pretty abysmal, which is why we’re going to build an AI to do this. Flags for python drive.py: • -a: Enable autonomous driving (as opposed to manual). • -i : Use none, exactInference, particleFilter to (approximately) compute the belief distributions. • -l: Use this map (e.g. small or lombard). Defaults to small. • -d: Debug by showing the all cars on the map. • -p: All other cars remain parked (so that they don’t move). Modeling car locations We assume that the world is a two-dimensional rectangular grid on which your car and K other cars reside. At each time step t, your car gets a noisy estimate of the distance to each of the cars. As a simplifying assumption, we assume that each of the K other cars moves independently and that the noise in sensor readings for each car is also independent. Therefore, in the following, we will reason about each car independently (notationally, we will assume there is just one other car). At each time step t, let Ct ∈ R2 be a pair of coordinates representing the actual location of the single other car (which is unobserved). We assume there is a local conditional distribution p(ct | ct−1) which governs the car’s movement. Let at ∈ R2 be your car’s position, which you observe and also control. To minimize costs, we use a simple sensing system based on a microphone. The microphone provides us with Dt, which is a Gaussian random variable with mean equal to the distance between your car and the other car and variance σ2 (in the code, σ is Const.SONAR_STD, which is about two-thirds the length of a car). In symbols, Dt ∼ N(∥at − Ct∥,σ2). (1) For example, if your car is at at = (1,3) and the other car is at Ct = (4,7), then the actual distance is 5 and Dt might be 4.6 or 5.2, etc. Use util.pdf(mean, std, value) to compute the probability density function (PDF) of a Gaussian with given mean and standard deviation, evaluated at value. Note that the PDF does not return a probability (densities can exceed 1), but for the purposes of this assignment, you can get away with treating it like a probability. The Gaussian probability density function for the noisy distance observation Dt, which is centered around your distance to the car µ = ∥at − Ct∥:The figure below shows another example where a black car (ours) and gray cars are located in the 2D grid and the sensor estimates the distances of the black car from the other cars. Note that we can access the information of distances (Dt) measured by the sensor, but we’re not provided with the exact locations (Ct) of gray cars.Your job is to implement a car tracker that (approximately) computes the posterior distribution P(Ct | D1 = d1,…,Dt = dt) (your beliefs of where the other car is) and update it for each t = 1,2,…. We will take care of using this information to actually drive the car (i.e., set at to avoid collision with ct), so you don’t have to worry about that part. To simplify things, we will discretize the world into tiles represented by (row, col) pairs, where 0 ≤ row < numRows and 0 ≤ col < numCols. For each tile, we store a probability distribution whose values can be accessed by self.belief.getProb(row, col). To convert from a tile to a location, use util.rowToY(row) and util.colToX(col). In Problems 1 and 2, you will implement ExactInference, which computes a full distribution over tiles (row, col). In Problem 3, you will implement ParticleFilter, which works with particle-based representation of this distribution. Problem 1: Emission Probabilities In this problem, we assume that the other car is stationary (e.g., Ct = Ct−1 for all time steps t). You will implement a function observe that upon observing a new distance measurement Dt = dt updates the current posterior probability from P(Ct | D1 = d1,…,Dt−1 = dt−1) to P(Ct | D1 = d1,…,Dt = dt) ∝ P(Ct | D1 = d1,…,Dt−1 = dt−1)p(dt | ct), where we have multiplied in the emission probabilities p(dt | ct) described earlier. The current posterior probability is stored as self.belief in ExactInference, which you should update self.belief in place. Problem 1a [7 points] Before jumping into the code, please read util.py to find useful functions. Fill in the observe method in the ExactInference class of submission.py. This method should update the posterior probability of each tile given the observed noisy distance. After you’re done, you should be able to find the stationary car by driving around it (-p means cars don’t move): Notes: • You can start driving with exact inference by executing the following command: python drive.py -a -p -d -k 1 -i exactInference You can also turn off -a to drive manually. • Remember to normalize the updated posterior probability (see useful functions provided in util.py). • On the small map, the autonomous driver will sometimes drive in circles around the middle block before heading for the target area. In general, don’t worry too much about driving the car. Instead, focus on if your car tracker correctly infers the location of other cars. • Don’t worry if your car crashes once in a while! Accidents do happen, whether you are human or AI. However, even if there was an accident, your driver should have been aware that there was a high probability that another car was in the area. Problem 2: Transition Probabilities Now, let’s consider the case where the other car is moving according to transition probabilities p(ct+1 | ct). We have provided the transition probabilities for you in self.transProb. Specifically, self.transProb[(oldTile, newTile)] is the probability of the other car being in newTile at time step t + 1 given that it was in oldTile at time step t. In this part, you will implement a function ExactInference.elapseTime that updates the posterior probability about the location of the car at a current time t P(Ct = ct | D1 = d1,…,Dt = dt) to the next time step t + 1 conditioned on the same evidence, via the recurrence: . Again, the posterior probability is stored as self.belief in ExactInference. Problem 2a [7 points] Finish ExactInference by implementing the elapseTime method. When you are all done, you should be able to track a moving car well enough to drive autonomously by executing: python drive.py -a -d -k 1 -i exactInference Notes: • You can also drive autonomously in the presence of more than one car: python drive.py -a -d -k 3 -i exactInference • You can also drive down Lombard: python drive.py -a -d -k 3 -i exactInference -l lombard Problem 3: Particle Filtering Though exact inference works well for the small maps, it wastes a lot of effort computing probabilities for cars being on unlikely tiles. We can solve this problem using a particle filter which has complexity linear in the number of particles rather than linear in the number of tiles. Implement all necessary methods for the ParticleFilter class in submission.py. When complete, you should be able to track cars nearly as effectively as with exact inference. Problem 3a [18 points] Some of the code has been provided for you. For example, the particles have already been initialized randomly. You need to fill in the observe and elapseTime functions. These should modify self.particles, which is a map of tiles (row, col) to the number of times that particle occurs, and self.belief, which needs to be updated after you resample the particles. You should use the same transition probabilities as in exact inference. The belief distribution generated by a particle filter is expected to look noisier compared to the one obtained by exact inference. You can execute the following command to check the behavior of your code: python drive.py -a -i particleFilter -l lombard Notes: • If you have implemented ParticleFilter correctly, self.belief should never appear in your code. Also, self.updateBelief should never be called, except the 187th line of distributed submission.py, which is a part of ParticleFilter.observe. 0 points will be given if the above conditions are violated even if the grader gives you a full point. • In the implementation of random process, you should useutil.weightedRandomChoice in both observe and elapseTime. The method util.weightedRandomChoice calls random.uniform, which is affected by a random seed and how many time it is called. Therefore, please read the following and write your code carefully. – In observe, util.weightedRandomChoice is used in a part that re-samples the particles, which should be written as a following form: for _ in range(self.NUM_PARTICLES): – In elapseTime, util.weightedRandomChoice is used in a part that finds the distribution of particles on the next time step, which should be written as a following form: for particle in self.particles:
CSED342 – Artificial Intelligence General Instructions ¥This icon means you should write code. You can add other helper functions outside the answer block if you want. Do not make changes to files other than submission.py. Please use Python 3.9 to develop your code. You have to write answers in the same format as provided in submission.py. You should modify the code in submission.py between # BEGIN_YOUR_ANSWER and # END_YOUR_ANSWER Your code will be evaluated on two types of test cases, basic and hidden, which you can see in grader.py. Basic tests, which are fully provided to you, do not stress your code with large inputs or tricky corner cases. Hidden tests are more complex and do stress your code. The inputs of hidden tests are provided in grader.py, but the correct outputs are not. To run all the tests, type python grader.py This will tell you only whether you passed the basic tests. On the hidden tests, the script will alert you if your code takes too long or crashes, but does not say whether you got the correct output. You can also run a single test (e.g., 2a-1-basic) by typing python grader.py 2a-1-basic We strongly encourage you to read and understand the test cases, create your own test cases, and not just blindly run grader.py.In this assignment, you will formulate some problems as constraint satisfaction problems (CSPs) which consist of variables and unary or binary factors between the variables. Once you defined CSPs, you can find the solutions by backtracking search. However, its run-time increases exponentially with the number of variables and factors. Therefore, you will also implement some heuristics which reduce the required time for backtracking. Problem 1. Warm-up Problem 1a [3 points] ¥ Let’s consider a CSP with n variables X1,…,Xn and n − 1 binary factors t1,…,tn−1 where Xi ∈ {0,1} and ti(X) = xi Lxi+1. Note that the CSP has a chain structure. The figure below illustrates an example of the factor graph with 3 variables.Implement create_chain_csp() by creating a generic chain CSP with XOR as factors. Note: We’ve provided you with a CSP implementation in util.py which supports unary and binary factors. For now, you don’t need to understand the implementation, but please read the comments and get yourself familiar with the CSP interface. For this problem, you’ll need to use CSP.add_variable() and CSP.add_binary_factor(). Problem 2: CSP solving So far, we’ve only worked with unweighted CSPs, where fj(x) ∈{0,1}. In this problem, we will work with weighted CSPs, which associates a weight for each assignment x based on the product of m factor functions f1,…,fm: m Weight(x) = Yfj(x) j=1 where each factor fj(x) ≥ 0. Our goal is to find the assignment(s) x with the highest weight. As in problem 0, we will assume that each factor is either a unary factor (depends on exactly one variable) or a binary factor (depends on exactly two variables). For weighted CSP construction, you can refer to the CSP examples we provided in util.py for guidance (create_map_coloring_csp(), create_weighted_csp() and create_or_csp()). You can try these examples out by running python run_p2.py Take a look at BacktrackingSearch.reset_results() to see the other fields which are set as a result of solving the weighted CSP. You should read submission.BacktrackingSearch carefully to make sure that you understand how the backtracking search is working on the CSP. Problem 2a [4 points] ¥ Let’s create a CSP to solve the n-queens problem: Given an n × n board, we’d like to place n queens on this board such that no two queens are on the same row, column, or diagonal. Implement create_nqueens_csp() by adding n variables and some number of binary factors. Note that the solver collects some basic statistics on the performance of the algorithm. You should take advantage of these statistics for debugging and analysis. You should get 92 (optimal) assignments for n = 8 with exactly 2057 operations (number of calls to backtrack()). Hint: If you get a larger number of operations, make sure your CSP is minimal. Try to define the variables such that the size of domain is O(n). Problem 2b [4 points] ¥ You might notice that our search algorithm explores quite a large number of states even for the 8 × 8 board. Let’s see if we can do better. One heuristic we discussed in class is using most constrained variable (MCV): To choose an unassigned variable, pick the Xj that has the fewest number of values a which are consistent with the current partial assignment (a for which get_delta_weight() on Xj = a returns a non-zero value). Implement this heuristic in get_unassigned_variable() under the condition self.mcv = True. It should take you exactly 1361 operations to find all optimal assignments for 8 queens CSP — that’s 30% fewer! Some useful fields: • csp.unaryFactors[var][val] gives the unary factor value. • csp.binaryFactors[var1][var2][val1][val2] gives the binary factor value. Here, var1 and var2 are variables and val1 and val2 are their corresponding values. Hint: you can simply use get_delta_weight() rather than csp.unaryFactors and csp.binaryFactors. Problem 3: Handling n-ary factors So far, our CSP solver only handles unary and binary factors, but for any non-trivial application, we would like to define factors that involve more than two variables. It would be nice if we could have a general way of reducing n-ary constraint to unary and binary constraints. In this problem, we will do exactly that for two types of n-ary constraints. The second type of n-ary factors is constraints on the sum over n variables. You are going to implement reduction of this type. Problem 3a [5 points] ¥ Let’s implement get_sum_variable(), which takes in a sequence of non-negative integervalued variables and returns a variable whose value is constrained to equal the sum of the variables. You will need to access the domains of the variables passed in, which you can assume contain only non-negative integers. The parameter maxSum is the maximum sum possible of all the variables. You can use this information to decide the proper domains for your auxiliary variables. How can this function be useful? Suppose we wanted to enforce the constraint [X1+X2+X3 ≤ K]. We would call get_sum_variable() on (X1,X2,X3) to get some auxiliary variable Y , and then add the constraint [Y ≤ K]. Note: You don’t have to implement the ≤ constraint for this part. Problem 3b [4 points] ¥ Let’s create a CSP. Suppose you have n light bulbs, where each light bulb i = 0,…,n − 1 is initially off. You also have m buttons which control the lights. For each light bulb i = 0,…,n − 1, we know the subset Li ⊆{0,…,m − 1} of buttons that control it. When button j is pressed, it toggles the state of light bulbs whose corresponding L includes j (If buttons B0 and B1 are pressed in the example shown in the figure, light bulbs L0, L2, and L3 will turn on, while L1 will remain off.). In code, Li corresponds to buttonSets[i]. Your goal is to turn on all the light bulbs by pressing a subset of the buttons. Implement create_lightbulb_csp to solve this problem.
CSED342 – Artificial Intelligence General Instructions This (and every) assignment has a written part and a programming part. You should write both types of answers in submission.py between # BEGIN_YOUR_ANSWER and # END_YOUR_ANSWER Your code will be evaluated on two types of test cases, basic and hidden, which you can see in grader.py. Basic tests, which are fully provided to you, do not stress your code with large inputs or tricky corner cases. Hidden tests are more complex and do stress your code. The inputs of hidden tests are provided in grader.py, but the correct outputs are not. To run all the tests, type python grader.py This will tell you only whether you passed the basic tests. On the hidden tests, the script will alert you if your code takes too long or crashes, but does not say whether you got the correct output. You can also run a single test (e.g., 3a-0-basic) by typing python grader.py 3a-0-basic We strongly encourage you to read and understand the test cases, create your test cases, not just blindly run grader.py. IntroductionFigure 1: Pac-Man, now with ghosts. For those of you not familiar with Pac-Man, it’s a game where Pac-Man (the yellow circle with a mouth in the above figure) moves around in a maze and tries to eat as many food pellets (the small white dots) as possible while avoiding the ghosts (the other two agents with eyes in the above figure). If Pac-Man eats all the food in a maze, it wins. The big white dots at the top-left and bottom-right corner are capsules, which give Pac-Man power to eat ghosts in a limited time window (but you won’t be worrying about them for the required part of the assignment). You can get familiar with the setting by playing a few games of classic Pac-Man, which we come to just after this introduction. In this project, you will design agents for the classic version of Pac-Man, including ghosts. Along the way, you will implement various search strategies. Files • submission.py : Where all of your multi-agent search agents will reside and the only file you need to concern yourself with for this assignment. • pacman.py : The main file that runs Pac-Man games. This file also describes a Pac-Man GameState type, which you will use extensively in this project • game.py : The logic behind how the Pac-Man world works. This file describes several supporting types like AgentState, Agent, Direction, and Grid. • util.py : Useful data structures for implementing search algorithms. • graphicsDisplay.py : Graphics for Pac-Man • graphicsUtils.py : Support for Pac-Man graphics • textDisplay.py : ASCII graphics for Pac-Man • ghostAgents.py : Agents to control ghosts • keyboardAgents.py : Keyboard interfaces to control Pac-Man • layout.py : Code for reading layout files and storing their contents Warmup First, play a game of classic Pac-Man to get a feel for the assignment: python pacman.py You can always add –frameTime 1 to the command line to run in ”demo mode” where the game pauses after every frame. Now, run the provided ReflexAgent in submission.py: python pacman.py -p ReflexAgent Note that it plays quite poorly even on simple layouts: python pacman.py -p ReflexAgent -l testClassic You can also try out the reflex agent on the default mediumClassic layout with one ghost or two. python pacman.py -p ReflexAgent -k 1 python pacman.py -p ReflexAgent -k 2 Note: you can never have more ghosts than the layout permits. Options: Default ghosts are random; you can also play for fun with slightly smarter directional ghosts using -g DirectionalGhost. You can also play multiple games in a row with -n. Turn off graphics with -q to run lots of games quickly. So, now that you are familiar enough with the interface, inspect the ReflexAgent code carefully (in submission.py) and make sure you understand what it’s doing. The reflex agent code provides some helpful examples of methods that query the GameState (a GameState specifies the full game state, including the food, capsules, agent configurations, and score changes: see submission.py for further information and helper methods) for information, which you will be using in the actual coding part. We are giving an exhaustive and very detailed description below, for the sake of completeness and to save you from digging deeper into the starter code. The actual coding part is very small – so please be patient if you think there is too much writing. Note: if you wish to run Pac-Man in the terminal using a text-based interface, check out the terminal directory. Problems Problem 1: Minimax Before you code up Pac-Man as a minimax agent, notice that instead of just one adversary, Pac-Man could have multiple ghosts as adversaries. So we will extend the minimax algorithm from class (which had only one min stage for a single adversary) to the more general case of multiple adversaries. In particular, your minimax tree will have multiple min layers (one for each ghost) for every max layer. Specifically, consider the limited depth tree minimax search with evaluation functions taught in class. Suppose there are n + 1 agents on the board, a0,…,an, where a0 is PacMan and the rest are ghosts. Pac-Man acts as a max agent and the ghosts act as min agents. A single depth consists of all n+1 agents making a move, so the depth 2 search will involve Pac-Man and each ghost moving two times. In other words, a depth of 2 corresponds to a height of 2(n + 1) in the minimax game tree. Problem 1a [2 points] Now fill out MinimaxAgent class in submission.py using the recurrence you designed. Remember that your minimax agent should work with any number of ghosts, and your minimax tree should have multiple min layers (one for each ghost) for every max layer. Your code should also expand the game tree to an arbitrary depth. Score the leaves of your minimax tree with the supplied self.evaluationFunction, which defaults to scoreEvaluationFunction. The class MinimaxAgent extends MultiAgentSearchAgent, which gives access to self.depth and self.evaluationFunction. Make sure your minimax code makes reference to these two variables where appropriate as these variables are populated from the command line options. Other functions that you might use in the code: GameState.getLegalActions() which returns all the possible legal moves, where each move is Directions.X for some X in the set NORTH, SOUTH, WEST, EAST, STOP. Go through ReflexAgent code as suggested before to see how the above is used and also for other important methods like GameState.getPacmanState(), GameState.getGhostStates(), GameState.getScore() etc. These are further documented inside the MinimaxAgent class. Hints and Observations • The evaluation function in this part is already written (self.evaluationFunction). You shouldn’t change this function but recognize that now we’re evaluating states rather than actions, as we were for the reflex agent. Look-ahead agents evaluate future states whereas reflex agents evaluate actions from the current state. Use self.evaluationFunction in your definition of Vmax,min wherever you used Eval(s) in part 1a. • The minimax values of the initial state in the minimaxClassic layout are 9, 8, 7, -492 for depths 1, 2, 3, and 4 respectively. You can use these numbers to verify if your implementation is correct. Note that your minimax agent will often win (just under 50% of the time for us–be sure to test on a large number of games using the -n and -q flags) despite the dire prediction of depth 4 minimax. python pacman.py -p MinimaxAgent -l minimaxClassic -a depth=4 • Pac-Man is always agent 0, and the agents move in order of increasing agent index. Use self.index in your minimax implementation, but only Pac-Man will actually be running your MinimaxAgent. • Functions are provided to get legal moves for Pac-Man or the ghosts and to execute a move by any agent. See GameState in pacman.py for details. • All states in minimax should be GameStates, either passed in to getAction or generated via GameState.generateSuccessor. In this project, you will not be abstracting to simplified states. • getAction should use Vmax,min to determine the best action for Pac-Man. • On larger boards such as openClassic and mediumClassic (the default), you’ll find Pac-Man to be good at not dying, but quite bad at winning. He’ll often thrash around without making progress. Don’t worry if you see this behavior. • Consider the following run: python pacman.py -p MinimaxAgent -l trappedClassic -a depth=3 Why do you think Pac-Man rushes the closest ghost in minimax search on trappedClassic? • You can assume that you will always have at least one action from which to choose in getAction. • getQ should return Qmax,min for the current state given action. Problem 2: Expectimax Random ghosts are of course not optimal minimax agents, so modeling them with minimax search is not optimal. Let’s assume that ghosts follow the uniform policy, therefore ghosts take legal actions uniformly in any state. Before implementing it, first extend Expectimax recurrence, so the algorithm considers multiple ghosts as opponents.Your recurrence should resemble that of Problem 1a Problem 2a [2 points] Fill in ExpectimaxAgent, where your agent will no longer take the min over all ghost actions, but the expectation according to your agent’s model of how the ghosts act. Assume Pac-Man is playing against RandomGhosts, which each choose getLegalActions uniformly at random. You should now observe a more cavalier approach to close quarters with ghosts. In particular, if Pac-Man perceives that he could be trapped but might escape to grab a few more pieces of food, he’ll at least try: python pacman.py -p ExpectimaxAgent -l trappedClassic -a depth=3 Problem 3: BiasedExpectimax Now assume that policy ghosts follow is biased to select to stop (i.e. Directions.STOP). Specifically, ghosts decide their next action according to the following distribution: for a = Directions.STOP elsewhere, where A is a set of legal actions of a player from the current state. Problem 3a [6 points] Fill in BiasedExpectimaxAgent. This time, your agent should take the expectation over ghosts’ biased action policy. Assume Pac-Man is playing against RandomGhosts which are likely to choose to stop in place. Your agent now would show some foolish actions. In particular, Pac-Man sometimes rushes to the very-close ghost even though there are no benefits for the game score (i.e. food pellets): python pacman.py -p BiasedExpectimaxAgent -l trappedClassic -a depth=3 Compared to the expectimax, the winning rate would still be half. The final score, however, would change when Pac-Man loses: you will get -503 not -502. In case the game loses, Pac-Man will stop to move between the two approaching ghosts before it dies. Do you know why? Problem 4: Expectiminimax In the real world, it is not the best prediction that treating (if playing with multiple opponents) all adversaries follow the same policy. From now on, you assume that ghosts are divided into two groups of following either min policy or random policy. Specifically, the ghosts with odd-number select the action for the minimum value and the ghosts with evennumber select the action randomly according to a certain distribution. For the simplicity of your implementation, suppose the action chosen by even-numbered ghosts is from uniform distribution. Problem 4a [4 points] Fill in ExpectiminimaxAgent, where your agent will take the min over half of the ghosts and the expectation over others. Assume Pac-Man is playing against RandomGhosts, some choosing the worst action for Pac-Man and others uniformly randomly choosing the action: python pacman.py -p ExpectiminimaxAgent -l minimaxClassic -a depth=4 The expectiminimax values of the initial state in the minimaxClassic layout are almost similar to the minimax values. They would be 9.0, 8.0, 7.0, and 263.75 for depths 1, 2, 3, and 4 respectively. Why the values for the expectiminimax and minimax are same for depths 1, 2, and 3 but differ for depth 4? Problem 5: Alpha-beta pruning Problem 5a [8 points] Make a new agent that uses alpha-beta pruning to more efficiently explore the expectiminimax tree, in AlphaBetaAgent. Again, your algorithm will be slightly more general than the pseudo-code in the slides, so part of the challenge is to extend the alpha-beta pruning logic appropriately to multiple expectiminimizer agents. You should see a speed-up. Ideally, depth 3 on mediumClassic should run in just a few seconds per move or faster. python pacman.py -p AlphaBetaAgent -a depth=3 The AlphaBetaAgent expectiminimax values should be identical to the ExpectiminimaxAgent expectiminimax values, although the actions it selects can vary because of different tiebreaking behavior. Again, the expectiminimax values of the initial state in the minimaxClassic layout are 9.0, 8.0, 7.0, and 263.75 for depths 1, 2, 3, and 4, respectively. Running the command given above this paragraph, the expectiminimax values of the initial state should be 9.0, 18.0, 27.0, and 36.0 for depths 1, 2, 3, and 4, respectively. Problem 6: Evaluation function Problem 6a [8 points] After implementing it, choose the Pac-Man agent model to be used for the test. You can choose among the agents you’ve implemented in Problem 1-5 or design your own agent model. You can test your code with: python pacman.py -l smallClassic -p ExpectimaxAgent -a evalFn=better -q -n 20 python pacman.py -l smallClassic -p MyOwnAgent -a evalFn=better -q -n 20 We will run your Pac-Man agent 20 times, and calculate the average score you obtained. If your average score is less than 1000, you’ll get no points. If your average score is more than 1500, you’ll get 8 points. Check the grader.py to see how the scores are calculated. Hints and Observations • Having gone through the rest of the assignment, you should play Pac-Man again yourself and think about what kinds of features you want to add to the evaluation function. How can you add multiple features to your evaluation function? • For your information, our solution code gets more than 1600 scores on average with various random seeds.
CSED342 – Artificial Intelligence General Instructions This assignment has only a programming part. ¥This icon means you should write code. You can add other helper functions outside the answer block if you want. Do not make changes to files other than submission.py. You should modify the code in submission.py between # BEGIN_YOUR_ANSWER and # END_YOUR_ANSWER Your code will be evaluated on two types of test cases, basic and hidden, which you can see in grader.py. Basic tests, which are fully provided to you, do not stress your code with large inputs or tricky corner cases. Hidden tests are more complex and do stress your code. The inputs of hidden tests are provided in grader.py, but the correct outputs are not. To run all the tests, type python grader.py This will tell you only whether you passed the basic tests. On the hidden tests, the script will alert you if your code takes too long or crashes, but does not say whether you got the correct output. You can also run a single test (e.g., 3a-0-basic) by typing python grader.py 3a-0-basic We strongly encourage you to read and understand the test cases, create your own test cases, and not just blindly run grader.py.The search algorithms explored in the previous assignment work great when you know exactly the results of your actions. Unfortunately, the real world is not so predictable. One of the key aspects of an effective AI is the ability to reason in the face of uncertainty. Markov decision processes (MDPs) can be used to formalize uncertain situations. In this homework, you will implement algorithms to find the optimal policy in these situations. You will then formalize a modified version of Blackjack as an MDP, and apply your algorithm to find the optimal policy. Problem 1. Value Iteration (Volcano Crossing)Figure 1: The example image of Volcano Crossing introduced during the class. In this problem, you will handle an algorithm that performs value iterations for the Volcano Crossing case. There is a grid-world modeled as an M by N grid of states (where M and N are positive integers). The grid world contains at least one volcano grid and one island grid. If the agent moves to any volcano cell, it receives a negative integer reward. If the agent moves to an island cell, it receives a reward of a positive integer. Whenever the agent reaches any island or volcano cell, the travel ends. To simplify the discussion, we assume that the transition probability is 1 (There is no slip, so the agent will go exactly to the cell it intends to). We only consider the discount factor (which is greater than 0 and less than or equal to 1) and the reward per move (moveReward, which is less than or equal to 0). The agent can move in four directions: east, south, west, and north. If the agent tries to move off the grid, it remains in the same cell. Problem 1a [5 points] ¥ VolcanoCrossing initializes with environment information regarding the grid world (provided as a numpy.ndarray), the discount rate, and the moveReward. When executing VolcanoCrossing.value_iteration(n), the algorithm performs n iterations for the given environment and return the value table containing the value Vn(s) for each state s. To ensure that the value iteration operates correctly, implement VolcanoCrossing.value_update to appropriately update the value table. Problem 2. BlackjackYou will be creating a MDP to describe a modified version of Blackjack. (Before reading the description of the task, first check how util.ValueIteration.solve finds the optimal policy of a given MDP such as util.NumberLineMDP.) For our version of Blackjack, the deck can contain an arbitrary collection of cards with different values, each with a given multiplicity. For example, a standard deck would have card values [1,2,…,13] and multiplicity 4. You could also have a deck with card values [1,5,20]. The deck is shuffled (each permutation of the cards is equally likely). The game occurs in a sequence of rounds. Each round, the player either (i) takes the next card from the top of the deck (costing nothing), (ii) peeks at the top card (costing peekCost, in which case the card will be drawn in the next round), or (iii) quits the game. (Note: it is not possible to peek twice in a row; if the player peeks twice in a row, then succAndProbReward() should return [].) The game continues until one of the following conditions becomes true: • The player quits, in which case her reward is the sum of the cards in her hand. • The player takes a card, and this leaves her with a sum that is strictly greater than the threshold, in which case her reward is 0. • The deck runs out of cards, in which case it is as if she quits, and she gets a reward which is the sum of the cards in her hand. In this problem, your state s will be represented as a triple: (totalCardValueInHand, nextCardIndexIfPeeked, deckCardCounts) As an example, assume the deck has card values [1,2,3] with multiplicity 1, and the threshold is 4. Initially, the player has no cards, so her total is 0; this corresponds to state (0, None, (1, 1, 1)). At this point, she can take, peek, or quit. • If she takes, the three possible successor states (each has 1/3 probability) are (1, None, (0, 1, 1)) (2, None, (1, 0, 1)) (3, None, (1, 1, 0)) She will receive reward 0 for reaching any of these states. • If she instead peeks, the three possible successor states are (0, 0, (1, 1, 1)) (0, 1, (1, 1, 1)) (0, 2, (1, 1, 1)) She will receive reward -peekCost to reach these states. From (0, 0, (1, 1, 1)), taking yields (1, None, (0, 1, 1)) deterministically. • If she quits, then the resulting state will be (0, None, None) (note setting the deck to None signifies the end of the game). As another example, let’s say her current state is (3, None, (1, 1, 0)). • If she quits, the successor state will be (3, None, None). • If she takes, the successor states are (3 + 1, None, (0, 1, 0)) or (3 + 2, None, None). Note that in the second successor state, the deck is set to None to signify the game ended with a bust. You should also set the deck to None if the deck runs out of cards. Problem 2a [5 points] ¥ Your task is to implement the game of Blackjack as a MDP by filling out the succAndProbReward() function of class BlackjackMDP. Problem 3: Learning to Play Blackjack So far, we’ve seen how MDP algorithms can take an MDP which describes the full dynamics of the game and return an optimal policy. But suppose you go into a casino, and no one tells you the rewards or the transitions. We will see how reinforcement learning can allow you to play the game and learn the rules at the same time! Problem 3a [5 points] ¥ We are using Q-learning with function approximation, which means Qˆopt(s,a) = w · ϕ(s,a), where in code, w is self.weights, ϕ is the featureExtractor function, and Qˆopt is self.getQ. We have implemented Qlearning.getAction as a simple ϵ-greedy policy. Your job is to implement Qlearning.incorporateFeedback, which should take an (s,a,r,s′) tuple and update self.weights according to the standard Q-learning update. Problem 3b [5 points] ¥ Now, you’ll implement SARSA, which can be considered as a variation of Q-learning. Your task is to fill in incorporateFeedback of SARSA, which is same with Qlearning except the update equation. Problem 3c [5 points] ¥ Now, we’ll incorporate domain knowledge to improve the generalization of RL algorithms for BlackjackMDP. Your task is to implement blackjackFeatureExtractor as described in the code comments in submission.py. This way, the RL algorithm can use what it learned about some states to improve its prediction performance on other states. Using the feature extractor, you should be able to get pretty close to the optimum on some large instances of BlackjackMDP.
CSED342 – Artificial Intelligence General Instructions This assignment has been developed in Python 3.8, so please use Python 3.8 to implement your code. we recommend using Conda environment. You should modify the code in submission.py between # BEGIN_YOUR_ANSWER and # END_YOUR_ANSWER You can add other helper functions outside the answer block if you want, but do not import other libraries and do not make changes to files other than submission.py. Your code will be evaluated on two types of test cases, basic and hidden, which you can see in grader.py. Basic tests, which are fully provided, do not stress your code with large inputs or tricky corner cases. Hidden tests are more complex and do stress your code. The inputs of hidden tests are provided in grader.py, but the correct outputs are not. To run all the tests, type python grader.py This will tell you only whether you passed the basic tests. The script will alert you if your code takes too long or crashes on the hidden tests, but does not say whether you got the correct output. You can also run a single test (e.g., 2a-1-basic) by typing python grader.py 2a-1-basic We strongly encourage you to read and understand the test cases, create your own test cases, and not just blindly run grader.py. Problems Here, we are going to solve two problems, Text reconstruction and Maze search. Both are search problems, which are defined by state, action, cost, and successor. The object is to find the minimum cost path from a starting state to the goal. Problem 1. Text reconstruction In this problem, we consider two tasks: word segmentation and vowel insertion. Word segmentation often comes up in processing many non-English languages, in which words might not be flanked by spaces on either end, such as in written Chinese or in long compound German words. Vowel insertion is relevant in languages such as Arabic or Hebrew, for example, where modern script eschews notations for vowel sounds and the human reader infers them from context. More generally, it is an instance of a reconstruction problem given lossy encoding and some context. We already know how to optimally solve any particular search problem with graph search algorithms such as uniform cost search or A*. Our goal here is modeling — that is, converting real-world tasks into state-space search problems. Setup: n-gram language models and uniform-cost search Our algorithm will base its segmentation and insertion decisions on the cost of processed text according to a language model. A language model is some function of the processed text that captures its fluency by estimating the likelihood of text, N p(w1,w2,…,wN−1,wN) = Xp(wi|w1,…,wi−1). i=1 A very common language model in NLP is an n-gram sequence model, which assumes p(wi|w1,…,wi−1) = p(wi|wi−(n−1),…,wi−1). We’ll use the ngram model’s negative log-likelihood (−log p(wi|wi−(n−1),…,wi−1)) as a cost function c(wi−(n−1),…,wi−1,wi). The cost will always be positive, and lower costs indicate better fluency. As a simple example: in a case where n = 2 and c is our n-gram cost function, c(big, fish) would be low, but c(fish, fish) would be fairly high. Word segmentation In word segmentation, you are given as input a string of alphabetical characters ([a-z]) without whitespace, and your goal is to insert spaces into this string such that the result is the most fluent according to the language model. Problem 1.a [10 points] Implement an algorithm that finds the optimal word segmentation of an input character sequence. Your algorithm will consider costs based simply on a unigram cost function. Before jumping into code, you should think about how to frame this problem as a state-space search problem. How would you represent a state? What are the successors of a state? What are the state transition costs? Uniform cost search (UCS) is implemented for you in util.py, and you should make use of it here. Fill in the member functions of the WordSegmentationProblem class and the segmentWords function. The argument unigramCost is a function that takes in a single string representing a word and outputs its unigram cost. You can assume that all the inputs would be in lowercase. The function segmentWords should return the segmented sentence with spaces as delimiters, i.e. ‘ ’.join(words). For convenience, you can run python submission.py to enter a console in which you can type character sequences that will be segmented by your implementation of segmentWords. To request a segmentation, type seg mystring into the prompt. For example: >> seg thisisnotmybeautifulhouse Query (seg): thisisnotmybeautifulhouse this is not my beautiful house Console commands other than seg – namely ins and both – will be used for the upcoming parts of the assignment. Other commands that might help with debugging can be found by typing help at the prompt. Vowel insertion Now you are given a sequence of English words with their vowels missing (A, E, I, O, and U; never Y). Your task is to place vowels back into these words in a way that maximizes sentence fluency (i.e., that minimizes sentence cost). For this task, you will use a bigram cost function. You are also given a mapping possibleFills that maps any vowel-free word to a set of possible reconstructions (complete words). For example, possibleFills(‘fg’) returns set([‘fugue’, ‘fog’]). Problem 1.b [10 points] Implement an algorithm that finds optimal vowel insertions. Use the UCS subroutines. When you’ve completed your implementation, the function insertVowels should return the reconstructed word sequence as a string with space delimiters, i.e. ‘ ’.join(filledWords). Assume that you have a list of strings as the input, i.e. the sentence has already been split into words for you. Note that an empty string is a valid element of the list. Note: If some vowel-free word w has no reconstructions according to possibleFills, your implementation should consider w itself as the sole possible reconstruction. Putting it together We’ll now see that it’s possible to solve both of these tasks at once. This time, you are given a whitespace- and vowel-free string of alphabetical characters. Your goal is to insert spaces and vowels into this string such that the result is the most fluent possible one. As in the previous task, costs are based on a bigram cost function. Problem 1.c [15 points] Implement an algorithm that finds the optimal space and vowel insertions. Use the UCS subroutines. When you’ve completed your implementation, the function segmentAndInsert should return a segmented and reconstructed word sequence as a string with space delimiters, i.e. ‘ ’.join(filledWords). The argument query is the input string of space- and vowel-free words. The argument bigramCost is a function that takes two strings representing two sequential words and provides their bigram score. The special out-ofvocabulary beginning-of-sentence word -BEGIN- is given by wordsegUtil.SENTENCE_BEGIN. The argument possibleFills is a function; it takes a word as string and returns a set of reconstructions. Note: Unlike in problem 1.b, where a vowel-free word could (under certain circumstances) be considered a valid reconstruction of itself, here you should only include in your output words that are the reconstruction of some vowel-free word according to possibleFills. Additionally, you should not include words containing only vowels such as “a” or “I”; all words should include at least one consonant from the input string. Use the command both in the program console to try your implementation. Similar to ins command, vowels are striped and spaces are also ignored. For example: >> both imagine all the people Query (both): mgnllthppl imagine all the people Problem 2. Maze search In this problem, we consider searching a 2D grid maze. It’s a common task to find an exit path with the minimum cost. Starting from the first state, the agent can take any action from possibleMoves. To see how action corresponds to the actual move, please check util.directions. If a valid action is chosen, the agent moves toward the direction with predefined cost. However, every maze has a wall that the agent can pass but at a high cost. Also, the size of a maze is finite, which limits its state space. Problem 2.a [3 points] Implement an algorithm that finds the minimum cost of a path from the starting point to the goal. Fill in the member functions of the MazeProblem and the UCSMazeSearch function. When you’ve completed your implementation, the function UCSMazeSearch should return a cost of the shortest path. The arguments start and goal are the coordinates of the starting point and the goal in a maze. As we are going to explore a 2D maze, each coordinate is represented as a tuple of two integer numbers. The argument moveCost is a function that takes in a coordinate and a direction, and outputs a cost to move in the direction from the given coordinate. The argument possibleMoves is a function that takes in a single coordinate and outputs a set of possible moves and their costs. Maze search with A* search algorithm Until now, maze search is not that different from text reconstruction. However, with uniform cost search used in text reconstruction, the agent has to search a lot of states that might be meaningless in a high-level perception. Consider the following figure showing a grid maze, where A and G represent the current positions of the agent and the goal.With a given figure, humans can notice that going straight to the goal is the shortest path. However, with uniform cost search, the agent does not know about such a strategy. Instead, it will move around all the nearby cells. To prevent such explorations, we can use A* search with a heuristic cost function, instead of uniform cost search. If heuristic cost is consistent, A* search always finds the shortest path with less exploration compared to uniform cost search. As the term ’heuristic’ implies, depending on a heuristic cost function, A* search differs in time to find the shortest path. With a na¨ıve heuristic, finding the shortest path can be non-optimal. Still, it will find the shortest path if the given heuristic cost function is consistent.up: with UCS, down: with A* search. Green tiles represent visited states.Heuristic used for A* search can be non-optimal. Still, it will find the shortest path if it is consistent. Problem 2.b [12 points] Implement a heuristic cost function that is consistent with the maze search problem. Fill in the function consistentHeuristic. It is used as a heuristic cost function for this problem, which is an input argument of util.UniformCostSearch.solve. When you’ve completed your implementation, the function AStarMazeSearch should return a cost of the shortest path. Note that if your heuristic cost function is well-defined, A* search should be faster than UCS.
CSED342 – Artificial Intelligence General Instructions You should write answers in submission.py between # BEGIN_YOUR_ANSWER and # END_YOUR_ANSWER In Problem 1 you just need to provide your answers. In Problem 2 and Problem 3 you have to implement some functions. You can add other helper functions outside the answer block if you want. Do not make changes to files other than submission.py. Please use Python 3.7 and NumPy to develop your code. You can refer to the official documentation of Numpy to install it. We recommend you use Conda to set up the environment. You have to write answers in the same format as provided in submission.py. Your code will be evaluated on two types of test cases, basic and hidden, which you can see in grader.py. Basic tests, which are fully provided to you, do not stress your code with large inputs or tricky corner cases. Hidden tests are more complex and do stress your code. The inputs of hidden tests are provided in grader.py, but the correct outputs are not. To run all the tests, type python grader.py This will tell you only whether you passed the basic tests. On the hidden tests, the script will alert you if your code takes too long or crashes, but does not say whether you got the correct output. You can also run a single test (e.g., 3a-0-basic) by typing python grader.py 3a-0-basic We strongly encourage you to read and understand the test cases, create your own test cases, and not just blindly run grader.py.Advice for this homework: • Words are simply strings separated by whitespace. Don’t normalize the capitalization of words (treat great and Great as different words). • You might find some useful functions in util.py. Have a look around in there before you start coding. Problems Problem 1. Hinge Loss Here are two reviews of “Frozen,” courtesy of Rotten Tomatoes (no spoilers!):Rotten Tomatoes has classified these reviews as “positive” and “negative,” respectively, as indicated by the in-tact tomato on the left and the splattered tomato on the right. In this assignment, you will create a simple text classification system that can perform this task automatically. Problem 1a [2 points] We’ll warm up with the following set of four mini-reviews, each labeled positive (+1) or negative (−1): • (+1) so interesting • (+1) great plot • (−1) so bored • (−1) not interesting Each review x is mapped onto a feature vector ϕ(x), which maps each word to the number of occurrences of that word in the review. For example, the first review maps to the (sparse) feature vector ϕ(x) = {so : 1,interesting : 1}. Recall the definition of the hinge loss: Losshinge(x,y,w) = max{0,1 − w · ϕ(x)y}, where y is the correct label. Suppose we run stochastic gradient descent, updating the weights according to w ← w − η∇wLosshinge(x,y,w), once for each of the four examples in order. After the classifier is trained on the given four data points, what are the weights of the six words (‘so’, ‘interesting’, ‘great’, ‘plot’,‘bored’, ‘not’) that appear in the above reviews? Use η = 1 as the step size and initialize w = [0,…,0]. Assume that ∇wLosshinge(x,y,w) = 0 when the margin is exactly 1. Problem 2: Sentiment ClassificationIn this problem, we will build a binary linear classifier that reads movie reviews and guesses whether they are “positive” or “negative.” Problem 2a [2 points] Implement the function extractWordFeatures, which takes a review (string) as input and returns a feature vector ϕ(x) (you should represent the vector ϕ(x) as a dict in Python). Problem 2b [8 points] We’re going to train a linear predictor, which can be represented by a logistic regression model. Here is the definition of linear predict: if w · ϕ(x) > 0 if w · ϕ(x) < 0where σ is a logistic(or sigmoid) function. Your task is to implement the function learnPredictor using stochastic gradient descent, minimizing the negative log-likelihood loss (NLL) defined as: LossNLL(x,y,w) = − log(pw(y | x))You should first derive ∇wLossNLL(x,y,w), then exploit the formula to update weights for each example. Initialize the weights w as 0. Also, you can print the training error and test error after each iteration through the data, so it’s easy to see if your code is working. Problem 2c [3 points] The previous features include unigram(single) words only, which cannot consider the context of a word in an utterance. In this task, we’ll incorporate n-gram words into features. In other words, the feature vector will count the number of occurrences of consecutive words of length n. Implement extractNgramFeatures which extracts n-gram word features. Problem 3: Multi-Layer Perceptron & Backpropagation In this problem, we will build a binary non-linear classifier with Multi-Layer Perceptron (MLP) and train the classifier with the NLL loss using stochastic gradient descent. Note that you are not allowed to use Python libraries that support automatic differentiation (e.g., PyTorch, TensorFlow). Use Numpy to implement your codes. Suppose we have a feature extractor ϕ that produces 2-dimensional feature vectors, and a training dataset Dtrain = {(x1,y1),(x2,y2),(x3,y3),(x4,y4)} (a.k.a XOR problem) with 1. ϕ(x1) = [0,0], y1 = 0 2. ϕ(x2) = [0,1], y2 = 1 3. ϕ(x3) = [1,0], y3 = 1 4. ϕ(x4) = [1,1], y4 = 0. Problem 3a [4 points] Implement the forward function in MLPBinaryClassifier to predict the likelihood of y = 1 using 2-dimensional features with sigmoid activation. Do not modify the init function of MLPBinaryClassifier provided. Note that you need to save intermediate activations within the forward function for backpropagation (Problem 3b). Problem 3b [8 points] Implement the loss and backward functions in MLPBinaryClassifier to backpropagate the negative log-likelihood (NLL) loss to network parameters: W1, b1, W2, and b2. Utilize the saved activations from the forward process to compute the gradient for each parameter. Problem 3c [2 points]
CSED342 – Artificial Intelligence General Instructions Assignment 1 has four problems – problem 0, 1, 2, and 3. You only need to submit problem 1, 2, and 3. Problem 0 is not be graded, but must be solved by yourself before participating in this course. This assignment has been developed in Python 3.8, so please use Python 3.8 to implement your code. we recommend using Conda environment. You should modify the code in submission.py between # BEGIN_YOUR_ANSWER and # END_YOUR_ANSWER You can add other helper functions outside the answer block if you want, but do not import other libraries and do not make changes to files other than submission.py. You can solve all the problems without any libraries other than collections and math. Your code will be evaluated on two types of test cases, basic and hidden, which you can see in grader.py. Basic tests, which are fully provided, do not stress your code with large inputs or tricky corner cases. Hidden tests are more complex and do stress your code. The inputs of hidden tests are provided in grader.py, but the correct outputs are not. To run all the tests, type python grader.py This will tell you only whether you passed the basic tests. The script will alert you if your code takes too long or crashes on the hidden tests, but does not say whether you got the correct output. You can also run a single test (e.g., 2a-0-basic) by typing python grader.py 2a-0-basic We strongly encourage you to read and understand the test cases, create your own test cases, and not just blindly run grader.py. Problems Problem 0. Optimization and probability In this class, we will cast AI problems as optimization problems, that is, finding the best solution in a rigorous mathematical sense. At the same time, we must be adept at coping with uncertainty in the world, and for that, we appeal to tools from probability. The three problems below will not be scored, but please solve them because they are basic concepts. Problem 0a [0 points] Suppose you repeatedly roll a fair six-sided dice until you roll a 6 (and then you stop). Every time you roll a 3, you win 2 points, and every time you roll a 1 or a 2, you lose 1 points. You do not win or lose any points if you roll a 4 or a 5. What is the expected number of points you will have when you stop? Problem 0b [0 points] Suppose the probability of a coin turning up heads is 0 < p < 1, and that we flip it 5 times and get {H,T,H,H,T}. We know the probability (likelihood) of obtaining this sequence is L(p) = p(1 − p)pp(1 − p) = p3(1 − p)2. Now let’s go backward and ask the question: what is the value of p that maximizes L(p)? Hint: Consider taking the derivative of logL(p). Taking the derivative of L(p) works too, but it is cleaner and more natural to differentiate logL(p). You can verify for yourself that the value of p which minimizes logL(p) must also minimize L(p). Problem 0c [0 points] Let’s practice taking gradients, which is a key operation for being able to optimize continuous functions. For w ∈Rd and constants ai,bj ∈Rd and λ ∈R, define the scalar-valued function , where w, ai and bj are column vectors (e.g. w = (w1,…,wd)⊤) and is known as the L2 norm. Compute the gradient ∇wf(w). Recall: the gradient is a d-dimensional vector of the partial derivatives with respect to each wi: . If you’re not comfortable with vector calculus, first warm up by working out this problem using scalars in place of vectors and derivatives in place of gradients. Not everything for scalars goes through for vectors, but the two should at least be consistent with each other (when d = 1). Do not write out summation over dimensions, because that gets tedious. Problem 1. Implementing string functions In this problem, you will implement short functions that handle Python strings. The main purpose of this exercise is to familiarize yourself with Python and strings. If you’re new to Python, the following articles provide pointers to various tutorials and examples for the language: • Python for Programmers: https://wiki.python.org/moin/BeginnersGuide/Programmers • Example programs of increasing complexity: https://wiki.python.org/moin/SimplePrograms Hint: You can use the .split() method to split a string into a list. Problem 1a [4 points] Implement find alphabetically first word in submission.py. Problem 1b [4 points] Implement find frequent words in submission.py. Problem 1c [4 points] Implement find non singleton words in submission.py. Problem 2. Implementing vector operations In this problem, you will implement a bunch of short functions related to vector representations. The main purpose of this exercise is to understand vector representations and operations in programming. Problem 2a [4 points] Implement dense vector dot product in submission.py. Problem 2b [4 points] Implement increment dense vector in submission.py. Problem 2c [4 points] Implement dense to sparse vector in submission.py. Problem 2d [4 points] Implement sparse vector dot product in submission.py. Problem 2e [4 points] Implement increment sparse vector in submission.py. Problem 2f [4 points] Implement euclidean distance in submission.py. Problem 3. Advanced Programming Problem 3a [4 points] Implement mutate sentence in submission.py. Hint: You can consider Depth First Search (DFS) to solve this problem.
OkkyunWoo Data cache in Pipelined CPU Uses a blocking data cache instead of a “magic memory”Data flow When there is a cache miss, the cache requests data from memory When a dirty cache line is evicted, it should be written back to memory*acknowledgement from the memory is implicit in our lab Signals to / from the cache addr[31:0], din[31:0], is_input_valid, mem_rw cache is_ready, dout[31:0] is_hit, is_output_valid Input signals to the data cache addr: memory address that CPU wants to read or write mem_rw: access type (0: read, 1: write) din: data that CPU writes to cache for stores • addr and din should be used only when is_input_valid is true • din should be used only when mem_rw is 1 addr[31:0], din[31:0], is_input_valid, mem_rw cache is_ready, dout[31:0], is_hit, is_output_valid Output signals from the data cache is_ready indicates the status of the cache • True if cache is ready to accept a request • False if cache is busy serving a prior request Cache cannot accept a request currently. LD/ST would be stalled In the 5-stage pipeline, is_ready will always be true when LD/ST goes into MEM stage cache addr[31:0], din[31:0], is_input_valid, mem_rw is_ready, dout[31:0], is_hit, is_output_valid Output signals from the data cache n is_output_valid indicates whether dout and is_hit are valid dout: data accessed from cache (for read) is_hit indicates whether a cache hit occurred cache n When the output from cache are valid, LD/ST instructions can use them and continue execution addr[31:0], din[31:0], is_input_valid, mem_rw is_ready, dout[31:0], is_hit, is_output_validn The size of a cache line (block) is 16 bytes 32 bitsaddr … … … … .. 4 3 2 1 0 tags sets block offset 4B offset # sets # ways Block offset 0 Block offset 1 Block offset 2 Block offset 4 Set 0 Way 0 4B 4B 4B 4B Way 1 … n Asynchronous read: • valid, data, is_hit Synchronous write • Writes to the cache line (from both CPU and memory) should be synchronous Write-back, write-allocate • Read data from the memory if a write miss occurs n Replacement policy • Choose any way except for MRU way Structure • Choose between direct-mapped or set-associative (extra point) but not fully-associative • Size: 256 Bytes (data bank) • You are free to define # of ways and sets Each cache line should have: • Valid bit • Dirty bit • Bits for replacement • …Matrix data layout n Memory layout of the matrix (row-major order) • Assume each element of the matrix is 4 B • Assume cache line size is 16 B address data 0x00 0x04 0x08 0x0c 0x10 0x14 0x18 0x1c cache matrix memory n Naïve implementation • Is this cache-friendly? No. Why?n Tiled implementation • Is this cache-friendly? If yes, why?n Tiled implementation • Is this cache-friendly? If yes, why? • Reuse data (in the cache) as much as possible within each tile The tile size is set to the cache line sizeSubmission • Blocking data cache • Direct-mapped (no extra credit) • N-way associative cache (Full extra credit + 3) • Youneedtofollowtherulesdescribedinlab_guide.pdf • The design of the cache • Direct-mapped or associative cache • Analyze cache hit ratio • If you implement associative cache, compare it with direct-mapped cache • Explain your replacement policy • Naïve matmul vs optimized matmul • Why is the cache hit ratio different between two matmul algorithms? • What happens to the cache hit ratio if you change the # of sets and # of ways? Submission • Implementation fileformat • .zipfilename:Lab5_{team_num}_{student1_id}_{student2_id}.zip • Contentsofthezipfile(only*.v): • cpu.v • … • Do notincludetop.v,InstMemory.v,DataMemory,RegisterFile.v, and CLOG2.v • Report fileformat • Lab5_{team_num}_{student1_id}_{student2_id}.pdf
Yunseon Shin Objectives ◼ Understand and implement a pipelined CPU ◼ Implement a pipelined CPU with control flows 2 Labschedule • You will be implementing a pipelinedCPU with control flow instruction support • Cache will be implemented inLab5 Lab4-1 Lab4-2 Lab5Datapath (w/control flow instructions) • Resolve at EXE stage (BEQ, BNE, BLT, BGE, JAL, JALR) • Miss prediction causes two bubblesSubmission • 5-stagepipelinedCPU w/ control flow instructions • Implement your design over lab4-1 implementation • Control hazard • Branch prediction (need to flush on misprediction) • Always not taken (no extra credit) – Does not require BTB • Always taken (partial extra credit +3) – Require BTB (32 entries) • 2-bit global prediction (partial extra credit +5) – Require BTB (32 entries) • Gshare (full extra credit +7) – Require BTB (32 entries) • The BTB must be initialized as empty • Youneedtofollowtherulesdescribedinlab_guide.pdf • Howto handle branch prediction? • Describe your design of branch predictor • If you implement 2-bit global prediction • Compare total cycles of 2-bit global prediction with that of always-taken and always-not-taken • If you implement always-taken • Compare total cycles of always-taken with that of always-not-taken Submission • Implementation fileformat • .zipfilename:Lab4-2_{team_num}_{student1_id}_{student2_id}.zip • Contentsofthezipfile(only*.v): • cpu.v • … • Do notincludetop.v,InstMemory.v,DataMemory,andRegisterFile.v • Report fileformat • Lab4-2_{team_num}_{student1_id}_{student2_id}.pdf Questions? FAQ • Assuming that such a situation rarely occurs in the lab, you can implement what you learned in class. • It doesn’t matter much about the problems that cause conflict. Even if a conflict occurs, you can update it with a new target. 8 FAQ ◼You don’t need to match the exact cycle of the answer.txt o It could be different following your branch prediction method o Given cycle is result of 5 stage pipeline cpu in “Ripse” 9
Yunseon Shin Contents ◼ Objectives ◼ Pipelined CPU without control flow instructions ◼ Data Hazard ◼ Assignment 2 Objectives ◼ Understand and implement a pipelined CPU ◼ First implement a pipelined CPU without control flows 3 Labschedule ◼You will be implementing a pipelined CPU without control flow instruction support ̶ Control flow instructions will be implemented in Lab 4-2 Lab4-1 Lab4-2Pipelined CPU ◼Increase throughput through better HW utilization5 Datapath(w/ocontrolflowinstrs.) ◼You don’t have to implement control flow instructions now ̶ E.g., JAL, BEQ, …Update pipelineregisters ◼You need to understand how pipeline registers work ̶ Pipeline registers are updated at rising edge of the clockHazard ◼Your implementation should properly resolve: ̶ Data hazard ̶ Structural hazard • We do not append hardware modules to resolve structural hazard ̶ Control hazard • We do not implement branch instructions now Datahazard ◼You need to detect when the data hazard occursDatahazard ◼To stall the pipeline, you need to prevent any architectural state update by NOP(s)Data forwarding ◼ To reduce stalls, you can also implement data forwarding (extra credit)◼ How to halt CPU?◼ You need to pipeline the halt signal◼ Hazard and forwarding ̶ Also, data hazard should be handled properly by stalls or data forwarding̶ 5-stage pipelined CPU •Data hazard − Stall (no extra credit) − Data forwarding (extra credit +10) •You don’t have to handle control hazard − Control flow instructions will not be used in this implementation ̶ You need to follow the rules described in lab_guide.pdf ̶ Do not modify these files: top.v, RegisterFile.v, DataMemory.v, and InstMemory.v ̶ Compare total cycles between the single cycle and pipeliend CPU •Non-control flow input file ̶ How to implement hazard detection? •When detected? ̶ How to implement data forwarding? •When forwarded? ◼ File format ̶ .zip file name: Lab4_{team_num}_{student1_id}_{student2_id}.zip ̶ Contents of the zip file (only *.v): • cpu.v •… • Do not include top.v, DataMemory.v, InstMemory.v, and RegisterFile.vETC. ◼ In this lab, even if the same register is read from and written to at the same cycle, the internal forwarding mentioned in the textbook is not needed, because the write is done first at the at the negative edge. 18 Questions?
Contents ◼ Objectives ◼ Multi-cycle CPU ◼ Assignment Objectives ◼ Understand why a multi-cycle CPU is better than single-cycle implementation ◼ Design and implement a multi-cycle CPU, which has its own datapath and control unit Why Multi-Cycle CPU? ◼ Problem on single-cycle CPU: underutilization of resources (ALU, memory, register file, etc.) ◼ Solution: use higher clock frequency and allocate a different number of cycles for each instruction typeMulti-Cycle CPU (Finite State Machine)Multi-Cycle CPU (Microcode Controller)Single-Cycle CPU (Datapath w/o Resource reuse)Multi-Cycle CPU (Datapath w/ Resource Reuse)Multi-Cycle CPU ̶ Appendix C can also be helpful ̶ Link: https://www.elsevier.com/books-and-journals/book-companion/9780128203316 Assignment ◼ Use Verilator ◼ Implement a multi-cycle RISC-V CPU (RV32I) ̶ Multi-cycle CPU • Datapath − ALU − Register file • Control unit − Microcode controller − Generate the control signals used in the datapath ̶ You can use FSM with either 1 cycle or more cycles for each stage Assignment • Skeleton code updated • Top.v, cpu.v, RegisterFile.v, and memory.v are updated • You can take other modules (e.g., ALU) from your single-cycle CPU to implement the multicycle CPU • Other modules (add more or change if you need) • Testbench • Simulation code • tb_top.cpp • Instruction codes for Verilog RTL (.txt) • basic_ripes.txt, non-controlflow_mem.txt, loop_mem.txt, ifelse_mem.txt, recursive_mem.txt • Assembly codes for Ripes (.asm) (will explain later) • basic_ripes.asm, non-controlflow_mem.asm, loop_mem.asm, ifelse_mem.asm, recursive _mem.asm • Makefile Assignment (cont’d) ◼Implement the same instructions required in the single-cycle CPUModularization ◼ Modularize the main CPU structure (strongly recommended) ̶ Datapath • ALU • Register file ̶ Control unit • Microcode controller ̶ Etc. • MUX, … Evaluation Criteria ◼Source code ̶ The score will be calculated based on the final register values (x1-x31) of the Verilog RTL after test cases for evaluation are executed (same as single-cycle CPU) • You can check the correct register values with single-cycle Ripes simulation (Ripes doesn’t support multi-cycle simulation) ̶ Implementation guidelines • Your control unit should be a well-implemented state machine − Each state should generate its control signals • All storage units (registers, PC, etc.) must be updated only at the clock’s positive edges • Your code should have resource reuse, which affects your control unit design − E.g.) Combining “PC + 1” logic with the ALU • If you don’t follow guidelines, you will get penalty Evaluation Criteria (cont’d) ◼Report ̶ The report should include (1) introduction, (2) design, (3) implementation, (4) discussion, and (5) conclusion sections ̶ Attach screenshots of your microcode controller, control unit code in the report ̶ Key points: • Difference between single-cycle CPU and multi-cycle CPU • Why multi-cycle CPU is better? • Multi-cycle CPU design and implementation • Description of whether each module (RF, memory, PC, control unit, ..) is clock synchronous or asynchronous • Microcode controller state design • Resource reuse design and implementation • Number of cycles took it took to run basic_ripes, and loop_ripes examples Submission ◼ Submit your report and source code on PLMS with filename: ̶ Lab3_{TeamID}_{StudentID1}_{StudentID2}.pdf Zip file contents • PDF file of your report (note there is no folder): ̶ Lab3_{TeamID}_{StudentID1}_{StudentID2}.zip • Zip file of your source code (without testbench) • Do not create a folder within the zip file ◼ There can be penalties for submissions that do not adhere to the guidelines ◼Submission ̶ Evaluation will be done with all instructions (both control-flow and non-control-flow instructions)Questions?
Contents • Assignments • Single-Cycle CPU (RV32I) • Ripes simulator • How to run C program on Ripes & Verilog RTL (Non-mandatory)• Use Verilator • Implement a single-cycle RISC-V CPU (RV32I) • Single-cycle CPU • Datapath • ALU • Register file • Control unit • Generate the control signals used in the datapath • Your implementation of the CPU should process one instruction in a cycle • Skeleton code • top.v – Top module (Do not touch) • opcodes.v – Opcodes of instructions you must implement • Other modules (add more if you need) • cpu.v, instruction_memory.v, data_memory.v, register_file.v • Testbench • Simulation code • tb_top.cpp • Instruction codes for Verilog RTL (.txt) • basic_ripes.txt, non-controlflow_mem.txt, loop_mem.txt • Assembly codes for Ripes (.asm) (will explain later) • basic_ripes.asm, non-controlflow_mem.asm, loop_mem.asm • Makefile • RV32I instructions you should implement• We are going to use the ECALL (environment call) instruction to halt the machine at the end of a program • Simulation ending condition • If instruction == ECALL • If GPR[x17] == 10 • Set is_halted = 1 (Testbench will stop simulation when is_halted is 1) • Else • Consider ECALL as NOP • Example of instructions exiting the program• For other instructions, refer to the RV32I manual • References: • See RISC-V specification (Vol. 1) provided for the lab • https://github.com/riscv/riscv-isa-manual/releases/tag/Ratified-IMAFDQC • https://msyksphinz-self.github.io/riscv-isadoc/html/rvi.htmlModularization • Modularize the main CPU structure (strongly recommended) • Datapath • ALU • Register file • Control Unit • Etc. • MUX, adder, .. • Keep one module in one Verilog file (Verilator issue) • Match file name with module name (Verilator issue) Magic Memory • In instruction_memory.v, data_memory.v • It is NOT a realistic model of the main memory • In our lab, memory works like a register file, except that the memory is byte-addressable and accessed with memory address instead of register ID • Real memory devices are much slower than CPUs • However, we assume there is a magic memory with very low latency for simplicity Initialize instruction memory The number of instructions < MEM_DEPTHEvaluation Criteria (Source code) • Single-Cycle CPU • The score will be calculated based on the final register values (x1-x31) of the Verilog RTL after testbenches for evaluation are executed (i.e., how many registers have the correct values) • Testbench will print final register values • You can check correct register values by running .asm file with Ripes • You are encouraged to run your own program on your Verilog RTL model Evaluation Criteria (Report) • You can write report in Korean or English • Report should include (1) introduction, (2) design, (3) implementation, (4) discussion, and (5) conclusion • Key points: • Single-cycle CPU design and implementation • Description of whether each module(RF, memory, PC, control unit, ..) is clock synchronous or asynchronous • Description of each stage in single-cycle CPU Assignment Submission • Submit your assignment to PLMS with filename: • Lab2_{TeamID}_{StudentID1}_{StudentID2}.pdf • PDF file of your report • Lab2_{TeamID}_{StudentID1}_{StudentID2}.zip • Zip file of your source code (without testbench) • One directory including all codes when unzipped• Ripes is a visual computer architecture simulator and assembly code editor built for the RISC-V instruction set architecture • Ripes can help you debug code• How to install? • https://github.com/mortbopet/Ripes/releases • Install the lastest version• Follow the instruction in the link above • Web version is also available • https://ripes.me/ • But you can’t load a program with web version. • Still, you can copy and paste your code to editorProcessor configurationLoading a programLoading a program • For web version, • You can’t load a program with web version. • Still, you can copy and paste your code to editorRunning the programAs you can see, assembly code uses pseudo-instructions and register aliases. See “RISC-V Assembly Programmer’s Handbook” Chapter of RISC-V manual. x10 issuex10 issueIn Ripes Simulator, x10 holds the system call instruction’s index when it is called. You don’t need to implement this on your CPU.• How to install? • Use Docker (MacOS/Windows/Linux Support) • For Windows users, • Use CSE Education Slurm Cluster to use Docker • You can request the account of CSE Education Slurm Cluster at the below link • https://postechackr.sharepoint.com/sites/cse/SitePages/CSE-Cluster- Howto.aspx?csf=1&e=qwAkG9&cid=dfb4c189-2455-4381-a8c1-2489054f57bb • Or, use WSL to run docker on your computer • Get docker image • $ docker pull acplpostech/acpl_ubuntu_18.04_riscv:latest • Start docker • $ docker run -v ~:/mnt -it –rm acplpostech/acpl_ubuntu_18.04_riscv:latest /bin/bash • Risc-V Assembly Code Generate (Use /RISCV_Crosscompile/script.sh) • $ cd /RISCV_Crosscompile • $ ./script.sh file_name C Code (example.c) Assembly Code• Risc-V Assembly Code Generate (Use /RISCV_Crosscompile/script.sh) • Output file • /RISCV_Crosscompile/{file_name}_ripes.asm -> for Ripes input • $ mv /RISCV_Crosscompile/{file_name}_ripes.asm /mnt • $ exit #exit docker • Now you can find {file_name}_ripes.asm in home directoryCaution • Since we model RV32I without the “M” extension for multiply/divide, you can’t use multiplication on the c code • You can still multiply or divide by a power of 2 using shift left or right operations • You will need to implement some additional instructions that are commonly emitted by the compiler Assignments (Optional) • Implement LUI and AUIPC if you want1. Make new program with cross-compiler output file ({file_name}_ripes.asm)2. Move the function to the top (because default PC is 0x0 in Ripes)3. Replace ‘jalr zero, 0(ra)’ at the end of with ‘li a7, 10’ & ‘ecall’ (exit inst.)4. For every function call, replace ‘auipc ra, 0x0’ & ‘jalr ra, 0(ra)’ with ‘jal ra, ’ (target function)5. For every function return, replace ‘jalr zero, 0(ra)’ with ‘jr ra’ (return)6. Now you can simulate the source code in Ripes.7. Use parser.sh in Docker to extract HEX instruction code from Ripes disassembled instruction code…
1. Undirected Graph – Graph Traversal (2 pts) e.g.) A D B C E C E (correct) A D B (incorrect) You can modify graph.cpp and graph.h files for this problem. b. Input & Output Input: Pairs of nodes with integer labels that indicate edges. – (A,B): an edge between node A and node B. – (‘End’,’DFS’) or (‘End’,’BFS’):String representing traverse mode. Output: – Result of DFS or BFS traverse separated with a white space – Multiple traverses separated with a new line, in the ascending order. c. Example Input & Output Input Output “[(‘A’,’C’), (‘A’,’B’), (‘A’,’D’), (‘B’,’C’), (‘B’,’D’), (‘B’,’E’), (‘B’,’F’), (‘C’,’F’), (‘C’,’E’), (‘End’,’DFS’)]” A B C E F D “[(‘A’,’C’), (‘A’,’B’), (‘A’,’D’), (‘B’,’C’), (‘B’,’D’), (‘B’,’E’), (‘B’,’F’), (‘C’,’F’), (‘C’,’E’), (‘End’,BFS)] A B C D E F “[(‘A’,’C’), (‘A’,’B’), (‘A’,’D’), (‘B’,’C’), (‘B’,’D’), (‘B’,’E’), (‘B’,’F’), (‘C’,’F’), (‘C’,’E’), (‘G’,’H’), (‘End’,’DFS’)]” A B C E F D G H “[(‘A’,’B’), (‘A’,’C’), (‘A’,’D’), (‘B’,’F’), (‘C’,’F’), (‘H’,’G’), (‘E’,’J’), (‘J’,’I’), (‘End’,’DFS’)]” A B F C D E J I G H d. Example execution >> ./pa4.exe 1 “[(‘A’,’C’), (‘A’,’B’), (‘A’,’D’), (‘B’,’C’), (‘B’,’D’), (‘B’,’E’), (‘B’,’F’), (‘C’,’F’), (‘C’,’E’), (‘End’,’DFS’)]” [Task 1] A B C E F D 2. Undirected Graph – Cycle Count (1 pts) a. Implement a function that returns the number of cycles in the given undirected graph. A cycle is a non-empty path in which the only repeated vertices are the first and last vertices. Note that any subset of vertices of a cycle does not form another cycle (that is, there is no inner-cycle). You can modify graph.cpp and graph.h files for this problem. b. Input & output Input: Pairs of node labels that indicate edges. – (‘A’,’B’): an edge between node A and node B. – If the input edge already exists in the graph, ignore the input. Output: – The number of cycles in the given undirected graph c. Example Input & Output Input Output “[(‘A’,’B’), (‘B’,’C’), (‘A’,’C’)]” 1 “[(‘A’,’B’), (‘A’,’C’), (‘C’,’D’), (‘C’,’E’), (‘B’,’D’), (‘D’,’E’)]” 2 “[(‘A’,’B’), (‘A’,’C’), (‘C’,’D’), (‘C’,’E’), (‘D’,’B’), (‘D’,’E’), (‘C’,’F’), (‘A’,’F’)]” 3 d. Example execution3. Directed Graph – Topological Sort (2 pts) a. Implement a function that performs a topological sort using the given directed graph. If there exists more than one result, print the topological sort that comes first in the ascending order. To take an example below, acceptable topological sorts are ‘A B C D F E’, ‘A C B F E D’, ‘A C D B F E’, etc. Among these, the desirable output is ‘A B C D F E’. Also, print ‘error’ if the topological sort could not be performed. You can modify graph.cpp and graph.h files for this problem.b. Input & output Input: Pairs of node labels that indicate edges. – (‘A’,’B’): an edge from node A to node B. – If the input edge already exists in the graph, ignore the input. Output: – Result of topological sort or ‘error’ message c. Example Input & Output Input Output “[(‘A’,’B’),(‘A’,’C’),(‘B’,’F’),(‘F’,’ E’),(‘C’,’E’),(‘C’,’D’)]” A B C D F E “[(‘A’,’B’), (‘A’,’D’), (‘B’,’C’), (‘C’,’E’), (‘D’,’E’), (‘E’,’F’)]” A B C D E F “[(‘B’,’C’), (‘C’,’D’), (‘D’,’B’)]” error d. Example execution >> ./pa4.exe 2 “[(‘A’,’B’),(‘A’,’C’),(‘B’,’F’),(‘F’,’ E’),(‘C’,’E’),(‘C’,’D’)]” [Task 2] A B C D F E 4. Directed Graph – Cycle Count (2 pts) a. Implement a function that returns the number of cycles in the given directed graph. A cycle is a non-empty path in which the only repeated vertices are the first and last vertices. Unlike an undirected graph, the edges of the graph have direction in this time. For instance, (‘A’,’B’) is different from (‘B’,’A’). You can modify graph.cpp and graph.h files for this problem. b. Input & output Input: Pairs of node labels that indicate edges. – (‘A’,’B’): an edge from node A to node B – If the input edge already exists in the graph, ignore the input. Output: – The number of cycles in the given directed graph c. Example Input & Output Input Output “[(‘A’,’B’), (‘B’,’C’), (‘C’,’A’)]” 1 “[(‘A’,’B’), (‘B’,’C’), (‘A’,’C’)]” 0 “[(‘A’,’B’), (‘A’,’C’), (‘C’,’D’), (‘C’,’E’), (‘D’,’B’), (‘D’,’E’)]” 0 “[(‘A’,’B’), (‘A’,’C’), (‘C’,’D’), (‘E’,’C’), (‘D’,’B’), (‘D’,’E’)]” 1 “[(‘A’,’B’), (‘A’,’C’), (‘C’,’D’), (‘E’,’C’), (‘D’,’B’), (‘D’,’E’), (‘C’,’F’), (‘F’,’A’)]” 2 d. Example execution5. Single Source Shortest Path – Dijkstra’s Algorithm (2 pts)a. Implement a function that finds the shortest path from the source node to the destination node in the given graph using Dijkstra algorithm. We assume that the given graph is a directed, weighted, and weakly-connected graph. All weights of edges are positive (i.e. larger than 0). This function should return the sequence of node labels along the path and also the length (sum of the weights of the edges) of the path. If there exists multiple shortest path, print out all of them with ascending lexicographic order. (e.g. if both of A->B->E and A->C->E are shortest paths with cost 5, prints out ‘A B E 5’ then ‘A C E 5’). If the path from the source node to the destination node doesn’t exist, return ‘error’. You can modify the graph.cpp and graph.h files for this problem. b. Input & output Input: A sequence of commands – (‘A-B’, integer): an edge from node A to node B with a weight value {integer}. – (‘A’, ‘B’): a pair of node labels that indicates the source and the destination node. The first element indicates the source node and the second one indicates the destination node. Output: – A sequence of the node labels of the shortest path(s) followed by length of the path. If there exists multiple paths, you should print out all of them sorted by ascending lexicographic order, separated with newline( ). – error if the shortest path could not be determined c. Example Input & Output Input Output “[(‘A-B’,10),(‘A-C’,3),(‘B-D’,5),(‘C-B’,2), (‘C-E’,15),(‘A-D’,20),(‘D-E’,11),(‘A’,’E’)]” A C E 18 “[(‘A-B’,10),(‘A-C’,3),(‘B-D’,5),(‘C-B’,2), (‘C-E’,15),(‘A-D’,20),(‘D-E’,11),(‘A’,’D’)]” A C B D 10 “[(‘A-B’,10),(‘A-C’,3),(‘B-D’,5),(‘C-B’,2), (‘C-E’,15),(‘A-D’,20),(‘D-E’,11),(‘D’,’A’)]” error d. Example execution >> ./pa4.exe 3 “[(‘A-B’,10), (‘A-C’,3), (‘B-D’,5), (‘C-B’,2), (‘C-E’,15), (‘A-D’,20), (‘D-E’,11), (‘A’,’E’)]” [Task 3] A C E 18 6. All Pairs Shortest Path of Graph – Floyd’s Algorithm (2 pts)a. a. Implement a function that finds the shortest paths of all pairs of nodes. Unlike problem 3, there will be an edge(s) with negative weight value(s). There will be no negative cycle in the given graph. This function should return the distances of all paths in the given graph like the above image. You can modify the graph.cpp and graph.h files for this problem. b. Input & Output Input: A sequence of commands – (‘A-B’, integer): an edge from node A to node B with weight value {integer}. Output: – A distance matrix in a string format. The nodes in the row and column of the matrix are sorted in lexicographic order. If the source and the destination node are the same, the distance should be 0. If the path doesn’t exist, the distance is INF.Input Output “[(‘A-B’,4),(‘B-C’,9),(‘B-D’,1), (‘C-D’,10),(‘D-C’,8),(‘D-A’,-2)]” 0 4 13 5 -1 0 9 1 8 12 0 10 -2 2 8 0 “[(‘A-B’,4),(‘A-F’,3),(‘B-F’,6), (‘B-C’,9),(‘F-E’,-2),(‘E-F’,5), (‘C-E’,-3),(‘E-C’,8),(‘E-D’,6)]” 0 4 9 7 1 3 INF 0 9 10 4 6 INF INF 0 3 -3 2 INF INF INF 0 INF INF INF INF 8 6 0 5 INF INF 6 4 -2 0 “[(‘A-B’,4),(‘B-C’,9),(‘C-E’,-2), (‘E-C’,8),(‘B-H’,1),(‘A-H’,4), (‘H-C’,3),(‘B-F’,6),(‘A-G’,7), (‘G-B’,-4),(‘B-G’,8),(‘G-F’,7), (‘F-E’,6),(‘E-F’,5),(‘E-D’,6)]” 0 3 7 11 5 9 7 4 INF 0 4 8 2 6 8 1 INF INF 0 4 -2 3 INF INF INF INF INF 0 INF INF INF INF INF INF 8 6 0 5 INF INF INF INF 14 12 6 0 INF INF INF -4 0 4 -2 2 0 -3 INF INF 3 7 1 6 INF 0 d. Example execution7. Prim’s Algorithm (2 pts) a. Implement a function that finds the Minimum-cost Spanning Tree (MST) of the given weighted undirected graph using Prim’s algorithm. Given a start node, this function starts with the single-vertex tree of the given node. Then, the function prints the added edge and the weight of the edge each time the tree grows. When printing an edge, you first must print the label of the node that already exists in the tree, then print the label of the node that was recently inserted into the tree. If there are multiple edges with the same weight, this function checks the label of the added node (i.e., the node which is not included in the tree) and selects the node with the first label in lexicographical order. Finally, the function returns the cost of the MST (i.e., the sum of edge weights). You can assume that the given graph is a connected graph. You can modify graph.cpp and graph.h files for this problem. b. Input & Output Input: A sequence of commands – (‘A-B’, integer): an edge between node A and node B with weight value {integer}. – (‘MST’, ‘A’): find MST using the Prim’s algorithm which starts with node A. Output: – For each time the tree grows, print the labels of the nodes indicating the added edges and the weight of the edge as a string separated with a white space. – Print the cost of MST. Input Output “[(‘A-B’, 3), (‘A-C’, 1), (‘B-C’, 4), (‘B-D’, 1), (‘C-D’, 2), (‘D-E’, 5), (‘MST’, ‘A’)]” A C 1 C D 2 D B 1 D E 5 9 “[(‘A-B’, 3), (‘A-C’, 1), (‘B-C’, 4), (‘B-D’, 1), (‘C-D’, 2), (‘D-E’, 5), (‘MST’, ‘E’)]” E D 5 D B 1 D C 2 C A 1 9 “[(‘A-B’, 3), (‘A-C’, 1), (‘B-C’, 1), (‘B-D’, 4), (‘C-D’, 2), (‘D-E’, 5), (‘MST’, ‘E’)]” E D 5 D C 2 C A 1 C B 1 9 d. Example execution8. Kruskal’s Algorithm (2 pts) a. Implement a function that finds the Minimum-cost Spanning Tree (MST) of the given weighted undirected graph using Kruskal’s algorithm. The function prints the added edge and the weight of the edge each time the tree grows. When printing an edge, you must print the label in lexicographical order. If there are multiple edges with the same weight, this function also selects the edge in lexicographical order. That means it compares the first node of edges, and if the first node is the same, it compares the second node of edges. The function returns the cost of the MST (i.e., the sum of edge weights). You can assume that the given graph is a connected graph. You can modify graph.cpp and graph.h files for this problem. b. Input & Output Input: A sequence of commands – (‘A-B’, integer): an edge between node A and node B with weight value {integer}. – (‘MST’, NULL): find MST using Kruskal’s algorithm. Output: – For each time the tree grows, print the labels of the nodes indicating the added edges in lexicographical order and the weight of the edge as a string separated with a white space. – Print the cost of MST. Input Output “[(‘A-B’, 3), (‘A-C’, 1), (‘B-C’, 4), (‘B-D’, 1), (‘C-D’, 2), (‘D-E’, 5), (‘MST’, NULL)]” A C 1 B D 1 C D 2 D E 59 “[(‘D-B’, 1), (‘D-C’, 2), (‘E-D’, 5), (‘B-A’, 3), (‘C-A’, 1), (‘C-B’, 4), (‘MST’, NULL)]” A C 1 B D 1 C D 2 D E 59 “[(‘A-B’, 1), (‘B-C’, 1), (‘C-D’, 1), (‘D-A’, 1), (‘A-C’, 1), (‘B-D’, 1), (‘MST’, NULL)]” A B 1 A C 1 A D 1 3 d. Example execution
1. Quick Sort (3 pts)a. Implement a function that sorts a given array using the Quick Sort algorithm with in-place partitioning in ascending order. Use the first element at the pivot as shown in the above figure. You can modify sort.cpp and sort.h files for this problem. b. Input & Output Input: A sequence of commands – (‘insertion’,integer): insert integer into the array (there will be no duplicated integers.) – (‘quickSort’,NULL): sort the array using the Quick Sort algorithm Output: – Every value in the array whenever swapping happens including the initial step, string separated with the white space (please use built-in function to print the array). – We won’t test array size over 20 or array size of 0. c. Example Input & Output Input Output [(‘insertion’,17), (‘insertion’,20), (‘insertion’,2), (‘insertion’,21), (‘insertion’,4), (‘quickSort’,NULL)] 17 20 2 21 4 17 2 20 21 4 17 2 4 21 20 4 2 17 21 20 2 4 17 21 20 2 4 17 20 21 [(‘insertion’,5), (‘insertion’,6), (‘insertion’,4), (‘insertion’,3), (‘insertion’,2), (‘insertion’,1), (‘quickSort’,NULL)] 5 6 4 3 2 1 5 4 6 3 2 1 5 4 3 6 2 1 5 4 3 2 6 1 5 4 3 2 1 6 1 4 3 2 5 6 1 2 3 4 5 6 d. Example execution2. Recursive Merge Sort (3 pts)a. Implement a function that sorts a given array using the Merge Sort algorithm in ascending order using recursive merge sort. Split a list of elements into two sublists with the first sublist bigger than the second sublist for the case when the input array has an odd number of elements. You can modify sort.cpp and sort.h files for this problem. b. Input & Output Input: A sequence of commands – (‘insertion’,integer): insert integer into the array. – (‘mergeSort’,NULL): sort the array using the Merge Sort algorithm. Output: – Every value in the array for each sorting step including the initial step, string separated with the white space (please use built-in function to print the array). – You don’t need to consider exceptional cases such as overflow or an empty array. We will not test such cases. c. Example Input & Output Input Output [(‘insertion’,56), (‘insertion’,42), (‘insertion’,20), (‘insertion’,17), (‘insertion’,13), (‘insertion’,28), (‘insertion’,14), (‘mergeSort’,NULL)] 56 42 20 17 13 28 14 42 56 20 17 13 28 14 42 56 17 20 13 28 14 17 20 42 56 13 28 14 17 20 42 56 13 28 14 17 20 42 56 13 14 28 13 14 17 20 28 42 56 [(‘insertion’,6), (‘insertion’,5), (‘insertion’,4), (‘insertion’,3), (‘insertion’,2), (‘insertion’,1), (‘mergeSort’,NULL)] 6 5 4 3 2 1 5 6 4 3 2 1 4 5 6 3 2 1 4 5 6 2 3 1 4 5 6 1 2 3 1 2 3 4 5 6 d. Example execution >> ./pa3.exe 2 “[(‘insertion’,56), (‘insertion’,42), (‘insertion’,20), (‘insertion’,17), (‘insertion’,13), (‘insertion’,28), (‘insertion’,14), (‘mergeSort’,NULL)]” [Task 4] 56 42 20 17 13 28 14 42 56 20 17 13 28 14 42 56 17 20 13 28 14 17 20 42 56 13 28 14 17 20 42 56 13 28 14 17 20 42 56 13 14 28 13 14 17 20 28 42 56 3. BST Insertion / Deletion (4 pts) a. Implement functions that inserts and deletes an element into a binary search tree (BST). You can modify bst.cpp and bst.h files for this problem. b. Input & output of BinarySearchTree::insertion Input: Key of the element to be inserted. The key has a positive integer value. Output: Return the -1 if the key already exists in the tree, 0 otherwise. (If the key already exists, do not insert the element)Example of deleting the node with degree 2 in Binary Search Tree c. Input & output of BinarySearchTree::deletion Input: Key of the element to be deleted. Output: Return -1 if the key does not exist in the tree, 0 otherwise. If the key does not exist, do not delete any element Note that replace the smallest key in right subtree when delete the node with degree 2 d. task_3 prints i. the return for each insertion/deletion and ii. the results of preorder and inorder traversal of the constructed tree. e. Example Input & Output Input Output [(‘insertion’,4), (‘insertion’,6), (‘insertion’,6), (‘insertion’,7), (‘deletion’,7)] 0 0 -1 0 0 4 6 4 6 [(‘insertion’,4), (‘insertion’,2), (‘insertion’,10), (‘insertion’,9), (‘insertion’,15), (‘insertion’,1), (‘deletion’,1), (‘deletion’,4), (‘deletion’,10)] 0 0 0 0 0 0 0 0 0 9 2 15 2 9 15 f. Example execution4. AVL Tree Insertion / Deletion (10 pts)Example of left rotation to resolve RR imbalance AVLTree class is a subclass of BinarySearchTree class implemented in task3. If you use the insert and erase functions of BinarySearchTree, you can implement it more simply. a. Implement a function that inserts and deletes an element into a AVL tree. The insertion and deletion might cause the AVL tree to violate its properties (Imbalance). Your code should be able to resolve the imbalances (LL, LR, RL, RR) of the AVL tree. You can modify avl.cpp and avl.h files for this problem. Also, You can add public member at Node class implemented in tree.h if needed. b. Input & Output of AVLTree::insertion (insert function for AVL tree) Input: key of element to be inserted. (keys are given only positive value) Output: – 0, if the insertion is successful. – -1, if the key already exists in the tree. c. Input & Output of AVLTree::deletion (delete function for AVL tree) Input: key of element to be deleted. (keys are given only positive value) Output: – 0, if the deletion is successful. – -1, if the key does not exist in the tree. – Note that replace the smallest key in right subtree when delete the node with degree 2 in BST deletion stage. d. task_4 prints i. The return value for each insertion and deletion ii. The results of preorder and inorder traversal of the constructed tree. e. Example Input & Output Input Output [(‘insertion’,4), (‘insertion’,6), (‘insertion’,0), (‘deletion’,7)] 0 0 0 -1 4 0 6 0 4 6 [(‘insertion’,4), (‘insertion’,2), (‘insertion’,10), (‘insertion’,9), (‘insertion’,15), (‘insertion’,5), (‘insertion’,0), (‘deletion’,4), (‘insertion’,10)] 0 0 0 0 0 0 0 0 -1 9 2 0 5 10 15 0 2 5 9 10 15 f. Example execution5. Open hash table (2 pts) a. Implement an open hash table with digit-folding-method. This hash table is used with integer keys and hashing into a table of size M. This hash table uses a singly linked list as a collision handling method. You don’t need to consider the maximum length of the linked list, deletion of a key which does not exist or multiple insertions of the same key. You can modify open_hash_function.cpp, open_hash_table.cpp, open_hash_function.h and open_hash_table.h files for this problem. b. Input & output Input: A sequence of commands – (‘M’,integer): the size of a hash table. (The first command is always ‘M’) – (‘insert’,int): insert integer into the hash table. – (‘delete’,int): delete integer from the hash table. Output: For each slot of the hash table, print out – the linked list, if the state of the slot is occupied. – the state, if the state of the slot is empty. c. Example Input & Output Input Output [(‘M’,4), (‘insert’,32615), (‘insert’,315), (‘insert’,6468), (‘insert’,94833)] 0: 6468 1: 32615, 315 2: empty 3: 94833 [(‘M’,4), (‘insert’,32615), (‘insert’,315), (‘insert’,6468), (‘insert’,94833), (‘delete’,32615), (‘delete’,6468)] 0: empty 1: 315 2: empty 3: 94833 [(‘M’,4), (‘insert’,32615), (‘insert’,315), (‘insert’,6468), (‘insert’,94833), 0: 22 1: 315 (‘delete’,32615), (‘delete’,6468), (‘insert’,22)] 2: empty 3: 94833 d. Example execution6. Closed hash table (5 pts) a. Implement a closed hash table with rehashing implementation. This hash table is used withThis hash table usesn-bit integer keys and hashing into aquadratic probing as a collisiontable of sizehandling method. The index2. of the key after -th collision, , is: ℎ() ℎ() = (ℎ() + ()) 2 Where is the binary mid-square hash function. This function maps an -bit integer key to an index of aℎ() 2-sized table.n As a key is n bits, your code shouldr () n treat the square of the key as 2 bits. You can assume that is even. , is: () = 2 + + 1 You don’t need to consider an insertion when the table is full or a deletion of a key which does not exist or multiple insertions of the same key. And also you don’t need to consider the case when the hash function cannot find an available slot. Assume you cannot insert a new key into the deleted slot. You can modify closed_hash_function.cpp, closed_hash_table.cpp, closed_hash_function.h and closed_hash_table.h files for this problem. b. Input & Output Input: A sequence of commands – (‘n’,integer): the size of a key. (The first command is always ‘n’) – (‘r’,integer): the size of an index. (The second command is always ‘r’) – (‘insert’,integer): insert integer into the hash table. – (‘delete’,integer): delete integer from the hash table. Output: For each slot of the hash table, print out – the value, if the state of the slot is occupied. – the state if the state of the slot is empty or deleted. c. Example Input & Output Input Output [(‘n’,4), (‘r’,2), (‘insert’,15), (‘insert’,2), (‘insert’,3)] 0: 15 1: 3 2: empty 3: 2 [(‘n’,4), (‘r’,2), (‘insert’,15), (‘insert’,2), (‘insert’,3), (‘delete’,2), (‘delete’,3)] 0: 15 1: deleted 2: empty 3: deleted [(‘n’,4), (‘r’,2), (‘insert’,15), (‘insert’,2), (‘insert’,3), (‘delete’,2), (‘delete’,3), (‘insert’,4)] 0: 15 1: deleted 2: 4 3: deleted d. Example execution
