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
3answers
36 views

Nth value of Function

Given x and y we define a function as follow : f(1)=x f(2)=y f(i)=f(i-1) + f(i+1) for i>2 Now given x and y, how to calculate f(n) Example : If x=2 and y=3 ...
1
vote
3answers
917 views

Find an odd-length cycle in an undirected graph.

I have an exam next week and I found a question that I have difficults to solve: Given the following: Input: Simple undirected graph $G(V, E)$. Output: Find an odd-length cycle in $G$ or ...
0
votes
0answers
118 views

Backward Substitution Method Questions

Question-1 is, G(n) = 2G(n-1) if n is odd and n≥1; G(n) = G(n-1)+G(n-2) if n is even and n>0; G(0) = 1 Solve for both odd and even values of n. Use backward substitution method ? I suppose; In the ...
3
votes
1answer
74 views

Partial sums of Pillai's function

Pillai’s arithmetical function (gcd-sum function) is defined by $$ P(n) = \sum_{k=1}^n\gcd(k,n) $$ Let $\sum_{n\leq x}P(n)$ be summation of all values of P for all $n$ up to given $x$. I dervied that ...
0
votes
1answer
24 views

Given a value and an arbitrary range, finding equivalent value in other arbitrary range

While strictly related to a programming project of mine, the problem in itself boils down to a math problem, as I am not sure which steps to take to produce the results i need. I have an input value ...
3
votes
4answers
675 views

Numbers whose digits sum to 7

Let $S$ be the sequence of all positive integers whose decimal digits add to exactly 7, in increasing order: $$S = \langle7, 16, 25, \ldots, 70, 106, 115, 124, \ldots 160, 205, \ldots, 10230010, ...
1
vote
1answer
132 views

Merge two or more cubic Bézier curves for optimization

I am looking for an algorithm which can merge several cubic Bezier curves. For instance, I have a lot of cubic Bezier that are joined to form a poly-Bezier curve. The idea is to merge dynamically some ...
1
vote
0answers
96 views

Iterative Mean, Covariance Algorithm Convergence

The problem is to show that the following iterations converge to the vector $\mu$ and the matrix $\Sigma$. We have data in the form of nx1 vectors $\mathbf{Q}_k$, $1 \leq k \leq N$ where ...
7
votes
1answer
527 views

Optimal Tic Tac Toe algorithm without lookahead

Is there any algorithm for tic tac toe that does not rely on a lookahead algorithm that is perfect for any sized boards? Edit: For boards larger than $3 \times 3$, we have to find the best move for ...
6
votes
4answers
80 views

$k$-th number in $N \times M$ Table

Given an array $A$ , where $A[i][j] = i\times j$ and $1 \leq i \leq N, 1 \leq j \leq M$ , then what is the best way to find the $k$-th number in this array , if we order them into a single array in ...
3
votes
1answer
58 views

Partition of graph with maximal score

Let $G=(V,E)$ be an undirected graph. Suppose that we partition the nodes into groups $C_1,C_2,\ldots,C_k$. The score of group $C_i$ is $E(C_i)/n(C_i)$, where $E(C_i)$ is the number of edges within ...
0
votes
1answer
77 views

Need to figure out how to do the math for deck of cards using different searches.

Below are the two questions I found from the websites ( I have added the link below ), that I am interested in learning the answers. My intention are not to post the answers for that guy but, I ...
0
votes
0answers
55 views

Global optimization

Assume that I want to find the global minimum of a non-linear, non-convex, multidimensional function subject to several restrictions. Could you recommend me any deterministic strategy which can ...
-1
votes
1answer
229 views

Number of ways to win chocolate game

Alice and Bob are playing a game. They have N containers each having one or more chocolates. Containers are numbered from 1 to N, where ith container has A[i] number of chocolates. The game goes like ...
3
votes
3answers
357 views

Solving inhomogenous ODE

I have an inhomogenous ODE. The main issue here is variables are matrices. It is bit of matrix calculus. A solution would be highly appreciated interms of x . I guess we can use same methods for ...
0
votes
4answers
59 views

Is it correct to write gcd(a,b) if a<b?

While creating an algorithm to compute the greatest common divisor of two numbers I saw that — on various websites/books — when you have "gcd(a,b)" a is superior to b ; is it an obligation or am I ...
4
votes
2answers
161 views

Given $N$, what is the next prime $p$ greater than $N$?

Certain data structures in programming related to collections operate in an optimal way if they have prime number of elements. This means if a program (programmer) requires $N$ (any natural number) ...
0
votes
0answers
99 views

Please give me an example of the algorithm where $\Theta$ will be equal to $e^n$

Please give me an example of the algorithm where $\Theta$ or $O$ will be equal exactly to $e^n$ . The algorithm should not be simple counting from 0 till $e^n$ . It should be a clear relation of two ...
1
vote
0answers
56 views

$U(n) =$ the smallest strictly positive integer $k$ such that $2^k-1$ is divisible by the first $n$ primes. What are the first values of $U(n)$?

$U(n) =$ the smallest strictly positive integer $k$ such that $2^k-1$ is divisible by the first $n$ prime numbers (except for the first prime number: $2$). What are the first values of $U(n)$ up to ...
1
vote
1answer
71 views

Graph Isomorphism algorithm that doesn't always work

I just thought of the following incomplete algorithm for deciding whether two graphs are isomorphic: Let $A$ and $A'$ be adjacency matrices of two graphs. Then for some unitary $U,U’$ and diagonals ...
3
votes
1answer
227 views

How to solve this recurrence Relation - Varying Coefficient

Sir,I have two questions related to this recurrence relation. It has been messing with me for long. Because of this I couldn't proceed my work for some time .This contains a polynomial term n+2 in ...
2
votes
2answers
2k views

Determinant of complex matrix

How is the determinant of a complex matrix calculated? Is it the same algorithm as for real matrices, but the determinant itself is complex instead of real? (I was unable to find any hints with ...
0
votes
1answer
71 views

Algorithm for Stepping Through Latitude, Longitude and Height with a Heading

I have a function which reads in latitude, longitude, height, heading and step size. My function should calculate the latitude, longitude and height of the position one step size away in the direction ...
-1
votes
1answer
52 views

Probability of 1 at both end of string

Given a string S having N characters long and consists of only 1s and 0s. Now given an integer K, let us pick two indexes i and j at random between 1 and N, both inclusive. What's the probability ...
0
votes
1answer
88 views

Parity of number of factors up to a bound?

Consider $b,n\in\mathbb{N}$ where $b\leq n$. We want to find the parity (ie. odd or even) of the number of divisors of $n$ that are $\leq b$. The question is to find a fast algorithm to find that ...
1
vote
1answer
98 views

Normal number generator with digit extraction algorithm?

Are there any known ways to define an absolutely normal number (or very likely normal) number, which posses digits that can be extract via algorithm? I want to find numbers like pi that are normal and ...
3
votes
1answer
473 views

Checking connectivity of adjacency matrix

What do you think is the most efficient algorithm for checking whether a graph represented by an adjacency matrix is connected? In my case I'm also given the weights of each edge. There is another ...
0
votes
0answers
51 views

Data structure issues with incremental Delaunay triangulation

I am implementing the incremental algorithm of Delaunay triangulation with a data structure based on Faces (triangles): 3 vertex indices and 3 Neighbor indices. The issue I have is that the structure ...
0
votes
1answer
57 views

Find longest vector by summing some vectors in given set

Given $n$ vector $(x_1, y_1), (x_2, y_2),(x_3, y_3),\dots,(x_n,y_n)$. Find a subset S of vector such that $\text{}\left |\sum_{v\in S} v\right |$ Sorry for my English. Please give me a hint how to ...
-1
votes
1answer
31 views

Inductive Proof Algorithm

so I'm working on an algorithms assignment and am having a tough time understanding what to do: The equation is: $$T(n) = 2T(n/4) + n = \Theta(n) = O(n)$$ Right now I have gotten this far: $$T(1) = ...
0
votes
1answer
198 views

Building bicubic coons patch from four boundary curves

I want to create s coons patch surface from four boundary curves s1(u), s2(u) q1(v), q2(v) I know that equations are the following (added screenshots from a presentation): There are a few ...
1
vote
2answers
50 views

How to find the asymptotic behavior of these sums?

Let $$X(n) = \displaystyle\sum_{k=1}^{n}\dfrac{1}{k}.$$ $$Y(n) = \displaystyle\sum_{k=1}^{n}k^{1/k}.$$ $$Z(n) = \displaystyle\sum_{k=1}^{n}k^{k}.$$ For the first, I don't have a formal proof but I ...
3
votes
0answers
25 views

Connected graph where edge costs depend on a parameter $t$. Find the $t^*$ which gives the minimum cost minimum spanning tree.

The set-up: Let $G=(\,V,\,E\,)$ be a connected graph. Associated with every edge $e\in E$ is a cost/weight function $f_e(t) = a_e t^2 + b_e t + c_e $, where $a_e>0$. For a fixed $t$ we can define ...
1
vote
0answers
30 views

Enumerating certain size 15 square matrices

This is an attempt to tackle A zero sum subset of a sum-full set by complete enumeration. I am looking for an algorithm which will efficiently (i.e. within reasonable time, several hours at the most) ...
1
vote
1answer
98 views

Find 3rd largest number out of 7 under at most 11 comparisons

I know similar problem like "sort 5 numbers in 7 comparisons". I know no general algorithms exist. Do I just enlist all possible game trees?
0
votes
1answer
49 views

How to simulate from a simple point process

Define a point process by the conditional intensity function $$\lambda^*(t) = \mu + \alpha \sum_{t_i < t} e^{-(t-t_i)}$$ where $\mu$ and $\alpha$ are positive parameters. I would like to ...
0
votes
1answer
33 views

formula for getting the least amount in the last column

I'm looking for a formula, that given $x ≥ 5$ , it will split $x$ over 3 columns with the least amount in the 3rd column, however the 3rd column must be > 0. so where $x = 5$ it would look like: ...
0
votes
2answers
61 views

The value of loop variable at the end of a loop in the insertion sort

I am looking at the algorithm of the insertion sort: Input: $A[1 \dots n]$ ...
0
votes
0answers
32 views

Produce a list of the most-similar units, given various correlations/relationships

I have a database full of units (U1 - U50, U51...) where every unit has the same standard attributes (A1 - A10) and where a % of each attribute defines the amount of that attribute for that particular ...
1
vote
1answer
65 views

Assign most people their first choice based on a list of preferred choices

Given a list of choices (say 100), each person in a list (say 30) has to choose 5 choices in the order they would like them to be assigned. How would I assign each person a choice making sure as many ...
1
vote
0answers
265 views

A good book with algorithmic puzzles with solutions (not of kind “how to pass and IT interview”)

can you please advise me a book with algorithmic and mathematical (IT-oriented) puzzles. But I want not one more book of kind "How to pass an interview in Microsoft / Google / any other big company" ...
5
votes
1answer
114 views

filling an occluded plane with the smallest number of rectangles

I've got a specific problem which I'll try to describe as clearly as possible. I have a defined rectangular region on a cartesian plane, and within that region there are other given rectangular ...
0
votes
1answer
33 views

Is there a quick way to obtain $a,b$ in $ax+by = z$ where $x,y,z$ are fixed and $x+1 = y$?

Suppose that all numbers are postive integers. Let $x,y,z$ be fixed/given and $x+1=y$. Then would there be a quick way to find set of solutions $(a,b)$ that satisfy $ax+by=z$? "Quick" would be ...
1
vote
0answers
37 views

Can I solve this problem with matrices?

So I have some two dimensional data sets thats I want to analyse. They can be viewed in 2D form as below: $M1$: $$\begin{matrix}00 & 00 & 00 & 00 & 00 & 00 & 00 & 00 ...
3
votes
1answer
77 views

Total number of possible sub sequence with given condition

Given a sequence of two letters A and B find the total number of possible sub sequences where number of letter A is two times the number of letter B without ...
6
votes
2answers
161 views

How was the $3x+1$ problem checked up to $5 \times 2^{60}$?

The Wikipedia article for the Collatz conjecture states that: The conjecture has been checked by computer for all starting values up to $5 \times 2^{60} \approx 5.764 \times 10^{18}$. It gives ...
0
votes
2answers
215 views

Count the whistles

Sports Teacher gathered all the players in his garden and ordered them to line up. After the whistle all players should change the order in which they stand. Teacher gave all the students numbers ...
1
vote
2answers
411 views

Most Efficient Method to Find Roots of Polynomial [duplicate]

I am designing a software that has to find the roots of polynomials. I have to write this software from scratch as opposed to using an already existing library due to company instructions. I currently ...
0
votes
0answers
48 views

Biggest common sub-string search asymptotics

What is the function of Big-O in case where we use brute-force on two strings to find the biggest common sub-string. Please can you explain the underlying logic to the resulting formula corresponding ...
0
votes
0answers
124 views

Finding smaller matrix in bigger matrix

Given a bigger matrix of size R*C .Where each element of matrix is between [-20,20]. Now i need to find a smaller matrix of dimension H*W (H <= R, W <= C) in such a way that sum of squared ...