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
5 votes
2 answers
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, ...
user avatar
  • 421
15 votes
2 answers
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 ...
user avatar
  • 5,722
6 votes
1 answer
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 ...
user avatar
  • 2,785
1 vote
1 answer
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 ...
user avatar
2 votes
2 answers
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 ...
user avatar
2 votes
4 answers
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 ...
user avatar
  • 123
1 vote
1 answer
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)$?
user avatar
0 votes
1 answer
388 views

Understanding a few intricacies related to two naive algorithms to compute the convex hull of a set of points

I already understood how the well-known algorithms like Graham's scan, Quickhull, etc. work, but I have difficulties in understanding 2 naive algorithms to compute the convex hull: Let $S= \{p_1, \...
user avatar
  • 421
2 votes
1 answer
88 views

Optimization of Hierarchical Data Propagation

I have a system in existence which works on parent-child model. They share common attributes, as they belong to same class. A parent can enforces certain data on any user selected attribute, and the ...
user avatar
  • 121
5 votes
1 answer
233 views

Lamarckian and Genetic algorithm

Yesterday I've done some research how to optimize genetic algorithm and I've encountered a very interesting theory that we can use Lamarckian theory (adaptive theory) to optimize the neural network. ...
user avatar
4 votes
2 answers
2k views

Scheduling algorithm to minimize maximum deadline overshoot in pre-emptive scheduler

Suppose there are $n$ tasks, which need to be scheduled by a pre-emptive scheduler. Each task $T_i$ has a deadline $d_i$ and a total processing time $t_i$ associated with it. Now, all $n$ tasks are ...
user avatar
  • 325
14 votes
4 answers
5k views

Algorithms computing if a number is a multiple of 3

When doing mental calculus one can do: Given an integer k, sum all the digits (in base 10), and if the result is a multiple of 3, then k is a multiple of 3. Do you know of any algorithm working ...
user avatar
4 votes
1 answer
690 views

Algorithm for determining minimal set of covering prefixes

I have a set of strings. My goal is to find a minimal set of longest prefixes which will match most of that set. For instance, if my set is: ...
user avatar
1 vote
1 answer
81 views

How is this algorithm in these two complexities?

How is an algorithm with complexity $O(n \log n)$ also in $O(n^2)$? I'm not sure exactly what its saying here, I feel it may be something to do with the fact that big-oh is saying less than or equal ...
user avatar
0 votes
1 answer
2k views

Algorithm for finding the longest common subsequence using hash table. Why is it slow?

I've designed an algorithm to find the longest common subsequence. The steps are: Start with i = 0 Picks the first letter from the first string start from $i^{th}$ ...
user avatar
1 vote
2 answers
571 views

Broken stick problem

We have a broken stick. For every part, we know it's length. Our task is to connect all parts (glue them), that we will use as small amount of glue as possible. The amount of glue need to connect ...
user avatar
  • 135
8 votes
1 answer
121 views

sum of like indices in circular lists

Consider the following problem: Let a $k$-wheel be defined as an indexed circularly linked list of $k$ integers. For example… {3, 4, 9, -1, 6} …is a 5-wheel with 3 at position 0,...
user avatar
2 votes
1 answer
458 views

Maximimal Independent Set on Ring and Path

Let's consider distributed version of algorithm for finding MIS of any graph $A$. For details, MIS - Maximimal Independent Set. Slow version of distributed algorithm for MIS, page 2 - Distributed ...
user avatar
  • 3,149
0 votes
1 answer
105 views

Smoothing frequencies without count data

I have frequency data for different events under two conditions, resulting in sets of frequencies F1 and F2. I would like to normalize the frequencies of events under condition 1 by their frequencies ...
user avatar
  • 176
-1 votes
3 answers
3k views

Good explanatory resource for algorithm techniques such as greedy, backtracking and recursive functions

What would be a good book/resource that explains the basic idea behind those techniques, how to use (and maybe when to use them) and plenty of exercises with perhaps some worked examples (kind of like ...
user avatar
5 votes
0 answers
143 views

Will the Mersenne Twister PRNG eventually produce all integer sequences of a certain length?

I'm attempting to use the MT19937 variant of the Mersenne Twister PRNG to accomplish something. Whether or not this something is feasible depends upon the answers to these two questions: What is the ...
user avatar
2 votes
1 answer
214 views

Non-deterministic algorithm for solving figure of 8

I am struggling in trying to figure out a non-deterministic algorithm for the following problem. Consider the following problem, called the figure-of-eight problem (FOE). An instance is an undirected ...
user avatar
  • 23
1 vote
3 answers
11k views

DFS - Proof of Correctness

I'm currently studying the book "Introduction to Algorithms - Cormen". Although a proof of correctness for the BFS algorithm is given, there isn't one any for the DFS in the book. So I was courious ...
user avatar
  • 421
2 votes
0 answers
1k views

k-Trees Graph Coloring

There is an exercise in Distributed Algorithm I have some difficulties to solve. There are few ideas, however nothing useful at the time. I will appreciate any help with it. Graph $G$ is a $k$-tree ...
user avatar
  • 3,149
0 votes
1 answer
1k views

Notation Conventions for Tree Data Structures

I'm currently working on a paper describing a new algorithm in computational science. If all goes well, this algorithm will be around for a while (within the specific community). As such, I want to ...
user avatar
5 votes
1 answer
234 views

Finding containing sets in a set of sets

Suppose I have a set of sets of integers $A$, is there an efficient algorithm/data structure that will allow me to query for all sets of integers that include a given input set? That is, given input $...
user avatar
  • 6,061
2 votes
0 answers
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 ...
user avatar
6 votes
1 answer
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 ...
user avatar
  • 161
3 votes
5 answers
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)$. ...
user avatar
0 votes
2 answers
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 ...
user avatar
  • 9
26 votes
3 answers
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 ...
user avatar
2 votes
1 answer
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-...
user avatar
  • 421
2 votes
1 answer
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 ...
user avatar
8 votes
3 answers
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 ...
user avatar
  • 255
0 votes
1 answer
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 ...
user avatar
  • 17
8 votes
4 answers
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-...
user avatar
1 vote
1 answer
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 ...
user avatar
  • 3,149
0 votes
3 answers
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 ...
user avatar
  • 121
1 vote
0 answers
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 ...
user avatar
  • 121
2 votes
0 answers
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 ...
user avatar
5 votes
2 answers
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. ...
user avatar
  • 163
6 votes
1 answer
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$ ...
user avatar
  • 1,239
2 votes
2 answers
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 ...
user avatar
-1 votes
1 answer
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 ...
user avatar
3 votes
1 answer
1k views

How to recognize a STRIPS planning problem has no solution?

Strips –Stands for STanford Research Institute Problem Solver (1971). STRIPS Pseudo code - ...
user avatar
  • 765
4 votes
3 answers
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 ...
user avatar
  • 143
2 votes
1 answer
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$. ...
user avatar
1 vote
3 answers
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.
user avatar
4 votes
1 answer
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. ...
user avatar
  • 3,149
12 votes
1 answer
11k views

Remove minimum number of vertices to disconnect the graph

Consider an undirected graph with a source and a sink vertex. We would like to remove minimum number of vertices in that graph to disconnect any path between source and sink. Can we do this using say ...
user avatar
  • 121

1
198 199
200
201 202
211