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

8,288 questions
Filter by
Sorted by
Tagged with
31 views

### Can I find all the common subsequences between 2 sequences by using dynamic programming?

I need to know if there's a dynamic programming algorithm that returns all common subsequences between 2 sequences not just the longest one. Thank you.
34 views

### Algorithm to create dense style crossword puzzles

I am working on creating a program to generate dense American style crossword puzzles of grid sizes between 15x15 - 30x30. The database of words I'm using ranges between 20,000 and 100,000 words of ...
67 views

### How to find all the contiguous subsequence of an array is less than O(N^2) time complexity? [closed]

i am unable to find product of every contiguous subsequence of an array in less than O(N^2) time complexity. What actually i want to do is find the number of contagious subsequence whose product of ...
27 views

### Generate all combinations of a set/array with specific conditions

Apologies if this isn't posted in the right stack exchange, but I'm trying to come up with an algorithm that generates a set of sets ('set' as synonymous with 'array') with the following conditions: ...
21 views

### Solving NP problems : analogy between the SAT problem and the shortest path problem

in this 2minute-long video https://www.youtube.com/watch?v=TJ49N6WvT8M (pulled from a free udacity course on algorithms/theoretical computer sciences), whose purpose is to show how a SAT problem can ...
19 views

### Properties of roots of recurrence relations in the context of exponential algorithms in order to decrease the upper bound of the running time

The book "Exact Exponential Algorithms" by Fedor V. Fomin and Dieter Kratsch is an excellent book to start learning how to design exact exponential algorithms. In their second chapter, they introduce ...
9 views

### Is there some place I can an implementation of the Cartesian Product Algorithm for Type Inference?

Where can I find an implementation of the cartesian product algorithm for type inference? (Preferably in Python/C++, but any language would really do) I've searched the internet many times but there ...
37 views

### Probability that two elements are compared in randomized quicksort

I am having an issue in a specific part of the randomized quick-sort analysis. As per the randomized quick-sort algorithm the pivot is chosen from the given subset on which it is called from a random ...
27 views

21 views

### Knapsack-like problem with profit formula

Given two sets of $N$ integers, weights and reps, that store info about some dumbbells, find out the maximum profit by taking at most $M$ dumbbells. Each dumbbell can be taken at most once. The ...
20 views

### Parity of number of divisors

Im pretty new here. My question showing me an algorithm: TRUE_SEQ(A[1...n]) ...
14 views

### Generate slice that contains element

Suppose I have the array: [2, 3, 4, 5, 6, 7, 8, 9] Now based on few parameters: current_item - currently selected item. <...
39 views

### rolling around running numbers

I'm numbering generated files with two digits 00-99 and I want to retain the last 50. The algorithm should tell me the number of the current file that I'm about to save and which of the previous files ...
26 views

### Is using Fibonacci Heaps in Huffman Code, better than a regular Min-heap?

When using Huffman Code, to generate prefix-code trees for a sequence of letters, CLRS choose to use a normal Min-heap data structure. Using Fibonacci-heaps instead, are we not able to achieve a ...
32 views

### What is an algorithm to find the largest rectangle of white space in an image?

Take an image, (the Google home page) is a good example. I want an algorithm to find the largest white rectangle in this image. That is to say, the largest rectangle that would fit in an area of ...
71 views

### Fastest algorithm for finding the number of primes in a range

Is there an algorithm for finding the number of primes in a given range $[N, M)$ that works in time linear to $M-N$? For context, $N$ and $M$ can go up to $10^{10}$, but the distance between N and M ...
19 views

### “Job” scheduling with skill restrictions

I was given this real life problem and was asked if there would be a way to optimize this, I realize that this is akin to a job scheduling problem, but I can't seem to grasp how to make it work with ...
48 views

Consider a natural number $n>1$. We express it as $\lfloor \frac n 2 \rfloor + \lceil \frac n 2 \rceil$. We repeat the process for each of the two terms until all terms are 1 or 2. For example $9 = ... 1answer 24 views ### Algorithmic problem with many different time/space complexity solutions I am preparing a lesson about algorithmic thinking for beginner programmers. I would like to show them an easy to understand problem which has as many solutions as possible with different time or ... 1answer 14 views ### Matching vertex values with sum of edge weights on bipartite graph Earlier this week I asked this question (please review): Imagine StackOverflow started offering a subscription where companies could buy X number of impressions per month for a set of tags. ... 0answers 20 views ### What is the Big-O runtime of this algorithm? please [closed] val<- 0 for(i = 0; i < n; ++i) { for (j = n; j > i; --j) { val++; } 1answer 60 views +50 ### How can this Line-Breaking algorithm consider spaces as having width different than 1.0? The Divide & Conquer Algorithm for Line-Breaking described here is given below, both in Python and in Dart (which is similar to Java/C#). Line-breaking is also known as "line wrap", "word wrap", ... 2answers 131 views ### What is the worst-case big-O time complexity for this code? I had a quiz in my class and didn't do so well on it. I'm looking to find out if someone can explain to me what I did wrong here - our professor is overwhelmed with office hours as we moved online so ... 0answers 21 views ### Number line jumping algorithm Can you recommend an algorithm for the following problem? If you have any suggestion for simplifying the problem I am open to it. There is a number line going from$0$to$x$. There are$r$rewards ... 0answers 181 views ### Find the median element of two AVL trees in$O(\log n)$I'm attempting the problem of finding the median element in two AVL BST's in$O(\log n)$time. In this problem, we are given two AVLs, with a combined size of$n$(the distribution across the two ... 0answers 17 views ### How should I make this algorithm / What algorithms are avaiable for scheduling tasks As part of a school assessment task, I am required to create a solution which incorporates a complex algorithm. I have an idea for the algorithm and it goes as followed; A complex algorithm which ... 1answer 37 views ### Finding pairs of vertices which would disconnect a graph An assignment question asks, Given a connected, undirected graph$G$, describe an algorithm which can determine if the removal of any pair of vertices would cause$G$to become disconnected. There ... 1answer 14 views ### Raptor algorithm: find next best paths I'm reading Microsoft's white paper "Round-Based Public Transit Routing" (the RAPTOR algorithm). What are the ways to find next best paths (path is a sequence of trips and transfers from source to ... 0answers 11 views ### Assign resources that each have a certain amount of work they can provide to tasks that require a certain amount of work I'm attempting to do a hobby automation project and have come to a roadblock. I have a certain problem I need to solve, but can't think of the solution nor what the name for the problem would be. ... 1answer 17 views ### Covering maximal number of sets using fixed number of elements I've encountered some problem which seems general enough to have already been solved. There is a set of objects$O=\{o_1, o_2,\dots,o_k\}$and a family of sets$A_1,A_2,\dots,A_t \subseteq O$. For ... 1answer 41 views ### How to shift a matrix by x rows and y columns in the most efficient way? My objective is to shift rows by x and columns by y in a 2d matrix. My problem is to solve this objective in an efficient manner. x and y could be negative or positive. Negative would mean up/left ... 1answer 26 views ### Recognizing a trajectory from a set Given a set of 2d trajectories/paths, where a trajectory is a list of [x,y,time] coordinates, and a new trajectory, how can I recognize which one in the set is most similar to it? The lists may not be ... 0answers 43 views ### Understanding the recursive fast Fourier Transform Algorithm from CLRS Consider the following recursive fast Fourier transform algorithm from CLRS: I believe that I understand this algorithm correctly: you split the input coefficients into the odd and even terms, ... 1answer 34 views ### Algorithm to find player position in a 2D grid when all you know is the directional steps he has taken Given the 2D grid shown below, where blue tiles can be visited and island tiles cannot. Given that we do not know the starting position of a player on this grid. Given that the player can move 1 ... 1answer 16 views ### Transitive reduction with vertex additions? The transitive reduction of a (finite) directed graph is a graph with the same vertex set and reachability relation and a minimum number of edges. However, what if vertex additions are allowed? In ... 0answers 16 views ### algorithm :one of the following lines would make the algorithm correct? [closed] Which one of the following lines would make the algorithm correct? Count from 1 to N+2 (exclusive), and for each number that you count (call it "i"): Count from 0 to N+1 (exclusive), and for each ... 1answer 56 views ### Dijkstra algorithm modification with exactly one relaxation on a directed graph where the weights of outgoing edges of a node are the same Consider the standard version of Dijkstra's algorithm on directed graphs. Assume it is known that the input digraph$G = (V, E)$has the following property: for all$v \in V$the weight of all ... 1answer 31 views ### CLRS closest-pair$L_m\$ distances

I am studying algorithms and datastructures, and in CLRS chapter 33.4, the exercise 33.4-4 states the following: We can define the distance between two points in ways other than euclidean. In the ...
19 views

### How to prove optimal substructure for Lecture Hall assignment problem?

In CLRS, an approach has been given to prove the optimal substructure and the correctness of the greedy algorithm for the activity selection problem. In the Lecture Hall assignment problem, we sort ...
45 views

### Algorithm for optimal spacing in intervals

Is there an algorithm to optimally space points within multiple intervals? Optimal in this case means maximizing the smallest distance between any two points so that each pair of points has at least ...
33 views

### “Visited” vs “Seen” Positions in Breadth-First Search

I'm struggling to understand why there is such a radical difference in the execution time and number of steps required by two seemingly similar algorithms for Breadth-First Search in a 2d grid. In ...
492 views

### What's an efficient algorithm to calculate line breaks (word wrap) for balanced widths (minimum raggedness)?

This is a real-world application, not a student assignment. Suppose we have some numbered boxes which are to be laid out, in order, from left to right, top to bottom, with no space between them, into ...
37 views

### Why does MergeSort have O(n) space complexity if it splits the array log(n) times?

I know this is a common algorithm with plenty of analysis, but when I searched for an answer the only one I found was "Merge Sorting has O(n) auxiliary space because it copies the array into L and R". ...