2017/2018 Edition

Are Three Squares Impossible?

Lecturer: Prof. William F. Smyth (McMaster University, Canada).

About the lecturer | Course Summary | Slides: 1 2 3 | Assignment

About the lecturer:

William F. Smyth is an Emeritus Professor, Algorithms Research Group, Department of Computing & Software (C&S), McMaster University, a Visiting Professor, Algorithm Design Group, Department of Informatics, King's College London and an Associate Member, Department of Mathematics & Statistics, McMaster University.

Prof. Smyth received his Bachelor's degree in Pure Mathematics in 1957 at the University of Toronto and graduated from the University of Ottawa (M.Sc in Applied Mathematics). He received his Ph.D. in Computing Science at the Curtin University of Technology. Just after receiving his Bachelor's degree, he spent about 10 years in the "real world", mostly writing software for business, scientific and engineering applications of computers. From mid-1967 till mid-1982 he worked with various United Nations agencies in various countries for periods ranging from a few months to a few years: Kenya, Italy, Hungary, Roumania, Tanzania, India, Israel, Singapore, Sri Lanka. In 1982, he joined McMaster University as a Visiting Associate Professor and was awarded a tenure in 1986 and promotion to Professor in 1992. At the end of 1999 Prof. Smyth retired in order to devote all his time to research and to the supervision of graduate students. He has held an NSERC research grant since 1986 and has also been a participant in an MRC/NSERC collaborative grant entitled Computational Issues in Alignment & Sequencing as well as in an NSERC equipment grant for a Graduate Laboratory in Computational Biology. Also, for three years he was a co-holder of a NATO Travel Grant for String Algorithms. In 2008-2009 he was chief investigator of an NSERC RTI (Equipment) Grant for the Algorithms Research Group Design & Development Laboratory and one of three investigators for an Australian Research Council Grant, Indexes Allowing Fast & Efficient Text Search.

Research interests of Prof. Smyth include combinatorial algorithms, especially algorithms on strings, graph theory and its applications, various social/cultural issues.

In May 2003 the book, Computing Patterns in Strings, by Prof. Smyth was published by Pearson-Addison-Wesley (U.K.).

Course summary: These talks describe work done over the last 30 years or so both to understand and to compute repetitions in strings - especially since 1999. We will discover that, although much has been learned, much combinatorial insight gained, there remains much more that is unknown about the occurrence of repetitions in strings and the restrictions they are subject to. I present combinatorial results discovered only recently, and I suggest that possibly extensions of these results can be used to compute repetitions in an entirely new way. I hope that members of the audience will be motivated to work on some of the many open problems that remain, thus to extend combinatorial knowledge even further.

We begin with an introduction to basic notation, terminology and data structures related to strings and associated algorithms. We review the basic algorithms for computing repetitions and runs, as well as the various approaches to determining bounds on the number of runs in a string. We argue that these methods, though ingenious, do not provide enough insight into the possible behaviours of runs in strings and the relationships among them. We propose a new way of thinking about runs (squares) that raises questions for which currently there are only partial answers.

In the second talk, we describe a major extension of the Three Squares Lemma, the complications that ensue, and the methods developed to handle them. Specifically, we wonder what happens when two squares u^2 and v^2 occur at the same location, u < v, while a third square w^2 begins a distance k to the right. In this talk we explore the consequences of supposing that 3u/2 < v < 2u, 0 <= k < v-u, and v-u < w < v, w \neq u. We uncover evidence to support the strange notion that ...

Three Squares Are Impossible!

Finally, We describe the "easy case" when u^2 and v^2 occur at the same location with u < v <= 3u/2 - even two squares can scarcely occur! Then we show how all this work has barely scratched the surface - we take a timorous look ahead to the General Case and its consequences that await us sometime in the future!

Slides: 1 2 3

Assignment (due 31 May, 2012)