Re: Inefficient algorithms

[Ludovic Brenta <ludovic@ludovic-brenta.org>]

I just wrote on comp.lang.ada:
> Niklas Holsti <niklas.holsti@tidorum.invalid> writes:
>> Niklas Holsti wrote:
>>> 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.
>>
>> Replying to myself, since I realize that I probably misunderstood your
>> need: what you want is an inefficient O(2^n) solution to an easy
>> (non-exponential) problem. The problem I suggested is not, of course,
>> an easy one. But it has easy variants. For example, require that the
>> Boolean formula uses at most 10 of the n variables, where this limit
>> (10) is considered a fixed number independent of the total number (n)
>> of variables.
>
> Actually I do think that the problem is trivial and that you can solve
> it without recursion.  If you see your array of Booleans as a number in
> binary representation:
>
> procedure Inefficient (N : in Natural) is
>
>    subtype Valuation is Natural range 1 .. 2**N;

Make that 0 .. 2**N, of course.

>    -- We assume the solution is Valuation'Last but it could be any value.
>    Solution : constant Valuation := Valuation'Last;
> begin
>    for K in Valuation'Range loop
>       exit when K = Solution;
>    end loop;
> end Inefficient;

Granted, a decent optimizing compiler might grab victory from the jaws
of defeat in this case :)

-- 
Ludovic Brenta.