CS 360: Introduction to Artificial Intelligence

Find the sequence of cars and cdrs that return x when applied to the following expressions:

1. (a b x d)

   (car (cdr (cdr '(a b x d))))

2. (a (b (x d)))

   (car (car (cdr (car (cdr '(a (b (x d))))))))

What is the difference between the following s-expressions:

1. (car (setq '(a b c)))

   Attempts to use '(a b c) as the name of a value to assign to and fails.

2. (car '(setq '(a b c)))

   Returns setq as the front of a list consisting of the string setq and the quoted list '(a b c).

Suppose you executed the following set of commands:

(car (setq x '(a b c)))
x (1)
(setq x nil)
(car '(setq x '(a b c)))
x (2)

What value of x would appear on the screen after:

1. (1)?

   (a b c)

2. (2)?

   nil

Assign to the symbol x the list '(a b c). Use this to create the list '(a b c a b c).

(setq x '(a b c)) (append x x)

Write a function that replaces the first element of a list, i.e., (replace-first x y), replaces the first element of list y with the value of x.

(defun replace-first (x y) (append (list x) (cdr y)))

Write a recursive function power-of-two that computes the nth power of 2; e.g. (power-of-two 8) returns 256.

(defun power-of-two (n)
 (cond ((= n 0) 1)
       ((> n 0) (* 2 (power-of-two (1- n))))
       ((< n 0) (/ 1.0 (power-of-two (- n))))))

Write a non-recursive form of the same function, i.e., one that uses iterative constructs instead of recursion.

(defun power-of-two (n)
 (do ((x 1 (+ x 1)) (sum 1))
     ((> x (abs n)) (cond ((< n 0) (/ 1.0 sum))
                           (t sum)))
     (setq sum (* 2 sum))))

Write a recursive function count-atoms that counts the number of atoms that appear at all levels of an s-expression. For example:

• (count-atoms '(a (b c) (d (e) f))) = 6
• (count-atoms 1) = 1
• (count-atoms nil) = (count-atoms ()) = (count-atoms '(())) = 0
• (count-atoms '(1 2 (3 nil) () 4 5 ((nil 9) 10 a) r)) = 9

(defun count-atoms (list)
 (let ((count 0))
      (cond ((listp list) (dolist (x list) (setq count (+ count (count-atoms x)))))
            (t (setq count 1)))
      count))

Given a map represented as a property list, write functions that, given a start-node and a goal-node, implement:

• depth-first search

  (defun depth-first-search (start-node goal-node)
    (let ((searched-nodes ()))
      (defun dfs-impl (current-node)
        ;(print (format "searching for ~S~ from ~S~ (~D~)" goal-node current-node (length searched-nodes)))
        (cond ((eq current-node goal-node) (list current-node))
              (t (setq searched-nodes (cons current-node searched-nodes))
                 (let ((path nil))
                   (dolist (node (get current-node 'adjdst))
                     (cond ((not (member node searched-nodes))
                            (block recurse
                                   (setq path (dfs-impl node))
                                   (if (not (eq path nil)) (return (cons current-node path)))))))))))
      (dfs-impl start-node)))

• breadth-first search

  (defun breadth-first-search (start-node goal-node)
    (let ((searched-nodes ())
          (node-queue (list start-node)))
      (loop (when (or (endp node-queue) (eq goal-node (car node-queue))) (return))
            (let ((current-node (car node-queue))
                  (children (get (car node-queue) 'adjdst)))
              (let ((new-children (set-difference children (append searched-nodes node-queue))))
                (dolist (node new-children) (setf (get node 'parent) current-node))
                (setq searched-nodes (append searched-nodes (list current-node)))
                (setq node-queue (append (cdr node-queue) new-children))
                ;(format t "  Searching for ~S from ~S (~D) ~S~%" goal-node current-node (length searched-nodes) node-queue)
                )))
      (defun getpath (node)
        (cond ((null node) nil)
              (t (append (getpath (get node 'parent)) (list node)))))
      (cond ((endp node-queue) nil)
            (t (getpath (car node-queue))))))