Results 1 to 6 of 6

Math Help - Algorithm Design Problem

  1. #1
    Junior Member Sarasij's Avatar
    Joined
    Jun 2011
    From
    India
    Posts
    42
    Thanks
    2

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

    Please help me here guys...this problem is just getting more tough to me day by day.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2008
    Posts
    1,035
    Thanks
    49

    Re: Algorithm Design Problem

    Quote Originally Posted by Sarasij View Post
    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 {*,+}.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member Sarasij's Avatar
    Joined
    Jun 2011
    From
    India
    Posts
    42
    Thanks
    2

    Re: Algorithm Design Problem

    Quote Originally Posted by tom@ballooncalculus View Post
    \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 ?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2008
    Posts
    1,035
    Thanks
    49

    Re: Algorithm Design Problem

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

    Combination - Wikipedia, the free encyclopedia
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member Sarasij's Avatar
    Joined
    Jun 2011
    From
    India
    Posts
    42
    Thanks
    2

    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???
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Simple PI controller design problem
    Posted in the Advanced Applied Math Forum
    Replies: 1
    Last Post: April 17th 2011, 07:44 AM
  2. Design And Measurement math problem
    Posted in the Geometry Forum
    Replies: 1
    Last Post: April 18th 2010, 08:37 PM
  3. Another Design and Measurement Problem
    Posted in the Geometry Forum
    Replies: 1
    Last Post: April 18th 2010, 03:53 PM
  4. Replies: 2
    Last Post: November 4th 2009, 06:03 AM
  5. Design matrices problem
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: September 16th 2007, 03:18 PM

Search Tags


/mathhelpforum @mathhelpforum