How are we going to write a program which if fed the data gives the answer?
Any ideas for the algorithm? My approach: We have a graph here. We have vertices with indegree 0 and outdegree 1. - call it set A (start points) (m vertices) We have vertices with indegree 1 and outdegree 0. - call it set B (end points) (n vertices) The paths from set A to set B can be run on multiple processors (m x n paths possible). if no. of processors >= m x n then no. of steps will be maximum no. of elements in any path. In the above ques, m = 1 and n = 3. if no. of processors < m x n, then run a BFS on the graph and find the number of vertices at each level. In the above question, the vertices at levels are 1, 1, 3 , 1. ((Max of these i.e. 3) / number of processors) + maximum no. of elements in any path = would be the answer. Now this part would have a problem if m!=1; Another problem would be how to find the maximum no. of elements in any path possible. On Sep 25, 9:03 am, sivaviknesh s <sivavikne...@gmail.com> wrote: > A parallel program consists of 8 tasks – T1 through T8. Each task requires > one time step to be executed on a single processor. Let X -> Y denote the > fact that task X must be executed before task Y is executed. Suppose only > the tasks X, Y are to be executed. On any multiprocessor machine it would > require at least 2 time steps since in the first step X could be executed, > and Y could be executed in the next time step (since it requires X to > complete first). Now, suppose the following dependencies exist between the > tasks T1 – T8: > > T1 -> T2 > > T2 -> T3 > > T3 -> T6 > > T2 -> T4 > > T4 -> T7 > > T2 -> T5 > > T5 -> T8 > > What is the minimum number of time steps required to execute these 8 tasks > on a 2 processor machine and a 4 processor machine? > > a)4 & 2 > > b)5 & 2 > > c)5 & 4 > > d)6 & 2 > > -- > Regards, > $iva -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
