# Tag Info

343

I have personally enjoyed several Aha! moments from studying basic automata theory. NFAs and DFAs form a microcosm for theoretical computer science as a whole. Does Non-determinism Lead to Efficiency? There are standard examples where the minimal deterministic automaton for a language is exponentially larger than a minimal non-deterministic automaton. ...

33

There are many good theoretical reasons to study N/DFAs. Two that immediately come to mind are: Turing machines (we think) capture everything that's computable. However, we can ask: What parts of a Turing machine are "essential"? What happens when you limit a Turing machine in various ways? DFAs are a very severe and natural limitation (taking away ...

31

To add one more perspective to the rest of the answers: because you can actually do stuff with finite automata, in contrast with Turing machines. Just about any interesting property of Turing machines are undecidable. On the contrary, with finite automata, just about everything is decidable. Language equality, inclusion, emptiness and universality are all ...

27

State. you need to learn that one can model the world (for certain problems) as a finite state space, and one can think about computation in this settings. This is a simple insight but extremely useful if you do any programming - you would encounter state again and again and again, and FA give you a way to think about them. I consider this to be a sufficient ...

25

For a general audience you have to stick to things that they can see. As soon as you start theorizing they'll start up their mobile phones. Here are some ideas which could be worked out to complete examples: There is a surface which has only one side. A curve may fill an entire square. There are constant width curves other than a circle. It is possible to ...

24

Computer Science Unplugged addresses kids (and teachers) in primary school.

21

Fun way to learn $\lambda$-calculus: ...This game represents the untyped lambda calculus. A hungry alligator is a lambda abstraction, an old alligator is parentheses, and eggs are variables. The eating rule corresponds to beta-reduction. The color rule corresponds to (over-cautious) alpha-conversion. The old age rule says that if a pair of parentheses ...

21

Although it is not really the reason they were originally studied, finite automata and the regular languages they recognize are tractable enough that they have been used as building blocks for more complicated mathematical theories. In this context see particularly automatic groups (groups in which the elements can be represented by strings in a regular ...

18

You are asking (at least) two different questions: (a) What parts of theory build on finite automata nowadays? (b) Why were finite automata developed in the first place? I think the best way to address the latter is to look at the old papers, such as: Rabin, Scott, Finite Automata and Their Decision Problems, 1959 Here are the first two paragraphs: ...

17

You could try the notes from Madhu Sudan's course: Algebra and Computation

17

One idea is something simple from streaming algorithms. Probably the best candidate is the majority algorithm. Say you see a stream of numbers $s_1, \ldots, s_n$, one after the other, and you know one number occurs more than half the time, but you don't know which one. How can you find the majority number if you can only remember two numbers at a time? The ...

16

Another reason is that they're relatively practical theoretical models. A Turing machine, apart from the impossibility of the infinite tape, is kind of an awkward fit for what it's like to program a computer (note that this is not a good analogy to begin with!). PDAs and DFAs however are quite amenable to being models of actual programs in the sense that a ...

13

The volume of a unit sphere of dimension $n$ first grows as $n$ grows ($2,\pi,4\pi/3,\dots$) but starts decreasing for $n=6$ and eventually converges to $0$ as $n\to\infty$.

12

Maheshwari and Smid's Introduction to Theory of Computation is free, with a Creative Commons license. It has some computability and complexity theory as well but seems to be primarily on languages and automata.

11

One possibily path into abstract algebra could be to look at it from point of view of cryptography, which is about algorithms on finite field. Fields are rings, and fields are also two groups coupled by simple laws. Field theory uses vector spaces in prominent position (Galois theory), so this angle should cover a lot of abstract algebra. The book A ...

10

Chazelle, Liu, and Magen's paper Sublinear Geometric Algorithms (STOC 2003, SICOMP 2006) has several clever applications of the following random sampling trick. Variations of the same trick were previously used by Gärtner and Welzl [DCG 2001], who cite the first edition of CLR (1990). Suppose we are given a sorted circular linked list of numbers, stored in ...

10

There are $O(m^{3/2})$ triangles in any $m$-edge graph and that they can be found in $O(m^{3/2})$ time. There are many ways of doing this but I think one of the earliest is Itai and Rodeh (STOC 1977) who provide an algorithm that goes through a sequence of linear-time iterations, each of which removes a spanning forest from the graph. In the early iterations ...

10

Check out the "Living Binary Adder" Game here : http://courstltc.blogspot.com/2012/12/living-binary-adder-game.html I used to present this game to my students in the early chapters about DFA/NFA. It illustrates two important things in Automata Theory: How to transform a mental process into a simple mechanical one What abstraction really means. Two states, ...

10

A counter intuitive result from complexity theory is the PCP theorem: Informally, states that for every $NP$ problem $A$, there is an efficient randomized Turing machine that can verify proof correctness (proof of membership in $A$) using logarithmic number of random bits and reading only constant number of bits from the proof. The constant can be reduced ...

9

The concept of DFAs is very useful for designing efficient solutions to many types of problems. One example is networking. Every protocol can be implemented as a state machine. Implementing the solution this way makes the code simpler and simpler means a lower defect rate. It also means that changes to the code are easier and have a lower impact, again ...

9

In addition to the halting problem, I suggest discussing: Rice's Theorem. Some of the explanation on Wikipedia is a bit jargon-heavy, but it's generally not a hard theorem or proof to understand other than that; it has a lot of relevance to real-world concepts like anti-virus software. The proof is about as involved as the proof of the halting problem (...

9

One thing that proves to be counterintuitive for CS undergraduates, is the fact that one can select the $i$-th order statistics from an unsorted array of $n$ elements in $O(n)$ time. All of the students think they must first necessarily sort the array (in $O(n~lg ~n)$ time).

9

There are several ways to learn about type theory. For a working programmer, Types and Programming Languages by B. Pierce is a good start. Practical Foundations for Programming Languages by R. Harper might also be good. If you want a bit of easy to read background on operational semantics, I recommend G. Winskel's, The Formal Semantics of Programming ...

8

In my experience, it is not difficult to teach basic topics in combinatorics, graph theory, programming, algorithms and similar topics. You may want to look up topics covered in IOI competitions and national competitions. There are summer schools and workshops related to IOI competitions starting at quite early age. My personal favorite topic for such ...

8

Models of Computation — Exploring the Power of Computing by John E. Savage (Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 United States license).

8

Many countries organize summer schools for their IOI teams (consisting of high school students aged roughly 16 IIRC). The one we have in Iran used to have the following courses: programming, data structure and algorithms, combinatorics, and graph theory. I think ACM's Computer Science Teachers Association has a K12 curriculum on its Curriculum ...

7

In addition to the Heavy Hitters problem you've mentioned (which has quite a few algorithms: batch-decrement, space-saving, etc.), I'd consider presenting the following: Reservoir sampling - maintain a sample of $k$ elements, uniformly sampled from the set of items which appeared in the stream so far, in $O(k)$ space. Approximate bit counting on a sliding ...

7

building on MdBs answer/ angle, a classic result of something counterintuitive at the time of discovery in TCS at its foundations is the existence of (un)decidability itself. at the turn of the 20th century Hilbert, mirroring the thinking of other leading mathematicians of the time, thought that mathematics could be systematized (somewhat in the form of what ...

7

It's a wide field with a few quite different areas. I'd start with some of the most fundamental ideas about what computers are: Hopcroft and Ullman, "Introduction to Automata Theory, Languages and Computation." The reason I'd recommend that in particular, is their emphasis on proofs. They guide you through a rigorous way of thinking. That's the difference ...

6

There are class notes online. For example... http://valis.cs.uiuc.edu/~sariel/teach/notes/373/

Only top voted, non community-wiki answers of a minimum length are eligible