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
0answers
43 views

How to solve division one digit at a time?

I’m developing a computer program and I’m trying to work out some arithmetic algorithms for working with very large numbers. So far I have worked out a plan for addition, subtraction, and ...
2
votes
2answers
65 views

Given $2n$ points in the plane, prove we can connect them with nonintersecting segments

Given $2n$ points on the plane such that no three points lie on one line. Prove that it is possible to draw n segments such that each segment connects a pair of these points and no two segments ...
0
votes
1answer
28 views

Two-sigma notation k-means clustering

I have referred to this question: Two sigma notation, to get an understanding of how two-sigma notation works. But this is insufficient for my purposes. I am looking at a k-means clustering ...
1
vote
2answers
24 views

Find algorithm for converting number to Balanced ternary

I have this math question, I have to find an algorithm that is able to convert any number to balanced ternary. Balanced ternary is like ordinary base $3$ in the sense that the positions are ...
0
votes
0answers
9 views

GMRES method In matrix, how to set $x_0$

I am not sure if my question is reasonable or not, but because I'm not good at matrices I had to ask this question in here. This is the algorithm of The Generalized Minimum Residual Method (GMRES). ...
1
vote
1answer
16 views

Levenshtein distance calculations

What is the correct Levenshtein distance between the following strings? hahaha ahahah These sites report different values: ...
1
vote
1answer
25 views

Scheduling problem on bipartite graph

Consider a bipartite graph $(G, U, V)$. Each $v$ in $V$ represents a soccer team, and each $u$ in $U$ represents a mini-tournament needs to be scheduled. If $u_i$ and $u_j$ share no common neighbor, ...
3
votes
1answer
47 views

Bicolour Towers of Hanoi

I am trying to solve Bicolour Towers of Hanoi problem. It is a variation of classical Towers of Hanoi problem. There are $3$ pegs (let's call them $A$, $B$, $C$) and $N$ disks on peg $A$. Disks have ...
0
votes
0answers
38 views

What is the fastest algorithm for finding shortest path in undirected edge-weighted graph?

I am looking for the most efficient algorithm for finding shortest path between two Vertices. The graph is: undirected edge-weighted Non-negative less then 300 nodes I understand that most of ...
1
vote
0answers
23 views

Is Richardson iteration algorithm backward stable?

How do we analyze the numerical stability of Richardson iteration algorithm? Can we say it is backward stable?
0
votes
0answers
12 views

Is there a way to find the limit of a function algorithmically?

Is there a certain sequence of instructions that one may use to find the limit of a function? I know that, $\lim_{x \rightarrow c}f(x)=L$ iff $f(x)$ gets arbitrarily close to $L$ as $x \rightarrow c$, ...
0
votes
0answers
92 views

More intuitive/easier explanation for Knuth's division algorithm needed

Knuth's division algorithm, here refers to the D algorithm mentioned in TAOCP written by Donald Knuth in Volume 2 (Semi-numerical algorithms) Section 4.3.1 I have been trying to understand the ...
2
votes
0answers
28 views

Probabilistic methods and equations over $m$-dimensional space

Given a set $A$ of $n$ different points in the space $(\mathbb{Z}_p)^m$ (assume $p$ is prime), and given $\delta>0$. show the following property holds for a big enough $n$ and $p$ (you can demand ...
1
vote
0answers
36 views

question about isolation lemma.

Given the set $\mathcal{F}\in\mathcal{P}(\{1,...,m\})$, I need to provide it with probability $\frac{1}{2}$ a weight function $w:\{1,...,m\}\rightarrow\{1,...,n\}$ such that there will be a single ...
1
vote
2answers
32 views

Unprovable behavior of a turing machine

The wikipedia-article for the P-NP problem [1] says there are three possible answers to the P-NP-problem: $P=NP$ $P\neq NP$ $P=NP$ is independent of ZFC The third possible solution seems to be ...
0
votes
1answer
34 views

Are there shortcuts for predicting whether an exponential function will evaluate to a positive or negative value?

I'm a software architect, working on some algorithms involving unique storage formats for large numbers. The function I'm working with is:$$y = \frac{mx^p+b}{d}$$ ... where $p$ and $d$ would ...
0
votes
1answer
44 views

How to generate all possible SEC matrices for $n$-bit

I want to know if there is an algorithm with which man can generate all possible forms of single error correction matrices for n bits of data, both linear and non-linear. For example all possible ...
8
votes
2answers
170 views

Finding an algorithm for the given problem

Let's presume that we have a PVP fight scene, where 1 or 2 heroes, are fighting 3 monsters. The monsters that the heroes are fighting are the following: Skeleton (2 of this monster) ...
0
votes
2answers
52 views

Fewest operations on an algorithm?

I'm very stumped on this problem I have and was wondering if anyone could lend me a hand here? Suppose that you have two different algorithms for solving a problem. To solve a problem of size $n$, ...
2
votes
1answer
39 views

Extended Josephus permutations generated by keyword

The (well known) generalized Josephus algorithm consists in starting from the ordered set $Z_n=\{1,2,...,n\}$, and choosing and removing cyclically from left to right each m-th element until the set ...
3
votes
4answers
75 views

Recurrence relation $T(n+1)=T(n)+⌊\sqrt{n+1}⌋$?

Consider the following recurrence relation $T(1)=1$ $T(n+1)=T(n)+⌊\sqrt{n+1}⌋$ for all $n≥1$ The value of $T(m^2)$ for $m≥1$ is $(m/6) (21m – 39) + 4$ $(m/6) (4m^2 – 3m + 5)$ $(m/2) (m^{2.5} – ...
-4
votes
1answer
26 views

Designing an Algorithm to find the length of a simple cycle in a d-regular graph [closed]

I understand the question in general but don't know how to design and analyze the algorithm in the question. I was thinking of applying some sort of graph search algorithm like depth-first / ...
5
votes
0answers
75 views

Does Pollard rho works for Gaussian integers?

Should I expect that the Pollard rho method ...
0
votes
2answers
118 views

Write recurrence relation for above algorithm and solve it using Iteration Method.

Consider the following recursive algorithm for computing the sum of the first $n$ squares: $\sum \limits _{i=1} ^n i^2 = 1^2 + 2^2 + \cdots + n^2$. Algorithm: ...
0
votes
2answers
319 views

Write an algorithm to find minimum number from a given array of size ‘n’ using divide and conquer approach.

In Divide and conquer strategy, three main steps are performed: Divide: Divides the problem into a small number of pieces Conquer: Solves each piece by applying divide and conquer to it ...
2
votes
2answers
578 views

A Seating Optimisation Problem

Suppose that you have a cinema hall of size $n\times m$ (where $n$ is the number of rows and $m$ the number of seats in a row). Now, given that there are exactly $l$ people who need only the left ...
-1
votes
1answer
39 views

Graph Algorithms Question (Design and Analysis)

I'm trying to design the algorithm and answer these two questions but can't produce a solution. I've tried drawing the pictures for the graph as well.
0
votes
1answer
29 views

Graph Theory Problem (Algorithms)

I'm having difficulty in approaching this problem and coming up with a solution. I'm not sure where to start in answering this question.
-1
votes
1answer
67 views

Lower bound for two eggs problem

I have just read about two eggs problem. I know that with decreasing amount of jumps we can reach worst case scenario of first jump $a = \sqrt{2n}$, $n$ is the number of floors, how about the lower ...
0
votes
1answer
40 views

Efficient extraction of coefficient from generating function

In Mathematica I give input for generating function: Series[Exp[x + x^2/2], {x, 0, 6}] It gives output: $$1 + x + x^2 + \frac{2x^3}{3} + \frac{5x^4}{12} + ...
0
votes
1answer
48 views

Prove $\log(n) = O(n)$ using induction

I am using the lecture notes here on page 19 (Algorithm Notes 1) example 1 is the inductive proof of $\log(n) = O(n)$. I understand the base case but I don't understand the rest of the example. ...
0
votes
1answer
58 views

Calculating distance of closest pair of $n$ points in unit square

There are $n$ points are placed in a unit square. Show that the distance between the closest pair is $O(\frac{1}{\sqrt{n}})$. My intuition is that the solution would involve using ...
3
votes
0answers
77 views

A variation of Buchberger algorithm

Let $I$ be an ideal of a polynomial ring $R$. Fix a monomial order. Denote the $S$-polynomial of $f, g\in R$ by $S(f, g)$ and denote the gcd of their leading terms by $T(f, g)$. Consider the ...
1
vote
2answers
68 views

Must an algorithm terminate?

I am confused. Sometimes i read about terminating and not terminating algorithms. I almost always read these things in the context of turing machines. This means to me: There are algorithms which ...
1
vote
0answers
31 views

Big O Notation Clarification

Working through a textbook on algorithms (CLRS intro to algorithms) and just wanted to see if someone could help me understand one of the exercises at the end of a chapter. Problem: Is $n^{2 + 1} = ...
0
votes
0answers
8 views

NP-Complete: reduce “L” the language such as circuits C1 and C2 compute the same function

I'm trying to reduce the NP-Complete language "CIRCUIT-SAT" (C is a boolean circuit that is satisfiable) to my language L, but my classmates are pointing out that i'm actually doing the opposite, ...
-1
votes
1answer
43 views

Time Complexity

Prepping for an exam and wondering whether I correctly calculated the time complexity. Function is given as: $function XYZ(n:integer)\\ begin for\ i:=1 \ do \ 2*n^2 \ do;\\ ...
0
votes
0answers
7 views

Predicting possible inputs leading to output satisfying certain condition

Suppose there is a data set of statistical data with a number of input columns and one output column. The predictors characterize some particular process that is repeated, so one data row is ...
0
votes
1answer
22 views

How the xor sum algorithm is connected with or?

I was searching for a solution to the problem: For a given array of numbers find the sum of xor of all possible subsets. Here xor of a subset is the value comes from xoring all the elements of that ...
2
votes
3answers
107 views

Finding XOR of all even numbers from n to m

Problem : Given a range $[n,m]$, find the xor of all even numbers in this range. Constraints : $1 \le n \le m \le 10^{18}$ How do we solve this problem? P.S. I asked this question at stackoverflow ...
0
votes
0answers
11 views

a special minimum weighted matching in bipartite graph

Recently, I encounter an interesting minimum weighted edge cover problem in bipartite graph, and unfortunately I cannot solve it. Consider a bipartite graph $G=[U,V,E,W]$, where $U,V$ is the vertex ...
3
votes
1answer
34 views

Algorithm for assigning users to “buckets” according to users' preferences and ranking

Suppose there is a set of $n$ users which must each be assigned to one, and only one, of $k$ mutually exclusive "buckets". However, the number of users allocated to the $i$-th bucket must be no lower ...
0
votes
0answers
84 views

Creating shapes, just with rotations

I have a game with orbiting objects, these objects can orbit around a point. But this point itself can orbit around a point. So my Question is, is it posible to create any closed shape with this ...
0
votes
0answers
21 views

Are variables in mathematic algorithm syntax scoped like in programming languages?

In a programming language, a variable is only valid in its own scope and can be redeclared in another scope, such as: { int i = 4; } { double i = 1.2; } But how ...
0
votes
0answers
41 views

A book to study machine learning and code from scratch?

I have a basic understanding of mathematics, stats and I wanted to learn machine learning alogorithms and learn how to code them from scratch. Is there an book out there which I can turn to which will ...
1
vote
0answers
24 views

Inverting a sparse Matrix

I have a sparse, square, symmetric matrix with the following structure: (Let's say the size of the matrix is N x N) the structure of the sparse matrix Here, the area under the blue stripes is the ...
0
votes
1answer
19 views

What is the upper bound on the Diameter of a connected Graph?

I am writing a program in Java where I have to store the shortest path for each vertex in a two-dimensional array. I know the number of verticies, so the number of rows is known but I don't know the ...
1
vote
2answers
26 views

Summation of differences in exponent

Came to this summation during an algorithm analysis problem and any help would be much appreciated:$$\sum_{j=1}^n3^{n-j}$$
1
vote
2answers
44 views

Fast verification of solution to x'Ax<C

Assume we have some complex vector with N dimensions $\vec x$. We need to verify if this is a valid solution to: $\vec x^HA\vec x<C$ where $A$ is a Hermitian matrix and $C$ is some real ...
0
votes
0answers
19 views

Decimal multiplication ( primary school algorithms ) and relations to the Fourier Transform.

I suppose most of us are familiar with multiplication algorithms for decimals numbers we learn in primary school. 13*13 = 3*13 + 10*13 = 169 what actually is performed in this case (but of course they ...