# Algorithm Design Problem

• May 9th 2012, 12:16 PM
Sarasij
Algorithm Design Problem
The problem is as follows:
---------------------------------------------------------------------------------------------------------------------------------------------------
You are given a list of positive integers along with a sequence of operations from the
set {*,+}. You construct expressions from these two lists so that:

1. The numbers in the expression are drawn from the first list, without repetition and without altering their order.

2. All the operators in the second list are used in the expression, in the same order.

For example, if the two lists are [1,3,2,1,4] and [’*’,’+’], the set of possible expressions you can form are :

{1*3+2, 1*3+1, 1*3+4, 1*2+1, 1*2+4, ..., 2*1+4}

For each expression, the value is computed by bracketing operators from the right.
That is, the expressions above are evaluated as

{1*(3+2), 1*(3+1), 1*(3+4), 1*(2+1), 1*(2+4), ..., 2*(1+4)}

The aim is to "determine maximum value among these expressions". In this example,
the maximum value is 18, from the expression 3*2+4, which is evaluated as 3*(2+4).

You may assume that the length of the first list is more than the length of the second
list.

Describe an algorithm to solve this problem.
-----------------------------------------------------------------------------------------------------------------------------------------------
Let's take a first list on n numbers [a1,a2,...,an] and say the second list of operators have any sequence of m symbols from {*,+} where n>m.

I am puzzled with the thought that if I store each expression constructed from the above 2 lists in a 1D array(say A[X]) how many terms will that array

contain? That is what can be the upper bound for the possible size of this array? Is it O(n^m) or something less? If this riddle is solved then finding a

maximum is very easy in O(X) time.

• May 10th 2012, 06:48 AM
tom@ballooncalculus
Re: Algorithm Design Problem
Quote:

Originally Posted by Sarasij
how many terms will that array contain?

$\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 {*,+}.
• May 10th 2012, 11:09 AM
Sarasij
Re: Algorithm Design Problem
Quote:

Originally Posted by tom@ballooncalculus
$\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 ?
• May 10th 2012, 12:17 PM
tom@ballooncalculus
Re: Algorithm Design Problem
Each expression is one distinct way of choosing m+1 elements from the first list.

Combination - Wikipedia, the free encyclopedia
• May 10th 2012, 02:18 PM
emakarov
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.
• May 10th 2012, 09:45 PM
Sarasij
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???