\chapter{Introduction} % %the point is to motivate the rest of the work, pique interest in proofs in CS Proofs are taught in the computer science curriculum, with the intent that students will be able to use these to ascertain whether the algorithms they have learned are applicable to the problems they wish to solve. Moreover, it is desirable that students will be able to show that the resource consumption of their implementation is suitable for the circumstances of their implementations. Certainly there may be additional reasons. It can be the case that not every student gains the whole of the capabilities that we might wish. Insight into the partial understandings students do achieve might enlighten us as to specific aspects of the material, increased emphasis on which might improve student learning. The purpose of the research is to discover the understandings of proof we find in the population of students of computer science (and engineering), so as to provide information that might be helpful for teaching. It is a qualitative study, because we seek the variety in the nature of the various understandings. We do not attempt to establish the relative frequencies with which these conceptualizations occur.\\ The analytic lens of the study is phenomenography, including variation theory.\\ In this chapter we list our research questions addressing conceptions of proof in students of computer science. We briefly summarize what distinguishes qualitative research from other research. We provide a short description of phenomenography as extended to variation theory. We explain how phenomenography and variation theory are suited to investigate the questions we have pursued. It is important for students of computer science %, and of computer science and %engineering (called, in the following, computer science) to comprehend, apply, and synthesize proofs. %, and to be able to synthesize simple proofs. These skills are needed because proofs are used to demonstrate the resource needs and performance effects of algorithms, as well as for safety, liveness, and correctness/accuracy. We claim herein that some students, having learned an algorithm, are not certain of the problem environment in which this kind of algorithm is effective, and as a result are reluctant to apply the algorithm. It is desirable for students to be able %correctly, to develop internal conviction, and to ascertain that an algorithm is a good match for a problem, which can sometimes be proved, otherwise their knowledge of the algorithm is less useful. It is important for instructors to impart, efficiently and effectively, knowledge about proof to the students. We will be using phenomenography. Phenomenography and its outgrowth, variation theory, \cite{marton1981phenomenography,svensson1997theoretical,marton1997learning,marton2005unit} provide insight into ways to help students discern specific points. The points, whose emphasis is conjectured to be most beneficial, are identified by a qualitative research process. \section{Research Questions} In order to address the students effectively, it can help to know their preparation and their approach to gaining new knowledge. This preparation may include useful ideas, and also may include unhelpful conceptions. Their approach to learning might not yet include the degree of attentiveness to precision and thoroughness that is appropriate for deductive logic. Besides their current knowledge and learning approach, their opinion of the structure of relevancy is interest. We have identified facets of student conceptions surrounding the idea of proof, which led to specific questions. We propose to research these questions: \begin{itemize} \item What do students think a proof is? \item How do students attempt to understand proofs? \item What do students think a proof is for? \item What do students use proof for (if anything), in particular in circumstances other than when assigned? \item Do students exhibit any consequence of inability in proof, such as, avoiding using recursion? \item What kind of structure do students notice, do student make use of, in proof? \item How familiar and/or comfortable are students with different (specific) proof techniques: induction, construction, contradiction? \item What do students think it takes to make an argument valid? \end{itemize} These questions are interesting because with the curriculum we are trying to build capabilities into the students, that will enable them to tackle various problems they may encounter. Moreover, we wish the students to develop the ability to have, in the terminology of Harel and Sowder\cite{harel1998students}, conviction with an internal source, and to be correct in their convictions. As new situations emerge, and as students who have graduated find the occasion to modify an algorithm to a new situation, we want these individuals to be able to know that their modified algorithms are appropriate. It is important that they understand this algorithm-applicability purpose of proof, so that they can judge applicability for themselves, and it is important to know what hindrances they are experiencing, so that we can help the students overcome them. It is important that they recognize that there is structure in proofs, and that they can construct % architect their own proofs, because we cannot foresee every situation our students may experience. Because we are greatly concerned that students should apply their knowledge of proof to algorithm-related contexts they may subsequently encounter, the split between what students perform for assessment, and what students perform for their own purposes is significant to us. Thus it may be helpful to supplement what assessments tell us, about the extent to which the students are absorbing the knowledge about proof we are trying to impart, with information from interviews. Interviews impose a burden of analysis which is usually too extreme for a lecture class. Progression across multiple courses is beyond the scope of a lecture class. Phenomenographic research yields critical factors, which are ideas whose emphasis is thought to be particularly helpful in deepening student understanding. Thus the relevance of this research to the curriculum is that the work will generate suggestions about points to emphasize. \section{Qualitative Research} \begin{quote} Black and Williams 1998 stated When instructors understand what students know and how they think --- and then use that knowledge to make more effective instructional decisions --- significant increases in student learning occur'' \cite{black1998inside}%Black, Paul and Dylan William, Inside the Black box: Raising standards through classroom assessment Granada Learning 1998 \end{quote} How students think, for example, how they approach the study of proof, starting from a preparation in which an appreciation of definitions as foundational for deduction from axioms and premises is not yet present, is a qualitative question. Before the existence of categories of description for this preparation, we cannot have measures. The qualitative approach aims to create categories of description. These can help phrase questions for quantitative studies. Qualitative analysis has types; some of these were created to address specific domains of research. These types include basic qualitative research, phenomenology, ethnography, grounded theory, and narrative analysis, each of which is interpretive.~\cite{merriam2009qualitative} Critical research, while qualitative, goes beyond interpretation, as it intends to reform the object of its attention. Each of the above is a type of qualitative research associated with a qualitative research methodology. One type of research, which differs from those above in that it delimits its scope to the description of ways of experiencing, by a student, the communication from a source of instruction, is phenomenography. While the formerly mentioned types of qualitative research are associated with a qualitative research methodolgy, phenomenography is characterized by an aim, namely to describe people's conceptions.~\cite{svensson1997theoretical}. It is necessary that the descriptions be subject to comparison and to systematization. As for the methods associated with phenomenography, Svensson states~\cite[p. 161--162]{svensson1997theoretical} ""development of methods was included as a main aim of the research and the development of methods was an integrated part of the tradition. However, methods have been dealt with in a problem-solving attitude rather than by giving prescriptions. The methods have been considered to have been derived from the basis of the general aim, the general character of the phenomena of conceptions and also from the basis of the specifics of the phenomena and the situation under investigation. Therefore phenomenographic research represents a research approach in a double sense. It means an emphasis on approaching the research objects in the sense of creating methods adapted to the objects. \ldots The approach to describing conceptions is closely related to the view of the research objects and is not a system of generally defined methods. The most significant characteristics of the approach are the aiming at categories of description, the open explorative form of data collection and the interpretive character of the analysis of data." Svensson~\cite{svensson1997theoretical} reports that phenomenography was extended to include variation theory. Variation is key to the phenomenography/variation theory qualitative research approach. Variation of the communicated information is deemed necessary for discernment by the student of what is being mentioned. Variation among the students, in their approach to receiving information is considered predictive of their success in learning. \section{Phenomenography with Variation Theory} Phenomenography is an empirical research approach.~\cite{svensson1997theoretical} Svensson states ~\cite[p. 169--171]{svensson1997theoretical} that phenomenography's "methodological assumptions also tend to have generality. The most central characteristics are the explorative character of the data collection and the contextual analytic character of the treatment of data. \ldots The analysis, then must not only mean an aggregation of specific data within generally given interpretations, but a delimitation of specific data related to each other as referring to parts of the same phenomena.\ldots The content is, then, not primarily considered in terms of meaning of linguistic units, but from the point of view of expressing a relation to parts of the world. \ldots scientific knowledge about conceptions is based on differentiation, abstraction, reduction and comparison of meaning". Booth~\cite{booth2001learning} states "When I say methodology' I mean that phenomenographic studies are based on certain principles but that the actual methods used vary according to the specific question being addressed; it is not prescriptive. Phenomenography is not an experimental methodology -- phenomenographers do not set up controlled trials and attempt to measure the results of change; but it is relatively naturalistic, researchers engage with the learners themselves, in close proximity (both spatial and conceptual) to the learning situations they find themselves in. Nor is it a quantitative methodology -- the results are descriptive and lie at a collective level, in the sense that individuals are seen as contributing fragments of data that together constitute a whole and collective experience, which can be subjected to research analysis." Marton and S\"alj\"o~\cite{marton1976qualitative} performed an experiment which showed that a students' approaches to learning have been predictive of their learning outcome, reiterated in Marton and Booth.~\cite[p. 22]{marton1997learning} In looking at, and developing categories for, students' ways of experiencing their learning, we may obtain insight into the students' approaches, and can hope to improve their outcomes. Marton\cite[p. 36]{marton1997learning} has defined that one conception (of a thing, $x$) differs from another, for the purposes of phenomenography, by the existence of a distinct manner in which participants were found to voice the way they thought about $x$. The categories of conceptions (also, conceptualizations) include two overriding categories,\cite[p. 35]{marton1997learning} the first being "a learning task, some facts to memorize", and the second having as objective "a way to change oneself, to see things in a new light, to relate to earlier learning, and to relate to a (changed) world." At the next level of drawing distinctions, S{\"a}lj{\"o}~\cite{saljo1979learning} has found five qualitatively distinct conceptualizations, and Marton~\cite{marton1997learning} has found six distinct conceptualizations falling into the two overriding, task and objective. (See Table \ref{WaysLearning}.) \begin{table}[h]\label{WaysLearning} \caption{Distinct Ways of Experiencing Learning, from Marton and Booth~\cite{marton1997learning}.} \begin{enumerate} \item learn as increase knowledge \item learn as increase and be able to reproduce knowledge \item be able to apply new knowledge \item acquiring new meaning, multiple ways of thinking about things, changed perspective, improved understanding, thinking more logically \item modified perspective, multiple perspectives, dynamic perspective \item changing the person \end{enumerate} \end{table} Marton and Booth\cite[p. 78]{marton1997learning} observe that successive understandings increase in completeness as they move toward a theoretical understanding. \subsection{Conceptualizations} Selden and Selden\cite{kaput1998research} include, in their questions regarding teaching and learning mathematics, that instructors aim for their students to `achieve the kind of organizing and integrated use of language'' used in the mathematics community. D\"orfler\cite[p. 122]{dorfler2000means} complements the idea of concept, saying " ' What is the concept $xy$?' should be substituted, or at least complemented, by such questions as 'Which actions can be recorded and/or guided by the concept $xy$?' \ldots Learners must indulge in the discourse \ldots mathematical objects \ldots are discursive objects. This means they come into existence exclusively by and within the discourse, even if this discourse ascribes to them existence an properties of an objective and independent character. " Wittgenstein said \cite[p. 19--20]{wittgenstein1989wittgenstein} "To understand a phrase, we might say, is to understand its use. \ldots Similarly, you only understand an expression when you know how to use it". So, we are inquiring into student conceptualizations, as shown by the students' use of their concepts, and by the students' reflections (in interviews) upon their concepts. % $$While there are many aspects of students' conceptualizations of proofs that are interesting, we concentrate our attention onto proofs that seem to be useful in showing the correctness, progress, termination, safety and resource utilization of algorithms.$$ \subsection{Relevance Structure} %define it, add flesh, define/mention part of phenomenography Relevance structure is a part of phenomenography: Marton and Booth state~\cite[p. 143]{marton1997learning} "Each situation, whether we consider it a learning situation or a situation in which one is applying something learned, has a certain \textit{relevance structure:} the person's experience of what the situation calls for, what it demands. It is a sense of aim, of direction, in relation to which different aspects of the situation appear more or less relevant. It is the way the learner experiences the situation as a whole, \ldots that renders the perspective in its component parts." Knowledge may alter the perspective with which students view new material. For example, students who know they are about to work on projects, in which they are expected to apply new material they are studying, are enabled to receive and organize, mentally, that new material, assisted more or less by its relation to their anticipated use of it. Marton and Booth suggest that relevance structure may be "the driving force of learning"\cite[p. 145]{marton1997learning} and assert that learning's "chief mechanism is variation". Changes in the curiosity of the learner, as may be brought about by the presentation of problems, can change the student's capability of experiencing something, and thereby change the student's way of experiencing it, which is learning. Sudden insight is an example of a change in a person's way of experiencing something. Booth has written on relevance structure in learning computer science.~\cite{booth2001learning} She writes "In pedagogical terms, the course aims to provide the heterogeneous group of new students with a relevance structure \ldots a whole sense of the programme, what it is aimed at, what it demands and where it will lead -- not only by bringing about genuine needs to use the practical tools they are learning, but also by raising questions that relate to theoretical studies to come and to social issues"~\cite[p. 176]{booth2001learning} There is a connection between the ideas relevance structure and motivation, as illustrated in a remark of Booth's "to create a relevance structure, or motivation if preferred, for the coming education by offering the students from the start a whole picture -- however vague and incomplete at the outset -- that encompasses the overall goals of the programme"~\cite[p. 178]{booth2001learning} Thota\cite{thota2014programming} refers to the relevance structure when considering "pedagogic principles \ldots that consider how to tie students' experiences to the course goals (relevance structure)" \ldots The two principles of teaching that are espoused in phenomenographic pedagogy are (a) the relevance structure -- making the learner personally experience the relevance of the learning situation, and (b) variation theory - emphasizing the critical aspects that lead to a change in the learner's understanding of a learning concept." Thota claims that "The learning that occurs is dependent on how the learner personally experiences the relevance of the learning situation".\cite[p. 127]{thota2014programming} Thota, citing Bowden and Marton\cite{bowden2004university} observes "exposure to the critical aspects of professional situations, likely to be encountered in the future, enables students to develop holistic capabilities that link disciplinary knowledge and professional skills." Thota relates that a relevance structure can be built, in part, by relating and contextualizing learning.\cite[p. 128]{thota2014programming} Thota reports\cite[p. 131]{thota2014programming}, of students "they become more engaged in learning when they see the relevance of programming to their chosen major and future career needs." Thota summarizes\cite[p. 131]{thota2014programming} "The building of the structure of relevance can be achieved by: (a) awareness of pedagogical content knowledge as it should be understood by learners; (b) ensuring learners reveal their experience of ways of learning (including the what and how of learning); (c) relating learning to the learner's own personal interests and motivations and contextualizing the set assignments to create authentic situations." Relevance structure plays a role in motivating student learning. Relevance structure can be present in a course at different levels of detail. Present not only at the level of "this test driven development practice might aid your employability", relevance can be shown at the level of an individual algorithm. For example, the purpose of learning to prove whether a problem has optimal substructure can be to determine whether a dynamic programming approach is suitable for a solution. Students who do not know that optimal substructure is important for the use of a dynamic programming approach might not make mental connections between these ideas. It is claimed herein that relevance structure provides another avenue for retrieval of knowledge, lessening the risk of knowledge being inert. Without the relevancy of optimal substructure for dynamic programming, it might not occur to a student to make use of a dynamic programming approach in a situation when that is warranted. \section{Phenomenography / Variation Theory for these Research Questions} Conceptualizations, as we have seen above, are important for our research questions, and are a central object of attention for phenomenography. Phenomenography and variation theory (henceforth "phenomenography") address mental concepts without reference to any sensory modality through which they may have been acquired.~\cite[p. 160]{marton1997learning} As a deductive, logical argument, a proof is a mental concept that can exist without reference to any sensory modality. Phenomenography concerns itself with students' approaches to learning. This allows us to hope to effect a change in approach, and thereby effect an improvement in students' outcomes. \section{Overview} Chapter 2 discusses the phenomenographic research perspective, and the epistemological framework. Chapter 3 discusses the methodology applied in the study, including sections on sample selection, data collection, and analysis. Chapter 4 describes the results of the analysis. Chapter 5 provides interpretation and discussion. Chapter 6 discusses validation and reliability. Chapter 7 discusses some related work. Chapter 8 concludes the description of completed work. Chapter 9 describes some possible future work.