Mathematical questions about Algorithms, including the Analysis of Algorithms, Combinatorial Algorithms, proofs of correctness, invariants, and semantic analyses

learn more… | top users | synonyms (1)

1
vote
1answer
107 views

How to search between $n$ candidates from unknown position?

It might be involved more with search algorithm but I cannot think of any of them. Here is the problem: You are in a corridor that stretches infinitely in both directions. Your room is somewhere ...
0
votes
0answers
31 views

finding quadilaterals from given sides

I have a set of Points. I triangulated the Points as delaunay triangles but i only have edges for the triangles means edge array of the whole set of Points. Now i need to find the traingles and ...
0
votes
1answer
26 views

How to check if a 2D mesh is connected

I'm trying to optimize structures by using FEM and genetic algorithms (GA), the FEM solver is a commercial one, and I'm programming the GA. Something like this. My first approach is simple, just ...
0
votes
1answer
26 views

Fast Fourier Transformation: inverse transform of the product of polynomials

I have managed to implement and understand most of the Fast Fourier Transformation. However, I have one last question. If one has two polynomials, say $A(x)$ and $B(x)$, and one computes DFT of ...
0
votes
0answers
10 views

KMP Algorithm-Longest prefix which is also a proper suffix

Im trying to learn KMP Algorithm, im watching this video on KMP algorithm http://youtu.be/SVKe7bvQ4Xk?t=5m4s There is a statement in the video for determining π[K].It says length of longest prefix of ...
0
votes
1answer
44 views

Algorithm for finding contradictions in a directed graph that represents implications

I need an algorithm that does this: For a directed graph where nodes represent boolean values and edges represent implication (implies TRUE and implies FALSE): If (arc exists between any ...
0
votes
1answer
63 views

Solving the recurrence relation $T(n)=4T\left(\frac{\sqrt{n}}{3}\right)+ \log^2n$

How we calculate the answer of following recurrence? $$T(n)=4T\left(\frac{\sqrt{n}}{3}\right)+ \log^2n.$$ Any nice solution would be highly appreciated. My solution is: $n=3^m \to ...
1
vote
2answers
48 views

Find if a number lies in this pattern

I have a sequence of numbers below... $1, 2, 4, 7, 11, 16 ...$ You get this list by starting at $1$ then add $1, 2, 3, 4, 5 ...$ Given a number $n$, how can I determine if it will show up in this ...
1
vote
1answer
41 views

Recurrence Relation - Merge Sort

We know the recurrence relation for normal merge sort. It is T(n) = 2T(n/2) + n. After solving it we can get T(n) = cnlogn. I ...
0
votes
0answers
21 views

Multi-armed bandit optimization

I've got a variation of multi-armed bandit problem, where I need not to minimize the regret, but to find a bandit with a maximum reward. Could you please tell how this problem is called or suggest ...
1
vote
0answers
25 views

Computing rotating pairs

I'm trying to develop an algorithm that my software development team can use to pair off for daily stand-up calls. Each dev should be paired with every other dev before there is a repeat. In other ...
1
vote
2answers
46 views

Solve $T(n) = T(n-1)+\log^2(n)$

I was trying to solve $T(n) = T(n-1)+\log^2(n)$ using substitution method and variables substitution but I can't find the correct answer. My attempt: Let $m = \log(n)$ then $T(2^m) = ...
1
vote
1answer
49 views

Residue class of a huge repunit modulus a huge number

Given a number with only 1: X = 1111...1 (N times 1 in total), and another number M, I want ...
1
vote
1answer
40 views

Arrange blocks to form matrix of $N \times 3$

Given are the blocks of 3 different colors (Red,Green and Blue). Red colored block of size $1 \times 3.$ Green colored block of size $1 \times 2.$ Blue colored block of size $1 \times 1.$ ...
0
votes
1answer
60 views

Count numbers with prime digit

Given a number N I need to find the count of the numbers that have atleast one prime digit (2,3,5 or 7) in it. Now N can be upto 10^18.What is the best approach to solve this problem. Example : Let ...
0
votes
2answers
50 views

Solving polynomial to get all coefficients

Given an array of N integers where N can go upto 10^4 and each element can be upto 10^5. Now i need to find the coefficients of polynomial p that is given as : ...
1
vote
1answer
50 views

Find if arrangement is possible or not

The company has k buses and has a contract with a school which has n students. The school planned to take the students to d different places for d days (each day in one place). Each day the company ...
1
vote
2answers
112 views

What algorithm do i need to solve my problem?

unfortunately I even don't know what kind of problem I deal with. But I'll try to explain as good as I can and maybe you can tell what kind of problem this is and how to solve it. I want to find ...
1
vote
1answer
22 views

How to get a function similar to the ELO ranking system

I'm not an expert in maths. I'm looking a function similar to the ELO system in order to give the users a score. Those are the requirements for the system: The score must be between -100 and 100 ...
0
votes
2answers
96 views

Modulus of large powers

Given an array of N integers where $2 ≤ N ≤ 2×10^5$ and each element in array is less than $10^{16}$. Now I am given a variable $X$ that can also go up to $10^{16}$. We need to find if $X \mid ...
2
votes
0answers
80 views

Finding optimal velocity profile using Dynamic Programming

This question has been asked on scicomp but I thought maybe it's more a mathematical problem of how Bellman's idea is to be applied here. The main problem for me is: How to introduce the time ...
-2
votes
1answer
258 views

Modulo of a large sequence of $1$s

Given two numbers $N$ and $M$, we need to find the remainder when $111 \cdots1$ ($N$ times) is divided by $M$. Here $N$ can go up to $10^{16}$ and $M$ up to $10^9$. How to solve this problem? ...
2
votes
1answer
20 views

Non probabilistic algorithm for min-cut problem?

I know about Karger's algorithm and its variations, all of them being probabilistic. Is there non-trivial (i.e. non-brutefoce) deterministic algorithm for mincut problem?
0
votes
2answers
27 views

Get neighbors for N dimensional square

I need some algorithm to get neighbours of x vertex of N dimensional square. Thanks in advance.
1
vote
0answers
59 views

Integer partitions without rotated solutions?

I'm searching for an algorithm to determine a list of all integer partitions of a number $n$ into a fixed number $m$ of summands (say $n=6$ and $m=4$), for instance to be stored into a list of ...
2
votes
0answers
33 views

Speed dating/networking challenge

I am trying to organise an event with 54 participants. I want them to participate in 9 different activities at stations around a hall. Obviously this will require 9 sessions to allow the participants ...
1
vote
4answers
59 views

How to prove correctness of this algorithm

Situation There is a long patch of grass with seeds planted along it. Each seed needs to be within 2 metres of a sprinkler in order to be watered daily. Describe an algorithm that will result in ...
0
votes
3answers
80 views

Is this approach for testing orthogonality/parallelity of vectors wrong as I think?

In a math book four methods are written for testing parallelity/orthogonality of two vectors that are(notice $\vec v$ and $\vec w$ are approximations of vectors and we have x,y and z components of ...
4
votes
1answer
42 views

How do I detect anomalies in a real-time data

I'm trying to find a few good algorithms which could solve the problem of finding anomalies in my data. One of the main problems is that I need to find it in the real time data. So I came out with ...
1
vote
0answers
38 views

Alternating Direction Method of Multipliers (ADMM) application

$\newcommand{\argmin}{\operatorname{argmin}}$ Recall, that ADMM algorithm solves the problem of the form: $\min \text{ } f(X) + g(Z)$ $\text{s.t. } AX + BZ = C$ where $X$, $Z$ and $C$ are real ...
0
votes
1answer
31 views

Evolutionary algorithm

Can someone provide me a good reference for the CMA-ES algorithm? I'm new in the world of optimization and just reading the author reference doesn't help me a lot. I know the basic idea of a genetic ...
2
votes
2answers
153 views

For recurrence T(n) = T(n − a) + T(a) + n, prove that T(n) = O(n^2 ) complexity

I have been looking over this question for hours now, and can't seem to work it out. It's a question regarding the complexity of sorting algorithms Assume that $a$ is constant and so is $T(n)$ for $n ...
1
vote
0answers
47 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
20 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
32 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 ...
4
votes
5answers
93 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
20 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
99 views
0
votes
1answer
84 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 ...
2
votes
1answer
52 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
67 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
43 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
95 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
271 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
20 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
36 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
60 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 ...
6
votes
3answers
132 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
78 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
121 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?