^April May – 2007 ^June

In the last decade range division scheduling policies have been proposed to overcome the large waiting times which are experienced in multi-server systems with heavy-tailed job size distributions. we analyze the effectivness of such scheduling policies, joint work with Hagit Sarfati.

mRNA molecules are folded in the cells and therefore many of their substrings may actually be inaccessible to protein and microRNA binding. The need to apply an accessability criterion to the task of genome-wide mRNA motif discovery raises the challenge of overcoming the core $O(n^3)$ factor imposed by the time complexity of the currently best known algorithms for RNA secondary structure prediction [Zuker et al., Nussinov et al.].

We speed up the dynamic programming algorithms that are standard for RNA folding prediction. Our new approach significantly reduces the computations without sacrificing the optimality of the results, yielding an expected time complexity of $O(n^2 \psi(n))$, where $\psi(n)$ is shown to be constant on average under standard polymer folding models. Benchmark analysis confirms that in practice the runtime ratio between the previous approach and the new algorithm indeed grows linearly with increasing sequence size.

The fast new RNA folding algorithm is utilized for genome-wide discovery of accessible cis-regulatory motifs in data sets of ribosomal densities and decay rates of S. cerevisiae genes and to the mining of exposed binding sites of tissue-specific microRNAs in A. Thaliana. This paper, joint work with Ydo Wexler and Chaya Zilberstein, has received the RECOMB2006 Special Mention Award.

We consider a new question regarding random walks on graphs: How long does it take for several independent random walks, starting from the same location, to cover an entire graph? We study the cover time, the expected time required to visit every node in a graph at least once, and we show that for a large collection of interesting graphs, running many random walks in parallel yields a speed-up in the cover time that is linear in the number of the parallel walks. We demonstrate that an exponential speed-up is sometimes possible, but that some natural graphs allow only a logarithmic speed-up.

We present and discuss the problem placing a sequence of disjoint rectangles on a larger rectangle. In the formal definition of the problem, the inputs are the integral dimensions of (the larger) rectangle , and a sequence of natural numbers, . The output is a sequence of rectangles, placed in a disjoint fashion on such that the area of is smaller than or equal to . Our goal is to place a maximal length prefix of . In this talk, we briefly motivate the problem, than we show the problem is hard. The main part of the talk is devoted to an approximation algorithm whose output satisfies: The area covered by all placed rectangles divided by the area covered by all rectangles in an optimal placement lies within a factor of This approximation ratio is achieved under the assumption that for each , , where . The complexity of the algorithm is linear. This is a joint work with Dror Rawitz and Oran Sharon.

This lecture summarizes the work done by the industrial partners in the MODELWARE project to measure the return on investment due to the adoption of a model driven development (MDD) strategy. The industrial partners in the project were France Telecom, Thales Air Traffic Management, Western Geco, WM-Data, and Enabler. Each of the industrial partners was teamed with one or two academic partners to assist in the creation and customization of MDD processes and tools appropriate to the industrial partner, taking into account their application domain, size of the company, software process maturity, and level of sophistication.

Each team carried out a series of experiments in order to measure the improvement in productivity. A baseline was established at the beginning of the project, and subsequently measurements were made using the MDD tools and processes. Different experiments focussed on different phases in the software lifecycle.

It was found that MDD provides little or no improvement in productivity in the initial phases of development, but significant gains of 20-60% were observed in the execution of maintenance tasks.