CS 575 Automata and Formal Languages

http://www.cs.uky.edu/~goldsmit/575/syl.html

Syllabus

Time and Place: TR 12:30 pm - 1:45 pm, 263 FP Anderson Hall

Professor: Dr. J. Goldsmith
Office: 311 Davis Marksbury Building
Office Hours: Tuesdays, 4-5 PM, and Thursdays, 10-11 AM, or by appointment. Email questions encouraged and answered.

Course Description:

Introduction to models of computation and of formal grammars: finite automata and regular languages, pushdown automata and context-free languages, Turing machines, decidability, and computational complexity, including polynomial and nondeterministic polynomial time, polynomial space, and exponential time bounded computation.
Prereqs: CS 375 or consent of instructor; needed knowledge: Basic Boolean logic, set theory, and graph theory, especially notions of graph theory, depth first and breadth first search.

Textbook:

Automata, Computability, and Complexity: Theory and Applications, Elaine Rich. Pearson Prentice Hall, 2008.
Errata for the book

Grading:

There will be biweekly homeworks due Thursdays at the beginning of class except those weeks when there is an exam; assignments will be posted at least a week in advance, on the web. The lowest homework grade will be dropped. Illegible work will not be graded. There will be one midterm exam and one final.

Homework will be 50% of your grade; the midterm will be 20% and the final 30%.

Homeworks will be due on Thursdays at the beginning of class on: Jan. 19th, Feb. 2nd, 16th, Mar. 8th, 29th, April 12th, and Tuesday April 25th.

READ THIS:

Attendance in class and section is very strongly encouraged.

Copying of homework from other students or from other sources is strictly prohibited. Obtaining a solution from another source without citing the source is plagiarism. You are encouraged to visit Dr. Goldsmith in her office hours or to send her email if you are stuck on homework problems. You do not need an appointment for regularly scheduled hours.

Week by Week Course Outline:

Date	Topic	Chapter	Assignment
Jan. 12	Math review, strings, languages	2	First homework
Jan. 17--19	Turing machine variants	4, 17
Jan. 24--26	algorithms, Church-Turing thesis, RAMs	17.4, 18
Jan. 31-Feb. 2	decidability, Halting Problem	19, 20	Second homework
Feb. 7--9	reducibilities	21
Feb. 14--16	reducibilities; recursion theorem	25	Third homework
Feb. 21--23	big-O; P and NP, NP-completeness	27, 28
Feb. 28--Mar. 1	NP-completeness, other complexity classes	28, 29	Fourth homework
Mar. 6	Review		Practice Midterm
Mar. 8	MIDTERM
Mar. 11--18	SPRING BREAK!
Mar. 20--22	DFAs, regular operations, NFAs, equivalence	5	Fifth homework
Mar. 27--29	regular expressions, equivalence with FAs	6
Apr. 3--5	Pumping Lemma, Myhill-Nerode Thm	8
Apr. 10--12	CFGs, PDAs, equivalence	11, 12	Sixth homework
Apr. 17--19	ambiguity Pumping Lemma, nondeterminism	12, 13	Seventh homework
Apr. 24--26	2-stack automata, review of complexity	14, 15
May 2	FINAL: WEDS., MAY 2nd, 8 AM

Dear Student: As part of our curriculum improvement process, the Department of Computer Science would like to know how well this course has helped you meet the learning objectives for the course. Please respond to the supplemental questions beginning at 37 on the response sheet as follows:

0= Not Applicable 1= Unacceptable 2= Poor 3= Acceptable 4=Good 5=Outstanding

The course has helped me to improve my ability, my understanding, or my knowledge in the following categories:

37. ability to apply knowledge of computing and mathematics appropriate to the discipline;
38. recognize the relationship between machine models and language generation;
39. analyze languages in terms of machine complexity;
40. analyze algorithms in terms of time and space complexity;
41. design better algorithms;
42. recognize problems that are intractable or incomputable;
43. understand the relevance of Theory to the CS curriculum.