28
$\begingroup$

I'm teaching a second year "Introduction to Theoretical Computer Science" course, and one of the skills/habits I've tried to instill in the students is to actually read definitions, take them seriously and go back to consult them when appropriate. This has been less successful than I would like. As I am very frequently seeing theory questions over at cs.stackexchange where "look at the definition!" is the natural answer, I don't seem to be the only one struggling with this.

Some example for situations I have in mind are:

  • A) I'm introducing right-linear grammars (where rules are of the form $T \rightarrow aU$) and context-free grammars (where the constraint is that rules have a single non-terminal on the left). Then I'm asking whether all right-linear grammars are context-free, expecting that students look at the two definitions are arrive at "obviously, yes". But a lot of them seem to instead try to remember whether I ever told them.
  • B) Students trying to learn all kinds of facts regarding the empty set by heart (e.g. $\emptyset \subseteq A$ is always true) rather than recognizing that these are just consequences of the general definitions.
  • C) Students feeling stuck questions like "If $A$ is $\mathrm{NP}$-complete and $A \leq_p B$, is $B$ necessarily $\mathrm{NP}$-complete?" while being a bit hazy about what $\mathrm{NP}$-complete means. I'd want them to look up the definitions of terms they are uncertain about before throwing their hands in the air.

What I've tried is just straight-on telling them that and how definitions are central, and that if in doubt, they should look at them. I reminded them of "look at the definition" when they asked questions of this nature. I promised them they could avoid having to learn plenty of stuff by heart if they'd only started at what the definitions say.

Are there any better techniques to get this point across? Or maybe some insight why this seems to be so difficult?

$\endgroup$
18
  • 4
    $\begingroup$ Isn't this more appropriately asked at Computer Science Educators Stack Exchange? (Related discussion at Meta.) $\endgroup$ Sep 8 at 11:20
  • 8
    $\begingroup$ @JoelReyesNoche I really don't see how, unless you want to argue that a root cause of the problem is that I am trying to teach students who enrolled for CS rather than students who enrolled for math. $\endgroup$
    – Arno
    Sep 8 at 11:28
  • 21
    $\begingroup$ @JoelReyesNoche Convincing students of the value of going back to definitions is arguably more central to Mathematics, than to Comp Sci, education. I think this question is apropos. the choice of example notwithstanding. $\endgroup$
    – ryang
    Sep 8 at 12:17
  • 4
    $\begingroup$ My answer at math.stackexchange.com/questions/1399781 might be useful for some students. $\endgroup$ Sep 8 at 17:07
  • 9
    $\begingroup$ They may have issues not only with definitions, but with applying logic. As for CS, the usual mantra is RTFM, which teaches a similar skill you want to teach. $\endgroup$
    – Rusty Core
    Sep 8 at 20:00

10 Answers 10

27
$\begingroup$

In my experience, students are often predisposed to "learn" by memorizing facts; that's how much of their early education worked, so that's what they're used to. When you give them a definition and then a bunch of consequences of the definition, they don't think "okay, I have a definition and then 87 examples of using the definition", they think "okay, I have 88 facts about this thing, and one of them is called 'the definition'." The definition is often the most abstract and complicated fact - which means that even if you tell them "the definition is the most important one", they'll instinctively avoid it if they possibly can. To give an example in a different context: say you're trying to write a program in Python, and you want to make a particular thing happen. Obviously, you could go back to fundamentals - if you're prepared to write machine code, you can make the computer do whatever the heck you want - but the way you're actually going to approach it is to Google the thing you want to do and find out which Python command does it.

To get students to make real use of a definition, you need to do two things. One is what it sounds like you're already doing - raise the importance of the definition above the other facts. I'd recommend, if you aren't doing it already, taking time to demonstrate solving problems in class where you explicitly demonstrate going back to the definition. Don't just pick out the relevant part of the definition, either: restate the whole definition, to demonstrate "this is what I reflexively do to solve the problem", and then identify the parts you actually need.

The second thing you need to do is demystify the definition. Don't let it be just another fact. For example, the formal definition of "NP-complete" might be phrased as (partially lifted from Wikipedia):

A decision problem C is NP-complete if it can be solved in polynomial time by a non-deterministic Turing machine, and furthermore every problem which can be solved in polynomial time by a non-deterministic Turing machine can be converted in polynomial time by a deterministic Turing machine into an instance of C.

But no one's going to use that definition. I'm no computer science researcher, but I doubt even the best in the field think about it this way except when they're actively writing a formal proof. For working with the ideas, it's better to phrase it like this:

A decision problem C is NP-complete if the solution can be checked easily, and every problem with easily-checked solutions can be easily phrased as an example of C.

This is a terrible definition in the literal sense, because it's very vague; but it conveys the idea well enough to make it easy to use. The example problem you gave, for example (if $A$ is NP-complete and $A \leq_p B$, is $B$ necessarily NP-complete) is much more approachable by this definition.

The way that I generally encourage this demystification is by asking not for the definition, but for what the term means. To many students, a "definition" is a thing they have to memorize. "What does X mean" is a thing they have to understand. It takes some work to get them there - you have to model paraphrasing things in a way that is loose but useable, and you have to demonstrate switching back to the precise definition when needed - but if you can get them thinking about what things mean, you'll see a lot of progress.

$\endgroup$
7
  • 1
    $\begingroup$ I imagined solving the problem in the classroom like: "We want to prove that every foobar is a barbaz. FIRST! Who can tell me: what is a foobar? look for raised hands SECOND! Who can tell me: what is a barbaz? look for raised hands. Good! Now how why are all <definition of foobars> <definition of barbazzes>?" $\endgroup$
    – user253751
    Sep 10 at 11:34
  • $\begingroup$ Yes, yes, and yes. $\endgroup$
    – ryang
    Sep 10 at 18:22
  • $\begingroup$ I don't think drawing parallels to Python programs is at all illustrative. Programs are designed deliberately to hide the underlying details for the sake of hiding them. You don't do that for math. $\endgroup$
    – Passer By
    Sep 12 at 0:55
  • $\begingroup$ @PasserBy I'm not sure I understand your point there - programs aren't intentionally designed to obscure their inner workings, except in cases where intellectual property protection is a concern. As far as I'm aware, when details are hidden, it's because things would be more difficult to understand or to use with the details present; just like how the formal definition of the real numbers (as the collection of Dedekind cuts of rational numbers) is technically correct but actively unhelpful to a student who's just learning about square roots. That's the connection I'm aiming to draw here. $\endgroup$ Sep 12 at 1:10
  • 1
    $\begingroup$ The difference being, there is more to hiding details for programs than alleviating the complexity. It's more than trying not to be unhelpful, it's actively helpful. It is encouraged to have your higher level program not depend on the inner workings of the lower level, to the point where hiding the details just so you won't use them is a good idea. $\endgroup$
    – Passer By
    Sep 12 at 1:17
16
$\begingroup$

First of all, you should test them on remembering the definitions.

Second, there are probably a significant number of your students who do not understand the definitions. Suppose you gave them an example of a grammar that was not right-linear and the definition of a right-linear grammar, and asked them why, according to the definition, the example grammar was not right-linear. Many of them would not be able to accomplish this task. You may have to teach them to do this task for various definitions and hope that they figure out how to do this for definitions where they have not been shown how to do it for that definition. In my experience, there are a few students who do not learn this skill in general. (In other words, suppose you give examples for various definitions throughout the course and, at the end, give the definition for a context-sensitive grammar and an example of a non-context-sensitive grammar, and ask why the grammar is not context-sensitive. There may be some students who simply still cannot point to the production that violates the rule.)

Third, many of your students probably have some trouble with basic logic. Probably not at the level where they could not compare the definitions of right regular grammar and context free grammar, but that might be at the edge of their logical capacities. In some students, this could be caused by a working memory capacity issue, where they really cannot remember both definitions simultaneously well enough to think about both of them at the same time. If you cannot do logic, it's much less useful to remember the definitions, because you cannot use them to conclude anything (since you also need logic to do that).

$\endgroup$
3
  • 4
    $\begingroup$ They have access to the definitions at all times, and I actually prefer instilling the habit of looking up a definition over them learning any of the definitions in my module by heart. But trying to break down the "look at it and its obvious" into smaller, even more obvious steps sounds like something I should try. $\endgroup$
    – Arno
    Sep 9 at 8:51
  • 10
    $\begingroup$ “I actually prefer instilling the habit of looking up a definition over them learning any of the definitions in my module by heart” — that sounds good, but can be limiting: for example, if you don't know the definition, you won't recognise a form of it when you come across one.  Memory can work two ways; lookup only one.  (For example, I initially avoided learning all the trigonometric formulas, as I could work them out from a few basic ones when needed.  I did badly in the following exams, because I didn't recognise cases where they could be applied in reverse…) $\endgroup$
    – gidds
    Sep 9 at 16:12
  • 3
    $\begingroup$ @Arno: I'm not sure breaking into smaller steps actually helps here. Fundamentally, a significant minority of my students have trouble applying modus ponens because separating out the facts P, P->Q, and Q is very hard for them, and making them use modus ponens more times makes things harder, not easier. $\endgroup$ Sep 9 at 19:12
8
$\begingroup$

You asked:

Students trying to learn all kinds of facts [...] by heart rather than recognizing that these are just consequences of the general definitions. [...] Are there any better techniques to get this point across? Or maybe some insight why this seems to be so difficult?

The answer is simply that the students are unable to do basic logical reasoning. They don't even understand that the statement "Every object of type $S$ is also an object of type $T$" is of the form "$∀x{∈}S\ ( \ x∈T \ )$", nor how to even start proving it, even though it is obvious to anyone with a rudimentary grasp of basic (first-order) logic that one can prove it using the following Fitch-style outline:

  Given any $x∈S$:
    [Possibly expand definition of $x∈S$ otherwise you know nothing about $x$.]
    ...
    [Possibly deduce definition of $x∈T$ otherwise you usually cannot conclude...]
    $x∈T$.

It should be obvious that you cannot possibly do anything if you didn't use any of the definitions of $S$ and $T$! But do students know that? And do teachers know that?

Ultimately, the only solution is for teachers of any mathematical subject to require every proof to be written in a logically structured format (whether or not Fitch-style). If students understand that we cannot consider something to be a proof unless it follows permitted logical deductive rules, then all your problems will vanish.

Also, students should be taught what definitions really mean, and observe that the simple example there is a theorem about odd naturals that cannot be proven without using the definition of "odd".

$\endgroup$
5
$\begingroup$

This is something I know very well from the other side, as an amateur student of maths for the last 40 years or so. In my experience, reading a definition and actually understanding it are two very different things. Once you understand the definition at a deeper level, you very often forget how hard it was to get to that point. It simply takes a certain amount of tedious grind, using what you know, to actually understand.

I blame to a very large extent the way maths is taught in school, where you too often focus on learning a handful of useful results, without really going into the fundamental understanding of the basics. This is what I call the 'accountant's mindset': you learn to use a number of ready-made tools that enable you to carry out routine tasks, that require no deeper understanding of what makes the tools work. I think the only cure is to keep going back to the definitions and emphasising how you use the definition and why they must be what they are.

I think it was Steve Awodey who once said that too much teaching focuses on 'what' when it was equally important, if not more, to talk about 'why': a definition tells what a concept is, but it doesn't excplain why it must be that way; very often, if you know the practical motivations behind the definition, you can easily construct it yourself - and use it where appropriate.

In the ideal world, one should always be able to draw a direct line from first principles to whatever you are working at; or rather, the opposite way: you should always be able to answer 'Why' with a reference back to definitions, and then on to 'what is the reason for that definition', etc all the way down to something like first order logic. If the reasoning stops at 'Theorem x.y.z', then you are an accountant in my book :-)

$\endgroup$
6
  • 2
    $\begingroup$ Some definitions are really just convention though. Many students would prefer a definition of "rectangle" which explicitly rules out squares. This is not the definition preferred by mathematicians, and this creates a struggle. At some point the student must just agree to use the definition which the mathematical community agrees to. $\endgroup$ Sep 9 at 12:01
  • 3
    $\begingroup$ Understanding why we have chosen the definitions we have chosen is a far more advanced skill, and (as Steven Gubkin points out) may require some mathematical maturity from the students to even be comprehensible. Also, not every definition is so fundamental that it needs a deep reason. Plenty of times it is indeed "defining it like this lets me prove Theorem x.y.z, so that's why I did it". $\endgroup$
    – Arno
    Sep 9 at 13:51
  • $\begingroup$ @StevenGubkin In the case of rectangles, the justification for including squares could be simply that 'rectangle' comes from 'right angles': it's a fure whose main feature is it has only right angles - accompanied by a discussion of why you can't have rectangles with more or less than 4 sides. $\endgroup$
    – j4nd3r53n
    Sep 10 at 8:15
  • $\begingroup$ @Arno I think very often you can justify an advanced definition with anecdotes - take the difinition of a group: there is a historical background for the formal definition (Galois and polynomials), but there's also simply the practicalities around simple accounting: we realised early on the we wanted to be able to subtract any two numbers - hence the need for an additive inverse etc. And then the idea turns out to be very useful in a lot of areas. $\endgroup$
    – j4nd3r53n
    Sep 10 at 8:23
  • $\begingroup$ I agree that providing motivation for definitions is important. I also love characterization theorems (for example, the exterior derivative can be shown to be the only "natural" operator from $k$ forms to $k+1$ form on a manifold) which can provide rigorous justification for a definition. However, certain definitions do boil down to convention. A famous (and still contentious) example is whether or not to include 0 as a natural number. $\endgroup$ Sep 10 at 17:37
4
$\begingroup$

insight why this seems to be so difficult?

I have studied CS with a side-dish of math (some decades ago) and I was surprised by (but very much enjoyed) the actual theoretical aspects of CS. I generally didn't know what to expect from a CS curriculum except that in my case it was abundantly clear that I wanted to study whatever there is to know about computers etc.

Therein might lie your problem. Many of your students probably had no idea what CS entails, didn't expect it so heavily related to maths (i.e., logic, proofs, formulae etc.) and are quite unable to cope with languages, grammars, automata, lambda calculus, O-notation and so on. Also I'd suggest that a healthy percentage couldn't care less and have zero intrinsic interest. At least that was the case in the cohort I studied back then.

In my case, at least 50% of all students bowed out within the first 4 semesters, and without having any statistics, I assume that was because of maths and theoretical CS, mostly.

Another point is this: since the beginning of my time in the workforce, first as programmer and then as still-programming/developing/architecting/coaching teamlead, I over and over find that young programmers (who, in my company, usually have studied CS or something very close at uni levels) love to solve problems by cut&paste; by going to Stack Overflow; by reading tutorials and so on. Having worked closely with dozens if not more people over the decades, I think I met exactly one person who (like me) actually went to the reference documention of whatever tool or programming language we used, first, when trying to understand it or solve a deep problem. Almost everybody else seems to have a deep aversion against really "grokking" some topic from first principles.

Sure, just going to a tutorial and copying some lines of code is usually quicker, and often the software kind of works at the end; but for me personally, I get my satisfaction from deeply understanding what I am doing; I am fascinated by digging deep. Meanwhile, I am very aware that this is not normal for everybody, even CS students. This is a bit of a parallel to your definitions - the core documentation of whatever you're using is the definition, and a tutorial would be something like a practical example.

As to "why" that is, I assume that CS (especially theoretical, but basically all of it) is by its very nature not "natural" for humans to learn and do. This is probably also the reason why we have such a shortage, worldwide, of people really excelling at it. If it were easy and came to most of us as a matter of course, we would have boatloads of people easily chugging out software and advancing the field...

Are there any better techniques to get this point across?

Unfortunately I find it very hard to suggest anything except repeating your point over and over again. At least in my country, alas, due to changes to the school system in the last decade (EU -> Pisa...) I am afraid that schools do not have the time or capacity anymore to really bring the pupils to uni-level logical thinking, primarily cramming facts and forgetting them as quick as possible to make space for the next test. This is only partially cynical - that opinion comes from talking with and experiencing the education of some of them, including one of my adult children.

Maybe in your next class, take out the first 2-3 sessions to talk about nothing else except how to approach these things (basically, what you explained in your post). Make them aware what they have to expect, and give them techniques to actually do the work. Maybe, in the first time, after actually teaching your first few definitions, take another hour or two just for Q&A where you test them on it and make it routine for them to go to the definitions.

Maybe, on your test sheets, write a message "go back to your definitions whenever you don't know what to do" in big letters.

$\endgroup$
3
  • 1
    $\begingroup$ Thanks, this is a useful perspective. I do indeed suspect that some of the students ought to be studying Software Engineering instead, and hope that we'll explain the difference better in the future. I've actually tried your "first 2 lectures on the meta level" idea, but I'm not sure whether the words coming out of my mouth there carried any meaning for the students. But your last suggestion is something I hadn't thought of, and that I'll definitely try out! $\endgroup$
    – Arno
    Sep 9 at 14:37
  • 3
    $\begingroup$ Once upon a time, the manual was the only information available. Before the World Wide Web, you couldn't just ask for solutions like people to today, here. Kids these days are products of their times. There's something to be said about going old-school to really learn something. $\endgroup$
    – JDługosz
    Sep 9 at 22:42
  • $\begingroup$ @JDługosz Too true. $\endgroup$
    – ryang
    Sep 10 at 17:21
4
$\begingroup$

I've said in the past that the math discipline has a problem of jumping into the higher-levels of conceptual difficulty with exercises too fast. Let's say we take Bloom's Taxonomy as a model. Non-STEM teachers constantly complain that they spend all their time at Level 1, memorizing facts, and can't move past that. Math teachers, on the other hand, give a definition and then taking that for granted, launch immediately to at least Level 3, applications.

Note in the OP's example they've given a definition or two and then immediately expect logical inferences based on those definitions.

I understand, because I don't have time to do any better in my math courses (e.g., discrete mathematics for CS majors) -- there's too much dense content in the curriculum to do any differently. But if I had more time I would:

  • Test remembering definitions directly with multiple-choice or fill-in-the-blank quizzes
  • Test basic understanding of definitions with true/false quiz questions of whether different cases qualify for the definition at hand. (E.g.: Is 5 an integer? Is 1/2? Is -8? Is 0? Is pi?)

I manage to work in a little bit of that in lower-level algebra classes, but as I say, time is very constrained in our math classes.

At one point another SE poster once wrote something like, "People don't understand the importance of definitions until they have to use them in anger (i.e., prove something)". That's sort of true, and if students get to the point of a proof-writing course, and they're still intransigent about not reading definitions, then they probably just fail.

$\endgroup$
3
$\begingroup$

I try to stress that definitions are just useful shortcuts, ways to put several disparate phenomena under the same roof (like context free grammars and the others in the classification), and show the similarities/usefulness of said definitions. One of the basic "proof techniques" taught in the discrete math course (first one that for our students means real proofs, not mostly "learn when/how to apply formula XYZ") is "If nothing looks useful, try unraveling the definitions". It is widely useful, for example when dealing with congruences modulo $m$ (often rewriting $a \equiv b \pmod{m}$ as $a = b + k m$ allows to see patterns/simplify).

$\endgroup$
2
$\begingroup$

Maybe do an in-class exercise with 1 simple (fast) problem, where the students don't have access to the definition. For ease of grading, use a multiple choice answer format. Collect papers and set aside.

Then follow up with similar exercise, but with the appropriate definition included the handout. Have students pass the papers and grade them in class, both sets. Then write the performance down on the board, for each set.

This might seem childishly simple, but I think you need to make it simpler, to drive different behavior. If you give them a lecture on "read the definitions", they will tune out. Or keep it for infrequent high scale tests (mid-term/final). Or project style homeworks. Instead of all that, do something simple.

$\endgroup$
1
  • 1
    $\begingroup$ Do you mean something like asking "Are all blemfarps red?" without telling them what a "blemfarp" is, and then telling them that a "horun" is a green triangle, and ask whether there is a red horun? Have you tried this yourself, or do you have some theoretical reasons for believing this might accomplish something? $\endgroup$
    – Arno
    Sep 9 at 8:46
2
$\begingroup$

Give them the definitions they should learn. Then, various exercises that can be solved using the definitions. Occationally, an exercise may invoke older definitions for repetition.

When we learned the Pythagoras theorem, lots of triangle exercises followed.

Also, tell them early on: "Memorizing everything won't get you an A here. Perhaps not even a C. This is math, and you must be able to reason, and combine several facts & techniques to arrive at an answer."

Also: "In math, you don't learn all the answers, you learn how to work out the answers. If I ask, what is 987*365, you don't complain you never learned that particular product. You learned a method for working out ALL products. CS works the same way, to some extent."

$\endgroup$
1
$\begingroup$

I’ve been able to inculcate students with the awareness that definitions are not just legal agreements—which they basically are—or boring fine print, by persistently demonstrating҂ using definitions to successfully deal with problems: for example, in modelling scenarios and translating texts, manipulating expressions, and crafting explanations.

Frequently, applying definitions is not just the most direct way to accomplish the task at hand, but the only way; in such cases, I specifically emphasise this point.

However, the process really does require time and trust, and is part of the larger process of encouraging sense-making҂.

Eventually, students even become comfortable with mathematical vocabulary having multiple meanings depending on context and even the exam board—which reinforces the importance of referring to the definition!

Addednum

҂ I couldn't have expanded my points better than how Reese has said it in this answer:

  1. acculturating students to reflexively turn to definitions rather than to regard them parenthetically, and
  2. getting hands dirty in demystifying definitions and unravelling meaning, perhaps even thinking about their whys and hows.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.