ch3.tex

 \chapter{Methodology}
 Knowledge about how students conceptualize has a qualitative nature. For
 qualitative research, methodology varies, but has standard parts: design of the
 study, sources and their selection, data, the process of analysis, the interpretation,
 and the approach to validation. Sample selection is recorded and reported
 so that others may judge transferability to their own context. Interviews are
 the principle technique used by phenomenographical research. Documents
 can also be used. Normal conduct of teaching can also provide data that can
 be used, if in an anonymous, aggregate form. Both deductive and inductive
 analysis provide qualitative data.
 
  
  \section{Design of the Study}
  
  
  Information learned in tutoring and lecturing undergraduates inspired the research questions.
  
   This study is qualitative because
    we seek to be able to describe the nature of the various
   understandings achieved by the students, rather than the relative frequency
   with which any particular understanding is obtained.
  
  The study was designed to observe undergraduate students as they progressed through the curriculum.
  %Changes in conceptualizations of students as they progressed through the curriculum would be interesting if we could detect them.
  
  Consistent with a phenomenographic study, the principle data were interview transcripts.
  
  We 
  conducted over 30 interviews.
  Our interview participants were sampled from the students, faculty and graduates of a large public research-oriented university in the northeastern United States. 
  
  We used early interviews to explore students' notions of proof, adapting to the
  student preference for proof by mathematical induction and incorporating the use of recursive
  algorithms.
  We used exams to study errors in application of the pumping lemma for regular
    languages.
  We used later interviews    to investigate questions that developed from analysis of earlier interviews.
   We used homework 
    to observe student attempts at proofs, and
   to observe student familiarity/facility
  with different (specific) proof techniques: induction, construction, contradiction,
  and what students think it takes to make an argument valid.
  We used yet later interviews to discover whether students used proof techniques on their own, and how students ascertained whether circumstances were appropriate for the application of algorithms they knew, and how students ascertained certain properties of algorithms.
  
 
 %\chapter{Design of the Study}
 %This work is a qualitative study, the underlying philosophy is constructivist,
 %the research perspective is phenomenography, as extended to variation theory and structural relevance,
 %and the epistemological framework is 
 %social constructivism, in particular, that mental preparation is influential, readying students to learn from instructors and peer interaction, some material better than other material.
 
 %a layered collection of intellectual disciplines,
 %including
% complexity applied to cognitive neuroscience, and neurophysiology.
 %At the highest level of integration, computer science and mathematics
% reside, supported by studies in memory and attention, including computational
 %complexity applied to cognitive neuroscience, and neurophysiology.

 
 % the focus is on determining what questions
 %would be posed, in the process of continuous curriculum adaptation and improvement
 %the meaning students are making of their specific educational experiences.
 
  \section{Parts of the Study}
  
  The parts of the study reflect the several research questions.
  The first part of the study was about what undergraduates think proof is, and how they go about understanding them.
  This part informed us about any structure students used as they pursued proof-related activities, and about what students thought was required for an attempted proof to be valid.
  The second part was about what undergraduates think proof is for.
  The third part was about what students do when a situation might be well-addressed by proof.
  This part informed us about the comfort level students have about the use of proof, and the consequences students experience, as a result of their choices about application of proof.
  
  These parts are summarized in Table \ref{parts}.
  
  \begin{table}
  \caption{Parts of the Study}
  \begin{tabular}{|p{4cm}|p{8cm}|}\hline
  Part & Purposes \\\hline \hline
  first & what proof is\\
  & how to understand proofs\\
  & use of structure\\
  & how is validity attained\\\hline
  second & purpose of proof\\\hline
  third & student use of proof\\
  & comfort level with proof\\
  & consequences of not applying proof\\ \hline  
  \end{tabular}
  \label{parts}
  \end{table}
  
 
 
 \section{Population Studied}
 In a phenomenographic study, it is desirable to sample widely to obtain as broad as possible a view of the multiple ways of experiencing a phenomenon within the population of interest.\cite{marton1997learning} which in turn cites Glaser and Strauss 1967\cite{glaser1968discovery} We studied, by interview, homework and test, undergraduate students who have taken courses involving proof. Typically but not always, these are students majoring in computer science. Some of these undergraduate students are dual majors, in computer science and mathematics.  We interviewed graduate students emphasizing those who have been teaching assistants for courses involving proofs. We interviewed faculty who have been taught courses involving proof. We have interviewed former students who have graduated from the department. We have interviewed undergraduates who transferred out of the department.
 
  For the benefit of readers wondering to what extent the results might be transferable, demographics of some commonly seen properties of populations are provided:
  
  Number of interviews transcribed:\\
  Number of interview subjects:\\
  Percentage by race:\\
  Percentage by sex:\\
  Percentage by age:\\
  Percentage by language:\\
  Percentage by domestic/international:\\
 
% \section{Chronology of the Design}
% The design of this study began while teaching Introduction to the Theory of
% Computing. While helping students learn the pumping lemma for regular
% languages, and trying to understand from where the several difficulties arose,
% I became curious about the bases of these difficulties. One example was that
% a student felt strongly that a variable, a letter, denoting repetitions in a mathematical
% formulation, could only stand for a single numeric value, rather than a
% domain. Subsequently I have learned that symbolization is a category identified
% by Harel and Sowder \cite{harel1998students}, for students of mathematics learning proofs. Our
% student is a vignette of our computer science student population harboring
% some of the same conceptualizations. As a consequence of this opinion, the
% student felt that showing that a mathematical formulation had a true value
% was equivalent to demonstrating a true value for a single example, rather than
% demonstrating a true value for a domain. Here we see evidence for the category
% Harel and Sowder  \cite{harel1998students} call (is it inductive, perceptual?) where an example
% is thought to provide proof of a universal statement. Later, while helping students
% study the relationship between context free grammars and pushdown
% automata, I learned from the students that many of them did not find inductive
% proofs convincing. Subsequently I have learned that Harel and Sowder  \cite{harel1998students} created
% a category called axiomatic reasoning. In axiomatic reasoning, students
% begin with accepted information, such as axioms and premises, and apply rules
% of inference to deduce the desired goal. This category had not always been
% reached by their students, similarly to ours. As will be seen, later interview data showed,
% some of our students learn to produce the artifact of a proof by mathematical
% induction by procedure. They learn the parts, and they supply the parts
% when asked, but are not themselves convinced. (McGowan and Tall report a similar situation.) This matches with two other
% categories created by Harel and Sowder \cite{harel1998students}, internalization and interiorization.
% Still later, when leading a course on ethical reasoning for issues related to computer
% science, I found that most of the students did not notice that methods
% of valid deductive argumentation were tools that they might apply to defend
% their opinions.
% Thus the idea of exploring the nature of the students' degrees of preparation
% for understanding and creating proofs appeared.
% First, interviews about proofs in general were conducted, with a broad interview
% script. 
 
 %The students almost all selected  proofs by mathematical induction.
 
 
% During analysis of these data, a more elaborate interview script was developed,
% aiming at the ideas of domain, range, relation, mapping, function, the ideas of
% variable, as in programs and mathematical formulations, and abstraction.
% Some students emphasized that mathematical definitions are analogous to
% definitions in natural languages, and that mathematical discourse is carried
% out in the mathematical language created by these definitions.
% The capabilities for expression and care bestowed by these definitions invest
% mathematical reasoning with its persuasive power.
% Thus both the reasoning processes, using concepts and the clearly defined
% mathematical concepts together provide the ability of mathematical argumentation
% to be convincing. Students who appreciated this found it invigorating.
% Other students had different reactions to definitions. Thus, the role of definitions
% and language became another area of exploration.
% The difference between a domain and a single point in a domain can be seen as
% a level of abstraction. If something is true for a single point in a domain, but is
% also true for every single point in the domain, then the point can be seen as a
% generic particular point, representative of the domain. This concept of ability
% to represent is related to the idea of abstraction.
% We saw data in this study that affirmed the observations of others, that students
% do not always easily recognize the possibility of abstraction.
 


 
 \section{Sample Selection}
 
 All participants were volunteers.
 Volunteers were sought in all undergraduate classes involving proofs, and also some that did not involve proofs, so that we could sample  students at different stages in their undergraduate careers.
 
 Graduate student volunteers were also sought. Most of the graduate student interviews were among teaching assistants in courses that taught and/or used proofs. We also included faculty of courses that involved proofs.
 
% Students from the University of Connecticut who have taken or are taking the  relevant courses were offered the opportunity to be interviewed.
  The undergraduate students
 who volunteered were mostly male, mostly traditionally aged students. Some students were domestic, and some international. 
 Some students were African-American,
 some Asian, some Caucasian, some Latino/a, some with learning disabilities such as being diagnosed as on the autistic spectrum.
 
 \subsection{Proofs Using the Pumping Lemma for Regular Languages}
 This study is in the first part, about what proof is.
 
 The participants for the study of proofs using the pumping lemma for regular languages were
 forty-two students, of whom thirty-four were men and eight women,
 forty-one traditional aged, 
 %one former Marine somewhat older, one collegiate athlete (a
 %woman),
  there were three students having Latin-heritage surnames, 1/4 of the
 students had Asian heritage, 2 had African heritage, and 8 were international
 students. Each student individually took the final exam. A choice among
 five questions was part of the final exam; one required applying the pumping
 lemma. Half the students (21/42) selected this problem. These were 17 men
 and 4 women. Three quarters of those (15/42) selecting the pumping lemma
 got it wrong. These students, who chose the pumping lemma problem and
 subsequently erred on it, form the population of our study.
 
 \subsection{Proofs by Mathematic Induction}
 This study is in the first part, about what proof is.
 
 The participants for the study of proof by mathematic induction 
 %We studied students who 
 were taking, or
 % who
  had recently taken, a course
 on Discrete Systems required of all computer science, and computer science and
 engineering students.
 Volunteers were solicited from all students attending the Discrete Systems
 courses.
 Interviews of eleven students were transcribed for this study. Participants
 included 2 women and 9 men. Two were international students, a third was a
 recent immigrant.
 

 
 \subsection{Domain, Range, Mapping, Relation, Function, Equivalence in Proofs}
 This study is in the first part, about what proof is.
 
 For the study about domain, range, mapping, relation, function and equivalence in proofs, students
 taking, or having taken, discrete systems, especially students who
 had sought help while taking introductory object oriented programming volunteered
 to be interviewed.
 
 \subsection{Purpose of Proof}
 This study is in the second part, about why proof appears in the curriculum.
 
 Undergraduate students were sought for this study, because we wanted to know what students thought the purpose was while they were taking the undergraduate subjects.
 
 
  \subsection{Student Use of Proof for Applicability of Algorithms}
  This study is in the third part, about student use of proof.
  
  The students participating in this part were mainly those having internships or summer jobs. This changed the ratio of domestic to international students, such that a greater proportion were domestic students. Also, the ratio of women to men students was affected, such that a greater proportion were male students.
 
 \section{Data Collection}
 Our corpus included interview transcripts, homework, practice and real tests,
 observations from individual tutoring sessions, and group help sessions. %Interview  transcripts were analyzed with thematic analysis.
 Homework, practice
 and real tests, from several different classes were analyzed for proof attempts.
 (Incidentally, data from multiple instructors was combined, and no use of information about any specific instructor was used.)
 Data from individual tutoring  sessions and group help sessions were also informative. 
 Aggregations of anonymous data were used.
 
 \subsection{Interviews}
 An application to the Institutional Review Board was approved, for the conduct of the interviews. The protocol numbers include H13-065 and H14-112.
 
 %Consistent with phenomenographic studies, we wished to sample widely, so we sampled not only current students of courses involving proof, but also teaching assistants, faculty and former students associated with these courses. Some students are strictly CS/E majors, others are dual majors or minors in CS/E and math. Some students are not CS/E majors. Some former students are professionally employed in development, and others have left the major.
 
% All interview participants were volunteers.
 
The audio portion of all interviews was collected by electronic recorder and subsequently transferred to a password protected computer. From here the interviews were transcribed, and names were redacted. The redacted interview data were analyzed using the Saturate application.

 
 \subsubsection{Proofs by Mathematic Induction}
 Interviews were solicited in class by general announcement, and by email.
 Interviews were conducted in person, using a voice recorder. No further
 interview script, beyond these following few questions, was used. The interviews
 began with a general invitation to discuss students' experience with and
 thoughts on proofs from any time, such as high school, generally starting with
 
 \begin{itemize}
 \item ``Tell me anything that comes to your mind on the subject of using proofs,
 creating proofs, things like that.''
 \end{itemize}
 and then following up with appropriate questions to get the students to elaborate
 on their answers.
 Additional questions from the script that were used when appropriate included
 \begin{itemize}
 \item ``Why do you think proofs are included in the computer science curriculum?'',
 \item ``Do you like creating proofs?''
 \end{itemize}
 and, after proof by induction was discussed,
 \begin{itemize}
 \item “Do you see any relation between proof by induction and recursive algorithms?”.
 \end{itemize}
 
 Almost every student introduced and described proof by mathematic induction as experienced
 in their current or recent class.
 \subsubsection{Expanded semi-structured interview protocol for domain, range, language, equivalence class in Proofs}
 \subsubsection{Expanded semi-structured interview protocol for definitions, language, reasoning in Proofs}
 
 \subsection{Documents}
  
  
  
  \subsubsection{Proofs Using the Pumping Lemma for Regular Languages}
  The study was carried out on the exam documents. The interpretation was informed
  by the events that occurred in the natural conduct of lectures,
  help sessions and tutoring.
  One method of assessing whether students understood the ease of application
  of the pumping lemma to a language to be proved not regular was offering a
  choice between using the Myhill-Nerode theorem with a strong hint or using
  the pumping lemma. The pumping lemma problem, which could very easily
  have been solved by application of the Myhill-Nerode theorem, especially with
  the supplied hint, was designed, when tackled with the pumping lemma, to
  require, for each possible segmentation, a different value of $i$ (the number of
  repetitions) that would create a string outside of the language. The intent was
  to separate students who understood the meaning of the equation's symbols,
  and the equation itself, from those students engaged in a manipulation with at
  most superficial understanding.
  
 \section{Phenomenographic Analysis}
 
 %Describing how analysis was done in detail is really important. 
 %How do you do phenomenography?
 
 %Is this the way everything was analyzed?
 
 
 
 Marton and Booth\cite[p. 133]{marton1997learning} describe a desirable analysis technique:
 
 \begin{quote}
 [ Apply] the principle of focusing on one aspect of the object and seeking its dimension of variation while holding other aspects frozen.\end{quote} %partial derivative
 
 Remember to apply both perspectives, 
  \begin{quote}that pertaining to the individual and that pertaining to the collective.
  \end{quote}
 
\begin{quote} [E]stablish a perspective with boundaries, within which [one seeks] variation.\end{quote}
 
 Recalling that Marton and Booth regard the learning objective as a collection of related aspects, with the relationships, we can observe that a component hierarchy can represent the aspects. Recalling that Marton and Booth discuss the depth of understanding, we can observe that one consequence of depth of understanding is the development of a generalization/specialization hierarchy. Marton and Booth contrast situations with phenomena, such that phenomena are understandings and situations serve as relatively concrete examples of phenomena, as used in instruction and assessment.
 
 We may search for evidence of recognition of aspects; they might be mentioned by learners. Marton and Booth have observed that in different context, different aspects shift between foreground (consciousness) and background.
 
 \begin{enumerate}
 \item search for extracts from data, that might pertain to perspective
 \item inspect them in context of own interview
 \item inspect them in context of other extracts all interviews on the same theme
 \end{enumerate}
 
 Deductively (in the sense of qualitative analysis), in a reductionist fashion, we may select an aspect of the learning objective and seek mention of it.
 
 \begin{enumerate}
 \item select one aspect of the phenomenon and inspect across all subjects
 \item select another aspect
 \item whole interview -- to see where these two aspects lie relative to other aspects, and to background
 \end{enumerate}
 
 Holistically, we might attune our investigation to seek evidence that generalization may have occurred.
 
 \begin{enumerate}
 \item all of research problems, one problem at a time, whole transcripts that have particularly interesting ways of handling problem
 \end{enumerate}
 
 Marton and Booth advise persistence ``return to again and again \ldots until there is clarity''.
 
 Completion may be recognized by the achievement of a result, specifically the ability to identify a number of qualitatively different ways in which phenomenon has been experienced (not forgetting different methods of expression)\cite[p. 133]{marton1997learning}.
 
 Overlap of the material at the collective level is expected.
 
 Marton and Booth advise us to ``assume that what people say is logical from their point of view''\cite[p. 134]{marton1997learning}, citing Smedlund\cite{smedslund1970circular}
 
 
 \subsection{Application of Phenomenographic Analysis in this Study}
 
 We applied phenomenographic analysis,  basic inductive analysis and deductive qualitative analysis in this study.
 
 The analysis for the research question "What do students think proof is for?", which was approached as "Why do you think we teach proof?" exemplifies a phenomenographic approach. One aspect of the phenomenon of proof is its utility' We selected student verbal productions related to the use of proof. We considered them in the context of their own interview, and we compared them to data from other interviews on the same theme.
 
  \subsubsection{Phenomenographic Analysis of What Students Think Proofs Are}
  
  \begin{quote}
  Mathematics, as it is currently practiced, is a delicate interplay between monastic contemplation and blowing stuff up with dynamite. (Ellenberg)\cite[page 223]{ellenberg2014not}
  \end{quote}Probably I don't want to keep this, but it's fun at the moment.
  
  Some students exhibit an understanding of proof at the "black box" level, i.e., there is understanding of the role of proof, without considering any internal structure . When a proof exists, we can know that the thing the proof proves is true, in the context that applies. We can "use that theorem". Other students, though, do not have this idea consolidated yet. For example, if we consider proof by exhaustion applied to a finite set of cardinality one, we can associate to it, the idea of a test. Students, assigned to test an algorithm for approximating the sine function, knew to invoke their implementation with the value to be tested, but did not check their result, either against the range of the sine function, or by comparison with the provided sine implementation, presenting values over 480 million.
  
  Moving the the "white box" level, we find a spectrum of variation in student understanding.
  The most opaque end of this spectrum has been called "magic incantation". In this conceptualization we find those ideas of statements that are not clear, and use of mathematical symbols that is not understood.
  
  Ellenberg\cite[page 409]{ellenberg2014not} reports that some mathematicians regard axioms as strings of symbols without meaning, and that this quite formal conceptualization can be contrasted with another conceptualization that axioms are true statements about logical facts. He talks of these conceptualizations being taken by the same individual at different times. 
  
  Our participants seemed to regard axioms as strings of symbols that do mean something, though that meaning the participant ascribed might not be correct (especially as participants did not always know definitions of the entities being related), or the participant might feel unable to ascribe any meaning. We did find participants who appreciated the significance of definitions. They were dual majors in math.
  
  Another waystation on this dimension of variation is "sequence of statements". A more elaborate idea is "sequence of statements where each next statement is justified by what when before". A yet more complete concept is "finite sequence of statements, starting with the premise and ending with what we want to prove, and justified in each step." A more profound conceptualization was found "finite sequence of statements, starting with axioms and premises, proceeding by logical deduction using (valid) rules of inference to what we wanted to prove, that shows us a consequence of the definitions with which we began, an exploration in which we discover the truth value of what we wanted to show".
  
  A few categories, such as those above, serve to identify a dimension of variation. When our purposes include discovering which points we may want to emphasize, we can examine the categories seeking to identify how they are related and how they differ.
  
  It can certainly be that having more categories provides more critical aspects. For example, Harel and Sowder\cite{harel} offered extrinsic and intrinsic conviction, and their most advanced definitional/transformational class as broader categories, and (how many?) useful subcategories of these, yielding (how many?) critical aspects that suggest what teachers could usefully vary, to help learners discern items that would advance their knowledge.
  
  
  
 \subsubsection{Phenomenographic Analysis of How Students Attempt to Understand Proofs}
 Some students are attempting to understand proofs while not recognizing that they are studying a proof.
 "Were we studying proofs today?" "No" "Were we discussing certain contexts, and why certain ideas will always be true in those contexts?" "Yes" "Doesn't that seem like proof, then?" "Yes"\\
 "So, you're taking introduction to the theory of computing this semester. Do you seen any use of proofs in that course?" "No"\\
 
 
 Some students read proofs.
 
 Some students look up the definitions of terms used in the proofs and some do not.
 Some students think (or hope) they can solve problems involving producing proofs, without knowing the definitions of the terms used to pose the problem.
 Some students are aware that definitions are given, but "zone out" until examples are given. When examples are given, the students attempt to infer definitions themselves. Some students will compare the definitions they infer with the mathematical community's definitions. Some students do not.
 
 Some students think that the reading of proofs is normally conducted at the same speed as other reading, such as informal sources of information.
 
 Of students who read proofs attentively, some try to determine what rule of inference was used in moving from one statement to the next, and some do not.
 
 Some students notice that lemmas can be proved and then used as building blocks in a larger argument, and some do not.
 
 Some students can identify the forms of proof learned in discrete systems, when they see them employed in proofs, such as the combination of arguing by contrapositive and modus ponens. Some cannot.
 
 Some students can identify these forms in an argument if the argument is made about concrete objects, such as cars or specific people. Some of these students have difficulty transferring this ability with concrete objects to application to abstract entities such as sets, algorithms or symbols.
 
 Some students who achieve with difficulty the ability to recognize the application of rules of inference in one argument about abstract entities, become quicker at recognizing arguments of similar form about other abstract entities, and some continue to achieve with difficulty, as if learning the first argument did not facilitate learning the second argument.
 
 Students would attend to diagrammatic representation of proofs, such as a block digram depicting machine descriptions packaged as input for yet other machines to process, but were not observed to employ such diagrams.
 
 Students have been seen to employ decision tree diagrams.
 
 Students would attend to algorithm representation of proofs, such as a recursive process that determines a prime factorization, but were not observed to employ such algorithmic descriptions.
 
 Except when assigned to do so, students were not observed to attempt to solve simpler problems, such as by imposing partitioning into cases. Except when assigned to do so, students were not observed to attempt to solve more general problems, as is sometimes helpful.\cite[that pin dropping probability problem]{ellenberg2014not}
 
 \subsubsection{Phenomenographic Analysis of Reasons for Teaching Proof}
 
 Excerpts of student transcripts were selected on the basis of being related to this question. A dimension of variation emerged from the data, such that the excerpts seemed readily organized along this dimension.
 
 \begin{longtable}{|p{7cm}|p{8.5cm}|}\hline
 
 \endfirsthead
 
 \multicolumn{2}{c}%
 {{\bfseries \tablename\ \thetable{} -- continued from previous page}} \\
 \hline \multicolumn{1}{|c|}{\textbf{Category}} &
 \multicolumn{1}{c|}{\textbf{Representative}}  \\ \hline 
 \endhead
 
 \hline \multicolumn{2}{|r|}{{Continued on next page}} \\ \hline
 \endfoot
 
 \hline \hline
 \endlastfoot
 
% \begin{tabular}{|p{7cm}|p{8.5cm}|}\hline
 Category & Representative\\\hline\hline
 
  
  some students do not see any point to proof&
 They teach it to us because they were mathematicians and they like it.\\
 
 
 & we didn't see ok why do i really have to know the proof of the theorem to do that right? We didn't see the point, because no one taught us the point, so, that's a very important part that was missing.\\\hline

  some students think that it satisfies the curriculum goals, to be able to reproduce a previously taught proof, or follow a procedure to generate a proof, without being personally convinced&
 I was able to get a full score, but I don't understand why a proof by induction is convincing\\\hline
 
 Some students do not see a relationship between a problem and approach&
 When I have to prove anything, I always start with proof by mathematic induction, that was the one they taught the most.\\\hline
 
  Some students are surprised to discover that there is a relation between proof by induction and recursion&
 I never noticed that before, but now that you mention it, I see that they are isomorphic.\\\hline
 
  Some students see the relationship but do not use it&
  Professor (redacted) would be really proud of me that I learned to understand proof by induction quite well. \ldots I understand how recursion matches induction, there's a base case, there's a way of proceeding. \ldots I just couldn't figure out how to program the merge-sort algorithm.\\\hline
 
  some students think the only reason for studying proof is to understand proofs of, for example, resource utilization of known algorithms&
  I would never consider writing a proof except on an assignment.\\
  
  & I understand the proof of the lower bound on comparison sort. \ldots I understand the proof of the upper bound on searching in a binary search tree. \ldots If I had to prove something about termination on a search tree, I don't know how I would do that.\\
  
 
 & I know that recursion has the same structure as proof by mathematical induction. \ldots If I had an algorithm with a recursive data structure like a tree, and I had to prove something like termination about it, I'm not sure what approach I would use, it would depend.\\\hline
 
 Some students see that they could employ proof to explore whether an algorithm can be expected to solve a problem in a given context that includes bounds upon resources that are available for consumption. & mostly design the algorithm first, we had some expectation of what that complexity results would be and then we try to find an approach to prove.
%\end{tabular}
 \end{longtable}
 
 

 
 Data were analyzed using a modified version of thematic analysis, which is
 in turn a form of basic inductive analysis.\cite{Merriam2002,Merriam2009,braun2006using,fereday2008demonstrating,boyatzis1998transforming} Using thematic analysis, we
 read texts, including transcripts, looked for “units of meaning”, and extracted
 these phrases. Deductive categorization began with defined categories, and
 sorted data into them. Inductive categorization “learned” the categories, in
 the sense of machine learning, which is to say, the categories were determined
 from the data, as features and relationships found among the data suggested
 more and less closely related elements of the data. A check on the development
 of categories compared the categories with the collection of units of meaning.
 Each category was named by either an actual unit of meaning (obtained during
 open coding) or a synonym (developed to capture the essence of the category).
 A memo was written to capture the summary meaning of the category.
 Next a process called axial coding, found in the literature on grounded theory,
 \cite{strauss1990basics,kendall1999axial,glaser2008conceptualization} was applied. This process considered each category in turn as a central
 hub; attention focused on pairwise relations between that central category
 with each of the others. The strength and character of the posited relationship
 between each pair of categories was assessed. On the basis of the relationships
 characterized in this exercise, the categories with the strongest interesting relationships
 were promoted to main themes. A diagram showing the main
 themes and their relationships, qualified by the other, subsidiary themes and
 the relationships between the subsidiary and main themes was prepared to
 present the findings. Using the process of constant comparison, the structure
 of these relationships was reviewed in the light of the meanings of the categories.
 A memo was written about each relationship in the diagram, referring
 to the meaning of the categories and declaring the meaning of the relationship.
 A narrative was written to capture the content of the diagram. Using the
 process of constant comparison, the narrative was reviewed to see whether it
 captured the sense of the diagram. Units of meaning were compared with the
 narrative and their original context, to see whether the narrative seemed to
 capture the meaning. The products of the analysis were the narrative and the
 diagram.
 
 %\chapter{Analysis}
 
 The product of analysis in a phenomenographic study, is a set of categories, and relationships \textit{among} them.
 
 Marton and Booth\cite[p. 135]{marton1997learning} state "in the late stages of analysis, our researcher [has] a sharply structured object of research, with clearly related faces, rich in meaning. She is able to bring into focus now one aspect, now another; she is able to see how they fit together like pieces of a multidimensional jigsaw puzzle; she is able to turn it around and see it against the background of the different situations that it now transcends."
 
 Using Marton's overriding categorization of task and objective, we can consider that some students do not know, at least when they are studying CSE2500, that they need to be able to understand some proofs, to be good developers. Therefore, they can logically approach the study of proof in CSE2500 as a task, having some facts that they must memorize. Other students, including those with dual majors in math, wish to improve themselves by improving their ability to couch arguments in mathematical terms and both ascertain facts for themselves and convince others. Students who are aware that there are computer-science related purposes for proof, for example, in the study of algorithms they will be using proofs to understand resource consumption, will recognize the study as having the objective to improve themselves vis-a-vis dealing with proof.
 
 
 Because the relationships are expected to form a partial order, corresponding to set inclusion of subsets of the complete (with respect to the objective of teaching) understanding of the information being taught, we can say relationships \textit{between} categories.
 
 The set inclusion relationship can be that a deeper understanding includes a more superficial understanding.
 It may also be that a deeper understanding qualifies a more superficial understanding, such as being applicable in a restricted domain. Thus, understanding of a liquid as being divisible to any degree can be qualified as to scale such as macroscopic, microscopic and so on.
 
 In a phenomenographic study, this partial order is referred to as a hierarchical order.
 
 The objective of teaching, as will be in some parts of this study, the components of proof, may have many parts, called, in phenomenology, internal structure. The granularity of the subdivision of the objective of teaching results in the number of parts in the internal structure. If we let $n$ denote the number of parts obtained with a specific granularity, we see that the number of subsets will be $2^n$, which will be inconveniently large unless the granularity is sufficiently coarse. Thus, we choose a granularity resulting in approximately 4 elements of internal structure.
 
 Thus, when the teaching objective is, what is a proof, we may limit the granularity, such that the internal structure of a proof is, for example, 
 \begin{enumerate}
 \item that particular statement which is to be proved
 \item axioms, premises, suppositions, cases
 \item other statements
 \item warrants (rules of inference)
 \end{enumerate} 
 
 We might choose to pursue finer granularity in some cases, for example, we might pursue "What is a statement?", because instructors have found that not all students arriving in CSE3502 have the same depth of understanding of statement, and some do not have sufficiently deep understanding of "statement" to be able to comprehend a proof.
 
 
 Marton and Booth\cite[p. 22]{marton1997learning} call our attention to learners directing their attention to the sign vs. to the signified. With proofs, Polya \cite{} has mentioned a procedural approach to executing a proof, without understanding, as have Harel and Sowder \cite{harel1998students}, and Tall\cite{tall2001symbols}. Weber and Alcock\cite{weber2004semantic} have observed and described students omitting understanding of warrants in proofs. In each of these cases, the sign is provided, but the signified is at best incompletely understood.
 
 Analysis can usefully illuminate learning processes, taking note of the temporal domain\cite{marton1997learning}. This has been used by Booth in her analysis of how students understand the process of programming\cite{marton1997learning}.
 
 [p. 136]\cite{marton1997learning} important to be looking whether conceptualizations appear in a certain case, in a certain period of time (such as, when see proofs again in 3500, 3502, are they recognized as proofs, some no some yes, are they helpful as proofs, or troublesome, some helpful, some not, "never did get that")
 
\subsubsection{Phenomenographic Analysis of How Students Attempt to Apply Proofs (When not assigned)}
  
  
\subsubsection{Phenomenographic Analysis of Whether students exhibit consequences of inability (such as avoiding recursion)}
   
\subsubsection{Phenomenographic Analysis of Whether students notice structural elements in proofs}
 
 
  • How familiar and/or comfortable are students with different (specific) proof
  techniques: induction, construction, contradiction?
  • What do students think it takes to make an argument valid?
 
 \subsection{Analysis of Interviews}
 
 Data were analyzed using a modified version of thematic analysis, which is
 in turn a form of basic inductive analysis.\cite{Merriam2002,Merriam2009,braun2006using,fereday2008demonstrating,boyatzis1998transforming} Using thematic analysis, we
 read texts, including transcripts, looked for “units of meaning”, and extracted
 these phrases. Deductive categorization began with defined categories, and
 sorted data into them. Inductive categorization “learned” the categories, in
 the sense of machine learning, which is to say, the categories were determined
 from the data, as features and relationships found among the data suggested
 more and less closely related elements of the data. A check on the development
 of categories compared the categories with the collection of units of meaning.
 Each category was named by either an actual unit of meaning (obtained during
 open coding) or a synonym (developed to capture the essence of the category).
 A memo was written to capture the summary meaning of the category.
 Next a process called axial coding, found in the literature on grounded theory,
 \cite{strauss1990basics,kendall1999axial,glaser2008conceptualization} was applied. This process considered each category in turn as a central
 hub; attention focused on pairwise relations between that central category
 with each of the others. The strength and character of the posited relationship
 between each pair of categories was assessed. On the basis of the relationships
 characterized in this exercise, the categories with the strongest interesting relationships
 were promoted to main themes. A diagram showing the main
 themes and their relationships, qualified by the other, subsidiary themes and
 the relationships between the subsidiary and main themes was prepared to
 present the findings. Using the process of constant comparison, the structure
 of these relationships was reviewed in the light of the meanings of the categories.
 A memo was written about each relationship in the diagram, referring
 to the meaning of the categories and declaring the meaning of the relationship.
 A narrative was written to capture the content of the diagram. Using the
 process of constant comparison, the narrative was reviewed to see whether it
 captured the sense of the diagram. Units of meaning were compared with the
 narrative and their original context, to see whether the narrative seemed to
 capture the meaning. The products of the analysis were the narrative and the
 diagram.
 
% \section{Interview}
 Some students remembered taking proofs in high school in geometry.
 Some students were taking proofs contemporaneously in philosophy.
 Some of the students studying proof in philosophy found them disturbing, expressing a preference for geometrical proofs.
 Some students remembered having to furnish proofs of geometrical facts, also facts about prime numbers and sets.
 Some students knew that CSE2500 treated proofs because they would be used in later courses. Students did not know why proofs would be used later, and were generally happy to hear some example uses.
 Though students were asked whether they made use of proofs spontaneously, none of those interviewed gave an example.
 Some students preferred to articulate with code, and some (who were dual computer science / math) sometimes preferred mathematical symbols, depending upon the context.
 Some students do wish to convince themselves of things, such as tractable execution times, and correctness. Though students were asked whether they made use of proofs for this purpose, none of those interviewed claimed to do so, rather they mentioned going carefully over their algorithm construction, and considering cases.
 
 In interviews, the students almost all chose to discuss proofs by mathematical induction.
 
 \subsubsection{Themes / Categories}
 \begin{itemize}
 \item Definitions\\
 Students divided into (1)those who found definitions boring, difficult to pay attention to, and undesirable compared to examples, from which they preferred to induce their own definitions, and (2) those who had caught on to the idea that definitions were the carefully crafted building blocks of reasoning.
 \item Procedures
 Students sometimes learned what was desired in a proof, but learned to produce it by procedure, and were not themselves convinced.
 \item Context
 Students asked whether the topics for examples and exercises, such as prime numbers, had relevance to programming, with which they had experience, but not unrelated to the topics.
 Students did not know the context in which the proofs, or procedure version of proof, was applicable, so, for example, did not apply proof by mathematic induction to recursive algorithms, and did not know how to tell whether recursive algorithms would be applicable.
 \item Concrete vs. Abstract
 Some students felt quite comfortable with the application of rules of inference to concrete items, but had difficulty transferring application of those rules to mathematical symbols.
 \item Symbolization
 consistent with Harel and Sowder's 1998 categorization of concepts, we found students who would attempt to write in symbols, but not understand what was denoted, and consequently were uncertain about appropriate operations. Some of these students were glad to see a progression from pseudocode with long variable names to pseudocode with short variable names to mathematical symbolization (formula translation (FORTRAN) in reverse).
 \item Applicability of single examples
 Some students believed that a few examples constituted a proof. These examples were not generic particular, nor were they transformational, in the sense of Harel and Sowder's 1998 model.
 \item Substructure
 Students familiar with methods, in the sense of object-oriented programming, and with construction of programs involving multiple method calls, did not always recognize that proofs could be built from multiple lemmas, although they did understand that axioms could be applied.
 \item Proofs are used, in computer science, to show resource consumption (complexity class), properties of models of computation, and computability/decidability. No occasion was identified, other than assignment, when students recognized they were undertaking proofs. 
 
 \end{itemize}
 \subsubsection{Relationships}
 
 \subsection{Analysis of Homework and Tests}
 \subsubsection{Proofs}
 Proofs submitted on homework and tests were analyzed in several respects. 
 The overall approach should be valid. For example, students who undertook to prove that the converse was true did not use a valid approach.
 The individual statements should each be warranted. 
 Use of structure, such as lemmas, and care that cases form a partition of the relevant set are gladly noticed.
 Proof attempts that lose track of the goal, and proof attempts that assert with insufficient justification, the goal are noted.
 \subsubsection{Pumping Lemmas}
 We wrote descriptions for each error. Some example descriptions
 are in Table II.
 
  
 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$
 
 A handful of students did exhibit their reasoning that for
 all segmentations there would exist at least one value of 𝑖 that
 would generate a string outside the language.
 We categorized the errors as misunderstandings of one or
 more of:
 1) ∣𝑥𝑦∣ ≤ 𝑝 permits ∣𝑥𝑦∣ < 𝑝\\
 2) 𝑥 is the part of the string prior to the cycle\\
 3) 𝑦 is the part of the string which returns the state of
 the automaton to a previously visited state\\
 4) 𝑧 is the part of the string after the (last) cycle up to
 acceptance\\
 5) 𝑝 − 1 characters is the maximum size of a string
 that need not contain a cycle, (strings of length 𝑝
 or greater must reuse a state)\\
 6) 𝑖 is the number of executions of 𝑦\\
 7) There must be no segmentation for which pumping
 is possible, if pumping cannot occur.\\
 8) A language is a set of strings.\\
 9) A language class is a set of languages.\\
 Categories are shown in the chapter on results (labelled table iii).\\
  
  
 
 
 \subsection{Analysis of Help Session and Tutoring}
 some students, who do know that any statement must and can, be
 either true or false, thought implications must be true.
 
 
 
%  The study proceeded using prior interview experiences to suggest further investigation.
 %  Originally asking about proofs and what they were for, we received answers about proof by induction and found out not all students contemplate why the curriculum contains what it does.
   % (reference Guzdial on students trusting that whatever curriculum they take, is very likely to qualify them for a job).
   %When providing leading questions about why, interview data indicated that not all students apply proof techniques with which they have been successful.
   %So, when application of proofs developed as a part of the study.
   %Consequently, what clues there may be that prompt recall of proof and proof techniques to application to a problem became part of the study, involving structural relevance.
   %Generalization is related to the presence of one situation evolving a response that was learned in the context of a different situation prompted the view of teacher teaching from context of generalization hierarchy present and situation as example and homework situation as another example.
   %What opportunities to foster generalization do students notice?
   
  % \subsection{Within What is a Proof?}
   %The study was devoted to proofs, a subject that can be subdivided.
   %Part of the study was aimed at the idea of domain, directed at the concept that
   %though a variable could identify a scalar, it might also represent a set.
   %Part of the study was aimed at the activity of abstraction, because some students
   %exhibited the ability to operate at one level of abstraction, not necessarily a
   %concrete level, yet the ability to traverse between that level of abstraction and
   %a concrete level seemed to be absent. Other students claimed to be able to
   %understand concrete examples with ease, but to encounter difficulty when
   %short variable names were used within the same logical argument.
   
   %\subsection{Order of Exploration}
   %The order of exploration was data driven, thus the material was sought sometimes
   %in reverse order of the curriculum, almost as if seeking bedrock by starting
   %at a surface, and working downwards.