Tom Fotherby's Blog

Microsoft released a software update that expands the number of video formats that the XBox will play. This is quite exciting for me because I usually have to watch anything I download on my unimpressive 15″ computer monitor but now I can stick it on a USB key and watch it on my TV from the comfort of my sofa (which actually isn’t comfortable at all!).

Even better than a USB key, we found out how to stream video from Ubuntu Gutsy. The protocol that the Xbox uses to communicate with Windows Media Center PC’s is UPnP. To run your own UPnp server on Ubuntu 7.10 you need to install “ushare” (open source streaming software developed for the “GeexBox” Linux distribution):

1. sudo emacs /etc/apt/sources.list
• add “deb http://www.geexbox.org/debian/ unstable main”
2. sudo apt-get update;sudo apt-get install ushare
3. ushare -n Arbitary_UPnp_Server_Name -c pathToTargetMediaDir -x -i eth0

To get to the media in the XBox dashboard, you go to the “Media” tab, select “Videos”, then you should see “uShare” listed amongst the sources list. As a reference, the uShare version is currently 1.1 and the XBox dashboard version is 2.0.6683.0. Note: For some reason .avi files don’t show unless you rename them to .mov.

I would say thank you to Microsoft for this update except this isn’t really a fix, it’s more of an uncrippling. Why did they cripple it so it can’t play xVid in the first place? They must have been hoping people would just use WMV format videos but they must have received enough feedback to tell them that this isn’t the case.

Here are three C++ programs to find the median of a set of numbers. The first is short and simple. The last is fiddly and fast.

Simple but not linear (n*log n time):

Sort using STL sort (presumably quicksort), then find the middle value:

#include 
#include 

int main() {
  int A[7] = {23, 1, 33, -20, 6, 6, 9};
  std::sort(A,A+7);
  std::cout << "The medium is: " << A[3] << std::endl;
}

Linear time (But too much memory used in recursion):

The running time of the following algorithm is linear rather than logarithmic. The reasoning behind this is that each recursive call takes linear time (on average), and each recursive call reduces the size of the problem by a constant factor:

#include 
#include 
using namespace std;

// Find Kth element using recursion
int getKElem(vector A,int K) {
  int a = *A.begin();  // Pick randomly a number a from A = {a1, ..., an}.

  // gather all numbers smaller, equal and bigger than a.
  vector S, E, B;
  for(vector::const_iterator ci = A.begin(); ci!=A.end(); ci++) {
    if (*ci < a)      S.push_back(*ci);
    else if (*ci > a) B.push_back(*ci);
    else              E.push_back(*ci);
  }

  if (S.size() >= K) return getKElem(S,K);
  else if (S.size()+E.size() >= K) return a;
  else return getKElem(B,K-S.size()-E.size());
}

int main() {
  int myints[7] = {23, 1, 33, -20, 6, 6, 9};
  vector A (myints, myints + sizeof(myints) / sizeof(int) );

  cout << "Element " << A.size()/2 << " is: " << getKElem(A,A.size()/2) << endl;
}

Linear time with decent memory footprint:

Here is the algorithm with the recursion unraveled:

#include 
#include 
using namespace std;

// Find Kth element without recusion
int findKMedian(vector A,int K) {
  int l,m;
  l=0;
  m=A.size()-1;
  while (l A (myints, myints + sizeof(myints) / sizeof(int) );

  cout << "Element " << A.size()/2 << " is: " << findKMedian(A,A.size()/2) << endl;
}