CSci 4511 - Homework 1

Homework 1 -- due Thursday February 7

This homework will be graded out of 100 points. It will count 6% of the grade.
Submit the assignment electronically using canvas. The written part has to be uploaded as a .pdf file. This makes it easy for us to mark the homework.
For the programming part you will need to upload the code you wrote and the output produced.

Written questions

  1. [15 points] Answer the following questions briefly but precisely:
  2. [25 points] You are given the following problem: Given a 7-gallon jug filled with water and an empty 3-gallon jug can you have precisely 5 gallons of water in the 7-gallon jug? Assume you can fill the jugs with water as many times as desired, but you cannot measure how much water is in each jug. When you move water out of a jug you can either fill up the other jug or dump the water.
    You are to formulate the problem using a state-space search representation. Describe (precisely):
    1. what is the initial state
    2. the goal test
    3. the actions. Write the actions as rules, specifying applicability conditions and resulting state. For instance, if a state is a pair (x,y) of the amount of water in the 7-gallon jug and the amount in the 3-gallon jug, here are a couple of actions:
      Fill the 7-gallon jug: if (0, y) then (7, y)
      Move 3 gallons from 7-gallon to 3-gallon jug: if (x, 0) and x>3 then (x-3, 3)
    4. is the state-space a tree or a graph?
    5. show graphically the state space explored and the solution you found (there might be more than one solution).
  3. [20 points] You are given an instance of the traveling salesperson problem (TSP). A salesperson has to visit a group of cities, visiting each only once and getting back to the starting city. Assume each city is directly connected to each other city. The objective is to minimize the total distance traveled.
  4. [20 points] This question is on properties of search algorithms. Consider the following algorithms: You need to explain the reasons for your answers, not simply write the name of one algorithm.
    1. if you want to limit the memory requirements, which algorithm(s) would you choose? why?
    2. if you want to limit the time required the find a solution, which algorithm(s) would you choose? why?
    3. if you want to find the minimum cost solution, which algorithm(s) would you choose? why?
    4. if you want to solution with the minimum number of steps, but you do not want to use a lot of memory, which algorithm(s) would you choose? why?

Programming Part

  1. [10 points] Download and install the AIMA book code from https://github.com/aimacode. Once done, submit the file that shows all test were run successfully.
    To show the output of your program, if you start the program from the command line in linux you can save the output into a file (let's call it output.txt) using the command
     % script > output.txt 

    If you use windows or do not use the command line, submit a screen dump that shows the output of the vacuum cleaning agent.

    The AIMA code is written for different programming languages. The ones we will use are lisp https://github.com/aimacode/aima-lisp or python https://github.com/aimacode/aima-python.

    Details on using the python software

    Details on using the Lisp software

  2. [5 points] Use the code to run the reflex vacuum agent.
  3. [5 points] Use the code to run the random vacuum agent.
    Copyright: © 2019 by the Regents of the University of Minnesota
    Department of Computer Science and Engineering. All rights reserved.
    Comments to: Maria Gini
    Changes and corrections are in red.