IMPORTANT NOTE: Back up your code constantly somewhere other than the Raspberry Pi. Improper device tree modications can cause the Pi not to boot up anymore. If that happens, you will have to reash your microSD card. We probably can prevent this by plugging in your microSD card into a laptop and modifying the cong.txt le from there, but anything is possible.You know how hardware is. Your goal is to toggle an external LED on and o from kernel space by making a driver that uses gpiod and interrupts. You must use gpio pin 5 for the LED and 6 for the button.Note that these numbers don’t correspond to the physical pin numbers, as we have discussed many times in class. The circuit is the same as assignment 2, but you must use the pins I’ve specied. Also note that usually gpio 6 for the button will usually have a pull up scheme where the value read will be 1 when the button is not pressed, meaning the button should usually connect gpio 6 to ground when pressed.Rubric 1. (50 points) In person demonstration of functionality. In person demonstrations can be done during instructor or TA oce hours and possibly before or after class. We will also oer check o during 3-5pm on Friday Nov 3rd as well, WHICH WILL BE THE LAST TIME AVAILABLE TO DEMO YOUR PROJECT 2. a. (10 pts) Module insertion message (from a simple printk() statement) appears in kernel log b. (10 pts) LED state changes via module c. (10 pts) Button state can be detected via module d. (10 pts) Interrupt service routine called and prints kernel log message when button is pressed, and debouncing works e. (10 pts) Button press toggles LED on/o using interrupt service routine, and toggling works again after module removed and inserted again i. Toggling should not work during the period when the module has been removed but not reinserted2. (50 points) Submission of relevant commented code les and report to Canvas a. (10 points) Code attempts to achieve objectives/requirements stated in instructions b. (10 points) Code reasonably includes comments (at least every other line includes a comment) c. (5 points) The following le(s) must be submitted in source form (.tbl, .c, etc.) – not a PDF i. gpiod_driver.c ii. Your .dts le iii. cong.txt d. (25 points) PDF report that includes: i. (1 point) Title of assignment/project ii. (1 point) Your name iii. (5 points) 1 paragraph (at least 4 sentences) describing the goal of the project and the steps you took to complete it (include a statement on each key function) iv. (5 points) A 2nd paragraph (at least 4 sentences) describing what you found challenging/any bugs you had to x, what you learned, and what you think would be another interesting application for this gpiod approach. v. (5 points) Include a screenshot showing a signicant portion or all of your driver code. vi. (4 points) Include a screenshot of terminal output showing the messages printed by your code. vii. (4 points) All screenshots in the report must include a gure label with a short description.Guidelines ● Three files must be worked with to pull this off: ○ Device tree overlay file ○ Boot configuration file config.txt which is in /boot/ ■ You will have already played with this file in-class ■ We just need config.txt to include the compiled device tree overlay file ○ Module/driver file, which I will call gpiod_driver.c ● For the device tree overlay ○ You need to make a device tree overlay file that enables gpiod to access gpio pins 5 and 6 according to the “Device Tree” section of the documentation here (hosted by The Linux Kernel Archives).■ You can start with the file contents here: https://stackoverflow.com/a/59950806 (posted by user Simon on Stack Overflow) ■ The modifications you should make: 1. target should be replaced with target-path and should be set equal to the root node of the device tree, i.e., “/” (including the quotation marks) ○ See an example of this target-path here ○ This will ultimately make it so we have a fake device under the root node of the device tree that exposes gpio pins 5 and 6 for gpiod to use in kernel space 2. hsncarr should be renamed to a name of your own choosing for the fake device that we are making 3. compatible will have to be set equal to the same name that you later use in your driver code for compatible (you get to choose, so choose a new name)4. carr-gpios is following the syntax specified in the “Device Tree” section of the documentation here (hosted by The Linux Kernel Archives) ○ You want to replace carr with your own function name, and duplicate this line with yet another function name ○ Use function names for these two lines to correspond to your LED and your button ○ 17 in each line should be replaced with the appropriate gpio index ■ When you are done with editing the overlay file, compile it (replacing name_of_file with the name of your file): dtc -@ -I dts -O dtb -o name_of_file.dtbo name_of_file.dts ○ If you see errors, you will need to visually debug ■ The previous command compiles your overlay file, producing a compile file with the extension .dtbo ■ We need to copy this compiled file to where the boot configuration can see it: cp name_of_file.dtbo /boot/overlays/ ■ If you end up needing to change your overlay file again, you will have to run the complication and copy commands again ● For the boot configuration file config.txt ○ The kernel is given the device tree at boot ○ We need to make sure modification to the device tree is included by modifying the configuration file to include our modified overlay ○ At the end of the config.txt file in /boot you need to have (where name_of_file refers to the name of your compiled device tree overlay): ■ dtoverlay=name_of_file■ NOTE: Do not include the file extension ○ Once you are done with this, you have to reboot for the overlay to take effect and be implemented in the device tree ■ You will have to reboot anytime you make changes to the overlay file (after again compiling and again copying the compiled file) ● For the module/driver file gpiod_driver.c ○ The previous two modifications should make the GPIO pin accessible to your driver ○ Your driver doesn’t exist yet, however! So now you need to write it, and the goal of your driver is to: ■ Have a button trigger an interrupt that toggles an LED, all in kernel space (i.e., all in your driver) ■ You MUST use GPIOD, not the old deprecated gpio method ○ Grab the template file and Makefile from Canvas (Files/Project 2/) ○ The template file has /*INSERT*/ or other notes wherever code where will definitely have to be added ○ Feel free to draw liberally (including copy and paste) interrupt code from here■ That file was using the old gpio method (don’t use those parts), we want to use their interrupt code with gpiod ■ Be sure to cite that reference if you use the code ■ The author uses IRQF_TRIGGER_RISING, you should change RISING to FALLING (because of the pull up behavior of our gpio pin for the button) ○ You will have to use gpiod [NOT gpio functions – those are deprecated] and irq (interrupt) functions. Below are the prototypes from /include/linux/gpio/consumer.h [real definitions appear to be here], https://elixir.bootlin.com/linux/latest/source/include/linux/interrupt.h, and elsewhere in the Linux source code to give you an idea of the inputs and outputs. ■ struct gpio_desc *__must_check devm_gpiod_get(struct device *dev, const char *con_id, enum gpiod_flags flags); ■ void gpiod_set_value(struct gpio_desc *desc, int value); ■ int gpiod_get_value(const struct gpio_desc *desc); ■ int gpiod_set_debounce(struct gpio_desc *desc, unsigned int debounce); ■ int gpiod_to_irq(const struct gpio_desc *desc); ■ static inline int __must_check request_irq(unsigned int irq, irq_handler_t handler, unsigned long flags, const char *name, void *dev) ■ const void *free_irq(unsigned int irq, void *dev_id)○ The first function gets you a struct pointer of type gpio_desc that refers to the gpio pin for your LED, and the second function takes that pointer and can alter the gpio pin output value (0 or 1). Follow the wonder of slide 35 in Lecture 16 to figure out what to use for *dev on the first function because the devm_gpiod_get_index() function in the slide takes the same first input argument. You cannot just use “dev” – look at what is being passed along from the right screenshot to the left in the slide. For the LED output pin, *con_id will actually just be the function string that you used earlier for the device tree (i.e., relating to -gpios), and button will be similar (but a different name).Flags will be GPIOD_OUT_LOW (start with pin with output value 0) for the LED and GPIOD_IN for the button. ■ Note: we don’t need MODULE_DEVICE_TABLE() for what we’re doing despite it being shown on slide 33 of lecture 16 ○ Your probe function must use printk (with a line feed “ ”) to print some message to the kernel log (which can be viewed with tail -f /var/log/kern.log) when the module is inserted ○ You must implement switch debouncing using the gpiod_set_debounce function (you will do this in the probe function, not the interrupt service routine)○ Be sure to free your irq in the remove function, otherwise your system may freeze when you reinsert the module ○ Your interrupt service routine must print a message to the log (printk) indicating that the button has been pressed ○ Here is the workflow you will use ■ Write the driver code ■ Compile it by using the new Makefile from canvas (Files/Project 2/) and running “sudo make” after changing ■ Make sure the module is removed (if previously inserted) by running: sudo modprobe -r gpiod_driver 1. This is what we use for these types of modules, rather than insmod/rmmod2. Notice we don’t put .ko for this function ■ Copy your newly compiled gpiod_driver.ko to a special spot for these kinds of modules [step 1 (making the folder) must be done the first time]: 1. sudo mkdir /lib/modules/$(uname -r)/misc/ 2. sudo cp gpiod_driver.ko /lib/modules/$(uname -r)/misc/ ■ Update the dependencies related to modules (again, something special we have to do for this kind of module)1. sudo depmod ■ Insert the module: 1. sudo modprobe gpiod_driver ○ Again, no .ko extension for this command ■ Now try your button and see if it toggles the LED ■ You can also watch the kernel log in parallel (another terminal) to see if you are getting print statements from your driver related to what you are trying: 1. tail -f /var/log/kern.log ■ If it doesn’t work, you’ll loop back through these bullet points after attempting to fix the code
You will interface your Raspberry Pi with an external circuit implemented on a breadboard via the Pi’s GPIO pins. Your software will run in user space by using the libgpiod library in a typical .c le (a user application).Choose two GPIO pins and set one up to toggle an LED and the other to read from a button/switch. Be sure to use the 330 ohm resistor in series with the LED. Check out the pinouts online or in the slides for the Raspberry Pi to know where to connect wires. Make it so that when the button is open initially, the LED will be on for (approximately) 0.5 seconds and o 0.5 seconds and continue to alternate until the end of time.Then, if the “button” is pressed and released quickly, that should double the frequency of the LED’s alternation between on and o. Any additional quick presses and releases should continue to double the frequency. A long press should result in a return to the original frequency of alternating between on and o. Then it should be able to be accelerated again if the button is pressed quickly. A button press must be detected pretty immediately and cause the LED to turn o while the button is being pressed.In Ryon B12 (door code: 3090#) [you should have 24/7 card access to Ryon], there will be a small box immediately to your right containing LEDs, 330 Ohm resistors, jumper wires, breadboards, and buttons if you did not get them in class. There is a red sheet of paper in front of this box saying “424 Assignment 2”. You can of course use your own supplies. Please feel free to use the same circuit between you and classmates, no need for each of you to have your own breadboard/LEDs/etc. Let me know if anything runs out. Don’t return your borrowed supplies to me until the end of the semester, as we will use them for future work.Note: Be sure to consider button debouncing: One seeming press of the button will generally result in multiple rapid switches between 0 and 1 for the GPIO pin value until it stabilizes, which means that you may not get a clean 0 to 1 or 1 to 0 transition when pressing or releasing. Your code should be robust to this issue, and accuracy in terms of time keeping can be sacriced as such. In general the code does not need to be exact for timing for this assignment.Rubric ● (50 points) In person or submitted recorded video demonstration of functionality. In person demonstrations can be done during instructor or TA oce hours. ○ (10 points) LED toggles on and o ○ (10 points) Initial LED toggling is approximately 0.5 s on and 0.5 s o ○ (10 points) Quick (you can be the judge of quick) button press causes LED toggling frequency to double ○ (10 points) Long (again, you can be the judge of long) button press causes LED toggling pattern to return to 0.5 seconds on and 0.5 seconds o ○ (10 points) Further quick button presses continue to double toggling frequency as expected ○ Recorded video demonstration submission■ If you prefer to submit a video demo, please upload it to the Box folder that I shared with your Rice email. It is your responsibility to let me know 48 hours before the deadline if you do not have access to the folder, otherwise it is not my responsibility if you have to submit late. Video les submitted must be named as the following (replacing words as appropriate): ELEC424_Assignment2_Firstname_Lastname_netID● Note: I have set the privacy to where I believe no one can view each others’ videos, however you will be able to see who has uploaded and who has not. If this is a concern for you, please meet with us to do an in person demonstration instead. ● (50 points) Submission of relevant commented code les and report to Canvas ○ (10 points) Code attempts to achieve objectives/requirements stated in instructions ○ (10 points) Code reasonably includes comments (at least every other line includes a comment) ○ (5 points) The following le(s) must be submitted in source form (.tbl, .c, etc.) – not a PDF■ Your main .c le ○ (25 points) PDF report that includes: ■ (1 point) Title of assignment/project ■ (1 point) Your name ■ (5 points) 1 paragraph (at least 4 sentences) describing the goal of the project and the steps you took to complete it (include a statement on each key function)■ (5 points) A 2nd paragraph (at least 4 sentences) describing what you found challenging/any bugs you had to x, what you learned, and what you think would be another interesting application for GPIO. ■ (5 points) After completing the coding and demonstration parts of the assignment, I grant permission for you to ask chatGPT to complete an assignment similar to this one. Ask chatGPT how to make a gpio C program for the Raspberry Pi Zero W using libgpiod (no need to give it all the details, you can ask for a simple version). Write a 3rd paragraph (at least 4 sentences) describing what chatGPT tells you, how accurate you think it is, and how it seems to dier from your solution.● You must include a shared link to your chatGPT chat (instructions) and cite chatGPT according to the standard of this document. ■ (4 points) Include a screenshot showing a signicant portion or all of your code.■ (2 points) Include a screenshot of terminal output showing the messages printed by your code. ■ (2 points) All screenshots in the report must include a gure label with a short description.Guidelines ● Install the necessary package on your Pi: sudo apt install libgpiod-dev ● Your code must print out a message to the console every time that a button press is detected, and state which type (short or long) is detected● Consider my incomplete code below for some of the most relevant functions in libgpiod: ○ // Declare variables ○ const char *chip_title = “gpiochip0”; ○ struct gpiod_chip *chip; ○ struct gpiod_line *line_output; ○ struct gpiod_line *line_input; ○ // Open chip that handles GPIO ○ chip = gpiod_chip_open_by_name(chip_title); ○ // Grab lines from chip for output (LED) and input (button) ○ // v and w should be GPIO numbers – 5 and 6 are my suggestions ○ line_output = gpiod_chip_get_line(chip, v); ○ line_input = gpiod_chip_get_line(chip, w); ○ // Specify which line is output and which is input ○ // The “something” is a name that doesn’t matter for us ○ // z is the initial output value, can be 0 or 1 ○ gpiod_line_request_output(line_output, “something”, z); ○ gpiod_line_request_input(line_input, “something”); ○ // The below functions set values ○ gpiod_line_set_value(line_output, t) ○ gpiod_line_set_value(line_output, y) ○ // The below function reads input ○ button_state = gpiod_line_get_value(line_input); ○ // The following two lines close things up for you ○ gpiod_line_release(line); ○ gpiod_chip_close(chip);● You will have to include the flag -lgpiod at the end of the compile command when running gcc, otherwise it will say gpiod functions are undefined ● You can get inspiration from online examples, but do not directly copy their code ● You may talk with classmates about the assignment, but do not share or copy code● Although libpgiod is currently hosted on kernel.org, you can easily view the relevant (albeit older) gpio.h header file on GitHub here to know more about what the input/output arguments are for the above functions ● Feel free to use any typical libraries for timing
You will create your very own system call and add it to the Linux kernel. This is kernel hacking, congratulations! Then you will compile your customized kernel and test it within a Linux environment using CLEAR (not the Raspberry Pi). The workow will be to edit the kernel to add a system call, develop a C program that calls the new system call, and then use user-mode Linux (UML) to run the modied kernel and C test program.Rubric 1. (56 points) In person or submitted recorded video demonstration of functionality. In person demonstrations can be done during instructor or TA oce hours. a. Do not implement your counter in user space (e.g. don’t have your counter in your C test le – that will result in a serious point reduction (let’s say -80 points) because that’s not the point of this assignment). The counter must be in the syscall function.b. Each of the following is worth 7 points. If doing a recorded video, demonstrate items iii to viii sequentially and provide narration stating which item you are testing at each part of the video.i. netid_test produces print statement about calling syscall ii. syscall prints counter value to terminal/console (this happens by default with printk with the default message priority)iii. syscall increments counter value when rst input argument is 0 and the count is incremented by the amount specied by the second argument; iv. syscall increments counter by when 1 when test script given no input arguments (test script will pass 0 and 1 as rst and second arguments, respectively, to syscall in this case)v. syscall correctly increments counter if the rst argument is 0, the second is a positive number, and the third argument is another positive number vi. syscall resets counter value to 0 for rst input argument of 1 (regardless of any second and third input arguments)vii. syscall prints message about input being invalid if rst input argument not 0 or 1 viii. dmesg shows previous syscall printk() outputs (this veries that a system call was used)c. Recorded video demonstration submission i. If you prefer to submit a video demo, please upload it to the Box folder that I shared with your Rice email. It is your responsibility to let me know 48 hours before the deadline if you do not have access to the folder, otherwise it is not my responsibility if you have to submit late. Video les submitted must be named as the following (replacing words as appropriate): ELEC424_Assignment1_Firstname_Lastname_netID1. Note: I have set the privacy to where I believe no one can view each others’ videos, however you will be able to see who has uploaded and who has not. If this is a concern for you, please meet with us to do an in person demonstration instead.2. (44 points) Submission of relevant commented code les and report to Canvas a. (5 points) Code attempts to achieve objectives/requirements stated in instructions b. (10 points) Code commented in detail c. (4 points) Three les must be submitted in their source form (.tbl, .c) – not a PDF i. arch/x86/entry/syscalls/syscall_64.tbl ii. kernel/sys.c iii. Netid_test.c d. (25 points) PDF report that includes: i. (1 point) Title of project ii. (1 point) Name iii. (5 points) 1 paragraph (at least 4 sentences) describing the goal of the project, what les you modied, and what your approach was to the problem.iv. (5 points) A 2nd paragraph (at least 4 sentences) describing what you found challenging, what you learned, and what you think would be another interesting system call to invent.v. (5 points) After completing the coding and demonstration parts of the assignment, I grant permission for you to ask chatGPT to complete an assignment similar to this one. Ask chatGPT how to make a counter system call (no need to give it all the details, you can ask for a simple counter). Write a 3rd paragraph (at least 4 sentences) describing what chatGPT tells you, how accurate you think it is, and how it seems to dier from your solution.1. You must include a shared link to your chatGPT chat (instructions) and cite chatGPT according to the standard of this document. vi. (4 points) Include a screenshot showing a portion or all of your system call code, and another screenshot showing a portion or all of your test le code.vii. (2 points) Include two screenshots of terminal output showing your counter working on one test or two. viii. (2 points) All screenshots in the report must include a gure label with a short description.Note: Be sure that you are using linux kernel version 6.5.5 (in other words, follow the instructions on the next pages). Otherwise, we may not grant points for the demonstration.Steps 1. Open up a terminal and log into CLEAR 2. Make a folder for this assignment and “cd” into that directory 3. Download the Linux kernel source code, version 6.5.5 (you *must* use this version for this assignment) using the following command: ○ wget https://cdn.kernel.org/pub/linux/kernel/v6.x/linux-6.5.5.tar.xz4. Try the “ls” command – you should see something like “linux-6.5.5.tar.xz” – this is a compressed folder, we need to uncompress it using tar. Use the following command to uncompress it: ○ tar -xvf linux-6.5.5.tar.xz ○ Note: You can be fancy and lazy instead by running “tar -xvf $(!!)” after running ls, where $(!!) will insert the output of the last command you ran5. Change your directory to the uncompressed folder (mine was linux-6.5.5) 6. Add your system call to the system call table in the Linux source code. Do so by editing the arch/x86/entry/syscalls/syscall_64.tbl le. Look for the end of the rst range of system calls – they should end somewhere around 450. Let’s say the nal system call was: 443 common joe_cool sys_joe_coolYou would want to add yours on the next row as something like: 444 common netid sys_netid Use your actual netid. Also be sure to increment whatever the nal system call number is by 1 for your own system call. In my example, we went from 443 to 444, but yours will be a dierent number. NOTE: There are tabs between the items (e.g. between common and netid), not spaces. So use tabs to make your items line up with the previous system calls.7. Now we need to write our system call code and include that code in a le that will be included in kernel compilation. I recommend editing kernel/sys.c to include your new syscall function. Go to the absolute end of that le and include your function there.The requirements for this function are that it: ○ Takes in 3 input arguments of type: int, int, int ○ Increments a counter when the rst input argument is 0; the second input (int) argument species how much the counter should increase by; the third argument (int) species what number the counter should start ati. This counter should start at zero (before being incremented) unless the third argument species something else ii. This will require the counter to be a static variable – look around online, talk with a friend, or talk with me if you are unsure of how static variables work ○ Resets the counter to 0 when the rst input argument (int) is 1 (second and third input arguments don’t matter in this case)i. Counter will not be incremented in this instance ○ Prints out the current count using printk() [with linefeed, otherwise you might not see it until later – the kernel is fun like that] in both cases of rst input 0 and 1 ○ Has an error condition if the rst input is not 0 or 1 i. Should use printk() to say a string like “input was invalid” [with linefeed, otherwise you might not see it until later – again the kernel is fun like that] ii. Should use “return -EINVAL” [EINVAL is a macro dened in the kernel – it means invalid argument]8. Enter “make ARCH=um menucong” ○ This is how we congure the linux kernel before it is compiled ○ ARCH=um is specifying user-mode linux (UML), explained later in this document ○ Use the right arrow key multiple times to select Save on the bottom and then hit enter ○ Hit enter again to save cong, then hit enter again to return to the main menu ○ Hit escape twice in a row to exit the conguration9. Enter “make -j20 ARCH=um linux” [see below if compilation fails] ○ Compilation may fail because of an error mentioning random. If so, you will need to edit the le it mentions (util.c): i. Comment out an include line (#include ) ii. Change the os_getrandom() function’s return line to be “return 0;” ○ You are compiling the Linux kernel! ○ -j20 has the command run in parallel10. If it compiled, you shouldn’t see any error messages. ○ If it didn’t compile, look at your counter function code and syscall table code, then try to gure out what went wrong.11. Work on a C le to test your system call, which will just be a main function that uses syscall with your syscall number to invoke your custom syscall. Save this c le in the root of the linux source code that you’ve compiled. Use the following header les for the le, and see the next point for the requirements for the program. ○ #include ○ #include ○ #include ○ #include ○ #include Test program requirements: This C test le must: ○ Be able to take in three command line arguments and convert them to the right types (int, int, int) to be passed as the reset ag, the increment value, and the initial value to the counter system call ○ Use syscall() to call your custom counter system call ○ Include a printf() statement that says “Calling counter syscall…” with a linefeed○ The test le shouldn’t require command line arguments i. If no command line arguments are given, the reset ag should default to 0, the increment value should default to 1 (the counter will be incremented by 1), and the initial value before increment should default to 0○ The test le should support a variable number of command line arguments i. If the rst argument is 1, no other arguments should be required to be given ii. If the rst argument is 0, the second argument is an arbitrary value, and the third argument is not provided, the counter should increment the current count value by the second argumentiii. If the rst argument is 0, the second argument is an arbitrary value, and the third argument is provided, then the counter should have its value as the third argument incremented by the second argument 12. Compile your C test le using “gcc -o netid_test netid_test.c”, replacing netid in both cases with your own.13. Now we will run user-mode Linux (UML), which eectively runs an entire Linux instance within a process running on Linux. It’s a little meta. This means that you don’t have to replace CLEAR’s currently running kernel (which is not allowed!), which provides a number of advantages and dramatically improves turnaround time on debugging kernel code.14. To run UML, we enter “./linux rootfstype=hostfs rw init=/bin/bash” ○ You should see a bash prompt with a blinking cursor ○ If any message pops up like “random: crng init done”, just hit enter and the bash prompt will reappear15. Now change directories to where your linux source and test le are (note: you currently at root /) ○ On CLEAR, you want to change to /storage-home/n/netid [except replacing n with the rst letter of your netID and replacing netid with your full netid] then change to the specic folder where your test script is16. Try running your test script via “./netid_test” (with your netid replaced) 17. Do the “Calling counter syscall…” [printf() from your test function] message and count [printk from your syscall code] print to the console? ○ Does the count increment properly when 0 is given as the rst input argument and a positive number as the second input argument?○ Does it reset when 1 is given as the rst input argument? ○ Will it start incrementing again after reset with 0 as the rst input argument and a positive number as the second input argument? ○ Does the counter increment correctly if the rst argument is 0, the second is a positive number, and the third argument is another positive number? ○ Does input besides 0 or 1 (e.g. 10) for the rst argument produce your printk() message about invalid input and the count is not incremented? i. If you see delays where messages don’t appear until another system call, make sure you have linefeeds at the end of every print statement18. We must also check if the kernel buer was also getting this output – try “dmesg | tail -n10” to view the 10 most recent messages in the kernel buer. Your counter printk() statements should appear there! 19. See the rubric at the beginning of this document for turn in instructions and deliverables
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
Problem 0a [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().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: Weight(x) = Ym j=1 fj (x) 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_p1.pyNotice we are already able to solve the CSPs, because in submission.py, a basic backtracking search is already implemented. Recall that backtracking search operates over partial assignments and associates each partial assignment with a weight, which is the product of all the factors that depend only on the assigned variables.When we assign a value to a new variable Xi , we multiply in all the factors that depend only on Xi and the previously assigned variables. The function get_delta_weight() returns the contribution of these new factors based on the unaryFactors and binaryFactors. An important case is when get_delta_weight() returns 0. In this case, any full assignment that extends the new partial assignment will also be zero, so there is no need to search further with that new partial assignment.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 1a [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 1b [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. 3 • In BacktrackingSearch, if var has been assigned a value, you can retrieve it using assignment[var]. Otherwise var is not in assignment. Hint: you can simply use get_delta_weight() rather than csp.unaryFactors and csp.binaryFactors.Problem 1c [5 points] ¥ The previous heuristics looked only at the local effects of a variable or value. Let’s now implement arc consistency (AC-3) that we discussed in lecture. After we set variable Xj to value a, we remove the values b of all neighboring variables Xk that could cause arcinconsistencies. If Xk’s domain has changed, we use Xk’s domain to remove values from the domains of its neighboring variables. This is repeated until no domains have changed.Note that this may significantly reduce your branching factor, although at some cost. In backtrack() we’ve implemented code which copies and restores domains for you. Your job is to fill in arc_consistency_check().You should make sure that your existing MCV implementation is compatible with your AC-3 algorithm as we will be using all three heuristics together during grading. With AC-3 enabled, it should take you 769 operations only to find all optimal assignments to 8 queens CSP — That is almost 45% fewer even compared with MCV! Hint 1: documentation for CSP.add_unary_factor() and CSP.add_binary_factor() can be helpful. Hint 2: although AC-3 works recursively, you may implement it iteratively. Using a queue might be a good idea. li.pop(0) removes and returns the first element for a python list li. Hint 3: you should remove inconsistent values from self.domains[var] for some var, but the order of domain values should be kept. For example, when a value 2 is popped from [1, 2, 3, 4], the next domain value list is [1, 3, 4] rather than [3, 1, 4].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.Suppose we have boolean variables X1, X2, X3, and we want to enforce the constraint that Y = X1 ∨ X2 ∨ X3, that is, Y is a boolean representing whether at least one variable should be true. For reference, in util.py, the function get_or_variable() does such a reduction. It takes in a list of variables and a target value, and returns a boolean variable with domain [True, False] whose value is constrained to the condition of having at least one of the variables assigned to the target value. For example, we would call get_or_variable() with arguments (X1, X2, X3, True), which would return a new (auxiliary) variable X4, and then add another constraint [X4 = True].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 2a [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 2b [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.
Introduction Figure 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 contentsWarmup 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 2Note: 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.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 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.First, design the recurrence for Vmax,min(s, d) in math. You should express the idea in terms of the following functions: IsEnd(s), which tells you if s is an end state; Utility(s), the utility of a state; Eval(s), an evaluation function for the state s; Player(s), which returns the player whose turn it is; Actions(s), which returns the possible actions; and Succ(s, a), which returns the successor state resulting from taking an action at a certain state. It would be helpful to review the recurrence of depth-limited search in lecture notes.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 are 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 futurestates 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.• If there is a tie between multiple actions for the best move, you may break the tie. • getQ should return Qmax,min for the current state given action.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 1aProblem 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=3You may have to run this scenario a few times to see Pac-Man’s gamble pay off. PacMan would win half the time on an average and for this particular command, the final score would be -502 if Pac-Man loses and 532 or 531 (depending on your tiebreaking method and the particular trial) if it wins (you can use these numbers to validate your implementation). Why does Pac-Man’s behavior in expectimax differ from the minimax case (i.e., why doesn’t he head directly for the ghosts)?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: p(a∈A) = ( 0.5 + 0.5 ∗ 1 len(A) for a = Directions.STOP 0.5 ∗ 1 len(A) 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 rush 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?In 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 even-number select the action randomly according to a certain distribution. For the simplicity of your implementation, suppose the action chosen by even-numbered ghosts are 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 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 6a [8 points] ¥ Write a better evaluation function for Pac-Man in the provided function betterEvaluationFunction. The evaluation function should evaluate states (rather than actions). You may use any tools at your disposal for evaluation, including any util.py code from the previous assignments.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 point. 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?• You may want to use the reciprocal of important values rather than the values themselves for your features (such as distances between Pac-Man and ghosts). • For your information, our solution code gets more than 1600 scores in average with various random seeds.
Consider an MDP problem. There are four states {SA, SB, SC, SD}, at each of which two actions {+, −} are available, and the state transition and reward have no randomness. All the (action, reward) pairs are described in Figure 1. Assume all the episodes have length 3 (e.g. SA +−→ SB −−→ SA −−→ SA). Figure 1: MDP problem with (action, reward) pairs.Problem 1a [2 points] Ò Find the optimal policy at the initial state SA with discount factor γ = 0.001. Justify your answer. Problem 1b [2 points] Ò Find the optimal policy at the initial state SA with discount factor γ = 0.999. Justify your answer.Problem 1c [2 points] Ò What is the optimal policy at the initial state SB? Explain your answer in terms of discount factor γ ∈ (0, 1).You 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.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] ¥ You will first implement a generic Q-learning algorithm Qlearning, which is an instance of an RLAlgorithm. As discussed in class, reinforcement learning algorithms are capable of executing a policy while simultaneously improving their policy. Look in simulate(), in util.py to see how the RLAlgorithm will be used. In short, your Qlearning will be run in a simulation of the MDP, and will alternately be asked for an action to perform in a given state (Qlearning.getAction), and then be informed of the result of that action (Qlearning.incorporateFeedback), so that it may learn better actions to perform in the future.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 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 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.
In this homework, 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.1 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.2 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 segmentation and insertion decisions based on the cost of produced 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 P p(w1, w2, . . . , wN−1, wN ) = N i=1 p(wi |w1, . . . , wi−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). 3 We’ll use the n-gram model’s negative loglikelihood − 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.4 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.Furthermore, these costs are additive: for a unigram model u (n = 1), the cost assigned to [w1, w2, w3, w4] is u(w1) + u(w2) + u(w3) + u(w4).In German, Windschutzscheibenwischer is ”windshield wiper”. Broken into parts: wind wind; schutz block / protection; scheiben panes; wischer wiper.2See https://en.wikipedia.org/wiki/Abjad. 3This model works under the assumption that text roughly satisfies the Markov property. 4This estimate p(wi |wi−(n−1), . . . , wi−1) is gathered from frequency counts taken by reading Leo Tolstoy’s War and Peace and William Shakespeare’s Romeo and Juliet. But, the estimation is applied with 1) parameter sharing that assume p(wi |wi−(n−1), . . . , wi−1) = p(wj |wj−(n−1), . . . , wj−1) when two n-gram word sequences are identical, and 2) laplace smoothing that prevents p(wi |wi−(n−1), . . . , wi−1) to become zero. We’ll cover these two techniques in the chapter 7.For a bigram model b (n = 2), the cost is b(w0, w1) + b(w1, w2) + b(w2, w3) + b(w3, w4), where w0 is -BEGIN-, a special token that denotes the beginning of the sentence. We have estimated u and b based on the statistics of n-grams in text. All the costs returned by the cost functions are non zero. Also, any words not in the corpus are automatically assigned a high cost, so you do not have to worry about this part.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 1a [4 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 statespace 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, and you should make use of it here.5 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 lower case. The function segmentWords should return the segmented sentence with spaces as delimiters, i.e. ‘ ’.join(words).For convenience, you can actually 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 houseConsole 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.You are encouraged to refer to NumberLineSearchProblem and GridSearchProblem implemented in util.py for reference. They don’t contribute to testing your submitted code but only serve as a guideline to how your code should look like.5Solutions that use UCS ought to exhibit fairly fast execution time for this problem, so using A* here is unnecessary.Problem 1b [6 points] ¥ Implement an algorithm that finds the optimal word segmentation for a given input character sequence, with the constraint that it can only have at most k words. This is called k-word segmentation. For example, if the input sequence is ‘pepperonimage’ and k is 2, it should be segmented into ‘pepperoni mage’ instead of ‘pepper on image’, even though the latter is more fluent.When you’ve completed your implementation, the function segmentKWords should return the k-segmented sentence with spaces as delimiters, i.e., ‘ ’.join(words). You can assume that k ranges from 1 to the length of the input sequence (or the number of characters in the sequence). The argument unigramCost is the same as in problem 1a.To test your implementation, use the k-seg command in the program console followed by the value of k. For example: >> k-seg 4 thisisnotmybeautifulhouse Query (k-seg) (k = 4): thisisnotmybeautifulhouse this isnotmy beautiful houseNow 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).6 For example, possibleFills(‘fg’) returns set([‘fugue’, ‘fog’]).Problem 2a [4 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 empty string is a valid element of the list.The argument queryWords is the input sequence of vowel-free words. Note well that the empty string is a valid such word. 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.Since we use a limited corpus, some seemingly obvious strings may have no fills, eg chclt → {}, where chocolate is actually a valid fills. Dont worry about these cases. Note: If some vowel-free word w has no reconstructions according to possibleFills, your implementation should consider w itself as the sole possible reconstruction. 6This mapping, too, was obtained by reading Tolstoy and Shakespeare and removing vowels.Use the ins command in the program console to try your implementation. For example: >> ins thts m n th crnr Query (ins): thts m n th crnr thats me in the cornerThe console strips away any vowels you do insert, so you can actually type in plain English and the vowel-free query will be issued to your program. This also means that you can use a single vowel letter as a means to place an empty string in the sequence. For example: >> ins its a beautiful day in the neighborhood Query (ins): ts btfl dy n th nghbrhd its a beautiful day in the neighborhoodProblem 2b [6 points] ¥ This time, you are given a sequence of English words with missing vowels and a set of specific vowels. Implement an algorithm for the limited vowel insertion problem that inserts vowels into the words without using the provided set of restricted vowels. Use the UCS subroutines.When you’ve completed your implementation, the function insertLimitedVowels should return the reconstructed word sequence containing only the allowed vowels as a string with space delimiters, i.e., ‘ ’.join(filledWords). The input set of restricted vowels is assumed to be given as a string (e.g., ‘a’, ‘iou’). The other assumptions and arguments queryWords, bigramCost, and possibleFills are the same as in problem 2a.To test your implementation, use the limited-ins command in the program console, followed by the string of restricted vowels. The query is preprocessed in the same way as the ins command. For example: >> limited-ins i thats me in the corner Query (limited-ins) (limited_vowels = ‘i’): thts m n th crnr thats me on the cornerWe’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 3a [6 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-of-vocabulary beginning-of-sentence word -BEGIN5 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 2, 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 peopleNow, we’ll apply A* search to accelerate search speed. First, you exercise by making a simple problem and a heuristic function to be familiar with A* search. Then, you make a heuristic function for the text reconstruction task.Problem 4a [4 points] Ò In this problem, you should define your own simple search problem SimpleProblem and a heuristic function admissibleButInconsistentHeuristic. As the name suggests, the heuristic function should be admissible but not consistent, so A* cannot find the minimum cost path with the heuristic function. Also, we assume the heuristic returns 0 when given an end state. Before implementing them, check UniformCostSearch and its parameter heuristic to examine how A* works.Problem 4b [6 points] ¥ We’re going to speed up the joint space and vowel insertion problem with A*. Recall that score an output using a bigram model b(w ′ , w) is more expensive than using a unigram model u(w) because we have to remember the previous word w ′ in the state. Now let’s tackle the task by following the guideline below:1. Implement makeWordCost that returns a unigram cost function wordCost (which takes any w and returns a number) when given the bigram cost function bigramCost (which takes any (w ′ , w) and returns a number). Your can exploit ub(w) = minw′ b(w ′ , w), where ub and b corresponds to wordCost and bigramCost respectively. Also, you may need wordsegUtil.SENTENCE_UNK to indicate any non-existing word in training corpus. Note: Don’t confuse ub defined here with the unigram cost function u used in Problem 1.2. Implement RelaxedProblem which is a relaxed problem of JointSegmentationInsertionProblem. The relaxed problem calculate action’s cost based on wordCost.3. Implement makeHeuristic which returns a consistent heuristic function for the given query. You can exploit RelaxedProblem and util.DynamicProgramming.4. Finally implement fastSegmentAndInsert which should be faster than segmentAndInsert. You should use UniformCostSearch.solve with a proper heuristic argument.
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 touching • (+1) quite impressive • (−1) not impressive • (−1) quite boringEach 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,touching : 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’, ‘touching’, ‘quite’, ‘impressive’, ‘not’, ‘boring’) 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.In 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: fw(x) = ( +1 if w · ϕ(x) > 0 −1 if w · ϕ(x) < 0 = ( +1 if σ(w · ϕ(x)) > 0.5 −1 if σ(w · ϕ(x)) < 0.5where σ 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)) pw(y | x) = ( σ(w · ϕ(x)) if y = 1 1 − σ(w · ϕ(x)) if y = −1 You should first derive ∇wLossNLL(x, y, w), then exploit the formula to update weights for each example. 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, feature vector will counts number of occurrences of consecutive words of length n. Implement extractNgramFeatures which extract n-gram word features.Problem 3a [2 points] Suppose we have a feature extractor ϕ that produces 2-dimensional feature vectors, and a toy dataset Dtrain = {x1, x2, x3, x4} with 1. ϕ(x1) = [−1, 0] 2. ϕ(x2) = [2, 0] 3. ϕ(x3) = [0, 3] 4. ϕ(x4) = [4, 3]Run 2-means on this dataset. What are the final cluster centers µ? Run this algorithm until it converges, with initial centers: 1. µ1 = [−2, 0] and µ2 = [3, 0] 2. µ1 = [−1, −1] and µ2 = [2, 3]Problem 3b [6 points] Implement the kmeans function. You should initialize your k cluster centers to random elements of examples.After a few iterations of k-means, your centers will be very dense vectors. In order for your code to run efficiently and to obtain full credit, you may need to precompute certain quantities. As a reference, our code runs in under a second on all test cases. You might find generateClusteringExamples in util.py useful for testing your code.
In this problem, you will implement a bunch of short functions related vector representations. The main purpose of this exercise is to familiarize yourself with Python, and to understand vector representations in programming.If you’re new to Python, the following 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/SimpleProgramsProblem 1a [2 points] Implement denseVectorDotProduct in submission.py. Problem 1b [2 points] Implement incrementDenseVector in submission.py. Problem 1c [2 points] Implement dense2sparseVector in submission.py.Problem 1d [2 points] Implement sparseVectorDotProduct in submission.py. Problem 1e [2 points] Implement incrementSparseVector in submission.py.Problem 2. Programming 2 In this problem, you will implement short functions more, and the main purpose of this exercise is also to familiarize yourself with Python. Problem 2a [2 points] Implement minkowskiDistance in submission.py. Problem 2b [2 points] Implement getLongestWord in submission.py. Problem 2c [2 points] Implement getFrequentWords in submission.py.
In this task, we aim to perform a basic Computed Tomography (CT) image reconstruction using the Filtered Back Projection (FBP) algorithm. We will utilize the sinogram data provided in the file sinogram.mat, which contains projections from 180 angles. Our reconstruction will employ a Hammingwindowed Ramp filter for better image quality. (35 points)(a) Please implement the Basic global thresholding on flower.tif. (start with T = 0.1). (15 points) (b) Please implement the Region Splitting and Merging method on nebula.jpg to show the results of the minimum four-quadrant region size limit of 8*8 and 4*4 respectively. (15 points) (Hint: Region Splitting and Merging based on the characteristics of mean and standard deviation of gray level of pixels in an area. Since the background standard deviation of the image is close to 0, and the average gray level of the nebula is greater than the mean gray level of the dark background, we believe that: Q = T RUE, σ > a and 0 < m < b F ALSE, otherwiseFor this task, the value of a is set to 0.7, and the value of b is set to 170. For the result image, the area pixels that satisfy the attribute are set to white, and the other pixels are set to black.)Super pixel is a method that turns a pixel-level picture into district-level pictures, which is an abstraction of basic information elements. A super pixel is a small area composed of a series of adjacent pixels with similar characteristics such as color, brightness, and texture. Most of these small areas retain effective information for further image segmentation, and generally do not destroy the boundary information of objects in the image.In this problem, you need to turn seahouse.jpg to super pixel style using SLIC algorithm with cluster center 100, 500 and 1000 (In practice, number of cluster center can be different with these values, but should be close to these values) show the result images. (35 points) Reference, doi: 10.1109/TPAMI.2012.120.
(a) Apply the 3 × 3 Sobel kernels (x-direction and y-direction) on Figure 1.tif to sharpen the image. Since the Sobel kernels are separable, you should implement this by the combination of simple kernels. Show the Sobel kernels and the corresponding processed images. (Implement your own convolution operator.) (10 points)(b) Perform Gaussian Highpass filtering D0 = 100 on ’Figure 1.tif’ in the frequency domain. Show the Gaussian Highpass filter and the results (You can use fft2(), ifft2() and fftshift(), but not the built-in filtering function such as imfilter(), filter(), and filter2()). (15 points)Implement Homomorphic filtering on ’PET-scan.tif’ with the best paramters you think to improve the contrast of the subjet’s limbs. Show the Homomorphic filter and filtered results. The preferable condition is that the variance of pixel values within the white box exceeds 3 × 10−4 , when the image is normalized to 0–1. (20 points)Convert ’PeppersRGB.tif’ from RGB to HSI color space, and then convert it back. Show the image in HSI space and the recovered result in RGB space (Hint: you need to normalize all channels to [0,1] in HSI space).(20 points)In the process of image acquisition, the image blur caused by the relative movement between the acquisition device and target at the moment of exposure is called motion blur. In the spatial domain, the degenerate function model of motion blur can be expressed as: g(x, y) = h(x, y)⋆f(x, y) + n(x, y)Here, g(x, y) represents the output image, h(x, y) represents the degradation function, f(x, y) represents the input image, and n(x, y) represents the noise. The model in frequency domain can be expressed as: G(x, y) = H(x, y)F(x, y) + N(x, y)We can use PSF= fspecial(’motion’,L,theta) to simulate the convolution kernel h(x, y). Here, theta refers to the angle between the direction of motion and the horizontal direction, which is called the direction of motion blur. L refers to the distance the pixel moves in the direction of motion, which is called the motion blur distance.Restore the blurred.tif following: (a) Calculate the spectrum of the image, shift the zero frequency to the center of the spectrum. Display the spectrum logarithmically. You can use fft2().(5 points)(b) Estimate the parameters L and theta for blurred.tif (with a shape of N × N, N = 640). Motion blur will produce periodic bright and dark stripes in the spectrogram. As shown in the example picture, theta is the angle between the stripe and the vertical direction, d represents the distance between two similar dark stripes (the distance between the two dark stripes near the center is 2d), then L=N/d.You can use the Radon transform to estimate the angle theta, and then rotate it 180-theta degree counterclockwise. Vertical projection of the rotated spectrogram can be used to estimate L, L=N/d. Show the estimated parameters in your report. (15 points)(c) Implement Wiener filtering with the estimated parameters, and choose the best K you think. You can obtain H(u, v) through the psf2otf() function. (15 points)
Please complete all the coding assignments using MATLAB. Make sure your results in the report are the same as the results of your codes. For general operations, the following functions may be useful: load, imread, double, im2double, uint8, imshow, zeros, size, montage, subplot, bar.You must implement the core code in each question WITHOUT using relevant build-in functions, e.g, fspecial, imfilter, filter2, conv2, imsharpen, ordfilt2, hist, imadjust, histeq, adapthisteq, etc. You can type help FunctionName in Command Window of MATLAB for detailed help text for the functionality specified by FunctionName.(a) Compute the histogram of grain.tif and show the histogram image in your report. (Built-in functions hist and histogram are not allowed). (5 points)(b) Implement histogram equalization on grain.tif. Show the histogram equalized image and the histogram of equalized image in your report. (Built-in function histeq is not allowed). (10 points) (c) Implement contrast limited adaptive histogram equalization (CLAHE) on tire.tif, where you traverse every pixel with a 41 × 41 patch and process histogram equalization within each patch and update the center patch of 3 ×3. Each time you move the patch with a step of 1 pixel.The clip limit for CLAHE is 0.02, which means that after the normalization of the histogram, amplification above 0.02 should be clipped and evenly distributed to other parts of the histogram. Show the CLAHE processed images and corresponding histogram in your report. (Built-in function adapthisteq is not allowed) (20 points)(a) Apply the 3 × 3 Laplacian kernels (x-direction and y-direction) on moon.jpg to obtain the details of the image. Since the Laplacian kernels are separable, please separate them into combinations of 1-D kernels and then apply them to the image sequentially. Show the separated Laplacian kernels and the corresponding processed images. (Implement your own convolution operator.) (15 points)(b) Apply the 3 × 3 Laplacian kernels (not separated) to sharpen the image by 2-D convolution. Show the results in your report. (10 points) (c) Use unsharpen mask to sharpen the image. Show the results in your report. (10 points) The pixel intensity of the result images should be normalized to uint8 values within [0, 255].Apply the median filter and Gaussian filter to the image lena noisy.tif. In your report, Please show the images processed by the median filter and Gaussian filter respectively, and analyze the cause of the results. (Filtering operations cannot be implemented by calling functions, Hint: Choose the best kernel size you think, σ = 1) (30 points)
Problem 1: Consider an endlessly repeating sequence of keys, analogous to an infinite piano keyboard. This sequence follows a specific pattern that repeats indefinitely: wbwbwwbwbwbw. You need to determine if a continuous section of this sequence can be found which includes exactly W white keys (denoted by w) and B black keys (denoted by b).Constraints: • W: An integer such that 0 ≤ W ≤ 100 • B: An integer such that 0 ≤ B ≤ 100 • The sum of W and B must be at least 1 (W + B ≥ 1), ensuring that you are always looking for a non-empty segment. Input: The input is given from Standard Input in the following format: W BOutput: If there is a contiguous substring S containing exactly W ’w’ characters and B ’b’ characters, output Yes; otherwise, output No. Sample Input 1 3 2 Sample Output 1 Yes The first 15 characters of S are wbwbwwbwbwbwwbw. You can take the 11’th through 15’th characters to form the string bwwbw, which is a substring consisting of three occurrences of w and two occurrences of b. Sample Input 2 3 0 Sample Output 2 No The only string consisting of three occurrences of w and zero occurrences of b is www, which is not a substring of S. Sample Input 3 92 66 Sample Output 3 YesProblem 2: You are presented with two strings S and T, and a target string X of the same length as S, initially filled entirely with the character ‘#‘. Your task is to determine if it’s possible to transform X into S by repeatedly overlaying the string T onto X.Constraints: • The string S is composed of letters and has a length N. • The string T also consists of letters and has a length M, where M is less than or equal to N. • You can overlay T on any part of X, replacing M consecutive characters, as many times as you want. • Given lengths: 1 ≤ N ≤ 2 × 105 and 1 ≤ M ≤ min(N, 5).Input: The input is given from Standard Input in the following format: N M S T Output: Print Yes if it is possible to make X match S; print No otherwise. Sample Input 1 5 3 ABABC ABC Sample Output 1 YesBelow, let X[l : r] denote the part from the l’th through the r’th character of X. You can make X match S by operating as follows. 1. Replace X[3 : 5] with T. X becomes ‘##ABC‘. 2. Replace X[1 : 3] with T. X becomes ‘ABCBC‘. Sample Input 2 7 3 ABBCABC ABC Sample Output 2 No It’s impossible to make X match S. 3 Sample Input 3 12 2 XYXXYXXYYYXY XY Sample Output 3 YesProblem 3: You are given an n digit number f. Based on this number, you will generate a new n digit number g. Let gi denote the i’th digit of g. The generation rule is that g1 can be any digit from 0 to 9, and the subsequent digits gi , i > 1 are generated according to the following rule: gi ← fi + gi−1 2 or fi + gi−1 2 Note that based on a single number f, multiple different values of g can be generated.Input: The first line contains a nonempty sequence consisting of digits from 0 to 9, which is the number f. The sequence length does not exceed 50 .Output: Output the single number — the number of possible g’s which can be generated. Sample Input 1: 12345 Sample Output 1: 48 Sample Input 2: 09 Sample Output 2: 15Problem 4: You are organizing a conference, and need to choose the conference dates. The conference must span several consecutive days. Each day, one lecturer is needed to give a presentation, and each lecturer cannot give more than one presentation during the conference.There are n lecturers who can participate in the conference in total, the i’th of whom is available from day li to day ri , inclusive of li and ri . Several consecutive days can be chosen to hold the conference if there is a way to invite available lecturers to each of the days, without inviting lecturers more than once.For k from 1 to n, we want to find out how many ways there are to choose k consecutive days as the conference dates.Input: The first line of input contains one integer n, indicating the number of lecturers (1 ≤ n ≤ 1 × 104 ). Each of the next n lines contains two integers li and ri , indicating the i’th lecturer is available during these days (1 ≤ li ≤ ri ≤ 2 × 104 ).Output: Print n lines, where the k’th line contains one integer indicating the number of ways of selecting a conference of k days. Sample Input 1: 3 1 3 2 4 3 6 Sample Output 1: 6 4 3Explanation: k = 1: all the days 1 to 6 are valid, so there are 6 ways. k = 2: [1, 2], [2, 3], [3, 4], [4, 5] are valid, [5, 6] is not valid, so there are 4 ways. k = 3: [1, 3], [2, 4], [3, 5] are valid, 3 ways. Sample Input 2: 5 1 3 1 3 1 3 1 3 1 3 Sample Output 2: 3 2 1 0 0 Explanation:k = 1: days 1, 2, 3 are valid. k = 2: [1, 2], [2, 3], are valid, 2 ways. k = 3: [1, 3] is valid, 1 way. k = 4 or 5: There are no enough lecturers to invite, 0 ways.
Problem 1: Suppose you have 2n balls and 2 bins. For each ball, you throw it randomly into one of the bins. Let X1 and X2 denote the number of balls in the two bins after this process. Prove that for any ε > 0, there is a constant c > 0 such that the probability Pr [X1 − X2 > c√ n] ≤ ε.Problem 2: Suppose that for a certain decision problem, we have an algorithm which computes the correct answer with a probability at least 2/3 on any instance. We wish to reduce the error probability by running the algorithm n times on the same input, using independent randomness between trials, and taking the most common result as the final answer. Using Chernoff bounds, provide an upper bound on the probability that this modified algorithm produces an incorrect result.Problem 3: Suppose you have n coins, where the i’th coin has a size ci > 0, and many piggy banks, each with a uniform capacity V , such that V ≥ max(ci). You want to place all the coins into the minimum number of piggy banks. To do this you use the following greedy strategy. Start with one active piggy bank. Then, sequentially go through the coins, attempting to place each coin into any active piggy bank where it fits. If a coin does not fit into any active piggy bank, take a new piggy bank and make it active. The algorithm is shown below. Prove this algorithm is a 2-approximation, i.e. it uses at most two times the minimum number of piggy banks needed for all the coins.Algorithm 1 Piggy Bank Coin Packing 1: Input: Sizes of coins c1, c2, . . . , cn; size of piggy bank V 2: Output: Number of piggy banks used 3: Initialize b ← 1 ▷ current number of active piggy banks 4: Initialize P1, P2, . . . ← 0 ▷ space used in each piggy bank 5: for i = 1 to n do 6: if ∃j ≤ b such that Pj + ci ≤ V then 7: Choose any j with Pj + ci ≤ V 8: Pj ← Pj + ci ▷ put ci in j-th active piggy bank 9: else 10: b ← b + 1 11: Pb ← ci ▷ open a new piggy bank and put ci in it 12: end if 13: end forProblem 4: Consider an n × n grid graph G, as shown below. Each node v in G has a weight w(v) > 0. You want to choose an independent set of nodes with maximum total weight. That is, you want to choose a set of nodes S with maximum total weight such that for any v ∈ S, none of v’s neighbors are in S.To do this, consider the following greedy algorithm. Let V be the set of all nodes in G. Choose the node in V with the largest weight (breaking ties arbitrarily), add it to the independent set, then remove the node and all its neighbors from V . Repeat this process until V is empty. Let S be the output of this algorithm. Solve the following problems.1. Let T be any independent set in G. Show that for each node v ∈ T, either v ∈ S, or there is a neighbor v ′ of v with v ′ ∈ S and w(v) ≤ w(v ′ ). 2. Show that the greedy algorithm is a 4-approximation.
Problem 1: Given a set C, a collection of subsets of C and an integer k ≥ 1, the Set-Packing problem asks if there are k subsets from the collection which are pairwise disjoint (i.e. no two sets share an element). Show that the Set-Packing problem is NPcomplete.Problem 2: Given a Boolean CNF (conjunctive normal form) formula ϕ and an integer k ≥ 1, the Stingy-SAT problem asks whether the formula has a satisfying assignment in which at most k variables are set to true. Prove that Stingy-SAT is NPcomplete.Problem 3: Given a set C, a collection of subsets of C and an integer k ≥ 1, the Set-Cover problem asks whether there are at most k subsets from the collection which cover C, i.e. whose union includes all of C. Show that Set-Cover is NP-complete. Do not use a reduction from a problem which is very similar to Set-Cover.Problem 4: Consider a list with n unique positive integers, and suppose we iterate through the numbers one by one in a random order. As we do this, we maintain a variable b equal to the largest number we have seen so far. Initially b is set to 0. Compute the expected number of times b is updated.For example, if the input list is [4, 7, 5], and we iterate through the list in the order 3, 1, 2, then b is updated twice, when we see 5 and 7.
Problem 1: Given a network G(V, E, s, t), give a polynomial time algorithm to determine whether G has a unique minimum s − t cut.Problem 2: We are given an n × m array of cells. Denote the cell in the r’th row and the c’th column as (r, c), where 1 ≤ r ≤ n and 1 ≤ c ≤ m. A robot is at cell (1, 1) and wants to reach cell (n, m). From cell (x, y), the robot can only move to (x, y + 1) or (x + 1, y). In addition, some cells contain impassable obstacles and the robot cannot move to these cells. Your goal is to put additional obstacles in the minimum number of cells (other than cell (n, m)) such that the robot cannot reach (n, m). Find an algorithm based on max flow.Problem 3: Consider a restaurant with m different menu items. Each customer to the restaurant want to order one item, and each of them has a set of items they are willing to order from. The restaurant makes di amount of item i, for 1 ≤ i ≤ m, so that at most di customers can order item i. Given n customers, where the j’th customer has a list Cj of items they are willing to order, design an efficient algorithm to maximize the number of customers you can serve.Problem 4: Consider an n × n grid containing n rows and n columns of vertices. Each vertex (i, j) has edges to four neighbors (i − 1, j), (i + 1, j), (i, j − 1), (i, j + 1), except for the boundary vertices, which have edges to two or three neighbors.Each vertex and edge also has a positive integer capacity. We are given m start vertices, and for each vertex we want to find a path which connects the vertex to an arbitrary vertex on the grid’s boundary. Furthermore, we need to ensure that the number of paths which pass through each vertex or edge does not exceed its capacity. Give an algorithm to determine whether this is possible. Hint: First transform the graph to convert the vertex capacities to edge capacities.Problem 5: Given a set C, a collection D of subsets of C, and a value k, the k-SETPACKING problem asks if there exist k subsets from D which are mutually disjoint, i.e. no two of the subsets share an element. Show that the SETPACKING problem is in NP.Problem 6: Consider the following problem about scheduling courses. The problem is defined by 3 sets C, S and R. Here, C represents a set of courses, S repreesents the available time slots for the courses, and R contains a collection of course requests from students, where each request is a subset of C representing the the courses that a particular student wishes to take. The goal is to schedule all the courses without any conflicts.For example, if C = {a, b, c, d}, S = {1, 2, 3}, R = {{a, b, c}, {a, b, d}, {b, d}}, then it is possible to schedule the courses without conflicts by assigning course a to time slot 1, b to slot 2 and c, d to slot 3. However, if C = {a, b, c, d}, S = {1, 2, 3}, R = {{a, b, c}, {a, c}, {b, c, d}}, then it is not possible to schedule the courses without any conflicts. Prove that the problem of determining whether a conflict-free schedule exists is NP-complete. Hint: Use a reduction from the 3-COLOR problem.
Problem 1: Suppose you are given a set of intervals I1 = [s1, t1], . . . , In = [sn, tn], which can possibly overlap. Your task is to select a set of points p1, . . . , pm so that each interval intersects at least one of the points. Give an algorithm to minimize the number of selected points m, and prove that your algorithm is optimal.Problem 2: Suppose you need to perform n tasks, and you can only perform one task at a time. It takes ti time to perform the i’th task, and the task has an importance of wi > 0. Let Ci be the completion time of the i’th task, i.e. the time when you finish performing the task.Find an ordering of the tasks to minimize their weighted completion time, defined as ∑n i=1 wiCi . Your algorithm should work in O(n log n) time, and you need to analyze the algorithm’s time complexity and prove its correctness.Problem 3: A thief is planning to rob houses along a street. Each house has a certain amount of money stashed, and the thief can rob any set of houses, as long as he does not rob any adjacent houses. Determine the maximum amount of money the thief can steal.Problem 4: Given three sequences L1, L2 and L, design an efficient algorithm to check if L1 and L2 can be interleaved to produce L. For example, the sequences L1 = aabb and L2 = cba can be interleaved into sequence L = acabbab, but L1 and L2 cannot be interleaved into sequence L = aaabbbc. Analyze the time and space complexity of your algorithm as a function of the lengths of L1 and L2.Problem 5: Suppose you are given a propositional logic formula containing only the terms ∧, ∨, T and F, without any parentheses. You want to find out how many different ways there are to correctly parenthesize the formula so that the resulting formula evaluates to true.For example, the formula T ∨ F ∨ T ∨ F can be correctly parenthesized in 5 ways: (T ∨ (F ∨ (T ∨ F))) (T ∨ ((F ∨ T) ∨ F)) ((T ∨ F) ∨ (T ∨ F)) (((T ∨ F) ∨ T) ∨ F) ((T ∨ (F ∨ T)) ∨ F) Of these, 3 evaluate to true: ((T ∨ F) ∨ (T ∨ F)), (T ∨ ((F ∨ T) ∨ F)) and (T ∨ (F ∨ (T ∨ F))).Give a dynamic programming algorithm to solve this problem. Describe your algorithm, including a clear statement of your dynamic programming equation, show that it is correct, and prove its running time.Problem 6: Consider a weighted directed graph G with n vertices and m edges, where each edge (i, j) has a positive integer weight wi,j . A walk is a sequence of not necessarily distinct vertices v1, v2, …, vk, such that any two consecutive vertices vi , vi+1 are connected by an edge.The length of the walk is the sum of the weights of the edges in the walk. Design an algorithm to find the number of different walks from a vertex s to another vertex t which have length exactly L, and analyze the time complexity of your algorithm.
