<p>The hard parts of this are hard for everyone, of course: P = NP (or not). But the others aren't too difficult to get across in a short period of time, especially if the students have something of a math background. </p>

<p>You can easily construct problems that grow exponentially and whose programs for solution must also grow at that rate. <strike>Drawing a completely connected graph for example and adding vertices.</strike>. Listing all of the permutations of n distinct elements, for example.  </p>

<p>The halting problem is great, of course, and you can often use a graphic to illustrate the problems: a machine that takes machines as one input and tapes as another. </p>

<p><a href="https://i.sstatic.net/33ICy.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/33ICy.png" alt="enter image description here"></a></p>

<p>But you can also convince students that <em>most</em> problems don't have solutions as there are only a countable number of computer programs given any finite character set. But the number of problems is uncountable. The fact that we know of only a few unsolvable problems is similar to the fact that we know only a few non-algebraic numbers, though most (again uncountably many) real numbers are not algebraic while only countably many are algebraic. </p>

<p>But laying out the broad outlines (feasible, non-feasible, non-computational) lets you say a few words about what we don't yet know and why CS, like math, isn't a fixed body of knowledge, but a field ripe for research. </p>

<p>You can even go a bit farther and talk about the issue that for some problems a solution is hard to find, but easy to check, which is fundamental to encryption. It is hard to find factors, but easy to check that they <em>are</em> factors once found. This gives you a way to talk about nondeterministic algorithms of which "repeatedly guess and check" is one variety. </p>

<p>One final idea that can be fun. Assuming you have already covered sorting to some extent, you can have the class, or small groups within the class, brainstorm the most inefficient sorting algorithm they can think of. But it needs to be an algorithm, not just randomness. But "Mix the values and check if sorted. Repeat until done." is actually an algorithm if your mixer is truly random. That is, it is guaranteed to sort. </p>

<p>If your students know some calculus, you can mention Newton's Method for finding zeros of a function. While it seldom gives you the exact value it is a process (pseudo algorithm) for guessing and then improving the guess in the next iteration. I say "pseudo algorithm" since it isn't guaranteed to terminate or to find an exact answer. But it is an improvement on pure "guess and check" </p>

<hr>

<p>A resource on Non Computability and its relation to self reference and recursion is this <a href="https://users.cs.duke.edu/~ola/papers/selfref2.pdf" rel="nofollow noreferrer">paper</a> by Owen Astrachan of Duke</p>

CC BY-SA 3.0
2017-12-10T19:32:20.873Z
_Drawing a completely connected graph for example and adding vertices._ — I think you need a better example. The time to add a vertex and all its incident edges to a complete graph grows **linearly** with the number of vertices, not exponentially.  Drawing a complete graph takes time **quadratic** in the number of vertices, assuming each edge can be drawn in constant time.  Even if the time to draw an edge scales linearly with its length, and the vertices are evenly spaced on a circle whose radius is proportional to the number of vertices, drawing a complete graph takes "only" O(n^3) time.
JeffE
CC BY-SA 3.0
2017-11-20T14:20:45.910Z
Be careful with naming things: In english “halt” is a verb. If you say halt, you are giving an order. To discover if someone can halt, you would ask “Can you halt?”. In OO programming we could write `if ( program(s).withInput(s).willHalt() ) {loopForever()}else{return true;}`.
ctrl-alt-delor
CC BY-SA 3.0
2017-11-19T23:05:02.280Z
2017-12-10T21:36:58.187Z
2017-12-10T21:36:58.187Z
Buffy
<p>I have one experience of introducing students with computability and complexity, in one 2-hour lecture. These <em>students</em> are a bit unusual maybe: They are secondary teachers in some scientific field (maths, physics, etc.), most of them quite new to CS and programming. The lecture is part of a larger set of lectures, where they get some intuitions about algorithms and their complexity.</p>
<p>Below is my course outline, which is by no means perfect but may give some ideas. It is very dense for a 2-hour lecture. Many concepts are not formally defined but I rely a lot on their intuition and their (very limited) programming experience.</p>
<ol>
<li><p>Computability</p>
<ul>
<li>What does it mean to <em>compute</em>?
<ul>
<li>Many formalizations, that happen to be equivalent</li>
<li>Choice of Python-like pseudo-code as the model</li>
</ul>
</li>
<li>Vocabulary: algorithms (=object in the model), partial function, decision problem, computable problem</li>
<li>Algorithms as data, and existence of a universal algorithm (admitted)</li>
<li>There exist uncomputable functions, by (un)countability (since some of the students knew the notion)</li>
<li>The halting problem is undecidable: proved within the Python-like formalism</li>
<li>Presentation of the Turing Machine model, using mainly examples</li>
</ul>
</li>
<li><p>Complexity</p>
<ul>
<li>Complexity of an algorithm <em>versus</em> complexity of a problem</li>
<li>Idea of grouping problems by <em>difficulty</em> into <em>complexity classes</em></li>
<li>Classes P (polytime alg.) and NP (polytime verification alg.)</li>
<li>Notion of reduction, NP-completeness and Cook-Levin Theorem (admitted)</li>
<li>P = NP ?</li>
</ul>
</li>
</ol>

CC BY-SA 4.0
2021-05-30T20:26:16.057Z
Yowsers - that really *is* a lot.  Do you have any notion of how much is absorbed/retained?
Ben I.
CC BY-SA 4.0
2021-05-31T11:10:31.303Z
Not much probably... Yet the goal may differ from other teaching situations. The main goal is that these teachers are exposed to the concepts and to the global picture. Later they may have to introduce at least some of this content to pupils, and they can refer to my lecture notes and other sources I gave to absorb the content they need, digest it before they restore it class.
Bruno
CC BY-SA 4.0
2021-05-27T15:27:04.697Z
2021-05-27T15:27:04.697Z
Bruno
<p>I was a software engineer (not a computer scientist), I have self-taught CS, some of it recently. I now teach computing.</p>
<p>One of the things I have learned as a teacher is not all knowledge should come from the teacher. It is better to get the students to do some activity, to actively learn.</p>
<p>A few years ago I saw two videos, one on the halting problem. One on NP, it was the busy beaver problem. The first <span class="math-container">$O(x) &gt; O(n!)$</span>, that I had seen.</p>
<p>Therefore get the students to watch the videos for homework, then to solve Busy beaver for n&lt;=4, and spend an hour on n=4 (I think it is 4 that can be done in less than an hour. And 5 would take years on the fastest computer. But you should check.) In class discuss the findings, and then get them to act out the parts of the machine in the halting proof. Then discuss that.</p>
<p>Below are links to the two videos that helped me.</p>
<ul>
<li><a href="https://www.youtube.com/watch?v=CE8UhcyJS0I" rel="nofollow noreferrer">Busy beaver</a></li>
<li><a href="https://www.youtube.com/watch?v=92WHN-pAFCs" rel="nofollow noreferrer">Halting problem</a></li>
</ul>
<p>Busy beaver is very simple, yet its big-O is higher than super-exponentiation.</p>
<hr />
<p>Note: Be careful with the halting problem. I keep hearing it said that it is impossible to determine if a program halts. This is clearly not true, for we have done it (here I mean: we = you and me). It should be stated that “it is impossible to determine, in the general case, if a program halts.” That is it is impossible to make a program/machine that will be able to tell you if a program/machine halts, that will work for all program/machine inputs.</p>

CC BY-SA 4.0
2021-03-07T16:08:23.923Z
Interesting. Can you please elaborate on "This is clearly not true, for we have done it (here I mean: we = you and I)," pretty please.
kate
CC BY-SA 4.0
2021-04-06T22:10:08.457Z
@Kate will `while True: pass` halt. Will `print ("Hello, world")` halt? We can tell if a well writer program can halt. The proof is not saying that we should give up on writing well written programs. It is saying that there are some algorithms that can not be written e.g. one that can tell us for all p(i), where p is a program and i is its input, will p(i) halt.
ctrl-alt-delor
CC BY-SA 4.0
2017-11-20T14:12:28.610Z
2021-05-26T15:31:48.740Z
2021-05-26T15:31:48.740Z
ctrl-alt-delor
<p>Essential Understanding 4.2 of the AP CS Principles curriculum is as follows: "Algorithms can solve many, but not all, computational problems." Among the topics I am expected to cover in the context of this standard are algorithms that run in a reasonable time v. those that don't, the difference between solvable and unsolvable problems, the use of a heuristic, and the existence of undecidable problems.</p>

<p>My plan is to cover the 0/1 knapsack problem, the heuristic of a greedy algorithm, and the halting problem. This is a relatively small part of the course and is assessed by only a couple of multiple-choice questions on the AP Exam, so I don't need more than one lesson (or two) of material. </p>

<p>That said, I am afraid any one-day lesson will be inevitably reductive as these are complex topics. Moreover, the students are new to programming and computer science in general, so I need to balance abstract with theory with concrete, relevant examples.</p>

<p><strong>What lesson ideas, examples, and/or analogies do well to serve the teaching of this standard?</strong></p>

CC BY-SA 3.0
2017-11-20T00:19:10.693Z
What does the knapsack problem have to do with undecidability? A high computational complexity is radically different from undecidability. I fear that by teaching them together, you're going to confuse the students into thinking that exponential-worst-case problems are unsolvable, even though they get solved daily (e.g. in compilers).
Gilles 'SO- stop being evil'
CC BY-SA 3.0
2017-11-20T00:41:32.513Z
I edited my question title. In the context of the curriculum, the topics of complexity and undecidability go together standards-wise. They are sub-categories of the EU quoted above. Given their importance relative to other topics and the limitations of time, I’d like to transition from complexity to undecidability in the context of a single lesson if possible.
Peter
<lesson-ideas><algorithms>
How do I construct a basic lesson on computational complexity and undecidability?
# How do I construct a basic lesson on computational complexity and undecidability?

(Asked by: username_0 on 2017-11-19)

Essential Understanding 4.2 of the AP CS Principles curriculum is as follows: "Algorithms can solve many, but not all, computational problems." Among the topics I am expected to cover in the context of this standard are algorithms that run in a reasonable time v. those that don't, the difference between solvable and unsolvable problems, the use of a heuristic, and the existence of undecidable problems.

My plan is to cover the 0/1 knapsack problem, the heuristic of a greedy algorithm, and the halting problem. This is a relatively small part of the course and is assessed by only a couple of multiple-choice questions on the AP Exam, so I don't need more than one lesson (or two) of material.

That said, I am afraid any one-day lesson will be inevitably reductive as these are complex topics. Moreover, the students are new to programming and computer science in general, so I need to balance abstract with theory with concrete, relevant examples.

**What lesson ideas, examples, and/or analogies do well to serve the teaching of this standard?**

**Tags:** lesson-ideas, algorithms

> **Comments:**
> **username_1**: What does the knapsack problem have to do with undecidability? A high computational complexity is radically different from undecidability. I fear that by teaching them together, you're going to confuse the students into thinking that exponential-worst-case problems are unsolvable, even though they get solved daily (e.g. in compilers).  
> **username_0**: I edited my question title. In the context of the curriculum, the topics of complexity and undecidability go together standards-wise. They are sub-categories of the EU quoted above. Given their importance relative to other topics and the limitations of time, I’d like to transition from complexity to undecidability in the context of a single lesson if possible.  

---

## 3 answers

### Answer by username_2 on 2017-11-19. Score: 6

The hard parts of this are hard for everyone, of course: P = NP (or not). But the others aren't too difficult to get across in a short period of time, especially if the students have something of a math background.

You can easily construct problems that grow exponentially and whose programs for solution must also grow at that rate. Drawing a completely connected graph for example and adding vertices.. Listing all of the permutations of n distinct elements, for example.

The halting problem is great, of course, and you can often use a graphic to illustrate the problems: a machine that takes machines as one input and tapes as another.

[![enter image description here](https://i.sstatic.net/33ICy.png)](https://i.sstatic.net/33ICy.png)

But you can also convince students that *most* problems don't have solutions as there are only a countable number of computer programs given any finite character set. But the number of problems is uncountable. The fact that we know of only a few unsolvable problems is similar to the fact that we know only a few non-algebraic numbers, though most (again uncountably many) real numbers are not algebraic while only countably many are algebraic.

But laying out the broad outlines (feasible, non-feasible, non-computational) lets you say a few words about what we don't yet know and why CS, like math, isn't a fixed body of knowledge, but a field ripe for research.

You can even go a bit farther and talk about the issue that for some problems a solution is hard to find, but easy to check, which is fundamental to encryption. It is hard to find factors, but easy to check that they *are* factors once found. This gives you a way to talk about nondeterministic algorithms of which "repeatedly guess and check" is one variety.

One final idea that can be fun. Assuming you have already covered sorting to some extent, you can have the class, or small groups within the class, brainstorm the most inefficient sorting algorithm they can think of. But it needs to be an algorithm, not just randomness. But "Mix the values and check if sorted. Repeat until done." is actually an algorithm if your mixer is truly random. That is, it is guaranteed to sort.

If your students know some calculus, you can mention Newton's Method for finding zeros of a function. While it seldom gives you the exact value it is a process (pseudo algorithm) for guessing and then improving the guess in the next iteration. I say "pseudo algorithm" since it isn't guaranteed to terminate or to find an exact answer. But it is an improvement on pure "guess and check"

---

A resource on Non Computability and its relation to self reference and recursion is this [paper](https://users.cs.duke.edu/~ola/papers/selfref2.pdf) by Owen Astrachan of Duke

> **Comments:**
> **username_4**: Be careful with naming things: In english “halt” is a verb. If you say halt, you are giving an order. To discover if someone can halt, you would ask “Can you halt?”. In OO programming we could write `if ( program(s).withInput(s).willHalt() ) {loopForever()}else{return true;}`.  
> **username_3**: _Drawing a completely connected graph for example and adding vertices._ — I think you need a better example. The time to add a vertex and all its incident edges to a complete graph grows **linearly** with the number of vertices, not exponentially.  Drawing a complete graph takes time **quadratic** in the number of vertices, assuming each edge can be drawn in constant time.  Even if the time to draw an edge scales linearly with its length, and the vertices are evenly spaced on a circle whose radius is proportional to the number of vertices, drawing a complete graph takes "only" O(n^3) time.  

---

### Answer by username_5 on 2021-05-27. Score: 3

I have one experience of introducing students with computability and complexity, in one 2-hour lecture. These *students* are a bit unusual maybe: They are secondary teachers in some scientific field (maths, physics, etc.), most of them quite new to CS and programming. The lecture is part of a larger set of lectures, where they get some intuitions about algorithms and their complexity.

Below is my course outline, which is by no means perfect but may give some ideas. It is very dense for a 2-hour lecture. Many concepts are not formally defined but I rely a lot on their intuition and their (very limited) programming experience.

1. Computability

   * What does it mean to *compute*?
     + Many formalizations, that happen to be equivalent
     + Choice of Python-like pseudo-code as the model
   * Vocabulary: algorithms (=object in the model), partial function, decision problem, computable problem
   * Algorithms as data, and existence of a universal algorithm (admitted)
   * There exist uncomputable functions, by (un)countability (since some of the students knew the notion)
   * The halting problem is undecidable: proved within the Python-like formalism
   * Presentation of the Turing Machine model, using mainly examples
2. Complexity

   * Complexity of an algorithm *versus* complexity of a problem
   * Idea of grouping problems by *difficulty* into *complexity classes*
   * Classes P (polytime alg.) and NP (polytime verification alg.)
   * Notion of reduction, NP-completeness and Cook-Levin Theorem (admitted)
   * P = NP ?

> **Comments:**
> **username_6**: Yowsers - that really *is* a lot.  Do you have any notion of how much is absorbed/retained?  
> **username_5**: Not much probably... Yet the goal may differ from other teaching situations. The main goal is that these teachers are exposed to the concepts and to the global picture. Later they may have to introduce at least some of this content to pupils, and they can refer to my lecture notes and other sources I gave to absorb the content they need, digest it before they restore it class.  

---

### Answer by username_4 on 2017-11-20. Score: 2

I was a software engineer (not a computer scientist), I have self-taught CS, some of it recently. I now teach computing.

One of the things I have learned as a teacher is not all knowledge should come from the teacher. It is better to get the students to do some activity, to actively learn.

A few years ago I saw two videos, one on the halting problem. One on NP, it was the busy beaver problem. The first $O(x) > O(n!)$, that I had seen.

Therefore get the students to watch the videos for homework, then to solve Busy beaver for n<=4, and spend an hour on n=4 (I think it is 4 that can be done in less than an hour. And 5 would take years on the fastest computer. But you should check.) In class discuss the findings, and then get them to act out the parts of the machine in the halting proof. Then discuss that.

Below are links to the two videos that helped me.

* [Busy beaver](https://www.youtube.com/watch?v=CE8UhcyJS0I)
* [Halting problem](https://www.youtube.com/watch?v=92WHN-pAFCs)

Busy beaver is very simple, yet its big-O is higher than super-exponentiation.

---

Note: Be careful with the halting problem. I keep hearing it said that it is impossible to determine if a program halts. This is clearly not true, for we have done it (here I mean: we = you and me). It should be stated that “it is impossible to determine, in the general case, if a program halts.” That is it is impossible to make a program/machine that will be able to tell you if a program/machine halts, that will work for all program/machine inputs.

> **Comments:**
> **username_7**: Interesting. Can you please elaborate on "This is clearly not true, for we have done it (here I mean: we = you and I)," pretty please.  
> **username_4**: @Kate will `while True: pass` halt. Will `print ("Hello, world")` halt? We can tell if a well writer program can halt. The proof is not saying that we should give up on writing well written programs. It is saying that there are some algorithms that can not be written e.g. one that can tell us for all p(i), where p is a program and i is its input, will p(i) halt.  

---

