LCS Technical Memos (1974 - 2003): Recent submissions

Now showing items 82-84 of 486

    • On the Redundancy Achieved by Huffman Codes 

      De Prisco, Roberto; De Santis, Alfredo (1995-09)
      It has been recently proved that the redundancy r of any discrete memoryless source satisfies r < 1 -H(pn), where pn is the least likely source letter probability. This bound is achieved only by sources consisting of two ...

    • The Power of Team Exploration: Two Robots Can Learn Unlabeled Directed Graphs 

      Bender, Michael A.; Slonim, Donna K. (1995-09)
      We show that two cooperating robots can learn exactly any strongly-connected directed graph with n indistinguishable nodes in expected time polynomial in n. We introduce a new type of homing sequence for robots, which helps ...

    • Charge-Based Proportional Scheduling 

      Maheshwari, Umesh (1996-05)
      Most priority-based schedulers lack the ability to control the relative execution rates of applications. A recent scheme, called lottery scheduling [WW94], uses randomization to control the execution rates of threads in ...