# 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,547 questions
Filter by
Sorted by
Tagged with
8 views

### What is the probability of comparision between smallest and greatest element in array when quick sort randomly choose the pivot element?

Consider the recursive quick sort with random pivoting i.e. each time a random pivot element is chosen uniformly. When this ...
2 views

### Detect line intersections excluding endpoints

Suppose I knew the endpoints of various different lines within a 2D plane. For example, A = (1,1) B = (2,1) C = (3,4) D = (1,1) Now, there are lines AB and CD, with a common point of (1,1). However,...
27 views
+50

### Creating a priority search tree to find the number of points in the range [-inf, qx] X [qy, qy'] from a set of points sorted on y-coordinates

A priority search tree can be constructed on a set of points P in O(n log(n)) time but if the points are sorted on the y co-ordinates then it takes O(n) time. I find algorithms for constructing the ...
37 views

### Determine the number of self-crossings for an irregular orientation of an n-pointed star, whose vertices lie on the boundary of a circle

I need to create an algorithm that will output the number of self-crossings for an irregular orientation of an n-pointed star, whose vertices lie on the boundary of a circle. The sample input is as ...
515 views

### Maxflow problem

I need help with the following practice problem on network flow: A cohort of $k$ spies resident in a certain country needs escape routes in case of emergency. They will be travelling using the ...
24 views

### Is this algorithm faster than any prior solution to “Generate All Balanced Parentheses”?

It's an old question: "Generate All Balanced Parentheses." The problem statement in short: given n pairs of parentheses, generate all combinations of well-formed parentheses strings of length 2n. A ...
12 views

### How can I generate all palindromic substrings in a string using trie?

How can I generate all palindromic substrings in a string using trie in O(k^2) time complexity where k = length of the string. ie, there's the string, ededmdeff. The palindromes include ede, ded, ...
24 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 ...
58 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 ...
18 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 ...
416 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 ...
38 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 ...
42 views

### How to sort a large list of elements where everything is sorted but k elements?

Assuming the list is very large, and $k$ is very small, what's the fastest algorithm to sort this list?
18 views

### Algorithm to solve a physical ring removal puzzle

Assume we want to solve the so-called "Super-G" problem from Jean-Claude Constantin. The goal of the puzzle is to get the ring off the other components. Here is a picture of the problem: Source: ...
15 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 ...
156 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$ ...
61 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 ...
39 views

### If a convex optimization problem can be NP-Hard, in what sense are convex problems easier than non-convex problems?

Being new to the OR and Optimization world, I've always assumed that a problem being convex meant that it can be solved in polynomial time. Now I am learning that a convex optimization problem can ...
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
70 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 ...
28 views

### Image Processing (Encryption/Decryption) system using Residue Number System [on hold]

I'm preparing for my final year project in school and i plan on working on the implementation of Residue Number System in Image Processing. I found this thesis online by Pallab Maji here: http://...
27 views

### Find N best subset of quotations

I am faced with the following problem; We are provided cost quotations for shipping cost per packet by various shipping companies, let's call these quotations Q1 ... Qk. Each Quotation is a M x N ...
69 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", "...
40 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 ...
100 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 ...
181 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 ...
319 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 ...
205 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. ...
24 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 ...
18 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 ...
9 views

### Exploring previously unknown area with a drone algorithm [on hold]

I'm working on a drone platform for mapping indoor environment based on depth and image proccesing. I'm looking for an algorithm for exploring previously unknown area, something like a house with a ...
67 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 ...
24 views

### Binary Search Symbol Table

Hi I'm attempting to self teach myself from Algorithms (Sedgewick) and ran across the following problem: ...
166 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 ...
22 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 ...
285 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 ...
28 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 ...
31 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) ...
17 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 ...
36 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 ...
31 views

### GOING BACK IN TIME [closed]

I have been asked this question in some interview. We need to build to go back in time. Implement a ticking clock which goes back in time, decremented by units specified (in hours). Application ...
51 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 ...
21 views

### Algorithm for competing cells of 0s and 1s. Can it be made faster? [closed]

I'm working on a practice algorithm problem, stated as follows: There are eight houses represented as cells. Each day, the houses compete with adjacent ones. 1 represents an "active" house and 0 ...
13 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 ...
283 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'. ...