LCS Technical Memos (1974 - 2003): Recent submissions

Now showing items 427-429 of 486

    • On the Worst-case Behavior of String-searching Algorithms 

      Rivest, Ronald L. (1976-04)
      Any algorithm for finding a pattern of length k in a string of length n must examine at least n-k+1 of the characters of the string in the worst case. By considering the pattern 00…0, we prove that this is the best possible ...

    • Automatic Design of Data Processing Systems 

      Ruth, Gregory R. (1976-02)
      The design of data organization and data accessing procedures for data processing systems operating on large keyed fields of data is a common and recurrent activity in modern data processing applications. A considerable ...

    • Improved Bounds on the Costs of Optimal and Balanced Binary Search Trees 

      Bayer, Paul J. (1975-11)
      A binary search tree can be used to store data in a computer system for retrieval by name. Different elements in the tree may be referenced with different probabilities. If we define the cost of the tree as the average ...