MAD 3512 - THEORY OF
ALGORITHMS
FLORIDA INT'L UNIV.
HOMEWORK SHEET
TEXTBOOK:
An Introduction to Formal Languages and Automata
by Peter Linz, 4th Edition (D.C. Heath & Co., 2006)
OLD SAMPLE TESTS: Anwers and Hints : Theory of Algorithms
(MAD
3512)
RESB 306.03.c1, c2 (Circulation Desk, UP Library)
These are
the homework problems for the entire course. Later on in the
semester,
a few
problems may added and a few may be deleted.
Review of
Discrete Mathematics:
Sec. 1.1 Nos. 1, 5, 7, 8, 9, 10,
11, 12, 13, 25, 26, 27, 29, 30, 31, 32, 33
(Self revision. If you have trouble with these problems review
your Discrete Math.)
Formal
Languages and
Regular Expressions:
Sec. 1.2
Nos.
4, 5, 6, 10
Sec. 3.1
Nos.
1,
2, 3, 4, 5, 6, 7, 8, 9, 10,
12,
13, 14, 15,
16a-c, 17a-f, 20a-d
Suppl.
Prob. Nos. E1, E2, E3,
E4, E5
Context-Free
& Right Linear Grammars:
Sec. 1.2
Nos.
11a-d, 12, 13, 14a-h, 15a-d, 16,
17, 18a-c, 21, 22
Sec. 3.3
Nos.
2, 3, 4a-b, 6, 7, 10, 11
Sec. 5.1
Nos. 2, 7a-d,
8a-d, 13a-b, 20, 22,
23, 24, 25
Sec. 5.2
Nos. 6,
9, 11, 13a-b
Finite
Automata (Deteministic and Non-Deteministic):
Sec. 2.1
Nos.
1, 2a-d, 3, 4, 7a-d, 9a-c,
10,
11
Sec. 2.2
Nos.
2, 4, 5, 7, 11,
12, 14, 16
Sec. 2.3
Nos. 1, 3, 5,
6, 7a-b, 10, 11
Sec.
2.4 Nos.
1, 4, 6
Regular
and Non-regular Languages :
Sec. 3.2
Nos.
1, 2, 3, 4, 5, 7, 8a-b,
9, 10a-c,
13a, 18a-b
Sec. 3.3
Nos.
1, 12, 13
Sec. 4.1
Nos. 5, 6, 7,
12, 13, 14, 16, 26
Sec.
4.2 Nos.
1, 2, 5, 6
Sec. 4.3
Nos.
1, 3a-b, 4a-f, 5a-d, 14, 17,
21, 23, 24
Suppl.
Prob. Nos. E6, E7, E8,
E9, E10, E11
Turing Machines, Turing-Computable Functions & Turing-Decidable
relations:
Sec.
9.1 Nos.
2, 3, 4, 5, 6, 7a-b, 7g,
9, 11a
Sec. 11.1
Nos. 2, 5, 6,
7,
8, 12a-b
Recursive Functions, Recursive & Semi-recursive relations
Sec. 13.1
Nos. 1a-b,
3,
4a-b, 5a-b, 6, 7, 9a-c, 10,
11, 15a-d
Suppl.
Prob. Nos. E12, E13,
E14