by David Ginat,
The first part of the current column involves a continuation (that we just recently developed) of the challenge
posed in the previous issue of the column.
The second part of the column involves the
analysis of repeated applications of a given
operator. The analysis embeds the utilization
of the notion of a metric, for realizing algorithmic execution termination. Termination
is shown without identifying a specific value
that will be reached upon the execution end.
The analysis also examines a lower bound on
the number of operator applications that any
algorithmic solution will require, and raises
some questions for the interested reader.
ROW/COLUMN TRANSFORMATIONS II
Given an N×N matrix of black and white
squares, we may repeatedly apply an
operator that switches the color (black to
white and white to black) of each square
in a selected row or a selected column.
The goal is to determine whether a given
matrix may be obtained from an initially
all-white matrix in a series of applications
of the operator.
Example. The left 3× 3 matrix below may
be obtained by three applications of the operator (e.g., on the first row, the third row, and
the middle column). No series of the operator
applications may yield the right 3× 3 matrix.
Given an N×N matrix of positive and negative integers, we may repeatedly apply
an operator that changes the signs of all
the integers in a selected row or a selected
column. The goal is that the sum of the integers in each row and in each column will
be non-negative. We ask two questions.
1. Can we obtain the desired goal for
every given matrix of positive and negative integers?
2. What is the lower bound on the number of operator applications necessary
for reaching the desired goal (for those
matrices for which the goal may be
Example. The goal may be obtained for
the matrix below in two operator applications. We may first apply the operator
on the 3-rd (bottom) row, and then on
the 2-nd (middle) column. Can we obtain
the goal for every given 3× 3 matrix of
integers? And how many operator applications may suffice for obtaining the goal for
3× 3 matrices?
An operator application on a specific row
may improve the row’s sum, but worsen the
sums of some of the columns. Then, attempts
to “correct” the columns may result in worsening the just-improved row. Is there a way to
continuously improve the row/column sums?
One may examine a variety of examples.
way to fit into existing academic structures
and programs. And as suggested by a
reviewer (thank you), statistics will likely
play a larger role as software engineers
develop for big data projects.
Perhaps we should use new terms and/
or structures, though I have none here
to suggest (yet). But I feel strongly that
software engineering education is enhanced by the right mathematics topics at
the right time. Because, like art and brain
surgery, software engineering is easy; software engineering correctly is very difficult,
yet very important as our society increases
its reliance on algorithms and applications.
Mathematical reasoning is also a challenge,
but it if it results in better software, then it
is worth the extra effort.
The author would like to acknowledge
an email discussion with Franz Lichtenberger that helped in the development of
this column, as well as helpful comments
1. Bourque, P. and Fairley, R. E. Guide to the software
engineering body of knowledge (SWEBOK (R)):
Version 3.0. IEEE Computer Society Press, 2014.
2. Capretz, L. F. Psychological types of Brazilian
software engineering students. Journal of
Psychological Type, 68, 5 (2008), 37-42.
3. Henderson, P. B. Mathematical reasoning in software
engineering education. Communications of the ACM,
46, 9 (2003), 45-50.
4. Joint Task Force on Computing Curricula, Association
for Computing Machinery (ACM) and IEEE Computer
Society. 2013. Computer Science Curricula 2013:
Curriculum Guidelines for Undergraduate Degree
Programs in Computer Science. ACM, New York, NY,
5. Joint Task Force on Computing Curricula, Association
for Computing Machinery (ACM) and IEEE Computer
Society. Curriculum Guidelines for Undergraduate
Degree Programs in Software Engineering. ACM,
New York, NY, 2015.
6. Laird, L. Strengthening the ‘engineering’ in software
engineering education: A software engineering
bachelor of engineering program for the 21st century.
In Software Engineering Education and Training
(CSEET), 2016 IEEE 29th International Conference,
April 2016, 128-131.
7. Lichtenberger, F. Mathematics education for
software engineers: It should be radically different! In
Proceedings ICTM2, University of Crete, Greece, 1-6
John P. Dougherty
Department of Computer Science
370 Lancaster Avenue
Haverford, Pennsylvania 19041 USA
DOI: 10.1145/3123734 Copyright held by author.
+ 3 + 2 − 1
+ 4 − 5 + 1
− 8 + 1 − 1