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
27 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.
3
votes
1answer
32 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 ...
1
vote
1answer
48 views

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

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 ...
1
vote
1answer
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: ...
0
votes
0answers
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 ...
2
votes
1answer
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 ...
0
votes
0answers
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 ...
1
vote
1answer
33 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 ...
0
votes
0answers
26 views

Prove/disprove: $\frac{O(f(n))}{O(g(n))} = \frac{\Omega(f(n))}{\Omega(g(n))}$ [closed]

Prove/disprove: $$ \frac{O(f(n))}{O(g(n))} = \frac{\Omega(f(n))}{\Omega(g(n))} $$ While the definition of: $$ \frac{O(f(n))}{O(g(n))} $$ is: $$ \left\{t(n) = \frac{x(n)}{y(n)} \colon x(n) \in O(f(...
0
votes
0answers
14 views

Number selection algorithm (to fill up total amount)

I'm trying to create an algorithm in SQL(syntax doesn't really matter) that will read the results table that consists of 2 columns: number (1,4,15,30...etc) and it's quantity(1,2,3,4,5...) like: <...
-1
votes
1answer
47 views

Merging $t$ arrays of size $t$ cannot be done in $O(t^2)$

Dr. John claims that he designed a comparison-based algorithm FastMerge that can merge $t$ arrays of size $t$ at most each in $O(t^2)$ time. In Dr. John’s own words, ”Given $t$ sorted arrays $B_1,B_2,...
1
vote
1answer
53 views

Knapsack Problem with exact required item number constraint

How would we solve the knapsack problem if we now have to fix the number of items in the knapsack by a constant $L$? This is the same problem (max weight of $W$, every item have a value $v$ and weight ...
1
vote
2answers
47 views

Grid Puzzle Split Algorithm

I want to generate a random partition of an $N\times N$ grid into $N$ connected groups having $N$ tiles each. How would I do this? Max grid size will be 10x10. Below is an example for a 5x5 grid.
1
vote
0answers
15 views

Modify Fibonacci Heap to Have a Linear Chain of Marked/Unmarked Nodes Only

In CLRS book there is an exercise (19.4-2), the aim of which is to create a linear chain of nodes by a sequence of Fibonacci-Heap operations. I have solved the problem by recursively making a union ...
0
votes
0answers
20 views

Please explain the algorithm for finding bridges in graph?

let, low[] and disc[] be two 1D arrays disc[i] stores the discovery time of node[I] low[i] stores the lowest value between disc[i] and discovery time of children of node[i] I'm curious that what is ...
0
votes
0answers
19 views

Is there a line that separates two sets of points? [duplicate]

You have two $n$-point sets $P$ and $Q$ of two-dimensional points: $$ P = \{p_1,\dots,p_n\}, \text{ where } p_i = \{a_i, b_i\} \\ Q = \{q_1,\dots,q_n\}, \text{ where } q_i = \{c_i, d_i\} $$ You ...
2
votes
1answer
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 ...
1
vote
1answer
20 views

Parity of number of divisors

Im pretty new here. My question showing me an algorithm: TRUE_SEQ(A[1...n]) ...
2
votes
1answer
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. <...
1
vote
3answers
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 ...
1
vote
0answers
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 ...
1
vote
1answer
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 ...
1
vote
2answers
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 ...
1
vote
0answers
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 ...
3
votes
2answers
48 views

Enumerate the terms resulting from decomposing a number by repeated divisions by 2

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 = ...
1
vote
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 ...
1
vote
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. ...
-2
votes
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++; }
-1
votes
1answer
54 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", ...
1
vote
2answers
130 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 ...
3
votes
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 ...
1
vote
0answers
174 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 ...
0
votes
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 ...
1
vote
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 ...
2
votes
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 ...
0
votes
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. ...
1
vote
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 ...
0
votes
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 ...
1
vote
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 ...
1
vote
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, ...
2
votes
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 ...
2
votes
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 ...
-2
votes
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 ...
3
votes
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 ...
1
vote
1answer
30 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 ...
0
votes
0answers
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 ...
1
vote
1answer
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 ...
2
votes
1answer
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 ...
3
votes
2answers
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 ...
1
vote
2answers
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". ...

1
2 3 4 5
166