1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Hashing problem

  1. Jan 15, 2017 #1
    1. The problem statement, all variables and given/known data
    In a factory, machines are making cars (1-n) along the production line. One machine is making one part on the existing construction (part 1 is made by machine 1,...). Installation order of some parts is not important, but some parts have to be installed before others. Engineers have put together a dependence list for car parts as a table:
    1 2
    2 4
    3 2,1
    4
    5 3,8,7,6
    6 4,7
    7 3,8
    8 4,3,1


    where the first column represents parts (1-8), and the second column represents preconditions for installment of each part. That is the list of parts (second column) whose installment must be done before the installment of current part (first column).

    For each given list (second column), find the order of machines along the production line such that the manufacturing process of a car is done without interruptions, if such order exists. Also, find lists from the given table that give orders with interruptions.

    Design an algorithm for this problem.
    Show the final order of machines along the production line, if it exists.

    2. Relevant equations
    -Hash functions
    -Hash tables

    3. The attempt at a solution

    For each part (1-8, first column) we have to find a hash function without collisions that satisfies the second column in the table (if possible).

    This is obviously the reversed process from generating hash table from given hash function.

    I have found that the only possible order of machines along with production line, such that there is no interruption in the process is:
    [tex]4,2,1,3,8,7,6,5[/tex]

    Also, lists [itex]4-7,4-3-1[/itex] are causing an interruption (collision) in a process.

    Question: How can we generate hash function from hash table (reversed algorithm from standard, where hash function is given - create hash table)?
     
    Last edited: Jan 15, 2017
  2. jcsd
  3. Jan 15, 2017 #2

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    I do not understand how the problem of finding an algorithm for this has anything to do with hash functions. Can you explain what you mean by the hash function "satisfying" the second column?
     
  4. Jan 15, 2017 #3
    Maybe I have misunderstood the problem. I think that for each given list (second column), the order of machines along the production line such that the manufacturing process of a car is done without interruptions, if such order exists, is a hash function. Sequence that I gave in the original post should be generated by some function, right?
     
  5. Jan 15, 2017 #4

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    In what way can the order of a sequence be a function? A function of what? What are we hashing and what is the output?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Hashing problem
  1. OpAmp problem (Replies: 8)

  2. Problems with DFT (Replies: 2)

Loading...