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)

1
vote
1answer
74 views

Prove that $\exists$ a Boolean Assignment that satisfies at least $\Sigma_{3\leq i \leq 15}$ $ m_{i} \dfrac{2^{i}-1}{2^{i}}$ clauses

Suppose that we have a boolean formula which is conjunction of $\Sigma_{3\leq i \leq 15}$ $ m_{i} $ clauses. The clauses consists of $m_{3}$ disjunction of length 3, $ m_{4}$ disjunction of length ...
3
votes
1answer
134 views

Move the Bishop

Given an n × m chessboard, a bishop and two numbers a and b.Initially bishop is placed on the position (i, j) on the board.There can only be actions of the following types: ...
-1
votes
2answers
120 views

How do I guess an intital step length in a line search (minimization)?

I am currently trying to write a "simple" minimizer for a function $y = f(x)$ where $x$ is a multidimensional vector and $y$ is a real number where I have access to the derivate vector. If I have a ...
1
vote
0answers
69 views

Proof of the Surfer Model Pagerank formula

How do you prove this formula for the Surfer Pagerank algorithm mathematically? ...
1
vote
2answers
43 views

Best way to generalize a distribution of data into smaller subsets?

Suppose I had a data set as follows: 168.95, 176.83, 178.13, 179.61, 179.44, 172.83, 173.37, 174.06, 174.94, 175.43, 175.73, 175.5, 173.78, 174.06, 172.71, 174.3, 178.38, 178.43, 177.18, 175.34, ...
0
votes
1answer
56 views

Help with probability formula in programming problem

I am trying to solve this dynamic programming problem using probabilities. I know how the recurrence for it should look but I have problems using a probability formula. I have the next case: In a ...
0
votes
1answer
56 views

Data Points Within 4% of Best fit line algorithm

This question is actually based on a problem I am attempting to solve within a C program. I am attempting to understand how the mathmatical equation that would need to be writtne. I will have 10 ...
4
votes
1answer
81 views

Minimizing the distance between points in two sets

Given two sets $A, B\subset \mathbb{N}^2$, each with finite cardinality, what's the most efficient algorithm to compute $\min_{u\in A, v\in B}d(u, v)$ where $d(u,v)$ is the (Euclidean) distance ...
2
votes
2answers
75 views

Minimum number of elements needed from n sets

Suppose that we have n sets. They may or may not have common elements. How can we find the minimum number of elements that we should pick so that we have at least one element from each set? For ...
0
votes
1answer
105 views

The RSA Algorithm

My public key is $e=41$, $m=63680341$, and $y=62723227$. How do I decipher into plaintext the ciphertext $y$? The professor gave a hint and said that the plaintext is hello in a foreign language. My ...
0
votes
1answer
49 views

2D sub array problem

Given a N*N 2D array in which each element could be between 1 to 100 I need to find subarray with most number of 1's in it,subarray with maximum 2's in it..and so on till for the maximum element of ...
2
votes
3answers
169 views

How bad, really, is the bisection method?

We know that the bisection method for root finding is slow (linear convergence), but has the advantage of always working for a continuous function, if we start with a interval which brackets the root. ...
2
votes
2answers
158 views

Tiny Planet Algorithm?

So I've recently been looking at the Tiny Planet images. I've been googling a few things to try and find out how images are converted from normal to a tiny planet. Some phone apps, as well as ...
-1
votes
1answer
88 views

How to determine the prime numbers? [closed]

What is the best way to determine the prime numbers? Is there a way other than trial-and-error to determine them? Is the set of prime numbers finite or infinite?
1
vote
1answer
58 views

simple maths problem

N locations are numbered from 0 to N-1. Given a int[] containing N elements. The i-th (0-based index) element of array is the number of persons who live near location i.One car can move to one ...
0
votes
2answers
81 views

Algorithm for finding lowest average grade difference

Given a class with n boys and n girls, in which the girls recieved the grades P1,...,Pn, and the boys recieved the grades S1,...,Sn in an exam, find a pairing of girl-boy in a way that minimizes the ...
0
votes
1answer
31 views

Help Specify possible definitions for this Boolean Function

My math is rusty, but I need some guidance here. Problem I wish to design a stochastic, boolean procedure $f(state)$, that picks a winner, $f(state_{win})\to 1$ or loser, $f(state_{loss})\to 0$. I ...
0
votes
1answer
38 views

Calculating an exponentially increasing vector of points in a test and measure system

My application is setting and measuring current and voltage in a physical system with a software algorithm. Given these parameters: min, ...
1
vote
3answers
69 views

Newton's method for square root

Solving $x^2-a=0$ with Newton's method, you can derive the sequence $x_{n+1}=(x_n + a/x_n)/2$ by taking the first order approximation of the polynomial equation, and then use that as the update. I can ...
1
vote
1answer
54 views

Making longest sequence

F(N) is defined as number of digits in a number N. EXAMPLE : F(123)=3 I want to make a consecutive integer sequence starting from number m (m, m + 1, ...). But to add a number n to my sequence its ...
0
votes
3answers
48 views

Box into another box

There are n Boxes. Each box has a size. A box can be put into another box only if the size of box who hold the other box is at least twice as large as the size of box which is held. Each box can hold ...
0
votes
3answers
169 views

Minimum number of exchanges

Suppose we want to arrange n numbers stored in an array such that all negative value occur before the positive ones. What will be the minimum number of exchanges in the worst case ? I tried it in the ...
1
vote
1answer
101 views

Ranking System (ELO)

I want to create a ranking system for a sports game, where more that 2 "teams/players" participate in each match. This means NOT chess, or soccer, or boxing. It could be bowling or long jump etc. For ...
0
votes
1answer
78 views

Efficient polynomial evaluation using idea of fast fourier transform

Please would anyone suggest an efficient algorithm ($O(n \log n)$) to evaluate a polynomial at all the $n$th roots of unity, where $n$ is not a power of $2$?
4
votes
1answer
255 views

An algorithm for Gaussian integers

Question : Let $i^2=-1$. If a pair $(a+bi, c+di) (a,b,c,d\in\mathbb Z, a\not\equiv b, c\not\equiv d\ \text{(mod 2)})$ such that $a+bi$ and $c+di$ are relatively prime is given, then can we say that ...
0
votes
1answer
63 views

Question Understanding Simple Algebra With Regards to Computational Complexity

Initial Disclaimer: I decided not to post this on Stack Overflow as my problem lies with understanding the mathematics of this problem, but does not relate to theory at all. I am studying Parallel ...
0
votes
1answer
44 views

Algorithm to partition a graph under constraints

What would be an algorithm to partition the vertex set of an undirected graph into 2 vertex disjoint subsets such that each vertex has at most $\left\lfloor\frac{d}{2} \right\rfloor$ no of its ...
2
votes
1answer
89 views

Graph isomorphism and existence of nontrivial automorphisms

Consider the following two algorithmic problems - one of determining whether two graphs are isomorphic and the other of determining if a graph has a nontrivial automorphism: (1) Decision problem: ...
1
vote
0answers
20 views

algorithms, np, colorability

I have a question that states as follows: Give an argument that a graph is 3-colorable if and only if the input 3sat instance is satisfiable. I don't ...
2
votes
1answer
36 views

Is there an algorithm or method to tell if a fraction can be represented exactly in a particular base?

For instance, 1/3 cannot be represented exactly in base 10, but in many other bases it can. Is there an algorithm that will tell you, given x,y,z, where x and y form a ratio of integers (a fraction) ...
0
votes
0answers
26 views

Faster algorithm to test associativity of magma [duplicate]

Is there a faster algorithm to test associativity of a finite magma than just computing the two products of every triple of elements?
4
votes
2answers
699 views

Algorithm of cutting a polygon into equal parts

I have a convex polygon. I need to divide it into 4 equal parts using the two slit. For example, if I have a square, I have to cut it along the diagonals. Are there some common algorithm for this ...
2
votes
2answers
957 views

Counting Distinct Palindromic Substrings

Given a string $S$, I want to count the number of distinct palindromic substrings of $S$. I know the basic $o(n^2)$ approach to do so. But I want to find a better approach for strings that can be ...
2
votes
1answer
150 views

Computing square root faster than Newton’s method

Is Newton's method when it comes to, say, a 4000 bit number a serious consideration for computing the floor square root function?
1
vote
1answer
85 views

White Black Cube

Given a cube of dimension N*N*N made of unit cubic cell and color of each cell could be black or white.I want to find maximum size of subcube which has atleast K% of its cells as black. I want to ...
5
votes
1answer
185 views

Numbers permutation

Given $n$ numbers and $k$ positions I want the total number of permutations of these n numbers on these $k$ positions if repetition is allowed and if the following two arrangements are considered ...
0
votes
1answer
27 views

Compute the quantity of some numbers that satisfy some condition

Suppose we have a sequence whose length is n and its contents are all digits, such as $b_nb_{n-1}...b_1(b_i=0,1,2,...,9)$. And $bn$ would not be $0$. Given L, R and m, if $L\le ...
1
vote
0answers
38 views

Improved approximation algorithm for maximum weighted matching

I've read the discussion here: http://stackoverflow.com/questions/5203894/a-good-approximation-algorithm-for-the-maximum-weight-perfect-match-in-non-bipar, and I have implemented the Drake and ...
1
vote
0answers
148 views

Make the maximum sum in a interval.

Two players $A$ and $B$ are playing a game with array $A$ of $N$ elements in which each player chooses an array interval with maximum sum. The other simultaneously chooses another interval in the same ...
0
votes
1answer
17 views

Make two values equal

I have two integers x and y. If the value is divisible by two, then I can remove a half of the value. If the value is divisible by three, then I can remove exactly two-thirds, and if the value is ...
0
votes
0answers
150 views

Strassen's Matrix Multiplication Example Problem

How to multiply two matrices using strassen's matrix multiplication.I have only learned the theory part but i cannot find any examples on the net. Could some one explain with two 2X2 Matrices.
1
vote
1answer
175 views

K piles stone game

Their are k piles with total n stones in some order where each pile can have stones greater or equal to zero.Two player A and B plays a game in which player A cant see the configuration of piles but ...
-1
votes
2answers
137 views

The number of elements of a finite group which is a quotient of a finitely generated free abelian group

Let $G$ be a finitely generated free abelian group. Let $\omega_1,\cdots,\omega_n$ be its basis. Let $\alpha_1,\cdots,\alpha_m$ be a finite sequence of elements of $G$. Suppose $\alpha_i = \sum_j ...
1
vote
0answers
34 views

2D Matrix problem

Given a N*N matrix (1 indexed) which is initially zero. That is all its row and column are zero. Now I have to transform it to new matrix being entered in minimum number of moves where I can perform ...
0
votes
1answer
61 views

Maximum independent set for a graph with no cycles.

Maximum independent set for a undirected graph with no cycles can be solved in polynomial time?? if so analyse its complexity and give an algorithm. or prove that the above problem is NP-complete and ...
0
votes
1answer
75 views

How to solve a recurrence relation?

I want to solve the following recurrence relation with Guess method and induction: $T(1) = 1$ $T(n) = T(3n/4) + T(n/5 + 1) + n$ for $n > 1$
10
votes
1answer
258 views

How many Groups there are on a finite set?

Let say cardinality of set S is $n=|S|$. We know that there are $n^{n^2}$ all binary operations on that set. To find out how many groups can be created by this set and by those operations, we need not ...
0
votes
1answer
81 views

Greedy Algorithm that does not produce a linear Code.

In a section of study of LexiCode this problem comes . Any help and hint appreciated. Find an ordering of $\mathbf{F}_{2}^5$ so that the greedy algorithm does not produce a linear code [Edit: ...
1
vote
1answer
23 views

Rating based on 2 criterias

I'm trying to write rating system which scores items based on two criteria with different importance. Criteria_1 will have importance 0.2 and Criteria_2 will have 0.8. Maybe a bit of trickiness adds ...
1
vote
0answers
51 views

Finding code in 5-guesses only

Suppose you want to crack a code composed of 4 digits (each between 0 to 5 when repetitions allowed) and you get feedback like in mastermind, how can you find it in less than 5 guesses in an ...