Homework 1 -- due Tuesday February 5

1. [60 points] Answer the following questions from Russell's textbook:
   1. [15 points] Chapter 2, question 2.5;
   2. [15 points] Chapter 2, question 2.6.
   3. [15 points] Chapter 3, question 3.7.
   4. [15 points] Chapter 3, question 3.9 part a.

2. [30 points] Answer the following Lisp questions.
   To answer them you need to read Chapter 2 of Graham's book or Lamkins's book Chapter 3, Lesson 1 to 7. If you know Scheme, look at the class notes on Differences between Lisp and Scheme.
   You can find information on Lisp and how to use it on the ITLabs machines. Look in particular at ways for capturing output from Lisp.
   Test your functions with the computer and submit both the functions and results on test cases using the IT Labs Submit Tool.
   1. [10 points] Write a function to return a list containing the integers from min to max (extremes included). Assume that min and max are different, and that min is less than max. It should work like this:
      (enumerate -1 6) = (-1 0 1 2 3 4 5 6)
(enumerate 0 5) = (0 1 2 3 4 5)
(enumerate 1 2) = (1 2)
   2. [10 points] Write a function to remove (without modifying the list) the FIRST occurrence of a given element from a flat list. If the element is not in the list, the original list will be returned. The element can be either an atom or a number.
      It should work like this:
      (remv 3 '(2 4 6 -3 3 8 6 3)) == (2 4 6 -3 8 6 3)
(remv 3 '(2 4 6 -3 8 6 5)) == (2 4 6 -3 8 6 5)
(remv 'a '(c a b a)) == (c b a)
(remv 'a '(c b)) == (c b)
(remv 3 '()) == ()
      
   3. [10 points] Write a function to remove (without modifying the list) ALL the occurrences of a given element from a flat list. If the element is not in the list, the original list will be returned. The element can be either an atom or a number. Try to write this as an iterative function, using either the function do or dolist.
      It should work like this:
      (remvall 3 '(2 4 6 -3 3 8 6 3)) == (2 4 6 -3 8 6)
(remvall 3 '(2 4 6 3 3 8 6)) == (2 4 6 8 6)
(remvall 'a '(c a b a)) == (c b)
(remvall 'a '(c b)) == (c b)
(remvall 3 '(2 4 6 -3 8 6 5)) == (2 4 6 -3 8 6 5)
(remvall 3 '()) == ()
      
3. [10 points] [Graduate Students only] Graduate students have to answer this question (part of an old WPE question). Undergraduate students do not need to answer this question. They will get credit (10 points) for it without having to do any work. However, undergraduates are welcome to answer this question, which will count as some extra credit (precise amount to be decided).
   1. Consider the "N-Frog Puzzle" consisting of N frogs numbered 1 through N, and an empty space (E) arranged in a linear array. Initially frogs are arranged in an ascending order form left to right, with the empty space (E) occupying the leftmost position in the array. The goal is to have all the frogs arranged in a descending order. The exact location of the empty space does not matter in the final solution.
      The puzzle has two legal moves. A frog may move to the next square (if vacant) or leap over one frog to the next square beyond (if vacant) just as we move in the game of Droughts. Frogs can go forward or backward at pleasure. Cost of a solution is measured by the number of moves. For example, a solution path for the 3-Frog puzzle is
      E123 -> 21E3 -> 2E13 -> 231E -> 23E1 -> E321
      with a cost of 5 units.

      Specify the N-Frog-puzzle (not its solution!) by answering the following questions. Justify your answers briefly.

      1. Describe the general N-Frog-puzzle as a search space problem. Provide a simple representation for the states and characterize the following set of states using your representation: start state, goal states, error states.
      2. Analyze the state space with respect to complexity (i.e number of states) and looping.
   Copyright: © 2008 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.