When students are wrong but have a valid point, encourage them
Computational Complexity 2018-03-12
I often have the class VOTE on a statement (the choices are usually TRUE/FALSE/UNKNOWN TO SCIENCE/Stewart-Colbert-2020)
I ask the students who voted incorrectly (some say anything except Stewart-Colbert-2020 is an incorrect vote, though I'm partial to Bee-Oliver, though John Oliver was not born in this country so he's not eligible, though our current president might say that neither was Obama so thats not a bar to the presidency) why they vote the way they do to get a good discussion going. I give some examples. I use real first names but decided to not give last names for reasons of security. The people involved all agreed. If you have examples of students being WRONG but HAVING A POINT, leave an intelligent comment about it!
1) In Discrete Math they vote on: is Q, the rationals, countable?One of the NO votes was named Alice (really!).
Alice: The rationals, like there are SO many of them. They are just so crammed in their. I mean really!
Bill: I think you want to say that between any two rationals is a rational.
Alice: Thats what I said!!
Bill: Great! And realize that a set is countable if there is a bijection from the set to N. So what you are really saying is-----
Alice: There is a bijection between N and Q but not an order preserving Bijection!
2) In Formal Lang theory they vote if alpha is a reg expression and L(alpha) is the lang generated by alpha then is there a reg exp beta such that L(beta) is the complement of L(alpha). One of the NO votes was named Andrea (nickname Andy).
Andy: Given alpha I just don't see an easy way, or for that matter any way, to create beta.
Bill: I will soon prove that regular expressions are equivalent to DFA's. So what one would do is take the L(alpha), form the DFA, complement the DFA, then convert back to a regular expression.
Andy: Oh, yes that works, but it seems complicated.
Bill: It is! You though it would be complicated so it was false. Even though its true, your intuition that its complicated is correct! In fact, there are reg expressions of length n such that the complement lang has a rather large reg expression.
3) Formal Lang theory again. Not a vote this time. I had on the board the regular expression
(a UNION b)(a UNION b )^*
A student Dolapo thought it could be simplified:
Dolapo: Can't you write that as the regular expression (a union b)^+ ?
Bill: Yes and no. Yes the lang is (a UNION b)^+, but + is not allowed in regular expressions.
Dolapo: Why not?
Bill: First off, they really could have been defined that way and perhaps should have. So why weren't they? I go with historical accident, but some people disagree- see my blog post here