# 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.

10,508 questions
Filter by
Sorted by
Tagged with
621 views

### Why not relax only edges in Q in Dijkstra's algorithm?

Can someone tell me why almost in every book/website/paper authors use the following: foreach vertex v in Adjacent(u) relax(u,v) when relaxing the edges, ...
520 views

### Where is the mistake in this apparently-O(n lg n) multiplication algorithm?

A recent puzzle blog post about finding three evenly spaced ones lead me to a stackoverflow question with a top answer that claims to do it in O(n lg n) time. The interesting part is that the solution ...
12k views

### Difference between := and ← in pseudocode

This is a snippet from some pseudocode for a sorting algorithm. In it, the symbol ← is used to denote assignment, for example for the variable done. However, in the ...
1 vote
808 views

### Simple routing table question

I'm having difficulties understanding the solution to the following question: Consider the following description of a LAN: The main Internet connection is connected to our gateway router. This ...
2k views

### Using transitive closure to determine acyclic property on directed graph

Is it possible to use Warshall's algorithm (calculating the transitive closure) to determine if a directed graph is acyclic or not? I'm trying to achieve this but getting stuck on the reflexive ... 3k views

### Optimal algorithm for finding all ngrams from a pre-defined set in a text

I'm thinking about the optimal algorithm for the following problem: Input data: a text, say it's an article about 5-50 pages. a set of ngrams (ngram strings, n>2), of arbitrary length, could be more ...
1 vote
793 views

### Input that causes an operation on a binomial heap to run in $\Omega(\log n)$ time?

I was studying binomial heaps and its time analysis. Are there any inputs that cause DELETE-MIN, DECREASE-KEY, and DELETE to run in $\Omega(\log n)$ time for a binomial heap rather than $O(\log n)$?
388 views

194 views

### Compare vectors, photo mosaic

I’m trying to make a photo mosaic web application. I split the main picture in to a number of squares. I split this square up in to 9 squares. Then I calculate the mean color (RGB) of the entire ...
1k views

### An online parallel algorithm for finding top K elements

Suppose we have a function on GPU which calculates elements of array from which we need to select top K elements. The number of elements can be quite big so we can't store them in memory and our ...
915 views

### What does big O mean as a term of an approximation ratio?

I'm trying to understand the approximation ratio for the Kenyon-Remila algorithm for the 2D cutting stock problem. The ratio in question is $(1 + \varepsilon) \text{Opt}(L) + O(1/\varepsilon^2)$. ... 2k views

### Find all increasing/decreasing sub array

I have a question that I still struggle with. It would be really appreciated if you guys could give me some hints. Here is the problem : Assume that $a[1\dots n]$ is an array of $n$ positive real ...
30k views

### What is the fastest algorithm for finding all shortest paths in a sparse graph?

In an unweighted, undirected graph with $V$ vertices and $E$ edges such that $2V \gt E$, what is the fastest way to find all shortest paths in a graph? Can it be done in faster than Floyd-Warshall ...
667 views

### Bellman-Ford: shortest path

my assumption: - we have an undirected graph with only positive edges - the edges are sorted alphabetically:     e.g A-B, A-C, B-D     and e.g not C-A, D-B, A-...
6k views

### SSTF disk scheduling algorithm? What if lowest seek times are equal in either direction?

Using the Shortest-Seek-Time-First (SSTF) disk scheduling algorithm (where we select a request with a minimum seek time from the current head position), what happens if the requests in both directions ...
3k views

### Finding maximum and minimum of consecutive XOR values

Given an integer array (maximum size 50000), I have to find the minimum and maximum $X$ such that $X = a_p \oplus a_{p+1} \oplus \dots \oplus a_q$ for some $p$, $q$ with $p \leq q$. I have tried this ...
2k views

### Data structures and algorithms for bridge game play?

In a bridge game, a deck of 52 cards (13 spades , 13 clubs, 13 diamonds, 13 spades) are dealt to 4 players (13 cards each) then game starts.Game session ends after 13 tricks each having 4 cards.There ...
1k views

### XOR-like behavior in flow networks

XOR is not the correct name, but I am looking for some kind of exclusive behavior. I am currently solving a set of different (assignment) problems by modeling flow networks and running a min-cost-max-...
1 vote
279 views

### Label Assignment Problem

I try to solve an exercise in Distributed Algorithm described as follow. Let's define a label assignment problem as follow. There is a anonymous network (vertices don't have unique ID's , nodes don't ...
196 views

### Shortest paths graph

Given a directed graph $G$, edge weights for each edge, source vertex $s$ and $d[v]$ for each vertex in the graph (the distance from $s$ to $v$), I need to find an algorithm that builds the shortest ...
1 vote
787 views

### Bellman-Ford algorthm and negative cycle proof

I found the algorithm for finding the negative cycle in a graph after running Bellman-Ford algorithm. The algorithm is to perform another relax iteration over all the edges. Than if we find an edge ...
328 views

### Logarithmic space difference between deterministic and non-deterministic algorithms

I had an interview today, and the interviewer has told me about a theorem (of someone called Hill- or Hell-something) which states that for a non-deterministic algorithm there exists a deterministic ...
8k views

### The stable marriage algorithm with asymmetric arrays

I have a question about the stable marriage algorithm, for what I know it can only be used when I have arrays with the same number of elements for building the preference and the ranking matrices. ...
636 views

### Single machine job scheduling to minimize weighted sum of completion time

Given $n$ jobs, schedule them such that the weighted sum is minimum. weighted minimum sum S for the schedule $\sigma = \{ J_1, J_2, ... J_n \}$ is given by : $S = \sum_{1\leqq i \leqq n} w_i C_i$ ...
1k views

### Maximum weight matching

There are polynomial time algorithms to find maximum weighted matching in a general graph. Is there any algorithm that also handles negative weights in the general graph and find maximum weighted ... 73 views

### Prove given equality check function works for all subset of integers

I wrote a function to check equality between integers a and b using bitwise shift operators. Return value of ...
1k views

### How to recognize a STRIPS planning problem has no solution?

Strips –Stands for STanford Research Institute Problem Solver (1971). STRIPS Pseudo code - ...
3k views

### Algorithm for getting the outer boundary of a large graph

I am trying to create an isochrone based on the OpenStreetMap data set. Everything works fine, I extracted data, processed it into a DAG, ran a Dijkstra algorithm over it. The result is a subset of ...
171 views

### Is there an efficient method to store large DAGs?

I have a DAG representing strict partial order where each node is an assignment of variables $V$ to their values $v$. Each arc $(u,w)$ represents a change in one variable value such that $u\succ w$. ...
1 vote
138 views

### Summation of $O(n)$ from $1\le k\le n$

Summation of $O(n)$ from $1\le k\le n$. I think it should be $O(n)$ only. Because we are addition $O(k)$ and maximum order will be $O(n)$. But answer is given as $O(n^2)$. Correct me if I'm wrong.
I am trying to understand the distributed 6-color algorithm for vertex coloring (on page 10). Here is a short description Idea of the algorithm: We start with color labels that have $\log n$ bits. ...