A critical set in a Latin square of order n is a set of entries in an n×n array which can be embedded in precisely one Latin square of order n, with the property that if any entry of the critical set is deleted, the remaining set can be embedded in more than one Latin square of order n. The number of critical sets grows super-exponentially as the order of the Latin square increases. It is difficult to find patterns in Latin squares of small order (order 5 or less) which can be generalised in the process of creating new theorems. Thus, I have written many algorithms to find critical sets with various properties in Latin squares of order greater than 5, and to deal with other related structures. Some algorithms used in the body of the thesis are presented in Chapter 3; results which arise from the computational studies and observations of the patterns and subsequent results are presented in Chapters 4, 5, 6, 7 and 8. The cardinality of the largest critical set in any Latin square of order n is denoted by lcs(n). In 1978 Curran and van Rees proved that lcs(n)<=n²-n. In Chapter 4, it is shown that lcs(n)<=n²-3n+3. Chapter 5 provides new bounds on the maximum number of intercalates in Latin squares of orders m×2^α (m odd, α>=2) and m×2^α+1 (m odd, α>=2 and α≠3), and a new lower bound on lcs(4m). It also discusses critical sets in intercalate-rich Latin squares of orders 11 and 14. In Chapter 6 a construction is given which verifies the existence of a critical set of size n²÷ 4 + 1 when n is even and n>=6. The construction is based on the discovery of a critical set of size 17 for a Latin square of order 8. In Chapter 7 the representation of Steiner trades of volume less than or equal to nine is examined. Computational results are used to identify those trades for which the associated partial Latin square can be decomposed into six disjoint Latin interchanges. Chapter 8 focusses on critical sets in Latin squares of order at most six and extensive computational routines are used to identify all the critical sets of different sizes in these Latin squares.

A critical set in a Latin square of order n is a set of entries in an n×n array which can be embedded in precisely one Latin square of order n, with the property that if any entry of the critical set is deleted, the remaining set can be embedded in more than one Latin square of order n. The number of critical sets grows super-exponentially as the order of the Latin square increases. It is difficult to find patterns in Latin squares of small order (order 5 or less) which can be generalised in the process of creating new theorems. Thus, I have written many algorithms to find critical sets with various properties in Latin squares of order greater than 5, and to deal with other related structures. Some algorithms used in the body of the thesis are presented in Chapter 3; results which arise from the computational studies and observations of the patterns and subsequent results are presented in Chapters 4, 5, 6, 7 and 8. The cardinality of the largest critical set in any Latin square of order n is denoted by lcs(n). In 1978 Curran and van Rees proved that lcs(n)<=n²-n. In Chapter 4, it is shown that lcs(n)<=n²-3n+3. Chapter 5 provides new bounds on the maximum number of intercalates in Latin squares of orders m×2^α (m odd, α>=2) and m×2^α+1 (m odd, α>=2 and α≠3), and a new lower bound on lcs(4m). It also discusses critical sets in intercalate-rich Latin squares of orders 11 and 14. In Chapter 6 a construction is given which verifies the existence of a critical set of size n²÷ 4 + 1 when n is even and n>=6. The construction is based on the discovery of a critical set of size 17 for a Latin square of order 8. In Chapter 7 the representation of Steiner trades of volume less than or equal to nine is examined. Computational results are used to identify those trades for which the associated partial Latin square can be decomposed into six disjoint Latin interchanges. Chapter 8 focusses on critical sets in Latin squares of order at most six and extensive computational routines are used to identify all the critical sets of different sizes in these Latin squares.

A critical set in a Latin square of order n is a set of entries in an n×n array which can be embedded in precisely one Latin square of order n, with the property that if any entry of the critical set is deleted, the remaining set can be embedded in more than one Latin square of order n. The number of critical sets grows super-exponentially as the order of the Latin square increases. It is difficult to find patterns in Latin squares of small order (order 5 or less) which can be generalised in the process of creating new theorems. Thus, I have written many algorithms to find critical sets with various properties in Latin squares of order greater than 5, and to deal with other related structures. Some algorithms used in the body of the thesis are presented in Chapter 3; results which arise from the computational studies and observations of the patterns and subsequent results are presented in Chapters 4, 5, 6, 7 and 8. The cardinality of the largest critical set in any Latin square of order n is denoted by lcs(n). In 1978 Curran and van Rees proved that lcs(n)<=n²-n. In Chapter 4, it is shown that lcs(n)<=n²-3n+3. Chapter 5 provides new bounds on the maximum number of intercalates in Latin squares of orders m×2^α (m odd, α>=2) and m×2^α+1 (m odd, α>=2 and α≠3), and a new lower bound on lcs(4m). It also discusses critical sets in intercalate-rich Latin squares of orders 11 and 14. In Chapter 6 a construction is given which verifies the existence of a critical set of size n²÷ 4 + 1 when n is even and n>=6. The construction is based on the discovery of a critical set of size 17 for a Latin square of order 8. In Chapter 7 the representation of Steiner trades of volume less than or equal to nine is examined. Computational results are used to identify those trades for which the associated partial Latin square can be decomposed into six disjoint Latin interchanges. Chapter 8 focusses on critical sets in Latin squares of order at most six and extensive computational routines are used to identify all the critical sets of different sizes in these Latin squares.

Made available in DSpace on 2014-06-11T19:24:52Z (GMT). No. of bitstreams: 0 Previous issue date: 2010-02-24Bitstream added on 2014-06-13T20:52:44Z : No. of bitstreams: 1 souza_acp_me_rcla.pdf: 6507132 bytes, checksum: a4ba6e1c2a6b5b1061118d1485c4e613 (MD5) / See-Sp / Esta pesquisa tem como objetivo trabalhar a Análise Combinatória, fazendo uso da Metodologia de Ensino-Aprendizagem-Avaliação de Matemática através da Resolução de Problemas. Abordamos, em nossa fundamentação teórica, a Análise Combinatória contida na Matemática Discreta, iniciando a pesquisa com uma introdução histórica da Análise Combinatória, seguida por uma análise de livros didáticos e pela busca de trabalhos de outros autores que se referiam ao ensino e à aprendizagem desse conteúdo. Criamos três projetos para trabalhar com a metodologia de ensino adotada por nós, em três cenários diferentes, onde a pesquisadora assumiu três posturas diferentes frente ao problema da pesquisa: como uma professora-pesquisadora, com seus próprios alunos, em sua sala de aula; como uma pesquisadora, ministrando uma oficina de trabalho, em um encontro de Educação Matemática, tendo como participantes, professores, educadores matemáticos e até alunos da Licenciatura em Matemática; e, como uma pesquisadora, em Encontros em Educação Matemática, divulgando sua pesquisa. Através da análise dos dados, obtidos nas aplicações dos três projetos, pudemos mostrar como os participantes desses projetos se envolveram ao fazer uso da metodologia de ensino adotada e relatamos as contribuições que trouxeram para nossa pesquisa. Verificamos que houve envolvimento ativo dos participantes na construção de novos conceitos e conteúdos, através da resolução dos problemas propostos, por meio de um trabalho investigativo, que proporcionou uma aprendizagem com compreensão e significado, com resultados importantes para a prática docente. Esta pesquisa foi desenvolvida seguindo a Metodologia de Pesquisa apresentada por Thomas A. Romberg. / This paper has the objective to study the Combinatory Analysis using Methodology of Teaching-Learning-Assessment of Mathematics through Problem Solving. In our theoretical fundamentation we address the Combinatory Analysis contained in the Discrete Mathematics, starting the research with a historical introduction of the Combinatory Analysis followed by a review of textbooks and the search for other author’s articles concerning this content’s teaching and learning. We have developed three projects to apply the teaching methodology we adopted in three different settings, where the researcher played three distinct roles facing the research’s problem: a) as a teacher-researcher, with her own students in her own classroom; b) as a researcher, conducting a workshop in a Mathematical Education conference, with teachers, mathematics educators and graduate students; c) as a researcher, in Mathematics Education Conferences divulgating her research. By analyzing all the data obtained in the application of the three projects we could show how the participants were engaged in using the adopted teaching methodology and we also reported the contributions they have brought to our research. We could verify that there was significant involvement from all the participants in the construction of new concepts and contents by solving the proposed problems in an investigative way, providing a different learning, full of understanding and meaning, with very significant results in terms of teaching practice. This research was developed following the Research Methodology presented by Thomas A. Romberg.

[pt] Este trabalho surgiu da seguinte observação: os clássicos algoritmos de busca em 2d-tree começam da raiz para acessar dados armazenados nas folhas. Entretanto, como as folhas são os nós mais distantes da raiz, por que começar as buscas pela raiz? Com representações clássicas de 2d-trees, não existe outra forma de acessar uma folha. Existem 2d- trees, porém, que permitem acessar em tempo constante qualquer nó, dado sua posição e seu nível. Para o algoritmo de busca, a posição é conhecida, mas o nível não. Para estimar o nível de um nó qualquer, um método de otimização estatística do custo médio das buscas é proposto. Como os piores custos de busca são obtidos quando se começa da raiz, este método melhora ambos: o consumo de memória pelo uso de 2d-trees que permitem acessar em tempo constante qualquer nó, e o tempo de execução através da otimização proposta. / [en] This work emerged from the following observation: usual search procedures for 2d-trees start from the root to retrieve the data stored at the leaves. But since the leaves are the farthest nodes to the root, why start from the root? With usual 2d-trees representations, there is no other way to access a leaf. However, there exist 2d-trees which allow accessing any node in constant time, given its position in space and its depth in the 2d-tree. Search procedures take the position as an input, but the depth remains unknown. To estimate the depth of an arbitrary node a statistical optimization of the average cost for the search procedures is introduced. Since the highest costs of these algorithms are obtained when starting from the root, this method improves on both, the memory footprint by the use of 2d-trees which allow accessing any node in constant time, and execution time through the proposed optimization.

This thesis is concerned with studying the behavior of a gossiping protocol in the specific sense meant by Ericsson; in the following pages I’ll introduce a Markov process which models the spread of information in such systems. The results will be verified by means of a discreet-event simulation. / Gossiping Protocols, are inherently random in behavior.Nonetheless, they are not structure-less. Their asymptotic behavior when implemented in large scales is the matter of focus in this thesis. / Tel: +46709700505 Address: Pinnharvsgatan 3 E lgh 1202 43147 Mölndal Sweden

Accurate and reliable effort estimation is still one of the most challenging processes in software engineering. There have been numbers of attempts to develop cost estimation models. However, the evaluation of model accuracy and reliability of those models have gained interest in the last decade. A model can be finely tuned according to specific data, but the issue remains there is the selection of the most appropriate model. A model predictive accuracy is determined by the difference of the various accuracy measures. The one with minimum relative error is considered to be the best fit. The model predictive accuracy is needed to be statistically significant in order to be the best fit. This practice evolved into model evaluation. Models predictive accuracy indicators need to be statistically tested before taking a decision to use a model for estimation. The aim of this thesis is to statistically evaluate well known effort estimation models according to their predictive accuracy indicators using two new approaches; bootstrap confidence intervals and permutation tests. In this thesis, the significance of the difference between various accuracy indicators were empirically tested on the projects obtained from the International Software Benchmarking Standard Group (ISBSG) data set. We selected projects of Un-Adjusted Function Points (UFP) of quality A. Then, the techniques; Analysis Of Variance ANOVA and regression to form Least Square (LS) set and Estimation by Analogy (EbA) set were used. Step wise ANOVA was used to form parametric model. K-NN algorithm was employed in order to obtain analogue projects for effort estimation use in EbA. It was found that the estimation reliability increased with the pre-processing of the data statistically, moreover the significance of the accuracy indicators were not only tested statistically but also with the help of more complex inferential statistical methods. The decision of selecting non-parametric methodology (EbA) for generating project estimates in not by chance but statistically proved.

The problem addressed in this thesis was identified in a real life context in which an attempt was made to re-constitute a BSc Computer Science degree programme. The curriculum was modelled on the ACM/IEEE Computing Curriculum of 2001. It was further required to comply with accreditation requirements as defined by ABET’s Computing Accreditation Commission. Relying on a spreadsheet, the curriculum was iteratively and manually evaluated against the ACM/IEEE curriculum specification. A need was identified to automate or at least semi-automate this process. In this thesis a generalisation of the problem is presented. Curricula are modelled as directed graphs (digraphs) in which graph vertices represent curriculum elements such as topics, knowledge areas, knowledge units year- levels or modules. Edges in the graph represent dependencies between these vertices such as belonging to grouping or pre-requisites. The task of curriculum comparison then abstracts to a task of digraph comparison. A framework, the Graph Comparison Framework, is proposed. The frame- work comprises of components which are used to guide the digraph comparison process. The so-called Graph Trans-morphism algorithm component is the only component in the framework which is mandatory. The algorithm converts the information from one of the digraphs being compared into the structure of the other. This conversion enables the graphs to be compared as graph isomorphisms. All digraphs are modelled as sets of triples, making it possible to subtract one digraph from another using the set minus operator. The resultant difference sets are used by components defined in the framework to quantify and visualise the differences. By modelling curricula as digraphs and applying the framework to the di-graphs, it is possible to compare curricula. This application of the framework to a real-world problem forms the applications research part of the thesis. In this part, domain knowledge of curriculum design is necessary to apply to the curriculum being developed in order to improve it. / Thesis (PhD)--University of Pretoria, 2014. / Computer Science / unrestricted

This thesis describes methods of secret communication based on latin squares and their close relative, quasigroups. Different types of cryptosystems are described, including ciphers, public-key cryptosystems, and cryptographic hash functions. There is also a chapter devoted to different secret sharing schemes based on latin squares. The primary objective is to present previously described cryptosystems and secret sharing schemes in a more accessible manner, but this text also defines two new ciphers based on isotopic latin squares and reconstructs a lost proof related to row-latin squares. / Denna uppsats beskriver kryptosystem och metoder för hemlighetsdelning baserade på latinska kvadrater och det närliggande konceptet kvasigrupper. Olika sorters chiffer, både symmetriska och asymmetriska, behandlas. Dessutom finns ett kapitel tillägnat kryptografiska hashfunktioner och ett tillägnat metoder för hemlighetsdelning. Huvudsyftet är att beskriva redan existerande metoder för hemlig kommunikation på ett mer lättillgängligt sätt och med nya exempel, men dessutom återskapas ett, till synes, förlorat bevis relaterat till rad-latinska kvadrater samt beskrivs två nya chiffer baserade på isotopa latinska kvadrater.

An area in graph theory is graph colouring, which essentially is a labeling of the vertices or edges according to certain constraints. In this thesis we consider star edge colouring, which is a variant of proper edge colouring where we additionally require the graph to have no two-coloured paths or cycles with length 4. The smallest number of colours needed to colour a graph G with a star edge colouring is called the star chromatic index of G and is denoted <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Cchi'_%7Bst%7D(G)" />. This paper proves an upper bound of the star chromatic index of bipartite graphs in terms of the maximum degree; the maximum degree of G is the largest number of edges incident to a single vertex in G. For bipartite graphs Bk with maximum degree <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?k%5Cgeq1" />, the star chromatic index is proven to satisfy<img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%20%5Cchi'_%7Bst%7D(B_k)%20%5Cleq%20k%5E2%20-%20k%20+%201" />. For bipartite graphs <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?B_%7Bk,n%7D" />, where all vertices in one part have degree n, and all vertices in the other part have degree k, it is proven that the star chromatic index satisfies <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Cchi'_%7Bst%7D(Bk,n)%20%5Cleq%20k%5E2%20-2k%20+%20n%20+%201,%20k%20%5Cgeq%20n%20%3E%201" />. We also prove an upper bound for a special case of multipartite graphs, namely <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?K_%7Bn,1,1,%5Cdots,1%7D" /> with m parts of size one. The star chromatic index of such a graph satisfies<img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Cchi'_%7Bst%7D(K_%7Bn,1,1,%5Cdots,1%7D)%20%5Cleq%2015%5Clceil%5Cfrac%7Bn%7D%7B8%7D%5Crceil%5Ccdot%5Clceil%5Cfrac%7Bm%7D%7B8%7D%5Crceil%20+%20%5Cfrac%7B1%7D%7B2%7Dm(m-1),%5C,m%20%5Cgeq%205" />. For complete multipartite graphs where m &lt; 5, we prove lower upper bounds than the one above.