1. Limited time only! Sign up for a free 30min personal 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!

Homework Help: Find the median of a set of sorted lists, Computer Science

  1. Feb 21, 2008 #1
    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[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 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)
    Last edited: Feb 21, 2008
  2. jcsd
  3. Feb 29, 2008 #2
    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 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?
    Last edited: Feb 29, 2008
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook