\chapter{Results} Three papers in this area have been published to date: \begin{itemize} \item CCSCNE: Categorizing the School Experience of Entering Computing Students \item FIE: Mathematization in Teaching Pumping Lemmas \item Koli Calling: Computer Science Students' Concepts of Proof by Induction \end{itemize} \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 \begin{enumerate} \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. \end{enumerate} \section{Results of Combined Investigations} There are some categories that are shared among the several contexts. \section{Categories} Categories found in one or more investigations Categories\\ 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 levels. \begin{tabular}{p{3cm}p{3cm}} Categories & Achievement Levels\\ The idea of a false statement sometimes becomes troublesome when negation is being learned.&\\ &True and false make sense, and we can make arguments using them.\\ 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 figures.&\\ &We might wish to help students traverse multiple rendering of ideas.\\ 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) examples\\ \end{tabular} Using the achievement levels we can infer critical factors. \begin{tabular}{p{3cm}p{3cm}} Achievement Levels& Critical Factors\\ True and false make sense, and we can make arguments using them.&\\ & 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 ideas.&\\ & 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) examples.&\\ & Authentic applications show the use of this knowledge.\\ \end{tabular} \subsection{Abstraction} 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. \subsection{Definitions} Without abstraction the burdensomeness of definition is increased. This could contribute to the reluctance of students to embrace definitions. \subsection{Symbolization} 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. \subsection{Structure} 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.