Mathematical questions about Algorithms, including the analysis of algorithms, combinatorial algorithms, proofs of correctness, invariants, and semantic analyses. See also (comptutational-mathematics) and (computational-complexity).

learn more… | top users | synonyms (1)

0
votes
1answer
31 views

Is there a way to compute if(i < j) k := (a + b)c with polynomials over $\Bbb{Z}_p$?

Let $p$ be a prime and let all variables be in $\Bbb{Z}_p$. Then you can write the result of if(i > 0) k = (a + b)c; (C code) as a polynomial $k := ...
1
vote
0answers
32 views

What about generlizing grammars?

Say we came up with a finite grammar (specifies a finite number of strings) given a set of input strings. How then do we generalize the grammar so that it works for larger input strings and also ...
3
votes
3answers
628 views

Does a 15-puzzle always have a solution

For those that are not familiar with (this type of) sliding puzzles, basically you have a number of tiles on a board equal to (n * m) - 1 (possibly more holes if you want). The goal is to re-arrange ...
0
votes
3answers
52 views

grouping non-zero entries in a matrix according to a rule

I have a matrix say, $a = \left[\matrix{ 0 & 1 & 0& 0& 0& 1& 0\\ 0& 0 &0 &0 &0 &1& 1\\ 1& 0 ...
2
votes
2answers
105 views

summation of ceil and floor function

I need a closed solution or a faster algorithm for calculating $$ \sum_{k=1}^{n-1} \left\lceil \frac{n}{k}-1 \right\rceil $$ and $$ \sum_{k=1}^{n-1} \left\lfloor \frac{n}{k} \right\rfloor $$ where $ ...
0
votes
2answers
68 views

What is the difference between maximal flow and maximum flow?

I have tried a lot on internet, but I am unable to get a good answer on the difference between maximal and maximum flow in case of network flow. Anybody has an idea? with example would be really ...
0
votes
1answer
67 views

Placing two queens on an $n \times m$ chessboard

I want to find the number of ways in which two queens can be placed on a chessboard so that they can attack each other. two queens can attack each other on a row, a column or on same diagonal just ...
0
votes
1answer
61 views

Existence of a det. poly-time algo for problem $f: X \to Y$.

$f : X \to Y$ is a deterministic polynomial-time algorithm for problem inputs $x \in X$ and problem outputs $f(x) = y \in Y \iff $there exists a polynomial $P_f \in \Bbb{Z}[x_1]$ such that $C\cdot ...
1
vote
0answers
47 views

Check if an integer has any prime factors excluding some set

I'm looking for an algorithm that returns true if the set of prime factors of some number only contains values in some set $S$, and false otherwise Example: $S = \{2,5\}$ For the number $250$ the ...
0
votes
1answer
73 views

Proof by Induction Algorithm [closed]

I am stuck on trying to prove this algorithm using mathematical induction. ...
1
vote
0answers
34 views

Can cuts of size 2 be detected in linear time in an undirected, unweighted graph?

I'm having trouble finding any literature on the specific subject of 2-edge cut detection. It's not hard to come up with an algorithm that finds all 2-edge cuts in quadratic time, but it's not clear ...
0
votes
1answer
147 views

P, NP-Complete and NP-Hard Problems

I have confusion over P, NP-Complete and NP-Hard problems. I understand a polynomial time algorithm is one which can be solved for a an input string of length n. But why would a problem not be in ...
1
vote
2answers
45 views

Number of solutions for $xy<d$, where $x,y>1$

Is there a way we can determine number of solutions for equation $$xy < d$$ where $d$ is a constant and $x$ and $y$ are positive integers greater than $1$? I am not interested in actual ...
0
votes
1answer
35 views

Number of configurations in a constrained nested loops and configuration back from serial

Consider 4 counters looping the digits 0, 1, 2 to form the various "configurations", like in : ...
2
votes
0answers
76 views

Upper limit for adding N numbers in grid of N processors in parallel

We must show how N binary numbers, each consisting of N bits each, can be added in a linear grid of N+logN processors. Suppose that the binary digits can be inserted directly in each processor of the ...
0
votes
3answers
48 views

Algorithm - if known $x$ and $y$ value

I am new to this site, so please bear with my bad question-writing skills! I was given a puzzle, in which I have to work the algorithm being used to generate the $y$ value from the $x$ value. Here ...
0
votes
0answers
26 views

finding the least non-zero of a multivariable polynomial

Let $P(x_1,x_2,...,x_m)$ be a homogeneous polynomial of degree n, with integers coefficients. How can you find the least* $a=(a_1,a_2,...,a_m)$, where $a_i$ are positive integers and $P(a)!\neq 0$? ...
2
votes
0answers
86 views

Todd-Coxeter algorithm: coincidences

I'm trying to understand the Todd-Coxeter algorithm with the help of a multiplication and relator table, but there is one thing about coincidences that is not really clear. For some small groups (for ...
1
vote
0answers
53 views

Divisibility via Inclusion-Exclusion

Let $N$ be a large natural number, let $A$ be a subset of naturals, and ask: How many numbers $n\leq N$ are divisible by one or more numbers in $A$. This is a classical application of the ...
1
vote
1answer
52 views

How to test for a polygon witn n vertices if it's nonintersecting polygon or not?

How can you design an algorithm to know if an n-vertex polygon nonintersecting ? On what criteria is the test going to be
0
votes
1answer
202 views

Find all subsets whose sum modulo a value is 0.

How can we find the count of number of subsets of a given set (e.g. {1,7,4,90,23} ) whose sum is a multiple of a given value A. One method which I know of is to store all subset sums modulo A and ...
0
votes
2answers
43 views

What can be observed by evaluating a polynomial at roots of order greater than the polynomial itself?

I have been reading through an algorithms book on the use of FFT for large number multiplication. An example it used to emphasize a point was: Evaluate the following polynomial at all roots of unity ...
1
vote
1answer
67 views

Minimum Cut algorithm on undirected graph with no source or sink

When dealing with Minimum Cuts, what do you do when you are given an undirected graph without edge weights and no source and sink node? How do you modify the graph so that it can be used with ...
1
vote
3answers
164 views

How to choose the starting point in Newton's method?

How to choose the starting point in Newton's method ? If $p(x)=x^3-11x^2+32x-22$ We only learnt that the algorithm $x_{n+1}:=x_n-\frac{f(x_n)}{f'(x_n)}$ converges only in some ...
0
votes
3answers
55 views

How do you solve a equation by converting to logarithm form for the problem$3e^{x-4} +2=83$?

$3e^{x-4} +2=83$ I understand converting logarithms but i dont understand how to convert e into log form and solve. help would be deeply appreciated.
1
vote
0answers
27 views

Decentralized Algorithm for a one dimensional ring

I'm working on a homework in which a graph of n nodes is arranged as a one-dimensional ring and every node has 3 out-going edges. I need some help in proving that any decentralized algorithm would ...
1
vote
1answer
65 views

Matlab create matrix without loops

I'm trying to create a Matrix in Matlab, which is dependent on 2 control variables $i$ and $n$. They are defined like this: $i=1:10$, $n=0:N-1$. Now I'm trying to define a matrix, where an entry is: ...
0
votes
1answer
35 views

Reversing $\sum_0^kx\cdot2^i$

I'm trying to write an algorithm, and the easiest way I found for explaining the mathematical problem I'm facing is the following: Assume you have $x$ US dollars and you're gambling on a roulette. ...
2
votes
2answers
201 views

number of solutions of x*y<N [closed]

How many solutions (unique pairs (x,y) ) exist for equation $xy < N$ ? constraints : $x >1 , y>1 , N<=50000$ I tried following method , but it fails for say N=24 , in which i calculate ...
1
vote
1answer
40 views

Reverse engineering the objective function

If there is a finite iteration algorithm can we find a function that this algorithm optimizes, in hindsight? Edit: Suppose there is a set of functions $f_i(x)$, where $x\in \mathbb R^n$, ...
0
votes
1answer
86 views

Count Integers satisfying the conditions

Given some constraints ,I need to find possible ways that these conditions are satisfied. I need to find four POSITIVE integers a,b,c,d such that ad-bc > 0 and also a+d=N for a given value of N. How ...
1
vote
0answers
59 views

Given a set of generators of a group G, is there a method to find a presentation for G using those generators?

Suppose I have a group $G$, which I know is finitely presentable and infinite. (In particular, I have a presentation for it, though not the one I want). Suppose I have a small list of generators ...
0
votes
1answer
45 views

Tight bound of worst case performance of algorithm

I am trying to find the "tight bound of an algorithm for the worst case run time. I have found that the upper bound of the worst case is O(n), I have also found that the lower bound for the worst case ...
0
votes
1answer
77 views

efficient algorithm to place people in a specific order

You are preparing a banquet where the guests are government officials from many different countries. In order to avoid unnecessary troubles, you are asked to check the list of international conflicts in ...
0
votes
1answer
14 views

Mathematical algorithm to alter values to specific range

I have a scroll bar in a computer program that scrolls from is -1 to 1.Its initial value is 0 .I need it to scroll from 0 to 1 and the initial value to be 0.5 What is the mathematical way to ...
1
vote
3answers
43 views

How multiple of number is determined?

Problem 5 Project Euler 2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder. It is suggested in above example that, 2520 is divisible by ...
2
votes
0answers
65 views

Composing permutations in factorial notation

Given two permutations $p_1$ and $p_2$ in factorial notation, is there a direct algorithm which computes their composition directly, i.e. without translating to a different notation or via computing ...
0
votes
2answers
28 views

Relating number of iterations to n

n = length of list with more than n > 0. index = 0 step = 1 while index < n: index = index + step step = step + 1 return How many times will the loop ...
1
vote
1answer
349 views

Solving the recurrence relation $T(n) = T(n-\sqrt n) + 1$

I have an algorithm that at each step can discard $\lceil\sqrt(n)\rceil$ possibilities at a cost $1$. The solution to the recurrence relation below is related to the question of complexity of such ...
0
votes
1answer
24 views

return a number between 3 to 5 by get a number between 1 until 10000! [closed]

I want to have a math math formulas to do this operation: A:get a number between 1 to 10000 B:reteun a number between 3.00 until 5 for example 3.89 for greater number return greater number too! ...
0
votes
0answers
42 views

Find cardinality of set

I have faced the following problem recently: We have a sequence A of M consecutive integers, beginning at $A_{1} = 1$: $1,2,...M$ (example: $M = 8$ , $A = 1,2,3,4,5,6,7,8$ ) We have the set $T$ ...
1
vote
0answers
165 views

How do I measure the goodness of cosine similarity scores across different vector spaces?

I am a computer scientist working on a problem that requires some statistical measures, though (not being very well versed in statistics) I am not quite sure what statistics to use. Overview: I ...
2
votes
1answer
81 views

Soft Question: Algorithms: Will We (One Day) No Longer Need to Study Algorithms? [closed]

I'm just now getting into the study of algorithms and it seems like as computers get faster and faster the need to study algorithms may begin to diminish. How likely is it that in 50 years there ...
1
vote
0answers
50 views

Conjugate Gradient Method Near Exact Line Search

Unlike Newton-type methods, there is no natural step-length value $\alpha _k$ in conjugate gradient methods. Because of this, why do we need to use a near exact line search if we are to expect rapid ...
0
votes
0answers
197 views

NAESAT (Not all equal sat) problem

Given the following NAESAT problem: c3 = {x1,x2}, {x2,x3},{x3,x1} where cn = {x1,x2}, {x2,x3}..{xi,xi+1} What is c4? Well ...
0
votes
1answer
68 views

Checking convergence of an iteration

How to check if an algorithm converges in an interval, for example $x_{k+1}:=\frac{1}{11}(1-\cos(x_k))$ does it converge for any startpoint $x_0\in (-\pi/2,\pi/2)\setminus\{0\}$ ? (as hint: ...
4
votes
1answer
108 views

A game problem- double or increment by 1

Its a two player game. Initially $P=1$, and there is some fixed integer $Q>1$. A valid move consists of either increasing $P$ by $1$ or doubling it iff on doing so $P$ does NOT exceed $Q$.The ...
1
vote
1answer
90 views

Repetitive Multiplication/Division

I have a number x = 10000 (for example), I want to divide it by a number y = 1.2 (for example) continuously until the result is equal or less than 1. for example: ...
0
votes
2answers
57 views

Is there a formula for finding the lowest common factor

Us there an formula/algorithm for finding the lowest/least common factor/denominator (other than one) of two numbers? Thanks!
0
votes
1answer
46 views

Is there a formula for finding the lowest factor of a number

Is there a simple formula/algorithm to find the lowest factor of a number other than one? Thanks!