Computer Science 456/656: Automata and Formal Languages
Fall 2000
Assignments
This page will be updated frequently.
Most recent update: November 28, 2000.
-
Background.
It is important for you to have taken the prerequisite courses,
MAT 351 and CSC 269.
-
Tuesday August 29, 2000.
Lecture: Basic mathematical concepts.
Chapter 1 of your textbook, pages 1-35.
-
Thursday August 31, 2000.
Lecture: Mathematical induction and recursive definitions.
Chapter 2 of your textbook, pages 36-68.
-
Tuesday September 5, 2000.
Lecture: Regular languages and finite automata.
Chapter 3 of your textbook, pages 71-99.
Assignment 1
will be due on Tuesday, September 5, in class.
-
Thursday September 7, 2000.
Lecture: Completion of discussion of regular languages and finite automata.
Chapter 3 of your textbook.
-
Tuesday September 12, 2000.
Assignment 2
will be due on Tuesday, September 12, in class.
Lecture: Nondeterminism.
Chapter 4 of your textbook, pages 100-134.
-
Thursday September 14, 2000.
Lecture: Continuation of the discussion on nondeterminism.
Chapter 4 of your textbook, pages 100-134.
-
Tuesday September 19, 2000.
Assignment 3
will be due on Tuesday, September 19, in class.
Lecture: Regular and Nonregular Languages.
Chapter 5 of your textbook, pages 135-160.
-
Thursday September 21, 2000.
Lecture: Criteria for Regularity.
Chapter 5 of your textbook, pages 135-160.
-
Tuesday September 26, 2000.
Lecture: Criteria for Regularity.
Chapter 5 of your textbook, pages 135-160.
Context-free Grammars. Context-free Langugues.
Chapter 6 of your textbook, pages 163-197.
-
Thursday September 28, 2000.
Assignment 4
will be due on Thursday, September 28, in class.
Lecture: Context-free Grammars. Context-free Langugues.
Chapter 6 of your textbook, pages 163-197.
-
Tuesday October 3, 2000.
Lecture: Context-free Grammars. Context-free Langugues.
Chapter 6 of your textbook, pages 163-197.
-
Thursday October 5, 2000.
Lecture: Context-free Grammars. Context-free Langugues.
Chapter 6 of your textbook, pages 163-197.
-
Monday October 9, 2000.
The TA will be in TBE B361 starting at about 11:00 and most of the afternoon,
and will give you back (graded) Assignment 4 if you go there to meet her.
-
Tuesday October 10, 2000.
Assignment 5
will be due on Tuesday, October 10, in class.
Examination.
There will be an examination on Tuesday, October 10, in class.
It will cover material up through, and including, Chapter 6 in your
textbook.
-
Thursday October 12, 2000.
Lecture: Push-Down Automata.
Chapter 7 of your textbook, pages 198-236.
-
Tuesday October 17, 2000.
Lecture: Push-Down Automata.
Chapter 7 of your textbook, pages 198-236.
-
Thursday October 19, 2000.
Lecture: Introduction to Turing machines and computability.
Every machine is equivalent to some Turing machine, so if no Turing
machine can do a computation, no machine can do that computation.
Chapter 9 of your textbook, pages 257-293.
-
Tuesday October 24, 2000.
Lecture: Review of Push-Down Automata, including parsing.
Chapter 7 of your textbook, pages 198-236.
-
Thursday October 26, 2000.
Lecture: Continuation of the discussion on Turing Machines.
Chapter 9 of your textbook, pages 257-293.
-
Tuesday October 31, 2000.
Assignment 6
will be due on Tuesday, October 31, in class.
Lecture: Continuation of the discussion on Turing Machines.
-
Thursday November 2, 2000.
-
Tuesday November 7, 2000.
-
Thursday November 9, 2000.
Assignment 7
will be due on Thursday, November 9, in class.
-
Tuesday November 14, 2000.
Examination.
There will be an examination on Tuesday, November 14, in class.
-
Thursday November 16, 2000.
Today we will discuss reduction and tractability.
-
Tuesday November 21, 2000.
Today I will hand back the graded examination, and discuss it.
In the remaining time, we will continue the discussion of complexity
theory and reduction.
This is the last class in the
easy portion of the course.
-
Tuesday November 28, 2000.
Today, I will define what it means for a language to be NP-complete.
If any single NP-complete problem is tractable, they all are, and P=NP.
-
Thursday November 30, 2000.
Today, I will introduce what is normally thought of as the "standard"
NP-complete problem, Boolean Satisfiability, and will prove that
it is NP-complete. It will be difficult to do this one proof in only
75 minutes, but I will do my best.
-
Tuesday December 5, 2000.
Today, I will introduce a number of classical NP-complete problems.
Originally, there were 14, but many more are known now.
It is important for you to be able to "intuit" that a given practical
problem is NP-complete, so that you will know that looking for a tractable
algorithm for the problem is hopeless. This will save you days, weeks,
even years of grief.
We will discuss the question of whether breaking RSA coding is tractable.
As you might imagine, this is a very important practical problem, as
RSA coding is used extensively.
-
Thursday December 7, 2000.
Assignment 8
will not actually be due on Thursday, December 7, in class.
But it would be a good idea to work it.
I'm sure we'll have something to talk about on the last day of class.
Perhaps I will will introduce the computational hierarchy, or define
Kolmogorov Complexity, or maybe even talk about Oracles.
-
Final Examination: Tuesday, December 12, 6:00 PM
-
Monday, December 18, 3:10 PM Final Grades are now
Ready. Please do not phone or stop by.
Send me email and I will respond
sometime tomorrow.

Back to
Course Page