Dijkstra and Bellman-ford are the two basic methods to solve Single-source shortest paths problem，and SPFA is the optimized version of Bellman-ford. However, since the algorithm time complexity is 0 (kn), SPFA’s time efficiency has some instabilities. This paper will compare the time efficiency between Dijkstra optimized with heap and three kinds of SPFA in different density graphs. Meanwhile, random data is created to test optimized Dijkstra and 3 types of SPFA. Finally, according to the calculation result of two methods’ time efficiency, some suggestion is given for their application under different situation.

No abstract uploaded!

In this paper, we will discuss some upper bound formulas for Ramsey numbers.At first, we will derive a more unified form from two parameter formulas which was obtained by Yiru Huang etc. Then, similar to their methods, we introduce two new bound formulas for Ramsey numbers in this paper. At last, as the applications of our new bound formulas, some upper bounds for small Ramsey numbers will be obtained.

No abstract uploaded!

Structural variations in genome could be more critical than SNP (Single-Nucleotide Polymorphism) in causing tumor cells, immune system diseases and fatness. It is necessary and important to detect structural variations with next generation sequencing data by means of efficient and accurate algorithms. This paper introduced a new algorithm using k-mers (short fragments of genome), string algorithms and graph algorithms, which combines similarity check, variation detection with sequence assembly. Our results showed that our method has high accuracy and it is more reliable than methods using reference and more efficient than popular algorithms.

No abstract uploaded!

This research, initiated by a problem excerpted from Baidu, one of the most famous internet search engines in China, explores two types of movements, “converging curve” and “tracing curve” named by this research group, which really act in a regular pattern. In the research, by applying scores of mathematical methods, we found that the key to converging curves is to spot the invariant elements from the changeful motions. For tracing curves, we adopt estimating equations to get the solution. Due to the limit of time and the relevant knowledge of the research group, many unexpected problems constantly appeared which are quite far beyond our ability. Yet we still tried to apply some promising mathematical thoughts, and have achieved some exciting results. In the process of discovering and rediscovering, we did not succeed in finding a perfect solution to the problem. After all, as a group of middle school students fascinated by mathematics, creating and discovering more are the greatest delight of us all.

No abstract uploaded!

No abstract uploaded!

No abstract uploaded!

No abstract uploaded!

This essay mainly involves a method to count the number of permutations of size n with length of the longest increasing subsequence equal to 2. The question is raised as the research project of Algebraic Combinatorics in 2016 Tsinghua Math Camp. This essay will show the relationshi between a permutation's longest increasing subsequence andits correspondingRobinson-Schensted map. Moreover, theessay will develop a general formula to count thenumberwith the help of the hook length formula.

Characterization of homogeneous polynomials with isolated critical point at the origin follows from a study of complex geometry. Yau previously proposed a Numerical Characterization Conjecture. A step forward in solving this Conjecture, the Granville-Lin-Yau Conjecture was formulated, with a sharp estimate that counts the number of positive integral points in ndimensional (n≥3) real right-angled simplices with vertices whose distance to the origin are at least n-1. The estimate was proven for n≤6 but has a counterexample for n = 7. In this project we come up with an idea of forming a new sharp estimate conjecture where we need the distances of the vertices to be n. We have proved this new sharp estimate conjecture for n≤7 and are in the process of proving the general n case.

In this paper we study the generalization of the Brocard congurations. The denition of q-period broken line is given and then the new necessary and sucient condition about the existence of two conjugate Brocard points of the q􀀀period loop broken line is investigated. Based on the past research, a geometric method for the construction of all possible loop broken lines with conjugate Brocard points is developed.

The optimal mass transportation problem, proposed by Monge, is dominated by the Monge-Ampere equation. In general, as the Monge-Ampere equation is highly non-linear, this type of partial dierential equations is beyond the solving ability of a conventional nite element method. This diculty led Gu et al. alternatively to the discrete optimal mass transportation problem. They developed variational principles for this problem and reported the calculation for the optimal mapping, based on theorem that among all possible cell decompositions, with constrained measures, the trans- portation cost of the discrete mapping from cells to the corresponding discrete points is minimized by the decomposition induced by a power Voronoi diagram. Their research inspired us to consider a similar discrete optimal mass transportation problem. Here we replace the L2 Euclidean distance by the length of the shortest path connecting two points on a line network. To solve the optimal trans- portation problem on a line network, we study a type of Voronoi diagram on undirected and connected networks and propose an elegant construction algorithm. We further consider weighted distances in a network and develop a method to compute the centroidal Voronoi tessellation (CVT) for a network. By using real geographic data, the method proposed is proved ecient and eective in several practical applications, including charging station distribution in a trac network, and trash can distribution in a park.

No abstract uploaded!

Sign language bridges the communication between the deaf-mute and the rest of the world. With the development of computer technology, the research on sign language recognition is prospering. Currently, there are two kinds of research methods. One is based on machine vision, the other is based on wearable input devices. Comparing with machine vision, wearable devices have the advantage of being able to get real-time information of the bend of the fingers and the movement of the hand. The essay applies recent technology in the field of voice recognition, and aims at finding out the best algorithm for medium vocabulary continuous sign language recognition. By building a hybrid Deep Neural Network-Hidden Markov Model, and designing and making a low-cost digital glove, the essay successfully compares the features between Dynamic Time Warping (DTW), Gaussian Mixture Model-Hidden Markov Model (GMM-HMM) and Deep Neural Network-Hidden Markov Model (DNN-HMM) as of solving the problem of sign language recognition. Tests show that in terms of calculating the observation probability, DNN has a much better performance than HMM, especially when syntax is not provided, meaning that DNN better suits the developing trend of sign language recognition. Real-time recognition is achieved on the intelligent terminal with an accuracy of over 97%, using the trained model and a decoding program.

The aim of this study is to figure out the optimization of survival probability of the generals in the card game "Legends of the Three Kingdoms". First, based on combinatorics and probability theory, the PASCAL program was performed to analyze the probabilities of success when several popular generals perform their special skills in the game. The results are as follows: Second, seven typical generals, including Zhou Tai, Zhang Jiao, Zhen Ji, Lu Xun, Ma Chao, Xiahou Dun, and Guo Jia, were chosen, and their abilities including attacking and defense were arbitrarily quantified according to a model constructed in the present study. The scores are as follows: Card-drawing Changing Attacking Defense Blood-selling Zhen Ji 5.62 Zhou Tai 1.04 Ma Chao 1.68 Xiahou Dun 1.19 Guo Jia 3.36 Lu Xun 3.55 Zhang Jiao 2.55 The abilities of different generals were sorted, and by comparison with the statistical record online, the reliability of the model was proved. Thus, the irrationality of the game is identified in this study, and we recommend the game designer to modify the abilities of some generals and to obtain an optimized value according to the output of the model, by which the game would be more popular.

We reduced the unsolved problem of Evans triangles to the problem of nding rational points on a class of elliptic curves, the twisted Edwards curves En. We proved that the set of all Evans triangles with a given ratio is isomorphic to a quotient group of En(Q). After this, using Sage, we can solve the Evans problem for an amount of cases within the capacity of computer. Even without the help of a computer, we can still obtain a large class of new Evans triangles, and nd an eective way to test if the rank of an Edwards curve is positive or not.

No abstract uploaded!

Nowadays, pictures have more and more applications in various fields. Because different situations may have different commands of the ratios of pictures, we present a program which can resize the pictures according to their contents. Compared with the traditional method which only cares about the geometric constraints, our program can reserve the important contents of the pictures, which means that the visual effect of the pictures will not be damaged after the resizing. In order to change the ratio of pictures while avoiding distorting their main contents, we use a method called seam carving. Based on the energy function used for finding useless pixels and dynamic programming used for finding some continuous seams which will be deleted later, our program can finally change the image to a new ratio perfectly. Due to some deficiencies of the basic program, we also make some improvements. The first one is the improvement of the algorithm: we add face detection to the basic program. Not only does this improvement can solve many problems of the basic program automatically, but also it is our own innovation of the study of content-aware resizing. The second one is the addition of customization: we allow users to select the specific contents that they want to reserve, which can meet the different needs of users. It’s also our own innovation which will be very useful in practical situations. Our program can have many practical applications. We have some ideas about how to put this algorithm into real use, which is one of our practical innovations of this topic. In terms of different ratios of photo printing, graphic designing and screen displaying, this program will have various uses, which will make a groundbreaking progress in practice.

No abstract uploaded!

No abstract uploaded!

No abstract uploaded!

No abstract uploaded!