Sec. 1.2.1: Mathematical Induction

This section presents the induction principle for proofs, with good examples. I actually read this section carefully. There’s even a quick discussion about using induction for proving correctness of programs, using some kind of Floyd-Hoare logic. Exercises are quite good, as usual. This being a book about algorithms, there’s no mention to the recursion theorem in the context of set theory, which is commonly studied along with induction principles in courses or books about sets. However, the last exercise here is about generalizing induction for well-ordered sets. Nothing about corecursion, though.

Sec. 1.2: Mathematical Preliminaries

This is the big section with the mathematical background required for algorithm analysis. The first time I started reading vol. 1, I spent a long time in this section, eventually losing interest. Not that I don’t like math, quite the contrary; but I started reading the book expecting algorithms, and it took too damn long to get to them. So here is what Knuth says in the beginning of this section:

The reader may choose to read the following subsections carefully, with implicit faith in the author’s assertion that the topics treated here are indeed very relevant; but it is probably preferable, for motivation, to skim over this section lightly at first, and (after seeing numerous applications of the techniques in future chapters) return to it later for more intensive study. If too much time is spent studying this material when first reading the book, a person might never get on to the computer programming topics!

And so it is that I am skimming this section. Later I can get back to it for some fun and games. I might also get back to read the whole Concrete Mathematics book, another one I started and never finished. Additional motivation to read the CMath book is that there is a free ebook called Concrete Math Companion, which presents J programs and algorithms related to subjects treated in CMath. Just imagine the geekiness factor of this whole endeavor. It boggles the mind.

Markov algorithms in Scala

Now here’s the Scala code for Markov algorithms. I mostly followed the form of the Haskell code, except for string processing, which is done with StringBuilders to improve performance. Definitely a premature optimization.

case class StepParams(theta: String, phi: String, b: Int, a: Int)

class Algorithm(params: Array[StepParams]) {
  private def replaceIfPossible(p: StepParams, s: StringBuilder) =
  {
    val i = s.indexOf(p.theta)
    if (i != -1)
    {
      s.replace(i, i + p.theta.length, p.phi)
      true
    }
    else false
  }

  private def execLoop(word: StringBuilder, step: Int): String =
  {
    if (step == params.length)
      word.toString
    else if (replaceIfPossible(params(step), word))
      execLoop(word, params(step).b)
    else
      execLoop(word, params(step).a)
  }

  def exec(in: String) = execLoop(new StringBuilder(in), 0)
}

object Markov {
  val absDiff = new Algorithm(Array(StepParams("ab", "" , 0, 1),
                                    StepParams("a" , "c", 1, 2),
                                    StepParams("b" , "c", 2, 3)))

  val min = new Algorithm(Array(StepParams("ab", "d" , 1, 3),
                                StepParams("ad", "d" , 2, 3),
                                StepParams("db", "dd", 1, 3),
                                StepParams("a" , ""  , 3, 4),
                                StepParams("b" , ""  , 4, 5)))

  // The gcd algorithm, Exercise 8, Section 1.1
  val gcd = new Algorithm(Array(StepParams("ab", "" , 1, 2),
                                StepParams(""  , "c", 0, 2),
                                StepParams("a" , "b", 2, 3),
                                StepParams("c" , "a", 3, 4),
                                StepParams("b" , "b", 0, 5)))

  def replicate(n: Int, c: Char) =
  {
    val sb = new StringBuffer(n)
    for (i <- 1 to n)
      sb.append(c)
    sb.toString
  }

  def buildGcdString(m: Int, n: Int) = replicate(m, 'a') + replicate(n, 'b')

  def main(args: Array[String])
  {
    val in = if (args.length > 0) args(0) else "aaabb"
    println("absDiff: " + absDiff.exec(in))
    println("min    : " + min.exec(in))
    println("gcd    : " + gcd.exec(in))
  }
}

After loading this in the interpreter we can try it:

scala> Markov.gcd.exec(Markov.buildGcdString(24, 16))
res1: String = aaaaaaaa

Markov algorithms in Haskell

What follows are the basic definitions and the execution engine for Markov algorithms, written in Haskell. After the code I’ll show how to use it with some sample algorithms.

import Data.List

-- The parameters for a computational step
-- Each step is (theta, phi, b, a), following Knuth's notation
type StepParams = (String, String, Int, Int)

-- An algorithm is a sequence of steps
type Algorithm = [StepParams]

-- replace the first (leftmost) occurrence of string from with string to
replace :: Eq a => [a] -> [a] -> [a] -> [a]
replace []   to [] = to
replace _    _  [] = []
replace from to s@(c:cs)
    | isPrefixOf from s = to ++ (drop (length from) s)
    | otherwise = c : (replace from to cs)

-- The execution function
exec :: [StepParams] -> String -> String
exec ps input = execLoop (input, 0)
    where execLoop (word, step)
              | step == length ps = word
              | otherwise         = execLoop $ doStep (ps!!step) word
          doStep (theta, phi, b, a) word
              | isInfixOf theta word = (replace theta phi word, b)
              | otherwise            = (word, a)

Here are some algorithms. This calculates the absolute difference between numbers m and n, represented as strings with m ‘a’s and n ‘b’s, as suggested in the text. The output is formed with ‘c’s, the number of which will be the absolute value of m – n.

absDiff :: Algorithm
absDiff = [("ab", "" , 0, 1),         
           ("a" , "c", 1, 2),
           ("b" , "c", 2, 3)]

We can execute this algorithm for some sample input with

exec absDiff "aaaabb"

Which should print “cc”.

And here is the algorithm for calculating the greatest common divisor of m and n, using the same convention for the input. The output will consist of ‘a’s. This is the answer to exercise 8 of Section 1.1.

mGcd :: Algorithm
mGcd = [("ab", "" , 1, 2),      -- 0
        (""  , "c", 0, 2),      -- 1
        ("a" , "b", 2, 3),      -- 2
        ("c" , "a", 3, 4),      -- 3
        ("b" , "b", 0, 5)]      -- 4

The name is mGcd (for Markov gcd) to avoid clashes with the Prelude’s gcd. Note also that in step 1 the string theta (which is empty) should always match, so the value of a is irrelevant. I put 2 there, Knuth used 0 in the answer. Now let’s define some auxiliary functions to help us actually use this with some significant numbers:

buildStr m n = (replicate m 'a') ++ (replicate n 'b')

interpretResult = length

markovGCD m n = interpretResult $ exec mGcd (buildString m n)

And now we can use it:

*Main> markovGCD 2166 6099
57

It takes quite a few seconds, but outputs the correct answer to exercise 4 of Section 1.1.

Sec. 1.1: Algorithms

Section 1.1, Algorithms, is an introduction to the ideas of the book. It’s interesting to see how Knuth wrote the book in a time when computers were not widespread, and he thought about a target audience of people with little programming experience. He even explains what a variable assignment is. Nowadays no one would recomend TAoCP for beginners, so very few people will read this section without knowing how assignment works, or how to read an algorithm. 

By the end of the section Knuth shows briefly how to formalize the notion of algorithm mathematically, employing Markov algorithms. This was interesting, because although I had seen Markov algorithms before (in Curry‘s Fountations of Mathematical Logic), I didn’t really play with them. I ended up writing programs in Haskell and Scala to simulate an algorithm expressed with the notation as presented by Knuth, so I could check if I was getting it right. Later I’ll be posting the code here; first let’s see if I can get syntax highlighting working for these two languages.

The Art of Computer Programming

I’m reading Knuth‘s masterpiece The Art of Computer Programming for real, this time. I’ll log some notes about my efforts here. Due to Real Life obligations, it will have to proceed in a quiet fashion, and many moons shall pass between posts. Such is life.

Also, although Knuth recommends reading the books in order, I will probably read some parts concurrently. For example, right now I will skim through Chapter 1 (which I read many years ago, even doing many exercises) and begin studying Chapter 3 seriously, because random number generation interests me. So be it.