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
34 views

All my notes together on $\Bbb{Z}_p$-theoretic comp. complexity theory.

Def 1. A $\Bbb{Z_p}^k$-machine is a theoretical computer with $k$ data memory slots and $p$ is a prime number. All the operations on the machine are done one at a time in the ring $\Bbb{Z}_p$. No ...
0
votes
1answer
43 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 ...
8
votes
4answers
266 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
19 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
19 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
21 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
9 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
14 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
33 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
37 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
49 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
43 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
48 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
12 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
0answers
36 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
27 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
56 views

Proof by Induction Algorithm [on hold]

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
37 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
59 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
27 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
14 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
34 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
39 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
15 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
40 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
46 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
80 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
0answers
21 views

top surface in a set of 3D points [closed]

I have a set of 3D points with coordinates. I want to find all the points with maximum $z$ coordinates, example: if the set of points defining a cube, how I can find the coordinates in the top ...
0
votes
2answers
26 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
25 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
24 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
20 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. ...
0
votes
0answers
31 views

How to solve Flowchart logical reasoning questions?

I came across these crazy flow chart questions : You are given a table with 13 values, followed by a series of steps (say 8), some steps have yes or no branches as conditions, some just say go to ...
2
votes
2answers
150 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
23 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
68 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
22 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
20 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
60 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 ...