When data is stored, transmitted or read, errors occur. In order to be able to
correct these errors, error-correcting codes are used. These codes add redundant
information, in order to be able to correct errors that might occur. There are
three types of errors hat might occur, namely substitution, insertion and deletion errors. Substitution errors are errors where the original symbol is wrongly
decoded or stored and the receiver reads another symbol. Insertion errors are
errors where the receiver reads a symbol at location where there should not
be a symbol and a deletion error is an error where the receiver does not read a
symbol while the reader should have. Substitution errors are the most common
and therefore, codes which correct these type of errors are ore extensively examined. There are however methods of storing data, for example storing data
using DNA as medium, for which insertion and deletion or indel errors occur at
a significant rate and therefore error-correcting codes should not only be able
to correct substitution errors, but also indel errors.We want codes to be
as efficient as possible, in other words, to be able to correct as many errors as
possible by adding as few redundant symbols as possible. The size of a code
is the number of codewords in a code and we would like this number to be as
big as possible. Ward Spee has done research into the maximum size of error-
correcting codes that can correct exactly t' deletions, exactly t′′ insertions and
at most s substitutions for his masters thesis at the University of Technology
Delft. In his research he has found various bounds on he size of these error-
correcting codes. These bounds contain the size of a set V which is not known.
This bachelor thesis project revolves around determining bounds on this size.

The magical "Cheney card trick" will be presented in this thesis using a mathematical approach. This trick is performed by a magician and an assistant in the following way: the magician leaves the room, and the assistant lets the audience draw 5 cards from a standard deck of 52 cards. Then, the assistant returns one of the 5 drawn cards to the audience and places the remaining 4 cards on the table. The magician can enter the room once the 4 cards have been placed on the table. The magician looks at the 4 cards on the table and, by these 4 cards, identifies the card that was given to the audience.
This thesis explores the underlying mathematical principles. The trick’s workings will first be explained, after which an algorithm for performing the trick will be given. In the analysis of the trick, we noticed that the size of the deck that we performed the trick with could be expanded. Given that we draw n cards from a deck of size d, we introduce an upper bound. This upper bound on the deck size is: d ≤ n! + n − 1. Furthermore, we introduce Birkhoff-von- Neumann’s theorem and Hall’s marriage theorem. Using these two theorems, we will prove that a convention for the magician and the assistant to perform the trick always exists when we attain the introduced upper bound. We will prove the existence of a convention and provide algorithms to perform the trick with a deck of cards attaining the introduced upper bound. While performing the trick, a specific order of the cards appears more often than others. When analysed, we find that a less preferable order of the cards is only necessary for approximately 10 per cent of the drawn hands. Additionally, a theorem of Gale-Shapley about stable and optimal matches is introduced, adding an extra dimension to Hall’s marriage theorem. Gale-Shapley’s algorithm is then introduced, and the possibility of finding a stable match between hands and messages is explored. Altogether, this thesis aims to find an answer to the question: What mathematical principles and ideas underlie the "Cheney card trick"?

Every day an extremely large amount of messages get sent over the internet, radio, WiFi, etc. These messages need to be encoded in order to protect the important data. However just like many of these systems messages can get corrupted over a certain channel due to noise, fluctuations in power or temperature etc. [2] Therefore cyclic redundancy checks (CRC), which are bits that are appended to message words to protect the data, are used to detect these errors. This is done by using CRC polynomials. An occurring undetected error is possible in any case, therefore we need to study closely the probability of an undetected error occurring, that is the probability that the received, erroneous data is accepted as the transmitted message. The code words that are the results of adding cyclic redunancy checks (CRC) can also be combined with an error-correcting codes like BCH codes. As shown in [3] combining CRC polynomials with error-correcting can reduce the previously mentioned probability, but one CRC polynomial can perform better. In this thesis these CRC polynomials are studied in combination with certain different codes and are evaluated based on their performance with respects to their undetected error probability. Two examples of codes are given, in the first example a CRC polynomial is found that does not perform well in the system without using an error-correcting code, but performs the best in the system with an error-correcting code. An analysis is done which shows that by looking at consecutive roots of the generator polynomial, optimal CRC polynomials can be found. The second example uses a different code and finds another optimal CRC polynomial

Coding techniques for correcting combinations of deletion, insertion and substitution errors are implemented in novel data storage applications. Error correcting codes have been well-studied for either substitution errors, or deletion and insertion (indel) errors, but the understanding of codes that correct combinations of these errors falls short. To achieve an efficient implementation in terms of redundancy, we are interested in the maximal size of a code that can correct t indels and s substitutions. Determining this maximal size in general is a difficult task, and thus in many instances we have to rely on bounds. In this thesis, we review existing bounds on the maximal size of both t-indel correcting codes and s-substitution correcting codes. Thereafter, we study how these bounds can be generalized to the setting of t-indel s-substitution correcting codes.  The main contributions of this thesis include two new explicit lower bounds, which are based on generalizations of the Gilbert-Varshamov bound. Furthermore, we show that the Singleton upper bound, several existing sphere-packing upper bounds and an upper bound based on matchings in hypergraphs can all be generalized to upper bounds on the maximal size of t-indel s-substitution correcting codes. Several of these bounds provide improvements upon existing results in literature. Moreover, we argue that the asymptotic redundancy of maximally sized t-indel s-substitution correcting codes lies between (t + s) logq(n) and 2(t + s) logq(n) + o(logq(n)).

The four-colour conjecture (4CC) is a question that asks whether any map can be coloured using only four colours, with the constraint that neighboring countries must have distinct colours. This conjecture has re- mained unanswered for over 170 years, with a rich history of various attempts to prove it. In 1879, Kempe put forward a proof, but it was invalidated by Heawood after 11 years. Heawood did succeed, however, in prov- ing the weaker five-colour theorem. It wasn’t until 1976 that the first genuine proof was discovered by Appel and Haken. This proof sparked controversy due to its reliance on approximately 1200 hours of computer computation, making it unverifiable by hand.
The purpose of this report is to provide a comprehensive overview of the historical background and re- cent advancements in the four-colour theorem. It will delve into the numerous failed attempts to prove the conjecture and discuss the groundbreaking proof by Appel and Haken. Additionally, it will explore a recent endeavor by Dr. Xiang, who approached the problem from a different perspective but also encountered a fallacy in his work. The main contribution of this thesis involves a new proof that builds upon the research of Dr. Yeh, who attempted to prove the four-colour theorem by transforming it into a system of linear equa- tions. The missing crucial steps will be addressed for whose correction new ideas will be introduced, using an integral version of Farkas’ lemma and superadditivity. The ideas being researched do not finalize the proof but contribute towards a possible elegant proof in the future. Finally, related topics such as maps on different surfaces and maps with disconnected regions will be considered, broadening the scope of the discussion.

The world can’t keep up with its own data and therefore needs new ways to store it. Research is being done into new types of experimental data storage like DNA sampling or racetrack memory, which could completely revolutionize the way storage works. However, such storage media are prone to certain type of errors like deletion errors where information is lost. Consequently, there has been a surge in interest in developing deletion correcting codes to address this challenge. We are interested in the maximal size of a code correcting up to a certain number of deletions. Nevertheless, constructing these codes can be quite intricate and therefore we are often limited to working with bounds.
In this thesis, we will study and evaluate upper bounds for these codes. We will compare bounds that were derived analytically to bounds that have been computed with the use of linear programs. We will compute upper bounds for 1-, 2- and 3-deletion correcting codes. Moreover, we will show how to compute these bounds with a linear program, by posing the problem of finding a largest deletion correcting code as finding the transversal number on a hypergraph. It will become clear that the bounds computed through linear programming are much stronger than any bound derived analytically.

Subgraph matching is a fundamental problem in various fields such as machine learning, computer vision, image processing, and bioinformatics, where detecting specific substructures within an object is often crucial. In these domains, not only structure plays an essential role, but also the feature information on nodes should be incorporated, thus highlighting the necessity for comprehensive analytical approaches.

In this thesis, we propose two novel subgraph matching frameworks using the Fused Gromov-Wasserstein (FGW) distance, namely the Subgraph Optimal Transport (SOT) and the Sliding Subgraph Optimal Transport (SSOT). Both frameworks integrate a dummy node strategy to handle the discrepancy between two graphs of different sizes. The SSOT extends upon the SOT by incorporating a sliding window framework and Wasserstein pruning to enhance the performance, especially for sparse large graphs. Our frameworks can be easily implemented and are adaptable for problems of exact matching, top-k approximate matching, and inexact matching.

We further propose a normalized FGW distance to cater to the practical interests and enhance the performance evaluation. We adopt the Frank-Wolfe algorithm for optimization and develop computation-reducing techniques by isolating the dummy node.

By conducting experiments on both synthetic and real-world datasets, we demonstrate that the SOT method achieves excellent performance on small graphs, and the SSOT method improves the accuracy over the SOT on large graphs. Both these two methods show the ability to outperform the state-of-the-art methods in noisy environments in terms of accuracy and efficiency.

While the Minimum Euclidean Distance detection is known to be optimal for channels affected by Gaussian noise, it has been shown that Minimum Pearson Distance detection (MPD) may perform better when the channel is also affected by an unknown offset, though for a good performance some adaptations for classical binary block codes are necessary. It is shown for cosets of first order Reed-Muller codes R(1,m) containing words of weight d/2, where d is the code's distance, that the minimum Pearson distance is always low for m≤4. However, it is possible to find cosets where the minimum Pearson distance is higher for m≥5.

Nowadays, we produce an enormous amount of data and all this data needs to be stored somewhere. In order to store all this data in an efficient and environmentally friendly way, solutions need to be found. A storage technique that has great potential to be a solution is synthetic DNA based storage.
A DNA-strand is made up of a sequence of four nucleotides, Adenine (A), Thymine (T), Guanine (G) and Cytosine (C). To save our data using DNA, our binary data is encoded to quaternary data, using this quaternary data DNA strands are made.
During this process, of saving our data in DNA, errors can occur, therefore two constraints are considered to minimise the number of errors in our codes.
The GC-weight, which is the number of G and C nucleotides in a DNA word and the maximal run-length, which is the maximum number of identical nucleotides in a row. In addition, the Hamming distance between words is also considered to be able to detect and even correct errors that still occur.

This research tries to find lower and upper bounds for the maximum size of DNA codes.
We continue the work of Van Leeuwen [1], Vermeer [2] and Laseur [3], who considered codes with fixed GC-weight. In this thesis we will relax this GC-weight constraint and we will look at codes where we have a set of GC-weights and all the DNA words in the code need to satisfy one of these weights. Furthermore, the codes we consider have a run-length of r=1. We will determine the maximum size of codes where the minimum Hamming distance d is equal to the length n of the DNA words. We determine lower and upper bounds for the case where d=n-1 and for specific sets of GC-weights we will determine the maximum size. Finally we will present nine algorithms, these algorithms create DNA-codes. The size of these codes give us lower bounds for the maximum size of DNA codes.

The amount of data being produced is growing exponentially. An im-
portant challenge is to find methods to store this data efficiently and in an
environmentally friendly way. One idea that is a growing research topic in-
volves using synthetic DNA. DNA has the potential to be more efficient and
environmentally friendly than current methods. DNA is made of a sequence of
four nucleotides, Adenine (A), Cytosince (C), Guanine (G), and Thymine (T).
To store data, DNA strands can be created with specic nucleotide sequences.
In the process of reading and storing data substitution errors can occur. Two
constraints are introduced to minimise the number of errors. The GC-weight
constraint which states that every DNA sequence must have a fixed number
of G and C nucleotides, and the runlength constraint, which states the maxi-
mum number of repeating nucleotides possible in every DNA sequence.

Humanity is producing data at exponential rates. Solutions need to be found in order to accommodate the bytes of today and the future in an efficient and environmentally friendly way. DeoxyriboNucleic Acid, well-known as DNA, is a suitable destination for this major collection of data, as it is a high-density storage medium with long storage endurance [1]. In the field of research about DNA-Based Data Storage Systems, people examine quaternary codes. The considered DNA-codes consist of equi-length DNA-words over the Alphabet {0, 1, 2, 3} representing the available DNA building blocks or nucleotides {A, T,C,G} standing for Adenine, Thymine, Cytosine and Guanine respectively. Combinatorial constrained coding is introduced to avoid DNA patterns prone to sequencing errors, that might occur when archival data is read from DNA-blocks [2]. If an error occurs anyway, an imposed minimum Hamming distance d that a DNA-code satisfies, enforces error correction and detection capabilities [3]. Methods are considered to optimize the number of DNA-words that can be stored in a DNA-code satisfying these restrictions. This research explores DNA-codes of which the DNA-words adhere to a fixed GC content referred to as the GC-weight w, as well as the no-runlength constraint r = 1 that will not allow adjacent symbol repetition. By increasing distance d, we build on the findings of Van Leeuwen [4] and Vermeer [5], who created DNA-codes satisfying d = 2 for r = 1 and r ≥ 1 respectively. The maximum size of a DNA-code satisfying d = 3 among other constraints is proven to be 12. Furthermore, we cover the case d = n where the length n of the DNA-words and the minimum distance d the DNA-code satisfies are equal. We derive maximum sizes of these DNA-codes for all possible GC-weights w. Finally, we present algorithms that create DNA-d codes satisfying d = 3 and d = 4 and succeed in improving sizes of the DNA-codes created by the algorithms designed by Limbachiya et. al. [6] and Van Leeuwen [4].

This thesis aimed to aid ErasmusMC in the workforce planning process of deciding how to implement training among the nursing personnel in order to build a more flexible workforce, so the hospital can be prepared for fluctuating and unexpected demand, while minimizing the costs of doing so.

To accomplish this, a mathematical model was developed taking into account the structure of the nursing personnel within the hospital, and the structure of how training among nurses is implemented. Since the planning was aimed to be done on a daily basis, the contractual obligations between nurses and the hospital had to be respected as well.

The resulted model was tested using real data provided by Erasmus MC, and with the mathematical optimization solver Gurobi. Consequently, a Genetic Algorithm (GA) approach was proposed; this heuristic accomplished to outperform Gurobi when applied to the biggest two instances considered in this project.

Flash calculations are used for the dynamic simulation of vapor-liquid phase equilibria (VLE) in many chemical processes. When used to predict the composition of mixtures in VLE, the repeated applicatino of these flash calculations, particularly in dynamic cases can cause small inaccuracies to cascade. One way to prevent this, is to have strong predictions and initial guesses for what a mixture in equilibrium will look like. For this, stability tests can be employed. Stability tests require the minimisation of the tangent plane distance, which is derived from the excess Gibbs Energy. The VLE problem and stability tests have been approached from a viewpoint based in mathematical optimisation, not one based in thermodynamics. As such, this work provides a slightly different description of flash calculations and stability tests, and can serve as both an introduction to the problems, as well as an approach to the problem in a different way than is traditionally done. In this report, the tangent plane distance function has been studied and applied to an example to gain intuition on the problem, and different optimisation methods were considered for minimising this function. A stochastic- and a deterministic method were applied to the stability problem to gain a better understanding of which type of method will work better for minimising the tangent plane distance. Both methods seem sufficient, but the scalability to higher dimensions is lacking, especially in the deterministic case.

Storage systems, such as Flash memories, suffer, apart from the always present
noise, also from offset. The presence of this noise can decrease the performance
of a decoder using the Euclidean distance significantly. To negate the effects of
offset, a new distance, the modied Euclidean distance, was introduced, which
offers immunity to offset. However, the modified Euclidean distance is less
resistant to noise, which calls for methods to improve its resistance. The coset
of Hamming codes, constant weight codes and Berger codes are discussed and are simulated to investigate their performance with both distances. These codes are compared to each other for the Euclidean distance and the modified Euclidean
distance.

Every day we produce an extremely high amount of data and a significant portion of this data is archival data. It is an important challenge to save this data in a cheap and environmentally friendly way. The current methods to save archival data are sufficient, but improvements can be made. Synthetic DNA based data storage is a great choice to do so. DNA is (roughly) made out of four nucleotides, Adine (A), Cytosine (C), Guanine (G) and Thymine (T). To save data using DNA the binary data is encoded to quaternary data and later DNA strands are created using this quaternary data. During the process of saving the data errors can occur. Previous research [3] has found that some errors can be prevented by taking two constraints into account.The no run-length constraint, which states that no DNA word can have two repeated symbolsand GC-weight constraint, which states that every DNA word must have a fixed number of G and C nucleotides. These constraints reduce the number of quaternary data sequences that can be used to save data. The aim of this thesis is to improve the lower bound on the maximum number of quaternary data sequences that satisfy the no run-length constraint, the fixed GC-weight and a minimum distance. Limbachiya et. al. [1] gave an algorithm to compute a set with a given minimum distance of quaternary data sequences that satisfies the constraints. The size of this set is the lower bound that we aim to improve. We do so by introducing two other algorithms that also compute a quaternary data sequences that satisfy the constraints and a minimum distance. The size of each computed set gives a lower bound on the maximum size. The lower bound computed with these two algorithms is always better or equal to the lower bound computed by Limbachiya et. al. for certain parameters. When the minimum distance of a code is 2 we know this maximum size. The formula for this maximum size is given in this thesis together with a proof for this formula.

With the internet growing exponentially, the amount of information stored digitally becomes enormous. Storage systems are expected to withstand failures to prevent the loss of data. To provide the reliability, data is stored multiple times in different storage units. If in this case, one of the storage unit goes offline, a backup of the data will be available in another. Needing to deal with duplication causes massive amount of excessive storage overhead. To prevent this overhead, erasure coding can be used. This form of coding can reduce the storage space needed, while still being able to provide a certain level of fault tolerance. Erasure coding makes use of so-called parities; symbols that do not directly contain data, but can be used to retrieve actual information nonetheless. When informational symbols get lost, due to a failure, the parity symbols are combined to reconstruct the lost symbol. Since multiple parities might be used in this process, repair traffic is generated. This traffic slows down the rest of the data flow, retaining quick access to the data. The amount of traffic needed to recover an erasure, is called the locality of a code. Codes with small amounts of storage overhead tend to have a greater locality, causing a lot of repair traffic in case of an erasure. In this thesis, multiple codes are being compared based on their locality and storage overhead. Besides these characteristics, a large code distance is favorable in erasure coding schemes. The distance within the code words of a scheme, determines how many erasures the scheme can handle without losing data. The Maximum Distance Separable (MDS) codes, such as the widely used Reed-Solomon codes, are optimal in the trade-off between code distance and storage overhead. In other words, these codes only need a little amount of overhead in order to withstand a large number of erasures. The pitfall of these codes, however, is their large locality which makes them almost unusable for some applications. Nevertheless, they form a great base for another type of coding scheme; the Locally Repairable Codes (LRC). These codes are extended with extra parity symbols on top of the MDS code which ensures a code locality lower than that of the MDS codes. Since less traffic is needed to repair erasures, they form an interesting group considering the compromise between code locality and storage overhead. The foundation of this thesis is formed by the content of the research paper “XORing Elephants: Novel Erasure Codes for Big Data” [4]. In this paper, researchers explain the creation of the (10,6,5) Locally Repairable Code and compare its characteristics to those of the (10,4) Reed-Solomon code. On top of the researchers’ findings, different parameter configurations will be applied to discover more of the LRC family in this thesis. Different configurations create codes that perform differently in recovering erasures. After comparing their characteristics, applications will be sought for each of the newly created LRCs. As one code might be optimal on the aspect of storage overhead, another might be optimal on the aspect of locality and yet another on the aspect of code distance. In Table 3 of the conclusion it shown which codes excels on what aspects.

Nowadays, enormous amounts of data are produced on a daily basis. Whether it is a cute family
picture, a funny cat video, or a scientic paper, all of the data is stored. The challenge in data
storage nowadays is about nding a way to store a lot of data, in such a way that it will stay
preserved for many years without too much maintenance and such that if errors occur, the data
can still be retrieved. DNA is a great choice for this, since the DNA from extinct species that
lived 10,000 years ago can still be retrieved, it does not need maintenance and it is estimated that
it can store 5 PB per gram [2]. However, in reading and writing DNA, substitution, insertion
and deletion errors occur, so the data needs to be protected against these errors. Therefore,
several coding methods have already been invented and researched. Takahasi et al. [1] designed
a full automated system for writing, storing and reading data, which consisted only of the word
hello, using DNA.
This thesis focuses on the coding method used by [1], namely a Hamming code, and compares
it to the implementation of a DNA based Reed-Solomon code, applied to the same data. An
analysis is made based on the net information density, GC-weight, homopolymer runs and
the error detection and correction properties. As expected, there is a trade-o between the
net information density and the error detection and correction properties. Although the net
information density of the Reed-Solomon code is lower, it can correct more errors and it has the
potential of also being applied to a bigger data set.

It is predicted that in about 100 years most of the earth's fossil fuels will have been depleted. Currently, fossil fuels still make up 80% of the Dutch energy production. Thus, to handle this depletion, the research on renewable energy production and its usage is being stimulated by governments. With the use of fossil fuel energy production, it is easy to increase production to meet the unexpected peaks in energy demand by burning more fuels. However, with renewable sources this is not possible. Thus, the way that the produced energy is being used needs to be altered. Furthermore, the amount of renewable energy that is privately generated has increased over the last couple of years. The energy that has been generated for private use and is not needed at that time, can either be sent back into the grid for other users or charged to a battery for later personal use. The electricity network that will regulate the buying and selling of energy is called a smart grid. When using a battery to store privately generated energy, the decisions that are made for the (dis)charging of the battery are of great influence on the total energy cost at the end of the month. When implementing a battery in a household or company that privately generates energy, these decisions need to be made within a fixed time limit of 15 minutes. In this thesis, four mathematical optimisation methods are compared to each other on result and run time. These methods are dynamic programming, local search, tabu search, and simulated annealing. Dynamic programming gives the solution with the lowest possible cost, but does not always have the lowest average run time. The total cost of the solution resulting from local search does not come close enough to the lowest possible cost generated by dynamic programming to be a viable alternative to dynamic programming. Tabu search is an extension of local search, it could result in a solution with a total cost close enough to the lowest possible cost if it runs more iterations than local search. However, due to this the average run time will exceed the run time of dynamic programming. Therefore, it is also not a viable alternative for dynamic programming. Simulated annealing has a shorter run time than dynamic programming when using a forecast time of 1 day or less. The total cost of the solutions come very close to those of dynamic programming. Therefore, while the run time of dynamic programming still fits within the available time limit, it is advisable to use this method to determine the charging decisions for a private battery in a smart grid. However, the simulations that were run in for this thesis do not encompass the entire real-life case. If after the expansion of the problem to be implemented in real-life the run time of dynamic programming were to exceed the available time period, then simulated annealing would be a good alternative for implementation.

Erasure codes protect data from being lost as servers tend to fail because of various reasons. Currently Reed Solomon Codes are being used by multiple big companies, however, more promising codes have been described in recent articles. This report compares the (14,10)-RS code (which is among others being used by Facebook), the Piggybacked (14,10)-RS code and the HeptagonLocal Code in terms of storage overhead, reliability and the repair bandwidth. As with most coding methods, most of the times a trade-off is found between the methods. The HeptagonLocal Code has the greatest storage overhead, however, it can repair one failed server, much faster then the other methods.

Information is spatially distributed over data servers and for many services online it has to be available at all times, but those servers are not always available. If we store the information in a smart way, we might be able to still get our information even if we can not reach the servers.
There are two factors we have to keep in mind when we restore the servers and information. Those are the repair bandwidth, this is the amount of data you need to download to repair a failed server, and the repair degree, this is the amount of other servers you have to access before you can repair your server.
We will look at two methods for restoring information with focusing on the repair degree, which means to access the least amount of other servers.
First we discuss how we can repair one and multiple failures or erasures using the cooperative and sequential repairing method. Then we discuss the parameters for a sequential locally repairable code and its locality or repair degree. Next we will discuss the parameters for the Hamming code and the extended Hamming code and their locality for which we have constructed a function to calculate the generalized Hamming weight with kappa smaller than or equal to 3. Now we can compare the sequential locally repairable code with the Hamming code for two erasures and we can compare the sequential locally repairable code with the extended Hamming code for three erasures. The result is that the sequential locally repairable code has a much lower locality than the Hamming code and the extended Hamming code, but they have a higher information rate.