University of Louisville,
CECS Department
===============================
AUTOMATA THEORY -
CECS 504-01
COURSE
SYLLABUS
Instructor: Dr. Mehmed Kantardzic Phone:
(502) 852-3703
E-mail: mmkant01@louisville.edu
Office
Hours: TTh 03:00 pm-04:00 pm DC 210
or
other times by appointment
Lectures: TTh 04:00pm-05:15 pm DC 116
Laboratory:
None
Course
Prerequisite: CECS 310
Course
Description:
This
course is an introduction to formal specification of different types of
automata and languages, and their applications to engineering problems
including modeling the behavior of discrete systems. Topics include theory of computing, formal
languages theory, and applications of cellular automata.
The
course contains heavy coverage of the following ABET goals: the ability
to apply knowledge of mathematics, and the ability to formulate and solve
problems.
Course Objectives:
At
the conclusion of this course, the successful (passing) student will be able
to:
a.
Understand
the basic principles of formal languages and abstract models of computation.
b.
Demonstrate
the ability to specify and design finite automata, pushdown automata, and
Turing machines.
c.
Demonstrate
the ability to analyze and design regular, context-free, recursive, and context
sensitive languages.
d.
Demonstrate
a working knowledge on computational complexity and limits of algorithmic
computation.
e.
Formalize
problems in computer science with greater mathematical maturity.
Text:
P.
Linz, An Introduction to Formal
Languages and Automata, 5nd Edition, Jones and Bartlett
Publishers, Inc., 2011.
Assignments:
Homework
assignments serve as an aid to the class lecture topics. They will be given in class and are expected
to be completed before the next class.
Unannounced quizzes may be given on homework assignments.
Grading Policy:
There
will be two TESTS and a COMPREHENSIVE FINAL EXAM. Arrangements must be made IN ADVANCE if for
some valid reason you cannot take an exam at the scheduled time. Tests and exams will be closed book.
In
addition to achieving a passing cumulative score (typically 60%), a minimum
performance of 50% should also be achieved in each of the next three areas
(given with weights):
10
Quizzes 20%
Two
Tests 40%
Final
Exam 40%
------
Total
100%
Grading
Scale
(90% & up) A
(80%-89.99%) B
(70%-79.99%) C (60%-69.99%) D
(below 60%) F
Cheating Policy:
Students
are encouraged to work together and learn from each other. However, cheating in any form on exams, or
copying of homework or computer programs will not be tolerated. Any evidence of cheating will result in a
failing grade for the course and appropriate notification will be made to the
Dean's office.
General Policies:
Paper-and-pencil
type homework will be assigned. Homework
is due at the beginning of the next class. Homework will NOT be collected and
graded, but the problems from the homework will be assigned for the unannounced
quizzes.
Students with Disabilities:
If
you need accommodations because of a disability, if you have emergency medical
information to share with me, or if you need special arrangements in case the
building must be evacuated, please see me after the first class meeting or make
an appointment to discuss it with me as soon as possible.
Tentative
Schedule:
The following is the tentative
schedule of topics, and associated text sections, which will be covered.
1. Introduction to the Theory of Computation (Chapter 1)
2. Finite Automata (Chapter
2)
3. Regular Languages and Regular Grammars (Chapters 3 and 4)
4. Context-Free Languages (Chapters
5, 6 and 8)
5. Pushdown Automata (Chapter
7)
6. Turing Machines (Chapters
9 and 10)
7. A Hierarchy of Formal Languages and Automata (Chapter 11)
Computer projects: None
Oral and written communication
requirements:
There
will be no oral or written communication requirements beyond normal homework
assignments, quizzes and exams.
Title IX/Clery Act Notification
Sexual
misconduct (including sexual harassment, sexual assault, and any other
nonconsensual behavior of a sexual nature) and sex discrimination violate
University policies. Students experiencing such behavior may obtain
confidential support from the PEACC Program (852-2663), Counseling Center (852-6585),
and Campus Health Services (852-6479). To report sexual misconduct or sex
discrimination, contact the Dean of Students (852-5787) or University of
Louisville Police (852-6111).
Disclosure
to University faculty or instructors of sexual misconduct, domestic violence,
dating violence, or sex discrimination occurring on campus, in a
University-sponsored program, or involving a campus visitor or University
student or employee (whether current or former) is not confidential under Title
IX. Faculty and instructors must forward such reports, including names and
circumstances, to the University's Title IX officer.
For
more information, see the Sexual Misconduct Resource Guide.
http://louisville.edu/hr/employeerelations/sexual-misconduct-brochure
NOTES & LECTURES
