- **Engineering, Comp Sci, & Technology Homework**
(*http://www.physicsforums.com/forumdisplay.php?f=158*)

- - **Find the median of a set of sorted lists, Computer Science**
(*http://www.physicsforums.com/showthread.php?t=216998*)

find the median of a set of sorted lists, Computer Science1. The problem statement, all variables and given/known dataGiven a set of sorted lists {X1, X2, ..., Xn} each Xi is in R^n , devise a divide and conquer algo that finds the median of X1[tex]\bigcup[/tex] X2 [tex]\bigcup[/tex] ... [tex]\bigcup[/tex] Xn efficiently. (n * log(n), n^2 is not acceptable, also no probabilistic, expected runtime) Also, Xi [tex]\bigcap[/tex] Xj = [tex]\phi[/tex] [tex]\forall[/tex] i, j s.t. i[tex]\neq[/tex]j 2. Relevant equationsalready know a procedure that finds the median of 2 equal sized, sorted lists in O(log(n)) time 3. The attempt at a solution- sort the lists by its median values, re-label them to be X1, X2..., Xn - divide the lists into L = {X1, ..., X[floor(n/2)]} and U = {X_ceil(n/2) ... , Xn} - find the med points of L, call it "ml", and the med point of U, call it "mu" - remove elements < ml from L, elements > mu from U, get new set of L', and U'. but at this point, the lists could be no equal in size, if we do a merge it could blow up the runtime, since merge is theta(n) |

X is list ; M is median ; r is # of elements less than M.
X1 : (M1,r1) X2 : (M2,r2) X3 : (M3,r3) .. Xn : (Mn,rn) ^ larger r's r r x x r x x xx x r x x x xx x x r xxx xxx xx x x x r xxx xxx xxxxxx x m_m_m_m_m_mm___m___> larger medians can you notice anything about that data? |

All times are GMT -5. The time now is 04:53 PM. |

Powered by vBulletin Copyright ©2000 - 2014, Jelsoft Enterprises Ltd.

© 2014 Physics Forums