To determine the function of a protein, we must know its 3-dimensional structure, which can be difficult to ascertain. Currently, predictive models are used to determine the structure of a protein from its sequence, but these models do not always predict the correct structure. To this end we use a nested graph model along with weighted invariants to minimize the errors and improve the accuracy of a predictive model to determine if we have the correct structure for a protein.

A graph is an ordered pair composed by a set of vertices and a set of edges, the latter consisting of unordered pairs of vertices. Two vertices in such a pair are each others neighbors. Two edges are adjacent if they share a common vertex. Denote the amount of edges that share a specific vertex as the degree of the vertex. A proper edge-coloring of a graph is an assignment of colors from some finite set, to the edges of a graph where no two adjacent edges have the same color. A bipartition (X,Y) of a set of vertices V is an ordered pair of two disjoint sets of vertices such that V is the union of X and Y, where all the vertices in X only have neighbors in Y and vice versa. A bipartite graph is a graph whose vertices admit a bipartition (X,Y). Let G be one such graph. An X-interval coloring of G is a proper edge coloring where the colors of the edges incident to each vertex in X form an interval of integers. Denote by χ'int(G,X) the least number of colors needed for an X-interval coloring of G. In this paper we prove that if G is a bipartite graph with maximum degree 3n (n is a natural number), where all the vertices in X have degree 3, then <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Cmathit%7B%5Cchi'_%7Bint%7D%5Cleft(G,X%5Cright)%5Cleq%7D%0A%5C%5C%0A%5Cmathit%7B%5Cleft(n-1%5Cright)%5Cleft(3n+5%5Cright)/2+3%7D%0A%5C%5C%0A%5Cmathit%7Bif%20n%20is%20odd,%7D%0A%5C%5C%0A%5Cmathit%7Bor%7D%0A%5C%5C%0A%5Cmathbf%7B3n%5E%7B2%7D/2+1%7D%0A%5C%5C%0A%5Cmathit%7Bif%20n%20is%20even%7D.%0A" />

This thesis examines the problem of counting and describing walks in graphs, and the problem when such walks have modular restrictions on how many timesit visits each vertex. For the special cases of the path graph, the cycle graph, the grid graph and the cylinder graph, generating functions and regular languages for their walks and walks with modular restrictions are constructed. At the end of the thesis, a theorem is proved that connects the generating function for walks in a graph to the generating function for walks in a covering graph.

<div>We consider the maximum vertex-weighted matching problem (MVM), in which non-negative weights are assigned to the vertices of a graph, and the weight of a matching is the sum of the weights of the matched vertices. Vertex-weighted matchings arise in many applications, including internet advertising, facility scheduling, constraint satisfaction, the design of network switches, and computation of sparse bases for the null space or the column space of a matrix. Let m be the number of edges, n number of vertices, and D the maximum degree of a vertex in the graph. We design two exact algorithms for the MVM problem with time complexities of O(mn) and O(Dmn). The new exact algorithms use a maximum cardinality matching as an initial matching, after which the weight of the matching is increased using weight-increasing paths.</div><div><br></div><div>Although MVM problems can be solved exactly in polynomial time, exact MVM algorithms are still slow in practice for large graphs with millions and even billions of edges. Hence we investigate several approximation algorithms for MVM in this thesis. First we show that a maximum vertex-weighted matching can be approximated within an approximation ratio arbitrarily close to one, to k/(k + 1), where k is related to the length of augmenting or weight-increasing paths searched by the algorithm. We identify two main approaches for designing approximation algorithms for MVM. The first approach is direct; vertices are sorted in non-increasing order of weights, and then the algorithm searches for augmenting paths of restricted length that reach a heaviest vertex. (In this approach each vertex is processed once). The second approach repeatedly searches for augmenting paths and increasing paths, again of restricted length, until none can be found. In this second, iterative approach, a vertex may need to be processed multiple times. We design two approximation algorithms based on the direct approach with approximation ratios of 1/2 and 2/3. The time complexities of the 1/2-approximation algorithm is O(m + n log n), and that of the 2/3-approximation algorithm is O(mlogD). Employing the second approach, we design 1/2- and 2/3-approximation algorithms for MVM with time complexities of O(Dm) and O(D²m), respectively. We show that the iterative algorithm can be generalized to nd a k/(k+1)-approximate MVM with a time complexity of O(D^km). In addition, we design parallel 1/2- and 2/3-approximation algorithms for a shared memory programming model, and introduce a new technique for locking augmenting paths to avoid deadlock and related problems. </div><div><br></div><div>MVM problems may be solved using algorithms for the maximum edge-weighted matching (MEM) by assigning to each edge a weight equal to the sum of the vertex weights on its endpoints. However, our results will show that this is one way to generate MEM problems that are difficult to solve. On such problems, exact MEM algorithms may require run times that are a factor of a thousand or more larger than the time of an exact MVM algorithm. Our results show the competitiveness of the new exact algorithms by demonstrating that they outperform MEM exact algorithms. Specifically, our fastest exact algorithm runs faster than the fastest MEM implementation by a factor of 37 and 18 on geometric mean, using two different sets of weights on our test problems. In some instances, the factor can be higher than 500. Moreover, extensive experimental results show that the MVM approximation algorithm outperforms an MEM approximation algorithm with the same approximation ratio, with respect to matching weight and run time. Indeed, our results show that the MVM approximation algorithm outperforms the corresponding MEM algorithm with respect to these metrics in both serial and parallel settings.</div>

Vid beräkning i addition krävs kunskap att tolka siffrors positioner och värden i tal. Kunskaper om det decimala talsystemets struktur och platsvärde är grundläggande för att kunna göra beräkningar i addition. Syftet med denna litteraturstudie var att genomföra en litteraturöversikt om hur platsvärdet förhåller sig till addition och hur undervisning kan bedrivas om det decimala talsystemet. Litteratursökningen som gjordes genererade i artiklar som mestadels undersökte elever i de lägre åldrarna. Resultatet i litteraturöversikten baserades på tio artiklar som har analyserats av skribenterna. Resultatet visade att det fanns ett förhållande mellan platsvärde och förmågan att beräkna addition. Elever i denna litteraturstudie har visat svårigheter med att förstå platsvärde i det decimala talsystemet. Svårigheterna gick att förebygga genom varierade undervisningssekvenser som belyste olika aspekter av det decimala talsystemet. Undervisningsformer med tavla och konkret material visade sig vara de mest förekommande metoderna. Slutsatsen från skribenterna blev att undervisningsformen i sig inte är avgörande för att förstå det decimala talsystemet. Det matematiska innehållet och hur det förmedlas av läraren är betydande för hur eleverna lär sig platsvärde i det decimala talsystemet.

We have found an operation between permutations in the symmetric group Sn upon which we have experimentally derived results that can be linked to desirable properties in cryptography, mainly in the domain of one-way functions. From it, we have implemented a beta version of an algorithm for a hashing function by exploiting the operation’s low computational cost for speed and its properties for security. Its design makes it resistant to length extension attacks and the encoding of blocks into permutations suggests that any differential cryptanalysis technique that is based on bit conditions should be useless against it. More precisely, when measuring the evolution of differences in the compression function, bit-based distances such as the exclusive-or distance should be replaced by another type of distance, still to be determined in future research. In this work we will present the algorithm and introduce a new framework of cryptanalysis for collision and preimage attacks in order to somehow measure its security. Once this is done, we will run comparison tests against MD5 and SHA256 in order to externally evaluate our algorithm in terms of speed, weaknesses and strength.

Let $M_v$ denotes a complete mixed graph on $v$ vertices, and let $S_6^i$ denotes the partial orientation of the 6-star with twice as many arcs as edges. In this work, we state and prove the necessary and sufficient conditions for the existence of $\lambda$-fold decomposition of a complete mixed graph into $S_6^i$ for $i\in\{1,2,3,4\}$. We used the difference method for our proof in some cases. We also give some general sufficient conditions for the existence of $S_6^i$-decomposition of the complete bipartite mixed graph for $i\in\{1,2,3,4\}$. Finally, this work introduces the decomposition of a complete mixed graph with a hole into mixed stars.

The arcsine distribution looks at the fraction of time one player is winning in a fair coin toss game and has been studied for over a hundred years. There has been little further work on how the distribution changes when the coin tosses are not fair or when a player has already won the initial coin tosses or, equivalently, starts with a lead. This thesis will first cover a proof of the arcsine distribution. Then, we explore how the distribution changes when the coin the is unfair. Finally, we will explore the distribution when one person has won the first few flips.

A set of elements with a binary operation is called a system, or, more explicitly, a mathematical system. The following discussion will involve systems with only one operation. This operation will be denoted by "⋅" and will sometimes be referred to as a product. A system, S, of n elements (x1, x2, ..., xn) is associative if xi ⋅ (xj ⋅ xk) = (xi ⋅ xj) ⋅ xk for all i, j, k ≤ n. In a modern algebra class the following problem was proposed. What is the least number of elements a system can have and be non-associative? A system, S, of n elements (x1, x2, ..., xn) is associative if xi ⋅ (xj ⋅ xk) /= (xi ⋅ xj) ⋅ xk for some i, j, k ≤ n. It is obvious that a system of one element must be associative. Any binary operation could have but one result. A nonassociative system of two elements (a, b) can be constructed by letting a ⋅ a = b⋅a = b. , a⋅(a⋅a) = a⋅b and (a⋅a)⋅a = b⋅a = b. If a⋅b = a, then a⋅(a⋅a) /= (a⋅a)⋅a Thus the system is nonassociative. As is often the case this question leads to others. Are there systems of n elements such that xi ⋅ (xj ⋅ xk) /= (xi ⋅ xj) ⋅ xk for all i, j, k ≤ n? If such systems exist, what are their charcateristics? Such questions as these led to the development of this paper. A system, S, of n elements such that xi ⋅ (xj ⋅ xk) /= (xi ⋅ xj) ⋅ xk for all i, j, k ≤ n is called an anti-associative system. The purpose of this paper is to establish the existence of antiassociative systems of n elements and to find characteristics of these systems in as much detail as possible. Propositions will first be considered that apply to anti-associative systems in general. Then anti-associative systems of two, three, and four elements will be obtained. The general results that each of these special cases lead to will be developed. A special type of anti-associative system will be considered. These special anti-associative systems suggest a broader field. For a set of elements a group of classes of systems is defined. The operation may associative, anti-associative, or neither. Many questions are let unanswered as to the characteristics of anti-associative systems, but this paper opens new avenues to attack a broader problem.

In a paper by Beeler and Hoilman, the traditional game of peg solitaire is generalized to graphs in the combinatorial sense. One of the important open problems in this paper was to classify solvable trees. In this thesis, we will give necessary and sufficient conditions for the solvability for all trees with diameter four. We also give the maximum number of pegs that can be left on such a graph under the restriction that we jump whenever possible.