Some people were complaining about the domain joaoferreira.org, because it was a bit long and they never got the number of r’s in Ferreira right. From today, they can’t complain anymore!
The new and official URL of this website is now shorter and r’s-free: joaoff.com .
If you don’t like it and prefer the old one, please let me know!
The other day I went to my pigeon-hole to collect my snail mail, and I had a letter from Donald E. Knuth, Professor Emeritus of the Art of Computer Programming!
Inside, there was a check for a correction I sent him some months ago. In fact, it was not really a correction; it was more like a comment. And it was so obvious (he even said that) that he just sent $\$$0.32, instead of the usual $\$$2.56. But hey, who cares? I’ve got Knuth’s autograph now
Perhaps I should set as one of my goals to find a proper error, so that I can receive a $\$$2.56 check By the way, the errata of the Concrete Mathematics is available online and this particular omission is documented as follows:
page 338, line 2 from the bottom
change “for $z$” to “for $z$ and multiplying by $a$”
That’s true: the last post was exactly 5 months ago, but I’m still alive! A lot of new stuff happened during these 5 months. Two days after writing the last post, I went with my group (Foundations of Programming) to a very nice hotel in Ruddington, where, during two days, each member had to present something about his/her work. I’ve talked about a result I’ve derived related with distributivity through the Greatest Common Divisor. My slides are available at the event’s webpage and I will put online a note with all the details.
A few days later Alexandra got ill with some strange pain in the abdominal area. The following weeks were really hard, since she had to go to the hospital emergency services. So that you have an idea of how strange the whole thing was, the doctors still don’t know what the problem is! Now, she has occasional pain, but it seems to be much more controlled.
Anyway, more or less at the same time I started to read a very nice article (a Functional Pearl) written by Jeremy Gibbons, Richard Bird and David Lester named “Enumerating the Rationals“. The paper presents some algorithms encoded in Haskell to enumerate the positive rational numbers. In particular, it presents algorithms to construct the famous Stern-Brocot and Calkin-Wilf trees. It also presents a very efficient algorithm to enumerate the rationals in Calkin-Wilf order just by using as current state the previous rational (i.e., two integer numbers). However, the authors claim that “it is not at all obvious” how to create a similar efficient algorithm for enumerating the rationals in Stern-Brocot order. Well, after reading it, Roland (my supervisor) and me found a way of doing it. The key idea is that rational numbers are pairs of coprime numbers (numbers which greatest common divisor is 1) and thus, we can use Euclid’s algorithm as a basis for enumerating these pairs. By using the Extended Euclid’s algorithm written using matrix multiplication, we were able to derive both Calkin-Wilf and Stern-Brocot enumerations from the same algorithm. We wrote a paper named “Recounting the Rationals: Twice!” that was submitted to the journal American Mathematical Monthly.
First of all, welcome to my new blog. Being this my first post, I will present myself, give you some background on what I am doing and explain what are my intentions about this blog. My name is João Fernando Ferreira and I am a research student at the Foundations of Programming research group at the University of Nottingham (visit the About page to find out more).
My research is on algorithmic problem solving and its main goal is to develop calculational problem-solving techniques resulting in educational material supporting the use of a calculational approach to algorithmic problem solving. The focus of the project will be on the dynamics of problem solving – the processes of mathematical modelling and effective calculation in the formulation of concise and precise algorithmic methods.
As any other researcher, I spend most of my time reading and writing. That is one of the reasons I have created this blog: to organise my written notes. Using a blog system brings me some advantages like:
- I can tag my notes and use the system search capabilities to find them;
- I can access and change them from any place in the world, as long as I have Internet access;
- I can add new content from any place in the world, as well;
- I can share my notes and get feedback from my colleagues, supervisors, friends or anyone who is just interested in the same topics.
Other important reason to share my notes and thoughts is that I think they may be of interest for programmers. Since this is my first post, and (probably) most of you don’t really understand what I am doing, I will start by presenting some historical facts (mixed with personal opinions) and motivations. It is my hope that these facts will help you understand the relation and importance of mathematical methodology to programming. Please note that to read the entire post, you may need to click the “Read more” link.
In the 1960s, programmers started recognising that there were serious problems in the programming field and that it was necessary to prove the correctness of programs. At the time, software engineering was facing a software crisis and programming was not very well understood. Many software projects ran over budget and schedule and some of them even caused property damage and loss of life (see the RISKS-FORUM Digest for some examples).
To solve these problems, computer scientists focused on programming methodology and on ways to build programs in a systematic way. A common consensus was that programs should be proved correct, and in the late 1960s, some important articles had an important impact on the field. In 1968, Edsger W. Dijkstra published an article on the harmfulness of the Go To statement, where he claims that its use makes it impossible to determine the progress of a program. Also, one year later, Tony Hoare published a seminal article where he introduces the Hoare triples and an axiomatic approach to language definition.