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.

7,657 questions
Filter by
Sorted by
Tagged with
16 views

How do we determine whether a heuristic is better than another in A* search Algorithm?

I am trying to solve a Maze puzzle using the A* algorithm. I am trying to analyze the algorithm based on different applicable heuristics. Currently, I explored Manhattan and Euclidean distances. ...
26 views

How is the right, root, left order traversal called in a binary search tree?

In a Binary Search Tree you have the following orders for traversal: Left, Root, Right is called Inorder (or ascending order). Root, Left, Right is called Preorder. Left, Right, Root is called ...
23 views

Algorithm for out-of-area point classification

I have a device that sends its coordinates every 30 seconds. When I receive the coordinates, I classify the point as either belonging to (ie being inside) one of a number of predefined areas (so I ...
37 views

C++ finding the shortest path, reducing time complexity, dijkstra v Floyd Warshall Algorithm?

I have an algorithm that I am performing on a graph and I am looking to do an analysis of how to speed it up and would appreciate any comments. The algorithm iterates over every edge in the graph. ...
26 views

Impossible recurrence relation help with masters theorem, plus evaluation of complexity

I had an exercise to solve a recurrence relation in my exam, I think it was a tricky question but I am not 100% sure. The recurrence was $T(n) = 2*T(n) + \sqrt{n} +42$, it was specifically asked to ...
68 views

Minimum path cover in a DAG

Given a directed acyclic graph $G=(V,A)$ and a set $A'$ of $A$. It is well known that searching for a minimum number of vertex-disjoint paths that cover all the vertices of $G$ can be solved in ...
19 views

AVL Tree confusion

I have some confusion with regards to AVL trees and the heights of various subtrees. When initially reading the overview of the algorithms purpose(to keep the tree balanced) I thought it put limits ...
45 views

Generate all combinations of values that are less than array's elements and have a sum = target

I want to find a way to generate sets that contain elements that sum to a certain target. Initially, I have an array that contains elements representing the maximum value that can be stored in that ...
7 views

Algorithm for Autonomously Culling Swarm

I'm trying to find an algorithm that would be able to cull a swarm of unknown size to around a known number with no overarching controller or dynamic registry (Each node should be able to decide ...
35 views

Why does Bellman-Ford algorithm use < rather than ≤?

The Bellman-Ford Algorithm uses a less-than symbol rather than a less-than-or-equal-to symbol. How does this identify that there is a negative cycle? For instance, say I have the below example going ...
26 views

...
69 views

Algorithm to find a simple path with maximum weight less than a constant in DAG

Given a weighted directed acyclic graph $G=(V,E,W)$, where the weights are non-negative and are on the vertices. I am searching for a simple path of maximum total weight, but this total weight should ...
54 views

What is the Time complexity of this sorting algo?

So i was trying to write an efficient sorting algorithm and i came up with this method, Sorting an array in ascending order by flipping (exchanging) 2 adjacent integers not in the correct order ...
23 views

Time complexity of simple function related to bits

I am wondering about correct answer to this task from a yesterday's test: A function Pow which calculates $y = a^k$ is given, where $k$ is an integer of length ...
11 views

String filtering - process hundreds to millions of filters

What would be the most efficient way (whether with algorithims, cpu(s), DBs & SQL, distributed computing, etc) to process many strings, say ~1000/minute, and filter each string over 100s to ...
25 views

43 views

How to find all the edges shared by all diametral paths of a tree?

A diametral path in a graph is a shortest path whose length is equal to the diameter of the graph. Now, given a tree with $n$ nodes, I would like to find the set of edges (possibly empty) which are ...
39 views

Number of bits needed to represent an integer with a specifed base

How many bits are required to represent an integer $x$ with base $b$?
25 views

Minimum amount of rectangles to create a 2-dimensional matrix

From this codegolf question. Consider an $r$ by $c$ matrix of nonnegative integers, called $M$. You also have a zero matrix of the same dimensions, called $N$. A "move" consists of replacing a ...
30 views

Point of Interest Problem

You are in a xy plane with a set of points F. You also have a collection P of N sets { P1,...., Pn} where each of the set consist of points of the form (Px,Py). Each set has a different number of ...
43 views

How to solve following tree problem?

Source of the problem is https://codeforces.com/contest/1152/problem/D . I think i understood the problem , but if possible please explain the problem in simple way and the solution also .I tried very ...
13 views

Maximizing total value given bound on total cost

I have a list of pairs with values and costs: | value | cost | 11, 1000 7, 700 7, 700 6, 700 2, 400 2, 500 1, 600 The ...
34 views

Absolute minimum difference

We are given a array of positive numbers. We can perform two types of operations on these sequence of numbers. If number E is even, then we can replace it by E/2 If number E is odd, then we can ...
19 views

47 views

Compute highest-scoring segmentation

I have the following problem: There is a "clean" sequence of sequences, say: clean = [ [1, 2], , [4, 5] ] And a "noisy" sequence which is not ...
20 views

Interpreting algorithm time complexity analysis

Lets say we have the following loop and want to find its time complexity: ...
43 views

Which algorithm to detect errors in 32bit data with 8bit parity

I want to transmit a 32bit message in eight groups of 5bit each. This leaves me with 8bits to use for error checking. Overall, a group is likely transmitted without error, but when there is an error ...
33 views

Visit every dot with a line

I have this problem where I want to fill every black shape with a line. Every dot of the shape needs to be visited by the line. Preferably creating the shortest line. Any idea how I can achieve this ...
33 views

How to move spheres in 3d without collision

Is there an algorithm that gets as an input 2 arrays (arr_origin, arr_dest) that represent spheres with a set radius (R) in a 3d space, (x,y,z) points. And finds a route for the spheres from origin to ...
52 views

Keeping track of best algorithms

Is there a site that keeps track of the "current best algorithms", e.g., for certain combinatorial optimization problems? In the latter there exists a range of classic problems such as MIN st-CUT or ...
15 views

Method of solving the largest sum in 2d matrices : the well known method is using kanades algorithm with the sum starting from every left to right boundaries , getting the largest sum of the sums and ...
48 views

23 views

Approximately counting the number of marked elements in a list of n numbers

Assume that we have n sealed boxes. There are k boxes with a ball inside. The goal is to approximate k by an additive error epsilon, using the minimum number of box probing. I know that this is ...
33 views

Finding the rightmost element in an array of duplicate elements using binary search

i was reading Binary Search in the wikipedia and i came across this part of 'rightmost index of an element in an array of duplicate elements'. i understood the process of determining the leftmost ...