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)

1
vote
2answers
28 views

How to find one solution of a linear inequality with constrains quickly?

Here is the inequality: $a_{1}x_{1}+a_{2}x_{2}+\dots+a_{n}x_{n} \leq B$. Assume we know the values of $\{a_{1},a_{2},\dots,a_{n}\}$ ($a_{i} > 0, \forall i \in [1,n]$)and $B$, is there any ...
0
votes
1answer
28 views

Is the invariant correct?

I want to show that Insetion Sort is stable... Do I have to do that using an invariant?? Is the invariant the following?? At the beginning of each iteration of the for loop, if $A[a]=A[b], a<b ...
5
votes
4answers
63 views

What is the number of full binary trees of height less than $h$

Given a integer $h$ What is $N(h)$ the number of full binary trees of height less than $h$? For example $N(0)=1,N(1)=2,N(2)=5, N(3)=21$(As pointed by TravisJ in his partial answer) I can't ...
1
vote
1answer
49 views

what' is the number of full subtrees of a full binary tree?

I'm looking for the number of full sub-trees of a binary tree; all possible tress of height less than $4$ are: Now my question is: What is $N(h)$ the maximum number of full sub-trees of a ...
0
votes
0answers
18 views

Determining whether two trees are isomorphic

Is there a (probably recursive) algorithm that can be used to determine whether two not necessarily binary ordered (sub)trees are isomorphic or not?
0
votes
3answers
78 views

Solving a summation for n

I am trying to simplify the following summation: $$\sum_{i=1}^{n/2}\sum_{j=i}^{n-i}j$$ I am not really sure how to solve the inner summation at the moment. I tried this: $$\sum_{j=2i}^{n}j-i$$ and ...
0
votes
0answers
14 views

Where can I find the algorithm of prediction dynamics of a 2d uninterrupted function?

Given I have a uninterrupted function in 2D space. This function is given to me as discrete values. I can get an every value of the function in the given interval. (Moreover I know some other ...
0
votes
0answers
44 views

Bin packing 3D / container loading problem : algorithm with “real” constraints handling

I search a bin packing 3D (or container loading) algorithm (for truck load) with handle of many differents constraints (for each item : stackability, possibles orientations, multi customers, max ...
0
votes
0answers
19 views

Is there an efficient algorithm to extract the farthest ends of a thin contour?

Let's say you have pixel bitmaps that look something like this: From this I can easily extract a contour, which will be a concave polygon defined by a set of 2D points. The question is what is the ...
0
votes
0answers
29 views

Kirchoff's First Law (Algorithm Complexity)

I want a help in understanding the figure and the complexity of Kirchoff's First Law Kirchoff's First Law states that the number of incoming flows into a node must be equal to the number of outgoing ...
0
votes
0answers
19 views

Non-deterministic multiplication algorithms

Are there any algorithms for non-deterministic Turing machines that can compute the decision problem $mn=x$ (where $m=O(n),x=O(n^2)$) faster than the equivalent deterministic algorithm? Equivalently, ...
2
votes
1answer
40 views

Algorithm for eliminating irrationality in denominator

Good day. Suppose $a$ is rational number, $p$ is positive integer and $a^{1/p}$ is irrational. If we want to eliminate irrationality in the denominator of the fraction $\frac{1}{a^{1/p}}$, then there ...
0
votes
1answer
26 views

Simplex algorithm question with restraints

How to perform simplex algorithm on the following: $$-x_1-2x_2 \rightarrow min \\ 4x_1+4x_2 \le 12 \\ x_1 \le 2 \ , x_2 \le 2 \\ x_1 \ge 0,x_2 \ge0$$ I would appreciate any hints how to solve this ...
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
40 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
36 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: ...
1
vote
0answers
105 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
41 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
20 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
101 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
27 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 ...