On the ’divide & conquer’ metaphor — the ‘quinta essentia’ of programming


By Prof. José Nuno Oliveira, HASLab/INESC TEC & University of Minho.

Abstract. "Divide & conquer" (D&C) is a well-known programming principle based on recursively breaking down a complex problem into sub-problems of the same kind. D&C is also a basis for parallel programming, Google map-reduce being one of its best known instances. But how does the metaphor with “divide et impera” in politics and sociology get into a programmer's way?
This talk introduces "formal metaphors" and their algebra to reason about a wide range of problem specifications that can be implemented in a D&C fashion. We show that this falls into the more general programming strategy known as "change of virtual data structure", which can be achieved in two basic ways. These will be illustrated with the quicksort and mergesort algorithms, showing what they have in common and what makes them different from the very start of development.

Keywords. Software Engineering; Formal methods; algebra of programming.

About the speaker. José Nuno Oliveira is a full professor at the Informatics Department of the university of Minho and a senior research member at HASLabINESC TEC and Univ. of Minho. He graduated in electrical engineering from the Univ. of Porto and received the MSc and PhD degrees in computer science from the Univ. of Manchester, UK. Prof. Oliveira's main research interests are formal methods, algebra of programming, and functional programming. Prof. Oliveira served on the PC of almost 50 conferences and workshops in his field of study and co-chaired some of them. He is also a member of IFIP WG2.1 and of the FME association.


Address:  University of Minho, Gualtar campus, Braga, Portugal.

Building. Departamento de Informatica, Building 07.

Coffee session: at 1:30PM-2PM, Sala de Estar, 4th floor.

Talks session: at 2PM-3PM, Auditorium A2, 1st floor.