f



help me in this computer theory problem

Problem 2 (5 points)
Write an algorithm that inputs an integer array A[1::n] and an odd
integer number k, and determines whether k can be represented as the
sum of two elements of the array. If k is the sum of two elements of
A[1::n], your algorithm should return true; else, it should return
false. Its running time should be O(n  lg n).



Please help me in this problem
0
9/4/2003 7:26:12 PM
comp.theory 5139 articles. 1 followers. marty.musatov (1143) is leader. Post Follow

5 Replies
361 Views

Similar Articles

[PageSpeed] 48


Savior wrote:

> Problem 2 (5 points)
> Write an algorithm that inputs an integer array A[1::n] and an odd
> integer number k, and determines whether k can be represented as the
> sum of two elements of the array. If k is the sum of two elements of
> A[1::n], your algorithm should return true; else, it should return
> false. Its running time should be O(n  lg n).
> 
> 
> 
> Please help me in this problem
>

Sure smells like homework to me. Here's a hint:

    sort; search;

Good luck.


Rick

 

0
rdecker (166)
9/4/2003 7:43:07 PM
Savior <bomb992000@yahoo.com> wrote:
> Problem 2 (5 points)
> Write an algorithm that inputs an integer array A[1::n] and an odd
> integer number k, and determines whether k can be represented as the
> sum of two elements of the array. If k is the sum of two elements of
> A[1::n], your algorithm should return true; else, it should return
> false. Its running time should be O(n  lg n).

So does Prof. Fink allow you to do this?  I know that in my algorithms
class if you tried to get someone else to do your homework for you it
would be considered cheating....

-- 

That's News To Me!
newstome@comcast.net
0
newstome (151)
9/4/2003 8:00:26 PM
In article <9d8c3f93.0309041126.6b9c1060@posting.google.com>,
    Savior <bomb992000@yahoo.com> wrote:

: Problem 2 (5 points)
: Write an algorithm that inputs an integer array A[1::n] and an odd
: integer number k, and determines whether k can be represented as the
: sum of two elements of the array. If k is the sum of two elements of
: A[1::n], your algorithm should return true; else, it should return
: false. Its running time should be O(n lg n).

Here's a start:

    #! /usr/bin/perl

    sub two_elements_summed_give {
        my $a = shift;
        my $k = shift;

        local $_ = join(""=>map{'/'x$_.'.'}@$a).'|'.'/'x$k;
        / ^  .
         * ( ^  |
           \.  )
      (      \/   + )
       \.          .+
        \.    (     \/
         +)   \.     .
         *    \|     \2
         \3    $     /x
         ||/^.        *(
                 ^    |
         \.   )(     \/
              +       )
               \.    (
                \/    +
                 )     \.
                .      *
               \|      \2
                \3      $
                       /x;
    }

    $| = 1;

    print "Enter A: ";
    my $a = [ split ' ', scalar <STDIN> ];

    print "Enter k: ";
    my $k = <STDIN>;
    $k =~ s/^\s+//;
    $k =~ s/\s+$//;

    if (two_elements_summed_give $a => $k) {
        print "True.\n";
    }
    else {
        print "False.\n";
    }

Hope this helps,
Greg
-- 
In this respect, there is one foreign aid policy that is sure to alleviate
endemic poverty throughout the world: translate the works of Bastiat, Mises,
Bauer, Hayek and into the languages of less developed countries and airdrop
them onto their city streets.          -- Jude Blanchette
0
gbacon (88)
9/4/2003 11:34:18 PM
Greg Bacon wrote:
>         local $_ = join(""=>map{'/'x$_.'.'}@$a).'|'.'/'x$k;
>         / ^  .
>          * ( ^  |
>            \.  )
>       (      \/   + )
>        \.          .+
>         \.    (     \/
>          +)   \.     .
>          *    \|     \2
>          \3    $     /x
>          ||/^.        *(
>                  ^    |
>          \.   )(     \/
>               +       )
>                \.    (
>                 \/    +
>                  )     \.
>                 .      *
>                \|      \2
>                 \3      $
>                        /x;

Getting Perl's regular expression engine to check for
a sum in unary representations of the inputs.  Wow!
And I say that as a winner of the Obfuscated C Contest.

-paul-
-- 
Paul E. Black (p.black@acm.org)
0
p.black (279)
9/5/2003 4:44:51 PM
In article <3F58BD83.CFAC94E6@acm.org>,
    Paul E. Black <p.black@acm.org> wrote:

: Getting Perl's regular expression engine to check for
: a sum in unary representations of the inputs.  Wow!
: And I say that as a winner of the Obfuscated C Contest.

We're computing sums, so I should've used adding regular expressions:

              /^.*
              (^|
              ###
          \.)(\/+)\.##
              .+#
              \.#
              ###


              (\/
              +)#
              \..
         *\|\2\3$/x||#
              /^.
              *(^
              |\.


              ##
              )(
              \/
         +)\.(\/+)\..#
              *\|
              \2
              ##

            \3$/x;

Still too many giveaways. :-(

Matching Perl regular expressions is actually NP-complete:

    http://perl.plover.com/NPC/

    http://home.hiwaay.net/~gbacon/perl/clique.html

Greg
-- 
[Freud] raved about "the stimulative effect of coca on the genitalia" and in
a letter to his fiancee, Martha, "forewarned her of the pleasure she could
expect from 'a wild man with cocaine in his body'"--revealing him to be not
just the father of psychoanalysis but a precursor of gangsta rap.  --GK
0
gbacon (88)
9/5/2003 7:00:26 PM
Reply: