Physics Forums (http://www.physicsforums.com/index.php)
-   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)

 chy1013m1 Feb21-08 01:05 PM

find the median of a set of sorted lists, Computer Science

1. The problem statement, all variables and given/known data
Given 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$$\bigcup$$ X2 $$\bigcup$$ ... $$\bigcup$$ Xn efficiently.
(n * log(n), n^2 is not acceptable, also no probabilistic, expected runtime)
Also, Xi $$\bigcap$$ Xj = $$\phi$$ $$\forall$$ i, j s.t. i$$\neq$$j

2. Relevant equations
already 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)

 basePARTICLE Feb29-08 07:10 PM

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 02:22 PM.