CS 575 Automata and Formal Languages, Fall 2016

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

Syllabus

Time and Place: M/W/F 11 -- 11:50 AM, 255 FP Anderson Hall

Professor: Dr. J. Goldsmith
Office: 311 Davis Marksbury Building
Office Hours: TBA 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:

Introduction to the Theory of Computation. Michael Sipser, Course Technology; 3 edition (June 27, 2012). You are encouraged to use the more affordable 2nd edition. (The bookstore refused to order it.)

Grading:

There will be biweekly homeworks due Fridays 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 Fridays at the beginning of class on: Sep. 2, Sep. 16, Sep. 30, ...

READ THIS:

Attendance in class and section is very strongly encouraged.

You are encouraged to discuss homework problems, AS LONG AS YOU GIVE CREDIT TO WHOMEVER DISCUSSED THEM WITH YOU AT THE TOP OF YOUR HOMEWORK. You are strongly discouraged from seeking solutions online; if you do, YOU MUST CITE ANY SOURCES EXPLICITLY FOR EACH PROBLEM FOR WHICH YOU FOUND AN OUTSIDE SOURCE. 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. The first instance of plagiarism will result in an un-droppable 0 on the homework. That typically drops you one letter grade. The second instance will become part of your permanent UK record, and can result in expulsion from the program.

You are encouraged to visit Dr. Goldsmith in her office hours or to send her email at any time if you are stuck on homework problems. You do not need an appointment for regularly scheduled hours. Email sent late Thursday night probably won't be answered in a timely fashion. PLAN AHEAD.

Week by Week Course Outline:

DateTopicChapterAssignment
Aug. 24--29 Math review, proofs; strings, languages 0 First homework
Aug. 29--Sep. 2Finite Automata, Nondeterminism, Regular Expressions1
Sep. 7--9 Equivalences 1 Second homework
Sep. 12--16 Pumping Lemma, Myhill-Nerode Thm 1.4
Sep. 19--23 CFGs, PDAs, equivalence2 Homework
Sep. 26--30 Equivalence, Ambiguity, Pumping Lemma2
Oct. 3 No class2
Oct. 5 REVIEW1--2
Oct. 7 MIDTERM1--2
Oct. 10 Discussion of Midterm
Oct. 12No class
14Turing Machines3.1 Homework
Oct. 17--21 Multi-tape and Nondeterministic TMs3.2
Oct. 24--28Coding TMs; Decidability4.1 Homework
Oct. 31--Nov. 4Undecidability, Reductions4.2, 5.3
Nov. 7--11Big O, P7.1, 7.2 Homework
Nov. 14--18Time and Space Hierarchy Theorems9.1
Nov. 21NP7.3
Nov. 24Thanksgiving
Nov. 29--Dec. 2NP-Completeness7.4, 7.5 Homework
Dec. 5--9 Other Complexity Classes, Review8.2 + Practice exam
December 15FINAL: WEDS., Dec. 14, 10:30 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:

  1. ability to apply knowledge of computing and mathematics appropriate to the discipline;
  2. recognize the relationship between machine models and language generation;
  3. analyze languages in terms of machine complexity;
  4. analyze algorithms in terms of time and space complexity;
  5. design better algorithms;
  6. recognize problems that are intractable or uncomputable;
  7. understand the relevance of Theory to the CS curriculum.

webmaster@cs.uky.edu
This page last modified: July 27, 2016