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, ...
• 421
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 ...
• 5,722
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 ...
• 2,785
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 ...
• 153
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 ...
• 123
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)$?
• 111
388 views

• 6,061
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 ...
• 161
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-...
• 421
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 ...
• 255
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 ...
• 17
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 ...
• 3,149
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 ...
• 121
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 ...
• 121
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 ...
• 121
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. ...
• 163
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$ ...
• 1,239
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 - ...
• 765
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 ...
• 143
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$. ...
• 677
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.
1k views

Distributed 6-color Vertex Coloring

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. ...
• 3,149