Time and Place: 11 am -- 12:15 pm T/Th, 397 ChemFizz
Professor:
Dr. J. Goldsmith
Office: 311 Davis Marksbury Building
Office Hours: Mondays 2-3, Tuesdays 1:30-2:30,
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). Note that the book is overpriced. You can acquire a cheaper version by looking at the previous edition.
Grading:
There will be biweekly homeworks due Tuesdays 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 Tuesdays at the beginning of class on: Jan. 23th, Feb. 6th, 20th, Mar. 27th, April 10th, and 24th.
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 |
|---|---|---|
| Jan. 11 | Math review, proofs; strings, languages | 0 |
| Jan. 16--18 | Turing machines | 3 |
| Jan. 23--25 | TMs, Church-Turing thesis, RAMs | 3 |
| Mar. 30--Feb. 1 | Time and space complexity | 7 |
| Feb. 6--8 | Nondeterminism, NP, reductions | 7, 5.3 (ish) |
| Feb. 13--15 | Decidability, Halting Problem | 4 |
| Feb. 20--22 | Semi-decidability, reductions, completeness | 4 |
| Feb. 27 | Review | Old Practice Midterm and New Practice Problems |
| Mar. 1 | MIDTERM | |
| Mar. 6--8 | Finite automata | 1 |
| Mar. 11--18 | SPRING BREAK! | |
| Mar. 20--22 | DFAs, regular operations, NFAs, equivalence | 1 |
| Mar. 27--29 | Regular expressions, equivalence with FAs | 1 |
| Apr. 3--5 | Pumping Lemma, Myhill-Nerode Thm | 1.4 |
| Apr. 10--12 | CFGs, PDAs, equivalence | 2 |
| Apr. 17--19 | Ambiguity, Pumping Lemma, nondeterminism | 2 |
| Apr. 24--26 | 2-stack automata, review of complexity | 2 |
| Practice exam | ||
| April 30th | FINAL: Monday, April 30, 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:
|
webmaster@cs.uky.edu
| This page last modified: January 2nd, 2018 |