Find ii-th number in unsorted sequence in logspace (deterministic turing machine)

There is given input – words is sequence of numbers: wi is number
in sequence, i is position. All of them are in written in binary
system.

w1#,...#wk#i Prove that there exists deterministic
Turing machine which find i-th number in sorted sequence w in
logspace.

I am not sure if I correctly solved it, so I ask for checking my reasoning. It seems to be fairly simple.

First of all, what we can do in logspace:
compare two numbers
iter over sequence (move to n-th number)

Simply, we consider one by one each element of sequence and count how many elements is less than currently considered. If we count i1 numbers, then we stop. It requires logarythmic(k) memory for counter. These counter can be reused (for each iteration).

Waht do you think ? Maybe some other approach to proving it ?

Answer

First let’s consider the case when numbers are unique. The idea is that for each element wt we count the number of elements in the sequence which are less than wt. After each loop on all elements of the sequence we check if there are i1 elements less than wt then wt must be i-th element in the sorted sequence, so we halt with the output equal to wt.

proc(w, k, i)
 for t=0 to k
   counter = 0
   for j=0 to k
     if w[t] > w[j]
      counter = counter + 1
   if counter == i-1 then output w[t] and halt 
end-proc  

Now, if numbers are not unique then we have to count duplicates as well

proc(w, k, i)
 for t=0 to k
   counter = 0
   dups = 0
   for j=0 to k
    skip if j == t
    if w[t] == w[j]
      dups = dups + 1
   for j=0 to k
     if w[t] > w[j]
       counter = counter + 1
   if counter+1 <= i AND i <= counter + dups+1 
     then output w[t] and halt 
end-proc 

  w[1] w[2] ... w[counter] w[t] w[t] ... w[t] ..
  \__________  __________/     \_____  ____/    
             \/                      \/
 all elements less than w[t]   duplicates        

Both procedures require only constant number of variables i, j, k, counter, and dups whose lengths are O(log(k)). Your solution is similar to these algorithms so your approach is correct.

Attribution
Source : Link , Question Author : Haskell Fun , Answer Author : fade2black

Leave a Comment