Tumble, a fast simple iteration algorithm for Fibonacci

A faster linear iteration process for Fibonacci (and Lucas) numbers is given. Algorithms are derived for individual numbers and for sequence generation. A general algorithm for generalized Fibonacci numbers is derived from these.     

A simple linear time certifying LBFS-based algorithm for recognizing trivially perfect graphs and their complements

We introduce a simple, linear time algorithm for recognizing trivially perfect (TP) graphs. It improves upon the algorithm of Yan et al. [J.-H. Yan, J.-J. Chen, G.J. Chang, Quasi-threshold graphs, Discrete Appl. Math. 69 (3) (1996) 247–255] in that it is certifying, producing a P₄ or a C₄ when the graph is not TP. In addition, our algorithm can be easily modified to recognize the complement of TP graphs (co-TP) in linear time as well. It is based on lexicographic BFS, and in particular the technique of partition refinement, which has been used in the recognition of many other graph classes [D.G. Corneil, Lexicographic breadth first search—a survey, in: WG 2004, in: Lecture Notes in Comput. Sci., vol. 3353, Springer, 2004, pp. 1–19].     

Improved upper bounds on synchronizing nondeterministic automata

We show that i-directable nondeterministic automata can be i-directed with a word of length O(2ⁿ) for i=1,2, where n stands for the number of states. Since for i=1,2 there exist i-directable automata having i-directing words of length Ω(2ⁿ), these upper bounds are asymptotically optimal. We also show that a 3-directable nondeterministic automaton with n states can be 3-directed with a word of length , improving the previously known upper bound O(2ⁿ). Here the best known lower bound is .     

New efficient algorithms for the LCS and constrained LCS problems

In this paper, we study the classic and well-studied longest common subsequence (LCS) problem and a recent variant of it, namely the constrained LCS (CLCS) problem. In the CLCS problem, the computed LCS must also be a supersequence of a third given string. In this paper, we first present an efficient algorithm for the traditional LCS problem that runs in O(Rloglogn+n) time, where R is the total number of ordered pairs of positions at which the two strings match and n is the length of the two given strings. Then, using this algorithm, we devise an algorithm for the CLCS problem having time complexity O(pRloglogn+n) in the worst case, where p is the length of the third string.     

A direct algorithm for restricted rotation distance

In this paper we present a concise O(n) implementation of Cleary's algorithm for generating a sequence of restricted rotations between any two binary trees. The algorithm is described directly in terms of the binary trees, without using any intermediate representation.     

Computing sparse permanents faster

Bax and Franklin (2002) gave a randomized algorithm for exactly computing the permanent of any n×n zero-one matrix in expected time exp[−Ω(n1/3/(2lnn))]n². Building on their work, we show that for any constant C>0 there is a constant ?>0 such that the permanent of any n×n (real or complex) matrix with at most Cn nonzero entries can be computed in deterministic time n(2−?) and space O(n). This improves on the Ω(n²) runtime of Ryser's algorithm for computing the permanent of an arbitrary real or complex matrix.     

Darts and hoopla board design

Dartboard design can be seen as an instance of the travelling salesman problem with maximum costs. This paper presents a simple yet optimal greedy algorithm to arrange numbers on both circular dartboards and linear hoopla boards. As a result, it identifies a class of polynomially solvable travelling salesman problems.     

Aspect-ratio Voronoi diagram and its complexity bounds

This Letter first defines an aspect ratio of a triangle by the ratio of the longest side over the minimal height. Given a set of line segments, any point p in the plane is associated with the worst aspect ratio for all the triangles defined by the point and the line segments. When a line segment si gives the worst ratio, we say that p is dominated by si. Now, an aspect-ratio Voronoi diagram for a set of line segments is a partition of the plane by this dominance relation. We first give a formal definition of the Voronoi diagram and give O(n2+ε) upper bound and Ω(n²) lower bound on the complexity, where ε is any small positive number. The Voronoi diagram is interesting in itself, and it also has an application to a problem of finding an optimal point to insert into a simple polygon to have a triangulation that is optimal in the sense of the aspect ratio.     

Minimal on-line labelling

The problem of on-line labelling is one of assigning integer labels in the range 1 to N to an input stream of at most N distinct items, drawn from a linearly ordered set, so that at each step the labels respect the ordering on the items. To maintain this constraint, items may have to be relabelled to accommodate new ones. With T(M,N) denoting the total number of relabellings that have to be performed for the first M inputs, it is known that for any given constant c in the range 0<c<1 there are exact bounds T(Nc,N)=Θ(NlogN) and T(cN,N)=Θ(Nlog²N). However, in the case c=1, when the labelling is called minimal, is known only that T(N,N)=O(Nlog³N). Existing algorithms for minimal on-line labelling are complicated, and our aim in this paper is to give a simplified and self-contained account of the problem.     

基于表示学习的中文分词

为提高中文分词的准确率和未登录词（OOV）识别率,提出了一种基于字表示学习方法的中文分词系统。首先使用Skip-gram模型将文本中的词映射为高维向量空间中的向量;其次用K-means聚类算法将词向量聚类,并将聚类结果作为条件随机场（CRF）模型的特征进行训练;最后基于该语言模型进行分词和未登录词识别。对词向量的维数、聚类数及不同聚类算法对分词的影响进行了分析。基于第四届自然语言处理与中文计算会议（NLPCC2015）提供的微博评测语料进行测试,实验结果表明,在未利用外部知识的条件下,分词的F值和OOV识别率分别达到95.67%和94.78%,证明了将字的聚类特征加入到条件随机场模型中能有效提高中文短文本的分词性能。     

On some properties of the NML estimator for Bernoulli strings

This paper proves the monotonicity of the sequence , where C_n denotes the normalization coefficient in the universal Normalized Maximum Likelihood (NML) model for the Bernoulli class. The main result is used to find a non-asymptotic estimation of logC_n.     

计算Fibonacci数的对分迭代算法

Fibonacci数有很多应用,它的求值有几种不同的算法。对原有算法的时间复杂性在理论分析的基础上进行了实验的分析,实验结果表明采用逐项递归算法、对分递归算法、直接求值算法和迭代算法的程序,其运行速度依次递升。论文还提出了一种对分迭代算法,它比原有最快的迭代算法约快20%～60%。     

Efficient algorithms for clique problems

The k-clique problem is a cornerstone of NP-completeness and parametrized complexity. When k is a fixed constant, the asymptotically fastest known algorithm for finding a k-clique in an n-node graph runs in O(n0.792k) time (given by Nešet?il and Poljak). However, this algorithm is infamously inapplicable, as it relies on Coppersmith and Winograd's fast matrix multiplication.We present good combinatorial algorithms for solving k-clique problems. These algorithms do not require large constants in their runtime, they can be readily implemented in any reasonable random access model, and are very space-efficient compared to their algebraic counterparts. Our results are the following:

•

We give an algorithm for k-clique that runs in O(nk/(εlogn)^k−1) time and O(nε) space, for all ε>0, on graphs with n nodes. This is the first algorithm to take o(nk) time and O(nc) space for c independent of k.

•

Let k be even. Define a k-semiclique to be a k-node graph G that can be divided into two disjoint subgraphs U={u₁,…,uk/2} and V={v₁,…,vk/2} such that U and V are cliques, and for all i?j, the graph G contains the edge {ui,vj}. We give an time algorithm for determining if a graph has a k-semiclique. This yields an approximation algorithm for k-clique, in the following sense: if a given graph contains a k-clique, then our algorithm returns a subgraph with at least 3/4 of the edges in a k-clique.

     

An efficient algorithm for Horn description

We give a new algorithm for computing a prepositional Horn CNF formula given the set of its models. Its running time is O(|R|n(|R|+n)), where |R| is the number of models and n that of variables, and the computed CNF contains at most |R|n clauses. This algorithm also uses the well-known closure property of Horn relations in a new manner.     

On a word avoiding near repeats

In this paper we construct an infinite binary word w with the following property: the minimal distance among two occurrences of a same factor of length n cannot be polynomially upperbounded. In particular, for all positive ε the number of distinct factors of w with exponent larger than 1+ε is finite.     

On the design of planar antenna using Fibonacci word fractal geometry in support of public safety

In this article, a planar antenna based on Fibonacci word fractal geometry with defected ground structure (DGS) has been investigated. A novel type of antenna radiator is proposed using Fibonacci word fractal which works for public safety and dedicated short range public safety applications. Size of proposed antenna is 50 × 44 mm and it resonates at 4.9 and 5.9 GHz having bandwidth ranging from 4.8 to 5.1 GHz and 5.8 to 6.8 GHz, respectively. Defected Ground Structure is used to improve gain for lower frequency band. Representative results of fractal patch antenna are reported to access the effectiveness of the developed approach in public safety applications. Simulation and experimental result confirms the efficiency of Whale Optimization Algorithm for antenna design. Experimentally measured results are matches well with simulated results and quite promising.     

Square-free partial words

We say that a partial word w over an alphabet A is square-free if every factor xx^′ of w such that x and x^′ are compatible is either of the form ?a or a? where ? is a hole and a∈A. We prove that there exist uncountably many square-free partial words over a ternary alphabet with an infinite number of holes.