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.

1
vote
0answers
6 views

Algorithm to separate circles to reduce collision the maximum between them

I'll try to do my best to explain this. I have X circles (from 2 to 4) which can move around smaller pivot circles. The pivot circles are fixed and cannot be moved once they are in the "field". Pivot ...
0
votes
0answers
4 views

Algorithm for units allotment to the customers based on preferences

I'm searching for a simple algorithm to allotment a real estate unit for the customer based on the customer preferences like the following table. Each customer has a priorities and we should allocate ...
0
votes
0answers
6 views

Fixed point of hash

Are hashing algorithms constructed to guarantee that no fixed point exists? My assumption is not, because I don’t see what utility that would have. (Please correct me if I’m wrong.) As such, purely ...
0
votes
1answer
17 views

Merge sort and quciksort recursion tree depth

1) I need to determine recursion tree depth for strings composed of 10, 100 and 1000 elements when using merge sort. For the 10 elements one I can do it on a paper, just drawing tree, but what about ...
1
vote
1answer
12 views

What is the motivation behind restore model of computation?

The memory that stores the input is called the input memory. The memory that an algorithm additionally occupies during the computation is called the working memory. $\textit{Model of Computations}$ ...
1
vote
1answer
28 views

Algorithm to find if there are N 1's in a matrix where no two 1's are in same row or column

I am trying to find an algorithm to determine whether a $N\times N$ matrix of ones and zeroes could have a sublist of ones, such that in that sublist we have only one $1$ from each row or column.
0
votes
0answers
21 views

Finding all edges on any shortest path between two nodes using dijkstra

Given a directed weighted graph, we need to mark all edges (represented by an ordered triple of (source,destination,weight) ) which lie on some shortest path from source to destination (there could be ...
14
votes
2answers
1k views

What is this data structure/concept where a plot of points defines a partition to a space

I encountered an algorithm to solve a real world problem, and I remember a class I took where I made something very similar for some for a homework problem. Basically it's a plot of points, and the ...
0
votes
0answers
19 views

use sparse table to optimising queries in suffix array

I want to build a suffix array and handle these queries: 1.word search in a text 2.longest common prefix of two suffixes(LCP) so after making the suffix array,I want to do these requests by ...
1
vote
0answers
33 views

An efficient algorithm to find a linear transformation between two ternary quadratic forms

Let $\mathbb{F}_p$ be a prime finite field for $p > 2$. Consider two ternary quadratic forms $$Q_1\!: x^2 - a_1(t)y^2 - b_1(t)z^2,\\ Q_2\!: x^2 - a_2(t)y^2 - b_2(t)z^2$$ over the field $\mathbb{F}...
-3
votes
0answers
22 views

We can write a serial algorithm. Is it possible to write a parallel algorithm?

We can write a serial algorithm. Is it possible to write a parallel algorithm? Consider a serial algorithm for multiplying an nxn matrix A with an nx1 vector x to yield an nx1 product vector y. ...
1
vote
1answer
28 views

Let G be a graph directed without circles. Suggest a method to find a minimum set of vertices So that all the vertices in the graph can be reached

Let G be a graph directed without circles. Suggest a method to find a minimum set of vertices So that all the vertices in the graph can be reached. I thought to run an SCC algorithm to find binding ...
-2
votes
0answers
31 views

Number of distinct traingle vertices

I was given the following question to solve: Consider you are given N distinct points with both a positive x coordinate and positive y coordinate. For each coordinate you are to form a right ...
3
votes
1answer
43 views

Why $\Theta(n^2)$ multiplication of coefficient required for canonical form of polynomial?

I was working through a textbook (Probability & Computing by Michael Mitzenmacher & Eli Upfal) and am not able to understand the following: Let $F(x)$ be given as a product $F(x) = \prod_{...
0
votes
0answers
11 views

Value iteration in MDP - updating each state once per inner loop?

In value iteration algorithm we update the utility of all possible states ("for each state update its new utility"). After we've updated all states we check to see if the delta is smaller than some ...
-1
votes
0answers
19 views

Understanding constraint satisfication problem : N-Queen Problem

I am searching pseudo code of Forward Checking-Minimum Remaining Value and Forward Checking-Lease Constraint Value.I try google but no more than show words.I am trying to understand these two ...
1
vote
1answer
23 views

Why theta(n^2) if m=floor(n/2) for Naive String-matching

I’m reading CLRS(Introduction to Algorithm, 3rd edition). In the chapter 32.1 about the naive string-matching algorithm, the book says the worst case running time is $\Theta(n^2)$ if $m = \lfloor \...
2
votes
1answer
13 views

Determine Intersection given only a hyperrectangle and a point-contained-in-shape-Predicate

Given only an n-dimensional hyperrectangle by its corner-point-values and an n-dimensional Predicate that corresponds to an arbitrary shape and tests whether a point is contained in said shape, is it ...
0
votes
0answers
18 views

Banker's algorithm - additional allocation

I have a problem with the banker's algorithm. There are 6 processes and one type of resources. The allocation is (0, 29, 35, 10, 25, 35) and the MAX need is ...
0
votes
0answers
13 views

Understanding Hough transform examples in python

I have been reading up about the Hough transform recently, but I want to implement the algorithm (or a follow an existing algorithm such that I understand it) in python. I can't find many resources to ...
1
vote
1answer
17 views

What Are the Ideas Behind Variations of the Coin Change Problem?

Problem: given a set of n coins of unique face values, and a value change, find number of ways of making change for ...
0
votes
0answers
9 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
1answer
22 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
29 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
23 views

Where is kruskal algorithm used in real time? [on hold]

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
16 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
57 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
39 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
36 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
46 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. There is no solution for this question in the book. I have only been able to ...
0
votes
1answer
32 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
55 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 ...
1
vote
2answers
26 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
27 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
238 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
36 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
36 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 ...
2
votes
2answers
55 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
21 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 [closed]

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
20 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
29 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 ...