The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [algorithms]

An algorithm is a sequence of well-defined steps that defines an abstract solution to a problem. Use this tag when your issue is related to design and analysis of algorithms.

Filter by
Sorted by
Tagged with
4
votes
2answers
114 views

Message receipt verification in a cluster

At my current project I had a network problem come up for which I could not find a solution. In a peer-to-peer network I needed to send an action to all peers, and each peer was to act on it only if ...
1
vote
0answers
208 views

Finding a sequence of numbers where every product of two mod k is unique

I want to make a sequence of numbers, where I pick the numbers $a_{0}, a_{1},..,a_{n}$. The length of the sequence is $n+1$. Now I want the product of any pair of two numbers in the sequence modulo $...
4
votes
1answer
200 views

Semantic similarity in text

Is there a relatively simple way of telling if two pieces of text are semantically similar? Some assumptions that are valid: It is all english I have a list of all the important nouns Are there any ...
7
votes
1answer
124 views

Find all the special graphs which can reduced to the shortest paths graph

I have a directed weighted graph $G = (V, E, W)$. There is always an edge from a vertex $i$ to another one $j$, the weight $w(i,j)$ could be positive infinity, and there does not exist any negative ...
11
votes
1answer
653 views

Bound on space for selection algorithm?

There is a well known worst case $O(n)$ selection algorithm to find the $k$'th largest element in an array of integers. It uses a median-of-medians approach to find a good enough pivot, partitions ...
10
votes
2answers
214 views

Determining the particular number in $O(n)$ time and space (worst case)

$\newcommand\ldotd{\mathinner{..}}$Given that $A[1\ldotd n]$ are integers such that $0\le A[k]\le m$ for all $1\le k\le n$, and the occurrence of each number except a particular number in $A[1\ldotd n]...
11
votes
4answers
3k views

Most efficient algorithm to print 1-100 using a given random number generator

We are given a random number generator RandNum50 which generates a random integer uniformly in the range 1–50. We may use only this random number generator to ...
1
vote
2answers
476 views

Existence of a route following one-way streets

I am trying to understand the approach for this problem: "If all streets are one way, there is still a legal way to drive from one intersection to another" The question is to prove that it can ...
10
votes
1answer
213 views

Determining how similar a given string is to a collection of strings

I'm not sure if this question belongs here and I apologize if not. What I am looking to do is to develop a programmatic way in which I can probabilistically determine whether a given string "belongs" ...
4
votes
1answer
365 views

Choosing an element from a set satisfying a predicate uniformly at random in $O(1)$ space

We are given a set of objects, say integers, $S$. In addition, we are given a predicate $P$, for example $P(i): \Leftrightarrow i \geq 0$. We don't know in advance how many elements of $S$ satisfy the ...
11
votes
2answers
1k views

Minimize the maximum component of a sum of vectors

I'd like to learn something about this optimization problem: For given non-negative whole numbers $a_{i,j,k}$, find a function $f$ minimizing the expression $$\max_k \sum_i a_{i,f(i),k}$$ An example ...
2
votes
1answer
583 views

Reason for global update steps in the push-relabel algorithm

I know why and how the push relabel algorithm works for solving the max-flow problem. But why is a global update step required?
11
votes
1answer
1k views

Tighter analysis of modified Borůvka's algorithm

Borůvka's algorithm is one of the standard algorithms for calculating the minimum spanning tree for a graph $G = (V,E)$, with $|V| = n, |E| = m$. The pseudo-code is: ...
6
votes
2answers
672 views

An edge that connects more than two nodes in a graph?

Is there a way to create a single edge on a graph that connects 3 or more nodes? For example, let's say that the probability of Y occurring after X is 0.1, and the probability of Z occurring after Y ...
4
votes
1answer
529 views

From in-order representation to binary tree

Is there a way to reconstruct a binary tree just from its in-order representation? I've searched the internet, but I could only find solutions for reconstructing a binary tree from inorder and ...
4
votes
1answer
576 views

Finding a minimal containing rectangle from a given set of rectangles

The problem is as follows: Given a finite set of rectangles ($S\subset\mathbb{R}\times\mathbb{R}$), build a data structure that will support the following operations: Check, receives a rectangle $r\...
5
votes
1answer
2k views

Polygons generated by a set of segments

Given a set of segments, I would like to compute the set of closed polygons inside the convex hull of the set of the end of those segments. The vertices of the polygons are the intersections of the ...
2
votes
2answers
3k views

Function Maximization in Java

I have a bivariate function like $ f(x,y) = \frac{1}{x^3 \sqrt{\pi}}. e^{\frac{2-x}{x^2}} . y^3 . e^{3.y \over 3-y} $ and I want to find its global maximum over a range of $ x \in [0, 200] \text{, ...
3
votes
1answer
560 views

How to random-generate a graph with Pareto-Lognormal degree nodes?

I have read that the degree of nodes in a "knowledge" graph of people roughly follows a power law distribution, and more exactly can be approximated with a Pareto-Lognormal distribution. Where can I ...
14
votes
1answer
11k views

Expected number of swaps in bubble sort

Given an array $A$ of $N$ integers, each element in the array can be increased by a fixed number $b$ with some probability $p[i]$, $0 \leq i < n$. I have to find the expected number of swaps that ...
4
votes
1answer
261 views

Vertex coloring with an upper bound on the degree of the nodes

Consider the set of graphs in which the maximum degree of the vertices is a constant number $\Delta$ independent of the number of vertices. Is the vertex coloring problem (that is, color the vertices ...
7
votes
4answers
17k views

Using Dijkstra's algorithm with negative edges?

Most books explain the reason the algorithm doesn't work with negative edges as nodes are deleted from the priority queue after the node is arrived at since the algorithm assumes the shortest distance ...
5
votes
1answer
571 views

Algorithm for type conversion / signature matching

I'm working on an expression typing system and looking for insights on what algorithms may be available which solve my problem -- or a proof that its complexity is too high to be reasonable to ...
4
votes
1answer
163 views

Why is solving of diagonal quadratic equations over $\mathbb R$ and $\mathbb C$ in $P$?

Let $\mathbb F\in\{\mathbb R, \mathbb C\}$ the field of real or complex numbers. Then [1, page 22 in the middle] claims that the following equation can easily be solved in deterministic polynomial ...
3
votes
1answer
230 views

What is the significance of the semi clustering formula in the Google Pregel paper?

Semi clustering algorithm is mentioned in the Google Pregel paper. The score of a semi cluster is calculated using the below formula $\qquad \displaystyle S_c =\frac{I_c - f_BB_c}{\frac{1}{2}V_c(V_c -...
7
votes
2answers
508 views

Balanced weighting of edges in cactus graph

Given a cactus, we want to weight its edges in such a way that For each vertex, the sum of the weights of edges incident to the vertex is no more than 1. The sum of all edge weights is maximized. ...
8
votes
1answer
545 views

How to detect stack order?

We take the sequence of integers from $1$ to $n$, and we push them onto a stack one by one in order. Between each push, we can choose to pop any number of items from the stack (from 0 to the current ...
7
votes
1answer
337 views

In s-t directed graph, how to find many small cuts?

Solving the maximum flow problem yields one qualified minimal cut. But I want several (maybe hundreds) small cuts as candidates. The cuts don't have to be minimum cuts, as long as they are small (in ...
7
votes
1answer
298 views

Algorithm to test a graph for $t$-transitivity

I am looking for an algorithm, which given a graph $G$ and a natural number $t$, determines if $G$ is $t$-transitive. I am also interested in knowing if this problem is in P, NP, NPC or some other ...
6
votes
1answer
529 views

Find string that minimizes the sum of the edit distances to all other strings in set

I have a set of strings $S$ and I am using the edit-distance (Levenshtein) to measure the distance between all pairs. Is there an algorithm for finding the string $x$ which minimizes the sum of the ...
8
votes
2answers
563 views

Minimizing the total variation of a sequence of discrete choices

My setup is something like this: I have a sequence of sets of integers $C_i (1\leq i\leq n)$, with $|C_i|$ relatively small - on the order of four or five items for all $i$. I want to choose a ...
13
votes
1answer
5k views

Getting parallel items in dependency resolution

I have implemented a topological sort based on the Wikipedia article which I'm using for dependency resolution, but it returns a linear list. What kind of algorithm can I use to find the independent ...
4
votes
2answers
4k views

Efficiently calculating minimum edit distance of a smaller string at each position in a larger one

Given two strings, $r$ and $s$, where $n = |r|$, $m = |s|$ and $m \ll n$, find the minimum edit distance between $s$ for each beginning position in $r$ efficiently. That is, for each suffix of $r$ ...
2
votes
2answers
1k views

How to use dynamic programming to solve this?

Here is the question: suppose we are given x cents, the amount we want to pay, and a 6-tuple (p, n, d, q, l, t) that represents respectively the number of pennies, nickels, dimes, quarters, loonies ...
5
votes
1answer
451 views

Prove that for a general data structure - operations Extract_min() and Insert(x) cost $\Omega(\log n)$?

I've been given the following problem: Given a data structure $M$ that is based on comparisons and supports the following methods on a group of numbers $S$: $\text{Insert}(x)$ – add $x$ to $S$ $\...
8
votes
1answer
715 views

CLRS - Maxflow Augmented Flow Lemma 26.1 - don't understand use of def. in proof

In Cormen et. al., Introduction to Algorithms (3rd ed.), I don't get a line in the proof of Lemma 26.1 which states that the augmented flow $f\uparrow f'$ is a flow in $G$ and is s.t. $|f\uparrow f'| ...
1
vote
0answers
37 views

constrained cover on biparite graphs [duplicate]

Possible Duplicate: Restricted version of vertex cover Suppose we have a $(A,B,E)$ bipartite graph and a positive integer k. Suppose that k is smaller than $|A|$ and we want to find one of those ...
3
votes
1answer
465 views

Efficient bandwidth algorithm

Recently I sort of stumbled on a problem of finding an efficient topology given a weighted directed graph. Consider the following scenario: Node 1 is connected to 2,3,4 at 50 Mbps. Node 1 has 100 ...
6
votes
3answers
1k views

What is the bitwise xor of an interval?

Let $\oplus$ be bitwise xor. Let $k,a,b$ be non-negative integers. $[a..b]=\{x\mid a\leq x, x\leq b\}$, it is called a integer interval. What is a fast algorithm to find $\{ k\oplus x\mid x\in [a..b]...
3
votes
2answers
16k views

Finding the number of distinct permutations of length N with n different symbols

I have one puzzle whose answer I have boiled down to finding the total number and which type of permutation they are. For example if the string is of length ten as $w = aabbbaabba$, the total number ...
9
votes
4answers
5k views

Shortest distance between a point in A and a point in B

Given two sets $A$ and $B$ each containing $n$ disjoint points in the plane, compute the shortest distance between a point in $A$ and a point in $B$, i.e., $\min \space \{\mbox{ } \text{dist}(p, q) \...
3
votes
1answer
167 views

Improve Markov Chain results

Apologies for another Markov Chain question but this one is best given its own question to avoid confusion. I am using a Markov Chain to get the 10 best search results from the union of 3 different ...
7
votes
1answer
3k views

If any 3 points are collinear

Given a set $S$ of points $p_1,..,p_2$ give the most efficient algorithm for determining if any 3 points of the set are collinear. The problem is I started with general definition but I cannot ...
27
votes
1answer
8k views

Which combinations of pre-, post- and in-order sequentialisation are unique?

We know post-order, post L(x) => [x] post N(x,l,r) => (post l) ++ (post r) ++ [x] and pre-order ...
2
votes
1answer
126 views

Algorithm to check the 2∀-connectness property of a graph

A graph is 2∀-connected if it remains connected even if any single edge is removed. Let G = (V, E) be a connected undirected graph. Develop an algorithm as fast as possible to check 2∀-connectness of ...
4
votes
1answer
584 views

Building ideal skip lists

I'm trying to find the best algorithm for converting an “ordinary” linked list into an “ideal" skip list. The definition of an “ideal skip list” is that in the first level we'll have all the ...
3
votes
1answer
338 views

Restricted version of vertex cover

I am interested in the complexity of the restricted version of the vertex cover problem below: Instance: A bipartite graph $G =(L, R, E)$ and an integer $K$. Question: Is there $S \subset L$, $...
3
votes
2answers
398 views

Generating number of possibilites of popping two stacks to two other stacks

Context: I'm working on this problem: There are two stacks here: A: 1,2,3,4 <- Stack Top B: 5,6,7,8 A and B will pop out to other two stacks: C and D....
6
votes
2answers
213 views

Finding the point nearest to the x-axis over some segment

I have problem with solving the following exercise Given the set $P$ on $n$ points in two dimensions, build in time $O(n\log n)$ a data structure of $P$ such that given a horizontal segment $s$ ...
4
votes
1answer
200 views

Is the following recurrence for this program's runtime correct?

Let $f$ and $g$ be two functions and $p$ a number. Consider the following program: ...