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

learn more… | top users | synonyms (1)

0
votes
3answers
155 views

Point inside the area of two overlapped triangles

The question is as simple as that, but I have been trying to figure out an answer (and searching for it) with 0 results. I mean, given two triangles (in 2D) I want to find just a single point which ...
1
vote
0answers
2k views

Best lotto algorithms 7 from 42

I have been looking for some algorithms to solve some problems with lottery 7 from 42. My question is , what is the best algorithm to guess at least 2 numbers from selected 7: example , I am able ...
2
votes
3answers
184 views

Expected value of number of sorted elements in a permutation

Consider the obvious algorithm for checking whether a list of integers is sorted: start at the beginning of the list, and scan along until we first find a successive pair of elements that is out of ...
0
votes
1answer
34 views

Algorithm design: θ(f(n)) - help explaining my answer

I am studying algorithm design and need some help explaining my (correct) answer to the following question: Assume that $T(n) = \Theta(n^2)$. Can we say that for every input size $n$, our ...
1
vote
1answer
32 views

Mathematics and Algorithms for Interpolation

I am doing some programming, where I am interpolating point a to point b, against a timer that is constantly incrementing by ...
2
votes
0answers
47 views

Explanation of the algorithmic form

Booth's multiplication algorithm is a multiplication algorithm that multiplies two signed binary numbers in two's complement notation.The core of the algorithm is the replacement of a string of $1's$ ...
4
votes
3answers
499 views

Proving big oh by notation with full expression power

I am trying to prove that: $(n^2 + 1)^{10}$ is $O(n^{20})$ but I am not able to figure out how can I prove it with full expression having a power. Any suggestions?
2
votes
1answer
40 views

“The three shooters algorithm”

As requested at http://stackoverflow.com/questions/29111313/the-three-shooters-algorithm?noredirect=1#comment46504341_29111313 I have moved that topic into here: Like the title says, you've got 3 ...
3
votes
1answer
248 views

Understanding the QR eigenvalue finding algorithm

I'm trying to code up a matrix library (purely as a learning exercise). This question is about the math I'm trying to understand in order to implement it. I just want to make sure I have a firm grasp ...
7
votes
1answer
154 views

Power towers of $2$ and $3$ - looking for a proof

Let $\uparrow$ denote the right-associative exponentiation operator: $a\uparrow b\uparrow c=a\uparrow(b\uparrow c)=a^{b^c}$ There is a sequence $A248907$ recently submitted to OEIS (see also ...
0
votes
2answers
17 views

$T(2N)/T(N)$ ~ $2^b$ (Please help me step out this simplification)

Algorithms textbook says if $T(N)$ ~ $aN^blgN$ then $T(2N)/T(N)$ ~ $2^b$ $$T(2N)/T(N) = a(2N)^blg2N/aN^blgN$$ $$= 2^b(1+lg2/lgN)$$ $$ = 2^b$$
1
vote
0answers
46 views

Algorithm to divide a set of symbols with constraints into minimum number of subsets

I have a set $$ S=\{a,c,d,e,f,j,m,q,s,t\} $$ with a constraint $$ C=\{am,cm,de,df,dm,ds,ef,em,eq,es,et,fj,fm,fs,jm,js\} $$ where $xy$ in $C$ means that $x$ and $y$ cannot be in the same subset. ...
1
vote
1answer
33 views

Min/Max number of inequalities needed to determine the order of $n$ numbers

We are given an ordered $n$-tuple of positive real numbers $R=(r_1,..r_n)$. A $k$-inequality is an inequality of the form $x_1<x_2<...<x_k$ where $x_1,..,x_k$ are in $R$. For example, for ...
1
vote
2answers
75 views

Is this an already existing algorithm/problem?

In my head I like to call this "the matchmaker algorithm", but I suspect it might be an existing thing... then again I don't any answers as of now ... whatever, let me explain: Imagine that you own a ...
5
votes
1answer
1k views

Knuth's mastermind algorithm

I read the other thread regarding Knuth's algorithm and mastermind but I still do not understand quite how it would be implemented. I am confused by the language or my brain is just broken (or both). ...
1
vote
1answer
62 views

Find $n$ numbers which LCM is equal to $k$

Is there any algorithm to find $n$ natural numbers which LCM is equal to $k$? (There is no number that's equal to $k$.)
0
votes
0answers
30 views

Find minimum algorithm complexity

So, I have this task: Let us have square matrix $A \ size\ n\ \times\ n$ for which is true: $$A(k,l)<=A(m,p)\ if \ k <=m, l<=p$$ I need to find algorithm, which finds value X in such matrix, ...
0
votes
1answer
23 views

Find out the angular speed in terms of time.

Here is the equation that describes the motion of a planet under the gravitational field generated by a fixed star: $u=\frac el\cos\theta+\frac 1l$, where $u$ is the reciprocal of the radial distance ...
1
vote
1answer
51 views

Probability to iteratively and independently remove $n$ elements until all gone

The problem is as follows: Let S be a set of n elements. At the first stage each element in S is in- dependently removed with probability p. Those elements not removed constitute the set S1. ...
0
votes
2answers
64 views

Count bulbs in ON state [duplicate]

A room has N (1 to N inclusive) bulbs and N switches. N people go in one by one. 1st person goes in and toggles none of the switches. 2nd person goes in and toggles all switches other than the ...
1
vote
1answer
75 views

Combining kindergardeners in 'fair' cookie-baking groups. Kirkman's schoolgirl problem extended version

I am coordinating cookie-baking events with kindergarten kids. This turns out to be a challenging problem, and I could use a little help: We would like a general way of creating 'fair' cookie-baking ...
0
votes
2answers
34 views

Two vectors moving towards the same point - ensuring they both hit that point at the same time

I'm working on an algorithm which involves two vectors in 3D space. They're both moving towards a single point within their respective directions - I need to make sure that they both hit the same ...
0
votes
1answer
42 views

Proof by induction of recurrence relation

I've been shown the following proof by induction of $P(n)$ where $n$ is a positive integer presumably. This is in the context of algorithmic analysis. $ P(n):T(n) = \begin{cases} ...
1
vote
0answers
50 views

Can every iterative algorithm be viewed as gradient descent over some objective?

In Algorithms for Non-negative Matrix Factorization, Lee and Seung give multiplicative algorithms derived from gradient descent on the Frobenius norm to find a non-negative matrix factorization. ...
0
votes
0answers
45 views

Clique of size $k$ or vertex with degree $\geq \log |V|$ is in $P$?

Prove that $L=\left\{ \left\langle G,k\right\rangle \mid G\mbox{ contains a vertex of degree at least }\log_{2}|V|\mbox{ or a clique of size }k\right\}$ is in $P$ ($G$ is undirected graph and $k$ is a ...
1
vote
0answers
282 views

Carry-save multiplier algorithm

I am having a hard time deciphering how carry-save multiplication is done (in binary, specifically). Here is a block diagram of the carry-save multiplier against the usual multiplier. Since the ...
0
votes
2answers
32 views

pumping lemma question

SO i have to prove that the following language is not regular {w ∈ {a, b}∗: #a ≥ #b}. Now i understand that we need to start by assuming that it is regular, and then say something like use S=a^(p+1) ...
0
votes
1answer
39 views

Testing the divisibility of $\sum_{k=0}^{m-1} (n+k) $ by $m$ when $m$ is odd

The theorem I am attempting to test is $$ \forall m, n \in \mathbb{Z}, n > 0, m \space odd \space \Rightarrow m | \sum \limits _{k=0}^{m-1} (n+k) $$ Please note: The object of this code is to ...
0
votes
1answer
91 views

Better time complexity.

I am new to complexity theory and want to know, Which one is better time complexity(faster) for an algorithm ?? \begin{equation} n^{k+log_2(n)}/log_2(n)2^{n(n+1)/2} \end{equation} or ...
0
votes
1answer
116 views

Is it possible to find longest path in DAG with negative edges with greedy algorithm?

I have exercise to find longest path in DAG and print it. There's no specified if edges can only be positive, though. The list is from greedy algorithms, so I think they assumed edge weights can be ...
2
votes
1answer
31 views

Finding the size of sumsets in limited space

Let $S=\{a+b:\ a\in A,\ b\in B\}$. I have an explicit representation of $A$ and $B$, but $S$ is too large to store in memory. (For the sake of argument, say $A$ and $B$ are 100 MB and $S$ is 1000 TB.) ...
0
votes
1answer
89 views

How to derive a one to one mapping between two discrete sets algorithmically

Given a set of possible coordinates like the below, how would I algorithmically derive a one to one mapping between the two sets (X and Y)? For example I can see 1 <-> A, 2 <-> B, 3 <-> D, 4 ...
1
vote
1answer
60 views

Sorting algorithms

How could we show that the algorithm of Mergesort is stable, Quicksort is not stable but it can be implemented as stable, Heapsort is not stable. I have show that the algorithm of Insertion ...
1
vote
2answers
36 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
31 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 ...
2
votes
0answers
95 views

The amazing lift.

I would like to ask for a program to efficiently calculate how a lift should fetch the people who need it. Most of us use lifts (or elevators) but maybe it could be programmed to be faster! Or can it? ...
6
votes
4answers
326 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 ...
2
votes
1answer
162 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
31 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
89 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
21 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 ...
2
votes
1answer
48 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
34 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
110 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
48 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 ...
0
votes
2answers
201 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)$ ...
3
votes
0answers
35 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
240 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
472 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
49 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$$ ...