Please help me with algorithms !!!

Discussion in 'C Programming' started by Natasha, Aug 31, 2006.

  1. Natasha

    Natasha Guest

    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
    Natasha, Aug 31, 2006
    #1
    1. Advertising

  2. Natasha

    jmcgill Guest

    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.
    jmcgill, Aug 31, 2006
    #2
    1. Advertising

  3. Natasha

    Randall Guest

    (Here's how to do it) Re: Please help me with algorithms !!!

    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
    Randall, Aug 31, 2006
    #3
  4. Natasha

    goose Guest

    Re: (Here's how to do it) Re: Please help me with algorithms !!!

    Randall wrote:
    >
    > Natasha wrote:
    >
    >>Problem #1.

    <snipped>
    >
    >


    Please do not top-post.

    goose,
    goose, Aug 31, 2006
    #4
  5. Re: (Here's how to do it) Re: Please help me with algorithms !!!

    goose <> 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.ghoti.net/~kst>
    San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
    We must do something. This is something. Therefore, we must do this.
    Keith Thompson, Sep 1, 2006
    #5
  6. Natasha

    Ian Collins Guest

    Re: (Here's how to do it) Re: Please help me with algorithms !!!

    Keith Thompson wrote:
    > goose <> 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.
    Ian Collins, Sep 1, 2006
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    4
    Views:
    502
    Chris Uppal
    May 5, 2005
  2. KK
    Replies:
    2
    Views:
    546
    Big Brian
    Oct 14, 2003
  3. MuZZy
    Replies:
    7
    Views:
    1,742
    Mike Hewson
    Jan 7, 2005
  4. entropy123

    Help: Algorithms in C (Sedgewick) "Graph.h"

    entropy123, Jul 29, 2003, in forum: C Programming
    Replies:
    1
    Views:
    587
    Martijn
    Jul 29, 2003
  5. Christopher Pisz

    Algorithms newsgroup referral please

    Christopher Pisz, Jun 12, 2013, in forum: C++
    Replies:
    2
    Views:
    156
    Victor Bazarov
    Jun 12, 2013
Loading...

Share This Page