Algorithms – TechUtils.in

June 18, 2018

#StackBounty: #algorithms #graphs #trees Cover k edges to minimize the length of the longest uncovered path in a tree

Bounty: 100

You are given a tree $Glangle V, Erangle$ and an integer $k$. The goal is to cover $k$ edges of the graph, to minimize the length of the longest uncovered path in the tree (and to return this path’s length)

Constrains: $O(nlog n)$ time and $O(n)$ space.

Now, the scheme of the algorithm is kinda obvious (from the given constrains). We need to priorities the edges and pick the highest $k$-edges (technically, we throw all edges to a priority queue and pick the first $k$)

So, I think, the keys should tell us how centric the edge is.

My first attempt was BFSing the graph from some node and BFSing again from the most distant node of the first scan.

Each node will get two values: distance from the first starting node and distance from the second starting node.

Though, I’m not sure how well this method grasp the notion of centric.

I’d be glad to hear your thoughts about the current idea or your own ideas.

Get this bounty!!!

April 23, 2018

#StackBounty: #ripple #algorithms #trust #future-proof Is the whole idea of proof of work or proof of stake quite unnecessary and super…

Bounty: 50

I only have a vague idea of proof of stake, but I think I reasonably understand proof of work. In the case of bitcoin, the whole hash thing business has to be combined with a mechanism to increase the difficulty according a certain time calculation. Now this difficulty/time calculation is merely a matter of good faith, and hope that a majority abides by it. If you look a bit deeper, the whole hash function itself relies on good faith, also called the 51% risk/attack whatever.

And hence you have currencies like ripple, which are just faith (maybe one degree higher compared to bitcoin and ethereum) as far as I can see, without any hash or other garnishing. This does seem to be equally functional. So did Satoshi over-design bitcoin? Does this suggest that a whole new generation of minimalistic cryptos will completely sweep away bitcoin, ethereum and the likes?

Get this bounty!!!

April 14, 2018

#StackBounty: #algorithms #strings #string-metrics #edit-distance Edit distance of list with unique elements

Bounty: 50

Levenshtein-Distance edit distance between lists
is a well studied problem.
But I can’t find much on possible improvements if
it is known that no element does occurs more than once in each list.

Let’s also assume that the elements are comparable/sortable
(but the lists to compare are not sorted to begin with).

In particular I am interested
if the uniqueness of elements makes it possible to improve upon
Ukkonen’s algorithm for edit distance
which has time complexity $O(min(m,n)s)$ and
space complexity $O(min(s,m,n)s)$,
where $s$ is the minimum cost of the editing steps.

More formally,

how efficiently can we compute the edit distance between two given strings
$s,t in Sigma^*$
with the promise that they don’t have any repeated letters?

$Sigma$ is a very large alphabet.

Get this bounty!!!

April 9, 2018

#StackBounty: #algorithms #expectation-maximization #t-distribution #latent-variable EM for a form of Student distribution

Bounty: 50

I consider $n$ replications from the following sampling density function for $y_iinBbb{R}^p$

begin{align}
f_p(y_ivertmu,Sigma,nu)={displaystyle {frac {Gamma left[(nu +p)/2right]}{Gamma (nu /2)nu ^{d/2}pi ^{p/2}left|{boldsymbol {Sigma }}right|^{1/2}}}left[1+{frac {1}{nu }}({mathbf {y} }-{boldsymbol {beta x_i }})^{T}{boldsymbol {Sigma }}^{-1}({mathbf {y} }-{boldsymbol {beta x_i }})right]^{-(nu +p)/2}}label{eq:2}
end{align}

Where $beta$ is unknown and the matrix $Sigma$ is parametrized as $sigma^2 Q.$

I would like to perform an EM algorithm.

If I am not mistaken, we have for the log-likelikehood
$$log L(Psi)=frac{-1}{2}nplog(2pi)-frac1{2}nlog vert Sigmavert-frac1{2sigma^2}sum_{j=1}^n z_j(y_j-beta x_i)^TQ^{-1}(y_j-beta x_i)$$

where I forgot everything about $nu$ because it supposed to be known.

Now we have

$$Zvert Y=ysim Gamma(m_1,m_2)$$ with $m_1=frac{1}{2}(nu+p)$ et $m_2=frac{1}{2}(nu+(y-mu)^TSigma(y-mu))$ for general $t_p(mu,Sigma,nu)$ distribution.

If I am doing the chameleon we have

$$Zvert Y=ysim Gamma(m_1,m_2)$$ with $m_1=frac{1}{2}(nu+p)$ et $m_2=frac{1}{2sigma^2}(nu+(y-mu_i)^T Q^{-1}(y-mu_i))$

In general case we have
begin{equation}
E_{Psi^{(k)}}(Z_jvert y_j)=frac{nu+p}{nu+Q(y_j,mu^{(k)},Sigma^{(k)})}
end{equation}

I can also do the chameleon here but I am pretty sure I miss something otherwise is trivial.

What am I missing ?

Get this bounty!!!

April 9, 2018

#StackBounty: #algorithms #computability #logic #search-problem Is there an analysis of the creation of axioms for a mathematical struc…

Bounty: 100

Historically, what has happened is the following:

There is a “mechanical” structure, most importantly, arithmetic, which operates according to a set of well-defined rules that a stupid computer can easily follow. e.g. a computer can easily calculate $5349cdot 5345=…$
There is a “mechanical” proof-system, most importantly, first order logic, which also operates according to well-defined rules that a stupid computer can follow. e.g. a computer can easily apply derivation rules to go from $forall x phi(x)$ to $exists x phi(x)$, etc.
Then there is a non-mechanical “creative” human, who uses his badly-understood “natural insight” to formulate a set of “axioms about arithmetic”, which are words in (2)’s language “about” the operations of (1)’s arithmetic computations. He also formulates a set of “logical axioms”, the rules by which the mechanical proof system should operate. He chooses these rules because his intuitive insight says that they are “obviously correct”.

It seems to me that this third element in the chain (though it happens first chronologically), is always done in an ad-hoc way. But the fact that this has always been done this way so far, doesn’t mean that it necessarily has to be this way.

My question is: Has there been an analysis of the creation of axioms as a computational problem? That is, of the problem of choosing axioms about some mathematical structure, for use in a logic-language?

This computational problem is essentially: given e.g. the rules of arithmetic, find a first-order statement that we can use as an axiom to then derive further properties.

ps. I know that this is a vague question. I am simply asking whether someone has analysed this problem in some way.

Get this bounty!!!

February 20, 2018

#StackBounty: #algorithms #optimization #linear-programming #convex-hull How to find the supremum of all the "good" (interior…

Bounty: 50

Let $S subset mathbf{R}^3$ be a set of point and let $O=(x_0,y_0,z_0)$ be the origin/point of reference.

We consider a convex polytope $P$ good / interior if:

$P$ is wholly contained within the interior of the convex hull of $S$:
$P subsetneq text{convexhull}(S)$.
$O$ is contained within the interior of $P$, namely: $O in P$.
none of the points in $S$ are in $P$ namely $S cap P = emptyset$.

Out of all good convex polytopes, we want to find either the maximum (supremum) of their volumes, i.e., $sup text{Vol}(P)$ where $P$ ranges over good polytopes.

Here is a 2D modest illustration (the green polytope might not be really the optimal):

The black dots are the set $S$, the origin $O$ is in the middle. The red lines go through the points in $S$ which define the boundary of $S$ (not a good polytope) and the green lines go through a good polytope.

Is there an efficient algorithm to compute this best convex and non-convex polytopes for a given set $S$ of points and origin $O$?

I would like to formulate this problem as an optimization problem or to come up with some algorithm using triangulation, $alpha$-shapes or $beta$-skeleton geometric transformation + convex hull, linear programming, maybe working in the dual space? etc.

One idea which I have is “pumping down” the convex hull of Delaunay Triangulation:

DT $leftarrow$ delaunayTriangulation($S cup O$)

CH $leftarrow$ convexHull(DT)

while Not empty(DT) and $O notin CH$:

$quad$ i. previousDT $leftarrow$ DT

$quad$ ii. update DT $leftarrow$ DT $setminus$ CH

return previousDT

EDIT: I think what I am looking for in a one-liner of math symbols is:

$$text{argmax}_{P} text{text{Vol}(P) , | , O in P setminus partial P , ; ,
Scap P = emptyset , ; , P subsetneq text{convexhull}(S) } $$

Where $partial P$ is the boundary of a polytope $P$.

Get this bounty!!!

February 18, 2018

#StackBounty: #algorithms #complexity-theory #linear-programming #convex-hull How to find the supremum of all the "good" (int…

Bounty: 50

Let $S subset mathbf{R}^3$ be a set of point and let $O=(x_0,y_0,z_0)$ be the origin/point of reference.

We consider a convex polytope $P$ good / interior if:

$P$ is wholly contained within the interior of the convex hull of $S$:
$P subsetneq text{convexhull}(S)$.
$O$ is contained within the interior of $P$, namely: $O in P$.
none of the points in $S$ are in $P$ namely $S cap P = emptyset$.

Out of all good convex polytopes, we want to find either the maximum (supremum) of their volumes, i.e., $sup text{Vol}(P)$ where $P$ ranges over good polytopes.

Here is a 2D modest illustration (the green polytope might not be really the optimal):

Is there an efficient algorithm to compute this best convex and non-convex polytopes for a given set $S$ of points and origin $O$?

One idea which I have is “pumping down” the convex hull of Delaunay Triangulation:

DT $leftarrow$ delaunayTriangulation($S cup O$)

CH $leftarrow$ convexHull(DT)

while Not empty(DT) and $O notin CH$:

$quad$ i. previousDT $leftarrow$ DT

$quad$ ii. update DT $leftarrow$ DT $setminus$ CH

return previousDT

EDIT: I think what I am looking for in a one-liner of math symbols is:

$$text{argmax}_{P} text{text{Vol}(P) , | , O in P setminus partial P , ; ,
Scap P = emptyset , ; , P subsetneq text{convexhull}(S) } $$

Where $partial P$ is the boundary of a polytope $P$.

Get this bounty!!!

February 18, 2018

#StackBounty: #algorithms #graphs #graph-theory #data-structures Graph algorithm or framework for determining node affinity based on ut…

Bounty: 50

I’m looking for an algorithm or framework for thinking about how to determine affinities between nodes. Perhaps affinity is poor choice of wording, but basically I want to use utilities between nodes to determine how alike or unalike they are from each other. I’ve attached an example diagram to illustrate what I mean:

In this example, Entities A and B are not well-aligned due to the negative utility between them. An appropriate algorithm or framework should identify that they belong to different groups, clusters, etc.

Additionally, I should be able to infer that Entities B and C are likely to be well-aligned, due to the mutual misalignment with A.

The utility magnitudes should also reflect the degree of alignment or misalignment. For example A2 and B3 should more more misaligned than A1 and B3.

To complicate things further, the utility “units” may be different, with multiple edges between nodes. As a simplifying assumption, I may be able to normalize utilities into a single edge and unit.

I apologize if this question is vague and/or ill-suited for this StackExchange. However I really don’t have a good lead on how to tackle such a problem.

Get this bounty!!!

February 16, 2018

#StackBounty: #algorithms #complexity-theory #linear-programming #convex-hull How to find the supremum of all the "good" poly…

Bounty: 50

Let $S subset mathbf{R}^3$ be a set of point and let $O=(x_0,y_0,z_0)$ be the origin/point of reference.

We consider a convex polytope $P$ good / interior if:

$P$ is wholly contained within the interior of the convex hull of $S$:
$P subsetneq text{convexhull}(S)$.
$O$ is contained within the interior of $P$, namely: $O in P$.
none of the points in $S$ are in $P$ namely $S cap P = emptyset$.

Out of all good convex polytopes, we want to find either the maximum (supremum) of their volumes, i.e., $sup text{Vol}(P)$ where $P$ ranges over good polytopes.

Here is a 2D modest illustration (the green polytope might not be really the optimal):

Is there an efficient algorithm to compute this best convex and non-convex polytopes for a given set $S$ of points and origin $O$?

One idea which I have is “pumping down” the convex hull of Delaunay Triangulation:

DT $leftarrow$ delaunayTriangulation($S cup O$)

CH $leftarrow$ convexHull(DT)

while Not empty(DT) and $O notin CH$:

$quad$ i. previousDT $leftarrow$ DT

$quad$ ii. update DT $leftarrow$ DT $setminus$ CH

return previousDT

EDIT: I think what I am looking for in a one-liner of math symbols is:

$$text{argmax}_{P} text{text{Vol}(P) , | , O in P setminus partial P , ; ,
Scap P = emptyset , ; , P subsetneq text{convexhull}(S) } $$

Where $partial P$ is the boundary of a polytope $P$.

Get this bounty!!!

February 15, 2018

#StackBounty: #algorithms #complexity-theory #linear-programming #convex-hull How to find the supremum of polytopes which are interior …

Bounty: 50

Let $S subset mathbf{R}^3$ be a set of point and let $O=(x_0,y_0,z_0)$ be the origin/point of reference.

We consider a convex polytope $P$ good / interior if:

$P$ is wholly contained within the interior of the convex hull of $S$:
$P subsetneq text{convexhull}(S)$.
$O$ is contained within the interior of $P$, namely: $O in P$.
none of the points in $S$ are in $P$ namely $S cap P = emptyset$.

Out of all good convex polytopes, we want to find either the maximum (supremum) of their volumes, i.e., $sup text{Vol}(P)$ where $P$ ranges over good polytopes.

Here is a 2D modest illustration (the green polytope might not be really the optimal):

Is there an efficient algorithm to compute this best convex and non-convex polytopes for a given set $S$ of points and origin $O$?

One idea which I have is “pumping down” the convex hull of Delaunay Triangulation:

DT $leftarrow$ delaunayTriangulation($S cup O$)

CH $leftarrow$ convexHull(DT)

while Not empty(DT) and $O notin CH$:

$quad$ i. previousDT $leftarrow$ DT

$quad$ ii. update DT $leftarrow$ DT $setminus$ CH

return previousDT

EDIT: I think what I am looking for in a one-liner of math symbols is:

$$text{argmax}_{P} text{text{Vol}(P) , | , O in P setminus partial P , ; ,
Scap P = emptyset , ; , P subsetneq text{convexhull}(S) } $$

Where $partial P$ is the boundary of a polytope $P$.

Get this bounty!!!