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
1answer
43 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
51 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
116 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
296 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
577 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
66 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
47 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
57 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
20 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
32 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
23 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
17 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 ...
2
votes
0answers
37 views

Using $\pi$ to number by X-mas presents

Context: For this X-max, I will make $50$ presents by myself for my family. I would like to label them so that the labels are totally ordered and all different. However, I think that the traditional ...
1
vote
1answer
36 views

How to find the number of $n$ for which $n!$ is divisble by $a$ but not $b$?

The values of $a$ and $b$ are known . I need to find the number of $n$ for which $n!$ is divisible by $a$ and not by $b$. Suppose $a=2$ , $ b=3$ then the possible solution is $1$ only for $n=2$.
2
votes
3answers
59 views

Efficient algorithm for optimization problem.

I had an interesting interview problem today. Let's assume that we have n boxes, containing many numbers. For instance, let's say $n=4$, and four boxes contain the following numbers: ...
0
votes
0answers
11 views

ID Assignment: Minimized Difference In Values

Say I have a 2D grid of squares, and I need to assign a unique ID value to each of the squares. I want to assign IDs such that the difference in value between any two adjacent squares is as small as ...
1
vote
3answers
117 views

Is there an algorithm to split a number into the sum of powers of 2?

Am I able to split, lets say 76, into the sum of powers of two, through an algorithm and without cycling through possible combinations? For the example above, the answer would be '2^6+2^3+2^2' or ...
0
votes
0answers
20 views

Group method of data handling (GMDH)

The task is to build mathematical model using GMDH (Wikipedia) and peform a forecast. There is initial data: x1 = 2; x2 = 2; x3 = 6; y = 18; The selection criterion to be used is the regularity ...
1
vote
1answer
23 views

Reorder one sequence into another one through swaps

I'm actually willing to know if the following lemma is true or not. (If true, how to proof it or else what is the counterexample?) Lemma. Given two sequence $s_1 = x_1, x_2, ..., x_n$ and ...
0
votes
0answers
175 views

DFS tree of a $K_{1,3}$-free connected graph

Let there be $G=(V,E)$ a connected, $K_{1,3}$-free graph. (A $K_{1,3}$-free graph is a graph which has no 'claw' structures in it, where a claw structure refers to a vertex that has $3$ edges ...
0
votes
1answer
17 views

Is finding the largest subgraph in a graph where every vertex in the subgraph is connected to every other vertex NP-Complete

Is there a way to find the largest subgraph in a graph where every vertex in the subgraph is connected to every other vertex in the subgraph? Or is such a problem NP-Complete? In math: $G = (V,E),$ ...
2
votes
0answers
36 views

Convex shape in ellipsoid containment test

Supposed you to want find out if an ellipsoid fully contains a convex shape. In the picture below I have drawn two situations. The left shape is overlapping with the ellipsoid, and the right shape is ...
0
votes
1answer
21 views

Logarithmic iterative algorithm for calculating $x^n$

Write a logarithmic iterative algorithm for calculating $x^n$ using successive multiplication, where $n$ is a perfect power of $3$. ...
0
votes
0answers
24 views

Write a logarithmic iterative algorithm

Write a logarithmic iterative algorithm for calculating x^n using successive multiplication, where n is a perfect power of 3. Help Please!
2
votes
0answers
18 views

Help solving the recurrence $W(n)=W(n/5)+W(7n/10)+\Theta(n)$.

Let $W(n)=W(n/5)+W(7n/10)+\Theta(n)$ for $n>5$ and $W(n)=\Theta(1)$ for $n\leq 5$. I want to show that $W(n)\in \Theta(n)$. Attempt 1 I understand the technique used in this question that solves ...
0
votes
0answers
15 views

Expected number of row operations of progressively populating a band matrix

Consider populate an $M\times M$ matrix $\mathbf{A}$ with randomly incoming length-$M$ row vectors: each row vector may have non-zero elements only at indices $i,i+1,\ldots, i+W-1$, where ...
0
votes
0answers
19 views

Maximum points on boundaries

Given $N$ points on a $2D$-plane of type , each coordinate of type $(x,y)$. We need to make a rectangle on this plane in such a way that maximum number of points lie on the boundary of this rectangle. ...
2
votes
1answer
39 views

Finding DFS in undirected graph

Consider the following sequence of nodes for the undirected graph given below. a b e f d g c a b e f c g d a d g e b c f a d b c g e f A Depth First Search (DFS) is started at node a. The nodes ...