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

``` 0 9/4/2003 7:26:12 PM comp.theory  5139 articles. 1 followers. 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).
>
>
>
>

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

sort; search;

Good luck.

Rick

``` 0 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 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 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 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 9/5/2003 7:00:26 PM