From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham
	autolearn_force=no version=3.4.4
X-Google-Thread: 103376,9dfc10efb95ba130
X-Google-NewGroupId: yes
X-Google-Attributes: gida07f3367d7,domainid0,public,usenet
X-Google-Language: ENGLISH,ASCII-7-bit
Path: 
 g2news1.google.com!news3.google.com!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail
From: Niklas Holsti <niklas.holsti@tidorum.invalid>
Newsgroups: comp.lang.ada
Subject: Re: Inefficient algorithms
Date: Sat, 11 Sep 2010 09:54:30 +0300
Organization: Tidorum Ltd
Message-ID: <8f0nd6F8ucU1@mid.individual.net>
References: 
 <1f6f73cd-f5ff-4408-a1d7-c9ca7dfa70ee@m35g2000prn.googlegroups.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
X-Trace: individual.net PKSCnu5oKoxLAgvpUs79nQS/ypYOrRh2uLlzImLRCF/ESHMEFz
Cancel-Lock: sha1:71yX9eWx/fqP/tZQC/vBz2E0guo=
User-Agent: Mozilla-Thunderbird 2.0.0.24 (X11/20100328)
In-Reply-To: 
 <1f6f73cd-f5ff-4408-a1d7-c9ca7dfa70ee@m35g2000prn.googlegroups.com>
Xref: g2news1.google.com comp.lang.ada:14007
Date: 2010-09-11T09:54:30+03:00
List-Id: <comp.lang.ada>

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
       .      @       .