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

1,975 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
288 views

### Recursion with loop inside

What is the time complexity of this algorithm? I assume that is $O(3^n)$ ...
63 views

### Machine learning for recommendation systems (feed forward and recurrent neural networks)

I recently started to learn about machine learning. I have created a feed forward neural network (ffnn) and a recurrent neural network (rnn) to predict user ratings of movies. I am using a subset of ...
139 views

### CRC: false positive under some circumstances

Consider two computers $A$ and $B$. $A$ uses $G$ and $B$ uses $G'$ for the CRC computation. It is given that $\deg G \ne \deg G'$. Computer $A$ wants to send a data $D$. The claim says that: There ...
248 views

### What is the change in time complexity due to substitution of variables?

This is a question I have after listening to a lecture. ...
509 views

### Creating admissible and consistent Heuristic function Help

I am trying to create a heuristic function for use in an A* algorithm. The problem to be solved is a single row tile puzzle with 3 total w tiles and 3 b tiles and one "_" tile as shown below WWW_BBB ...
188 views

### algorithm - maximum pair-wise xor

Given two integers m and n where m < n find the maximum pair-wise xor sum. The question is how to choose m distinct integers from 1 to n such that using those m numbers yields the maximum pair-wise ...
47 views

### A* algorithm to solve a title puzzle

The title puzzle has a setup of. Www_bbb where there are always 3 w's And 3 b's and 1_ . The rules of the puzzle are to get all w's on the right side of all b's where location of _ does not matter,...
24 views

### Understanding the notation and concept behind March Tests

Some background on my question: I have done some research into March Tests that are essentially access patterns for DRAM. One example of these march tests in the MATS+ algorithm shown below with (I ...
228 views

### Applicability of Dijkstra's algorithm to hypergraphs

When I search for Dijkstra's algorithm and hypergraphs, I don't get any results discussing it. The Wikipedia page regarding Dijkstra's algorithm doesn't mention hypergraphs and the one regarding ...
75 views

53 views

### Find K least values in a Tree in which each node has 4 children

Here is an example tree: Each node has either $0$ or $4$ nodes. The values $v(n)$ of the node $n$ is given by $v(n) = v(\operatorname{parent}(n)) + k(n)$, where $k(n)\in \{2, 2.5, 8, 50\}$, such that ...
41 views

### Robust orientation test

I stumbled upon this which looks like a promising way of implementing an orientation test. I'm not interested in the described adaptive approach, I'm fine with using the naive determinant approach ...
213 views

### How can I find the maximum weight between any two nodes in an undirected graph?

This is referring to not the length of the path, but the sum of the weights of the path traversed. I am getting confused by the variety of algorithms out there. Suppose that for a graph represented ...
116 views

### there exists a O(n) algorithm for subset sum under certain conditions?

I was wondering if anybody knows if there is an algorithm for Subset-sum, preferably exact, having a $O(n)$ Time Complexity or near-linear ($n$ = number of elements in the input set) I remember that ...
25 views

### Minimum give away on performance based queue?

I'm trying to solve algorithm problem, so far no luck Lets imagine A is an employer and there are N employee currently on line (queuing) for receiving their paycheck of the month, and each of the ...
54 views

### Comparison of Depth First Search Trees

Does anyone know of an algorithm who is able to return how similar a DFS Tree is from another DFS Tree? (Or any kind of tree in general) I'm not looking for a true or false. Instead, I would like it ...
219 views

### Resource distribution algorithm

I'm looking for efficient algorithm distributing atomic resources with arbitrar weight among a number of buckets with random capacity. Buckets can be added or removed, and resources from removed ...
178 views

### Boruvka MST algorithm using doubly linked lists

I'm reading Sedgewick & Wayne's Algorithms book, and one of the questions in one of the chapters is the following: Develop an implementation of Boruvka's algorithm that uses doubly-linked ...
27 views

### Proof of Zig-Zig step

There was a question connected with one of the video lecture lessons that I'm currently watching. Let two trees be given - the original and the tree after the zig-zig step: Calculate the cost of ...
250 views

### Path of the binary tree which has the highest number of bends

It is an interview question: Given a binary tree print the path of the tree which has the highest number of bends. I could come up with a solution which will keep track the left or right child ...
166 views

### IPL2025 Algorithm problem ? largest sum of n positive number without choosing 3 consecutive number

This question is already asked: To find a subsequence having largest sum among n positive integers by not choosing 3 consecutive elements https://stackoverflow.com/questions/29249104/maximum-sum-in-...
44 views

### Fast hill climbing algorithm that can stabilize when near optimal

I have a floating point number x from [1, 500] that generates a binary y of 1 at some ...
73 views

### Use of FFT in order to multiply two positive integers of $n$ digits

We're given two positive integers $t$ and $s$ of length $n$ in binary representation. Suppose we divide the numbers into ${n \over k}$ blocks of size $k=\lg n$ using FFT algorithm. Suppose ...
417 views

### Deterministic approximation algorithm for MAX k-CUT

I've been trying to solve this problem for two days. This problem is from Vazirani's book Approximation Algorithms (pg 23). Given an undirected graph $G = (V,E)$ with nonnegative edge costs, and ...
302 views

### Longest palindrome size with suffix trees

Suppose that I want to get the size of the biggest palindrome in a string s, and I am restricted to do it using suffix trees what is the best complexity I will get and why? I checked other answers but ...
89 views

### What is the run time of this algorithm?

Robot in a grid: Imagine a robot sitting on the upper left corner of a grid with $r$ rows and $c$ columns. The robot can only move in two directions, right or down, but certain cells are off limits ...
61 views

### What is the most efficent single-source shorthest path algorithm in unweighted directed grid graph?

As regards the topic. Here is an example of such a graph:
73 views

### Inductive proof that $n^2 + bn + d$ is $O(n^2)$ using definition of big O

Given that $T(n) = n^2 + bn + d$ then it's $O(n^2)$ if I can prove that: $O(n^2) = \{T(n): \text{there exist positive constants } c, n_0 \text{ such that } \forall n \geq n_0, 0 \leq T(n) \leq cn^2 \}$...
138 views

### Algorithm to find extrema of a function?

What are some simple algorithms that find the maximum of a function in a certain domain? The function $f$ is guaranteed to have 1 maximum and no other turning points between $a$ and $b$, how can I ...
318 views

### 'meet in the middle' combined with Dynamic Programming for subset sum

What is the reason why nobody has combined the 'meet in the middle' approach with the Dynamic Programming for subset sum? I found it curious that is a kind of a open problem.. as a matter of fact I ...
273 views

### Combinations of numbers in an array that sum to a given value

Given a particular value x and an array A, I'd like some way to determine (without literally checking each possible combination) all of the combinations of numbers in A that sum to it. Thanks to ...
80 views

### How do iterative algorithms for Levenshtein edit distance actually find the number of substitutions, deletions etc.?

Please can someone explain how Levenshtein edit distance works? I've stepped through the algorithm in code and in excel, but I don't understand how this actually succeeds in finding an edit distance. ...
85 views

### Dynamic Programming: Sum from two subset sums subtracted from each other

There are n values given. Is there a possibility to have two Arrays A and B each containing elements from the given values such that the sum of all elements of A ...
32 views

### Finding the optimal point among several weighted points in linear time

I'm trying to find the best position in a set of points where each point p has a weight w. I need to take into account the distance between each point and the weight of the points, the point with the ...
142 views

### Checking position of a point relative to convex polygon in $\mathbb{R}^2$

Just as the title says, I wish to check the position of a point relative to polygon in $\mathbb{R}^2$. My take on this problem is the following: ...
50 views

### Improving an integer factoring algorithm

I've written an algorithm for integer factorization (specifically RSA-like coprimes - products of two large primes, roughly of the same number of decimal digits) which is not based on QS, GNFS or any ...
317 views

### Minimum number of swaps required to have an alternating array

We are given an array with only $0$s and $1$s. The number of $0$s is greater or equal to the number of $1$s. The goal is to ensure that there is not a pair of $1$s adjacent to each other. We can only ...
390 views

### Round-Robin schedule: process A's time quantum expires at the same time as a process B arrives. What happens next?

Let's assume we are to implement a Round-Robin algorithm. What will happen in a case when a process has completed it's time quantum at the same time as another process arrives. Let's say we have a ...
56 views

### Voronoi diagram of a set of simple polygons

The Voronoi diagram is a well-known data structure that helps solve various proximity problems. We have several nice algorithms that build this diagram for $n$ point in optimal time $O(n\log n)$. I ...
How to prove that the problem VERTEX-COVER belongs to $NP$? The problem VC is defined as follow: INSTANCE: Graph $G = (V,E)$ and an integer $k$ PREDICATE: Is there a subset $V_1 \in V$ s.t \$\...