Courses/CS 332L/Spring 2006
From CSWiki
[edit] Grading and finals schedule
See Abbott
[edit] User pages and homework pages
I'd like you each to create a user account. (That will be required before the system allows you to submit your homework.) When you create a user account, please be sure to enter your email address. That allows someone to contact you through the wiki. (See Contacting users for how to do that.) Also create a user page and make sure to include your email address there too.
I'd also like you each to create a course page for yourself as a subpage of this page. (Please put your email address on your course page as well, making three places where you will have entered your email address.)
To create your course page enter [[/your name/]] below in the list of course pages. (Please enter your page in alphabetical order.) Entering [[/your name/]] will create a page "your name" as a subpage of this page.
Homework pages: [[/your name/]], Ivan Augustino, Kevin Chen, Oleg Gnatovskiy, Joan Kim, Kunhan Kim, Robert Lai, Herbert Lee, Tan Luong, Carlo Marini, Cuong Tham, Celia Torres, Diep Le, Sean Tseng, Robert Wimmer, Shiusen Yao, Raza Abbas, Susan Nguyen, Mads Moeller, Edmond Kong, Nicholas Mew, Justin Wu, Alain de lara, Mark Luntzel, Chia-Yao Chien, Jay Donnell, Daniel Germann,Teodoro Cruz,Robert Plamvonghora, Brian Smith, …
[edit] Textbook and course plan
Clocksin, W. and C. Mellish, Programming in Prolog, 5thedition.
We will focus primarily on the first 8 chapters of the book.
There will be a homework assignment each week. I will ask for volunteers to present the assignment in class the day it is due.
[edit] Prolog Interpreter
You can download a free version of SWI prolog from http://www.swi-prolog.org/.
[edit] Week 1. March 31
No class. Cesar Chavez day.
[edit] Week 2. April 7
Textbook: Chapter 1.
Notes:
Homework: Exercises 1.2 and 1.3.
A green checkmark ( 
) means that you presented your homework. A blue checkmark ( 
) means that you led the discussion of the homework.
Submissions:
[edit] Week 3. April 14
Textbook: Chapter 2 & Section 8.3.
Homework:
- Given the definitions of family from last week, design a query that asks "is there a person who's a father to children of both genders?". Demonstrate on your database.
- Define the predicate (rule) great_aunt. It takes two arguments, and holds if the first argument is the great aunt of the second. (A great aunt is either a sister of a grandparent or the wife of a brother of a grandparent.) Demonstrate on your database.
- The predicate brother/2 could be satisfied by full brothers, who share both parents, or by half brothers, who share only one parent. Define both predicates full_brother/2 and half_brother/2 that distinguish these two cases. You should not use brother/2 in your definitions. Demonstrate on your database.
- How does Prolog respond to the following queries? Explain why.
?- bread = bread. ?- ’Bread’ = bread. ?- ’bread’ = bread. ?- Bread = bread. ?- bread = sausage. ?- food(bread) = bread. ?- food(bread) = X. ?- food(X) = food(bread). ?- food(bread,X) = food(Y,sausage). ?- food(bread,X,beer) = food(Y,sausage,X). ?- food(bread,X,beer) = food(Y,kahuna_burger). ?- meal(food(bread),drink(beer)) = meal(X,Y). ?- meal(food(bread),X) = meal(X,drink(beer)).
- How does Prolog respond to the following query? Explain why. Draw the structure generated.
?- food(X) = X.
- How does Prolog respond to the following queries? Explain why.
?- X = 3*4. ?- X is 3*4. ?- 4 is X. ?- X = Y. ?- 3 is 1+2. ?- 3 is +(1,2). ?- 3 is X+2. ?- X = 1, Y is X+2. ?- X = 8, 3 is X+2. ?- X is 1+2. ?- 1+2 is 1+2. ?- is(X,+(1,2)). ?- 3+2 = +(3,2). ?- *(7,5) = 7*5. ?- *(7,+(3,2)) = 7*(3+2). ?- *(7,(3+2)) = 7*(3+2). ?- *(7,(3+2)) = 7*(+(3,2)).
- Trace (using trace/0) the execution of some query that uses backtrcking. Be able to provide a running commentary of what it is doing.
A green checkmark ( ) means that you presented your homework. A blue checkmark ( ) means that you led the discussion of the homework.
Submissions:
Mark Luntzel ( ) ( ) ( )
Oleg Gnatovskiy ( )
Shiusen Yao ( )
Alain de lara ( ) ( )( )
Jay Donnell ( )
Robert Lai ( )
Joan Kim ( )
Sean Tseng ( )
Susan Nguyen ( )
Carlo Marini( )
Edmond Kong ( )
Herbert Lee( )
Justin Wu ( )
Cuong Tham ( )
Celia Torres( )
[edit] Week 4. April 21
[edit] Textbook
Chapter 3, sections 3.1, 3.2, and 3.3.
[edit] Notes
Let's look at the predicates in C:/Program Files/pl/library/lists.pl.
[edit] Homework 4
- Define the predicate zipUnzip(?Xs, ?Ys, ?XsYs). Xs and Ys can be unified with lists of the same length. XsYs can be unified with a list of the same length as Xs and Ys, whose elements are the elements of Xs and Ys tied together with the - operator. Fails if the variables are instantiated to lists of different lengths.
?- zipUnzip([1, 2, 3], [a, b, c], Z). Z = [1-a, 2-b, 3-c] ?- zipUnzip([1, 2, 3], [a, b, c], [X, Y, Z]). X = 1-a Y = 2-b Z = 3-c ?- zipUnzip(A, B, [1-a, 2-b, 3-c]). A = [1, 2, 3] B = [a, b, c]
- Define your versions of the built-in predicates: length/2, sort/2, msort/2, merge/3, and merge_set/3. Name your functions my_length/2, my_sort/3, my_msort/2, my_merge/3, and my_merge_set/3. You may want to look at the definitions in C:/Program Files/pl/library/lists.pl to see how some of those predicates are defined.
my_sort([], []). my_sort(L, S) :- length(L, Length), Length > 0, HalfLength is Length//2, append(L1, L2, L), length(L1, HalfLength), sort(L1, SL1), sort(L2, SL2), my_merge(SL1, SL2, S).
- Define the predicate range(+Low, +High, ?Range) in which Range unifies with a list of integers starting with the integer Low and ending with the integer High. For example
?- range(4, 7, Xs). Xs = [4, 5, 6, 7]
- Define the predicate is_range(?Low, ?High, +Range) in which Range is a list of sequential integers, Low unifies with the first element in Range, and High unifies with the last element in Range. For example
?- is_range(L, H, [4, 5, 6, 7]). L = 4 H = 7 ?- is_range(L, H, [4, 5, 7]). No
- Use two calls to append/3 and a test for the empty list to define is_subsequence(?Sub, +Seq), which succeeds if Sub unifies with any non-empty subsequence of Seq, including Seq itself.
?- is_subsequence(Sub, [4, 5, 6, 7]). Sub = [4] ; Sub = [4, 5] ; Sub = [4, 5, 6] ; Sub = [4, 5, 6, 7] ; Sub = [5] ; Sub = [5, 6] ; Sub = [5, 6, 7] ; Sub = [6] ; Sub = [6, 7] ; Sub = [7] ; No
You need not generate the answers in the same order.
[edit] Submissions
A green checkmark ( ) means that you presented your homework. A blue checkmark ( ) means that you led the discussion of the homework.
[edit] Week 5. April 28
[edit] Textbook
Sections 3.6 and 3.7.
[edit] Notes
- The picture on p 64 is not consistent with assembly/2 on p 65. (For example, the picture has a single frame, and assembly/2 has two frames. Also, assembly/2 is not consistent with the tree structure at the bottom of p 65. assembly(bike, [wheel, wheel, frame]) whereas in the tree structure only one wheel is shown as subsidiary to the bike. In general, though, you can think of assembly/2 as representing the interior node of a tree and pasicpart/1 as representing the leaf of a tree.
- Two definitions of reverse/2.
reverse([], []). reverse([H|T], R) :- reverse(T, RT), append(RT, [H], R).
reverse_acc(L, R) :- rev_acc(L, [], R). % rev_acc/3 works like a "slinky." % It "pours" the first argument onto the second. % When it is done, it returns the second argument by unifying it with the third. rev_acc([], R, R). rev_acc([H | T], So_Far, R) :- rev_acc(T, [H | So_Far], R).
- Read this brief tutorial about Prolog and graphs. Note the use of \+ in the last clause of travel/4. It means "it is not true that." It prevents looping by ensuring that you don't visit the same node more than once.
- Note the predicate is_integer/1 on p 77.
[edit] Homework 5
- In prolog mod is the mod function.
?- X is 23 mod 20.
X = 3.Use the range/3 predicate and the mod function to generate a list of the divisors of a number.
?- divisors(28, Ds).
Ds = [1, 2, 4, 7, 14] - Do the homework at the end of Prolog and graphs by using the following strategy.
- See if there is a path of length 0.
- If not, see if there is a path of length 1.
- If not, see if there is a path of length 2.
- If not, see if there is a path of length 3. Etc. This strategy is known as Generate and Test. You are generating the integers in sequence and then testing to see if there is a path of that length. You continue to do that until you find a path or you determine that no path is possible. In some cases you might simply search forever. (You will learn about this in CS 486.)
- Use something like is_integer/1 to generate successively larger integers.
- Assume you know the total number of edges in the graph. Don't allow the possible length of the path to exceed the total number of edges. That is, as you increment the possible path length, don't allow it to exceed the total number of edges. If no path is found, fail.
- On backtracking generate longer and longer paths up to the limit of the maximum possible path length. When no further paths less than or equal to the maximum are found, fail. Given the data in Prolog and graphs, the following is one possible output.
?- shortestPath(1, 5, Path). Path = [1, 2, 5] ; Path = [1, 4, 5] ; Path = [1, 3, 5] ; Path = [1, 2, 3, 5] ; Path = [1, 4, 3, 5] ; Path = [1, 3, 4, 5] ; Path = [1, 3, 2, 5] ; Path = [1, 2, 3, 4, 5] ; Path = [1, 4, 3, 2, 5] ; No ?-
To avoid backtracking forever once one finds the longest possible path, you will have to modify is_integer/1 so that it fails when it reaches a limit. That is, convert is_integer/1 to be is_integer(+Max, ?Int), which on backtracking returns in Int all integers less than or equal to Max.
?- is_integer2(6, Int). Int = 0 ; Int = 1 ; Int = 2 ; Int = 3 ; Int = 4 ; Int = 5 ; Int = 6 ; No ?-
- Use generate and test to find (on backtracking) all perfect integers—i.e., integers which are the sum of their divisors.
?- is_perfect(X). X = 6; X = 28; …
[edit] Submissions
[edit] Week 6. May 5
Individual conferences. Please sign up to see me individually. To sign up, enter a pointer to your homework page, i.e., [[/your name/]]
9:30 Robert Lai 9:40 Brian Smith 9:50 Herbert Lee 10:00 your name 10:10 Jay Donnell 10:20 Alain de lara 10:30 Oleg Gnatovskiy 10:40 Joan Kim 10:50 Carlo Marini 11:00 Cuong Tham 11:10 Nicholas Mew 11:20 Daniel Germann 11:30 Susan Nguyen 11:40 Shiusen Yao 11:50 Mark Luntzel 12:00 Diep Le 12:10 Tan Luong 12:20 Raza Abbas 12:30 Justin Wu 12:40 Kunhan Kim 12:50 Sean Tseng 1:00 Ivan Augustino 1:10 Edmond Kong 1:20 Celia Torres 1:30 Teodoro Cruz
[edit] Week 7. May 12
[edit] Textbook 7
Pp. 86 (top), 88-89 (top), 92 (top), 122-123 (6.3), 177-178 (7.11), 116-117 (5.5).
[edit] Notes 7
- If you are willing to help other students in the class, please put your name and contact information on the Discussion page.
- From now on, please label your homework pages according to the week in which they are assigned. Homework assigned this week and due next week should be labelled Homework 7. Don't bother to change the pages of homework done prior to this week.
- Please be sure that you have a main homework page and that you link from that page to each of your individual homework pages.
- Please copy your check marks to your main homework page.
- Please be sure you put your code in code boxes. That makes it much easier for me to read—and it makes it look like you have taken some time to think about what you have submitted.
[edit] Homework 7
- Problem 4 p 260. This is similar to the differentiation example in section 7.11. Use - for NOT, -> for CONDITIONAL, * for AND and + for OR. Thus
P -> Q * R
meansif P then (Q and R)
[The following discussion is related to pp 116-117 (5.5) in the textbook.]
Prolog's operators have their precedence set correctly for this problem. -> binds less tightly than + and *, both of which bind less tightly than -. To see all the default operators and their precedence, look at the table in the operators section under Built-in predicates in the online user manual. You can also use the predicate current_op/3 to look up an operator
?- current_op(P, A, '->'). P = 1050 A = xfy
This means that the precedence of -> is 1050, that it takes two arguments, and that it associates to the right, i.e., that A -> B -> C = A -> (B -> C). To test that out try
?- (a -> b -> c) = (X -> Y). X = a Y = b->c ;
Note that the parentheses are needed because
?- current_op(P, A, =). P = 700 A = xfx
The = operator has precedence 700, which is less than 1050. In other words it binds more tightly. Also, it doesn't associate at all.
?- X = Y = Z. ERROR: Syntax error: Operator priority clash ERROR: X = ERROR: ** here ** ERROR: Y = Z .
- Problem 10 p 261. As instructed write predicates to add, subtract, and multiply two integers as defined. If subtraction would result in a number less than 0, return 0. In addition, write a predicate value(?S, ?N), which translates between between the successor notation and integers.
?- value(s(s(s(0))), N). N = 3; No
?- value(S, 3). S = s(s(s(0))); No
You will probably have to use var/1 and nonvar/1 to determine which argument is instantiated. If neither argument is instantiated, fail.
[edit] Submissions 7
A green checkmark ( ) means that you presented your homework. A blue checkmark ( ) means that you led the discussion of the homework.
Oleg Gnatovskiy
Sean Tseng
Joan Kim
Ivan Augustino
Herbert Lee
Tan Luong
Alain de lara
Shiusen Yao
Carlo Marini
Robert Lai
Brian Smith
Daniel Germann
Susan Nguyen
Robert Wimmer
Robert Plamvonghora
Jay Donnell
Diep Le
Cuong Tham
Nicholas Mew
Teodoro Cruz
Raza Abbas
Celia Torres
[edit] Week 8. May 19
[edit] Textbook 8
Section 6.9.
[edit] Notes 8
[edit] Homework 8
-
Extend last week's homework to work directly with expressions in which the leaf nodes are s-notation versions of the integers. In particular write the following predicates.
- value(?IntegerExpression, ?S_Notation_Expression)
in which (a) the first argument is an aritmetic expression using the operators +, -, and * and the leaf nodes are non-negative integers, and (b) the second argument is the same expression but with the leaf nodes replaced by s-notation versions of the integers. This predicate should "work in both directions." That is, either of the two arguments may be uninstantiated, although at least one must be instantiated. - sArith(+S_Notation_Expression, ?S_Notation)
in which (a) the first argument is an expression using the operators +, -, and * and the leaf nodes are s-notation integers, and (b) the second argument is the s-notation result of evaluating the first argument.
One should be able to write something like the following.
?- value(3 + 4, S_Expr), sArith(S_Expr, S_Ans), value(Ans, S_Ans). S_Expr = s(s(s(0)))) + s(s(s(s(0)))) S_Ans = s(s(s(s(s(s(s(0))))))) Ans = 7; No
Solution to sArith is a solution to this problem.
- value(?IntegerExpression, ?S_Notation_Expression)
- Select and solve three puzzles from those listed on these web sites: Enchanted Learning Logic Puzzles, PuzzlersParadise, Judy's logic problems. If you find these too easy (for example, if you have done this already in CS 460) select more challenging problems.
Note: See comment on an appropriate use of permute/2 for problems in which not all values are explicitly instantiated by the clues.
[edit] Submissions 8
A green checkmark ( ) means that you presented your homework. A blue checkmark ( ) means that you led the discussion of the homework.
Oleg Gnatovskiy
Susan Nguyen
Alain de lara
Tan Luong
Joan Kim
Robert Lai
Cuong Tham
Shiusen Yao
Sean Tseng
Daniel Germann
Brian Smith
Herbert Lee
Celia Torres
Justin Wu
Nicholas Mew
Robert Plamvonghora
Carlo Marini
Ivan Augustino
Teodoro Cruz
Raza Abbas
Robert Wimmer
[edit] Week 9. May 26
[edit] Textbook 9
Top half of page 183: A Prolog Interpreter.
[edit] Notes 9
To avoid the risk of cancelled classes, please enroll as soon as possible in any classes you plan to take over the Summer.
[edit] Homework 9
- Extend the interpreter in Notes 9 to include the other relational operators as well as a do-while (i.e., repeat-until) construct.
- Add function declarations and function calls to the language. See Adding functions
[edit] Submissions 9
A green checkmark ( ) means that you presented your homework. A blue checkmark ( ) means that you led the discussion of the homework.
Brian Smith
Oleg Gnatovskiy
Alain de lara
Cuong Tham
Joan Kim
Daniel Germann
Herbert Lee
Jay Donnell
Robert Lai
Shiusen Yao
Carlo Mariini
Susan Nguyen
Diep Le
Kunhan Kim
Robert Plamvonghora
Justin Wu
Ivan Augustino
Tan Luong
Robert Wimmer
[edit] Week 10. June 2
[edit] Textbook 10
None
[edit] Notes 10
I have a meeting at 11:00 today. It shouldn't last more than an hour.
[edit] Homework 10
- Implement records. You may start with Brian Smith's homework solution from last week, which has been modified to store functions as described in this week's Notes. You will have to add your own declaration of the dot (.) operator.
- (Optional)
- Define
while, do, if, then, else, andreturnas Prolog operators so that one could write, for example,program( a := 221; b := 493; while (a \== b) do ( if (a > b) then (a := a - b) else (b := b - a)), Fs, Vs).and
program( function (factorial(x), if (x < 2), then (return 1) else (temp = factorial(x - 1); return x * temp))); z := factorial(5), Fs, Vs).while, if, andreturnwould be unary prefix operators. The others would be binary operators. To implement a do-while structure,doandwhilewould have to be both unary and binary. This is not unusal. The operators+and-are both binary and unary operators.?- current_op(P, A, +). P = 500 A = fx ; P = 500 A = yfx ; No
- Add a definition for
;as a unary postfix operator (but keep its definition as a binary operator) so that one can terminate statements with;as in the following.program( a := 221; b := 493; while (a \== b) do ( if (a > b) then (a := a - b;) else (b := b - a;)), Storage_Out).Note the terminal
;in the then and else parts.In Pascal,
;is a statement separator. (People found that confusing.) In Java and C/C++,;is a statement terminator.
- Define
[edit] Submissions 10
Oleg Gnatovskiy
Carlo Marini
Tan Luong
Cuong Tham
Joan Kim
Shiusen Yao
Ivan Augustino
Teodoro Cruz
Jay Donnell
Daniel Germann
Justin Wu
Herbert Lee
Kunhan Kim
Brian Smith
Alain de lara
Brian Smith
Raza Abbas
Robert Plamvonghora
Robert Wimmer
[edit] Finals week. June 9
Individual conferences. Please sign up to see me individually. To sign up, enter a pointer to your homework page, i.e., [[/your name/]]. Please sign up from top down, with no blank spaces. I will be attending the Marshal graduation rehearsal from 1:00 - 2:30.
However, before signing up, please (a) do (and submit) the Week 10 homework and then (b) send me an email Russ.Abbott@gmail.com telling me what grade you think you deserve and why you think that's the right grade. If I agree, we can bypass the meeting. Please do the Optional portion of the Week 10 homework if you want an A without a meeting.
If you haven't heard from me, please sign up and come in to talk.
10:00 Robert Lai 10:15 Cuong Tham 10:30 Carlo Marini 10:45 Ivan Augustino 11:00 your name 11:15 your name 11:30 Shiusen Yao 11:45 your name 12:00 Jay Donnell 12:15 Justin Wu 12:30 your name 12:45 Tan Luong 1:00 - 2:30 Marshal rehearsal 2:30 Susan Nguyen 2:45 Robert Plamvonghora 3:00 your name 3:15 Kunhan Kim 3:30 Alain de lara 3:45 Nicholas Mew 4:00 Herbert Lee 4:15 Celia Torres 4:30 Robert Wimmer
