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

learn more… | top users | synonyms (1)

5
votes
0answers
22 views

Algorithm to find primes up to $n$ in $O\left(\frac{n}{\log n}\right)$?

Consider the problem of given an integer $n$, generating a list of the primes not greater than $n$. An optimized version of the Sieve of Eratosthenes can do such task in $O(n)$, while the more modern ...
6
votes
0answers
19 views

Embedding as a subgroup

Suppose I am given two finite groups $G$ and $H$ (not too large: let's say their orders are around $10000$ and $100$ respectively, and the order of $H$ divides the order of $G$). These may be ...
0
votes
0answers
14 views

a Greedy Algorithm problem

The question says that there are some activities are scheduled. We need arrange the rooms for those meetings. The requirement is that we need to use as few rooms as possible and we cannot change the ...
0
votes
0answers
4 views

reduction to Hessenberg

I have a homework question stating that: Suppose $A \in R^{n \times n}$ and $z \in R^{n}$. Give an algorithm for computing an orthogonal $Q$ such that $Q^{T}AQ$ is upper Hessenberg and $Q^{T}z$ is a ...
0
votes
0answers
15 views

How to apply a division algorithm

I need to apply a division algorithm to this equation and with this result apply partial fractions (I already know it) the problem is that I don't know how to do the division algorithm $$y= ...
0
votes
0answers
15 views

Seemingly-random algorithm for generating fictional static objects on a real-world map?

I'm a software engineer building a mobile game which uses geo-location and a real-world map. As the user moves around in the real world, the map display moves around following them, and displays ...
1
vote
0answers
48 views

Let A[1..n] be an array of numbers. [on hold]

Let A[1..n] be an array of numbers. To find the largest number in A, one way is to divide A into two halves, recursively find the largest number in each half, and pick the maximum between the two. ...
2
votes
1answer
39 views

Concrete FFT polynomial multiplication example

I have read a number of explanations of the steps involved in multiplying two polynomials using fast fourier transform and am not quite getting it in practice. I was wondering if I could get some help ...
0
votes
1answer
29 views

Finding the 'n'th k-permutation of a set, and finding 'n' for a given k-permutation (lexicographical ordering)

Suppose you have a set, and want to order the k-permutations of the set (for example, the permutations of 5 elements of the set {1, 2, 3, ..., 16}). Is there a fast way of finding 'n' (the ...
0
votes
1answer
19 views

Understanding Recursive algorithm using FIB

I am studying for an exam, and I came across this question, I think I got the answer correct, just need some validation. ...
1
vote
1answer
76 views

Why does Euclid's algorithm taken one step past the GCD seem to yield the LCM?

In class we are going over Euclid's Algorithm. For example, we learned that for integers $m$, $n$:$$\gcd(m,n) = sm + tn$$ Where $s$ and $t$ are integers that can be plugged in to satisfy the ...
0
votes
1answer
11 views

Find close-enough points in 3d space

I have 2 sets of points in 3d space , each set of size n. I need to calc. all the points from the first set the are close enough (dist between 2 points < TH, TH is given) to at least one of the ...
1
vote
1answer
23 views

Algorithm for determining what order to perform a set of tasks in

Consider a set of $n$ items. Each item has a date $d$ by which it must be completed. Each item also has a priority level of $p$ and takes a time $t$ to complete. Is there an algorithm for determining ...
1
vote
1answer
31 views

Relation of encryption to P, NP, and NP-Complete

After watching a Harvard Lecture regarding the understanding of P, NP, and NP-Complete,they also talk about our encryption algorithms being cracked or useless once we solve the mathematics side of it? ...
7
votes
6answers
561 views

Non-literal applications of “Shortest Path” algorithm?

It's obvious that it's used in stuff like Google Maps, but what are some more metaphorical applications where you're minimizing the path between nodes (which can represent anything)
0
votes
1answer
24 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
11 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, ...
0
votes
0answers
21 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
11 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
68 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.: ...
2
votes
2answers
38 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
21 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
38 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
53 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? [closed]

Could Some one help me finding algorithm for solution of nonlinear system of equation with newtonmethod in mathematica ?
0
votes
1answer
52 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
350 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
28 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
16 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
45 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
55 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
15 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
49 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
59 views

Proof by Induction Algorithm [closed]

I am stuck on trying to prove this algorithm using mathematical induction. ...
-2
votes
0answers
58 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 ...
0
votes
1answer
64 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
36 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 ...