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
0
votes
1answer
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. ...
0
votes
1answer
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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. ...
0
votes
0answers
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 ...
1
vote
0answers
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 ...
0
votes
0answers
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 ...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
2
votes
1answer
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 ...
-1
votes
1answer
26 views
3
votes
1answer
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 ...
-1
votes
1answer
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
1
vote
1answer
25 views

Complexity analysis using big - O, Omega and Theta notation

I was reading a research paper and there I read the following: $t=O\left(d^{2} \log _{d}^{2} n\right)$ matches the lower bound $\Omega\left(d^{2} \log _{d} n\right)$ in the regime where $d=\Theta\...
3
votes
1answer
117 views

Minimum Path cover in a Directed Acyclic Graph

Given a weighted directed acyclic graph $G=(V,D,W)$ and a set of arcs $D'$ of $D$, where the weights of $W$ are on the vertices. The problem is to partition $G$ into a minimum number of vertex-...
1
vote
1answer
27 views

Coloring book. Finding region by point

Let me explain what I want to achieve. I'm working on the coloring book project. On the input, I'm getting transparent images with black borders (Like this). Currently, I've created the 2D ...
2
votes
0answers
72 views

Decision Tree for searching an element in an n*n matrix

I just learnt decision tree concept in class. I have a question for homework. It says to prove that for searching an element in n*n matrix the lower bound is logn and prove it using decision tree. My ...
3
votes
1answer
19 views

Choosing which workers (limited number) to use in a binary assignment problem?

First of all, I am not completely sure whether this problem belong to the category of assignment problems so feel free to correct me in this case. The problem: We are given a set of $m$ workers $A = ...
4
votes
1answer
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 ...
0
votes
1answer
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$?
0
votes
0answers
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 ...
0
votes
0answers
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 ...
2
votes
0answers
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 ...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
1
vote
1answer
19 views

How to schedule events optimally given when the events are available?

Suppose I had a dictionary that contains events and the corresponding periods they are occurring. For example: $$ \begin{align} \textrm{Event 1} &\rightarrow \textrm{[1, 2, 3]} \\ \textrm{Event 2}...
0
votes
1answer
54 views

Longest path in a directed acyclic graph with constraints

Given a directed weighted acyclic graph G=(V,D,W) and a subset of edges D' of D. The problem is to find the longest path in G that passes by exactly one edge of D'. What is the complexity of this ...
0
votes
1answer
20 views

Help with Linear recurrence relation with balanced partition

In my slides for my algorithms class, I have a method of finding complexity of recursive functions called Recurrence Relation with "partizione bilanciata" which means "balanced partition". My course ...
0
votes
3answers
58 views

Minimum index Array Product

Given an array A(1 indexed based) of positive integers.For each element A[i] find the minimum index (say idx) such that the product of all the elements from index 1 to idx is divisible by A[i].where(...
1
vote
1answer
22 views

Difference between UCB1 and UCT

In Bandit Based Monte-Carlo Planning by Levente Kocsis and Csaba Szepesvári (2006) they propose the UCT algorithm which is derived from the UCB1 algorithm. UCB1 algorithm: $$X_j + \sqrt{\frac{2\ln n}...
3
votes
2answers
47 views

Compute highest-scoring segmentation

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

Interpreting algorithm time complexity analysis

Lets say we have the following loop and want to find its time complexity: ...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
1
vote
1answer
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 ...
0
votes
0answers
15 views

2d kanades algorithm

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 ...
2
votes
1answer
48 views

Like transitive reduction, but removing vertices rather than edges?

Suppose I have a directed graph $G = (V, E)$ (or, which is the same, a relation on the set $V$ as defined by the adjacency matrix) that may contain three vertices $x, y, z$, such that $xy, xz, yz \in ...
3
votes
0answers
24 views

Gin heuristic algorithm design

(Apologies if this or an equivalent question has been asked in the past; I didn't see anything that answered this question.) I'm designing an algorithm to compute a heuristic for a Gin game engine. (...
2
votes
1answer
34 views

Are there any benefits of implementing the Fisher–Yates shuffle algorithm from tail to head instead of head to tail?

I was looking at the Fisher–Yates shuffle algorithm and followed the Python implementation for it. Python starts from the end of the array to the start. Looking at the algorithm I didn't see any ...
1
vote
1answer
20 views

Wrapping the complexities of alternative algorithms: What is the proper “term” for it?

Suppose that we have two algorithms for the same task (e.g. search): AlgC: has bounded worst-case complexity, e.g. O(n.logn) AlgH: is a heuristic algorithm that is experimentally faster than AlgC, ...
0
votes
0answers
9 views

Time-slice Equalizing Algorithm

I have a requirement for which I am trying to write an algorithm and struggling a bit conceptually with. This seems like it should be a common-ish type problem so I imagine there is a name/standard ...
0
votes
0answers
12 views

Selecting right cartons for meeting demand (retail supply chain)

I am working on an inventory allocation problem and I could use some help figuring out an optimal solution. Let's say a retail chain's warehouse stores inventory in cartons (physical boxes). Each ...
2
votes
0answers
33 views

Dynamic Program for this Weighted Possion-Binomial Problem?

Setup: Suppose we have $n$ independent Bernoulli random variables, say $\boldsymbol{X} = \{X_1, ..., X_n\}$ each with prior $\mathbb{P}(X_j = 1) = p_j$, and weights between $-1$ and $1$, say $W = \{...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
0
votes
1answer
47 views

Need help regarding random password generator: Urgent [closed]

I had generated a random password from a website which unfortunately has put me into trouble. The password contains 26 characters which includes alphabets, numbers and special characters. My trouble ...
2
votes
1answer
48 views

Minimal hitting set with respect to set inclusion from a book “Parameterized Complexity Theory”

In the first chapter of "Parameterized Complexity Theory" by Flum and Grohe, an example is presented to find a hitting set of minimal cardinality. In Fig. 1.3, the author says a black colored leaf ...