Skip to content
Branch: master
Find file Copy path
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
293 lines (270 sloc) 15.5 KB
Importance goes here, rather than in analysis\\
Programmers/developers who produce and/or verify software that is used in safety critical applications, such as medical equipment, self-driving cars, and defense-related equipment should be able to know that their software functions correctly.
Programmers/developers who produce and/or verify software that is expected to perform work, such as search, efficiently, should be able to know that their algorithms are efficient.
Computer science is the expected background preparation for people working in these careers.
Proof is the method that is used to ascertain, and to convince, that these goals have been achieved.
\subsection{Interpretation of Results}
As in mathematics, some students learn as procedure that which we would prefer that they understand.
Some procedural learning is insufficiently accompanied by an understanding as to which contexts to which it applies, and has become in some cases what Whitehead calls "inert knowledge".
\section{Previously Published Work}
\section{Categories of Experience of Entering Students}
Undergraduate students beginning study of the computing disciplines present
a various degrees of preparedness.\cite{reilly2014examination} Some interview participants enjoyed
a modified Moore method\cite{cohen1982modified} geometry class in middle school, and relished
opportunities to create proofs (not yet published). Other students are not so
well prepared.
After publishing this paper, more information relating to its topic has been
encountered. For example, consistent with the work of Almstrum \cite{almstrum1996investigating}, we have
found that, about implications, some students, who do know that any statement
must and can, be either true or false, think implications must be true.
\section{ Representation/Symbolization in Pumping Lemmas}
Some of our results to date are consistent with the framework described by
Harel and Sowder in 1998\cite{harel1998students}. We have found students holding conceptualizations
that Harel and Sowder's 1998 model\cite{harel1998students} calls symbolization: We have found
that some students may lack facility in notation. For example, in the application
of the pumping lemma, students are expected to understand the role of $i$,
in the context that a string $s$, having component substrings $x$, $y$ and $z$, can be
used to generate other strings, of the form $xy^iz$, where $i$ gives the number of
copies of the substring $y$. Moreover, students are expected to understand that
the subdivision of a string of length $p$, expressed as $\sigma_1^a\sigma_2^{p-a}$, where $a \in \{0,1,\ldots,p\}$
uses $a$ as a parameter, a free variable, not one necessarily bound to a single instance
of a natural number, but a representation of a domain. We have seen this
lack of understanding in a situation in which it was proposed as evidence that
a single example, namely $\sigma_1^a\sigma_2^{p-a}$, formed a proof for a universally quantified
statement. An excerpt of the errors found on tests is shown in Table .
Table : Some example errors\\
Let x be empty\\
$|xy| \leq p, so xy = 0^p$\\
$|xy| \leq p; let x = 0^{p+r}, y = 0^{p+r}, 0 < r < p$\\
Let's choose $|xy| = p$\\
$0^{p+1}0^b1^p \neq 0^{p+1}1^p \therefore xy^2z \not\in \mathcal{L}$\\
where $\mathcal{L} = \{0^i1^j, i \neq j\}$\\
we choose $s = 0^{p+1}1^p$ within $|xy|$\\
thus $\neq 0^p1^{p+1}$\\
Let $x = 0^a, y = 0^b1^a$\\
$x = 0^{p-h}, y = 0^h$\\
$x = 0^i, y = 0^i, z = 0^i1^j$
Figure: Some categories / conceptualizations found among students of
introduction to the theory of computing, and published at FIE.
Harel and Sowder identified a category of conceptualization that correctly
applied transformation and axiomatic arguments. Some students expressed
enthusiasm for the power that inheres to building arguments with carefully
specified component ideas, in particular how the absence of ambiguity permitted
arguments to extend to great length while remaining valid. Not all of the
students had developed axiomatic conceptualizations of proof. About definitions,
we have collected preliminary data on students' conceptualizations of
definitions used in proofs. Some students think definitions are boring. Some
students think that they can infer definitions from a few examples. Concerning
executive function, we have found that some students do not state the
premises clearly, and some students do not keep track of their goal. About
rules of inference, we have found that some students apply invalid approaches
to inference.
\section{ Abstract Model for Proof by Mathematical Induction and Recursion}
Interviews with students revealed that some students see generation of a proof
by mathematic induction as a procedure to be followed, in which they produce
a base case, and prove it, and produce an induction step, and prove that. Some
of the students interviewed did not know why this procedure generated a
convincing argument. Moore, as reported in Polya[] noted that some students
of mathematics formed the same conceptualization, that there is a procedure,
but it does not necessarily produce a convincing argument. Polya[] wrote
a problem involving all girls being blue-eyed; a similar problem appears in
Sipser\cite{sipser2012introduction} about all horses being the same color. The purpose of this exercise is
to make students aware that the truth of the inductive step must apply when
the base case appears as the premise. In some cases, this point was not clear to
the students.
Students' conceptualizations of proof by mathematical induction can support
their choosing to apply recursive algorithms. One student reported success at
both mathematical induction and recursive algorithm application without ever
noticing any connection. This student opined that having learned recursion
with figures, and proof by mathematical induction without figures, that no
occasion for the information to spontaneously connect occurred. Students reporting
ability to implement assigned problems recursively, but not the ability
to understand proof by mathematical induction also reported that ability to
write recursive programs did not result in recognition of when recursive solutions
might be applicable in general. Students reporting ability to implement
assigned problems recursively, and also the ability to prove using mathematical
induction also reported preferring to implement recursive solutions in
problems as they arose.
Our work on students' choices of algorithmic approaches is consistent with
work by other researchers in computer science education\cite{} on conceptualizations
of algorithms. Our work served to unify that of mathematician educators
with that of computer science educators, by providing a plausible explanation why
the conceptualizations of recursive algorithms that were found, might exist.
Figure 4.0.2: Conceptualizations of proof by induction and recursion, published
in Koli Calling
Index Element of Model
\item Some students begin learning proof by mathematical induction as if it were
a procedure.
\item Some students learn two parts of this proof technique without seeing any
connection between the two.
\item Some students do not find the procedure to be a convincing argument.
\item Some students would not employ proof by mathematical induction to explore
whether a recursive algorithm would apply to a given problem.
\item Some students understand both proof by mathematical induction and also
recursion and had never noticed any similarity.
\section{Results of Combined Investigations}
There are some categories that are shared among the several contexts.
Categories found in one or more investigations
Definition of proof as convincing (to mathematicians) argument is not
always understood\\
Definitions in general are not always recognized as significant building
blocks in arguments\\
The idea of a false statement sometimes becomes troublesome when
negation is being learned.\\
In particular, accepting that an implication may be false, can be troublesome.
Notation is sometimes difficult.\\
Ideas presented relying on notation are not always connected with
ideas presented relying on figures.\\
Warrants are not always recognized.\\
Students do not always traverse levels of abstraction effectively.\\
The applicability of valid argument forms to contexts of interest is not
always appreciated.
\section{ Critical Factors}
To determine critical factors, we can convert negative categories into achievement
Categories & Achievement Levels\\
The idea of a false statement
sometimes becomes troublesome
when negation is being
&True and false make sense, and
we can make arguments using
Definition of proof as convincing
argument is not always understood&\\
Warrants are not always recognized.&\\
&Proof can sometimes be obtained
through a series of warranted assertions.\\
Definitions in general are not always
recognized as significant
building blocks in arguments&\\
&Using agreed definitions and
valid rules of inference we can
sometimes explore the consequences
of definitions.\\
Notation is sometimes difficult.&\\
&Notation helps.\\
Ideas presented relying on notation
are not always connected
with ideas presented relying on
&We might wish to help students
traverse multiple rendering of
Students do not always traverse
levels of abstraction effectively.&\\
&We might wish to help students
traverse multiple levels of abstraction.\\
The applicability of valid argument
forms to contexts of interest
is not always appreciated.&\\
&We might wish to give exercise
with authentic (career related)
Using the achievement levels we can infer critical factors.
Achievement Levels& Critical Factors\\
True and false make sense, and
we can make arguments using
& True and false apply to assertions.\\
Proof can sometimes be obtained
through a series of warranted assertions.
& Proof is exploration and discovery.\\
Using agreed definitions and
valid rules of inference we can
sometimes explore the consequences
of definitions.&\\
& Efficiency but also abstraction
are aided by notation.\\
Notation helps.&\\
& Notation is one representation
and there are others. Ideas appear
in multiple guises.\\
We might wish to help students
traverse multiple rendering of
& When notation allows for multiple
interpretations, abstraction
above those multiple interpretations
has been achieved.\\
We might wish to help students
traverse multiple levels of abstraction.&\\
&Multiple levels of abstraction are
relevant at the same time.\\
We might wish to give exercise
with authentic (career related)
& Authentic applications show the
use of this knowledge.\\
Literature reports \cite{} students of CS have trouble with abstraction.
Taking abstraction to be the ability to select some details to ignore,
and thereby find a simpler model of an entity, we can transform the ideal
knowledge transfer experience into on disabled by a lack of ability to see this dimension.
The multiple-inheritance hierarchy that could be used to organize
definitions and relationships of ideas is less able. More entities will be
grouped together than effective use of the multiple inheritance hierarchy
would consider equivalent.
Another useful concept that students have been seen to underappreciate is the significance of careful definitions.
Abstraction hierarchies allow for efficiency in definitions.
A new entity can be defined as a specialization of an existing entity, and its differences
make up the new definition material.
In the absence of this multiple inheritance hierarchy, every definition in its full length
is attached to its entity.
Tie in with Mazur. For students holding the same granularity of refinement of
concepts, conversations would be easier, because there would be fewer disconnects as one participant expressed a thought on one degree of refinement far from that of another student.
If the ideas implying the refinement of the definition inheritance graph, being different from one
discussant to the next, are rare, and/or the meaning of the sentence does not depend upon it, these exchanges are not too disruptive or distressing.
On the other hand when two sets of refinement are very different,
and the meaning of the exchange depends upon the refinement in the speaker, that the hearer does not have,
then some degree of failure of communication will ensue.
Absence of abstraction converts tree of topics into sequence of topics.
Tree of proof examples (say of application of proof technique) into sequence of examples.
Might detract from recognizing what is a related example.
Would detract from plausible inference technique of ``related problem seen before''.
We have a goal for student programming that they should strive for segments of programs
(e.g., method implementations) to be small. One way of accomplishing this is to use abstraction,
such as combining instructions into a method, and calling the method.
If students have difficulty with abstraction, they might
have difficulty with choosing groups of instructions to represent a method.
Correspondingly, if they practice grouping instruction into methods, and using those methods, they would
be gaining practice relevant to using abstraction.
One way to cultivate abstraction is to pose a question of which one of several examples is different.
When several things are examples of one abstract idea and one is not, identifying the one that is different involves noticing the abstraction.
These questions could be instantiated using blocks of code.
Without abstraction the burdensomeness of definition is increased. This could contribute to the reluctance of students to embrace definitions.
Use of symbols is a kind of abstraction.
Symbolization is the syntax for simple, clear definitions as Gries\cite[p.205]{gries2012science}(Science of Programming) recommends for construction of programs.
Students will be hindered at this program derivation/development style if symbolization is a not-yet-acquired skill.
Program development/derivation should begin with a formulation of the requirements.
Students may arrive with some programming experience that is of a more intuitive, less
mathematically disciplined sort.
We have to ask how we desire to cultivate the abilities of such students.
Vygotsky discussed language acquisition by children, in which some children will have begun to invent
some terms for items in their environment, and will need to be guided to abandon neologisms for the naming generally agreed in their environment.
Kuhn discussed the reluctance of scientists who have been rewarded for operating in one
perspective on nature to adopt a different perspective.
Instructor may encounter a similar reluctance on the part of students
to adapt a scientifically/mathematically disciplined approach to programming,
especially if the students have experienced some success in their earlier work.
To win over such students,
demonstration of superior outcomes on problems, especially on problems that seem insoluble otherwise,
are more frequently convincing.
Happily, Professor Gries has provided such examples.
By showing superior relative efficacy of these approaches in an activity the students recognize as
desirable, instructors could motivate the students to learn symbolization.
sequence vs. sequence that has come about from combining parts. Refer to Leslie Lamport's structure for proofs. Combine with Gries' proofs for deriving code. The purpose for getting through Goguen and Malcolm is that it applies to imperative programs.
You can’t perform that action at this time.