Please help me with algorithms !!!

[Natasha]

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

 

[jmcgill]

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.

 

[Randall]

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

 

[goose]

>

Please do not top-post.

goose,

 

[Keith Thompson]

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.

 

[Ian Collins]

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?