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
-1
votes
1answer
39 views

How to generate Deterministic finite automaton for given language

Problem: Write a program which generates Deterministic finite automaton which accepts given language. Language is defined with alphabet and start/end sub strings. For example: Alphabet={a,b,c}; start ...
0
votes
1answer
63 views

repository of test cases of hard, combinatorial, NP problems

I'm sure there are standard test cases of hard, combinatorial, NP problems, ... (like knapsack, bin packing, partitioning, ...) that practitioners or algorithm developers use when they compare a new ...
1
vote
0answers
27 views

How can I choose good hash function for PCY algorithm

As far as I understand from PCY (Park, Chen, and Yu) algo is that the algo uses hashing during the first pass to reduce the number of CANDIDATE pairs that are considered in the second pass. I have 2 ...
6
votes
1answer
419 views

Finding Shortest Paths of weighted graph using stacks

I will be given some kind of this graph as in the picture below. I've searched some algorithms but it seams as if it is something impossible for me to figure them out. In fact using Floyd–Warshall ...
0
votes
2answers
81 views

How to generate all combinations given an array of elements using backtracking?

Given an array, generate all combinations For example: Input: {1,2,3} Output: {1}, {2}, {3}, {1,2}, {2,1}, {1,3}, {3,1}, {2,3}, {3,2}, {1,2,3}, {1,3,2}, {2,1,3}, {2,3,1}, {3,1,2}, {3,2,1} I am ...
-1
votes
1answer
23 views

Maximize Reward with Cost Limit in a Fully Obserable Environment

I recently encountered a coding interview question which is broken down as follows. You are given an array N which consists of pairs n which consist of a reward and a cost. You are also given m which ...
5
votes
2answers
157 views

Block matching pattern matching problem

I've struggling with this problem for a while. Given text $T=t_1t_2\ldots t_n$ and pattern $P=p_1p_2\ldots p_m$ over alphabet $\Sigma=\mathbb{N}$, we say there's a block matching of $P$ in index $i$ ...
1
vote
0answers
76 views

multiset variant of subset sum problem known algorithms

I have been working in the time analysis for an exact solver I designed for the subset sum problem accepting multisets as input instances, and determined its time complexity to be dependent on the ...
0
votes
0answers
6 views

MaxEvaluations is a parameter of NSGII

Max Evaluations is a parameter of NSGII, but I don't know how to interpret it, Why a number as large as 10,000 or 20,000 is required
0
votes
3answers
106 views

How to prove that ($56n^2+106n+48)(\log(264n^2+200)) = Θ(𝑛^2\log n)$

I understand that essentially we have to prove that $$c_1(n^2\log n)\le (56n^2+106n+48)(\log(264n^2+200)) \le c_2(n^2\log n)\,.$$ I am confused on how to simplify this further? And ...
2
votes
2answers
99 views

Finding the last substring in lexicographical order in O(n) time

Given a string s, return the last substring of s in lexicographical order. Example 1: Input: "abab" Output: "bab" Explanation: The substrings are ["a", "ab", "aba", "abab", "b", "ba", "...
1
vote
1answer
44 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 ...
3
votes
1answer
103 views

Distinct Binary Heaps

I have $n$ elements out of $n-1$ are distinct. The repeated element is either minimum or maximum element. I need to figure out how many distinct max heaps can be made from it. My analysis : I started ...
4
votes
2answers
190 views

maximum flow with all or nothing through each edge

Consider a maximum flow problem, where each edge has a small integer capacity. Now, I want a solution that for each edge uses the entire capacity, or no flow through that edge at all. To avoid the ...
5
votes
1answer
340 views

Find all values repeating more than $\lfloor n/k \rfloor$ times in $O(n \log k)$ time

Given a parameter $k$ and an array (not sorted) of length $n$ return all values which repeat more than $\lfloor n/k \rfloor$ times in $O(n \log k)$ time. I've managed this in $O(nk)$ time, but can't ...
1
vote
2answers
224 views

Algorithm for scheduling unit time tasks with arrival times and deadlines

Suppose we have $n$ tasks to order over $n$ days. Each tasks takes 1 day to be completed. Each task has a start date when the task becomes available and a deadline when the task must be delivered. ...
0
votes
2answers
28 views

Efficient algorithm to filter off points from a point cloud

I have a master point cloud, which essentially just a list of points with {x,y} coordinates. The point cloud is HUGE ( like, it can contain more than 1 million ...
0
votes
2answers
23 views

Coefficients in cost function in A-star

I'd like to expand on this question : https://stackoverflow.com/questions/52420788/why-does-the-a-star-algorithm-need-gn Dijkstra's algorithm uses cost function $f(n) = g(n)$ whereas A* uses cost ...
-2
votes
2answers
73 views

Why haven't I solved the Travelling Salesman problem with the following argument using djikstras algorithm?

I claim to have solved the travelling salesman problem as follows. (You will have to be familiar with djikstra's algorithm for this.) 1) I am about to start using djikstra's algorithm on any given ...
0
votes
1answer
25 views

Binary Search Symbol Table

Hi I'm attempting to self teach myself from Algorithms (Sedgewick) and ran across the following problem: ...
2
votes
1answer
178 views

Merging rectangles into rectilinear polygon

Having a set of adjacent rectangles, what would be the algorithm that gets the rectilinear polygon wrapping around them?
2
votes
1answer
42 views

Max sum cyclic path of fixed length in matrix

Given a matrix NxM of positive integer values and a starting position (that has value 0), determine the maximum sum path of length K that starts and ends at the aforementioned position. Legal moves ...
2
votes
1answer
26 views

Non-Boolean SAT

I was wondering about the complexity of SAT tests with variables $x_i = 0 \lor 1 \lor 2 \dots \lor n$, with clauses being of the form $x_i = a \implies x_j \neq b$. When $n=2$, we have 2SAT, which has ...
1
vote
2answers
293 views

Why is Dijkstra's Algorithm more popular compared to Grassfire algorithm?

Consider algorithms to find shortest paths in a graph. The grassfire algorithm has a complexity of O(|V|) where V is the number ...
1
vote
1answer
35 views

I came up with a way to modify Dijkstra's Algorithm to handle graphs with negative edge weighs [duplicate]

Add a constant $c\geq |w_{min}|$ to each edge of $G$, so that each edge now has non-negative weight. Run Dijkstra's algorithm Can anyone tell me if this is viable or if it fails?
0
votes
0answers
17 views

O(n) algorithm for the connected components at most n/2 problem [duplicate]

I'm given a problem statement which states "There always exists a vertex from a tree G such that the remaining connected components have size at most |V(G)|/2". I'm trying to formulate an efficient ...
1
vote
2answers
35 views

Algorithm Design: Efficient O(n) algorithm to get the ith to jth largest elements in an array

I am trying to design an efficient algorithm that retrieves the ith to jth largest elements in an array. For example, if the following array is the input: ...
0
votes
1answer
23 views

Grassfire vs BFS

Expanding on this question : Why is Dijkstra's Algorithm more popular compared to Grassfire algorithm? What are the differences between grassfire and BFS? I'm surprised grassfire (supposedly) ...
0
votes
1answer
18 views

Can Dijkstra's algorithm outperform A star, in terms of vertices checked?

I know Dijkstra's algorithm can be seen as a specific case of A star, when the estimation heuristic used simply returns 0, so I know that A star with this specific heuristic can not check more ...
1
vote
0answers
40 views

Max sum of k contiguous subarrays

The question is: given an array of size $n$ and a number $m$, now our goal is to find AT MOST $m$ contiguous subarrays such that the sum of all these subarrays is the largest. It is also required that ...
1
vote
1answer
54 views

How can I calculate the maximum sum/product of sequence?

I am looking for an algorithm in $O(N^2)$ that finds the maximum value that be obtained from a sequence of real numbers greater than 0 (e.g. $\{ 1, 2, 3 , 4\}$) by inserting a plus ($+$) or ...
1
vote
0answers
15 views

Algorithm for searching string with wildcards

I'm trying to find efficient algorithm for checking if string with wildcards contains given substring. The parts of the string are separated with a "." character. So for example I have ...
0
votes
1answer
308 views

Create a binary search tree from a sorted array: Space complexity reasoning

Here is the Python code. The solution is fairly common and is seen in most textbooks like 'Cracking the Coding Interview' and 'Element of Programming Interviews'. ...
-1
votes
1answer
26 views
0
votes
0answers
15 views

Traverse tree collecting nodes combinations

Summary: I have a tree, containing car parts, from which I need to build all valid combinations of these parts. Parts can be required - every build must contain them. Parts can be optional. Parts ...
0
votes
2answers
54 views

What is the official name of a specific type of combination algorithm

Say that I have the following set of variables: [A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z] The values represent a list of variables from a dataset. ...
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
25 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 ...
4
votes
2answers
112 views

Find maximal subgraph containing only nodes of degree 2 and 3

I'm trying to implement a (Unweighted) Feedback Vertex Set approximation algorithm from the following paper: FVS-Approximation-Paper. One of the steps of the algorithm (described on page 4) is to ...
10
votes
1answer
308 views

Shift-resolve parsing - questions

I've recently came across a paper describing the parsing technique mentioned in the title. Unfortunately, the terminology used in said paper is somewhat beyond my comprehension, so I've been ...
17
votes
3answers
1k views

Algorithm to test whether a language is context-free

Is there an algorithm/systematic procedure to test whether a language is context-free? In other words, given a language specified in algebraic form (think of something like $L=\{a^n b^n a^n : n \in \...
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
31 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
63 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
2answers
58 views

Verifying connectivity of a graph in O(n^2)

I trying to solve the following problem in $O(n^2)$: We have vertices which represents cities and a textfile containing an edge on each line. How many roads do we need to build to make the graph ...
2
votes
1answer
33 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 ...
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 ...
44
votes
7answers
65k views

Minimum spanning tree vs Shortest path

What is the difference between minimum spanning tree algorithm and a shortest path algorithm? In my data structures class we covered two minimum spanning tree algorithms (Prim's and Kruskal's) and ...