Re: Inefficient algorithms

[Niklas Holsti <niklas.holsti@tidorum.invalid>]

Rick wrote:
> I am working on a class in algorithmic efficiency and, to make a
> point, need an algorithm that runs O(2^n) - a factoring algorithm
> perhaps.  All I can find is 'C' code I can't decipher.  Can someone
> please help with an Ada example.

Perhaps the canonical example is this: you are given a Boolean formula 
containing n Boolean variables. Find a valuation (a value, True or 
False, for each variable) that makes the formula True. The O(2^n) 
algorithm tries each of the 2^n valuations in some order, evaluates the 
formula for this valuation, and stops when True.

In Ada, something like:

    N : constant := ...;

    type Valuation is array (1 .. N) of Boolean;
    -- Valuation(k) is the value of Boolean variable number k.

    function Formula (Inputs : Valuation) return Boolean
    is begin
       return <complex formula>;
    end Formula;

The search through all possible valuations is logically like an n-deep 
nested loop of the form

    for Value1 in Boolean loop
       for Value2 in Boolean loop
          ...
             for Value_n in Boolean loop
                if Formula ((Value1, Value2, ..., Value_n)) then
                   <exit and report success>.
                end if;
             end loop;
          ...
       end loop;
    end loop;

Since N is a variable, you cannot write out this N-deep loop nest in the 
Ada program. Instead, use a recursive function that is given a partial 
valuation, for example a valuation that gives the values for the 
variables 1 .. k, and then extends the valuation by trying both False 
and True values for variable k+1, calling itself recursively until it 
has a full valuation, when it calls Formula to see if this full 
valuation is a solution.

HTH,

-- 
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
       .      @       .