

Homework
Exercises for
Chapter 2:
2.1, 2.2, 2.5, 2.6, 2.11.
Exercises for
Chapter 4: 4.1, 4.2, 4.5, 4.6.
Exercises for Chapter 5: 5.5, 5.8., 5.9, 5.14, 5.17.
Graduate students are required to submit (printed, doublespaced): 5.11 Due date: March 9, 2009.
Exercises for Chapter 7:
 Find the expression tree for this expression: (c + 3)*(d  2)/(c + 1)*d
 and use it to find prefix (straight Polish) and postfix (reversed Polish) form of that expression.
 Write a code (in C, C++, or Java) that determines whether given value key appears in a given linked list. The code must incorporate a while loop with a shortcircuit logical connective.
 Write the first 10 states resulting from the execution of the above code.
 Why C admits only copy semantics of assignments while Java admits both copy and reference semantics?
 List all forms of loops discussed in section 7.5.3 and indicate which of them are redundant? Justify your answer.
Graduate
students are required to study Chapter 8, Sections 8.1, 8.2, and 8.4,
and submit (printed, doublespaced) solution to exercise 8.8. Due date: March 16, 2009.
Exercises for Chapter 9:
9.1, 9.4, and 9.6 p. 241242.
Programming assignment #1
Credit: 5 points DUE DATE April 8, 2009
Programming language Sage (an extension of Python)
1. Go to http://www.sagemath.org/ and create a free "notebook" account for yourself.
2. Define class Sieve
class Sieve(): def __init__(self, n): YOUR CODE HERE def get(self): return self.primes;
that
has one instance variable primes. Each instance of class Sieve is a set
of all prime numbers not greater than n (a parameter in constructor
__init__).
3. Define class Divisors
class Divisors(): def __init__(self, n): YOUR CODE HERE def get(self): return self.divisors; that
has one instance variable divisors. Each instance of class Divisors is
a set of all divisors of n (a parameter in constructor __init__).
4.
Write a program that given integer number M constructs objects X of
class Sieve and Y of class Divisors (providing appropriate arguments to
the constructors of both classes), and find the set of all prime
factors of M as the intersection of X and Y.
5. (For graduate students only) Expand the above code to one that given integer n prints it prime factorization in the form:
n = a^n * b^m * c^k...
where a, b, c, ... are prime factors of n in an increasing order, and n, m, k, are the multiplicities of these factors.
WHAT TO TURN IN:
I. The complete printout of the source code in Sage
II. The traces of its execution for n = 20, 100, 1951, and 3072.
NOTE: Statement and expression forms that may be helpful:
n%m  the remainder of division of n by m []  the empty list [a,b,c]  a list of three elements: a, b, c range(n,m)  a list of all integers between n and m1 [i*j for i in list if i*j < n]  a list of all products i*j such that i is a member of list and i*j is less than n Set(list)  a set of elements of list;
examples: Set(range(n,m))
Set([i*j for j in list if i*j <= n])
for i in X: BODY OF THE LOOP  a "for" loop with i ranging over set or list X X.intersection(Y)  the intersection of sets X and Y X.difference(Y)  the settheoretic difference between sets X and Y
TUTORIALS: Sage http://www.sagemath.org/doc/tutorial/, with a few intro slides available here: http://wwwigm.univmlv.fr/~saliola/sage/MiniCourse/Lecture1IntroToSage.pdf
Python http://diveintopython.org/toc/index.html
DUE DATE April 8, 2009
Exercises for Chapter 13
1. Rewrite C programs in Fig. 13.2 and 13.3 along the lines of this C program discussed in class: http://csc.csudh.edu/suchenek/CSC321/StackL.c
2. Write programs mentioned in Exercises 13.1 and 13.2 p. 357.
Programming assignment #2
Credit: 5 points DUE DATE May 20, 2009
Write a Prolog program that allows its user to solves this puzzle:
1. There are five houses in a row: 1, 2, 3, 4, 5. 2. Each house has a unique color: yellow, blue, red, ivory, green. 3. Each house has one tenant: Norwegian, Ukrainian, Englishman, Spaniard, Japanese. 4. Each tenant drinks one beverage: water, tea, milk, orange juice, coffee. 5. Each tenant smokes one brand of cigarettes: Kools, Chesterfield, Old Gold, Lucky Strike, Parliament. 6. Each tenant has one pet: fox, horse, cat, dog, monkey. 7. The Englishman lives in the red house. 8. The Spaniard owns the dog. 9. Coffee is drunk in the green house. 10. The Ukrainian drinks tea. 11. The green house is immediately to the right of the ivory house. 12. The Old Gold smoker owns the cat. 13. Kools are smoked in the yellow house. 14. Milk is drunk in the middle house. 15. The Norwegian lives in the first house. 16. The man who smokes Chesterfields lives in the house next to the man with the fox. 17. The horse is kept in the house next to the house where Kools are smoked. 18. The Lucky Strike smoker drinks orange juice. 19. The Japanese smokes Parliaments. 20. The blue house is next to the house where the Norwegian lives.
Who owns the monkey?
Hint:
Use short lower case names as id's of all persons, animals, colors,
beverages, and cigarettes brands involved in the puzzle. Use 1, s(1), s(s(1)), ..., s(s(s(s(1)))) as id's of houses.
Use predicates lives(X,Y), drinks(X,Y), owns(X,Y), smokes(X,Y).
For instance, use lives(nor, 1). to encode requirement 15 of the above puzzle and owns(spa, dog). to encode requirement 8 of the above puzzle.
Use owns(W,hor):smokes(X,koo),lives(X,Y),lives(W,s(Y)). to encode requirement 17 of the above puzzle
WHAT TO TURN IN:
I. The complete printout of the source code in Prolog
II. The trace of its execution for the queries that lead to the solution of the puzzle.





