Thread: Group Project Help/Volunteer

  1. #1
    Registered User
    Join Date
    Mar 2007

    Group Project Help/Volunteer

    Hey for a project in my cs class, we were split into groups and asked to create instructions to help the other students learn about a certain data structure. My group has hash tables. We've created a set of instructions and I wanted to know if anyone could actually read them and then perform what it says to do and post it so my group and I can evaluate what we need to change if anything. I forgot to mention that the other groups have to perform the instructions given by the other groups. We as a group have done them but i mean we wrote them and we want an outside source. The teacher is 'too busy' to do it and we are the only class that exists for this subject. i'll post the instructions and maybe someone will be bored and want to help out by doing it! Thanks to anyone or if more than one person does it. This is the final project for this class which is why we want to make sure its perfect.

    Objective: This project will give you experience working with hash tables, as well as working with real data used by complex pieces of software, namely, Web proxy caches.


    In class we learned about hash tables, which store pairs of the form p = (k,v), where k is a key and v is a value associated with the key. The Standard Template Library does not strictly provide a hash table (although it does provide classes that will implement insert(), find() and erase()). To implement a hash table, you need to decide the following things:

    * the size of the hash table
    * what hash function you will use
    * how you will resolve collisions

    To make reasonable decisions you need to consider anything you may know about the population of keys you will be placing in the table. This should become apparent in the following application of hash tables.


    A "proxy cache" is a piece of software that handles web requests on
    behalf of a population of Web users. Instead of sending requests directly
    to the Web server that contains the item, users may point their Web browsers
    to a proxy cache that is running near them. If the proxy cache contains
    the item requested, it can return that item immediately instead of
    requiring the request to travel all the way to a remote (and possibly
    very busy) Web server and back. If the cache does not
    contain the item it will fetch the item from the remote Web server and
    forward it to the requesting browser, while storing a local copy. In this
    way, subsequent requests for popular items may be satisfied more quickly.

    Implementing a proxy cache requires three operations: insert(p), find(k)
    and delete(k), where the keys are strings representing the items being
    requested (the portion of a URL *after* http://, sometimes starting
    with "www", like ""). Sounds like a job for a
    hash table, no? (Go figure!) So your job for this project is to evaluate
    three different designs for a hash table.


    Each evaluation method will work in the same way:

    * Write a program that creates a hash table of a specified size.
    * Read input from a file called "requests.dat", each line of which is a
    request for an item residing on a server.
    * Place the item in the hash table using some hash function. The method
    we will use to resolve collisions is similar to separate chaining:
    we will store the elements in the "set" class provided by the STL.
    (#include <set>) That is, you don't know the actual underlying
    data structures used by the STL set --- just that you can store multiple
    items in it, and ask how many items are in the set.
    * Loop through each location in the hash table, printing out the number
    of elements stored in that location.

    You will do this three times, with a different set of hash table parameters
    each time. We observed that the best form of a hash table is one in which
    each "bucket" contains the fewest possible items. You will evaluate these
    hash table/hash function combinations:

    * First, use a hash table of size 256. The hash function you will use
    is f(k) = 10. Yes, it's a silly hash function; you should use it just
    to "sanity check" your work.
    * Second, create a hash table of size 256. The hash function you will use
    now is the function given in program 10.14 on page 386 of the text (this
    is the one we discussed in class in some detail).
    * Third, create a hash table, the size of which is a prime number of
    your choice with size less than 400.
    Select your own hash function. Try to find one that does a good job
    of spreading out the data. (Can you do better than in the second
    part above?)

    You will turn in the following for each of the three sets of parameters:

    1. A printout of the number of items in each location in the hash table
    in table form, with 5 elements across in one row and fields of width 8.
    For example, if your hash table is of size 14, your table may look
    like this:
    12 6 16 13 1
    4 0 8 5 15
    21 0 21 0

    2. A discussion of the results, including a discussion of why the table
    has the structure it does and how good you think the hash table
    parameters are. (This discussion may be brief --- a full analysis
    will entail knowledge of probability and statistics beyond the scope
    of this course. However, feel free to include information like mean,
    median and stddev if you are so inclined.)

  2. #2
    Registered User
    Join Date
    Oct 2006
    in the mean time, have you asked someone in another group to follow them?

  3. #3
    Registered User
    Join Date
    Mar 2007
    no, maybe i should clearify more. The project will be given out to the other groups and each of the groups has to evaluate each other based on things such as clarity, difficulty, did they learn anything. Then based on those comments the teacher will just look at the instructions and give a grade. He might try them i'm not sure he didn't say, but either way we want to make sure its as perfect as can be before we have to do hand it in.

  4. #4
    Registered User
    Join Date
    Mar 2007
    will no one like to do this, help me out please.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Problem Displaying a Struct
    By rockstarpirate in forum C++ Programming
    Replies: 16
    Last Post: 05-05-2008, 09:05 AM
  2. !!!Urgent Help on a group project!!!!!
    By AmeenR in forum C Programming
    Replies: 3
    Last Post: 12-13-2003, 09:22 PM
  3. ray casting
    By lambs4 in forum Game Programming
    Replies: 62
    Last Post: 01-09-2003, 06:57 PM