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 ...


18

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 ...


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

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

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

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

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

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

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 ...


8

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 ...


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 ...


6

It seems obvious, but from personal experience, the idea that you can estimate the median of a collection of items using a constant number of operations is a little shocking. And if that seems a little too technical, you can always convert it into a statement about polls an elections (you need 1300 people to get a sample with 3% error, regardless of the ...


5

Perhaps a good example (not directly related to computational complexity) is the Turing universality of simple computational models. For example the rule 110 is efficiently (weakly) universal: Given an (infinite) array of 0-1 (white-black) cells properly initialized and the simple substitution rules: we have a "working computer"! :-) For the definition ...


5

The kind of approach to theory of computation you describe is what I like to call an abstract machine based computability theory: i.e. a theory that define computable functions/languages/etc via some abstract kind of machine (automata, linear automata, Turing machine etc). An approach that uses $\lambda$-calculus instead of Turing machines could be thought ...


5

I think that - independently from the P vs NP question - the Cook-Levin theorem (and the related notion of NP-completeness) is another very good candidate; if you have an (efficient) solver for SAT then you have an (efficient) solver for any problem in NP .... and you can end up with something astonishing at least for me: solving $a x_1^2 + b x_2 + c = 0$ ...


5

Curiously, there is someone who argued that machine learning is uniquely fit among computer science topics to teach to high school students, because supposedly it is one of the few subfields where basic math can get you to understand enough to appreciate the important challenges. I disagree with this claim -- basic algorithms (say for searching, sorting) can ...


5

Here is a natural problem from graph theory where the proof and the algorithm are closely intertwined. In my view, one can discover this algorithm only via thinking about the proof and the algorithm "in parallel." The task is this: Input: An undirected graph. Task: Find a subgraph with maximum edge-connectivity. Note: What makes the task non-trivial is ...


4

This algorithm uses graph minimum cuts to classify large amount of unlabeled samples using only small amount of labelled samples. Its undergrad friendly. I have explained this to a few randomly chosen undergrads and they understood it. Ref: Blum, A., & Chawla, S. (2001). Learning from labeled and unlabeled data using graph mincuts. Self promotion ...


4

If I'm a student, I would've liked to learn more about other computational models (primarily, lambda calculus and recursive functions). More and more programming languages are incorporating functional features, and learning these subjects would give a great insight into this perspective of thinking about computation.


4

I see that Expectation Maximization (EM) has not been mentioned, and it's certainly "up there" in the top 10: http://www.cs.uvm.edu/~icdm/algorithms/10Algorithms-08.pdf .


4

A fun example and entertaining one is the undecidability of the tiling problem of Wang tiles. The result follows directly from the undecidability of the Halting problem by a simple simulation of Turing machines using Wang tiles. Interestingly, the undecidability of tiling problem for Wang tiles led to the beautiful result that there are tile sets that tile ...


4

There are several algorithms for estimating cardinality. This problem seems to be important enough in practice. For example, Redis, which describes itself as a ‘data structure server’, supports it. I suspect students would find this a good motivation. The algorithm that Redis uses, HyperLogLog, may be too difficult to analyze in an undergrad course. But, ...


3

A few good candidates off the top of my head: Every NFA has an equivalent DFA There exists a finite field of size $p$ or $p^i$ where $i \in \mathbb{N}$ and $i > 0$. Public key cryptography Calling to a function with encrypted arguments and receiving the desired result without revealing information about your inputs RSA encrpytion Reed-Solomon codes ...


3

favorites collected from here & elsewhere public key cryptography / RSA algorithm, trapdoor functions, Shannons counting argument showing most circuit functions are hard; re this mystery: 13.2 Most Functions Are Hard, But We Don’t Have Any Bad Examples To the everlasting shame of theoretical computer scientists everywhere, there is no known ...


3

heres one promising direction to go on this. AP/NSF recently announced a new high school advanced placement CS program initiative. there will be many advantages to using such a program such as a standardized lesson plan, college accreditation, etc. it is currently under development and to be ready for 2016. the tentative course syllabus and materials are ...


3

Actually, my students sometimes ask precisely this -- after spending a large chunk of the semester on finite automata and finally arriving at Turing machines. Why spend so much time on a weaker formalism when a stronger one is available? So I explain the inherent tradeoff in expressive power vs. analytic complexity. The richer models are typically more ...


2

Check out this book by Rudolf Lidl and Harald Niederreiter: Introduction to Finite Fields and its Applications (2nd edition, 1994) http://www.amazon.com/Introduction-Finite-Fields-their-Applications/dp/0521460948 Quoting the book description in Amazon: "The theory of finite fields is a branch of modern algebra that has come to the fore in recent years ...


2

Some have given great answers when it comes to how it relates to industry. What should be important is its scientific value, and Automata theory is often the doorway to first understand a higher tier of theory of computation in an undergraduate student's studies. Automata theory has a grand set of theorems that pop up all over the place in Theoretical ...


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