Learn more Learn more

Upcoming Deadlines

Recent Discussions

Browse all discussions »

Announcements

Course is Graded

I have generated grades for the class and authorized Coursera to mail statements to people who earned them. Approximately 300 got a regular SoA, and almost 300 additional people got the SoA with distinction. Thanks to all who participated, especially to those who helped others with problems that were posted on the forum. I hope everyone got from this course something that will serve them well in the future, whether or not they did enough work to earn a SoA.
Thu 12 Nov 2015 10:41 PM CET

Final Exam Deadline Extended

Several people have been surprised by the deadline for the final. While I do not have much sympathy for this situation, since the schedule was clearly indicated, I also see no harm in extending the deadline for 2 days. I have therefore set the true deadline to Tuesday Nov. 10, 11:59PM PST (GMT -8:00).
Mon 9 Nov 2015 8:04 PM CET

Schedule for Course Wrapup

All homeworks, up to and including the homework on Turing machines (week-5 homework) have a soft deadline 16 days after they were released and a hard deadline of Monday Oct. 26, 2015, 11:59PM. The last homework, on NP-completeness (week-6 homework) has both a hard and soft deadline of Sunday Nov. 1, 2015, 11:59PM, just before the final opens. Note that after the hard deadline for a homework, you are able to see the solutions to the questions, but you cannot see them before, which is why we are giving people a week between (most of) the hard deadlines and the final.

The final is a 3-hour exam, covering the material in the entire course. You will have a one week period in which to open it, but once you open it, it closes 3 hours later, so make sure you don't open it until you have 3 consecutive free hours. The 1-week window will begin Monday Nov. 2, 2015, 00:01AM and end Monday Nov. 9, 2015, 00:01AM. Remember that these times are GMT -8:00. Note: the exam is "open book," in the sense that you can use any materials such as class videos or Wikipedia, while you take the final. However, since the exam time is limited to 3 hours, you do not want to spend too much time learning the material during the time you are taking the final. You really need to get things straight before you begin.

Statements of Accomplishment will be emailed to all who score at least 50% of the marks. Recall that half the marks are your combined score on the seven homeworks, and the other half come from the final exam. For distinction, you need 90% of the marks, but each programming project done successfully gives you a 5% bonus.

Sat 24 Oct 2015 9:01 AM CEST

Challenge Problems 5

Problem 1
The Chain-Selection Problem is: given

1. A budget m,
2. A target t,
3. A directed graph G that consists of disjoint chains only (a chain is a sequence of nodes n_1, n_2,...,n_k, such that the only arcs among these nodes are from n_i to n_{i+1}, for i = 1, 2,..., k-1), and
4. A value v_i for each node n_i,

can we select m nodes, whose values sum to at least t, subject to the constraint that if we select a node, then we must select its predecessor, if any, in its chain?

Example: An example of a chain graph has nodes 1, 2,..., 10 and arcs 1→2, 2→3, 3→4, 6→7, 7→8, 8→9, and 9→10. The chains are 1-2-3-4, 5, and 6-7-8-9-10. In this graph, with a budget of 4, we could choose nodes {1, 2, 5, 6}, or {6, 7, 8, 9}, for example, but we could not choose {1, 2, 7, 8}, because it is not permitted to choose 7 without choosing its predecessor 6 in its chain.

Your question: Is the Chain-Selection Problem NP-complete or is it in P? Either give a reduction to show it is NP-complete or give a polytime algorithm to solve it.

Aside: This problem actually surfaced recently as a problem about materialized-view selection in databases. However, we can see it as one of choosing items to purchase in an environment where it doesn't make sense to purchase one item until you have purchased all the previous items on a chain. For instance, one chain might be "a TV" → "cable service" → "high-def decoder box." It doesn't make sense to buy cable service if you have no TV, and it doesn't make sense to get a decoder box unless you have cable service.

Problem 2
The Quadratic Allocation Problem is: given

1. Nonnegative integers a and b,
2. A list of integers i_1, i_2,..., i_k, and
3. An integer limit l (ell),

can we select a subset of the integers on the list i_1, i_2,..., i_k, such that the sum of ai+bi^2 over all selected integers i equals the limit l? Note: all integers are assumed represented in binary for this problem.

Is the Quadratic Allocation Problem NP-complete or is it in P? Either give a reduction to show it is NP-complete or give a polytime algorithm to solve it.

Aside: This problem arose during some consulting I was doing, where the integers represented the sizes of different software jobs, and the quadratic term is there because the cost of implementing software goes up faster than linearly with the size of the job.

We'll post hints for both these problems on the Challenge-Problem forum.
Mon 19 Oct 2015 9:01 AM CEST

Materials for Week 6

We're in the home stretch, with one important topic to learn: "NP-completeness," or more properly the "theory of intractable problems." There are three videos for this week. In the first, number 20, we use the Turing machine to define what it means to solve a problem in some polynomial amount of time. A key fact is that, although the Turing machine can be much slower than a real computer, it can only be *polynomially* slower. That means the answer to the question of whether a given problem can be solved in polynomial time has the same answer whether our model of computation is a Turing machine or a real computer. Video 20 also introduces the important class of problems NP. These are the problems that can be solved by a nondeterministic TM in polynomial time. It appears that at least some problems in NP require exponential time on a real computer or deterministic TM, but we don't know that is the case -- and thereby hangs the mystery of the theory of intractable problems.

Also in Video 20 we meet the idea of a polynomial-time reduction, a way to show that if one problem (say a problem in NP) has a polynomial-time algorithm, then another does. That gives us the notion of an NP-complete problem -- one to which every problem in NP has a polynomial-time reduction. The essential property of NP-complete problems is that if any one of them has a polynomial-time solution, then everything in NP has a polynomial-time solution. Since it appears that no NP-complete problem has a polynomial-time solution, a proof that a problem is NP-complete is almost-but-not-quite a proof that it cannot be solved in polynomial time. Commonly, we interpret a proof of NP-completeness as concluding the problem requires more than polynomial time.

In Video 21, we begin the process of proving certain real problems to be NP-complete. We start with Cook's theorem -- that the question of whether a Boolean expression is satisfiable (has an assignment of truth values to its variables that makes the expression true) is NP complete. Steve Cook proved this by showing how the language of any nondeterministic polynomial-time Turing machine could be reduced in polynomial time to the satistfiability problem.

Video 22 does the proof that two common problems: Node Cover and Knapsack are NP-complete. The proofs are by reducing SAT to each of these problems using a polynomial-time reduction.

A fourth video is a "problem session" from the earlier class; it addresses two common questions on undecidability and intractability.

There is a final homework for this session.  Both the hard and soft deadline are Sunday Nov. 1, just before midnight.  The reason for this schedule is to give you a reasonable amount of time to do the homework, and yet have the solutions posted before the final.

We have also posted a final set of challenge problems for you to consider. These let you try to apply what you learned about NP-completeness to decide if two problems that I encountered in my travels are NP-complete or have polynomial-time algorithms.
Sat 17 Oct 2015 9:01 AM CEST

Challenge Problems 4

Problem 1

Let L be the set of Turing machine codes M such that L(M) contains at least two strings. By Rice's theorem, L is not recursive. Show that L is recursively enumerable by constructing a Turing machine that accepts L. The description can be informal. Just remember to give the key ideas so the reader is convinced you understand how the TM works.

Problem 2

Devise an encoding with a finite alphabet for all context-free grammars with terminal alphabet {0,1}. Remember that CFG's may have any number of variables, so you will have to find a naming system for them. Incidentally, you can extend the encoding (but you don't have to in this problem) so the grammars may have any terminal alphabet. But since the encoding must use a finite alphabet, you would not be able to retain the identity of the terminal symbols. Thus, for example, {0n1n | n≥1} would look like the same language as {anbn | n≥1}. For most purposes that is not important. For example the test for emptiness of a CFL does not really depend on what the terminals are named.

Mon 12 Oct 2015 9:01 AM CEST

Materials for Week 5

In week 5 we finish the discussion of Turing machines and undecidability. Our goal is to show that certain problems cannot be solved by Turing machines, and therefore cannot be solved by computers in general (i.e., they are "undecidable"). We start with manufactured problems about Turing machines and use these to prove that some "real" problems -- those not posed simply as examples of undecidable problems -- are also undecidable. A key idea is that of "reduction" from one problem to another. If a problem P is known to be undecidable, and there is a way to use a hypothetical solution to another problem Q to solve P, then we have proved that Q is also undecidable.

There are only three videos this week, but they are in aggregate about as long as the four videos we have been showing in each of the past weeks. Video 17 explores Turing machine theory, showing that some obvious restrictions and obvious generalizations all define exactly the recursively enumerable (RE) languages. This video also looks at the two classes of languages defined by Turing machines: the RE languages and the recursive languages; the latter are languages defined by Turing machines that always halt. We show that each of these language classes have closure properties similar to those of the regular languages or context free languages -- with some differences, of course.

In video 18, we introduce our first undecidable problems, starting with a diagonalization over all Turing machines. Then, in video 19 we explore some real undecidable problems. We prove Rice's theorem, which lets us conclude that essentially everything about what Turing machines (or computer programs) do is undecidable. We introduce Post's Correspondence problem (PCP), a question that does not appear to have anything to do with computation, and prove PCP is undecidable. Finally, we use PCP to prove some questions about CFG's are undecidable; an example is whether a CFG is ambiguous.

There is one new homework for this week, and we'll offer another challenge-problem set (optional).

Finally, there is a third problem-session video, discussing the "HALF" problem and some points that were raised in the discussion forum from the first offering of the class.
Sat 10 Oct 2015 9:01 AM CEST

Materials for Week 4

We continue with our study of context-free languages this week, and we'll also start the subject of Turing machines. Video 13 finishes up pushdown automata, with the proofs that they can be used to define all and only the context-free languages. Video 14 is devoted to the pumping lemma for CFL's, and 15 covers both closure and decision properties.

Then, video 16 introduces Turing machines. The Turing machine is the common model for what it means to be able to compute something, and they have played this role since before there were computers. We give the definition of this type of automaton, but most of the time is spent talking about some subtle points necessary to understand what Turing machines can and cannot do: the fact that everything can be encoded as integers or binary strings, and the difference between Turing machines that are guaranteed to halt on any input and those that are not.

There is a new homework, and a second optional programming project. The latter is based on the CYK algorithm for deciding whether a string is a member of a CFL, as discussed in video 15.
Sat 3 Oct 2015 9:01 AM CEST

Challenge Problems 3

Problem 1:

Arithmetic expressions with operator + and parentheses can be generated by the grammar

E -> E+E | (E) | a

where a  is intended to represent any number.  A typical string in the language is a+(a+a).  This grammar is ambiguous.

(a) Give an example of a string that has two or more leftmost derivations or parse trees.
(b) Design an unambiguous grammar for the same language.

Problem 2:

The operation HALF(L), discussed in a previous challenge problem, is { w | for some x with the same length as w, wx is in L}. While regular languages are closed under HALF, CFL's are not. Give an example of a CFL L such that HALF(L) is not a CFL. Prove that your language L is a CFL by describing a CFG or PDA for L. Prove that HALF(L) is not a CFL by whatever means you find appropriate, e.g., using the pumping lemma and/or applying some CFL-preserving operation to HALF(L) to produce a language known not to be a CFL. We'll provide a hint later on the forum for challenge problems.
Mon 28 Sep 2015 9:01 AM CEST

Materials for Week 3

This week, we introduce context-free grammars (CFG's). These grammars define the context-free languages (CFL's), a superset of the regular languages. They are an important tool in both compiler construction and in natural-language processing.

In Video 9, we introduce the CFG notation and the related Backus-Naur Form (BNF) notation used to describe most programming languages' syntax today. Video 10 teaches about parse trees and the problem of ambiguity. Video 11 covers simplifications of CFG's -- ways to eliminate certain problematic structures in grammars. Finally, in Video 12, we meet the pushdown automaton, a finite automaton with an additional memory capability: a stack data structure. These automata recognize exactly the CFL's, as we shall learn in week 4.

There is one new homework for week 3, and we are also making available a "Problem Session" that was conducted by Zhu ChenGuang the first time this course was offered.

We also will post two new challenge problems in the class announcements, Monday morning 9/28/15. They are not graded, but you can discuss them on the Forum created for this purpose.

Incidentally, class registration is still open, but closes at the end of week 3. So if you have a friend who was planning to jump in late, tell them now is the time to jump in.
Sat 26 Sep 2015 9:01 AM CEST

Challenge Problems 2

This week, we have three challenge problems. The first is of medium difficulty, and the second is hard.  The third is very hard, and it doesn't really deal with automata.  Rather, it is something a few students got into last year, and it is a good opportunity to increase your understanding of dynamic programming algorithms, something that we will see in Week 4, as well as learning about recurrences and recursive algorithms.   Relevant background includes Ch. 2, Ch. 3, and Sect. 6.9 of the free on-line book i.stanford.edu/~ullman/focs.html

Problem 1:

Develop an algorithm that given:

1. A finite automaton A,
2. Two particular states p and q of A, and
3. A regular expression E,

tells whether there is any string in L(E) that takes state p to state q in A.

Problem 2:

Define HALF operation on a language L:

HALF(L) = {x | there exists a string y such that xy is in L and |x|=|y| }

Prove that if L is regular, so is HALF(L).

Example: if L = {0010, 10, 010}, then HALF(L) = {00, 1}. Note that 010, being of odd length, yields nothing for HALF. 0010 yields its first half: 00, and 10 yields its first half: 1.

Problem 3:

You probably know about Fibonacci numbers, where the n-th Fibonacci number F(n) is defined by F(0) = F(1) = 1, and F(n) = F(n-1) + F(n-2) for n≥2.  That is, the sequence of Fibonacci numbers starts 1, 1, 2, 3, 5, 8, 13,..., where each number after the first two is the sum of the previous two numbers.  If you write a function to compute F(n) using the definition, each call to F(n) winds up calling F twice, with arguments n-1 and n-2, and the result is a number of recursive calls that is exponential in n.  In fact, the number of calls will BE the n-th Fibonacci number.  But there is a more efficient dynamic-programming algorithm, where you fill in a table or array, whose n-th entry is F(n).  You can fill it in from low-to-high, until you have the entry for the value of n that you want.  As a warm-up, you could try writing this dynamic-programming algorithm and comparing its running time with that of the recursive algorithm.

But there is more to the story.  The straightforward dynamic programming algorithm takes a number of arithmetic steps that is linear in n to compute F(n).   It is truly remarkable that this is NOT the best way to compute large Fibonacci numbers.  In fact, it can be done in O(log n) arithmetic steps.  The technique is called "recursive doubling."  Here's an idea that does not work, but it might suggest an improvement that does.   Suppose we had a function Gk that, given F(n) for any n would compute F(n+k).  That is, Gk "advances" us from any Fibonacci number to the Fibonacci number that is k "down the line."   Suppose also, that we had a simple way to construct G2k from Gk.  Then by applying this construction logn times, we could get Gn, at least we could if n is a power of 2.  Then, we apply Gn to F(0), which is 1, to get F(n).  There are two things wrong.  First, G does not exist, and we cannot simply compute one Fibonacci number from another.  But there is something like G that can get us "down the line" from early Fibonacci numbers to later ones.  Second, n may not be a power of 2, so we need to fix up the algorithm to work for all n.  Have fun, and don't forget to put ideas on the Discussion Forum, but do not post the solution.
Mon 21 Sep 2015 9:01 AM CEST

Materials for Week 2

The materials for Week 2 will appear Saturday morning Sept. 19 (00:01 UTC -7:00). 

The materials for week 2 of Automata consist of four videos, two homework sets, an optional programming project, and an optional challenge problem set (which is in the form of a class announcement, NOT an email). The videos will finish the work on regular languages. In the first of these (video 5), we introduce regular expressions, and in video 6 we learn that the languages definable by regular expressions are all and only the regular languages. That is, regular expressions and finite automata of all kinds define the same languages.

Video 7 covers what are called "decision properties" of regular languages. We can answer many questions about the languages represented by regular expressions or finite automata that we cannot answer about programs in general. The existence of algorithms to do things like tell whether the language of a finite automaton is empty, or to find a minimum-state equivalent to a given finite automaton is one of the things that makes these automata so useful. Finally in the 8th video we learn about closure properties of regular languages: the fact that we can combine regular languages using many common operations,such as union or intersection, and get another regular language.

I apologize for giving a double homework this week, Because we allow essentially infinite tries, it is important that we bundle questions into groups of about 5. If we grouped them into smaller groups, you could just keep guessing A on each question until you were right. and if we grouped a larger number together, it would be too painful to repeat a whole set if you got one wrong. Thus, we cannot give the problems out in an exactly equal number each week. Since we are fairly liberal in setting deadlines, we hope you will not feel overwhelmed this week.

Also for your consideration is an optional programming project, involving code to translate from regular expressions to epsilon-NFA's, and a challenge problem about a certain regular languages. You are welcome to discuss these, and there are discussion forums for each.
Sat 19 Sep 2015 9:01 AM CEST

Important Course Survey

Stanford would appreciate your taking a survey when starting the automata course. Please go to short pre-course survey.

---- Jeff Ullman

Link to survey: https://stanforduniversity.qualtrics.com/SE/?SID=SV_enWZKK0uHnmCnop&a=42254b0b31d667f7a5a179c876e5bf3391f863af&c=415

Wed 16 Sep 2015 9:01 AM CEST

Challenge Problem 1

Here is the first challenge problem. Feel free to discuss, in the Forum devoted to Assignments, your ideas and solutions.

Let L be the language with alphabet {0, 1, 2} consisting of strings that do not have any three consecutive 0's, any three consecutive 1's, or any three consecutive 2's. Prove that L is a regular language (hint: design automata or regular expressions for some simpler languages and then use closure properties of regular languages to get L). Harder is to design a DFA A for which the language is L itself, but we encourage you try to design one as a second part of this exercise.

Note: this problem is optional and does not count toward your class score.
Mon 14 Sep 2015 9:01 AM CEST

Welcome to "Automata."

I want to welcome everyone to the free on-line automata course I have developed. First, I want to acknowledge the help of Zhu ChenGuang, without whose help I never would have been able to put these materials together. ChenGuang will be joining me as a "teaching assistant" for this course and will help in monitoring the class discussions. Both he and I will contribute comments when we think it is appropriate, but most of the time, participants will resolve their own discussions.

Homework


The course will have a number of homeworks that are designed using the Gradiance technology. The objective of these homeworks is to enable everyone to get 100% and learn the underlying material. While questions look like multiple choice, you should think of them as more conventional "solve this problem and submit the solution" questions. That is, you are given a problem to solve, which you should work completely. Then, you are given a random choice of responses that are designed to figure out whether you got the right solution or not. If you do have the right solution, you should be able to answer the question easily, regardless of the choices presented. If you get it wrong, you will be given a hint and allowed to try again. Your score on a homework is the maximum of any try. We group about 5 questions together, so you can't repeatedly guess each question independently, without actually doing the work.

The homework for each week will be made available on Saturday, 12:01AM, and due two Mondays (i.e., 16 days) later, 11:59PM.  All times are Pacific Time (GMT - 7:00 until November 1, when we go off daylight-savings time and it becomes GMT -8:00).  These times are what Coursera calls "soft deadlines," and need to be followed if you want full credit.  You can still get half credit by the "hard deadline," which will be Monday, Oct 26, 11:59PM for all but the last homework, which will be a few days later.

Videos

Each week you will have about 2 hours of video to watch, and either one or two groups of homework questions. The time taken by the videos is about half the time I took to deliver the same material in class. The reason the video goes faster than in-class presentation is that a lot of the "ums" and fumbling are edited out. The speed can be good, if the material is not dense or hard to follow. However, there will undoubtedly be points where the going is rough -- details of a proof or an algorithm. In those cases, I encourage you to take advantage of the fact that the lectures are on video, to repeat material, or pause it to stare at a slide for example. 

In the first week's videos, you will begin with an introduction to the whole course. I want to try to convince you of the value of learning the four big concepts that you can take away from this course: finite automata, context-free grammars, undecidable problems, and intractable problems (NP-completeness). The second video is an informal introduction to finite automata. Both these two first videos are "light," and I expect you to have little trouble. The third video introduces deterministic finite automata, and at this point we start to get more formal. In the fourth video, the important concept of nondeterminism is introduced. We learn the remarkable fact that despite the almost "magic" capability of nondeterminism, it does not add power to the finite automaton (although it does make description of many applications of automata a lot easier).

Statement of Accomplishment

To get a basic "statement of accomplishment," you need to get 50% of the marks. Half the marks come from the homeworks, and the other half from the final. You can even pass the course just by doing all the homework correctly.  Since you are allowed to make multiple tries, that is not impossible. However, the first time I gave this course, a number of people figured they could ignore the homework and just do the final. No one got 100% on the final, so please take the homework seriously.

Programming Assignments

There will also be two optional programming assignments. These do not affect your score for the basic statement of accomplishment.   However, for a SoA "with distinction," you need 90% on the homework and final combined, but you get a bonus of 5% for each of the programming assignments completed successfully (e.g., if you do both, then 80% on the homework + final gives you distinction).

Challenge Problems

Finally, we shall issue "challenge problems" after each week.  These do not count toward your score, but are worth considering.  Discussion on the class forum is welcome (but don't just publish the answer, please).

Sat 12 Sep 2015 9:01 AM CEST