Category: Uncategorized

I have taught a second semester course on discrete mathematics for several years. Early on, I would ask the following standard question on assignments when we got to asymptotic analysis.

Show that

One of the prerequisites for this course is Calc I, and so we cover big-O, big-theta, and big-omega with proof techniques based on the definitions (showing inequalities) as well as the limit method. The problem is that students would immediately try to apply the limit method (since it is simpler and easier to use than the definition) to this question and produce a proof something like the following.

Let and . Then we have that

Therefore, .

Which of course is completely wrong. First, the result is incorrect. The limit method actually shows that (that is, little-o), which implies big-O but precludes big-theta. However, indeed . The error in the supposed proof is an invalid calculus operation. Though the limit of a sum is equal to the sum of its limits, in this case the number of terms is not constant. The number of terms grows as so we cannot simply split the limits.

After a few semesters of continually getting these wrong answers, I changed the question. I gave it in two parts: the first part I gave them the typically incorrect proof and told them it was incorrect and asked them to identify why the proof was wrong. The second part asked them to prove the original inclusion using the definition-based proof. Most students were able to do the second part, but still far too many didn't understand why the limit proof was wrong.

Yet again, I changed the question. The first part changed so that I asked them to work through a limit proof for in which case the summation simplifies to

which is the well-known Gauss's formula and which is something that we go over in class several times when analyzing standard algorithms.

The intention was that when they go through the proof with the closed form using Gauss's formula, they'll get that which is incongruous with the original proof which shows that it is little-o.

Despite even this tweak, most students still do not get this question correct or struggle greatly with it. Some ignore the fact that we go over Gauss's formula multiple times; some lack the calculus rigor to see the problem, some are still struggling with trying to grasp the concept of asymptotic analysis.

I had always thought that presenting this question provided value in that it gave students an opportunity to avoid a common mistake and at the same get a deeper understanding by examining WHY the proof is wrong. I saw it as a sort of companion to the "bad" proof typically presented to students that (by hiding an invalid division by zero operation). However, I've slowly come to think that the question is far more trouble than it is worth. The only thing it succeeds in doing is getting every student to show up for office hours where I end up explaining the entire thing dozens of times. I could achieve the same thing by presenting it during lecture. Or, I could just get rid of the question altogether.

Developing good assignment and test questions can be one of the most difficult, challenging, and fun things to do when teaching a class. Most of my exams are open-book, open-note, and even open-computer. I don't like the type of questions that reward rote memorization or plug-and-chug type of work. I tend to prefer the type of question that has a very simple answer but you can only arrive at it by completely understanding the topic or thinking about it for a bit.

One particular type of question that I like is what I refer to as "Gomer" questions. In many areas of Computer Science, scenarios are often motivated by communication or interaction between Alice and Bob (A and B) sometimes with a malicious actor, Oscar. Gomer, however, is not malicious just incompetent if not well-meaning. I use "Gomer" as a reference to Gomer Pyle, the simpleminded auto mechanic played by Jim Nabors. Gomer has become a cultural stand-in for a simpleminded person and avoids the potential for offending students by choosing a more common name (nevertheless, the Oscars of the world will continue to be maligned as evil adversaries).

Gomer questions usually have the premise that Gomer has found a purported solution to a problem or a change or optimization to an existing algorithm or process, but he is inevitably wrong. The question then asks the student to consider Gomer's solution and find and explain the flaw. Gomer questions are similar to mathematical questions that ask the student to find a counterexample to some statement to demonstrate that the statement is false or flawed.

Here are two examples that I've used in some of my courses (solutions are left as an exercise).

From a Data Structures & Algorithms course:

Gomer has studied Strassen's matrix multiplication and thinks he has come up with a brilliant new breakthrough. He claims to have come up with a way to split an n x n matrix into 9 parts each 1/3 the original size and which only needs 6 recursive matrix multiplication operations. Is Gomer's improvement likely to be correct?

From a Cryptography course:

Gomer has written a secure, anonymous twitter app using RSA. His application uses a 1024-bit public RSA key. It works by taking a user's intended tweet (limited to 140 bytes), treating it as a single integer (taking the byte representation) and encrypting it using the 1024-bit RSA key. The message is then securely transmitted to Gomer's application server, decrypted, and posted to an anonymous twitter account. After the application goes live, it works great for the majority of posts, but sometimes decrypted messages are garbled. Identify the flaw in Gomer's application.

Gomer questions are great because they force a student to think about a problem indirectly by working through why a proposed solution doesn't work. Rather than forcing a student to come up with an original solution, it encourages them to break down an existing one, hopefully giving some insight into the nature of the problem.

Gomer questions are also good because it doesn't leave a student wondering if they are right or wrong about a solution. They are given a solution that they know is wrong and simply have to find the flaw. In fact, many Gomer questions can be developed by adapting wrong answers from students in previous semesters. This is nice because if a wrong answer tends to be common, you can prevent a large number of students from losing a lot of points while still getting the essential concept through to them.

Gomer questions are a nice departure from the usual type of questions because they make you think not about what a problem is, but instead, about what it isn't.