Mathematical questions about Algorithms, including the analysis of algorithms, combinatorial algorithms, proofs of correctness, invariants, and semantic analyses. See also (comptutational-mathematics) and (computational-complexity).

learn more… | top users | synonyms (1)

2
votes
1answer
82 views

Selection from cliques of a graph in polynomial time

Given a simple graph $G$ with $n$ disjoint cliques. Cliques may contain a different number of vertices. Each vertex belongs to one of this cliques. $G$ may also contain edges between two vertices from ...
0
votes
0answers
46 views

Can linear execution time be achieved [duplicate]

The SELECT algorithm determines the $i$th smallest of an input array of $n>1$ distinct elements by executing the following steps. Divide the $n$ elements of the input array into $\lfloor ...
1
vote
2answers
39 views

Dividing the interval in subintervals of equal length

I am asked to describe the operation of the processure BUCKET SORT at the array $$A=\langle 0.75, 0.13, 0.16, 0.64, 0.39, 0.20, 0.89, 0.53, 0.71, 0.42, 0.19 \rangle $$ dividing the interval $[0, 1)$ ...
0
votes
0answers
53 views

Equation of 3D arc given 2 points and radius

Aim Let A be the initial position of a sphere "alpha", and B the location of its target somewhere in 3D space. In my application, this target is close to another sphere "beta", and so depending on A ...
3
votes
0answers
31 views

Efficiently computing GCDs in $\mathbb{Z}[(1+\sqrt{-19})/2]$

The ring $\mathbb{Z}[(1+\sqrt{-19})/2]$ is a PID; hence any two elements have a GCD. How you would compute their GCD? In a Euclidean domain, you would use the Euclidean algorithm. But ...
1
vote
1answer
35 views

Singular Value Decomposition using Jacobi Method

First time user of the site, so I apologize if my question isn't worded properly. I'm trying to implement the SVD of a square matrix using Algorithm 6 found on this website: ...
0
votes
0answers
98 views

Proving a recursive algorithm as correct using induction

My objective is to give a recursive algorithm for finding the maximum of a finite set of integers, "making use of the fact that the maximum of n integers is the larger of the last integer in the list ...
0
votes
1answer
41 views

Algorithm to sort an array [closed]

I tried to apply the following Counting Sort algorithm at an example with array $$A=\langle 6, 0, 2, 0, 1, 3, 4, 6, 1, 3, 2 \rangle$$ ...
3
votes
0answers
157 views

Execution time of function

At the algorithm SELECT, there is the following step: ...
10
votes
0answers
97 views

Product of primes mod n

Let $n$ be an odd composite number. I'm trying to compute $$ f(n)=\prod_{n/2<p<n}p\pmod n $$ where $p$ ranges over the primes in the indicated region. Can this be done (significantly) faster ...
0
votes
1answer
36 views

Function of pseudocode applying it at an array

The following pseudocode is given: ...
2
votes
2answers
39 views

Djikstra's algorithm for shortest path problems (undirected version?)

When using Djikstra's algorithm, during each iteration, we pick a node $j$. Then, we look at all arcs $(i,j)$ where $i$ is not a "finished node", and determine if the distance from node $i$ needs ...
0
votes
1answer
14 views

Question regarding complexity

Dear mathstack exchangers, Currently I`m wondering what the complexity, time and space, is of generating numbers $c \in \mathbb{N}$ with the condition: $H+0 < c < B$. Where $B$ is my upperbound ...
1
vote
1answer
233 views

Minimum cost to convert string S to good string

Given a string $S$ of $0$ and $1$ we need to convert it into a good string. A string is called good if and only if : Their are no two or more $0s$ or $1s$ together. It means $001$ is not good but ...
0
votes
0answers
45 views

Count good numbers that are multiple of 7 upto M

Given a number of $N$ digits with $A[1]$ denoting the first digit , $A[2]$ second digit and $A[n]$ last digit from left to right. It is called good number if ...
0
votes
0answers
17 views

Notation in a fast perfect-power classification algorithm

I'm trying to implement a lengthy perfect-power classification algorithm with an interesting complexity of $O(\log_2(n)^{O(\sqrt{\log\log n\log\log\log n})}).$ To do so, I'm referring to Daniel J. ...
1
vote
1answer
25 views

Cluster algorithm with max range and variable point size

Let's take the simplest example: I have a non-defined amount of points with x- and y-coordinates and want to cluster them under following premises: A point can only be part of one cluster. The ...
0
votes
0answers
27 views

Crossing out as many pairs in a not decreasing series.

Suppose you have a non decreasing series $a_1\le a_2\le a_3\ldots\le a_n$ We can modify our series by only one operation: you can cross out a pair if and only if $2a_i\le a_j$. How can we ensure to ...
0
votes
0answers
21 views

finding the n in Aymptotic notations

consider any quadratic function $f(n) = an^2 + bn + c$, where a, b, and c are constants and $a > 0$. Throwing away the lower-order terms and ignoring the constant yields $f(n)= \theta(n2)$. ...
0
votes
2answers
24 views

Efficient greedy algorithm for elements with distances.

Let's say we have n points on a line all sorted by distance from an origin. There are only points on the right side of the origin. We want to make the biggest subset of these points as long as no two ...
0
votes
0answers
21 views

Adjacency of vertices from Prufer sequence

Is adjacency of vertices can be known from Prufer sequence without decoding? Thanks!
1
vote
2answers
43 views

How to solve the following recurrence

I know others have already posted about this recurrence $T(n) = 2T(n/2) + n\lg n$ on the following these two posts: post1 and post2 However, the style in which they have solved them, is not one with ...
0
votes
2answers
28 views

Trying to find a formula for the following algorithm

I am trying to make a formula for the following algorithm as a function of n, building up my answer using summations. The algorithm is: ...
1
vote
4answers
19 views

Selection Sort Summation Simplification

I am trying to simplify the summation for selection sort. Starting out with: $$\sum_{i=0}^{n-1}\sum_{j=i+1}^{n-1}1$$ I am able to get: $$\sum_{i=0}^{n-1}n-i-1$$ However, I don't understand how to ...
0
votes
1answer
19 views

Decrementing two values at different speeds to arrive at the same destination value at the same time

I have two values x and y that represent two time values in seconds. Normally both values will be exactly the same, but in some ...
0
votes
3answers
38 views

Asymptotic notation (big Theta)

I'm currently in the process of analyzing runtimes for some given code (Karatsuba-ofman algorithm). I'm wondering if I'm correct in saying that $\Theta(\left\lceil n/2\right\rceil) + \Theta(n)$ is ...
4
votes
3answers
136 views

Can't solve a recurrence

I am trying to solve the following recurrence: $$T(n) = 9T(n/3)+n^2$$ If I use the master method, I get $n^2\log{n}$ But, I am trying to solve it using substitution. When I try solving it this way, ...
0
votes
2answers
40 views

Finding the biggest decrease in a list of integers (Python)

Given an array of n integers, h0, . . . , hn−1, I want to find the largest decrease in values such that the largest decrease is max(hi − hj) such that i ≤ j. For example, given as an input the array ...
1
vote
0answers
24 views

why some people use the notation $a \leq O(n)$?

When describing the algorithm complexity denoted by $c$, some people use $c \leq O(n)$ instead of $c =O(n)$ to show complexity. I cannot understand why they should use $\leq $?
1
vote
1answer
34 views

Stuttering Subsequence Problem - Explain the example

I'm reading an article that deals with solving the stuttering subsequence problem in $\Theta (n)$. The article can be found here: http://www.cse.yorku.ca/~andy/pubs/Stutter.pdf Some background on ...
0
votes
0answers
25 views

Round Robin Tournament - Limited Fields

Is there an algorithm I could use to define a round robin tournament where n teams play each other once, but the game fields available are limited. I find an abundance of solutions suggesting the ...
1
vote
0answers
37 views

Is my answer for the composite relation correct and not the textbook's?

Note: This example is from Discrete Mathematics and Its Applications [7th ed, example 5 pg 593] Here is how my textbook's way of representing a relation with a matrix And the definition of a ...
1
vote
2answers
99 views

Compute coordinates of a point in 3D-Euclidean Space

My question concerns the computation of a point’s coordinates in three-dimensional Euclidean Space. I have a point P in three-dimensional Euclidean Space whose coordinates are unknown. My goal ...
0
votes
0answers
27 views

Count number of trees

Given an array with n elements which is the pre-order traversal of a tree. How many max-heap will have the same pre-order traversal?
2
votes
2answers
103 views

Solving for $x$: $x^x=N$

In a case such as $x^x=27$ we can solve by inspection that $x=3$. But how can we solve this algorithmically in general, given that $N\in Q$ where $Q\subset\Bbb Z$ and $Q=[1,10^{10}]$ and $x\in\Bbb ...
0
votes
0answers
12 views

How to find asymptotic cost of matrix filling algorithm . Big O Notation

So I have a list X of N strings each of length M that will be called x_i for the ith index in X Example ...
1
vote
1answer
26 views

How to make sure Player 2 always wins in 23 NIM game?

Game begins with a pile of 23 toothpicks. Players take turns, withdrawing either 1, 2, 3 toothpicks at a time. The player to withdraw the last toothpick loses the game. We need to make player 2 to ...
0
votes
1answer
44 views

How do we solve for $n$?

Asymptotic complexity gives an idea of how rapidly the space/time requirements grow as problem size increases. • Suppose we have a computing device that can execute 1000 complex operations per ...
1
vote
1answer
57 views

Algorithm that decides whether collection of primes exists which satisfies 3 equations

Suppose someone gives you a list of $n$ positive numbers $(a_1, \ldots , a_n)$, together with an upper limit $N$ and asks you to find prime numbers $p_1, \ldots ,p_n$ in the range $2, \ldots , N$ ...
0
votes
0answers
55 views

proof of the Reverse-delete algorithm?

is this proof ,which is provided in the wikipedia page https://en.wikipedia.org/wiki/Reverse-delete_algorithm (at the bottom of the page) correct ? Pseudocode ...
0
votes
1answer
13 views

Algorithm for smooth exponential curves

I want to plot an exponential curve between 256 and 0. Using the following equasion, I get the resulting data set. (Please note that I am rounding any decimals down to nearest whole number throughout ...
1
vote
1answer
50 views

Linear Programming - deriving the Dual of the Primal

I've the following linear programming problem: This is the LP representation of the uncapacitated facility location problem. This is the dual representation of this problem: My question is how ...
0
votes
0answers
36 views

Minimum coins to remove to ensure win

In nim game there are $N$ piles of coins, both players will take turns and pick at least one coin from one particular pile only, Alice starts the game first. A player loses when he/she cannot ...
4
votes
1answer
39 views

Efficient Algorithm for finding left (or right) Transversal in a Group

I'm wondering if anyone knows an algorithm to find a left or right transversal in a group efficiently. The definition is you are given a subgroup $H$ of a group $G$, and you want to find a ...
0
votes
1answer
26 views

Algorithm - return aliasing frequency

I posted this question on StackOverflow as well (link), but it is somewhere between a math question and a programming question (I'm looking for some formulas regarding aliasing frequencies and I want ...
3
votes
0answers
46 views

Counting the number of partitions that are a distance d away from a fixed partition.

Given a positive integer $N \in \mathbb{Z}^{\geq 0}$ let $Partitions(N)$ denote the set of all partitions of $N$, where a tuple $\left(f_1,\ldots,f_N \right)$ is a partition of $N$ if $\sum_{i=1}^N ...
0
votes
0answers
39 views

Optimizing a factorization algorithm

In the paper A ONE LINE FACTORING ALGORITHM the following algorithm is presented: ...
0
votes
1answer
23 views

Exact power of prime that divides an (unrelated) number

I am trying to understand a paper where a numerical algorithm is described. I do not understand the point where the expression "exact power of a prime that divides a number" is used. Here is the ...
0
votes
1answer
29 views

Splitting profits based on quantity of work when work is reused

General Problem We (a small organization) want to split all profits for a project based on the quantity of work invested into that project (thus, if Person A invests 40h and Person B invests 60h, A ...
3
votes
3answers
79 views

Propose an algorithm to find a “celebrity”

A celebrity is a person that everyone knows, but he doesn't know anyone. If we think of a group of people as a graph, where if there is an arrow from $A$ to $B$ that means "$A$ knows $B$", then a ...