Mathematical questions about Algorithms, including the analysis of algorithms, combinatorial algorithms, proofs of correctness, invariants, and semantic analyses. See also (computational-mathematics) and (computational-complexity).

learn more… | top users | synonyms (1)

1
vote
1answer
85 views

List number of moves to defeat the opponent

Given the position of chess board of two players, we have to find the minimum number of moves (and output them) so that only one player playing continuously and optimally defeat the other one ...
0
votes
1answer
2k views

How to solve the recurrence $T(n)=3T(n/2)+n$

The exercise stated that i have to solve the recurrence using the Recursion-Tree Method. I have already finished the base part, which is $\Theta(n^{\lg3})$ But for the recursive part I'm having ...
2
votes
2answers
433 views

Graph Run Time, Nodes and edges.

Hi i have these two problems that are part of a practice set i am doing for exams, i can't seem to get around them. If you can answer any of them thanks in advance. For a given graph $G=(V,E)$ and ...
1
vote
1answer
196 views

Continuous function $f(n)$ and $g(n)$ with different upper and lower bounds

Give examples of two continuous functions $f(n)$ and $g(n)$ of positive real inputs $n$, such that $f(n)$ not equal to $O(g(n))$, $g(n)$ not equal to $O(f(n))$, $f(n)$ not equal to $Omega(g(n))$ ...
1
vote
1answer
153 views

What are matroids and in what cases are they useful?

I came across the concept of matroids while studying up on the concept of greedy algorithms specifically The minimum spanning tree problem . I got this definition ...
4
votes
2answers
93 views

Squared linear sum

Is there any effective algorithm for a squared linear sum assignment problem? For squared linear sum assignment problem I mean the following: $$\min\left(\sum_i \sum_j c_{ij}x_{ij}\right)^2$$ with ...
2
votes
0answers
42 views

Proving a bound inequality for all n [duplicate]

Possible Duplicate: Prove that $\frac{n^n}{3^n} < n! < \frac{n^n}{2^n} $ for each $ n \geq 6 $ I want to prove $\dfrac{n^n}{3^n} \lt n! \lt \dfrac{n^n}{2^n}$ for all $n$ $\geq$ 6: So ...
2
votes
0answers
74 views

Algorithms for the Antikythera Mechanism

I am working on a little computer program, and i was wondering if any one knew of any collections of all the calculations done and their associated mathematical algorithms? The algorithms dont have ...
1
vote
1answer
568 views

Complex Numbers in Fractal Algorithms

I am a high school freshman who is undertaking a small development project on fractals. I do not want to get too in depth, but I would love to blow my math teacher's socks off. Having looked through ...
0
votes
1answer
332 views

Divide N items into M groups with as near equal size as possible

Im trying to split (say) N pink, fluffy balls into M groups as evenly as possible. Eg: ...
3
votes
2answers
286 views

Absolute difference between incoming and outgoing edges.

I am trying to prove that an algorithm can be devised to guarantee that absolute value of the difference between the sum of incoming edges and outgoing edges for each vertex is less than or equal to ...
2
votes
1answer
130 views

A peculiar algorithm

You are given an initial integer and a target integer. You may change the initial number by doing any of the operations $+2, -2, \times 2, \div 2$, any number of times in any order, to get the target ...
1
vote
1answer
121 views

How to compare time complexities involving an exponential and a polynomial?

A sequence of events $A_n, n \in \mathbb{N}$ is said to have a high probability, if $\mathrm{P} (A_n^c) \leq \frac{c}{n^d}$ for some $c, d >0$. Chernoff bounds are often used to prove some (upper ...
1
vote
0answers
89 views

Finding the minimum length of an addition chain

It is known that for every positive integer $n$ there exists one or more optimal addition chains of minimum length. It is rumored that finding the length of the optimal chain is NP-hard, and the ...
2
votes
1answer
102 views

Conditional merge of a sequence of DAGs / partial orders

I have a sequence of directed acyclic graphs, $G_i$. The union of their edge sets may not be a DAG. I want to find an edge set that is maximal in some sense but still acyclic. Alternatively I have a ...
8
votes
2answers
3k views

Prerequisite mathematics for studying data structures and algorithms

Forgive me if this seems trivial to you. But, I do need your advice. I am self-studying computer programming, now want to study Algorithms and Data Structures. All respected texts in A&DS talk in ...
0
votes
1answer
287 views

A question about Flajolet-Martin algorithm

I am reading this algorithm in these notes for counting the number of distinct items in a stream. From my understanding, the basic idea is that if such number is big enough, the distance between ...
7
votes
1answer
824 views

Algorithm to find conjugacy classes of subgroups/elements (in matrix groups)?

I'm looking for a simple (=doable to implement by myself) algorithm to compute the conjugacy classes of elements and subgroups of a given subgroup of $\text{P}{\Gamma}\text{L}(n,q)$. So given a group ...
1
vote
1answer
55 views

What do we mean by 1. and 2. order difference and what can this be used for when making lines and shapes?

So, I got this assignment I'm working on and one of the questions sounds like this: What do we mean by 1. and 2. order difference and what can this be used for when making lines and shapes? I ...
5
votes
1answer
512 views

Minimal set of inequalities

I have a set of $m$ linear inequalities in $R^n$, of the form $$ A x \leq b $$ These are automatically generated from the specification of my problem. Many of them could be removed because they are ...
2
votes
4answers
3k views

Get numbers that have only 2,3 and 5 as prime factors

I am given an integer N. I have to find first N elements that are divisible by 2,3 or 5, but not by any other prime number. ...
4
votes
1answer
661 views

Determining partial derivatives and cross products for bicubic interpolation using function values only?

I'm trying to implement a bicubic interpolation algorithm. In order to calculate the interpolated values, I need to calculate sixteen coefficients used in the calculation process - and that's where ...
0
votes
2answers
398 views

Inverse of matrix with QR method

What is the complexity of finding the inverse of matrix by QR decomposition? A is a $n×n$ with full rank.
1
vote
2answers
830 views

Rectangular spacing algorithm?

Thank God, there is a math section to this site, I'm going insane I have a problem I know how to solve by trial and error but I'm trying to figure out the 'smart' way to do it so I can make it into a ...
1
vote
3answers
927 views

Proving a factorial is not a certain complexity

I know this is a stupid question but I will ask it anyway. I need to do complexity analysis for n! to prove that it is not a certain complexity order. How can I go about doing that? Problem: Prove ...
1
vote
2answers
3k views

Calculating Average Case Complexity

I am trying to find the average case complexity of a sequential search. I know that the value is calculated as follows: Probability of the last element is $\frac{1}{2}$ Probability of the next to ...
0
votes
2answers
366 views

Formalizing the idea of “algorithm”

I have encountered several times, while doing mathematics, the following situation: We have a finite "sequence" $\left(a_{n}\right)_{n\in\left\{ 1,\ldots,p\right\} }$ of some objects that has the ...
0
votes
1answer
48 views

What is the mathematical property that let an algorithm working with a seed?

As programmer i find many solutions that generates pseudo-random values and surfaces, i'm always wondering how they can do that from a mathematical viewpoint. For example i can generate a terrain ...
4
votes
2answers
234 views

Finding the nearest integers to real numbers defined implicitly

I was trying to bound the maximum cost of top-down merge sort: $$ f(0) = f(1) = 0,\quad f(n) = n\lceil{\lg n}\rceil - 2^{\lceil\lg n\rceil} + 1, $$ where $\lg n$ is the binary logarithm of $n$ and ...
2
votes
0answers
218 views

Who invented the breadth-first permutation algorithm?

My initial problem was solved here. It is about enumerating all n-tuples of a permutation in a specific order. The solution algorithm is very simple and I'm sure has been used before. However, I did ...
2
votes
0answers
39 views

How to pick correct sign on matrices such that their sum is a nonnegative matrix?

Given a set of matrix $M_i$, by picking a sign coefficient $S_i\in\{-1,1\}$ How can I effectively find a combination that the sum $M^*= \sum_{i=1}^N S_iM_i$ is a nonnegative matrix. i.e. ...
1
vote
2answers
133 views

Algorithmic Complexity of $i^2$

I am new to the Big O notation in regards to algorithm design. I have had some exposure to it but I am not sure how to find the algorithmic complexity of a given function for a summation. If someone ...
1
vote
2answers
147 views

If $f(n) = \sum_{i = 0}^n X_{i}$, then show by induction that $f(n) = f(n - 1) + X_{n-1}$

I am trying to solve this problem by induction. The sad part is that I don't have a very strong grasp on solving by inductive proving methods. I understand that there is a base case and that I need an ...
3
votes
3answers
341 views

Working out an algorithm for finding out whether a point is in or outside of a 2D closed polygon

I'm having a bit of an issue with the following problem: Write a brief (1/2 page) design specification document (including pseudo code for the algorithm itself) that describes your approach to ...
0
votes
2answers
95 views

Fastest way to compare angles

I' m looking for an efficient (in terms of lowest number of additions/multiplications) way to compare two (directed) angles $\measuredangle p_1 p_0 q$, $\measuredangle p_1 p_0 r$ in a plane. For ...
0
votes
2answers
87 views

Triples algorithm complexity

This not optimal algorithm count the number of distinct triples $(i, j, k)$ such that $a[i] + a[j] + a[k] = 0$. ...
1
vote
2answers
4k views

$T(n) = 2T(n/2) + n \log n$ recurrence relation using master theorem

Assume that $$T(n) = 2T\left(\frac{n}{2}\right) + \Theta(n \log n)$$ By Generic form of master theorem with $a = 2$, $b = 2$ and $f(n) = c \, n \log n$, it can easily be proved that $T(n) = ...
0
votes
1answer
1k views

How to solve tribonacci series [duplicate]

Possible Duplicate: Fibonacci, tribonacci and other similar sequences Suppose my Tribonacci series is like this: \begin{equation} T(n) = T(n-1) + T(n-2) +T(n-3) \end{equation} with initial ...
2
votes
1answer
82 views

What is the value of this summation in Big O terms?

I am trying to do an analysis for the cost of n inserts into a hashtable datastructure and I have a factor like the one below: $$\sum_{i=0}^{\lfloor\lg {(n-1)}\rfloor} 2^i$$ What will be the Big O ...
0
votes
3answers
570 views

Number of combinations avoiding k consecutive elements

I had come across this problem. Consider the list of numbers from 1 to 100. How to find the number of combinations, such that no combination has k consecutive elements? (k is any constant, it can be 3 ...
2
votes
1answer
223 views

Maximizing a linear combination of certain integers

Consider some tuple $x = (x_1, ..., x_k) \in \mathbb{N}^k$ of $k$ non-negative integers such that $x_1 > x_1 > ... > x_k$ and suppose that $A \subset \mathbb{N}^k$ is such that there exists a ...
2
votes
3answers
784 views

Counting subsets containing three consecutive elements (previously Summation over large values of nCr)

Problem: In how many ways can you select at least $3$ items consecutively out of a set of $n ( 3\leqslant n \leqslant10^{15}$) items. Since the answer could be very large, output it modulo $10^{9}+7$. ...
3
votes
1answer
68 views

Show that we can compute the product $n = \Pi_in_i$ in time $O(len(n)^2)$ for given integers $n_1,…n_k$ with each $n_i> 1$.

Show that we can compute the product $n = \Pi_i\ n_i$ in time $O(len(n)^2)$ for given integers $n_1,...n_k$ with each $n_i> 1$. I know that we can compute $ab$ in time $O(len(a)len(b))$ courtesy ...
8
votes
3answers
2k views

How can I explain this integer partitions function recursion?

How to explain how this algorithm works? I need to write an article about this but I can't explain why this recursion works fine. It defines the number of partitions of a given integer ...
2
votes
1answer
1k views

Induction proof of lower bound for $\sum \sqrt n$

I'm having some trouble proving the following statement using mathematical induction: $$\frac{1}{2}n^{\frac{3}{2}} \leq \sqrt{1} + \sqrt{2} + \sqrt{3} + \sqrt{4} + ... + \sqrt{n} ,\text{ (for ...
1
vote
1answer
44 views

How do I project points such as to extend a curve?

Given a roughly drawn line (i.e. a squiggle) consisting of, say a few dozen points, how do I extend the line in keeping with the last few points of the line, i.e. if the line was curving downwards at ...
1
vote
2answers
114 views

Find $y=\sqrt{x}$ where $x$ and $y$ positive integers in polynomial time?

Let $x$ be a positive integer and let $y$ be a real number such that $$y=\sqrt{x}$$ Objectives: If $y$ is an integer, find it in polynomial time. If $y$ is not an integer, prove that there is no ...
3
votes
2answers
1k views

Algorithm to generate a prime number which is n-digits long

Is there an algorithm which, given the number of digits n, generates a prime number which is n-digits long, in polynomial time complexity?
2
votes
0answers
81 views

Proving that an effective procedure is correct

I will start with definitions, theorems, and a few solved exercises which I am taking as theorems now. My actual question will be last, if you want to scroll ahead to see it. Definitions: (1) The ...
1
vote
2answers
104 views

Statistic: calculating error of order of two sequences of objects

I am trying to derive a meaningful statistic from a survey where I have asked the person taking the survey to put objects in a certain order. The order the person puts the objects is compared to a ...