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)

4
votes
2answers
126 views

How to compute the closure of a set of binary strings in term of the “AND” and “OR” operators?

Given a set of $n$ binary strings of length $m$, how many binary strings at least should we add to the set to make sure that the binary "AND" and "OR" operators are closed on the set? The output of ...
4
votes
3answers
355 views

Is there an algorithm to find the roots of high-order polynomials?

It is not generally possible to determine the roots of a polynomial whose grade is bigger than 4 in terms of roots and basic operations. But I heard, that it is possible to give a criteria whether a ...
1
vote
0answers
141 views

randomized algorithm with probability of 3/4

I will be happy for a clue. I need to find a randomized algorithm with probability of $3/4$ and no more of $O(\log(n))$ bit's that send from A to B. A and B holding strings $as=(a_0,....a_{n-1})$ ...
2
votes
3answers
120 views

Formal proof for detection of intersections for constrained segments

They told me it was off-topic at stackoverflow. So I am trying my luck here. Yes, it's a homework, but I'm looking for some guidance (or related literature) instead of complete solutions. Please see ...
3
votes
0answers
50 views

Formal proof for detection of intersections for constrained segments [duplicate]

Possible Duplicate: Formal proof for detection of intersections for constrained segments Hi I need to come up with a formal proof for the following statement: Given an arbitrary count of ...
3
votes
1answer
922 views

Determine if function is little-o, little-omega or big-theta

Let $f(n) = n^3(5+2\cos(2n))$ and $g(n) = 3n^2+4n^3+5n$. Given these two functions, I must determine the appropriate symbol where the underscore is: $f(n) \in \_(g(n))$ So, first thing to do is take ...
2
votes
2answers
144 views

Calculations with liars and sums of prime factors

Suppose you are given a number $n$ and told that the sum of its prime factors is $s$. I'm looking for an efficient algorithm that checks the truth of the statement. Obviously one can simply ...
3
votes
1answer
165 views

Miller primality test bound

Good morning! I'm on my way to implement a deterministic (though unproven due to GRH) Miller primality test. On Wikipedia, it is said that it suffices to test all numbers in $[2, ...
1
vote
0answers
89 views

How to interpolate sequential points to obtain functions and/or vectors?

I would like to know how I can interpolate a sequence (time) of points in order to obtain curves as some kind of mathematical functions. Unfortunately math is not my area so I don't really know the ...
0
votes
1answer
88 views

Getting 5 or 7 and returning the opposite? [closed]

I get 5 or 7 and if i get 5 i need to return 7 if i get 7 i need to return 5. i need to do this in 1 mathematical formula. I have those: 12 - x 35 / x There ...
0
votes
1answer
96 views

computable function

Let $f$ be the function that maps the godel number of each proposition P in PA to 0 if P is provable false and 1 if P is provable true and 2 if P is independent of PA. Then $f$ is not computable. Is ...
3
votes
1answer
407 views

pickup and delivery driver problem

Let's assume food delivery for multiple restaurants (say 20). There are (say 10) drivers available. Further, let's say we get 100 orders over a 4 hour period to deliver food from these restaurants to ...
1
vote
1answer
174 views

Weighted Interval Scheduling

I am software programmer looking for Useful Algorithms And Mathematical Explanations & Theorems for Weighted Interval Scheduling Problem. Please Provide Me Some Useful Information on this. ...
6
votes
2answers
5k views

Extended Euclidean algorithm with negative numbers

I feel very sorry for asking probably simple and stupid questions on such a site, but a reasonable justification may be that smart answers to stupid questions will vaporize stupidity in the end and ...
2
votes
2answers
907 views

Omitting bases in Logs -> Big O

Can anyone explain, with the aid of a mathematical proof, why bases are omitted in Big - O notation? EDIT: I don't understand how: NB: $\log_2(n) =$ log to the base 2 of n $log_2(n) = ...
4
votes
3answers
121 views

Congruence of terms

There is concept of Term Rewriting. If one have rules for rewriting terms, one can obtain some term from another. For example, rule1: a -> f(b); rule2: b->t. Term A(f(t)) can be obtained from term ...
0
votes
1answer
355 views

Big O Rule Proof

Give a mathematical definition of the order notation $f(n) \in \mathcal O(g(n))$ and explain how this concept relates to the algorithmic idea of worst case analvsis. How do I go about answering ...
1
vote
1answer
160 views

Distribution of a random variable related to insertion sort

I am given a uniformly chosen permutation of the set $\{1,\ldots,n\}$ as an array $A[1,\ldots,n]$. For an integer $1 \leq j \leq n$ I am studing the distribution of the variable $X$ counting the ...
2
votes
1answer
258 views

Generating all words in a language from CFG

I have a non-ambiguous context-free grammar. Is there some standard algorithm to create list of all the words in the language the CFG defines? This can be done with an abvious brute-force search by ...
3
votes
1answer
1k views

Algorithm for joining two polygons based on set of 2D points

[Thanks for votes, I fixed the images now] I am working on system, that does some fuzzy logic. I don't have any special types, everything is done with simple math. The last problem I am facing is ...
42
votes
2answers
2k views

How do the Catalan numbers turn up here?

The Catalan numbers have a reputation for turning up everywhere, but the occurrence described below, in the analysis of an (incorrect) algorithm, is still mysterious to me, and I'm curious to find an ...
1
vote
1answer
284 views

How do I restore implied on-curve points in TTF Fonts?

I'm trying to find the coordinates of the implied point p2 using the control points p1 and p3. See here: In the TTF spec they say: Connected quadratic curves have first degree continuity and ...
3
votes
1answer
149 views

Uniform PRNG for long integer structures

Good morning! I don't actually know where to attribute this question (maybe it's better to publish it on StackOverflow), but it's more related to math theory than to actual realization. Since the ...
1
vote
0answers
69 views

Heuristic for adding items to a sorted list when exact comparison is unknown

a sorting question! Background: I've got a list of ~500 scrum tasks with a coarse priority (very high, high, medum, low, very low) and of course unique ids. Using those, I can define an ordering ...
2
votes
2answers
273 views

How to solve this basic math problem?

I'm having this problem on some game I'm coding which I think it's just math and has nothing to do with coding, that's why I'm posting it here and I'm going to simplify the problem without describing ...
1
vote
3answers
208 views

How to know which number is larger

We are given some expression, or formula, that outputs a number or expression for a number, we know that this number's decimal expansion is equal to that of Pi for the first 10^10^10^10^10 digits, ...
5
votes
3answers
2k views

What is the most efficient algorithm to find the closest prime less than a given number $n$

Problem Given a number n, $2 \leq n \leq 2^{63}$. $n$ could be prime itself. Find the a prime $p$ that is closet to $n$. Using the fact that for all prime $p$, $p > 2$, $p$ is odd and $p$ is of ...
0
votes
1answer
125 views

There is a table of the complexity of recursive algoritms?

I have a exam tomorrow and the teacher allow us to consult anthing that we want. So i thinking if exist any "table" that show the theta and big-oh for some common recursive formulas.
0
votes
0answers
162 views

Terminology, mapping a tree to a tree

I have stumbled upon a problem; unfortunately, I do not know the proper terminology to be used which hinders me in thinking about the problem and explaining the problem. I am not even sure this is the ...
0
votes
1answer
112 views

How to partition a list in smaller lists so that the odds of one element encountering another element is evenly distributed?

I'm struggling with an algorithm to divide a group of contestants into smaller groups to make up rounds. Take for example a group of 20 people, which I want to divide into 3 groups (7,7,6). For each ...
3
votes
3answers
2k views

Tips for constructing basic loop invariants?

One of the topics that I've struggled to grasp the most in my basic computer theory course is that of making a loop invariant to prove correctness of an algorithm. Even with what should be fairly ...
2
votes
1answer
2k views

Calculate the root of a number without useing the root function or decimal numbers

I'm trying to build a program in c# which will calculate prime numbers for me. I'm using the BigInteger class to work with 'endless' numbers. However, there is a big down side on this function, I ...
0
votes
2answers
590 views

Problems with euclidean GCD

\begin{align} 1414 &= 888 \cdot1 + 526 \qquad(1)\\ 888 &= 526 \cdot2 + 362 \qquad(2)\\ 526 &= 362 \cdot1 + 164 \qquad(3)\\ 362 &= 164 \cdot2 + 34 \,\,\,\qquad(4)\\ 164 &= 34 ...
1
vote
2answers
553 views

Euclidean algorithm to find the GCD

I have to find the greatest common divisor of $a=78$ and $b=132$. I have worked out to $$\begin{align} 132 & = 78 \times 1 + 54 \\ 78 & = 54 \times 1 + 24 \\ 54 & = 24 \times 2 + 6 \\ ...
0
votes
3answers
97 views

how prove $\binom{n}{n/2} = \Omega (\frac{2^{n}}{n})$?

how can prove $\binom{n}{n/2} = \Omega (\frac{2^{n}}{n})$ ? it s for algorithms coures . sorry for bad english :D
7
votes
2answers
554 views

Buckets of Balls, Will one fill if I add another Ball?

I was refereed here by stackoverflow.com. With some searching I found this: another balls and bins question, but its not quite what I am looking for. Rather the inverse. IE the expected number of ...
6
votes
1answer
1k views

Algorithm for computing square root of a perfect square integer?

My question is the following: Is there a polytime non-numerical algorithm for computing square root of perfect square integers? The more elementary the algorithm is, the better! EDIT: ...
6
votes
2answers
666 views

Expected travel time for regularly departing trains

I'm going to ask a very simple practical question, but I believe it has some interesting mathematical properties. The simple variant is: trains depart every $x$ minutes and take $y$ minutes to arrive ...
1
vote
3answers
368 views

Big Oh Question

I have the following question: Is the following statement true or false? ** All logs to base 2 log2n is a memeber of O(log(n)) My attempt: log2n - clogn <= 0 log2 + logn - clogn <= 0 1 + ...
2
votes
2answers
394 views

Second Order Homogeneous Recurrence Relation Question

I am revising for an exam in a few weeks and I have the following recurrence relation: f(1) = 1 f(2) = 2 f(n) = 5f(n/2) - 4f(n/4), n > 2 My lecture notes are ...
0
votes
1answer
169 views

Find whether n closed curves intersect

I have a number of closed curves (contours) which I want split into groups of mutually intersecting curves. The contours are made of straight lines and bezier curves. How could I do that? Thanks!
3
votes
0answers
163 views

Algorithm/Formula to compute adding and/or removing compound and/or non-compound percentages from a value?

I will first start with a scenario, I have to apply some adjustments to a particular value. These adjustments are either compound or non-compounded and they can either be added or subtracted to the ...
3
votes
1answer
215 views

Algorithmic Complexity of Iterated Sums

Suppose I have the following double summation \begin{align} F(n) = \sum_{i = a}^{\lfloor f(a, n) \rfloor } \ \sum_{j = b}^{\lfloor g(a, b, i, n) \rfloor } 1 \qquad a,b,n \in \mathbb{N}, \end{align} ...
0
votes
1answer
234 views

runge kutta 4 question

I have a quick question that I'm having a little trouble with, it seems simple enough but i just need a bit of clarification. If I had a system of ode's and I was to choose the runge kutta 4 method ...
2
votes
0answers
64 views

Iterative Compounded Growth Calculation

Hello I would like to develop a quick algorithm for computing compounded change over an arbitrary period $T$. I'll illustrate with an example. Suppose I have $N$ data points as follows: $$(x_0, t_0, ...
1
vote
1answer
76 views

Any concise way to represent this in a formula?

I'm doing a presentation and I have to include this in it: for j in 1..j_max b_offset = copy(b) b_offset[j] = b_offset[j] + 1 I can't do b_offset = b + ...
2
votes
0answers
95 views

What's the fastest way to solve these equations with powers in a field?

This is for an algorithm I'm working on. Perhaps we can work together! We can consider the integers modulo a prime $p$. They form a field with arithmetic operations modulo $p$. I'd like to find ...
6
votes
1answer
275 views

Algorithmic Analysis Simplified under Big O

Hi I am revising for my exams and I have the following inhomogeneous first order recurrence relation defined as follows: f(0) = 2 f(n) = 6f(n-1) - 5, n > 0 I ...
3
votes
1answer
1k views

One algorithm for drawing graph of implicit function

All! Does anybody know who is author of algorithm described here and is the proposed solution correct?
1
vote
2answers
637 views

Does $Ax + By = C$ pass through any lattice point?

Given an equation of a straight line of form $Ax + By = C$. where $A,B,C$ are integers. How could we check if this passes through any lattice point or not? Please suggest me a suitable algorithm.