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

learn more… | top users | synonyms (1)

0
votes
0answers
3 views

Definition of Pa(y) in Bayes Enumeration Function

I'm current taking a class in AI. We're being tasked with implementing the Bayes Enumeration function described on slide five of this PDF. Here is just the function: ...
0
votes
0answers
9 views

question about division algorithm described in handbook of applied crypto

http://cacr.uwaterloo.ca/hac/about/chap14.pdf#page=9 gives the following as a division algorithm: So step 1 is making it so that $yb^{n-t}$ is the same length as x and then step 2 loops until the ...
1
vote
1answer
9 views

Defining a region as a data structure

Is there a way for one to define a curve or region (such as a closed, 2-d disk) as a data structure into the computer, and make an algorithm which detects if a point is a boundary point, limit points, ...
1
vote
0answers
10 views

Maximizing variance of Hamming distance of a system

I have a system as shown below, where 4 registers have 8 bit input A,B,C,...
1
vote
1answer
8 views

Algorithm: Integer vectors with equal inproduct with a constant vector

Given vector $\vec{a} \in \mathbb{Z}^{n}$ and constants $D, e \in \mathbb{Z}$, I need to find all vectors $\vec{x}\in \mathbb{Z}^{n}$ such that $e \geq x_{i} \geq -e$ and $\vec{x} \cdot \vec{a} = D$ ...
1
vote
3answers
62 views

Product of “reversed” numbers

Consider any 2 binary numbers, e.g.: 10101011 ; 11111101 and their product, say P. "Reverse" (mirror image) all the digits of the 2 numbers, e.g.: ...
1
vote
1answer
15 views

Algorithm to compute maximum permutation sum in matrix

Given a matrix $A_{n\times n}$ of real numbers, what fast algorithms do there exist to compute the maximum value of $a_{1,\sigma(1)}+a_{2,\sigma(2)}+\ldots+a_{n,\sigma(n)}$ over all permutations ...
0
votes
1answer
17 views

Max flow min cut algorithm

I am trying to work this max-flow, min-cut out for my finals, but Im really not sure I have got it, I would appreciate some assistance! I understand the theorm, I comes from ford-fulkerson, where the ...
2
votes
1answer
37 views

How to know if the mth root of n is an integer?

If n can be represented in binary as a x bit integer, is there any algorithm such that we can determine if the mth root of n is an integer in time polynomial of x ?
1
vote
2answers
50 views

I want to know an estimate of $a_{i, j}$

Let $$ a_{ij} = \begin{cases} -1, & \text{if $i = -1$ and $j = -1$} \\ 1, & \text{if $i = -1$ and $j \ne -1$} \\ 1, & \text{if $i \ne -1$ and $j = -1$} \\ a_{i-1, j-1} + ...
-4
votes
0answers
23 views

How to Solve nonlinear system by newton method? [on hold]

Could Some one help me finding algorithm for solution of nonlinear system of equation with newtonmethod in mathematica ?
0
votes
1answer
51 views

Do there exist polynomials not computable in polynomial time?

Motivation: Computing a problem in $k$ memory slots Do there exist polynomials in $R = \Bbb{Z}_p[z_1, \dots, z_k]$ that can't be computed in time polynomial in $k,p$? Thanks... Good luck! Edit. I ...
9
votes
4answers
344 views

Application of computers in higher mathematics

Currently the main application of computers in mathematics seems to be to compute things, i.e. to solve equations, evaluate integrals, etc. It is at all possible to delegate the thinking of a ...
0
votes
1answer
22 views

Any problem computable in $k$ memory slots can be computed with polynomials.

Let our memory slots be represented by elements of $\Bbb{Z}_p$ for a prime $p$. $k$ memory slots would be $k$ copies of the ring: $R = (\Bbb{Z}_p)^k$. Suppose that for a problem $f : X \to Y$, ...
0
votes
1answer
26 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 := ...
0
votes
0answers
25 views

A prime connection between two numbers with same prefix

If I know that the number n is prime, is there a fast algorithm to check if 10*n+k is prime, where k is 1, 3, 7 or 9? I mean, an algorithm based on the fact that n is prime. Thanks for help! P.S. : ...
0
votes
0answers
11 views

Are these computational models equivalent?

Let $f : X \to Y$ be a problem that you want to compute. Say we have an $O(1)$-computable maps, $\phi, \psi$, such that $X \xrightarrow{\phi} (\Bbb{Z}_n)^k \xrightarrow{\psi} Y$. After all, ...
1
vote
0answers
15 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 ...
2
votes
3answers
40 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
41 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 ...
0
votes
2answers
55 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
0answers
6 views

Determining the minimal number of axis to test against in the SAT (Separating Axis Theorem)

Most implementations of the SAT algorithm I've seen involve testing each axis in either shape being tested against for collisions. But I recently implemented the SAT algorithm in python and noticed ...
0
votes
2answers
47 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
54 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
0answers
14 views

Projection of a polygon onto a line?

Recently I have started doing some research on the SAT (Separating Axis Theorem) for collision detection in a program I am making. I understand how the algorithm works and why it works, what I'm ...
0
votes
1answer
46 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 ...
0
votes
0answers
28 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
58 views

Proof by Induction Algorithm [closed]

I am stuck on trying to prove this algorithm using mathematical induction. ...
-2
votes
0answers
55 views

Multiplying the candies game

How to solve this game . At start am given with 0 candies and I gain candies at a rate of 2 candies per second. Any time if I have at least C candies, I can buy a bigger candy. Every time I buy a ...
1
vote
0answers
27 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 ...
-3
votes
0answers
38 views

What is the use of matlab? [closed]

What is matlab? Why do engineers use that? Whats it do? Can someone please explain how this is helping people to make life better?
0
votes
1answer
62 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
39 views

Number of solutions for inqeuality

Is there a way we can determine number of solutions for equation $$x*y < d$$ where d is constant and x & y are positive integers greater than 1. I am not interested in actual values, but ...
0
votes
1answer
28 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 : ...
0
votes
0answers
16 views

Amortized Analysis Problem

I need to find the cost of the problem below but I cannot find a pattern to find the total cost. Problem: The cost of multiplication of n-bit binary number by 2. If a bit changes the cost of that ...
2
votes
0answers
35 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
43 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
19 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$? ...
0
votes
0answers
42 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
16 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 ...
0
votes
0answers
42 views

How can nested for-loops be expressed in mathematical notation?

Apologies if this is an obvious question; I'm not very familiar with mathematical notation for algorithms. I was coding a solution for Project Euler #4, and I came up with an interesting way of ...
0
votes
0answers
19 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
0answers
47 views

Max-Flow Algorithm construction

I am trying to solve an algorithm that requires a reduction to max-flow by constructing the appropriate flow-network and finding the max-flow, but I am having trouble making the jump to the ...
0
votes
1answer
82 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
27 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
36 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
84 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
0answers
25 views

Euclidean algorithm to find GCD

I have to find GCD(975, 442) using Euclidean algorithm and write it in like: $ax + by$. Please tell me what do i do wrong. ...
0
votes
3answers
26 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
25 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 ...