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)

1
vote
0answers
60 views

Fast checking Matrix multiplication in mod 10

I recently faced this problem in a programming contest: Given 3 square matrices N x N of size N up to 1000. All elements in 3 matrices are from 0 to 9. Check if matrix A x B equals to C, mod 10. In ...
1
vote
1answer
70 views

Proving partial greedy property for minimal knight's path between two squares on unbounded chess board

I was thinking about how to write a computer program to find the path with minimal number of moves that takes a knight from one square $(x_1,y_1)$ to another square $(x_2,y_2)$ on an unbounded chess ...
0
votes
2answers
60 views

Finding the position at n?

This dance asks every performer to follow a precise sequence of steps: • Stage 0 : First, get away from obstacles by setting up your starting point at position 0 • Stage 1 : Take one step forward ...
3
votes
5answers
167 views

How to solve the recurrence relation $T(n) = T(\lceil n/2\rceil) + T(\lfloor n/2\rfloor) + 2$

I'm trying to solve a recurrence relation for the exact function (I need the exact number of comparisons for some algorithm). This is what i need to solve: $$\begin{aligned} T(1) &= 0 \\ T(2) ...
3
votes
2answers
97 views

Smallest linear combination of a set of vectors

I'm searching for an algorithm to accomplish a (hopefully) simple task. If I have a set of vetors, (e.g. $\left( ...
3
votes
2answers
173 views
0
votes
1answer
121 views

2048 algorithm for merging

Ok, here's a question my friend just sent me, ive mastered it to some extent, but am failing, so, please help a little: Your target is to merge these blocks in such a way that one bigger number is ...
3
votes
1answer
312 views

Is there any efficient algorithm for finding subgroups of a given finite group?

I am implementing an algorithm which finds every subgroup of given group. Here's my algorithm. Let $G$ be a group of order $n$ with elements $g_1,\cdots,g_n$. Then I consider each $\langle ...
1
vote
2answers
101 views

nth convolved Fibonacci numbers of order 6 modulo m

Problem: Find the coefficient of xk in (1−x−x2)-6 modulo m. Constraints: k≤264 m≤105, m can be a composite number. I have 10^5 such queries to process in 2 sec, so O(log k) for each query ...
0
votes
1answer
67 views

testing parallelity/perpendicularity of two 3D vectors with lengths close to zero using dot product

as u know dot product and vector norm(euclidean) definitions are as following: $ \vec v . \vec w = \left\lVert \vec v \right\rVert \times \left\lVert \vec w \right\rVert \times \cos\theta = (v_x ...
0
votes
0answers
114 views

A Simple Uncomputable Function?

Let F denote a computable function which takes an integer and returns an integer. Is "checking whether F has a finite null space" computable (using an algorithm which works for any F)? I believe ...
3
votes
1answer
439 views

Choose a k-subset such that its elements 's gcd is maximal

Given $n$ positive integer and a positive integer k. How to find a subset of size k such that its elements 's gcd is maximal (just give the maximum value of gcd is okay). Example: Give $3$ integers ...
1
vote
1answer
194 views

Pack rectangular objects of different sizes in a fixed size rectangle

If this has been asked before, please help me find it, I have scoured Math.stackexchange and have found quite similar questions but not exactly what I am looking for. I have a rectangular space. I ...
1
vote
1answer
83 views

Why does this algorithm to plot implicit equations work?

This may be an obvious question, but I can't seem to figure it out. I found an algorithm that receives an equation, and in order to plot its graph, for each pixel in the screen, it will replace the ...
3
votes
2answers
236 views

splitting polygon in 4 equal parts

I have a convex polygon and I want to divide into 4 equal parts using the two perpedicular splits. Like in a picture. I need s1 = s2 = s3 = s4; I need to get coordinates of point where the lines ...
8
votes
3answers
274 views

Algorithm for multiplying numbers

Background Today I had to explain to some kid how to multiply numbers with multiple digits in them. Then I recalled, that some other day I answered this question describing one of the numerous ...
2
votes
0answers
127 views

Quaternion conversion

We have a normalized orthogonal co-ordinate frame travelling through the curve as in figure 1 below, from one end to other. Let us call starting end as A and ending end as B. What we know is initial ...
1
vote
4answers
2k views

The fastest way to count prime number that smaller or equal N

I want to count all prime numbers that existing in N but I don't know how to count. Can any one tell me how to count prime numbers that are smaller than or equal to N in mathematics formal?
3
votes
0answers
16 views

Approximating the action of the U(N) exponential map

Let's say that I have a curve in $\mathbb{C}^N$ given by the action of the unitary group: $$x(t) = e^{Ht}x_0,~ H \in \mathfrak{u}(N),~ ||x_0||=1$$ I can approximate this to first order as: $$\tilde ...
2
votes
3answers
120 views

What is a bit-shifting standard C function for calculating $f(x) = \frac{(2^{16}- 1)}{(2^{32} - 1)}\cdot x$

I need to take 32-bit unsigned integers and scale them to 16-bit unsigned integers "evenly" so that $0 \mapsto 0$ and 0xFFFFFFFF $\mapsto$ ...
1
vote
1answer
22 views

How can I find the vector between two sets of data?

I need to identify the vector between two sets of data. The goal is to correctly "guess" whether a new piece of data is in group A or ...
2
votes
0answers
51 views

Given a set of nonnegative numbers, put $\pm$ between them to minimize the magnitude of the result

Let's say I have a finite set of non-negative numbers. I have to put $+$ or $-$ between the numbers, in order to minimize the absolute sum.(i.e the sum has to be closest to 0) For example: the set: ...
2
votes
0answers
28 views

Does the method of steepest decent always move in an orthogonal direction between iterations?

I understand everything, I think, about the method but the result (or requirement) that successive steps are orthogonal to each other. SO, with the formula for this algorithm as: ...
2
votes
1answer
60 views

What's wrong with this pseudocode for Forster-Overfelt's version of the Greiner-Horman polygon clipping algorithm?

The Problem I'm trying to understand and implement the Forster-Overfelt version of the Greiner-Horman polygon clipping algorithm. I've read the other Stackoverflow post about clarifying this ...
0
votes
0answers
48 views

Fastest Algorithms for Determining the Nullity of a Matrix

How exactly does one go about determining the Nullity of a Matrix quicker than simply running Gaussian Elimination on the matrix itself? To be perfectly honest I can't think of a method that doesn't ...
1
vote
0answers
81 views

Understanding Sobol sequences

Can someone explain to me in simple terms, how Sobol sequences work? The wikipedia article is fairly technical. They look pretty interesting. So I shall describe (whatever little I know) in short the ...
0
votes
1answer
85 views

Betweenness Centrality: How Long Does Mathematica Take?

A simple maths problem. If I have a disk of unit radius and place within it $N$ nodes such that the node density $\rho$ is given by $$\rho=\frac{N}{\pi R^{2}}=\frac{N}{\pi}$$ then connect each node ...
2
votes
1answer
159 views

Upper and lower bound of an approximate computation

I'm currently working on an exercise in The Art Of Computer Programming, Vol. 1 relating the algorithm for computing $\log_{10} x$ presented in the Mathematical Preliminaries. The algorithm is ...
1
vote
1answer
55 views

Maximum of minimum distance to a point cloud

I have $N$ 2D points $P_i$ in a rectangle $T$. I'd like to compute a coverage score defined as $$ \max_{x \in T} \min_{0 < i \leq N} \operatorname{distance}(x,P_i) $$ How can I do that ...
0
votes
1answer
30 views

Summation of infinte series

Sir, I have three infinite summation $A =J_1 \sum_{n=2}^\infty (n-1) f(n-2) \tag 1$ , $B =\sum_{n=0}^\infty f(n) \tag 2$ and $C =J_2\sum_{n=1}^\infty f(n-1) \tag 3$, with ...
2
votes
0answers
250 views

How to load warehouse pallets efficiently?

Assume that we would want to develop a warehouse management system, which picks up plastic boxes and stacks them on a pallet. A pallet has a maximum of $5$ vertical box stacks and the maximum height ...
1
vote
1answer
79 views

Digit wise modulo for calculating power function for very very large positive integers

I am writing a code to calculate $P^Q$ where $P$, $Q$ are positive integers which can have number of digits up to $100000$. I want the result as $r = P^Q \pmod{10^9+7}$, where $10^9+7$ is a prime ...
0
votes
1answer
38 views

Converting between rates using a common base rate

If I have a base rate of USD = 1 and know that all conversion rates are in relation to that currency, how would I convert other currencies between each other using that commonality? For instance, I ...
1
vote
2answers
2k views

Proving Hamiltonian Cycle is NP Complete

I'm trying to learn Complexity classes.I want to show Hamiltonian cycle is NP Complete. The text tells me that Inorder to prove NP-Completeness we first show it belongs to NP,by taking a ...
1
vote
2answers
82 views

Converting between exchange rates

Suppose I have a currency exchange rate of 1 USD = 102.642499 JPY. If I had 50 USD and wanted to get the value in JPY using that exchange rate, my equation would be 102.642499 * 50, correct? How ...
4
votes
1answer
57 views

How to check if $\text{position}\left(\frac{a + b} 2\right )$ is in range $\text{position}\left(a\right )$ and $\text{position}\left(b\right )$

Given a permutation of $n$ number $1, 2, 3,\dots,n$. How to check if it is exist $a,\ b$ with the same parity such that $\frac {a + b} 2$ is between $a, b$. How to solve this problem efficiently ? ...
2
votes
1answer
219 views

Why is Doolittle Decomposition Algorithm failing and what should I try next?

I am trying to find the LU Decomposition of the following matrix: So far I have only tried the Doolittle Decomposition algorithm with partial pivoting (it's never failed me before!). As far as I can ...
0
votes
0answers
292 views

Cleaning minimum tables

John has been newly hired to clean tables at his restaurant. So whenever a customer wants a table, he must clean it. But John happens to be a lazy boy. So in the morning, when the restaurant is ...
4
votes
5answers
328 views

Find if person go through given point

A person start moving from $(0,0)$ in a weird pattern as follow : In a single step he will move by one unit in the current direction it is moving. Initially the person is at position $(0, 0)$. In ...
0
votes
0answers
585 views

Count arrangment such that each person wear different tshirt

Few friends are going to a party. Each person has his own collection of T-Shirts. There are 100 different kind of T-Shirts. Each T-Shirt has a unique id between 1 and 100. No person has two T-Shirts ...
2
votes
1answer
83 views

How can I find the point (X, Y, Z) which minimizes this quantity?

I have a number of equally powerful light sources $L_i, 1 \le i \le N$ at points within a cube $(x_i, y_i, z_i), -1 \le x_i, y_i, z_i \le 1$. The intensity of each light falls off with distance ...
2
votes
1answer
84 views

Finding an $n$ such that $n^2 \equiv -1 \mod p$

What is an efficient algorithm to find the first number $n$ such that $n^2 \equiv -1 \mod p$ for a prime $p$, if such an $n$ exists? Is there anything better than the brute-force approach up to $p-1 ...
2
votes
1answer
53 views

How to measure trajectory regularity?

I have two animal running trajectories. A regular one with repeated back and forth running between point A and B, like the one on top in the figure. The other one is very irregular, animal paused and ...
1
vote
2answers
101 views

How can i find if a given number occurs in a custom Fibonacci sequence?

Its a recent interview question from Amazon. For e.g. let starting numbers be $a$ and $b$, then third number will be $a+b$ and so on: forming recursion like: $F(n)=F(n-1)+F(n-2) , n\ge 2$ $F(1)=a$ ...
1
vote
1answer
59 views

What does the histogram of values of a function on the y axis converge to?

I have implemented the following algorithm: ...
1
vote
2answers
41 views

Algorithm of order $O(n)$

Design an $O(n)$ algorithm, that given a real number $x$ and a sorted array $S$ of $n$ numbers, determine whether there exists any two elements in $S$ whose sum is exactly $x$. The solution I have ...
3
votes
2answers
101 views

Fibonaaci Recurrence

This is an interesting question where we are trying to solve another recursion which has same tree structure as the given recursion and also has term similarities Given Data in question ...
4
votes
2answers
111 views

Largest Equilateral Triangle in a Polygon

Is there an algorithm to determine the largest equilateral triangle in a convex polygon?
1
vote
0answers
84 views

Sparse matrix algorithms involving data-driven or random access / walk

I am looking for some well-known algorithms in which sparse matrix elements are accessed in a non-structured way, i.e. row/column depends on a value of another (sparse) matrix/vector element or some ...
1
vote
0answers
54 views

Solving the recursion $F(n)=K_0F(n-1)/(n-1)+K_1F(n-2)/(n-2)$

Please help me in solving the recursion $F(n)=K_0\frac{F(n-1)}{n-1}+K_1\frac{F(n-2)}{n-2}$, preferably using power series for the values of $F(n)$ in terms of $n$. Here $K_1$ and $K_2$ are ...