Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

0
votes
0answers
4 views

Algorithm for Team Meetings scheduling optimization

Consider persons P (about 100) and teams T (ca 20), where each person is member of 2-3 teams. Schedule succession of meetings M of teams where each P can attend and optimize waiting time by running M ...
1
vote
0answers
9 views

Expectation for the number of leaf nodes in a randomized tree construction

Consider this procedure for building a tree from $v_1, v_2, ..., v_n$: insert $v_1$ insert $v_2$ and connect it to $v_1$ via a directional edge from $v_2$ to $v_1$ insert $v_3$ and with a uniform ...
0
votes
0answers
27 views

How do I show that an iterative solution to Tower of Hanoi performs the same exact steps as a recursive solution? [duplicate]

So given the typical recursive solution to the Tower of Hanoi problem wherein you reduce the n-disk tower to two instances of an (n-1)-disk tower i.e move (n-1) disks from start to auxiliary. move ...
0
votes
0answers
19 views

Where is kruskal algorithm used in real time?

Kruskal algorithm comes under algorithms in which we can be able to jot down the points in favour of the predestination but in real life where are these algorithms used why we have to study those in ...
1
vote
1answer
15 views

Is there any implementation of AO* algorithm?

I'm trying to solve And-Or Graph, and I find AO* algorithm can handle it. Someone said it's already used in AI, but I can't find it in detail. Have it implemented? Or it's just a pseudocode that can'...
9
votes
2answers
1k views

How can you find all unbalanced parens in a string in linear time with constant memory?

I was given the following problem during an interview: Gives a string which contains some mixture of parens (not brackets or braces-- only parens) with other alphanumeric characters, identify all ...
0
votes
1answer
43 views

Proof of QuickSort algorithm correctness

Recently I’ve studied QuickSort and understood its general idea. Basically, we do the following: Pick an element from the array (no matter which one and how in this context) Rearrange elements in ...
2
votes
1answer
34 views

Split a list of elements into sub lists, each with different criteria

I have a list of elements of different values, say 0 to 3. I want to split it into a certain number of sub lists, each accepting only certains elements. The sub lists may not always have the same ...
1
vote
1answer
34 views

Is the complexity of this algorithm O($\sqrt{n}$) or linear?

Let's say I have two identical jars and I want to find the height that the jars will breaks when dropped from various heights. I can drop the jars from height increments using steps on a staircase. I ...
2
votes
0answers
39 views

Update each element to product of all others in linear time, constant additional space, no division

Question: I am trying to solve question 6.10.1 from Elements of Programming Interviews. I have only been able to find an $O(nlog(n))$ time and $O(log(n))$ ...
0
votes
1answer
30 views

Is TSP a more detailed form of the “Set Inclusion” question?

Set Inclusion GIVEN: set of cards, some with blue backs, and each with a positive, integer face value. QUESTION: Are there any [blue-backed cards] with a [face value <= L]? 2 independent ...
1
vote
1answer
48 views

What is the fastest algorithm to establish whether a linear system in $\mathbb{R}$ has a solution?

I know the best algorithm to solve a linear system in $\mathbb{R}$ with $n$ variables is Coppersmith-Winograd's algorithm, which has a complexity of $$ O\left(n^{2.376}\right). $$ How much easier is ...
0
votes
1answer
15 views

Algorithm for blending/merging shapes together like liquid

This is a basic example of how 2 circles would come together: A more complex example would be an arbitrarily shaped polygon like a country on earth, merging with another one or a circle. All of the ...
0
votes
0answers
26 views

Time complexity of Dijkstra's algorithm for sparse graph

I'm not sure I understand the answer to this question: As I understand it, the algorithm runs in O((E+V) * log(V)) with binary heap. Thus when, E = V^2/log(V), ...
1
vote
0answers
34 views

Error detection in sequence of integers

Let's say I receive a large sequence $s$ of numbers $n_0$, $n_1$, $n_2$, $\ldots$ Later I expect to receive the same sequence $s^*$ with the same numbers $n_0$, $n_1$, $n_2$, $\ldots$ but errors ...
3
votes
2answers
236 views

Bucket computation, cutting array with lines

Given an NxN array, drawing a line from the edge's midpoint to the opposite field how can the N buckets be found covering the majority of the line's path? A visual aid: Is there a better way to ...
1
vote
0answers
20 views

Understanding Dynamic Frequency Warping (not Dynamic Time Warping)

I am implementing a paper which need Dynamic Frequency Warping as a component. They have written very briefly about this algorithm and cite to this paper: Voice transformation using PSOLA technique (...
1
vote
2answers
32 views

Choosing heuristic for A* algorithm where cost is less than absolute distance

Looking for information on choosing a heuristic for instances where the cost of traversing an edge can be less than one. For example, say movement is allowed in the cardinal directions. Should all ...
0
votes
0answers
18 views

In a Min-Cut problem, how many times do i need to run Karger's Algorithm in a given set of nodes?

Question: Given 22 nodes, how many times do I need to run Karger's algorithm in order to find A min-cut problem within an error range (say, <2 or between 0-1) ?
1
vote
0answers
35 views

A look at an exact smallest grammar algorithm. How do we compute running time big-O?

A smallest grammar of a string $s$ over an alphabet $\Sigma$ is a smallest CFG $G$ such that $L(G) = \{s\}$, where size is the total number of symbols occuring on the right sides of production rules ...
1
vote
2answers
52 views

Algorithm for closest available resource

My apologies if question is not in correct format. I don't post here often. I don't know what tags would be appropriate for this question, or even if this is an appropriate question. Looking for ...
0
votes
2answers
19 views

calculation of Transitive Closure

This question is not from homework, but rather as preparation for the test: The calculation of place-in is a calculation in which the algorithm does not need space beyond the output size (beyond ...
0
votes
1answer
29 views

Applying minimax tree to this array [on hold]

Please tell me how I should apply minimax algorithm to the array $$ 15, 12, 14, 16, 11, 13$$ and make a tree?(I understand how minimax algorithm works but I can't apply it to an array)
0
votes
1answer
11 views

What is a genuine atomic multicast?

What is a genuine atomic multicast? What is the difference between a genuine and non-genuine atomic multicast?
0
votes
1answer
18 views

Does the Paxos algorithm use failure detectors?

Does the Paxos algorithm use failure detectors? If not, how can it solve consensus, given the impossibility result?
0
votes
1answer
19 views

How to find the angle of an arc to draw graphic

I would like to draw an arc from a specific point to a goal point, during the process of drawing a larger path. I would like to do it using bezier curves, which aren't adequate for modeling circular ...
1
vote
1answer
24 views

Is there an existing algorithm for this type of sorting?

This TED-ED video talks about some of the most basic sorting methods (bubble sort, insertion sort and quick sort,) in response to a scenario where a librarian ends up with a stack of 1,280 unsorted ...
2
votes
1answer
23 views

Convert NURBS curve into Cubic Bezier Curve

From this: Maybe you already know this, but it's impossible to convert nurbs to bezier splines exactly because nurbs are rational functions, and bezier splines are polynomials. I don't understand ...
0
votes
0answers
25 views

What is the ideal complexity of a task with (n-1)!/2^(n-1) possible threes?

I have n elements to connect. Each element has a given length. My objective is to connect all the elements, so that I get one large, with length sum of all elements. The elements must be connected the ...
0
votes
0answers
17 views

Finding disjoint paths between any number of cell pair marked in nXn matrix

What should be algorithm to find all the disjoint paths between any number of pairs of cells given in matrix? We will say two paths will not intersect if there there is no cell common between any two ...
0
votes
0answers
7 views

Finding all possible exclusive cliques in a graph

TL;DR I need to find all possible ways to traverse an undirected cyclic, possibly disconnected graph to find all exclusive sets of connected nodes which satisfy certain criteria. There's a graph of ...
0
votes
1answer
14 views

Removing max number of edges while keeping minimum distances

Suppose we have a graph with vertices from 1 to n.The graph is undirected and the starting point is 1 and we have path from 1 to any other vertex.We also have positive weight on each edge and there ...
0
votes
0answers
8 views

Where can I find the algorithm in pseudocode for deleting a key from a B-Tree?

I am reading the chapter on B-Trees in Introduction to Algorithms (3rd edition) by Cormen and found the deletion procedure very confusing. I could understand the algorithm for insertion because it ...
0
votes
3answers
48 views

Which is better ? Iterations or Recursions?

I've heard that any algorithm using iterations can be changed into one that uses recursions and vice-versa. But which type of repetition is preferable for minimum amount of computational effort and ...
0
votes
0answers
15 views

How to sort a woven shuffled stack

Say you have sort of a "woven shuffling situation" going on, sort of like this. Or that just looks like a regular shuffle for the most part. I'm trying to show the situation where something can be ...
1
vote
2answers
40 views

How can I efficiently find the largest positive interval in an unsorted array? [duplicate]

Given a set of values like [4, 8, 1, 5, 2, 6, 9, 2, 3, 5, 11, 9], how can I find the largest positive interval between any two of them? For example in the one I just listed, index 0 to index 1 has an ...
0
votes
0answers
11 views

How to identify the final set of “contours” when combining multiple primitive contours

This problem is in relation to how fonts work. Say you have a "glyph" that is composed of of these 5 "contours", or enclosed loops. On their own, each of them is a unified whole. The easiest thing we ...
2
votes
1answer
29 views

Word-hyphenation algorithm for monospaced fonts

I have seen a few standard hyphenation algorithms for non-monospaced fonts, where you are free to squeeze and separate words and letters, but I haven't seen any related to monospaced fonts ...
1
vote
1answer
14 views

If you have a smallest grammar approximation, do you immediately have a CFG inference algorithm?

The smallest grammar problem is to find a single-string CFG. So given a finite list of language samples, known to all lie in some CFG, can we, using the smallest grammars (approximated) of each ...
-1
votes
0answers
4 views

Read a string(ex:“gejdk738€;!&;&”) i assembly tasm [closed]

How can I read a large string i tasm? What would tipically be the stop condition supposing I have to use a loop(if I have to). Are there other methods?
2
votes
1answer
62 views

Confused about the correctness proof of Dijkstra's algorithm

In the proof of the correctness of Dijkstra algorithm, there is a lemma stating as follow: Let u be v's predecessor on a shortest path P:s->...->u->v from s to v. Then, If d(u) = δ(s,u) and edge (...
0
votes
0answers
22 views

N-Queens problem - maximum number of function calls

N-Queens problem - maximum number of function calls. We say, that a backtracking algorithm (code below) 'checks' a setup of N queens, when the function isFree(n-1, y) is called for $0\leq y < n$ ...
0
votes
0answers
35 views

Show that if the transitive closure can be computed in T(|V |) time then BMM can be solved in O(T(3n)) time

Show that if the transitive closure can be computed in T(|V |) time then BMM can be solved in O(T(3n)) time. I didn't understand the proof in the context of building edges. I added the proof i tried ...
0
votes
0answers
15 views

Johnson-Lindenstrauss and k-means

I have a question about Johnson-Lindenstrauss and k-means. I m study a resource that explain a link between Johnson-Lindenstrauss and k-means. From what I understand, Johnson-Lindenstrauss helps us ...
1
vote
0answers
56 views

What algorithm is appropriate for a thermostat controlling the heating of a room with floor heating?

I built my own thermostat that controls the boiler heater for the radiant floor heating in my house and I would like to develop / implement a smarter temperature control algorithm. What I am ...
0
votes
0answers
37 views

Shortest Uncommon Subsequence

Here is another GeeksforGeeks problem that asks how to find the shortest Uncommon Subsequence of 2 strings? For example, Input : S = “babab” T = “babba” Output : 3The subsequence “aab” of ...
2
votes
2answers
34 views

Cover the maximum of elements

I have a collection of subsets $\{S_1,\ldots,S_m\}$ where each $S_i\subset \{1,\ldots,n\}$. I would like to cover the maximum number of elements from $\{1,\ldots,n\}$ by choosing a single element from ...
3
votes
1answer
102 views

Optimal dividing of K people into N groups

A teacher at a school has to do this on a regular basis. Let's say 12 students should be divided into either 4 groups of 3, or ...
0
votes
1answer
21 views

Kiln optimization problem

Say I have a kiln for making castings. There are 3 shapes. I need to produce the following castings: 102 of A 364 of B 70 of C I can put 50 molds in the kiln at a time. I can have 75 molds made in ...
1
vote
0answers
13 views

Testing for a symmetric property $P$

We'll say $P$ is a symmetric property if $\forall x\in \{0,1\}^n:x\in P\iff \forall \pi \in S(n): f_{\pi }(x)\in P$ where $\forall i\in [n]:f_\pi (x)_i=x_{\pi(i)}$. Given a symmetric property $P$ we ...