| Date: 12/12 | Title: Program 3: Deadline extension and tips |
Due to popular demand, I am extending the deadline for program 3 to
12/14 Tue 5pm. The odd timing is to allow you time to study for
the final on the next morning. I cannot extended it any further because
of early grades that I need to submit (for graduating students).
You will get 100% if you submit by the new deadline (i.e., no penalty).
For those who may have been working hard to meet tonight's deadline,
you may keep on working. Submit by 11:59:59pm tonight for a 7% extra credit.
Also, here's an answer to a repeated question about solveability of
the different theorems: "O" means solveable, "X" means unsolveable,
"(n)" means the index of the last clause generated, and "begin neg
concl" means the begining of the negated conclusion.
Note that I may have incorrectly said "6" for the customs case.
two-pointer linear unit-pref begin
neg
concl
howling O (53) O (16) O (19) 6
customs O (95) O (14) O (18) 7
rr O (201) O (19) O (22) 6
harmonia O (29) X (11) O (13) 7
So, if your algorithm is failing for some reason for some but working
for some, try changing your "begin neg concl" argument. Also, track
back from the end and see if there's anything wrong.
BTW, the number of steps taken may vary across implementations, so
you do not have to worry if your result is exactly the same.
If you run out of time and if your method works for some but does not
for some others, make a note of that and explain why you think
your method did not work for that particular case. You will get
(a generous) partial credit if you do so.
|
| Date: 12/03 | Title: Program 3: Tips on (unify ...) |
| There seems to be some confusion about what (unify ...) returns and
how to use that to substitute variables with their matching terms
returned by unify.
Here's a brief view of what (unify ...) returns, which is basically
a list of ALISTs.
When you unify P(x) and P(y), you should get {x/y}. You put this in
a list and that's what (unify ...) returns:
* (unify '(p x) '(p y))
((X . Y))
So, the result is a list that contains (X . Y), which is an ALIST, an
association list. When you use (subst ...) or (sublis ...), all occurrences
of 'x will be replaced by 'y. Note that ALIST can be constructed by using
(cons ...), and also note the oddity here, that the second argument 'y is
not a list but a symbol.
* (cons 'x 'y)
(X . Y)
Now consider what happens when you unifyr P(x) and P(A) where A is a constant.
*(unify '(p x) '(p (a)))
((X A))
What you get is, puzzlingly an ALIST (X A). But what does that mean? Where
did the period in the middle go, and further, why did (A) now become a
symbol A? In fact, (X A) is equivalent to (X . (A)), so the period and
the list surrounding A did not go anywhere. It is just that when Lisp
is asked to print it on the screen, it prints the shorter version:
* '(X . (A))
(X A)
* (cons 'x '(a))
(X A)
See slide04.pdf, page 108 and 109 to learn how to use the returned
substitutions with sublis.
|
| Date: 11/10 | Title: Program 3: Some programming tips |
For this assignment, you may want to do at least these two
things to prevent your program from blowing up:
- Check if the resolvent clause you just generated
is already in the list of clauses.
- Compare the positive literal list and the
negative literal list separately:
For these two clauses,
(setq x '(1 ( (P X) (Q (A)) ) ( (R X) ) ))
(setq y '(2 ( (P X) ) ( (R (A)) ) ))
compare (second x) and (second y); and (third x)
and (third y).
- First, compare the length of the literal lists,
and if they are different, treat them as
distinct.
- Next, check if there are any discrepancy
in the list of predicates. See the
fol-dupe-check.lsp file in the src directory.
The goal here is to detect clauses that are
definitely different.
So, P(x) and P(Socrates) may pass as "not being
different."
That'll be okay for dupe check, because
eliminating just the obviously different
ones would be good enough.
- Check if your resolvent clause contains any repeated
Literals.
This can be done easily using the (member ...)
function. See the fol-dupe-check.lsp file.
|
| Date: 10/19 | Title: Program 2: Q-and-A's |
Q1: How do I pass the heuristic function as a parameter and get it called?
A1: The simplest is to simply use a (if ...) function:
(defun blah (state heuristic)
...
(if (equal heuristic 'h1)
(setq h (h1 state))
(setq h (h2 state))
)
...
)
or, use (cond ...) if you prefer. Use the above if (eval ...) does not
work.
Q2: How do I calculate the manhattan distance?
A2:
First, calculate the current (x,y) coordinate: x1,y1.
Then, calculate the target position's (x,y) coordinate: x2,y2.
The manhattan distance is:
abs(x2-x1) + abs(y2-y1).
Q3: Why does appy-op add the path to the current node in reverse
order?
A3: For efficiency. You can (reverse ...) the path after you get
the result.
Q4: Help! IDS does not return the solution and loops infinitely!
A4: You must use
(return-from )
once your dls call returned a goal, to break out of the infinite loop;
or terminate the while loop on that condition.
Q5: Do I need to implment both h1 and h2?
A5: Yes, you need to implement both and test both.
Q6: In the file eight-interface.lsp, hill-climbing misspelled.
A6: Please fix the typo and submit the correctly spelled one.
Q7: For A* and IDA*, shouldn't we pass f(n) instead of h(n)?
A7: No, only h(n) is the needed information at the time you call it,
because the g(n) part in f(n)=g(n)+h(n) is something that you cannot
give a functional form in the beginning (at least very easily that is).
Once you're in the routine, you can do (+ (second node) (third node))
to calculate the f value.
Q8: Should hill-climbing (or rather, heuristic search) use f(n)?
A8: No, hill-climbing should use just h(n). Adding g(n) does not
help since you only have one current state to expand from, which
has just one g(n) value.
Q9: What is the solution depth of the three example cases?
A9: Easy: 5
Medium: 9
Hard: 30.
Q10: My search never ends! I've been running it for 30 minutes and
it's not getting anywhere.
A10: Try printing the current depth of the exploration, and other info.
That will give you a clue as to how far you are in the search. Of course,
for DFS, this wouldn't help.
Q11: Help! My search quickly returns NIL without doing much search!
A11: Check if your dupe check is working properly. Turn off dupe check,
and then see if you're getting anything. Once you confirm that, you know
there's a problem with your dupe check call.
In hill-climibing (heuristic search), you may not want to do any dupe
check, because if you do, you will reach a dead-end pretty soon.
In IDS (and for that matter, IDA*), if you don't clear you dupe
list regularly, your subsequent searchs will return NIL very quickly,
ao after each loop, clear out the dupe list.
Q12: Should I check for dupe on the expanded nodes?
A12: No, it would be better to do that on the node just taken out of
the node-list.
|
| Date: 9/28 | Title: Homework 1: Q-and-A's |
Homework 1 Q-and-A's:
[Q1] On section 2, the search tree has arrows from one node to another, does
that mean that the search, when it expands a node, will only get those
that have an arrow from it, to them? For example, if a search expands
node b, will it only find node d or will it find nodes d and A?
[A1] The arrow tells you the parent-child relationship. A parent can only
expand into its child(ren). So, when expanding b in (A)-->(b)-->(d),
the outcome should only be (d), and not (A).
[Q2] I have a question on question1 of Uninformed Search. What does the
identical time complexity mean? If one search visits n-1 nodes to find
the goal, and the other search visits n-2 nodes to find the goal, are
those time complexity same? They can be same Since they both mean O(n)
time complexity.
[A2] Here, do not use the big-O notation. All calculations should be exact,
so, n-1 != n. I.e., calculate the exact number of nodes visited.[Added 9/28 9:45pm]
[Q3] For Questions 1,2,4 , is it enough if we just give the answer or do we
have to explain them also?
[A3] If you're sure about your answer, you don't need any explanation.
If you're not sure, and want partial credit (which will be limited),
explain.
[Q4] Question 2: I can't figure out which f(n) you are asking. Like for
hill-climbing it will just be h(n). But for greedy , we will have to
add g(n) also.
[A4] Here I am assuming f(n) = g(n) + h(n). For greedy, just use h(n) as the
evaluation function. For A*, use f(n) as the evaluation function.
For hill-climbing, use h(n).
[Q5] "For each cut that happens, draw a line to cross out the subtree."
Does this just mean , when we prune certain child nodes, draw a line
through them or does it involve some cutoff test etc.
[A5] Just indicate where the cut should happen. Sometimes, whole subtrees
can be eliminated. In that case, just show where the whole subtree
is hanging from:
\
o
/ \ cut
/ /
/ \
o o
/ \ / \
[Q6] Is the root at depth 0 or depth 1?
[A6] Depth means "how many steps have you come from the root to reach
the current node", so the root is at depth 0, and its immediate
child(ren) at depth 1.
[Q7] For section 1, question 1, the answer seems to depend
on the choice of m, n, and b. What should I say here?
[A7] Use these numbers: b=10, m=5, n=7, and k=4.
Ignore the condition n > 2b. [Added: 9/28 9:45pm]
[Q8] What is optimal? Is is the same as time complexity?
[A8] No, optimal here only is related to the depth of the goal that
was found. If the goal you found is at depth 10, but if there was
another goal at depth 3, then your solution is non-optimal.
|
| Date: 9/19 | Title: Prog 1: Q-and-A's |
Here are some Q&As for program 1.
Q1: If I want to compose a lisp function call to be passed to
(eval ...), but if I need certain variables to be evaluated
first, what can I do?
A1: If you know what you want to evaluate, it is simple:
(eval '(my-func arg1 arg2))
but, if you need arg1 and arg2 evaluated first, use (list ...):
(eval (list 'my-func arg1 arg2))
Q2: Should I worry about divide-by-zero error in deriv-eval?
A2: No, you don't need to do that check.
Q3: In the slide, one of the examples give 1/25 as the answer. Shouldn't
it be -1/25?
(deriv-eval '(/ (+ x 1) x) 'x 5)
-> 1/25
A3: Yes, -1/25 is correct.
(deriv-eval '(/ (+ x 1) x) 'x 5)
-> -1/25
Q4: What is the rule for unary minus, and how do I simplify it?
A4: The rule is
d(-f)/dx = -df/dx.
As for the simplification (- (- x)) should be simplified to x,
whatever x is (list, symbol, or number. Other cases are when
you have (- n) where n is a number. In that case, you need
to return -n (which can be accomplished by (- n)).
Q5: How far should I go in terms of simplification?
A5: You just need to do the most basic stuff. If you notice some cases
that did not simplify in your example expressions, analyze it and
explain why it did not simplify.
Q6: Can you give me some example cases and answers?
A6: Here are some random examples, but these are not comprehensive, and
your simplification results may vary.
*(deriv '(- x 10) 'x)
1
value: 1
*(deriv '(+ (* x (/ 10 x)) (/ 1 x)) 'x)
(+ (+ (* X (/ -10 (* X X))) (/ 10 X)) (/ -1 (* X X)))
value: -1/100
*(deriv '(+ (+ (* x x) (* (* x x) x)) (* 10 x)) 'x)
(+ (+ (+ X X) (+ (* X X) (* X (+ X X)))) 10)
value: 330
*(deriv '(+ 5 (* x x)) 'x)
(+ X X)
value: 20
*(deriv '(- (* x x) 5) 'x)
(+ X X)
value: 20
*(deriv '(* (/ x 3) (+ 4 x)) 'x)
(+ (/ X 3) (* 1/3 (+ 4 X)))
value: 8
*(deriv '(- (* (- x 10) x)) 'x)
(- (+ (- X 10) X))
value: -10
*(deriv '(- (- x)) 'x)
1
value: 1
*(deriv '(- (- (* x x))) 'x)
(+ X X)
value: 20
Q7: Where was that web page with the differentiation rules?
A7: http://www.cs.utexas.edu/users/novak/asg-symdif.html
|
| Date: 9/10 | Title: Prog 1: note on simplification |
Question
Some of my results never get simplified even though
it works most of the case. What's wrong?
Answer
Most likely, your input expression itself contains some of the
reducable expressions such as (+ 0 x) or (/ 0 x).
If this is part of a multiplication, then the problem might occur.
This is because unless (deriv ...) is called, recursively on
that expression, (splus ...) etc. will never be called.
For example, consider the following expression:
(deriv '(* (+ 0 x) (+ x x)) 'x)
This is just
(+ (* (deriv '(+ 0 x) 'x) '(+ x x))
(* '(+ 0 x) 'x) (deriv '(+ x x) 'x))
)
so the bold part will not go through (splus ...).
To avoid this, you may assume that all input expressions are
maximally simplified. In the case above, the input should have been
(deriv '(* x (+ x x)) 'x) .
|
| Date: 9/09 | Title: Lisp: compiling |
To optimize and speed up execution, you should compile your program
code. You can do this in CMUCL by running the (compile-file
<filename>) function. See below for an example, where I am
compiling function(s) in the file fibo.l. The file contained the
definition for the (fibo ..) function. Of course you can have multiple
function definitions in the file, and all of those will be compiled.
Again, * is the
lisp prompt, and my inputs to lisp are in bold.
* (compile-file "fibo.l")
; Python version 1.1, VM version UltraSparc/Solaris 7 on 09 SEP 04 10:49:52 am.
; Compiling: /user/choe/web_project/625/fibo.l 09 SEP 04 10:44:02 am
; Converted FIBO.
; Compiling DEFUN FIBO:
; Byte Compiling Top-Level Form:
; fibo.sparcf written.
; Compilation finished in 0:00:00.
#p"/user/choe/web_project/625/fibo.sparcf"
NIL
NIL
* (load "fibo.sparcf")
; Loading #p"/user/choe/web_project/625/fibo.sparcf".
T
* (fibo 20)
10946
*
Note that you need to first compile it, and the note what the resulting
compiled file is (the one highlighted in red above),
and then finally (load ...) that.
|
| Date: 8/31 | Title: Lisp: tracing function calls |
Here's an example of how you should use (trace ...) to track
the function calls and the return values. It becomes very handy when
you're debugging recursive functions.
CMU Common Lisp CVS Head 2003-07-01 16:23:01, running on unix
With core: /usr/local/lib/cmucl/lib/lisp.core
Dumped on: Tue, 2003-07-01 16:01:00-05:00 on empic5
See for support information.
Loaded subsystems:
Python 1.1, target UltraSparc/Solaris 7
CLOS based on Gerd's PCL 2003/06/18 09:23:09
* (load "deriv.lsp")
; Loading #p"/user/choe/web_project/420/deriv.lsp".
T
* (trace deriv) <--- Trace calls to deriv
;
; Warning: This function is undefined:
; DERIVMULT
;
(DERIV)
* (trace derivplus) <--- Trace calls to derivplus
(DERIVPLUS)
* (trace splus) <--- Trace calls to splus
(SPLUS)
* (deriv '(+ (+ x 2) (+ 2 x)) 'x) <---- Call deriv!
0: (DERIV (+ (+ X 2) (+ 2 X)) X) <---- shows how the functions are
1: (DERIVPLUS (+ (+ X 2) (+ 2 X)) X) called, with their full
1: DERIVPLUS returned (+ (+ 1 0) (+ 0 1)) arguments! You can easily
0: DERIV returned (+ (+ 1 0) (+ 0 1)) track what's going wrong
(+ (+ 1 0) (+ 0 1)) by looking at the arguments
* (quit) and the returned values.
|
| Date: 8/31 | Title: Downloading skeleton files |
To download the skeleton file, follow the procedure below (unix$ is
the unix prompt; you type in the commands in bold).
- Create a subdirectory where you will put your programs:
unix$ mkdir 625-prog1
unix$ cd 625-prog1
- Download the file using lynx, a text web browser (NOTE: this command will OVERWRITE deriv.lsp, if that file
already exists, so be careful):
unix$ lynx -source http://courses.cs.tamu.edu/choe/04fall/src/deriv-skel.lsp > deriv.lsp
- Run lisp, and load deriv.lsp:
unix$ lisp
...
* (load "deriv.lsp")
...
* (deriv '(+ x (+ x 2)) 'x)
...
*
|
| Date: 8/31 | Title: Lisp: coping with file load errors |
| When you write a lisp program file and (load "filename.lsp"),
sometimes it will cause an error message. This happens most likely
when you miss one or more parentheses.
First, read the message, and try to figure out which function caused
the error. If you cannot find out, you can start copy-and-pasting
each function into an interactive lisp session:
+-----------Editor-----------+ +---------Lisp-------------+
| | | |
| | |* (defun ... |
|; my square |\ | |
|(defun mysquare (x) | }----> |... |
| (* x x)) |/ | |
| | | |
| | |MYSQUARE |
| | | |
| | |* |
| | | |
+-----------Editor-----------+ +---------Lisp-------------+
If lisp does not echo back your function name (e.g., MYSQUARE above),
then you know there's an error in that function.
In editors like emacs or vi, you can match the parentheses:
- In emacs, use
M-x lisp-mode where M-x means [Alt]-[x].
Typing the matching pair at the end will automatically
bring you to the beginning one and back to the last one
you just typed.
- In vi, press on %
on
one parenthesis to go back and forth between the matching parenthesis.
|
| Date: 8/30 | Title: Lisp: writing program files and loading |
| [Q] How do I view the listing of my code in the lisp shell (or listner,
in technical terms) and edit it?
[A] You don't edit it in the lisp shell -- you write a program file
containing the function definitions, and use (load "filename") to
load it, and test it.
File: test.lsp
(defun mysqr (x)
(* x x)
)
Save that in a file, and run lisp, and there type ('*' is the lisp prompt):
* (load "test.lsp")
Then, type in:
* (mysqr 10)
If there was a bug in your program, edit it, and reload it using
* (load "test.lsp")
and test again by running
* (mysqr 10)
|
| Date: 8/30 | Title: Lisp exercise |
Here's an example which will help you get started wetting your
hands in Lisp. The commands in Bold are what you're supposed
to type in. My comments are in Italics - YC.
- CMU Common Lisp is installed in /usr/local/bin/lisp:
Example:
unix$ /usr/local/bin/lisp <-- 'unix$' is the unix prompt
CMU Common Lisp CVS Head 2003-04-21 16:23:29, running on unix
With core: /usr/local/lib/cmucl/lib/lisp.core
Dumped on: Mon, 2003-04-21 15:40:49-05:00 on empic5
See for support information.
Loaded subsystems:
Python 1.1, target SPARCstation/Solaris 2
CLOS based on Gerd's PCL 2003/03/22 16:15:17
* <-- '*' is the lisp prompt
- To quit from lisp, enter (quit)
Example:
CMU Common Lisp CVS Head 2003-04-21 16:23:29, running on unix
With core: /usr/local/lib/cmucl/lib/lisp.core
Dumped on: Mon, 2003-04-21 15:40:49-05:00 on empic5
See for support information.
Loaded subsystems:
Python 1.1, target SPARCstation/Solaris 2
CLOS based on Gerd's PCL 2003/03/22 16:15:17
* (quit) <-- your input
unix$ <-- the unix prompt
- If you caused an error and it doesn't seem to work, enter
q to go back up to the top-level.
Example:
CMU Common Lisp CVS Head 2003-04-21 16:23:29, running on unix
With core: /usr/local/lib/cmucl/lib/lisp.core
Dumped on: Mon, 2003-04-21 15:40:49-05:00 on empic5
See for support information.
Loaded subsystems:
Python 1.1, target SPARCstation/Solaris 2
CLOS based on Gerd's PCL 2003/03/22 16:15:17
* adf;lakjf <--- your erroneous input
Error in KERNEL::UNBOUND-SYMBOL-ERROR-HANDLER: the variable ADF is unbound.
Restarts:
0: [ABORT] Return to Top-Level.
Debug (type H for help)
(EVAL ADF)
Source: Error finding source:
Error in function DEBUG::GET-FILE-TOP-LEVEL-FORM: Source file no longer exists:
target:code/eval.lisp.
0] q <--- '0]' is the prompt
* <--- lisp prompt
|