Author: Sanjay Goel
This article is an excerpt from – Sanjay Goel (2010), Design of Interventions for Instructional Reform in Software Development Education for Competency Enhancement, Section 4.2, pp 91-97, http://eric.ed.gov/?id=ED516414.
Traditionally, software was regarded as belonging to the domain of ‘applied mathematics.’ Many experts view software development as a special type of mathematical problem solving activity which requires the developers to use various mathematical thinking processes like step-by-step approach to decomposition, abstraction, pattern recognition, spatial and temporal modelling, deduction and induction, and synthesis.
In his much debated talk called ‘On the cruelty of really teaching computing science,’ in 1989, Dijkastra emphasized on formalism . He further identified the following two radical novelties of programming: (i) conceptual hierarchies deeper than a single mind ever needed to face before, and (ii) in a discrete world small changes do not imply small effect. In 1991, the joint ACM/IEEE-CS curriculum task force  identified twelve unifying and pervasive concepts of computing – binding, complexity of large programs, conceptual and formal models, consistency and completeness, efficiency, evolution, levels of abstraction, ordering in space, ordering in time, reuse, security, and trade-off and consequences.
In a 2009 survey on required competencies for software developers, twenty software professionals assigned abstraction thinking and algorithmic thinking an average rating of 2.9 and 2.8 respectively on a scale of 0-4. An overwhelming majority of these respondents (70%) recommended these to be critical or very important competencies with respect to the requirements of software developers’ multi-faceted professional activities.
Algorithmic problem solving activities
Expert programmers think and develop algorithms rather than think in specific language syntax . In 1979, Kowalski postulated that an algorithm consists of logical and control components . The logic components define the knowledge that is needed to solve the problem. The control component determines how to use and sequence such knowledge to do so. Muller and Haberman  have enumerated algorithmic problem solving activities.
Problem comprehension is the first activity that involves reformulation of the problem statement in terms of data items, initial state, goal, assumptions, constraints, and scale. This is the most critical thinking stage for designing algorithms. For five consecutive years (2002-07), in data structure and algorithm courses, I emphasized on this aspect by engaging students to generate examples of increasing complexity in terms of scale, diversity, assumptions, goals, initial state, constraints, tolerance, and exceptions. The students were required to first develop the algorithms for the simplest possible case of each problem. With each additional case of increasing complexity of the problem, they were required to identify the limitations of the existing solution, and then modify the same to meet more complex demands.
The second activity of decomposition is the identification, naming, and listing of subtasks and data items with attributes, objectives, and roles. Analogical reasoning, generalization and abstraction are used for identifying similarities between problems, and extracting prototypes of problems from analogical problems in different contexts. This helps in identifying a problem’s prototype for its categorization.
This is followed by the problem’s structure identification, i.e., composition, identifying the relation between subtasks, data items, state transitions, data flow, and distinguishing between logic and control. Schematizing a problem’s structure using diagrams helps a great deal in this process. Flow chart has great limitations in terms of its inability to show data or states.
A new diagramming technique called ‘concept mapping’  was developed and used in various classes as mentioned above. The students who were exposed to concept mapping in their introductory data structures course continued to use it, or a self-modified notation, even after graduating.
Finally, algorithm thinking requires evaluation and appreciation of efficiency and elegancy, reflecting on problem-solving processes and strategies to draw conclusions for the future, and verbalization of ideas and differentiating between an idea and its implementation.
Lethbridge’s Study on Most Important and Influential Topics
Lethbridge et al [6-8] surveyed approximately 200 practicing software engineers and managers. Their report shows that five out of the thirteen subject categories did not contribute even a single topic to the list of twenty-five most important and influential topics, while these categories were felt by the respondents to be over emphasized in the curriculum. These subject categories are theoretical computer science, mathematical topics in computer science, other hardware topics, general mathematics, and basic science.
Computational Thinking: Beyond Traditional College-level Mathematics and Algorithmic Thinking
In 2009, I initiated an online discussion among the online community of software professionals on LinkedIn. Nearly 30% respondents felt that proficiency in mathematics indicates a high capability to handle abstractions, the ability to go into detail, ability to plan and approach a problem in a methodical/structured fashion. On the contrary, the other majority suggested that this relationship between mathematics and software has been exaggerated, and gave reasons like mathematics education does not necessarily enhance lateral thinking for problem solving. However, many respondents grounded software development competency into puzzle-solving ability.
Wing  viewed computational thinking as an approach to problem solving, system designing, and also understanding human behavior, by drawing on the concepts fundamental to computer science. Isbell et al  shift the emphasis from algorithm to interaction and suggest that computing problem solving is not so much about finding answers but more about creating services, interfaces, and behaviors. Fant  argues that, unlike mathematics, computer science is more concerned with issues related to creation and actualization of process expressions.
In my experience, students without good background in school level mathematics, especially in topics like algebra, geometry, trigonometry, functions, etc., have been found to perform poorly in software development oriented courses. However, performance in college level mathematics courses like higher calculus, differential equations, and linear algebra, etc., seem to have no correlation with the performance in software development skills of college level engineering students. There are many exceptional programmers whose performance in college level mathematics has been poor, and there are many poor programmers with very good performance in college level mathematics.
According to Wing , computational thinking is about producing executable descriptions, i.e. automable or automatically manipulatable models. She strongly recommended that computing faculty teach courses on computational thinking which includes thinking in terms of: constraints, abstraction, decomposition, heuristics, algorithms, recursion, concurrency, synchronization, efficiency, elegance, tradeoffs between processing and storage, caching, interpreting code as data and data as code, and prevention, detection and recovery from worst-case scenarios. Two relevant intuitions for computing are the concepts of having something and being in a state . In 1975, the chief designer of many programming languages, e.g., Pascal and Modula, Nicklaus Wirth, wrote a book titled, ‘Algorithms + Data Structures = Programs.’
There is a need to review the college level mathematics content from this perspective. Whenever mathematics courses succeed in engaging students in representing real-life problems into mathematical or computable problems, and then solving those problems using mathematical tools, they provide direct help in enhancing the analytical thinking skills required for software development. Courses on puzzle-solving and mathematical modeling have a higher potential to make such direct contribution. In 1999, SEI- CMU published a report to define the discipline of software Engineering . The mathematics requirements included ‘mathematical logic and proof systems,’ ‘discrete mathematical structures,’ ‘formal systems,’ ‘combinatorics,’ and ‘probability and statistics.’
Isbell et al  also take a position that though computing overlaps with various disciplines like mathematics, science, engineering, arts, humanities, and social sciences, it is neither of these and is a discipline in itself that requires a distinguished kind of mindset which they term computationalist thinking. They posit that the equivalence of model, language and machine is the key idea of computing. According to them, computing marries the representations of some dynamic domain and dynamic machine to provide theoretic, empirical, or practical understanding of domain or machine.
Computational thinking requires thinking in terms of data attributes, data flow, relationships, and state transitions. It also involves thinking about system-environment boundary, interface, system metrics, scale, sequence flows, transactions, composition, exception handling, testability, evolution, and documentation. Today, user interaction has become equally important. Isbell et al  posit that computationalist thinking focuses on model, abstraction, interpretation, scales and limits, simulation, and automation. They insist that computationalists must understand how to create, analyze, and critique models.
Abstraction as an Integral Part of Computational Thinking
Hazzan and Tomakyo  highlight the importance of mental habit of abstraction and the ability to make transitions between levels of abstraction as an important skill for software developers. Computational thinking involves stepwise refinement with different notations at different levels. It involves thinking about reality at different levels of abstractions and to model the same through executable formalisms. The fundamental feature of computational thinking is abstraction of a situation/system/problem in such a way that the selected details in the model make it executable by a machine. The choice of the selected executable abstractions of the problem is driven by its purpose . The purpose may be: (i) automation, or (ii) simulation either to get deeper insights or to create virtual worlds.
Abstraction is informally described as the process of mapping a representation of a problem onto a new representation. Philosophers like Aristotle, Hume, and Locke have taken a reductive perspective of the abstraction process and see it in terms of the filtering-away of irrelevant components and specifics, with the aim of extracting content or meaning. Constructivist perspective of abstraction emphasizes selection and combination of relevant constituents. Each new abstraction identifies a new phenomenon and becomes a potential constituent for further abstraction . Abstraction concepts include association, aggregation, composition, classification, or generalization.
The computing worlds consist of things (objects), events, and actions (activities, processes, and operations). Kramer viewed computational abstraction as generalization to identify the common core or essence, manipulating symbolic and numerical formalisms, and also moving from an informal and complicated real world to a simplified abstract model . Wing  sees it first as a process of deciding what details we need to highlight/ignore, and then choosing an appropriate representation to model the relevant aspects of a problem. It takes several iterations to fine tune computational abstractions. The maximum challenge is to gather a ‘complete’ overview of the given problem.
Computational abstractions are to be discovered by balancing creation against reuse, with a strong preference for reuse of things that are already tried and tested.
Abstraction of Real World
Nicholson et al  caution that since software developers solve problems that exist in the real world, their solutions must ultimately succeed in the real world, not just on the abstract level used to define the solution. They also suggest critical evaluation of computational abstractions because abstractions may become too generic/specific. The details removed in an abstraction may reemerge in a way that requires that they be considered. Any representation can have consequences for how the subject of the abstraction is understood. The existing computational abstractions may cross into new contexts by accident or default, and the same subject may recur at multiple layers of abstractions with different aspects and context. They insist on identification of the context of use and then defining the computational abstraction accordingly. For identification of the context of use, their recommendation is to understand the abstractions that are already used within the relevant context, and the socio-political context thereof. Software developers also need to identify the reusable ideas/components in the application and technology domain. Finally, regarding simultaneously working with multiple layers of abstractions, it is important to understand how the different layers of abstraction relate to each other, and always clearly indicate the layers being currently dealt with.
A Key Principal for Designing Hierarchy of Abstractions
In his classic paper, Miller had suggested that humans have an upper limit of the number of items that they can simultaneously hold in their temporary memory for further cognitive processing. This is in the range of seven plus/minus two . Software developers should keep this in mind as they develop their hierarchy of abstractions.
 E.W. Dijkastra, David L. Parnas, W.L. Sherlis, M.H. van Emden, Jacques Cohen, R.W. Hamming, Richard M. Karp, and Terry Winnograd, Peter J. Denning (ed.), A Debate On Teaching Computing Science, Communications of the ACM, pp 1397-1414, December 1989.
 A. Joe Turner, A Summary of the ACM/IEEE-CS Joint Curriculum task Force Report: Computing Curricula 1991, Communication of the ACM, pp 69-84, July 1991.
 Winslow, Programming Pedagogy — A Psychological Overview SIGCSE BULLETIN Vol. 28 No. 3, ACM, USA, pp 17-25, Sept. 1996.
 Robert Kowalski, Algorithm = Logic + Control, Communications of the ACM, Volume 22, Issue 7, ACM, pp 424 – 436, July 1979.
 Muller and Haberman, A course dedicated to developing Algorithmic Problem Solving Skills – Design and Experiment, 21st Annual Psychology of Programming Interest Group Workshop (PPIG 2009), University of Limerick, Ireleand, June 24-26, 2009, http://www.ppig.org/papers/21st-muller.pdf.
 Timothy C. Lethbridge, The relevance of software education: A survey and some recommendations, Annals of Software Engineering, Springer Netherlands, pp 91-110, March, 1998.
 Timothy C. Lethbridge, A survey of the relevance of computer science and software engineering education, . Proceedings of 11th Conference on Software Engineering Education, IEEE, pp 56-66, 1998.
 Timothy C. Lethbridge, What knowledge is important to a software professional?, Computer, IEEE, pp 44-50, 2000.
 J.M. Wing, Computational Thinking, Communications of the ACM, pp 33-35, March 2006.
 Charles L. Isbell, Lynn Andrea Stein, Robb Cutler, Jeffrey Forbes, Linda Fraser, John Impagliazzo, Viera Proulx, Steve Russ, Richard Thomas, and Yan Xu, (Re)Defining Computing Curricula by (Re)Defining Computing, Inroad SIGCSE Bulletin, Vol. 41, Number 4, pp 195-207, December 2009.
 Karl M. Fant, Computer Science Reconsidered: The invocation models of process expression, John Wiley & Sons, USA, pp 1-10, 2007.
 Michael Weigend, To Have or to Be? Possessing Data Versus Being in a State – Two Different Intuitive Concepts Used in Informatics, R.T. Mittermeir and M.M. Sysło (Eds.), Informatics Education – Supporting Computational Thinking, Third International Conference on Informatics in Secondary Schools – Evolution and Perspectives, ISSEP 2008 Torun Poland, Proceedings, Lecture Notes in Computer Science, Springer-Verlag Berlin Heidelberg, pp. 151–160, July 1-4, 2008.
 Hazzan, O. and Tomayko, J., Reflection and abstraction processes in the learning of the human aspects of Software Engineering, IEEE Computer, pp. 39-45, June 2005.
 Corrado Priami, Computational Thinking in Biology, In C. Priami (Ed.), Transactions on Computational System Biology VIII, Lecture Notes in Computer Science, Springer-Verlag Berlin Heidelberg, pp. 63–76, 2007.
 Chris Thornton, Quantitative Abstraction Theory, Artifical Intelligence and Simulation of Behavior Journal 1(3), SSAISB, 2003, retrieved from http://www.cogs.susx.ac.uk/users/christ/papers/q-abstraction-theory.pdf, last accessed Dec. 18, 2009.
 J. Kramer, Is Abstract the key to computing?, Communications of the ACM, April 2007, pp 37- 42.
 Keiron Nicholson, Judith Good, Katy Howland, Concrete Thoughts on Abstraction, 21st Annual Psychology of Programming Interest Group Workshop (PPIG 2009), University of Limerick, Ireland, June 24-26, 2009, http://www.ppig.org/papers/21st-nicholson.pdf.
 Miller, G. A., “The magical number seven, plus or minus two: Some limits on our capacity for processing information”. Psychological Review 63 (2), pp 81-97, 1956 retrieved from http://psychclassics.yorku.ca/Miller/.
 Thomas B. Hilburn, Iraj Hirmanpour, Soheil Khajenoori, Richard Turner, Abir Qasem, A Software Engineering Body of Knowledge Version 1.0, SEI, CMU, April 1999.