## CSCE A351: Automata, Algorithms, and Complexity

Course Syllabus, Spring 2016
• Tuesday, Thursday 10:00-11:15 AM. Room: RH 315
• Instructor: Dr. Kenrick Mock.
• Office Hours: : TWR 11:30-12:30PM, EIB 403E
• Prereq: CSCE A311, MATH A261
• Web page: Blackboard
Textbook

Course Description:   The first half of the course studies the theory of computing.  Topics include finite automata, context free grammars and parsing, regular languages, pushdown automata, Turing machines, decidability, computablity, and complexity.

What does all this mean?  These should become familiar terms as the course progresses.  Overall, the course is fairly mathematical and relies upon logic, algebra, and discrete math.  Some students find the abstract concepts difficult to grasp, particularly the proofs, so be prepared to put in some extra reading if this is the case! In general terms, at first we will study abstract computing devices starting from very simple devices (deterministic finite automata) and moving to complex abstract computing devices (turing machines).  Along the way we'll see other computing devices and ways to describe what can be computed through grammars, languages, and answer basic questions of computability and tractability. Through the concept of a turing machine we will describe algorithms and the complexity bounds of what can be computed.  Some problems we will see are undecidable (they can't be solved by any computer!) while others may be intractable (they can be solved by a computer, but take a ridiculously long time to do so).

The second half of the course studies techniques for the design and analysis of algorithms. This includes problem solving and the study of common problems such as sorting, searching, graph algorithms, string matching.  We will study the techniques used to solve these problems, including brute force, divide and conquer, decrease and conquer, transform and conquer, dynamic programming and greedy algorithms. Students should learn to develop a group of useful algorithms that can be used to solve common problems along with methods to analyze the correctness, time, and space used by these algorithms.

Instructor Goals:  The instructor will:

• Introduce fundamental topics in the theory of computing, including: formal languages, automata, grammars, computability, and Turing machines.
• Introduce the concept of computational complexity.
• Demonstrate the design of a wide variety of algorithms and algorithmic techniques.
• Demonstrate mathematical techniques to determine the efficiency of an algorithm.

Student Outcomes: Upon completion of the course the student will be able to:

• Construct automata, grammars, and Turing machines to recognize languages and perform computational tasks.
• Identify the complexity class of a language.
• Design algorithms to solve new problems in an efficient manner.
• Analyze the computational complexity of algorithms.

Homework Assignments :    Due on Blackboard by the posted date/time, or by the beginning of class if you are turning anything in on paper. Approximately seven homework assignments will be given, some of which may include programming in the language of your choice.  Late homeworks will be penalized 10% per day late up until the date solutions are posted. Unless otherwise indicated, programming assignments and written assignments must represent your own work. It is permissible to discuss the assignments with other students, but do not discuss the solution.

Small Group Problem Discussion: Every Thursday except for the first, last, spring break, and midterm weeks we will save the last 30 minutes of class for random groups of 3 (or 2) students to present solutions to problems given earlier that week. Each student should come prepared with a solution to all of the problems (usually 3) and will be responsible for presenting his or her solution to at least one of the problems to the small group. Your group can discuss the presented solution. I will post my own solutions to the problems after class. These are graded as done/not-done and two not-done will be dropped to allow for sick or unplanned events.

Questions: If you have any questions, feel free to come in to my office.  In general, I have an open door policy -- if I am available in my office, you are welcome to come by.  An even better way to reach me is through email.  I check my email frequently and you should receive a response quickly.  Email is preferred over telephone and you will probably receive a faster response since I don't check voicemail very frequently.

Grading:  Letter grade. There will be two exams, a midterm and a final exam. The midterm will cover the Automata material and the final will cover the Algorithms material. Unless prior arrangements are made no make-up exams will be given. Since you will be tested upon your critical thinking and problem solving skills and not your ability to memorize formula, the exams will be open book.  Any written material and a computer is acceptable to bring to the test.