Tag: Books

Algorithms on Strings

I was first exposed to string matching by given to read “Algorithms for Finding Patterns in Strings” back in 1990, when I naively asked Prof. Stathis Zachos something like “How does grep work?”.

Time passed, I became a system administrator and most of my exposure to string matching was through scripts and sysadmin stuff automation. Automata are nice, but Perl and shell brought food to the table.

These memories surfaced because I got to read “Algorithms on Strings” in January thanks to Bill Gasarch. Complete, self-contained and with plain and well understood English, the book covers the subject fulfilling simultaneously the needs of those who want to just read the theory, those who want to see the proofs and those who just want to write code.

The pseudocode in the book is understood by anyone who has ever written a single program in C or Java. It either introduces new functions or makes use of others previously defined. This may make it a little difficult at first for people who need to write something described in, for example, chapter six and may find themselves reading from chapter one up to six. In this process the book manages to educate even the programmer who does not care about theory not only about how to do certain functions, but why they are done the way they are. As a plus, references to appropriate Unix shell tools (e.g. diff) are given when appropriate.

A really impressive book, definitely worth your time! A book that you can use both to learn about stuff and as a reference.

Super Crunchers

I am slightly disappointed. Two problems with the book (three if you count the translation which was forcing me to re-translate in English and back to Greek):

  1. The book feels like an extended version of an already long paper. This becomes tiring at times.
  2. The book explains why traditional experts in certain (all?) fields will be replaced by statistical methods. What the book does not say, is that a new breed of experts will rise: The ones that will devise the statistical models. The untrained eye may easily believe that all it takes is a lot of data and a few keystrokes.

I wrote the above lines while reading the book and before the final chapter. Chapter 8 makes up for the above, but somehow I expected more. Maybe I do not belong to the target audience.

PS1: While reading the book, I think I discovered how the character of Ian Frost (from Turing) was named.

PS2: Going through the author’s page I came across stickK which seems to be a perfect tool to fight procrastination.

Open Systems Security – an Architectural Framework

“In the old days” when security information was scarce and many of us began shaping our security mentality (be it white, gray or black) by reading “Improving the Security of Your Site by Breaking Into it” and the Computer Security FAQ and running tools like iss and Crack. I think it was there that I first read about Arto Karila’s PhD thesis. Even though it is an OSI based document, it helped understand basic concepts. However there were two problems with the document:

  1. It was hard to find, and
  2. It was in a weird PostScript format that even modern versions of ghostscript refuse to display.

With the help of a friend I managed to transform it to PDF and upload it to Scribd: Open Systems Security – an Architectural Framework

Of historical value mostly.

Update 2013/04/13: Now available at https://github.com/a-yiorgos/karila

The development of social network analysis

As promised, I finished reading “The development of social network analysis“. The book, written by Linton C. Freeman follows the development of the field from pre-Moreno times and the introduction of structural thought into social studies up to the late 90s. According to the book cover it is based on the Keynote Lecture that Freeman gave in April 2000 at the twentieth annual meeting of the INSNA.

The study of social structure has come of age

This is the last sentence of the book. Before reaching it, Freeman takes us on a journey that roughly begins with the works of Auguste Comte who apparently planted the first seeds of structural thought. Since then the field of structural thought has been restarted a number of times, and for a variety of reasons, among them being megalomania, shift of interest, interdepartmental politics and job security, main scene politics (like the Jenner committee that essentially ended a whole group).

A whole chapter is devoted to the life of Jacob Levy Moreno, who many think of as the father of the field, although it is later shown that there were earlier studies with similar aims and results and that the systematic approach and development of his ideas is most probably owed to the work of Helen Jennings and Paul Lazarsfeld.

All the pioneers and heroes of SNA parade through the book, the flow of names and their interrelations is so vast that half way through the book I regretted not taking notes of the names and their relations in order to produce something like the TCS genealogy coupled with some visualization. Luckily, in page 131 such a pruned graph is presented by the author.

Professor Freeman characterizes social network analysis as an approach that involves four defining properties:

  1. It involves the intuition that links among social actors are important.
  2. It is based on the collection and analysis of data that record social relations that link actors.
  3. It draws heavily on graphic imagery to reveal and display the patterning of those links.
  4. It develops mathematical and computational models to describe and explain those patterns.

All the efforts of structural thought (almost all of them lacking combination of all four characteristics) are presented, most of them being in USA with a few in Europe, up until the great restart of the discipline by Harrison White and his team at Harvard. The central role that Barry Wellman played in unifying all the approaches to the structural thought, through organizing meetings with key persons, forming the INSNA and the Connections newsletter is covered. Plus the EIES system (of interest to those who seek fragments of Internet history) is also covered at some extent, showing the role that technology can play in forming both a discipline and (human) networks.

Continue reading “The development of social network analysis” →

Studies in the Economics of Transportation

While reading Nagurney‘s “Comment on Catching the Network Science Bug“, I was fascinated that “Studies in the Economics of Transportation”, which was written in 1956 was mentioned. After all, Network Science is supposed to be “newer” than that.

For anyone interested the book is available from the RAND classics section. A more readable PDF is located here.

I will not claim that I have given the book anything more than a brief look. However I read “A Retrospective on Beckmann, McGuire and Winsten’s Studies in the Economics of Transportation“.

This was not the first time that I saw this book being cited: It is also cited in Preface to “On a Paradox of Traffic Planning” (a preface to the English translation of Braess‘s “On a Paradox of Traffic Planning“ which introduces Braess’s Paradox).

Sometimes the titles stick to your head, I guess.

Chaitin’s books online

A few weeks ago I heard that Chaitin tries to put everything he has ever published online, and most of the stuff via arXiv. Over the weekend I gave it sometime and found some of his books:

I own “Meta Math!“. I bought it by chance. While in the bookstore, I opened it and stumbled upon LISP code. This is a really nice book. It is a personal log of Chaitin‘s career, an introduction to Kolmogorov complexity0 (which was independently invented by Chaitin too), algorithmic information theory, thinking about randomness (and in a way first presented to me years ago by a long time friend), LISP1, useful comments on NKS2, Polya‘s “How to Solve It!” and an introduction to the thought of Leibniz3.

Of course the book has irritating parts: Having invented a field independently of Kolmogorov, somehow puts you in the shadow of the man and Chaitin constantly tries to get out of the shadow and stand not on the shoulders of Turing and Goedel but next to them (when in fact such effort is not needed).

I loved the book4. It is the kind of book that reminds you why you loved Mathematics. Even Chaitin’s personal effort to stress the importance of his work (that annoys many) contributes to this. For he unquestionably loves Mathematics.

(Must make time and read “The Limits of Mathematics”; Time there is not…)


[0] – More about it at “An introduction to Kolmogorov complexity“.

[1] – Link to the Lisp interpreter that Chaitin has developed for his needs.

[2] – See also this presentation on NKS by S. Wolfram.

[3] – An essay on Leibniz by Chaitin.

[4] – I also loved “Title: Algorithmic information theory: Some recollections“.

Plato’s Republic

A friend suggested that I could use The Book Depository as an Amazon alternative, which was a very helpful tip especially for books over €50. As it happens to many who buy books from online bookstores, sometimes what you get is not what you ordered. In my case I had ordered “The Travelling Salesman Problem” and got “Plato’s Republic“. After some friction with their support service (Amazon is way better in this kind of issues) the order was completed and The Book Depository told me that I could keep “Plato’s Republic” too.

Now since it is highly unlikely that I will ever find time to read this version, I will gladly send it to anyone interested. If nobody shows any interest, I will donate it to a library.