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
2answers
43 views

Prove that the following algorithm has STOP property (number of steps is finite)

Prove that the following algorithm has STOP property. I am not sure if this term is widely know, so the definition of STOP property that I got during classes looks as follows: STOP property (for ...
1
vote
1answer
43 views

Is there an algorithm to find the minimal number of dimensions, given the distances between points?

Given some finite set $S := \{x_1,x_2,\ldots,x_k\} \subset \mathbb R^n$ we can define a distance matrix $D = (d(i,j))_{ij}$ with $$d(i,j) = \Vert{x_i - x_j}\Vert$$ where $\Vert \cdot \Vert$ is the ...
1
vote
2answers
48 views

Running Time of Sorting Algorithm

Determine the asymptotic running time of the sorting algorithm maxSort. Algorithm maxSort(A) Input: An integer array A Output: Array A sorted in non-decreasing order ...
1
vote
1answer
31 views

Looking for algorithm to iterate over matrix

I have such a product example: ...
1
vote
0answers
24 views

Searching Algorithm on Connected Graph

This is a recreational problem, not sure if it is asked due to my limited knowledge in discrete math. Suppose we have a connected graph (which can be seen as a "map"). We start at an initial vertex, ...
2
votes
1answer
38 views

Partitioning vertices in a bipartite graph according to minimum vertex covers

How to solve this problem? A vertex cover of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set. A minimum vertex cover is a vertex cover ...
2
votes
1answer
29 views

Sorting elements of linked list

I've been looking over sorting algorithms for linked list and here's what I came up with. As we know, for element access arrays will work better than linked list. Also, there is the benefit of ...
-1
votes
1answer
81 views

Algorithm : Visiting all stations in minimum time with additional constraints

I was given this question and not sure how to solve this. This is a DP minimization problem ? Problem : There are N stations in a certain region, numbered 1 through N. It takes di,j minutes to ...
0
votes
0answers
54 views

Is summing a function over all subsets in PP?

Consider the following decision problem: Input: a set $X = \{x_1, \ldots, x_n\}$, a mapping $f \colon 2^X \mapsto \mathbb{N}$ such that for $f(Y)$ is computed in polynomial time for any $Y \subseteq ...
0
votes
0answers
36 views

The computational cost of the adjacency-based Euclidean distance matrix

I know that the computational cost of the adjacency matrix is n*n. Namely, this graph-theoretical structure contains value 0 or 1 for every pair of vertices if there the edge exists or not, so it ...
1
vote
0answers
19 views

Maximum subset of connected edges

I have a graph $G$ with $m$ vertices $V$ and $n$ edges $E$. $G$ is weighted, directed, and cyclic. I want to select heaviest $k$ edges from $E$ such that all of the edges form a connected, undirected ...
0
votes
1answer
15 views

Variant of the “Stable Roommates Problem” when room has not 2 but “n” mates

I'm looking at the name of a variant of the Stable Roommates Problem, when the rooms have more than 2 mates, ie for example 6 to 8. Does this problem has a specific name? A well-known algorithm? To ...
1
vote
1answer
24 views

Better implementation to find the root of an element in QuickUnion implementation of UnionFind problem

I wanted to know which implementation is better to find the root of the element in the Quick Union implementation of the UnionFind problem. The professor has used a while loop to find the root of the ...
0
votes
1answer
15 views

efficiently find connected components in undirected graph considering transitive equivalence

I have a set of nodes and a function foo(u,v) that can determine whether two nodes are equal. By "equal" I mean transitive equivalence: ...
0
votes
0answers
37 views

Modifying BFS to Find the least transfer stop as possible

let's say that a map of a bus system is provide by as graph G. and each edge of this graph is colored to distinguish which of bus lines that edge is associated with. Come up an algorithm which ...
-2
votes
0answers
33 views

I can't come up with any algorithm for this question, any hint would be helpful

I can't come up with an algorithm for this question, any hint would be helpful, thanks
1
vote
2answers
103 views

Iterative Fibonacci algorithm correctness proof, finding loop invariants

The algorithm take in an integer $n$ and outputs the $n$th number in the Fibonacci sequence ($F_n$). The sequence starts with $F_0$. I am trying to prove the correctness assuming valid input: ...
2
votes
1answer
121 views

Mathematical Problem Solving

Will a study of the mathematical proof of a (data structure and algorithm based) problem, when posed as a proposition, highlight peculiar properties of the problem which may help in designing an ...
1
vote
1answer
55 views

Running Time for Finding Maximum

Consider the algorithm findMax that finds the maximum entry in an integer array. Algorithm findMax($A$) Input: An integer array $A$ Output: The maximum entry of $A$ ...
3
votes
2answers
122 views

Efficient data structure handling insert(number) and find(sum) returning pair a,b such that a + b = sum

There are two operations as follows: insert(num): insert num into the data structure. find(sum): return a pair(a, b) ...
0
votes
2answers
45 views

How to calculate time complexity of a randomized search algorithm?

Example: Finding an element from a sorted array Let's say we have an algorithm that accepts a sorted array of length N as its input. Then in each iteration it randomly selects an element from the ...
3
votes
0answers
65 views

Polynomial time algorithms for rank 1 elliptic curves over Q

As an outsider, it sounds like a lot of progress has been made on understanding rank 1 elliptic curves. Much of the BSD conjecture is known for rank 1, and Heegner points provide a way to calculate a ...
2
votes
1answer
39 views

Algorithm to find the two closest elements in a BST

For example, consider an AVL tree: Performing the two_close(T) should give back (13, 12), as they are the closest elements together. Said another way, you can take any two other elements in the tree, ...
2
votes
1answer
61 views

Longest-path in a graph, where the path should be 'straight'

Is there any existing work done on finding paths that are geometrically straight? I encountered a problem where I'd need to find the longest straight(-ish) path in a web of connected nodes, each of ...
3
votes
1answer
64 views

Performance of Modified Dijkstra's algorithm with Binariy heap as Priority Queue

we know the performance of Dijkstra's algorithm with binary heap is O(log |V |) for delete_min, O(log |V |) for insert/ decrease_key, so the overall run time is O((|V|+|E|)log|V|). Now let's modify ...
1
vote
0answers
182 views

Could you show the intractibility of SAT by showing that the number of variables contributing to an arbitrary unsatisfied clause is not constant? [closed]

Preface: This is not an attempted proof at P vs NP Starting with some CNF Boolean expression ϕ, by the rules of logical disjunction, a clause is only unsatisfied if each of the literals in it are ...
0
votes
0answers
76 views

Egg dropping problem

Egg drop. Suppose that you have an $n$-story building (with floors 1 through $n$) and plenty of eggs. An egg breaks if it is dropped from floor $T$ or higher, and does not break otherwise. Your goal ...
1
vote
0answers
16 views

Practicality of Algebraic Machine Learning Methods [closed]

Last year this article was released detailing a method of high level machine learning using methods found from abstract algebra, with seemingly amazing results and claims. However, since then I have ...
0
votes
1answer
49 views

Recursive factorial algorithm

I'm struggling to understand this factorial algorithm. ...
-1
votes
0answers
35 views

Algorithm to find two numbers in a close range that make a clean fraction

I am looking for 2 small numbers where, given 1 large number, those 2 small numbers make a nice fraction of roughly the level I'm looking for. So say we have the number $1234$. I would like to ...
4
votes
1answer
54 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 ...
2
votes
2answers
35 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 ...
3
votes
1answer
30 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
34 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 ...
2
votes
1answer
28 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
40 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
33 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 ...
15
votes
2answers
2k 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
32 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
37 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
23 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
33 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 ...
4
votes
1answer
95 views

Finding a subset with few neighbors

Given a bipartite graph $G(X+Y,E)$, how can I find a non-empty subset $Y'\subseteq Y$, such that $|N(Y')| \leq |Y'|$ (where $N$ is the set of neighbors)? If $|Y|\geq |X|$ then the problem is easy - $...
-2
votes
0answers
33 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
50 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
18 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
vote
1answer
24 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
17 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 ...
1
vote
1answer
22 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
13 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 ...