CPSC 668
Fall 2000
Homework


General Instructions:


Homework 4, due 10:20 AM, Friday, Dec 1, 2000:

(R) Exercise 8.8. Explain why or why not.

(S) Exercise 8.9

(T) Exercise 9.2

(U) Exercise 9.3

(V) Exercise 9.11

(W) Exercise 15.6

(X) Exercise 17.22

*** This is the entire assignment. ***


Homework 3, due 10:20 AM, Monday, November 6, 2000:

(N) Exercise 6.2.

(O) Exercise 6.5.

(P) Exercise 6.12.

(Q) Describe an algorithm to synchronize clocks (achieve epsilon- Clock Agreement and gamma-Clock Validity) in the following situation:

What are (upper bounds on) epsilon and gamma for your algorithm and why? (This is an open-ended question.)

*** This is the entire assignment. ***


Homework 2, due 10:20 AM, Wednesday, October 11, 2000 - postponed to Monday, October 16, 2000:

(F) Exercise 4.2. Your algorithm must ensure that a processor does not have to wait if only one processor is already in the critical section. Prove that your algorithm is correct.

(G) Exercise 4.5. Prove that your algorithm is correct.

(H) Exercise 4.7.

(I) Exercise 4.10.

(J) Exercise 5.2. Prove that your algorithm is correct.

(K) Exercise 5.6. Prove that your algorithm is correct.

(L) Exercise 5.17.

(L) Exercise 5.18. (Check the errata page.)

(M) Exercise 5.19. If you don't find the notation suggested in point 1 to be helpful, then just ignore it. (Check the errata page.)


Homework 1, due 10:20 AM, Friday, September 15, 2000:

(A) Exercise 2.8

(B) Exercise 2.11

(C) Exercise 3.3

(D) Exercise 3.5

(E) Exercise 14.3