\paragraph{Codes} \begin{longtable}{|p{7cm}|p{8.5cm}|}\hline \caption{Phenomenographic Analysis of What Students Think Proofs Are}\label{exemplar} \endfirsthead \multicolumn{2}{c}% {{\bfseries \tablename\ \thetable{} -- continued from previous page}} \\ \hline \multicolumn{1}{|c|}{\textbf{Code}} & \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 Code & Representative\\\hline\hline Abstraction, Logical Abstraction &\\ Comprehending and Applying & \\ Connecting Recursion and Induction & \\ Construct Using Patterns & \\ Context for Use &\\ Definition &\\ Difficulty with Mathematical Formulation & they are using many letters for base cases, k, k+1, let's say, and then they are using different letters, t for t and then for k+1 then t and k+1, so, it shows you they don't understand\\ Evaluating Proofs &\\ Generalization from instances &\\ Learning proof by induction &\\ Logic &\\ Logical progression, warrant &\\ Mathematical formulation &\\ Proof and programming &\\ Proof is logical steps &\\ Proof is magical incantation &\\ Proof is validation &\\ Proof relies on definitions &\\ Quantifiers &\\ Representations & visual proofs were just always easier, even to this day, I find that things that I can visualize I tend to do a lot better with, so I you know I had very little trouble for example with graph algorithms, because graphs for me personally were very, very easy to visualize, but heaps for example don't have like heaps are not a distinguished by their visual element\\ Structure &\\ Two too fast, relation or confusion &\\ \end{longtable} \paragraph{Preliminary Categories} \begin{longtable}{|p{7cm}|p{8.5cm}|}\hline \caption{Phenomenographic Analysis of What Students Think Proofs Are}\label{exemplar} \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 \end{longtable} \paragraph{Main theme and its relationships to minor themes} \begin{longtable}{|p{7cm}|p{8.5cm}|}\hline \caption{Phenomenographic Analysis of What Students Think Proofs Are}\label{exemplar} \endfirsthead \multicolumn{2}{c}% {{\bfseries \tablename\ \thetable{} -- continued from previous page}} \\ \hline \multicolumn{1}{|c|}{\textbf{Theme}} & \multicolumn{1}{c|}{\textbf{Relation to Main Theme}} \\ \hline \endhead \hline \multicolumn{2}{|r|}{{Continued on next page}} \\ \hline \endfoot \hline \hline \endlastfoot % \begin{tabular}{|p{7cm}|p{8.5cm}|} \hline Theme & Relation to Main Theme\\\hline\hline \end{longtable} \paragraph{Categories and Relationships} \begin{longtable}{|p{7cm}|p{8.5cm}|}\hline \caption{Phenomenographic Analysis of What Students Think Proofs Are}\label{exemplar} \endfirsthead \multicolumn{2}{c}% {{\bfseries \tablename\ \thetable{} -- continued from previous page}} \\ \hline \multicolumn{1}{|c|}{\textbf{Theme}} & \multicolumn{1}{c|}{\textbf{Relation to Main Theme}} \\ \hline \endhead \hline \multicolumn{2}{|r|}{{Continued on next page}} \\ \hline \endfoot \hline \hline \endlastfoot % \begin{tabular}{|p{7cm}|p{8.5cm}|} \hline Theme & Relation to Main Theme\\\hline\hline \end{longtable} \paragraph{Dimension of Variation and Critical Factors} \begin{longtable}{|p{7cm}|p{8.5cm}|}\hline \caption{Phenomenographic Analysis of What Students Think Proofs Are}\label{exemplar} \endfirsthead \multicolumn{2}{c}% {{\bfseries \tablename\ \thetable{} -- continued from previous page}} \\ \hline \multicolumn{1}{|c|}{\textbf{Dimension of Variation}} & \multicolumn{1}{c|}{\textbf{Critical Factor}} \\ \hline \endhead \hline \multicolumn{2}{|r|}{{Continued on next page}} \\ \hline \endfoot \hline \hline \endlastfoot % \begin{tabular}{|p{7cm}|p{8.5cm}|} \hline Dimension of Variation & Critical Factor\\\hline\hline \end{longtable} \paragraph{Codes} \begin{longtable}{|p{7cm}|p{8.5cm}|}\hline \caption{Phenomenographic Analysis of What Students Think Proofs Are}\label{exemplar} \endfirsthead \multicolumn{2}{c}% {{\bfseries \tablename\ \thetable{} -- continued from previous page}} \\ \hline \multicolumn{1}{|c|}{\textbf{Dimension of Variation}} & \multicolumn{1}{c|}{\textbf{Critical Factor}} \\ \hline \endhead \hline \multicolumn{2}{|r|}{{Continued on next page}} \\ \hline \endfoot \hline \hline \endlastfoot % \begin{tabular}{|p{7cm}|p{8.5cm}|} \hline Dimension of Variation & Critical Factor\\\hline\hline \end{longtable} \paragraph{Preliminary Categories} \begin{longtable}{|p{7cm}|p{8.5cm}|}\hline \caption{Phenomenographic Analysis of What Students Think Proofs Are}\label{exemplar} \endfirsthead \multicolumn{2}{c}% {{\bfseries \tablename\ \thetable{} -- continued from previous page}} \\ \hline \multicolumn{1}{|c|}{\textbf{Dimension of Variation}} & \multicolumn{1}{c|}{\textbf{Critical Factor}} \\ \hline \endhead \hline \multicolumn{2}{|r|}{{Continued on next page}} \\ \hline \endfoot \hline \hline \endlastfoot % \begin{tabular}{|p{7cm}|p{8.5cm}|} \hline Dimension of Variation & Critical Factor\\\hline\hline \end{longtable} \paragraph{Main theme and its relationships to minor themes} \begin{longtable}{|p{7cm}|p{8.5cm}|}\hline \caption{Phenomenographic Analysis of What Students Think Proofs Are}\label{exemplar} \endfirsthead \multicolumn{2}{c}% {{\bfseries \tablename\ \thetable{} -- continued from previous page}} \\ \hline \multicolumn{1}{|c|}{\textbf{Dimension of Variation}} & \multicolumn{1}{c|}{\textbf{Critical Factor}} \\ \hline \endhead \hline \multicolumn{2}{|r|}{{Continued on next page}} \\ \hline \endfoot \hline \hline \endlastfoot % \begin{tabular}{|p{7cm}|p{8.5cm}|} \hline Dimension of Variation & Critical Factor\\\hline\hline \end{longtable} \paragraph{Categories and Relationships} \begin{longtable}{|p{7cm}|p{8.5cm}|}\hline \caption{Phenomenographic Analysis of What Students Think Proofs Are}\label{exemplar} \endfirsthead \multicolumn{2}{c}% {{\bfseries \tablename\ \thetable{} -- continued from previous page}} \\ \hline \multicolumn{1}{|c|}{\textbf{Dimension of Variation}} & \multicolumn{1}{c|}{\textbf{Critical Factor}} \\ \hline \endhead \hline \multicolumn{2}{|r|}{{Continued on next page}} \\ \hline \endfoot \hline \hline \endlastfoot % \begin{tabular}{|p{7cm}|p{8.5cm}|} \hline Dimension of Variation & Critical Factor\\\hline\hline \end{longtable} \paragraph{Dimension of Variation and Critical Factors} \begin{longtable}{|p{7cm}|p{8.5cm}|}\hline \caption{Phenomenographic Analysis of What Students Think Proofs Are}\label{exemplar} \endfirsthead \multicolumn{2}{c}% {{\bfseries \tablename\ \thetable{} -- continued from previous page}} \\ \hline \multicolumn{1}{|c|}{\textbf{Dimension of Variation}} & \multicolumn{1}{c|}{\textbf{Critical Factor}} \\ \hline \endhead \hline \multicolumn{2}{|r|}{{Continued on next page}} \\ \hline \endfoot \hline \hline \endlastfoot % \begin{tabular}{|p{7cm}|p{8.5cm}|} \hline Dimension of Variation & Critical Factor\\\hline\hline \end{longtable} \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 & Just stuff that I had to learn. \\\hline Some students are not sure whether the material in 2500 is the more significant, or whether the proof techniques are the more significant: " i think a proof is um is just steps, little steps, induction, you start with your assumptions from there you build whatever it is whatever it is you want to prove, before i didn't have a clear concept of what a proof was, i had an idea, but and even now i don't feel like i have a very solid "This is a proof". I have the idea, i know how to go through the motion and how to prove a little bit, um, but, i wish there was more um probably like even if it's possible, have like a separate class about to do proofs" &just learning math and not learning where to apply, you don't really appreciate it.\\\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 generalize the domain of applicability for proof techniques: " i suspect that part of the reason that they didn't make connection between inductive proofs and recursive programs is that normally in a workplace setting and probably in a lot of courses, too, you know the programs you write that use recursion probably aren't simply for like evaluating mathematical expressions or um they're not very theoretical so, you probably would never have to so there are a lot more complicated than an inductive proof like most of the problems you need us to prove for induction, so it's not immediately obvious that they're connected, and also people probably rarely you know he's been out of school for a couple of years probably and people in the work force are not probably asked to prove their programs like by induction or anything" "Q: you could think of a tree as being recursively defined, right?\\ A: yes, to an extent i do when i think about the first kind of way we implemented trees i see them as graphs too in java, was binary tree you would have a node and that node would be connected to the you know child nodes, and that i can't say that it's a rec(ursive), well, it's sort of a recursive in a way Interviewer: a tree is defined to be a node that can have subtrees.\\ Participant: yeah. That's kind of a weird way of defining an interesting way of defining it, i guess" Some students see how proofs are applied to algorithms & we're going over graphs from a mathematical and you know theoretical i guess perspective in 2500 and then in 2100 we're going over them in a practical like usage in terms of like solving a maze is what we're going to do with them, so it was really cool when we started doing them in 2100 seemed like I know these, I already learned how to do this''\\\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.\\ Some students appreciate proofs can be used for ascertaining correctness:& "if something holds potential of being extremely useful in a lot of situations, we want to know that our solution is correct, so that is why we write proofs in computer science, also historically probably the first computer scientists some of the first ones i think Lady Ada Lovelace, Turing, were mathematicians, so like probably started off you know a history of writing a lot of proofs"\\ & " proofs are used when you want to when you have concept and you want to prove it, like you want to make sure that that it's true"\\ & 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.\\\hline & i think i mean proofs are about um you know building the next layer of truth kind of showing what you could do or compute um so in computer science for example uh by proving something we're just showing that its possible um we're kind of setting bounds on what we can do and can't do\\\hline & it might not be the highest lower bound, but it's the highest lower bound we know of, that we can prove, yet the best algorithm we have been able to find takes much more resources, time, memory, messages, then those proofs show us a window\\\hline %\end{tabular} Some students find that creating proofs related to algorithms can be more difficult than problems they practiced on when learning & i have to prove that uh if there is an edge um connecting two points and there is a path connects two points with edges with all weights less than this edge have to show that that edge wouldn't be in any minimum spanning tree, a lot of things going on there, not like a theorem with a couple simple assumptions and you have to show result, you know you have to show there are multiple minimum spanning trees possibly things like that it's not as uh i mean the way proofs come up isn't as straightforward i find, makes a little bit confusing sometimes,\\\hline Some students agreed with the idea that proofs could guide algorithm creation: & "Q: Do you think it changes the way you invent algorithms? A: I haven't thought about that actually, but, it does. It does."\\\hline & "that way you know that you're code, what you're how it's going to be."\\\hline \end{longtable} \paragraph{Codes} \begin{longtable}{|p{7cm}|p{8.5cm}|}\hline \caption{Phenomenographic Analysis of What Students Think Proofs Are}\label{exemplar} \endfirsthead \multicolumn{2}{c}% {{\bfseries \tablename\ \thetable{} -- continued from previous page}} \\ \hline \multicolumn{1}{|c|}{\textbf{Dimension of Variation}} & \multicolumn{1}{c|}{\textbf{Critical Factor}} \\ \hline \endhead \hline \multicolumn{2}{|r|}{{Continued on next page}} \\ \hline \endfoot \hline \hline \endlastfoot % \begin{tabular}{|p{7cm}|p{8.5cm}|} \hline Dimension of Variation & Critical Factor\\\hline\hline \end{longtable} \paragraph{Preliminary Categories} \begin{longtable}{|p{7cm}|p{8.5cm}|}\hline \caption{Phenomenographic Analysis of What Students Think Proofs Are}\label{exemplar} \endfirsthead \multicolumn{2}{c}% {{\bfseries \tablename\ \thetable{} -- continued from previous page}} \\ \hline \multicolumn{1}{|c|}{\textbf{Dimension of Variation}} & \multicolumn{1}{c|}{\textbf{Critical Factor}} \\ \hline \endhead \hline \multicolumn{2}{|r|}{{Continued on next page}} \\ \hline \endfoot \hline \hline \endlastfoot % \begin{tabular}{|p{7cm}|p{8.5cm}|} \hline Dimension of Variation & Critical Factor\\\hline\hline \end{longtable} \paragraph{Main theme and its relationships to minor themes} \begin{longtable}{|p{7cm}|p{8.5cm}|}\hline \caption{Phenomenographic Analysis of What Students Think Proofs Are}\label{exemplar} \endfirsthead \multicolumn{2}{c}% {{\bfseries \tablename\ \thetable{} -- continued from previous page}} \\ \hline \multicolumn{1}{|c|}{\textbf{Dimension of Variation}} & \multicolumn{1}{c|}{\textbf{Critical Factor}} \\ \hline \endhead \hline \multicolumn{2}{|r|}{{Continued on next page}} \\ \hline \endfoot \hline \hline \endlastfoot % \begin{tabular}{|p{7cm}|p{8.5cm}|} \hline Dimension of Variation & Critical Factor\\\hline\hline \end{longtable} \paragraph{Categories and Relationships} \begin{longtable}{|p{7cm}|p{8.5cm}|}\hline \caption{Phenomenographic Analysis of What Students Think Proofs Are}\label{exemplar} \endfirsthead \multicolumn{2}{c}% {{\bfseries \tablename\ \thetable{} -- continued from previous page}} \\ \hline \multicolumn{1}{|c|}{\textbf{Dimension of Variation}} & \multicolumn{1}{c|}{\textbf{Critical Factor}} \\ \hline \endhead \hline \multicolumn{2}{|r|}{{Continued on next page}} \\ \hline \endfoot \hline \hline \endlastfoot % \begin{tabular}{|p{7cm}|p{8.5cm}|} \hline Dimension of Variation & Critical Factor\\\hline\hline \end{longtable} \paragraph{Dimension of Variation and Critical Factors} \begin{longtable}{|p{7cm}|p{8.5cm}|}\hline \caption{Phenomenographic Analysis of What Students Think Proofs Are}\label{exemplar} \endfirsthead \multicolumn{2}{c}% {{\bfseries \tablename\ \thetable{} -- continued from previous page}} \\ \hline \multicolumn{1}{|c|}{\textbf{Dimension of Variation}} & \multicolumn{1}{c|}{\textbf{Critical Factor}} \\ \hline \endhead \hline \multicolumn{2}{|r|}{{Continued on next page}} \\ \hline \endfoot \hline \hline \endlastfoot % \begin{tabular}{|p{7cm}|p{8.5cm}|} \hline Dimension of Variation & Critical Factor\\\hline\hline \end{longtable} \paragraph{Codes} \begin{longtable}{|p{7cm}|p{8.5cm}|}\hline \caption{Phenomenographic Analysis of What Students Think Proofs Are}\label{exemplar4} \endfirsthead \multicolumn{2}{c}% {{\bfseries \tablename\ \thetable{} -- continued from previous page}} \\ \hline \multicolumn{1}{|c|}{\textbf{Dimension of Variation}} & \multicolumn{1}{c|}{\textbf{Critical Factor}} \\ \hline \endhead \hline \multicolumn{2}{|r|}{{Continued on next page}} \\ \hline \endfoot \hline \hline \endlastfoot % \begin{tabular}{|p{7cm}|p{8.5cm}|} \hline Dimension of Variation & Critical Factor\\\hline\hline \end{longtable} \paragraph{Preliminary Categories} \begin{longtable}{|p{7cm}|p{8.5cm}|}\hline \caption{Phenomenographic Analysis of What Students Think Proofs Are}\label{exemplar} \endfirsthead \multicolumn{2}{c}% {{\bfseries \tablename\ \thetable{} -- continued from previous page}} \\ \hline \multicolumn{1}{|c|}{\textbf{Dimension of Variation}} & \multicolumn{1}{c|}{\textbf{Critical Factor}} \\ \hline \endhead \hline \multicolumn{2}{|r|}{{Continued on next page}} \\ \hline \endfoot \hline \hline \endlastfoot % \begin{tabular}{|p{7cm}|p{8.5cm}|} \hline Dimension of Variation & Critical Factor\\\hline\hline \end{longtable} \paragraph{Main theme and its relationships to minor themes} \begin{longtable}{|p{7cm}|p{8.5cm}|}\hline \caption{Phenomenographic Analysis of What Students Think Proofs Are}\label{exemplar} \endfirsthead \multicolumn{2}{c}% {{\bfseries \tablename\ \thetable{} -- continued from previous page}} \\ \hline \multicolumn{1}{|c|}{\textbf{Dimension of Variation}} & \multicolumn{1}{c|}{\textbf{Critical Factor}} \\ \hline \endhead \hline \multicolumn{2}{|r|}{{Continued on next page}} \\ \hline \endfoot \hline \hline \endlastfoot % \begin{tabular}{|p{7cm}|p{8.5cm}|} \hline Dimension of Variation & Critical Factor\\\hline\hline \end{longtable} \paragraph{Categories and Relationships} \begin{longtable}{|p{7cm}|p{8.5cm}|}\hline \caption{Phenomenographic Analysis of What Students Think Proofs Are}\label{exemplar} \endfirsthead \multicolumn{2}{c}% {{\bfseries \tablename\ \thetable{} -- continued from previous page}} \\ \hline \multicolumn{1}{|c|}{\textbf{Dimension of Variation}} & \multicolumn{1}{c|}{\textbf{Critical Factor}} \\ \hline \endhead \hline \multicolumn{2}{|r|}{{Continued on next page}} \\ \hline \endfoot \hline \hline \endlastfoot % \begin{tabular}{|p{7cm}|p{8.5cm}|} \hline Dimension of Variation & Critical Factor\\\hline\hline \end{longtable} \paragraph{Dimension of Variation and Critical Factors} \begin{longtable}{|p{7cm}|p{8.5cm}|}\hline \caption{Phenomenographic Analysis of What Students Think Proofs Are}\label{exemplar} \endfirsthead \multicolumn{2}{c}% {{\bfseries \tablename\ \thetable{} -- continued from previous page}} \\ \hline \multicolumn{1}{|c|}{\textbf{Dimension of Variation}} & \multicolumn{1}{c|}{\textbf{Critical Factor}} \\ \hline \endhead \hline \multicolumn{2}{|r|}{{Continued on next page}} \\ \hline \endfoot \hline \hline \endlastfoot % \begin{tabular}{|p{7cm}|p{8.5cm}|} \hline Dimension of Variation & Critical Factor\\\hline\hline \end{longtable} \section{Does this go anywhere? 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. \paragraph{Codes} \begin{longtable}{|p{7cm}|p{8.5cm}|}\hline \caption{Phenomenographic Analysis of What Students Think Proofs Are}\label{exemplar} \endfirsthead \multicolumn{2}{c}% {{\bfseries \tablename\ \thetable{} -- continued from previous page}} \\ \hline \multicolumn{1}{|c|}{\textbf{Dimension of Variation}} & \multicolumn{1}{c|}{\textbf{Critical Factor}} \\ \hline \endhead \hline \multicolumn{2}{|r|}{{Continued on next page}} \\ \hline \endfoot \hline \hline \endlastfoot % \begin{tabular}{|p{7cm}|p{8.5cm}|} \hline Dimension of Variation & Critical Factor\\\hline\hline \end{longtable} \paragraph{Preliminary Categories} \begin{longtable}{|p{7cm}|p{8.5cm}|}\hline \caption{Phenomenographic Analysis of What Students Think Proofs Are}\label{exemplar} \endfirsthead \multicolumn{2}{c}% {{\bfseries \tablename\ \thetable{} -- continued from previous page}} \\ \hline \multicolumn{1}{|c|}{\textbf{Dimension of Variation}} & \multicolumn{1}{c|}{\textbf{Critical Factor}} \\ \hline \endhead \hline \multicolumn{2}{|r|}{{Continued on next page}} \\ \hline \endfoot \hline \hline \endlastfoot % \begin{tabular}{|p{7cm}|p{8.5cm}|} \hline Dimension of Variation & Critical Factor\\\hline\hline \end{longtable} \paragraph{Main theme and its relationships to minor themes} \begin{longtable}{|p{7cm}|p{8.5cm}|}\hline \caption{Phenomenographic Analysis of What Students Think Proofs Are}\label{exemplar} \endfirsthead \multicolumn{2}{c}% {{\bfseries \tablename\ \thetable{} -- continued from previous page}} \\ \hline \multicolumn{1}{|c|}{\textbf{Dimension of Variation}} & \multicolumn{1}{c|}{\textbf{Critical Factor}} \\ \hline \endhead \hline \multicolumn{2}{|r|}{{Continued on next page}} \\ \hline \endfoot \hline \hline \endlastfoot % \begin{tabular}{|p{7cm}|p{8.5cm}|} \hline Dimension of Variation & Critical Factor\\\hline\hline \end{longtable} \paragraph{Categories and Relationships} \begin{longtable}{|p{7cm}|p{8.5cm}|}\hline \caption{Phenomenographic Analysis of What Students Think Proofs Are}\label{exemplar} \endfirsthead \multicolumn{2}{c}% {{\bfseries \tablename\ \thetable{} -- continued from previous page}} \\ \hline \multicolumn{1}{|c|}{\textbf{Dimension of Variation}} & \multicolumn{1}{c|}{\textbf{Critical Factor}} \\ \hline \endhead \hline \multicolumn{2}{|r|}{{Continued on next page}} \\ \hline \endfoot \hline \hline \endlastfoot % \begin{tabular}{|p{7cm}|p{8.5cm}|} \hline Dimension of Variation & Critical Factor\\\hline\hline \end{longtable} \paragraph{Dimension of Variation and Critical Factors} \begin{longtable}{|p{7cm}|p{8.5cm}|}\hline \caption{Phenomenographic Analysis of What Students Think Proofs Are}\label{exemplar} \endfirsthead \multicolumn{2}{c}% {{\bfseries \tablename\ \thetable{} -- continued from previous page}} \\ \hline \multicolumn{1}{|c|}{\textbf{Dimension of Variation}} & \multicolumn{1}{c|}{\textbf{Critical Factor}} \\ \hline \endhead \hline \multicolumn{2}{|r|}{{Continued on next page}} \\ \hline \endfoot \hline \hline \endlastfoot % \begin{tabular}{|p{7cm}|p{8.5cm}|} \hline Dimension of Variation & Critical Factor\\\hline\hline \end{longtable} \subsubsection{Combined 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 undergraduate students recognized they were undertaking proofs. \item Among graduate students, proofs were undertaken in the context of preparing manuscripts for publication. These were scheduled to be approached after algorithm design, though retroactive adjustment of algorithms did occur for simplifying the proof. \end{itemize} \subsubsection{Combined 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 $i$ that would generate a string outside the language. We categorized the errors as misunderstandings of one or more of: \cite[get some page reference]{sipser2012introduction} 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).\\ \paragraph{Codes} \begin{longtable}{|p{7cm}|p{8.5cm}|}\hline \caption{Phenomenographic Analysis of What Students Think Proofs Are}\label{exemplar} \endfirsthead \multicolumn{2}{c}% {{\bfseries \tablename\ \thetable{} -- continued from previous page}} \\ \hline \multicolumn{1}{|c|}{\textbf{Dimension of Variation}} & \multicolumn{1}{c|}{\textbf{Critical Factor}} \\ \hline \endhead \hline \multicolumn{2}{|r|}{{Continued on next page}} \\ \hline \endfoot \hline \hline \endlastfoot % \begin{tabular}{|p{7cm}|p{8.5cm}|} \hline Dimension of Variation & Critical Factor\\\hline\hline \end{longtable} \paragraph{Preliminary Categories} \begin{longtable}{|p{7cm}|p{8.5cm}|}\hline \caption{Phenomenographic Analysis of What Students Think Proofs Are}\label{exemplar} \endfirsthead \multicolumn{2}{c}% {{\bfseries \tablename\ \thetable{} -- continued from previous page}} \\ \hline \multicolumn{1}{|c|}{\textbf{Dimension of Variation}} & \multicolumn{1}{c|}{\textbf{Critical Factor}} \\ \hline \endhead \hline \multicolumn{2}{|r|}{{Continued on next page}} \\ \hline \endfoot \hline \hline \endlastfoot % \begin{tabular}{|p{7cm}|p{8.5cm}|} \hline Dimension of Variation & Critical Factor\\\hline\hline \end{longtable} \paragraph{Main theme and its relationships to minor themes} \begin{longtable}{|p{7cm}|p{8.5cm}|}\hline \caption{Phenomenographic Analysis of What Students Think Proofs Are}\label{exemplar} \endfirsthead \multicolumn{2}{c}% {{\bfseries \tablename\ \thetable{} -- continued from previous page}} \\ \hline \multicolumn{1}{|c|}{\textbf{Dimension of Variation}} & \multicolumn{1}{c|}{\textbf{Critical Factor}} \\ \hline \endhead \hline \multicolumn{2}{|r|}{{Continued on next page}} \\ \hline \endfoot \hline \hline \endlastfoot % \begin{tabular}{|p{7cm}|p{8.5cm}|} \hline Dimension of Variation & Critical Factor\\\hline\hline \end{longtable} \paragraph{Categories and Relationships} \begin{longtable}{|p{7cm}|p{8.5cm}|}\hline \caption{Phenomenographic Analysis of What Students Think Proofs Are}\label{exemplar} \endfirsthead \multicolumn{2}{c}% {{\bfseries \tablename\ \thetable{} -- continued from previous page}} \\ \hline \multicolumn{1}{|c|}{\textbf{Dimension of Variation}} & \multicolumn{1}{c|}{\textbf{Critical Factor}} \\ \hline \endhead \hline \multicolumn{2}{|r|}{{Continued on next page}} \\ \hline \endfoot \hline \hline \endlastfoot % \begin{tabular}{|p{7cm}|p{8.5cm}|} \hline Dimension of Variation & Critical Factor\\\hline\hline \end{longtable} \paragraph{Dimension of Variation and Critical Factors} \begin{longtable}{|p{7cm}|p{8.5cm}|}\hline \caption{Phenomenographic Analysis of What Students Think Proofs Are}\label{exemplar} \endfirsthead \multicolumn{2}{c}% {{\bfseries \tablename\ \thetable{} -- continued from previous page}} \\ \hline \multicolumn{1}{|c|}{\textbf{Dimension of Variation}} & \multicolumn{1}{c|}{\textbf{Critical Factor}} \\ \hline \endhead \hline \multicolumn{2}{|r|}{{Continued on next page}} \\ \hline \endfoot \hline \hline \endlastfoot % \begin{tabular}{|p{7cm}|p{8.5cm}|} \hline Dimension of Variation & Critical Factor\\\hline\hline \end{longtable} \paragraph{Codes} \begin{longtable}{|p{7cm}|p{8.5cm}|}\hline \caption{Phenomenographic Analysis of What Students Think Proofs Are}\label{exemplar} \endfirsthead \multicolumn{2}{c}% {{\bfseries \tablename\ \thetable{} -- continued from previous page}} \\ \hline \multicolumn{1}{|c|}{\textbf{Dimension of Variation}} & \multicolumn{1}{c|}{\textbf{Critical Factor}} \\ \hline \endhead \hline \multicolumn{2}{|r|}{{Continued on next page}} \\ \hline \endfoot \hline \hline \endlastfoot % \begin{tabular}{|p{7cm}|p{8.5cm}|} \hline Dimension of Variation & Critical Factor\\\hline\hline \end{longtable} \paragraph{Preliminary Categories} \begin{longtable}{|p{7cm}|p{8.5cm}|}\hline \caption{Phenomenographic Analysis of What Students Think Proofs Are}\label{exemplar} \endfirsthead \multicolumn{2}{c}% {{\bfseries \tablename\ \thetable{} -- continued from previous page}} \\ \hline \multicolumn{1}{|c|}{\textbf{Dimension of Variation}} & \multicolumn{1}{c|}{\textbf{Critical Factor}} \\ \hline \endhead \hline \multicolumn{2}{|r|}{{Continued on next page}} \\ \hline \endfoot \hline \hline \endlastfoot % \begin{tabular}{|p{7cm}|p{8.5cm}|} \hline Dimension of Variation & Critical Factor\\\hline\hline \end{longtable} \paragraph{Main theme and its relationships to minor themes} \begin{longtable}{|p{7cm}|p{8.5cm}|}\hline \caption{Phenomenographic Analysis of What Students Think Proofs Are}\label{exemplar} \endfirsthead \multicolumn{2}{c}% {{\bfseries \tablename\ \thetable{} -- continued from previous page}} \\ \hline \multicolumn{1}{|c|}{\textbf{Dimension of Variation}} & \multicolumn{1}{c|}{\textbf{Critical Factor}} \\ \hline \endhead \hline \multicolumn{2}{|r|}{{Continued on next page}} \\ \hline \endfoot \hline \hline \endlastfoot % \begin{tabular}{|p{7cm}|p{8.5cm}|} \hline Dimension of Variation & Critical Factor\\\hline\hline \end{longtable} \paragraph{Categories and Relationships} \begin{longtable}{|p{7cm}|p{8.5cm}|}\hline \caption{Phenomenographic Analysis of What Students Think Proofs Are}\label{exemplar} \endfirsthead \multicolumn{2}{c}% {{\bfseries \tablename\ \thetable{} -- continued from previous page}} \\ \hline \multicolumn{1}{|c|}{\textbf{Dimension of Variation}} & \multicolumn{1}{c|}{\textbf{Critical Factor}} \\ \hline \endhead \hline \multicolumn{2}{|r|}{{Continued on next page}} \\ \hline \endfoot \hline \hline \endlastfoot % \begin{tabular}{|p{7cm}|p{8.5cm}|} \hline Dimension of Variation & Critical Factor\\\hline\hline \end{longtable} \paragraph{Dimension of Variation and Critical Factors} \begin{longtable}{|p{7cm}|p{8.5cm}|}\hline \caption{Phenomenographic Analysis of What Students Think Proofs Are}\label{exemplar} \endfirsthead \multicolumn{2}{c}% {{\bfseries \tablename\ \thetable{} -- continued from previous page}} \\ \hline \multicolumn{1}{|c|}{\textbf{Dimension of Variation}} & \multicolumn{1}{c|}{\textbf{Critical Factor}} \\ \hline \endhead \hline \multicolumn{2}{|r|}{{Continued on next page}} \\ \hline \endfoot \hline \hline \endlastfoot % \begin{tabular}{|p{7cm}|p{8.5cm}|} \hline Dimension of Variation & Critical Factor\\\hline\hline \end{longtable} \paragraph{Codes} \begin{longtable}{|p{7cm}|p{8.5cm}|}\hline \caption{Phenomenographic Analysis of What Students Think Proofs Are}\label{exemplar} \endfirsthead \multicolumn{2}{c}% {{\bfseries \tablename\ \thetable{} -- continued from previous page}} \\ \hline \multicolumn{1}{|c|}{\textbf{Dimension of Variation}} & \multicolumn{1}{c|}{\textbf{Critical Factor}} \\ \hline \endhead \hline \multicolumn{2}{|r|}{{Continued on next page}} \\ \hline \endfoot \hline \hline \endlastfoot % \begin{tabular}{|p{7cm}|p{8.5cm}|} \hline Dimension of Variation & Critical Factor\\\hline\hline \end{longtable} \paragraph{Preliminary Categories} \begin{longtable}{|p{7cm}|p{8.5cm}|}\hline \caption{Phenomenographic Analysis of What Students Think Proofs Are}\label{exemplar} \endfirsthead \multicolumn{2}{c}% {{\bfseries \tablename\ \thetable{} -- continued from previous page}} \\ \hline \multicolumn{1}{|c|}{\textbf{Dimension of Variation}} & \multicolumn{1}{c|}{\textbf{Critical Factor}} \\ \hline \endhead \hline \multicolumn{2}{|r|}{{Continued on next page}} \\ \hline \endfoot \hline \hline \endlastfoot % \begin{tabular}{|p{7cm}|p{8.5cm}|} \hline Dimension of Variation & Critical Factor\\\hline\hline \end{longtable} \paragraph{Main theme and its relationships to minor themes} \begin{longtable}{|p{7cm}|p{8.5cm}|}\hline \caption{Phenomenographic Analysis of What Students Think Proofs Are}\label{exemplar} \endfirsthead \multicolumn{2}{c}% {{\bfseries \tablename\ \thetable{} -- continued from previous page}} \\ \hline \multicolumn{1}{|c|}{\textbf{Dimension of Variation}} & \multicolumn{1}{c|}{\textbf{Critical Factor}} \\ \hline \endhead \hline \multicolumn{2}{|r|}{{Continued on next page}} \\ \hline \endfoot \hline \hline \endlastfoot % \begin{tabular}{|p{7cm}|p{8.5cm}|} \hline Dimension of Variation & Critical Factor\\\hline\hline \end{longtable} \paragraph{Categories and Relationships} \begin{longtable}{|p{7cm}|p{8.5cm}|}\hline \caption{Phenomenographic Analysis of What Students Think Proofs Are}\label{exemplar} \endfirsthead \multicolumn{2}{c}% {{\bfseries \tablename\ \thetable{} -- continued from previous page}} \\ \hline \multicolumn{1}{|c|}{\textbf{Dimension of Variation}} & \multicolumn{1}{c|}{\textbf{Critical Factor}} \\ \hline \endhead \hline \multicolumn{2}{|r|}{{Continued on next page}} \\ \hline \endfoot \hline \hline \endlastfoot % \begin{tabular}{|p{7cm}|p{8.5cm}|} \hline Dimension of Variation & Critical Factor\\\hline\hline \end{longtable}