Homework Assignments

Notes:
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 by the deadline announced on the Blackboard. Submissions by email are not accepted.
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. Late submission is subjected to a 50% penalty within the cut-off time (usually 48 hours after the announced deadline). No submission after the cut-off time.
5. Resubmission: If you submit a wrong file, or modify the solution after submission, you can resubmit within the deadline (at most twice). Only the latest submission will be graded and late penalty may apply if resubmitted after the deadline. For more details, see the FAQs page on the Blackboard.
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.