<p> This investigation examines several methods designed to minimize the computational cost of retrieving records from a binary search tree.</p> <p> No knowledge of the probabilities with which these records are requested is assumed. The aim of each method is to gradually restructure an initial, arbitrary (and perhaps costly) tree into one which has minimal search cost, on the basis of experience.</p> <p> While no one such 'self-organizing' method has yet received theoretical substantiation, it is hoped that this empirial investigation may assist in this endeavour.</p> / Thesis / Master of Science (MSc)

No description available.

Student Number : 9708525G - PhD thesis - School of Mathematics - Faculty of Science / Sequences of numbers have important applications in the field of Computer Science. As a result they have become increasingly regarded in Mathematics, since analysis can be instrumental in investigating algorithms. Three concepts are discussed in this thesis, all of which are concerned with ‘words’ or ‘sequences’ of natural numbers where repeated letters are allowed: • The number of distinct values in a sequence with geometric distri- bution In Part I, a sample which is geometrically distributed is considered, with the objective of counting how many different letters occur at least once in the sample. It is concluded that the number of distinct letters grows like log n as n → ∞. This is then generalised to the question of how many letters occur at least b times in a word. • The position of the maximum (and/or minimum) in a sequence with geometric distribution Part II involves many variations on the central theme which addresses the question: “What is the probability that the maximum in a geometrically distributed sample occurs in the first d letters of a word of length n?” (assuming d ≤ n). Initially, d is considered fixed, but in later chapters d is allowed to grow with n. It is found that for 1 ≤ d = o(n), the results are the same as when d is fixed. • The average depth of a key in a binary search tree formed from a sequence with repeated entries Lastly, in Part III, random sequences are examined where repeated letters are allowed. First, the average left-going depth of the first one is found, and later the right-going path to the first r if the alphabet is {1, . . . , r} is examined. The final chapter uses a merge (or ‘shuffle’) operator to obtain the average depth of an arbitrary node, which can be expressed in terms of the left-going and right-going depths.

<p>Our main results are that splay trees are faster for sorted insertion, where AVL trees are faster for random insertion. For searching, skip lists are faster than single class top-down splay trees, but two-class and multi-class top-down splay trees can behave better than skip lists.</p>

No description available.

<p>Our main results are that splay trees are faster for sorted insertion, where AVL trees are faster for random insertion. For searching, skip lists are faster than single class top-down splay trees, but two-class and multi-class top-down splay trees can behave better than skip lists.</p>

Magister Scientiae - MSc / Our main results are that splay trees are faster for sorted insertion, where AVL trees are faster for random insertion. For searching, skip lists are faster than single class top-down splay trees, but two-class and multi-class top-down splay trees can behave better than skip lists. / South Africa

One of the important tasks during software testing is the generation of appropriate test data. Various techniques have been proposed to automate this task. The techniques available, however, often have problems limiting their use. In the case of dynamic test data generation techniques, a frequent problem is that a large number of iterations might be necessary to obtain test data. This article proposes a novel technique for automated test data generation based on binary search. Binary search conducts searching tasks in logarithmic time, as long as its assumptions are fulfilled. This article shows that these assumptions can also be fulfilled in the case of path-oriented test data generation and presents a technique which can be used to generate test data covering certain paths in class methods.

O processo de análise química denominado de titulação por procura binária foi desenvolvido e aplicado em sistema de injeção em fluxo. Este procedimento de análise, baseado no método das variações contínuas, procura o menor intervalo em fração volumétrica do titulante, ou da solução da amostra, que contenha o ponto final de uma titulação. Ao ser introduzida alíquota da solução da amostra no percurso analítico, o sinal gerado pelo detector deve ser significativamente diferente daquele gerado com a inserção de uma alíquota da solução do titulante. Neste processo descontínuo, a procura do ponto final segue a lógica binária, reduzindo os incrementos de fração volumétrica, da solução de amostra ou do titulante, em 50%, a cada nova tentativa de procura. Os sinais gerados por um detector espectrofotométrico, acoplado ao sistema de fluxo, eram convertidos em sinais digitais e comparados com os sinais fornecidos pelo detector nas duas tentativas iniciais da procura. Um programa foi desenvolvido para gerenciar este procedimento de titulação, determinando o volume das alíquotas das soluções, para cada tentativa, bem como estabelecendo a rota de procura. O procedimento foi aplicado à uma série de titulações envolvendo reações de neutralização e complexação. Uma titulação, aplicando este procedimento, pode ser executada em 3 minutos, consumindo aproximadamente 2 cm3 das soluções reagentes. As limitações para a aplicação deste procedimento de análise são discutidas, bem como a inviabilidade de sua aplicação sem o emprego de recursos de automatização. / A flow injection analytical procedure named as binary search titrimetric process was studied. It was based on volumetric fraction variation methodology. Under its directive, the microcomputer can control the titrand and titrant solutions delevering into the analytical path, by varying both volumetric fractions, following an algorithm based on successive aproximation method. Analytical signals assessed from the analog output of the spectrophotometer for each tentatives were converted to digital making use of an interface card, attached in the microcomputer main board. After each solutions handling cycles, the data collected were processed in order to decide about the next tentative to be carried out, obeying the settled binary search algorithm. The feasibility was ascertained by titrating solutions employing neutralization and complexation reactions. The time interval to perform this titration process employing binary search concept was about 3 minutes, consuming ca 2 cm3 of reagents solutions. No significant difference at 5 % probability level was observed by comparing of the results obtained applying this procedure with those produced by manual procedures.

O processo de análise química denominado de titulação por procura binária foi desenvolvido e aplicado em sistema de injeção em fluxo. Este procedimento de análise, baseado no método das variações contínuas, procura o menor intervalo em fração volumétrica do titulante, ou da solução da amostra, que contenha o ponto final de uma titulação. Ao ser introduzida alíquota da solução da amostra no percurso analítico, o sinal gerado pelo detector deve ser significativamente diferente daquele gerado com a inserção de uma alíquota da solução do titulante. Neste processo descontínuo, a procura do ponto final segue a lógica binária, reduzindo os incrementos de fração volumétrica, da solução de amostra ou do titulante, em 50%, a cada nova tentativa de procura. Os sinais gerados por um detector espectrofotométrico, acoplado ao sistema de fluxo, eram convertidos em sinais digitais e comparados com os sinais fornecidos pelo detector nas duas tentativas iniciais da procura. Um programa foi desenvolvido para gerenciar este procedimento de titulação, determinando o volume das alíquotas das soluções, para cada tentativa, bem como estabelecendo a rota de procura. O procedimento foi aplicado à uma série de titulações envolvendo reações de neutralização e complexação. Uma titulação, aplicando este procedimento, pode ser executada em 3 minutos, consumindo aproximadamente 2 cm3 das soluções reagentes. As limitações para a aplicação deste procedimento de análise são discutidas, bem como a inviabilidade de sua aplicação sem o emprego de recursos de automatização. / A flow injection analytical procedure named as binary search titrimetric process was studied. It was based on volumetric fraction variation methodology. Under its directive, the microcomputer can control the titrand and titrant solutions delevering into the analytical path, by varying both volumetric fractions, following an algorithm based on successive aproximation method. Analytical signals assessed from the analog output of the spectrophotometer for each tentatives were converted to digital making use of an interface card, attached in the microcomputer main board. After each solutions handling cycles, the data collected were processed in order to decide about the next tentative to be carried out, obeying the settled binary search algorithm. The feasibility was ascertained by titrating solutions employing neutralization and complexation reactions. The time interval to perform this titration process employing binary search concept was about 3 minutes, consuming ca 2 cm3 of reagents solutions. No significant difference at 5 % probability level was observed by comparing of the results obtained applying this procedure with those produced by manual procedures.