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
0
votes
0answers
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 ...
0
votes
0answers
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,...
0
votes
1answer
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 ...
1
vote
0answers
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 ...
-1
votes
1answer
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 ...
1
vote
0answers
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 ...
0
votes
0answers
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, ...
-1
votes
1answer
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 ...
0
votes
1answer
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 ...
1
vote
0answers
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 ...
6
votes
1answer
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 ...
0
votes
2answers
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 ...
3
votes
2answers
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?
1
vote
0answers
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: ...
-1
votes
1answer
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 ...
5
votes
2answers
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$ ...
1
vote
0answers
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 ...
3
votes
1answer
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 ...
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
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 ...
0
votes
0answers
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://...
0
votes
0answers
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 ...
2
votes
2answers
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", "...
1
vote
1answer
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 ...
3
votes
1answer
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 ...
4
votes
2answers
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 ...
5
votes
1answer
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 ...
1
vote
2answers
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. ...
0
votes
2answers
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 ...
0
votes
2answers
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 ...
0
votes
0answers
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 ...
-2
votes
2answers
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 ...
0
votes
1answer
24 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
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?
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
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 ...
1
vote
2answers
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 ...
1
vote
1answer
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?
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
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: ...
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
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 ...
1
vote
0answers
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 ...
-3
votes
0answers
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 ...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
1
vote
0answers
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 ...
0
votes
1answer
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'. ...
-1
votes
1answer
24 views
0
votes
0answers
14 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 ...