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,635 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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$ ...
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 ...
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
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 ...
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", "...
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 ...
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 ...
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 ...
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 ...
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. ...
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 ...
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 ...
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 ...
25 views

Binary Search Symbol Table

Hi I'm attempting to self teach myself from Algorithms (Sedgewick) and ran across the following problem: ...
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?
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 ...
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 ...
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 ...
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?
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 ...
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: ...
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) ...
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 ...
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 ...
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 ...
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 ...
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'. ...
26 views

...
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 ...
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. ...
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. ...
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 ...
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 ...
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 ...
1k views

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