CSE 370 Assignment #1

Due: Wednesday, April 8, 2009.

Exercises:

Show your work.

  1. Exercise A.1, parts b,c,d,f,i

  2. Exercise A.2, parts c,f

  3. Exercise A.4, parts a,f

  4. Exercise A.5, parts a,f

  5. Exercise A.7, parts c,f

  6. Exercise A.8, parts c,f

  7. Exercise A.14, parts c,f

  8. Exercise 1.17

  9. There are 6 different types of pieces on a chess board: king, queen, rook, bishop, knight, pawn. An encoding for the six requires a minimum of 3 bits. Consider the following encoding: the first bit is used to indicate whether the piece can move only one square with a 1 or an arbitrary number of squares with a 0 (assume the pawn can only move forward 1 square for now, do not consider other moves). The other two bits are used to indicate whether the piece can move diagonally or orthogonally to the axes of the board (you can assume that the knight does not move either diagonally or orthogonally and moves more than one square). Derive the encoding for the six pieces using the following names for the 3 bits: "one", "diagonal", and "orthogonal". Do you have a unique encoding for each of the six? Which encoding(s) do you not use? Describe the moves of the "fictional" chess pieces for the encodings you are not using. If you don't know how chess pieces move, see http://en.wikipedia.org/wiki/Chess_piece.

  10. Exercise 2.1

  11. Exercise 2.2, parts a,d

  12. Exercise 2.6, parts a,c

  13. Exercise 2.10, parts a,f