Questions regarding well-defined instructions for completing a task, and relevant analysis in terms of time/memory/etc.

learn more… | top users | synonyms (1)

-2
votes
0answers
24 views

Solving simple recursion [on hold]

Sir,Please help me in solving the recursion $F(n)=K_0\frac{F(n-1)}{n-1}+K_1\frac{F(n-2)}{n-2} \tag 1$ ,preferably using power series for the values of $F(n)$ in-terms of n. $K_1$ and $K_2$ here are ...
-3
votes
0answers
26 views

Tree Traversal - Simple Puzzle type Issue

This is a puzzle like question,based on Fibonacci like structure of the tree. Actually it is a short question with out any complex concepts. It appears bit big,since I have added explanations with ...
7
votes
3answers
808 views

Are there any cases where quantum has given insight for classical algorithms?

To be more specific, has it ever happened that we've made some kind of significant improvement to a classical algorithm or problem as a result of some "trick" or insight gained from looking at quantum ...
3
votes
1answer
142 views

Applications of Harrow's algorithm for solving linear equations

In Harrow's algorithm for solving a system of linear equations the output is a quantum state rather than explicit information. Has anyone been able to apply knowledge of this quantum state to solve a ...
1
vote
0answers
92 views

Complexity of an algorithm for deciding 3-colorability of graph by the chromatic polynomial modulo $x-3$

As explained on MO computing the chromatic polynomial $P(G,x)$ modulo $x-3$ is enough for deciding 3-colorability. For non adjacent vertices $u$ and $v$, $G+uv$ is the graph with the edge $uv$ added ...
5
votes
0answers
66 views

Perfect hashing family variation - injectivity on $r$ disjoint sets

We denote by $[t]$ the set $\{1,2,\ldots,t\}$. A $(n,k)$-perfect hashing family is a set of functions $H=\{h_i:[n]\to[k]\}$ such that for every set $S\subset [n], |S|\leq k$, there exists some $h_S ...
0
votes
0answers
31 views

Sparse matrix-vector multiplication materials needed

I've been assigned a project at school, the theme is the influence on cache memory when doing sparse matrix-vector multiplications. I've been searching for materials for quite some time but all I can ...
0
votes
1answer
171 views

Examples of $2^{\Theta(n^2)}\text{poly}(n)$-time algorithms

What are notable examples of problems for which the best currently known algorithm has $2^{\Theta(n^2)}\text{poly}(n)$ running time ?
6
votes
0answers
40 views

Explicit error bounds on the abelian hidden subgroup problem

What are some explicit forms for the error probability in the typical quantum abelian hidden subgroup algorithm as a function of oracles queries? Ettinger, Hoyer, and Knill give a result that the ...
0
votes
0answers
61 views

The ratio $\frac{f(x_{i})-f(x_{i+1})}{||x_{i+1}-x_i||_2}$ as a performance index

Consider a problem \begin{equation} P:\min_{x \in X} f(x) \end{equation} Suppose it can be solved by an iterative method $A:X \rightarrow X$ $x_{i+1} = A(x_i)$ and $f(x_{0})\geq f(x_1) \geq ...
-1
votes
0answers
60 views

Making a function tail-recursive without using CPS

Is there a way to compute $\binom{n}{k}$ through the recurrence $\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}$ in a tail-recursive manner using only the basic structures found in mainstream ...
-2
votes
0answers
40 views

Data structures in Clauset-Newman-Moore algorithm for finding community structure in networks?

I am trying to implement the Clauset-Newman-Moore algorithm for discovering community structure in python. The paper describing the algorithm is in the comments because I cannot post more than 2 links ...
2
votes
1answer
54 views

Efficient (non-crypto-grade?) pseudorandom permutations with arbitrary domain size

I'm looking for an efficient/simple (even if not necessarily cryptographically strong) algorithm for implementing pseudorandom permutations with domain cardinality other than a power of 2. (FWIW, the ...
3
votes
1answer
169 views

Does a universal index exist?

Given a data table containing a very large number $N$ of rows, with each row containing a large number $k$ of fields, with each field containing a large but fixed number of bits, there are a number of ...
10
votes
1answer
81 views

Minimum equidecomposable decomposition

Given two polyhedra $P$ and $Q$, $P$ and $Q$ are are equidecomposable if there are finite sets of polyhedra $P_1, \ldots, P_n$ and $Q_1, \ldots, Q_n$ such that $P_i$ and $Q_i$ are congruent for all ...
-1
votes
0answers
27 views

eigenvalue of the product of a circulant matrix and diagonal matrix

Suppose we have a circulant matrix (A) and a diagonal matrix (B). Both of the matrices are of order n * n. The elements in the diagonal matrix are all different. Is there an algorithm to compute the ...
0
votes
0answers
74 views

Regularlity lemma and exceptional set

Regularity lemma is one of the most basic tools in algorithmic thoery and pure math theory like additive number theory and combinatorics. This lemma is stated two ways: the existence of a partion ...
6
votes
2answers
198 views

What is the value of this “game” (counters rebalancing)?

This question was posted in CS.SE two weeks ago, but it didn't get a satisfying answer. Suppose you have the following game: There are infinitely many counters $\{c_1,c_2,\ldots\}$, all initialized ...
4
votes
0answers
74 views

How many exponentiations can the Shamir algorithm reduce?

The Shamir's algorithm is depicted as follows (cited from Handbook of Applied Cryptography, chapter 14, algorithm 14.88, page 618) Shamir's algorithm INPUT: group elements $g_0,g_1,\dots, g_{k-1}$ ...
7
votes
2answers
214 views

Maximizing the number of heads in $N$ tosses by choosing which coin to toss

Assume you have two coins $A,B$ with biases $P_A,P_B$ respectively. We would like to make $N$ coin tosses and get the maximal number of heads possible. Unfortunately, we know $P_B$, but $P_A$ is ...
4
votes
2answers
451 views

Sum of products of all combinations?

We are given a list $S$ containing $n$ numbers $S=(s_1,\ldots, s_n)$. Let $S \choose k$ be the set of all possible $k$-combinations from $S$ (i.e. size $k$ subsets of $S$). We want to compute the ...
10
votes
1answer
228 views

Identifying useless edges for shortest path

Consider a graph $G$ (the problem makes sense both for directed and undirected graphs). Call $M_G$ the matrix of distances of $G$: $M_G[i, j]$ is the shortest path distance from vertex $i$ to vertex ...
7
votes
1answer
152 views

Is the feasible region of this SDP polyhedral?

We have a semidefinite program (SDP) with feasible region containing only a finite number of rank-$1$ matrices. Can we conclude that the feasible region of this SDP is polyhedral? We believe this to ...
4
votes
2answers
197 views

Intuitively, why is the complementary slackness condition true?

What's an intuitive proof that shows that the conditions of complementary slackness are indeed true: If $x^*_j > 0$ then the $j$-th constraint in the dual is binding. If the $j$-th constraint in ...
3
votes
1answer
121 views

Number of bits required for encoding variables with fixed sum?

Assume we'd like to be able to encode variables $x_1,x_2,\cdots,x_r\in \mathbb{N}$, such that $\forall i\in[r]:1\leq x_i\leq N$ and $$\sum_{i=1}^{r}x_i=M$$ It's easy to store the variables using ...
6
votes
1answer
180 views

Why is complementary slackness important?

Complementary slackness (CS) is commonly taught when talking about duality. It establishes a nice relation between the primal and the dual constraint/variables from a mathematical viewpoint. The two ...
3
votes
2answers
85 views

Minimal encoding of a set (unordered collection of elements)?

Assume you have universe $\mathcal{U}=\{e_1,e_2,\ldots e_N\}$. If we like to encode an ordered sequence of $k$ elements from $\mathcal{U}$, it's not hard to argue that $k\log |\mathcal{U}|$ bits are ...
0
votes
2answers
124 views

Determining the distribution of results of a simple algorithm

Setting Consider repeating the following process on the numbers $N=\{1, 2, 3, \ldots, n\}$: Pick an integer $k \in N$, uniformly at random. Pick a subset of $k$ elements from $N$, uniformly at ...
1
vote
1answer
54 views

Are there published algorithms for on-line creation of AVL trees from ordered streams?

Given an ordered stream of n items (n unknown in advance), it is well-known how to construct a red-black tree from them in O(n)-time. More specifically this is possible using only O(log n) additional ...
4
votes
0answers
65 views

What is known about finding heavy hitters in a sliding window?

This question is strongly related to another question I asked here a few weeks ago. In this problem setting we have a stream of elements $s_1,s_2,...$, such that $\forall i: s_i\in \mathcal X$ for ...
11
votes
3answers
418 views

How to iterate over vectors in order of probability in small space

Consider an $n$ dimensional vector $v$ where $v_i \in \{0,1\}$. For each $i$ we know $p_i = P(v_i = 1)$ and let us assume the $v_i$ are independent. Using these probabilities, is there an efficient ...
4
votes
0answers
57 views

What is the smallest deterministic construction of an ordered perfect hashing family?

A $(n,k)$-perfect hashing family is a family of functions $H=\{h_i:[n]\to[k]\}$ such that for every set $S\subset [n], |S|\leq k$, there exists some $h_S \in H$ such that $H_S$ is injective on $S$. ...
9
votes
1answer
132 views

Checking if a polynomial factors into linear factors

Let $f\in\mathbb{Q}[x_{1},x_{2},\ldots,x_{n}]$ be a polynomial given by an arithmetic circuit $C$ of size $s$. Given $C$ as the input, is there a deterministic algorithm to check whether all the ...
0
votes
1answer
30 views

Why is label pruning possible with hub labeling?

Hub labeling (HL) computes superlabels using the vertices visited by the forward and reverse Contraction Hierarchies (CH) search. Those labels are then pruned (see HL, sec. 4.2) to generate strict ...
4
votes
1answer
183 views

Intersection of two unsorted sets or lists

Suppose you are given two lists $L_1$ and $L_2$, each of which contains pairwise distinct elements from some set $S$. What is the complexity of computing the intersection $L_1\cap L_2$ of the two ...
1
vote
2answers
74 views

Difference between PRAM and machine model in dynamic multithreading

In the first edition of Introduction to Algorithms (Cormen et al., MIT Press, 1990), the discussion of parallel algorithms is based on the PRAM model. In the second edition, paralellism has been ...
5
votes
0answers
111 views

Best algorithm for inversion of symmetric positive-definite matrices

As I know, the time complexity for usual inversion algorithm of general matrix is $O(n^3)$. In recent years, there is a improvement from $O(n^3)$ to $O(n^{2.8....})$. However, does there exists a ...
4
votes
3answers
363 views

Is it possible to optimize the calculation of $ax+b$ once I know $a$ and $b$?

An "algorithm" for calculating $ax+b$ would take the steps Calculate $a$ times $x$ Calculate $b$ plus the result of previous line. But if the values of $a$ and $b$ are known, can we create a more ...
0
votes
0answers
59 views

Are there any approaches to the following scheduling problem?

Consider the following problem: we are given $K$ tasks $\langle n_1, n_2, ..., n_K \rangle$. Every task $n_i$ is qualified with two parameters: The time it takes to be completed ($t_i$) and, The ...
2
votes
1answer
153 views

Literature for Generalized Load Balancing

i am looking for literature on this kind of problem. $$ \begin{align} \min_x \max_k &\quad \sum_{i,j} x_{ij}c_{ijk}\\ \text{subject to}&\\ &\sum_j x_{ij}=1,&& \forall i\in\mathcal ...
8
votes
0answers
188 views

Additive error in counting the number of 1's in a sliding window?

The setting is as follows: We're given a stream of bits. At time $t$ you get to see bit $b_t$, and required to output $\widehat{s_t} \approx \Sigma_{i=0}^{N}b_{t-i}$ (i.e. approximately how many 1's ...
5
votes
0answers
160 views

Practical algorithm for testing whether an edge is Delaunay

I have a set of vertices $V\subset\mathbb R^3$ and a set of edges $S=\{(a,b)|a,b \in V\}$. I want to know whether an edge in the set $S$ is Delaunay against the vertices in $V$. My assumed ...
1
vote
1answer
81 views

Why does the construction step of Aho-Corasick take linear time in the number of nodes?

The original paper's analysis of this, as far as I can tell is this: "THEOREM 3. Algorithm 2 requires time linearly proportional to the sum of the lengths of the keywords. PROOF. Straightforward." ...
3
votes
0answers
138 views

Election algorithm with unreliable messages and a certain timestamp

I am struggling to get a correct algorithm for a leader election algorithm in a distributed system. My assumptions are as follows: Messages are sent unreliably with an at-most-once sending Nodes are ...
1
vote
0answers
167 views

What is the optimal strategy for this 2 player game?

Let some finite array of integers is given initially. There is a number k which is initially '0'. In a move, a player will select a number from the array arr[i] and change k to gcd(k,arr[i]). Also, ...
1
vote
1answer
88 views

Asymmetry in converting Burrows-Wheeler transform to suffix array?

Given a suffix array of a string $w$, it's possible to construct the Burrows-Wheeler transform of $w$ by subtracting one from the indices of the suffix array (wrapping around if necessary), then ...
9
votes
1answer
149 views

Bisecting a set of points into two optimal subsets

I want to divide a set of points into two equally-sized subsets such that the within-cluster sum of squares is minimized. We can assume that the points are in two-dimensional Euclidian space. I'm ...
0
votes
0answers
58 views

Greiner-Hormann clipping with degeneracies

I'm trying to understand the paper "Clipping of Arbitrary Polygons with Degeneracies" by E. L Foster and J. R. Overfelt [1], which claims to extend the classic Greiner-Hormann polygon clipping ...
1
vote
1answer
147 views

More questions about permutations

I'm interested in permutations classes defined by one or several excluded patterns of length 4. In particular, the following classes seem interesting but not so-well studied algorithmically. the ...
1
vote
0answers
79 views

Known generalizations of Gauss pivot method?

The well-known Gauss pivot method can be used to solve a system of linear equations over a field. I'm aware of two extensions of this method: (i) the Büchberger algorithm for computation of Gröbner ...