Guidelines:

  • Homework problems are taken from the online textbook by default. Use the online version if it is different than your paper book (See Materils).
  • Homework assignments are announced on the Blackboard with their deadlines, and must be submitted as PDF through the Blackboard. Assignments submitted by emails are NOT graded.
  • Before solving the homework problems, you are expected to read and understand the related material. You should show adequate work for credit.
  • The homework PDF file must have a header on the first page, and a header for each question. See HW-format. Please follow this format when you submit your homework in order to be graded. See also an example of a HW_Sample, which can be used as a template for your homework.
  • Late submission is subjected to a 50% penalty if it is submitted by the cut-off time (usually 48 hours after the announced deadline).
  • 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 on the Blackboard will be graded and late penalty may apply if resubmitted after the deadline.
  • Class SN (CSN): You may find your Class-SN here.

Homework 1: =================================================================
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: (The following EP's are mandotary homework problems taken from previous exams)
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: =================================================================
Section 4.3. Exer: 6, 15, 21, 30, 42, 46(c,d).
Section 4.4. Exer: 6(b,c), 12(a,b), 14, 20, 34, 39, 50(h), 52.
Total: 14 exercises.

Homework 3: =================================================================
Section 4.5. Exer: 2(c,d), 6, 12, 16, 20(a,b), 32.
Section 4.6. Exer: 4(c), 10, 12, 18, 23, 24, 26.
Total: 13 exercises.

Homework 4: =================================================================
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: =================================================================
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: =================================================================
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: =================================================================
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: =================================================================
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 LR = {w| wR ∈ L} is not regular. To prove, suppose you have a DFA for L, then modify it to make an NFA for LR.
Total: 8 exercises.

Homework 9: (Optional, for practice only) =======================================
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.
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.
Total: 26 exercises.