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
0
votes
0answers
288 views

Recursion with loop inside

What is the time complexity of this algorithm? I assume that is $O(3^n)$ ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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. ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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,...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
75 views

Maximum independent set in progressive k-partite graphs

I am working on the famous maximum independent set problem on a graph class called progressive $k$-partite graph, and it is defined as follows. Given a graph $G = (V_1, V_2, \dots, V_k, E)$, where $...
0
votes
0answers
61 views

Median of list of difference of elements

I have a list. I have to find median of absolute difference of all pairs of array. Eg - A={1,2,10} Difference for all distinct pairs : 1-10=9 1-2=8 2-10=8 ...
0
votes
0answers
2k views

proof why worst case for bubble sort is array sorted in reverse order

Question 1: Let's say we have bubble sort algorithm which sorts numbers in ascending order. Intuitively one might agree that the worst case input for this algorithm is array already sorted in ...
0
votes
0answers
291 views

Analysis of finding the k-th largest element in a subsegment of an array

Given an array $A$ of length $N$. There are $Q$ queries, each queries will be in the form ...
0
votes
0answers
33 views

inquiry -surface Chebyshev

I am working in grasshopper and need a formula that can divide any surface into equal points. I need an algorithm that can give me equidistributed points on the surface Chebyshev
0
votes
0answers
594 views

NFA: Parallel Bitmap Search vs Recursive Backtracking f

Why does an NFA that accepts/rejects bit strings implemented with a Recursive Backtracking algorithm outperform one that is written using a Parallel Bitmap search? set up two tests for these ...
0
votes
0answers
52 views

How to approach homework about graph traversal

I am given a connected, weighted undirected graph. I must obtain minimum possible weight sum of "marked" vertexes in the graph. Vertexes must be marked so that each simple cycle contains at least ...
0
votes
0answers
265 views

Code arithmetic expression in a binary tree

How to present (code into) an expression consisting of brackets and following operations: +, -, / and * into a binary tree. Then, I need to write an algorithm that will derive that very tree. Any ...
0
votes
0answers
76 views

Table of incompatible turns in an intersection (steps to writing a program)

I just began reading Data Structures and Algorithms (Aho, Hopcraft, and Ullman). At the beginning, there is an example that discusses designing a traffic light for a complicated intersection of roads. ...
0
votes
1answer
67 views

Is there any simpler way to have for each sequence element the amount of succeeding larger elements than to implement an AVL tree?

I have a sequence. And now for each element in this sequence I would like to know how many subsequent elements are larger. Or, in other words, I have a sequence $a_1, \ldots, a_n$, and for each $1\leq ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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-...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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:
0
votes
0answers
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 \}$...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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. ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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: ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
33 views

Algorithm for computing a sum with multiples of specific values

I am attempting to compute a known sum or closest value to that sum using the multiples of a subset of numbers. In this approach I want to minimize the multiples or coefficient. For instance if I ...
0
votes
0answers
151 views

Prove that Vertex Cover belongs to NP

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 $\...

1
32 33
34
35 36
40