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)

0
votes
1answer
17 views

Weighted Random Selection

I read a blog post about a simple algorithm to select a random item from a list, certain items in the list were weighted to increase the chance of it being selected. Add up all the weights. Pick a ...
1
vote
1answer
43 views

Minimize the squared dot product of two specific vectors

Do you think there exists a efficient algorithm(non brute-force) for the following problem. I search the optimal solution for the following problem: Given a vector $u=(u_1, u_2,..., u_k)^T$ with ...
0
votes
0answers
31 views

On Tree- Doubling Algorithm

Use the Tree-Doubling Algorithm, starting the Euler tour and the Hamilton cycle at the vertex a and resolving any ties alphabetically. Need help to this question. Thanking you.
0
votes
1answer
15 views

What is the lower bound for an algorithm that reconstructs a permutation?

In this challenge on codegolf.SE, one has to reconstruct a permutation $p$ of a vector of length $n$ given only a function $P\colon\{0,1\}^n\mapsto\{0,1\}^n$ which applies $p$ to a vector of booleans, ...
0
votes
1answer
45 views

Finding minimum paths in Graph theory

A Canadian postman, rather than returning to the post office $(p)$ after delivering mail along every street in town, wishes to return straight home $(h)$. Let $G$ be a connected graph and $p , h $ ...
0
votes
1answer
28 views

Design an algorithm - Median, computer science

I was wondering if this question belongs here or on StackOverflow, but it is a question of mathematical nature so this seems more appropriate. We have an array $S$ of $n$ different numbers ...
0
votes
1answer
40 views

improved segmented sieve of erastothenes complexity

I improved the segmented sieve of erastothenes , my algorithm doesnt repeat the multiples of primes using the equation $p^{2}_{n}p_{j}+2p_{n}p_{j} \times c =N$ wich shows when at least two multiples ...
0
votes
1answer
32 views

How to “layer” two scale adjustments in a formula?

First: I apologize for the title, I truly don't know what the correct terms to describe my problem are. If I receive suggestions for a more appropriate title or learn some new terms I will revise it. ...
1
vote
1answer
39 views

Why is the time complexity of factorization $2^n$?

Can somebody explain to me why, given the factor value N, the time complexity of a factorization algorithm (N / 2, N / 3, N / 4, ...) is $2^n$ rather than n?
3
votes
0answers
26 views

Check if a point is inside a rotated 2D NACA 0012 airfoil

I've already checked the rotated rectangle problem but this is (I think!) a little more complicated. I have a CFD calculation of a 2D NACA 0012 airfoil and I need to test if a point is inside the ...
3
votes
1answer
60 views

Infine Sequence ${1, 3, 2, 3, 1}$

I have an infine sequence where at the end of which the ones are written. Then till infinity we shall do the next procedure: for each segment with ends a and b (inside which the numbers are absent) we ...
-6
votes
1answer
213 views

Are the propositions right?

I want to choose if the following propositions are true or false and justify the reason for the choice. Polynomial: good, exponential: bad. Radix Sort works correctly if we use any right sorting ...
3
votes
1answer
63 views

Count connected components after $M$ marbles removed

There are $N$ marbles in a line, numbered $1$ through $N$ from left to right. We need to count numbers of ways to remove exactly $M$ marbles such that there are exactly $C$ remaining connected ...
1
vote
1answer
29 views

Function (algorithm) for obtaining random number(s) from dice

I'm afraid I don't speak maths very well. I hope this question is sufficiently comprehensible and mathematical. Suppose I have a perfect D$x$ (i.e. $x$-sided) die, and a pen and paper, and with these ...
0
votes
0answers
16 views

Matrix Multiplication Algorithms for Non-Square Matrices

I'm interested in learning about some of the algorithms available for multiplying non-square matrices, yet despite exhaustive Googling efforts I have been unable to find any discussions of such ...
2
votes
0answers
32 views

Recurrence relationship of Hamiltonian backtracking

I'm struggling to understand how to express the recurrence relation in terms of N of a backtracking algorithm to find out if a Hamiltonian path exists. Where N is the number of vectors. After finding ...
2
votes
1answer
57 views

an strange set $ \Xi_A =$ {$ n \in N | \exists k^2 \in A $ s.t $ k^2 \leq n$} is decidable ?, an Interview questions?

We are some student that had an Interview for M.sc Entrance Exam. This interview has two part and one multiple choice question. We see 1 strange question that some definition is so strange for us, we ...
0
votes
1answer
23 views

Does it make sense to use optimization algorithms(Like ACO) in weighing average to find weighs

I am going to use a DEM fusion method using simple weighing average,I am going to use 2 inputs to create my fusion function W1X1+W2X2/(w1+W2)=result this is a ...
0
votes
0answers
18 views

Checking the correctness of my triple-nested loop analysis

I am trying to analyze the complexity of a triple-nested loop. Using previous posts here as a guidance, I believe I have arrived at the correct solution. However I would appreciate if somebody could ...
0
votes
3answers
53 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
55 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
95 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
23 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
28 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
30 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
402 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
29 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
47 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 ...
5
votes
1answer
120 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
15 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
28 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
25 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
62 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 ...
4
votes
1answer
78 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
34 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
21 views

Compute the running times of these loops

Let c1, c2, c3, etc denote the cost of executing constant operations ...
0
votes
0answers
30 views

Proof of correctness of Bidirectional Dijkstra's algorithm.

Problem 4.52 Network flows Ahuja Magnanti & Orlin Bidirectional Dijkstra's algorithm (Helgason, Kennington, and Stewart [1988]). Show that the bidirectional shortest path algorithm described in ...
0
votes
0answers
7 views

minimum k-vertex connected subgraph containing a given set of vertices of a graph

Let G(V,E) be an weighted, undirected, K-connected graph. Let N be subset of V. What is the best way to find the smallest connected subgraph G'(V',E') of G(V,E) such that N is a subset of V' and ...
0
votes
0answers
12 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
17 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 ...
0
votes
0answers
15 views

Reflect a point on a lattice across a plane

I have a lattice three dimensional lattice of size lx * ly * lz with periodic boundary conditions on all three sides. My planar symmetry cuts are two horizontal and vertical planes (slope 0 and inf) ...
1
vote
1answer
35 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
53 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
44 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
0answers
32 views

Fibonacci polynomial summation

The $n^{th}$ value of a polynomial ($S_n$) of order $k$ is a polynomial in $x$ is given by : $\left(\frac{S_n}{x^n}\right)$= $\sum_{j=0}^n \left(\frac{{F_j}^k}{x^j}\right)$ Where ${F_j}$ is the ...
0
votes
2answers
16 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
22 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} ...
0
votes
0answers
34 views

$f(n)=3f(\frac{n}{3})+O(logn)$

I was asked to figure out the time complexity analysis for the following recurrence relation: $f(n)=3f(\frac{n}{3})+O(logn)$ I worked it out as O(nlgn), Would like to know if this is right or ...
1
vote
0answers
32 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
32 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 ...