UMBC CMSC451, Automata Theory and Formal Languages, Summer 2001, Session II

Homework Assignments

Homework 1, due Mon 07/16

1. A group of n people play a round-robin tournament (i.e., everybody plays one game against all other players). Prove by induction that it is always possible to label the players as P1, P2, P3, ..., Pn in such a way that P1 defeated P2, P2 defeated P3, ..., and P{n-1} defeated Pn.
   

2. A set X of n+1 numbers is chosen from the integers 1 through 2n (inclusively). Using the pigeonhole principle, show that no matter how X was chosen, there must be two elements a, b in X such that a divides b. Hint: there are exactly n odd integers between 1 and 2n.
   

3. Page 54, Exercise 2.2.4 parts b and c.

4. Page 54, Exercise 2.2.5 parts a, b and d.

5. Page 54, Exercise 2.2.8 parts a and b.

Homework 2, due Mon 07/23

1. Page 66, Exercise 2.3.2.

2. Page 67, Exercise 2.3.4.

3. Page 89, Exercise 3.1.1 parts b and c.

4. Page 129, Exercise 4.1.1 parts d and f.

5. Page 130, Exercise 4.1.2 part g.

Homework 3, due Mon 07/30

1. Page 147, Exercise 4.2.6 part a.

2. Page 180, Exercise 5.1.1 part d.

3. Page 180, Exercise 5.1.4 parts a and b.

4. Page 181, Exercise 5.1.7 parts a and b.

5. Page 236, Exercise 6.2.3 part a.

Homework 4, due Mon 08/06

1. Page 236, Exercise 6.2.3 part b.

2. Page 246, Exercise 6.3.5 parts a and b.

3. Page 251, Exercise 6.4.2 part b.

4. Page 271, Exercise 7.1.3.

5. Page 280, Exercise 7.2.1 parts b, c and e.

Homework 5, due Mon 08/13

1. Page 292, Exercise 7.3.2 parts a and b.

2. Page 316, Exercise 8.1.1 parts b and c.

3. Page 328, Exercise 8.2.2 part b.

4. Page 382, Exercise 9.2.6 parts b and d.

5. Page 391, Exercise 9.3.4 part b.

Back up to Summer 2001 CMSC 451 Homepage