proofvsAlg.tex

\subsection{Difficulty Formulating}
Some students lack conviction about proofs being correct, indeed, aren't using definitions and warrants "the other part of it is i think it has to do with fluency, right, because we don't speak math".

"when it's kind of like solve this problem here's the formal definition go for it i'm like whoa"

For validity/triangulation we have an observation from a faculty member "there's no chance that they are going to be able to write a proof, because they can't appeal to the definition".

Some students might possess intuition, but lack skill in formulation: "i see the relationship (between recursion and proof by mathematic induction), but i   often   have trouble making the formal connection."

\subsection{Missing Transformation}

Students perceive a difference between a proof and an algorithm, having to do with carrying out a process: "the code actually accomplishes something and it's easy to go from state 1 to state n" vs. "(a proof is) one total absolute truth we don't actually use the math language to accomplish anything."

It seems that the transformation occurring in the proof, from one logical representation to another, is sometimes missed. In phenomenography, we would say that this conceptualization of proof is incomplete, because one of the component aspects of the idea of proof, is missing in this conceptualization. If the students are not engaged with the transformation occurring in the proof, it seems likely that the students will not approach attempting a proof as envisioning and expressing a transformation.
 
 \subsection{Learning Transformation}

Some students are conscious of transformation but  lack intuition about direction of transformations starting from one representation and reaching another 
"analyzing every possible manipulation"

"trying everything, just going in every single direction, putting in every law, trying moving everything around, after maybe 20 to 30 (minutes), I kind of saw where i was going, ... my first one took me like an hour just to write i think it was a total of 5 steps using like 2 laws ... after a while it got to the point where i could see it, i understood where i was going with the laws and knew which ones to use". "it takes a while to see which one you're going to use but definitely after a while and after using them the time that it took for me to kind of react and realize which ones to use went down"

This can usefully be compared with the thinking of a programmer who knows several languages. First they know the transformations they wish to perform, in a generalized, non-language specific way, and then they think about how to express those transformations in the language of the present moment. (Gries has recommended a similar thing. I didn't find the reference, but it is in Science of Programming).
In summary, they don't have a feel for how to move towards where they want to go, "like mathematical induction because ... a given set of steps" and also don't have a feel for which moves are not allowed, due to lack of
warrant. 

By contrast with the multilingual developer, our students of proof might not have any mental representation of sufficient precision to support planning of the transformations needed for a proof. Then, they have not abstracted from several of these, into a generalized non-language specific representation for transformations, and they are not separating this non-language specific creation process from a later stage of translation into mathematical formulation. We can decide that mathematical formulation is the one generalized form, having developed over time in a large community. Nevertheless, creating a plan, and expressing that plan in a language can be seen as separate. Ability at both activities could be guided and nurtured.

Some students do see the transformation process in proving, at least in proof by mathematical induction: "proof by induction is a recursive process that you make, you define your inductive step and you apply it repeatedly, until you arrive at your destination".

It could be that, for seeing transformation processes, the ability to abstract is being used, and students who are weak at abstraction might not be discerning.  

Some students are confused about abstraction: "i'm not too fond of induction, for whatever reason, i don't know why i think that one made the least sense when i was learning i was learning you could just say there's a base case i increment once and i guess abstracting from that, and it's true for everything it seems i don't know, it seems kind of weird, sometimes when you think about it".

At a concrete level, students might perceive more easily: "Dominos! That's what just happened in my brain, cover this tree with dominos.
I just saw, i never thought of that problem i suppose, i mean, if it's come up to me it wasn't in the context of recursion, that or at least not that i was aware of."

Some students do appreciate the transformation at a more abstract level.
"those would be very helpful for proving that recursive algorithms would work. The base case would be the initial proof, and then variable to show that it could work for any number of iterations would show that it's a very valuable algorithm."

"you have like you know what you're looking for, it's almost like working backwards \ldots, i know what i'm looking for and i know where i'm starting,  if i can kind of work both ways i can find the path pretty easily"

"i'll start at the bottom to get something \ldots i'm supposed to come out with and will kind of modify that to see if it's something that looks a little more like one of my other rules, and kind of start linking them from both ends"


\subsection{Learning Transformation Patterns}
"proof by contrapositive, which was very difficult"

"there are patterns that you can use, like transitive patterns like if a=b and b=c then a= c, and there a list of these patterns that can be used to identify if proofs are logical.  If you could still between each step, I forget the term but it's like   false positive,   when you   think something   seems like a conclusion but it  really does not follow" 

"it always seems to be some kind of trick, how could I come up with this working on it for years or whatever, I think it's more the systematic thing, oh, this is a contradiction, or induction, I can definitely do that, and that sets you up a framework, you can actually prove something through that, then it becomes more obvious"

\subsection{Divergent Reasoning Styles}

Some students feel that the reasoning associated with planning an algorithm is different from the reasoning associated with planning a proof: when comparing writing a program using recursion and writing a proof by mathematical induction, a student has said that "when i actually have to do one or the other, i find it's an entirely different approach to reasoning about the problem".

\subsection{Perceived Differences}
Perceived differences can exist, even when abstraction is available. "I would say I am quite comfortable with both  recursion programming and inductive mathematical induction   but,  i'm not sure that any of the cognitive machinery that i use to deal with either of them is common to the two processes".

"we're using all these mathematical principles but the difference (from algorithms) is that a proof is something you only use once"

"with recursion for example learning recursion you can use, you can apply the principle to many many different algorithms and can still see how it's recursion you can do this with trees, \ldots, but proofs, that's it."

\subsection{Perceived Similarities}
"i tend to just write code, \ldots it's always been proof enough for me"

"proof would be a tool to prove that your hypothesis is correct, it wouldn't entirely replace experimentation, but it would certainly back up your experiments"

"(Int)do you think it changes the way you invent algorithms?\\
I haven't thought about that actually, but, it does. it does."

\subsection{Learning, but also Forgetting}
"in high school geometry i think that was probably the first time i was introduced to proofs, that was so long ago i don't really remember much about it, but i remember everyone else in the class hated it, certainly and i don't know if i really hated it, i didn't i didn't enjoy it that much"

"it was certainly taught to me in discrete systems, it didn't stick, because back then i didn't fully i didn't fully grasp the notion of recursion yet, it was certainly taught, attempted to be taught, but it was a little harder for me to solidify it, and then i certainly learned it again   in   algorithms and complexity"

"i'm not comfortable with that, was comfortable a year ago"

"the aha moment have always been proofs written for induction, despite the fact that I've done them multiple times, they go over my head and I have to relearn proofs by induction"

Professor Rota\cite{rota1997phenomenology} has observed that beautiful proofs are more memorable. There may be a connection between beauty and brevity, so it may be that beautiful proofs are more memorable because they are often shorter. (Go see whether Professor Rota discussed this.)

\subsection{Problem Solving}
We hope to help students learn to solve problems by analysis of the problem into parts, dividing the problem, and conquering it through solving the subproblems. We hope this for both algorithms and proofs. Some students are not seeing this.

"in the context of computer science, because the analogous notions in programming they're completely fine with, but in the setting of trying to prove a mathematical statement, those things kind of go out the door."

"when I start to create a proof, most commonly mathematical induction because this method of proof seems most straightforward to me, and most of these assignments we did mathematical induction, so that's what goes through my mind first"

The notion of problem solving combines with the notion of most frequently applied method. "depends on what you're proving.  my professor in 2500 says induction is the most important form of proving we do in the class, so, I guess first use induction"


\subsection{Divide and Conquer}
"the TA was saying yesterday, if you prove small blocks of the program true, you prove the whole thing is true, that's like that, and there you can build up, you build up to larger program, or it you have a large one you can break it up to prove each one of those are true"

"breaking them down into i have this chunk, i have (that) chunk, i'm going to label and use this chunk, i'm going to label and use (that) chunk"

"you have to take it all in at once in order to understand it, whereas code you know you sort of easily understand like piece by piece"

\subsection{Practice}
"the best way to learn about things you can do with proofs and how to write proofs is to do them, so i think problem a lot of people have is they just haven't written very many proofs then are expected to do things and they just don't have you know the tools they haven't built up the toolsets to handle that"

Some students have written quite a few programs before they arrive in our curriculum, some write programs outside of class, recreationally or for work. Some of our students have written proofs outside of our curriculum; this was found only among the math majors.

However, some students do not have extra experience with proofs: "basically i don't think separate from a homework assignment for me".


\subsection{Ideal Understanding}
Some students have learned what we hoped: "a proof is a list of statements where the next one builds on the previous one to prove a final statement conclusion".

\subsection{Assumed Correct, Excepting Bugs}

Some students are overconfident about program construction, having unwarranted (haha) intrinsic conviction about their programs, expecting them to be correct, complete. There is a name for deviations for departures of the ideal, correct, complete program, namely bugs. Warrants are not needed, definitions are from a limited set of keywords. It might even be the case that if a language is perceived to be too overloaded with constructs (sounds like: have to remember all of those theorems) it gets replaced with another language that seems more suited/matched to the way programmers think about solving problems (In Java you have to ... but in python you only have to ... .)

\subsection{Seeking Insight from Contrast}

"students can construct programs, more ably than they can construct proofs"

Is there a higher barrier to admission, to getting started writing proofs? Is it necessary to know ("all those theorems")? Are the problems addressed with algorithms and coding always much easier than the problems addressed with proof? Is the nature of what's being transformed so very different? Maybe. What's being transformed in proof is that mathematical formulation that students are awkward with. What's being transformed in algorithms and programs is data and data structures, to which we devote much attention. Why do proof problems seem like one shot/over and done with, when algorithms more clearly have wide applicability? Why are students more hesitant to create proofs than code? Why would a student feel,


 Why are some proof techniques more accessible than others? "induction proofs, ... we did that in 2500, and then we also did the laws of logic proofs". Is it the absence of a compiler? Professor Velleman at Amherst made a software tool from which selection of next step could be made. Why do some creators of algorithms first create an algorithm, and then try to prove it? (compare with Gries, Science of Computer Programming) What is it about the algorithmic representation of the transformation that makes it more approachable? (bound vs free variables?) 



Combining some inherent difficulty with the representation with the absence of structural relevance, we can obtain a hint about a student's motivation to improve. At the beginning of the curriculum, there are some students who are at a loss creating code, too. 
"we learned how to write code, but we didn't learn how to code"
 "other than that (formulaic header code) it's  always an adventure to see how code starts" 
 What helps students intuit what to do next in an algorithm, compared with proof ("just me trying everything, must going in every single direction, putting in every law, moving everything around, until after maybe 20 or 30 minutes I kind of saw where I was going, my first one took like an hour for fives steps using 2 laws. After a while it got to the point where I could see, I understood where I was going with the laws and knew which ones to use")
Some students learn how to comprehend proofs about resource consumption, yet are not confident of synthesis "give me the runtime, ... in the real world, ...you need to do that, you ... need to be able to definitively prove that it works or parameters, i don't really feel confident to be able to do that on my own at this moment, and any further, any more preparation it would be greatly appreciated."

You start writing your code, look at the proof of the algorithm, take it on faith (that the algorithm is correct) and say, where is it that the code doesn't match the algorithm, they assume the algorithm is right. (In other words the proof is not convincing.) For students who do not find proofs convincing, it is no surprise that they say they never undertake to prove anything that is not assigned. Moreover, they use code to obtain some measure of confidence. "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" It seems that students have trouble with counterfactuals: this edge is not in the graph, why is this edge not in the graph? "the way proofs come up isn't straightforward... makes it confusing"