Roland's blog

Here's the C code for the game of life. Next .. make it parallel with mpich. Game of Life

I am almost done with the algorithms course however, the programming assignment on satisfiability is turning out to be a real pain.

The issue is not the concept. The concept is straitforwad, but implementing tree traversals in C with arrays is a ROYAL PAIN.

http://cs.uc.edu/~jpaul/471s07/index.html - Dr. Paul's Course Page... I took it for 671 but it says 471.

Anyways, I think It's rather nice to have all course docs and I am sure he's going to take it all off soon so I made a copy just for my use.

If you need something you may try to ask me but probably it's better to ask the prof first.

from http://www.informatik.uni-ulm.de/acm/Locals/2005/html/judge.html 

Problem H: Help the problem setter

As the inductive definition of a binary search tree suggests, this problem is best solved using recursion.
Obviously, if the tree has only 1 node, there is only one binary search tree, so we can use any frequency (for example 1). Now assume we want to calculate the frequency for an inner node. First, we calculate the frequencies of the nodes in its left and right subtree by recursive calls. Now, we have to think about what happens if we do not use the current node as the root of its subtree. This means, that either a node of the left subtree or of the right subtree becomes the root. Without loss of generality, assume that a node L of the left subtree becomes the root. This means that some nodes may move from the left subtree to the right subtree. Obviously, this will only increase the access cost for the right subtree, so if we want to determine the lowest possible access cost, we keep the cost of the right subtree artificially constant. This can be done if we allow the new root to have 4 children.

Because the frequencies of the subtrees were determined in such a way that there is a unique optimal binary search tree, the structure of the left subtree does not change, but all nodes of the left subtree move one level up. That means that the access cost of the data structure decreases by the sum of the frequencies of nodes in the left subtree.
The new root gets two additional children: the old root and the root of the right subtree. For the same reason as above, the structure of the right subtree does not change.

This is an adaptation from wikipedia.

#include 
#include 
#include 

/* Let INFINITY be an integer value not likely to be
   confused with a real weight, even a negative one.    

      
roland's blog
Add new comment
Read more
    
  

Right now the infinity idea is just inf = 999 but you can change it.

def print_matrix(m)
  m.collect{|row| row.join("t")}.join("n") + "n"
end

def floyd(w)
  string = ""
  n = w.size
  p = Array.new(n) {[]}
  s = Array.new(n) {[]}
  for i in 0..(n-1)
    for j in 0..(n-1)
      p[i][j] = -1
      s[i][j] = w[i][j]
    end
  end

  for k in 0..(n-1)
    for i in 0..(n-1)
      for j in 0..(n-1)
        if s[i][j] > s[i][k] + s[k][j]
          p[i][j] = k
          s[i][j] = s[i][k] + s[k][j]
        end
      end
    end
    string << "p #{k}: n"
    string << print_matrix(p)
    string << "s #{k}: n"
    string << print_matrix(s)
  end
  string
end

inf = 9999

#~ w = [[0,   4,   inf, 3,    inf],
     #~ [inf, 0,   6,   inf,  2],
     #~ [1,   inf, 0,   inf,  inf],
     #~ [4,   inf, 2,   0,    3],
     #~ [inf, inf, 1,   inf,  0]]
      #~ 0      1     2      3       4       5
w = [[0,    inf,  -2,   inf,    inf,    inf],
     [3,    0,    inf,  inf,    inf,    inf],
     [inf,  4,    0,    inf,    1,      3],
     [inf,  inf,  -1,   0,      1,      inf],
     [inf,  inf,  inf,  2,      0,      1],
     [4,    inf,  4,    inf,    inf,    0]]
s = floyd(w)
w = File.open("floyd.tab", "w")
w.write(s)
w.close

Code

def LongestCommonSubsequence(t, p)
  n = t.size
  m = p.size

  lcs = Array.new(n+1) {[]}

  for i in 0..n
    lcs[i][0] = 0
  end
  for j in 0..m
    lcs[0][j] = 0
  end

  for i in 1..n
    for j in 1..m
      if t[i-1] == p[j-1]
        lcs[i][j] = lcs[i-1][j-1]+1
      else
        lcs[i][j] = [lcs[i][j-1], lcs[i-1][j]].max
      end
    end
  end
  lcs
end

t = "alligator"
p = "algorithms"

print "  | 0 ", (1..10).to_a.join(" ") + "n"
print "-"*28 + "n"
count = -1
lcs = LongestCommonSubsequence(t, p)
lcs.each do |line|
  print count+=1, " | ", line.join(" ") + "n"
end

Results

  | 0 1 2 3 4 5 6 7 8 9 10
----------------------------
0 | 0 0 0 0 0 0 0 0 0 0 0
1 | 0 1 1 1 1 1 1 1 1 1 1
2 | 0 1 2 2 2 2 2 2 2 2 2
3 | 0 1 2 2 2 2 2 2 2 2 2
4 | 0 1 2 2 2 2 3 3 3 3 3
5 | 0 1 2 3 3 3 3 3 3 3 3
6 | 0 1 2 3 3 3 3 3 3 3 3
7 | 0 1 2 3 3 3 3 4 4 4 4
8 | 0 1 2 3 4 4 4 4 4 4 4
9 | 0 1 2 3 4 5 5 5 5 5 5

When using optimal binary search tree, you want to make sense of how do you create the tree from the Root matrix. Well here's how you do it.

pi = [0.15, 0.1, 0.2, 0.3]
qi = [0.05, 0.05, 0, 0.05, 0.1]
root = optimal_search_tree(pi, qi)[1]

class Node
  attr_accessor :left, :right, :key
  def initialize
    @left = @right = @key = nil
  end
end

def build_tree(root, r, i, j)
  if i <= j
    r.key = root[i][j]
    build_tree(root, r.left ||= Node.new, i, root[i][j]-1)
    build_tree(root, r.right||= Node.new, root[i][j]+1, j)
  end
end

@root = Node.new
build_tree(root, @root, 0, root.size-1)

Dr. Paul describes in his book the OptimalSearchTree algorithm. Here's it's implementation in ruby.

def print_matrix(m)
  print m.collect{|row| row.join("t")}.join("n") + "n"
end

def optimal_search_tree(p, q)
  n = p.size
  root = Array.new(n){Array.new(n){0}}
  a = Array.new(n){Array.new(n){0}}
  sigma = Array.new(n){Array.new(n){0}}
  for i in 0..(n-1)
    root[i][i] = i
    sigma[i][i] = p[i] + q[i] + q[i+1]
    a[i][i] = sigma[i][i]
  end
  for pass in 1..(n-1)
    for i in 0..(n-1-pass)
      j = i + pass
      sigma[i][j] = sigma[i][j-1] + p[j] + q[j+1]
      root[i][j] = i
      min = a[i+1][j]
      for k in (i+1)..j
        sum = a[i][k-1] + (a[k+1][j] rescue 0)
        if sum < min
          min = sum
          root[i][j] = k
        end
      end
      a[i][j] = min + sigma[i][j]
    end
  end
  [a, root, sigma]
end

And test out the functions:

p = [15, 10, 20, 30]
q = [5, 5, 0, 5, 10]
a, root, sigma = optimal_search_tree(p, q)
print_matrix a; print "n"
print_matrix root; print "n"
print_matrix sigma; print "n"

Results:

a:
25      50      110     195
0       15      55      135
0       0       25      90
0       0       0       45
root:
0       0       1       2
0       1       2       3
0       0       2       3
0       0       0       3
sigma:
25      35      60      100
0       15      40      80
0       0       25      65
0       0       0       45