Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Please help me with algorithms !!!

Reply
Thread Tools

Please help me with algorithms !!!

 
 
Natasha
Guest
Posts: n/a
 
      08-31-2006
Problem #1.

I have 10000 ascii strings (such as perhaps loaded from a file)
A string is input from stdin.
I need to write pseudocode that returns (to stdout) a subset of strings
in the file that contain the same distinct characters (regardless of
order) as input in (input from stdin).
How do I optimize for time.
Assume that this function will need to be invoked repeatedly
For example, if I have strings in the file: mary, brad, pitt, yygr and
the user types in: ry --> the output should be "mary" and "yygr" or if
the user types in: dd --> brad

Problem #2

The whole point is to design a quick lookup to see if a phrase from a
dictionary of phrases occurs inside a user query.

I have a set of 100,000 ascii strings, up to 255 chars each.
Each string has 1 or more words (tokens), space-separated.
A query is input from stdin (1 or more ascii words (tokens),
space-separated)
How towrite pseudocode that determines if the query "soft matches" to
any string from (1). By "soft match", I mean that a contiguous subset
of tokens from the query must match the entirety of the tokens from a
single entry in (1), in the same token order.
How do I optimize for time (this has to process user queries as fast as
possible). For example,
a. if I have strings in (1): mary poppins, brad pitt, yygr
b. and the user types in pictures of brad pitt --the output should be
"true" (because it soft-matches to "brad pitt") or
c. if the user types in: brad --false
d. or if the user types in: brad pitt --true (exactly matches "brad
pitt")
e. or if the user types in: pitt brad pictures --false (right tokens as
in "brad pitt", but wrong order)
f. or if the user types in: brad pitts --false (char match to "brad
pitt", but not a token match)
g. or if the user types in: brad yygr --true (contains "yygr")

Please help

 
Reply With Quote
 
 
 
 
jmcgill
Guest
Posts: n/a
 
      08-31-2006
Natasha wrote:

> Please help


Natasha, it sounds as though you are over your head in a 300-level
Discrete course already. Be honest and up front as to whether you are
asking for help with homework, and maybe ask your Theory/Pseudocode
questions in comp.theory or comp.programming.
 
Reply With Quote
 
 
 
 
Randall
Guest
Posts: n/a
 
      08-31-2006
Hello Natasha:

This looks like a homework assignment. You are in luck today. I won't
give you the answer, but I will show you how to get the answer. It
looks like you're a bit overloaded and aren't sure where to start. Let
me get you started by identifying the "essential" elements you need to
address to solve your problem.

FIRST PART (IDENTIFY YOUR ALGORITHM AND DATA STRUCTURE)
Advice: don't worry about performance before you know what you are
doing. Make your algorithm work for just one specific case. Make is
store the strings "Mary" and "Brad." Then search those two strings
given another string like "ry".

List the essential parts of your algorithm (step by step instructions)
first:
1. You have 10,000 strings (you have to store them in something:
array, vector...)
2. The strings come from standard in

3. You have to search each of the 10,000 strings for some characters
(sounds like a loop with an if statement to me)
4. When you have a string containing those characters output them to
standard out (add a print statement to above)

SECOND PART (GENERALIZE YOUR SOLUTION)
Voice of experience:
This is where you make your very specific algorithm work for 10,000
strings. If you have an algorithm that can do two strings chances are
you already know how to do more.

"Assume that this function will need to be invoked repeatedly" probably
means that you should identify the things that change each time you
invoke the algorithm (A file name would be likely to change between
invocations right?). Other than a file name what else is likely to
change between invocations of your algorithm? Hint: what are you
searching for?

THIRD PART (CHECK YOUR WORK)
Give your algorithm some small sample data like the data below (ry ->
mary and yygr). Identify any oversights and correct them.

Good luck on your assignment.

-Randall

Natasha wrote:
> Problem #1.
>
> I have 10000 ascii strings (such as perhaps loaded from a file)
> A string is input from stdin.
> I need to write pseudocode that returns (to stdout) a subset of strings
> in the file that contain the same distinct characters (regardless of
> order) as input in (input from stdin).
> How do I optimize for time.
> Assume that this function will need to be invoked repeatedly
> For example, if I have strings in the file: mary, brad, pitt, yygr and
> the user types in: ry --> the output should be "mary" and "yygr" or if
> the user types in: dd --> brad
>
> Problem #2
>
> The whole point is to design a quick lookup to see if a phrase from a
> dictionary of phrases occurs inside a user query.
>
> I have a set of 100,000 ascii strings, up to 255 chars each.
> Each string has 1 or more words (tokens), space-separated.
> A query is input from stdin (1 or more ascii words (tokens),
> space-separated)
> How towrite pseudocode that determines if the query "soft matches" to
> any string from (1). By "soft match", I mean that a contiguous subset
> of tokens from the query must match the entirety of the tokens from a
> single entry in (1), in the same token order.
> How do I optimize for time (this has to process user queries as fast as
> possible). For example,
> a. if I have strings in (1): mary poppins, brad pitt, yygr
> b. and the user types in pictures of brad pitt --the output should be
> "true" (because it soft-matches to "brad pitt") or
> c. if the user types in: brad --false
> d. or if the user types in: brad pitt --true (exactly matches "brad
> pitt")
> e. or if the user types in: pitt brad pictures --false (right tokens as
> in "brad pitt", but wrong order)
> f. or if the user types in: brad pitts --false (char match to "brad
> pitt", but not a token match)
> g. or if the user types in: brad yygr --true (contains "yygr")
>
> Please help


 
Reply With Quote
 
goose
Guest
Posts: n/a
 
      08-31-2006
Randall wrote:
>
> Natasha wrote:
>
>>Problem #1.

<snipped>
>
>


Please do not top-post.

goose,
 
Reply With Quote
 
Keith Thompson
Guest
Posts: n/a
 
      08-31-2006
goose <(E-Mail Removed)> writes:
> Randall wrote:
>> Natasha wrote:
>>
>>>Problem #1.

> <snipped>
> >

>
> Please do not top-post.


For details, see <http://www.caliburn.nl/topposting.html>.

A note to the regulars: Please post this link, or a similar one, when
you ask people not to top-post. A lot of newbies don't know what
"top-posting" means; *most* of them are capable of learning given a
pointer to the right information.

--
Keith Thompson (The_Other_Keith) http://www.velocityreviews.com/forums/(E-Mail Removed) <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
 
Reply With Quote
 
Ian Collins
Guest
Posts: n/a
 
      09-01-2006
Keith Thompson wrote:
> goose <(E-Mail Removed)> writes:
>
>>Please do not top-post.

>
> For details, see <http://www.caliburn.nl/topposting.html>.
>
> A note to the regulars: Please post this link, or a similar one, when
> you ask people not to top-post. A lot of newbies don't know what
> "top-posting" means; *most* of them are capable of learning given a
> pointer to the right information.
>

Such as google?

--
Ian Collins.
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
help on implementation algorithms on vector antani C++ 1 03-19-2007 07:49 PM
Please please please help this guy with his open source java app casioculture@gmail.com Java 4 05-05-2005 08:24 AM
HELP! HELP! PLEASE, PLEASE, PLEASE tpg comcntr Computer Support 11 02-15-2004 06:22 PM
please help... ...me learn C++ please please please :) KK C++ 2 10-14-2003 02:08 PM
Help: Algorithms in C (Sedgewick) "Graph.h" entropy123 C Programming 1 07-29-2003 06:37 AM



Advertisments