Re: Algorithm Design Problem

Quote:

Originally Posted by

**Sarasij** how many terms will that array contain?

$\displaystyle \binom{n}{m+1}$

If the m symbols are all from {*} or all from {+} then you can obviously improve massively on having to construct that array at all. Presumably the problem is to effect a less dramatic improvement for {*,+}.

Re: Algorithm Design Problem

Quote:

Originally Posted by

**tom@ballooncalculus** $\displaystyle \binom{n}{m+1}$

If the m symbols are all from {*} or all from {+} then you can obviously improve massively on having to construct that array at all. Presumably the problem is to effect a less dramatic improvement for {*,+}.

Can you please give the argument how did you calculate the value of X ?

Re: Algorithm Design Problem

Each expression is one distinct way of choosing m+1 elements from the first list.

Combination - Wikipedia, the free encyclopedia

Re: Algorithm Design Problem

Here is program in OCaml, which is probably incomprehensible.

Code:

`let id x = x`

(*

ns : list of numbers (int)

len_ns : length of ns

os : list of binary operators of type int -> int -> int

len_os : length of os

op : the result accumulated so far of type int -> int

e.g. if ns = [1; 3; 2; 1; 4] and os = [(*); (+)],

and we select 1, then op = (1 * ...) that expects the second argument

cm : current maximum (maximum so far)

*)

let rec maximize ns len_ns os len_os op cm =

match (ns, os) with

| ([n], []) -> max cm (op n)

| (n :: ns', []) ->

let cm' = maximize ns' (len_ns - 1) [] 0 op cm (* skip n *) in

max cm' (op n) (* pick n *)

| (n :: ns', o :: os') ->

if len_ns > len_os + 1 then

let cm' = (maximize ns' (len_ns - 1) os len_os op cm) (* skip n *) in

maximize ns' (len_ns - 1) os' (len_os - 1) (o (op n)) cm' (* pick n and o *)

else maximize ns' (len_ns - 1) os' (len_os - 1) (o (op n)) cm

let run ns os =

maximize (rev ns) (length ns) (rev os) (length os) id 0

First, the program calculates left-to-right; so the first thing the main function "run" do is reverse the lists.

Consider a situation in the middle of the search. Suppose the initial (reversed) lists are [4; 1; 2; 3; 1] and [(+); (*)]. Suppose we skipped 4 and picked 1. Then the current expression is (1 * ...), which expects the second argument. This function that takes the next picked number and returns the result of the expression so far is the argument "op" of "maximize". The remaining lists at this point are [2; 3; 1] and [(*)]. Since the length of [2; 3; 1] is greater than the length of [(*)] by 2 (not by 1), we have a choice whether to pick 2. If we pick 2 and (*), then (after the recursive call) "op" becomes ((1 + 2) * ...) and we remove the heads of the lists "ns" and "os". If we don't pick n, then "op" stays the same and we remove the head of "ns" only.

The last argument "cm" of "maximize" is the maximum that is found so far. When we have a choice whether to pick the next number, we first feed "cm" to the recursive call that skips the number. It returns the maximum cm' that is obtained by exploring that part of the search tree. Then we feed cm' to the recursive call that picks the next number, and it returns the final maximum.

Re: Algorithm Design Problem

Ok,now I get it!! But that means the running time must be exponential in terms of the input n and m. Can we get a polynomial time here anyways by optimization???