Most recent 8 posts

See also all posts ordered by categories.

Query the sum of a submatrix

Maintain a matrix in a datastructure, allowing to update entries and to query the sum of a rectangular submatrix in time $O(\log(n)\log(m))$, where $n,m$ are the dimensions of the matrix.

Count all distinct substrings

Given a string $s$, determine the number of distinct substrings that it contains.

Determine the fixpoint of a rewriting system

Given the a rewriting system of the form $f:\Sigma\rightarrow \Sigma^\star$, determine the limit of $f^i(a)$ for some given seed letter $a\in \Sigma$.

Recognize a context free language

Given the grammar of a context free language and a string, decide if the string can be generated by the grammar.

Shortest path with negative edge weights

Given directed graph with possibly negative edge weights, find a shortest path between two given vertices.

bipartite vertex cover

Given an undirected bipartite graph find a minimum cardinality vertex set which covers all edges in the sense that it contains at least one endpoint of each edge.

sliding window

Given a string A (or array), and an integer k, find for every index i, the smallest index j (if it exists) such that {A[i],..,A[j-1]} consists of exact k distinct values.

maintaining the median of a dynamic set

Propose a data structure which permits to maintain a set of integers S, allowing to add elements and to remove the median. Both operations should work in logarithmic time.