1. Homework problems are taken from the online textbook (See Blackboard). Use this online version if it is different than your paper book. Before solving the homework problems, you are expected to read and study the related material.

2. Homework assignments must be typed, saved as PDF, and electronically submitted

3. The homework PDF file must have a header on the first page, and a header for each question. See HW format. You should follow this format when you submit your homework in order to be graded. See also a HW sample [doc] which can be used as a template for your homework.

4.

5.

6. You may find your Class-SN here

** Homework 1:** (Show work for credit)

Section 4.1. Exer: 6, 10(d,f), 12(a,b), 14(e), 24(c), 32(b,c), 40.

Section 4.2. Exer: 2(a,b), 22(a,b), 30(b,c), 32, 52.

__Extra Problems:__

EP#1. In modular arithmetic, compute each of the following. Show work for credit.

(a) (12990 * 270) mod 13.

(b) (53418 * 234567 * 6543) mod 11.

EP#2. Apply the modular exponentiation algorithm explained in the class to compute:

(a) 7^13 mod 9.

(b) 6^20 mod 13.

Total: 14 exercises.

** Homework 2:** (Show work for credit)

Section 4.3. Exer: 5, 6, 15, 30, 43, 46(c,d).

Section 4.4. Exer: 5(b,c), 11(a,b), 13, 21, 34, 39, 50(h), 52.

Total: 14 exercises.

** Homework 3:** (Show work for credit)

Section 4.5. Exer: 1(c,d), 5, 11, 16, 21(a,b), 31.

Section 4.6. Exer: 5(c), 11, 12, 19, 23, 25, 27.

Total: 13 exercises.

** Homework 4:** (Show work for credit)

Section 9.1. Exer: 6(a,h), 14, 20, 26(a,b), 34(c,e,g), 36(a,c), 42, 44(a,e,f), 48(a,c), 50(c,d,e).

Section 9.3. Exer: 8(a,b), 10(b,d), 14(b,d), 20(a,b), 32.

Total: 15 exercises.

** Homework 5:** (Show work for credit)

Section 9.4. Exer: 10, 28(b).

Section 9.5. Exer: 16, 40, 48(b), 56(a,b), 62, 64(Justify your answer).

__Extra Problem:__

EP#1. Let R be an equivalence relation on A. What is the maximum number of equivalence classes can R make if:

(a) |A| = 8, and |R| = 16.

(b) |A| = 100, and |R| = 122.

EP#2. Given a large matrix M representing a relation.

(*a) Explain how quickly you can tell if M represents an equivalence relation without drawing the digraph. Verify your method on small examples.

(b) Apply your method to find whether or not the following matrix represents an equivalence relation. Briefly justify your anser.

**
1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0
0 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0
1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0
0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1
0 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0
0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1
**

Total: 10 exercises.

** Homework 6:** Solve the following exercises. Show work for credit.

Section 9.6. Exer: 2(a,c), 14, 16(a,c), 22(c), 32(a,g,h), 36(a,c), 44(a,d), 52(a,c), 54(b,c), 62.

Total: 10 exercises.

** Homework 7:** Solve the following exercises. Show work for credit.

LNTC-Section 1. Exer: 3(a,b), 4, 5(c,d) 6.

LNTC-Section 2. Exer: 1(c,d,f), 2(d,e,f), 3, 4.

LNTC-Section 3. Exer: 1(e,h,j,k), 2.

Total: 10 exercises.

** Homework 8:** Solve the following exercises. Show work for credit.

LNTC-Section 4. Exer: 1(d,e,f,g), 2(a,b), 3(b), 4(c,d), 5.

__Extra Problem:__

EP#1. Design a small NFA (with minimum number of state) that accepts all strings that have even number of a's and even number of b's.

EP#2. Design a DFA equivalent to the NFA in Figure 6.

EP#3. Let L be a regualr language. Is the reverse of L must be also regular? Prove or disprove. Hint: To disprove, give a counterexample of L such that its reverse L^{R} = {w| w^{R} ∈ L} is not regular. To prove, suppose you have a DFA for L, then modify it to make an NFA for L^{R}.

Total: 8 exercises.

** Homework 9:** Solve the following exercises. Show work for credit.

Section 10.1. Exer: 10.

Section 10.2. Exer: 26, 36, 42(c,d,h), 50, 58, 60, 62.

Section 10.3. Exer: 2, 24, 28, 38, 42, 54.

Total: 14 exercises.

** Homework 10:** Solve the following exercises. Show work for credit.

Section 10.4. Exer: 2, 12.

Section 10.5. Exer: 8, 36, 44.

Section 10.7. Exer: 6, 14.

Section 10.8. Exer: 4, 16.

Section 11.1. Exer: 4, 12, 16.

Section 11.3. Exer: 18, 24.

Total: 14 exercises.