College of Computer & Information Science Fall 2006 Northeastern University Handout 3 CSU690: Algorithms and Data 15 September 2006

Review 1 (Tuesday, September 19)

1. Exercise 5, page 24.

2. A tromino is an L-shaped tile formed by three adjacent squares of a chessboard. Prove by induction on n ≥ 1 that any 2^{n} × 2^{n} chessboard with one square missing can be completely covered by trominoes, regardless of the location of the missing square.

3. Exercise 8 part (a), page 69.