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
2answers
33 views

Computing modular inverses for a sequence of numbers

I have a prime $p$ and an integer $L$ such that $p \gg L \gg 1$, and I need to compute modular inverses of numbers $1, 2, \ldots, L$ (modulo $p$). Obviously I could apply the extended gcd algorithm to ...
1
vote
1answer
193 views

Eliminating Epsilon Production for Left Recursion Elimination

Im following the algorithm for left recursion elimination from a grammar.It says remove the epsilon production if there is any I have the following grammer ...
1
vote
0answers
41 views

Algorithms: Recurrence

Here's a problem that I am struggling with... If two algorithms A and B both solve the same problem. On an input of size $n$ Algorithm $A$ breaks it into $5$ pieces of size $n/2$, recursively solves ...
1
vote
1answer
189 views

Proving by induction that a palindrome contains an even number of $b$s and $c$s

Suppose we want to construct palindromes that contain an $aa$ in the middle if the length is even and an $a$ in the middle if the length is odd. I'm trying to prove by induction that all of these ...
0
votes
1answer
97 views

A recursive definition of palidrome over {a,b}

Can someone please explain how this recursive definition produces palindromes over $\{a,b\}$? For example, how can we get the string $abaaaba$ as a valid string? Rule 1: $\epsilon$, $a$, and $b$ are ...
1
vote
0answers
15 views

Mapping elements to a boolean expression of similar elements

I'm trying to solve this problem that I suspect might be NP-hard; the basic idea is this: Given a list of elements $A$, determine if the elements in $A$ can be substituted into a boolean expression ...
1
vote
1answer
58 views

A Shifted Sorted Array - finding the shift

I was given a problem concerning a sorted array that is shifted by some "number of spaces", k. For example, take the sorted array $1, 2, 3, 4, 5 ,6$ It is shifted 2 spaces, we get: $5, 6, 1, 2, 3 ...
1
vote
0answers
95 views

How many subsets of NxM rectangle are tileable by dominos?

There are a lot of articles, formulas and algorithms for the number of domino tilings for some region, but I couldn't find anything about number of tileable regions. Is there any exact formula or at ...
0
votes
1answer
46 views

Can this algorithm be written as an equation?

Found an algorithm to compute the square root of a positive number A, using the following iteration: $$s_n=\frac{1}{2}(s_{n-1}+\frac{A}{s_{n-1}}),\ n=0,1, ...$$ and $s_{n-1}$ is an initial estimate of ...
3
votes
1answer
69 views

How to check if $n^2$ will square root evenly without square rooting $n^2$ [duplicate]

How can I easily check if the square root of a number is a whole number and not a decimal without computing the square rood of said number. I could square root the number (...
0
votes
2answers
60 views

Prove that so and so is $O(x^4)$

Given $f(x) = x^3 + 20x + 1$, how would I prove this is $O(x^4)$? By definition, the function is $O(x^4)$ iff $f(x) <= cn^4$, where $c$ is some constant. However, I'm not sure where to go from ...
1
vote
1answer
219 views

Largest white rectangle on board

Given a string rectangular board which is divided into unit cells. Each cell is initially painted black or white. The character board[i][j] represents the cell with coordinates (i, j). Each of those ...
0
votes
1answer
38 views

Calculate number of strings

Given a string S how many different strings can be formed by erasing a sigle letter from the given string? EXAMPLE : "ABA" Returns: 3 The following three Strings are possible in this case: "BA", ...
2
votes
0answers
56 views

Graph Connectivity

I am given an initial connected graph $G$ with $n$ nodes and $m$ edges. At each step I remove an edge from $G$ and ask if $G$ is connected. Can the queries be answered in $\mathcal{O}(\log n)$ time ...
1
vote
1answer
68 views

Getting some negative to positive interval from a positive random number generator?

Imagine I have a random generator. random(m, n) returns a random integer between 'm' and 'n' but both $m$ and $n$ needs to be positive integers. Is there any way I could get it to work if I was able ...
0
votes
2answers
78 views

Discrete math with SSNs

I am currently doing some discrete math and am completely stuck on two problems. They are both the same concept: An SSN is a Social Security number. How many SSNs have digits that sum to 2? How ...
1
vote
1answer
38 views

Correctness of complexity analysis of recursive algorithm

Given following recursive equation: $$T(n) = T(n-3) + \Theta(1)$$ Is it correct that this equation is O(1)?
2
votes
2answers
51 views

Comparison of almost planar graphs

I have multiple graphs all of which are almost planar. Is there any existing terminology / method which compares them, such that one can say which one is more planar? This could simply be the required ...
0
votes
2answers
311 views

Calculate the number of digits in a product of large numbers

I'm looking for a method that can calculate the number of digits in a product of several large numbers. For example, calculate the number of digits in the product 4*51*6001*70001*800001*9000001? I ...
1
vote
0answers
30 views

Polynomial regression - differences between algorithms

I know that I can find a polynomial regression's coefficients doing $(X'X)^{-1}X'y$ (where $X'$ is the transpose). This is a way of finding them; now, there is (as far as I know) at least one other ...
4
votes
0answers
106 views

Computational hard math problem

Given a square filled randomly with the numbers $1$ to $N$, for instance $$\begin{array}{cccc} 16 &12 & 9 & 1\\ 11 & 3 & 4 & 7\\ 2& 8 & 5&14\\ 6& 10& ...
2
votes
1answer
85 views

Algorithm to find maximum possible value of the minimum expression in a list

Problem Let $x_1, x_2, \ldots, x_m \in \mathbb{R}$, and suppose I have a bunch of expressions which are linear combinations of $1, x_1, x_2, \ldots, x_m$. For example, I might have \begin{align*} ...
3
votes
1answer
209 views

An alternate analysis to the (worst-case) run time of the euclidean algorithm

I was trying to figure out the running time of the euclidean algorithm. The analysis that I found on Wikipedia and CLRS both analyze the run time of the euclidean algorithm using the Fibonacci ...
8
votes
1answer
269 views

Stochastic gradient descent for convex optimization

What happens if a convex objective is optimized by stochastic gradient descent? Is a global solution achieved?
2
votes
1answer
69 views

What's the most efficient algorithm to determine the relative ordering of an unknown set of values?

This comes from a question on Arqade. The background is, there's a mall level. Vlad the organized crime boss wants $50,000 worth of mall property destroyed. Your task is to shoot and blow ...
5
votes
3answers
86 views

Name of the generalization of quadtree and octree?

What is the name of the equivalent of quadtrees and octrees in n-dimension ?
2
votes
1answer
125 views

Play with pairs of numbers

Two players are playing a game. The game is played on a sequence of positive integer pairs. The players make their moves alternatively. During his move the player chooses a pair and decreases the ...
1
vote
1answer
67 views

Game of chocolates

Two players A and B play a game alternatively and A starts the game. Their are 2 boxes of chocolates and we are Given the number of chocolates in both the boxes, let them be c1 and c2, the player ...
0
votes
1answer
85 views

How to tell if there exists a vector orthogonal to half your vectors

Given a set of $N$ vectors each with $n$ entries from the integers. How can you determine efficiently if there is any non-zero vector in $\mathbb{R}^n$ which is orthogonal to half of them?
1
vote
1answer
50 views

Most efficient way to solve this combination problem

I have 4 very large list (l1, l2, l3, l4) of components (approx 9 million items in each list). Each list item has a cost and a value. I want to know how I can achieve the maximum combined value for ...
1
vote
1answer
33 views

Trying to determine a number that when multiplied equals a static total

EDIT ---> Values I have been using currently to determine figures. Simple values test. This example is to assume each user gives 20/mo * 12. Then this amount is slowly given back to them over the ...
1
vote
0answers
36 views

A set is partitioned into $k$ non-empty sets, and the difference between elements of each subset is given, reconstruct each subset

We have a set $A = \{1, 2, 3, \dots, n\}$. This set is partitioned into $k$ non-empty subsets: $$A_1 = \{a_1, a_2, \dots, a_{m_1}\}$$ $$A_2 = \{a_{m_1 + 1}, a_{{m_1} + 2}, \dots, a_{m_2}\}$$ $$.$$ ...
0
votes
2answers
38 views

Room for computational geometry in advanced algorithms course

I am currently putting together an independent study in advanced algorithms and because of my interest in (computational) geometry, wanted to include as many interesting algorithms from this field as ...
2
votes
0answers
56 views

String diversity

String diversity is the number of symbols that occur in the string at least once. Diversity of s will be denoted by d(s). For example , d("aaa")=1, d("abacaba")=3. Given a string s, consisting of ...
1
vote
0answers
24 views

Algorithm to evaluate predictions

I am looking for an algorithm* to solve the following problem Scenario I'm observing a sequence of things. Every thing has some arbitrary visible properties and a hidden probability $p$ to turn out ...
1
vote
2answers
48 views

Unique combination of sets

We start with a finite number of $N$ sets, $\boldsymbol{X}_1,\ldots,\boldsymbol{X}_N$, each containing a finite number of integers. The sets do not in general have the same number of elements. The ...
2
votes
2answers
62 views

Condition for $N! > A^N$

I am given $A$ , I need to find minimum value of $N$ such that the condition $N! > A^N$ holds. EXAMPLE : If $A=2$ then minimum $N=4$ and similarly if $A=3$ then minimum $N=7$. How to solve this ...
0
votes
1answer
109 views

Submatrix with sum K

Given an N*M matrix of only 0's and 1's I need to find a submatrix in this 2d array whose area is minimum and which contain exactly K 1's or we can say whose sum is K.If their is no such matrix ...
0
votes
1answer
110 views

How to calculate total number of combination having sum divisible by a given number.

I have following code.And i want to calculate value of ans. ...
0
votes
1answer
148 views

Playing around with ${\int\frac{dx}{x^2-2x}}$

Found the above integral in the old posts and figured I would play around with it using double substitution and integration of partial derivatives. So here goes. $$\int \frac {dx}{x^2-2x}$$ $$= ...
-2
votes
1answer
81 views

How to change RSA Algorithm to be able to calculate D based on E or reverse?

I need an algorithm like RSA (http://en.wikipedia.org/wiki/RSA_(algorithm)) with an infrastructural different. RSA is a works very nice, it uses Euler's Phi function to calculate 2 values that are ...
0
votes
1answer
111 views

ElGamal Public Key Cryptosystem and Digital Signature Scheme

I'm tryting to understand how ElGamal algorithm works, and I got the following example, and I couldn't understand one part of this: A) P=23, g=5. B) x=3, then y=10 (for 53 mod 23=10 ). C) Sign for ...
0
votes
1answer
95 views

Karnaugh map minimum sum of products

I'm trying to give the minimum sum of products using Karnaugh Map of this expression: ...
1
vote
1answer
75 views

Probabilistic time algorithm for finding the solution for quadratic congruences (case when p is prime)

I was trying to solve the following equation: $$y = x^2 \bmod p$$ where $p$ is prime. I was trying to find an algorithm that solved this and that was in BPP (I don't think there is one in P). I ...
2
votes
0answers
108 views

Using an elliptic curve to create pseudo random number

I recently started learning about encryption. I read about how elliptic curves can be used to create pseudo random numbers (and how the nsa might have abused this fact to create a backdoor in ...
1
vote
1answer
93 views

Prove the correctness of the following greedy algorithm for finding a minimal spanning tree.

I have to prove that the following algorithm finds the minimal spanning tree. Let $G$ be the graph were doing the procedure on, and all edges have different weights. Step 1: Sort the edges in ...
1
vote
2answers
79 views

Moving the Robot

A robot is located on an infinite plane. At the beginning, the robot starts at the coordinates $(0, 0)$. The robot can then make several steps. The steps are numbered starting from $0$. In each ...
2
votes
1answer
51 views

Check if strings are intersting

Two strings S and T are said to be interseting if there are two non-empty strings A and B such that S = A+B and T = B+A.How to find if two strings are intersting or not? EXAMPLE : if S="tokyo" and ...
1
vote
0answers
114 views

Number of classes of K-sets

I am having a plane in N dimension. Th distance between 2 points (a1,a2,...,aN) and (b1,b2,...,bN) is max{|a1-b1|, |a2-b2|, ..., |aN-bN|}. I need to to know how many K-sets exist(here K-set refers to ...
2
votes
2answers
386 views

Flood algorithm - find polygon containing a given point.

I have some code that represents a set of a set of interconnected line segments in 2D, in pseudo-code it'd be like this: ...