AIAbu Sayed Md Sohidull Islam

Abu Sayed Md Sohidull Islam

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Abu Sayed Md Sohidull Islam has a total of 9 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Algorithms to Compute the Lyndon Array

    by Frantisek Franek, A. S. M. Sohidull Islam, M. Sohel Rahman, W. F. Smyth

    We first describe three algorithms for computing the Lyndon array that have been suggested in the literature, but for which no structured exposition has been given. Two of these algorithms execute in quadratic time in the worst case, the third achieves linear time, but at the expense of prior computation of both the suffix array and the inverse suffix array of x. We then go on to describe two variants of a new algorithm that avoids prior computation of global data structures and executes in worst-case n log n time. Experimental evidence suggests that all but one of these five algorithms require only linear execution time in practice, with the two new algorithms faster by a small factor. We conjecture that there exists a fast and worst-case linear-time algorithm to compute the Lyndon array that is also elementary (making no use of global data structures such as the suffix array).

  • Open Access

    Enhanced Covers of Regular & Indeterminate Strings using Prefix Tables

    by Ali Alatabbi, A. S. Sohidull Islam, M. Sohel Rahman, Jamie Simpson, W. F. Smyth

    A \itbf{cover} of a string $x = x[1..n]$ is a proper substring $u$ of $x$ such that $x$ can be constructed from possibly overlapping instances of $u$. A recent paper \cite{FIKPPST13} relaxes this definition --- an \itbf{enhanced cover} $u$ of $x$ is a border of $x$ (that is, a proper prefix that is also a suffix) that covers a {\it maximum} number of positions in $x$ (not necessarily all) --- and proposes efficient algorithms for the computation of enhanced covers. These algorithms depend on the prior computation of the \itbf{border array} $\beta[1..n]$, where $\beta[i]$ is the length of the longest border of $x[1..i]$, $1 \le i \le n$. In this paper, we first show how to compute enhanced covers using instead the \itbf{prefix table}: an array $\pi[1..n]$ such that $\pi[i]$ is the length of the longest substring of $x$ beginning at position $i$ that matches a prefix of $x$. Unlike the border array, the prefix table is robust: its properties hold also for \itbf{indeterminate strings} --- that is, strings defined on {\it subsets} of the alphabet $\Sigma$ rather than individual elements of $\Sigma$. Thus, our algorithms, in addition to being faster in practice and more space-efficient than those of \cite{FIKPPST13}, allow us to easily extend the computation of enhanced covers to indeterminate strings. Both for regular and indeterminate strings, our algorithms execute in expected linear time. Along the way we establish an important theoretical result: that the expected maximum length of any border of any prefix of a regular string $x$ is approximately 1.64 for binary alphabets, less for larger ones.

  • The swap matching problem revisited

    by Pritom Ahmed, Costas S. Iliopoulos, A.S.M. Sohidull Islam, M. Sohel Rahman


  • Open Access

    On the protein folding problem in 2D-triangular lattices

    by Abu Sayed Md Sohidull Islam, Mohammad Sohel Rahman

    : In this paper, we present a novel approximation algorithm to solve the protein folding problem in HP model. Our algorithm is polynomial in terms of the length of the given HP string. The expected approximation ratio of our algorithm is 1-2lognn-1 for n ≥ 6, where n2 is the total number of H's in a given HP string. The expected approximation ratio tends to reach 1 for large values of n. Hence our algorithm is expected to perform very well for larger HP strings.


  • On Palindromic Sequence Automata and Applications

    by Mahbubul Hasan, A. S. M. Sohidull Islam, M. Sohel Rahman, Ayon Sen