AFL course syllabus

 

• 10:15-12:00 Tuesdays in room M1 (Quantum, 2nd floor)
• 12:15-14:00 Thursdays in room M1 (Quantum, 2nd floor)

Homework sessions (13 times 2 hours) Aug 30 – Dec 15:

• 14:15-16:00 Mondays in room M2 (Quantum, 2nd floor)

Course Web Page: http://users.utu.fi/jkari/afl2022

Instructor:  Jarkko Kari <jkari@utu.fi>; office: Quantum 365, 3rd floor

Textbook:

• No textbook. Lecture notes are posted on the course web page.

About homework:

• To pass the course, at least 25% of the homework problems must be completed. The more problems you solve, the more credit towards the final grade you get: You get demo class
  • • A, if you complete 70%-100%,
    • B, if you complete 45%-70%,
    • C, if you complete 25%-45%

    of the given problems.

Midterms

• Two midterm exams: Dates TBA.
• Not mandatory. The class requirements can also be satisfied by taking a single final exam.
• Both midterms (3 hours) consist of 4 problems, each of which has maximum score of 4 point.
• A minimum of 5 points is required in both midterms.
• Homework activity (demo class A, B or C) and the combined score of the two midterms determine the final grade according to the following table:

Final Grade	Demo class
	A	B	C
1	13-14	14-15	15-16
2	15-18	16-19	17-20
3	19-22	20-23	21-24
4	23-27	24-28	25-28
5	28-32	29-32	29-32

Final exam:

• An alternative way to pass the class. One can take the exam more than once (even if one has passed the course) to improve the final grade.
• Dates TBA
• Anyone with democlass at least C has qualified to take the exam within one year.
• Exams (4 hours) consist of 5 problems, each of which has maximum score of 8 points.
• Homework activity (demo class A, B or C) and the score of the final exam determine the final grade according to the following table:

Final Grade	Demo class
	A	B	C
1	17-18	18-19	19-21
2	19-23	20-24	22-26
3	24-29	25-30	27-31
4	30-34	31-35	32-36
5	35-40	36-40	37-40

 

Brief course outline

Regular languages:

• Finite automata, regular expressions
• Kleene theorem
• Pumping lemma
• Closure properties and decision algorithms
• State minimization, Myhill-Nerode theorem

Context-free languages:

• Grammars, parsing
• Normal forms
• Pushdown automata
• Pumping lemma
• Closure properties and decision algorithms

Turing machines:

• Recursive and recursively enumerable languages
• Universal Turing machines
• Undecidability of the halting problem (Turing)
• Reductions, other undecidable problems