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)

2
votes
1answer
202 views

Solving for the closed form of a recurrence relation

Can someone concisely explain how we can find the closed form of a recurrence relation? I know the iterative process is generally the preferred method, but I'm having trouble deriving the steps and ...
3
votes
5answers
357 views

Translating matrix fibonacci into c++ (how can we determine if a number is fibonacci?)

Is it possible to determine if a number is a fibonacci number in less than N time (where N is the Nth fibonacci number) using the matrix method? I'm trying to exclude external libraries like cmath or ...
2
votes
4answers
8k views

Recurrence - finding asymptotic bounds for $T(n) = T(n-2) + n^2$

I've been working on a problem set for a bit now and I seem to have gotten the master method down for recurrence examples. However, I find myself having difficulties with other methods (recurrence ...
2
votes
1answer
205 views

It seems like a nim variant

Now this is a more of a computer science problem than a math problem but it is concerning game theory and it does seem a lot like nim (it's from an online judge), so i'm kinda stuck on this one i'd ...
0
votes
2answers
683 views

How to recognize ellipse/ellipsoid from random points? UN-weighted average?

Suppose we are getting random points in 2D (or 3D) which tend to be on ellipse (or ellipsoid). We can't guarantee points are uniformly distributed over ellipse (ellipsoid surface). The task is to ...
5
votes
1answer
192 views

Maximal subset with rank $k$

I'm trying to solve the following problem for an algorithm I'm trying to develop and I couldn't find anything helpful in scholar google. Here is the question: Suppose I have a set of $N$ vectors ...
1
vote
2answers
979 views

single elimination tournament, don't understand question?

A single elimination tournament is performed in rounds. In each round the teams each play exactly one game and the winners continue, and the losers are knocked out of the competition. So, in each ...
0
votes
1answer
352 views

What is a good reference for basic shape detection algorithms

I've been doing research for a presentation on computer vision, and right now I'm specifically researching shape detection. Since this is a math course and not a programming course, I'm only concerned ...
0
votes
0answers
182 views

Searching a Young tableau for a collection of numbers

This question is a follow up on: Searching a Young tableau. The previous question was "How many comparisons are needed to find an element $x$ in an $n \times n$ Young tableau of distinct elements ...
0
votes
2answers
670 views

Prove that $n! ≥ (⌈n/2⌉)^{⌈n/2⌉}$ [closed]

Prove that : $n! ≥ (⌈n/2⌉)^{⌈n/2⌉}$
0
votes
1answer
68 views

Generating hex color from a pair of numbers

I want to generate a color, in hexadecimal from a pair of two numbers. These numbers could be of any value. But the resulting number (in decimal) must be between 0 and 16777215 Its not the most ...
2
votes
1answer
494 views

Euler's totient function and complex numbers

I have this problem without a solution (yet) Say I have a complex number and wish to calculate $\phi(a+bi)$ where $\phi(n)$ is Euler's totient function. How would it have to be calculated? I know ...
3
votes
1answer
1k views

Searching a Young tableau

An $n \times n$ Young tableau is an $n \times n$ matrix of distinct integers, with each row and each column sorted in increasing order. Now, we are given an $n \times n$ Young tableau $T$ and an ...
9
votes
2answers
195 views

Why does the term ${\frac{1}{n-1}} {2n-4\choose n-2}$ counts the number of possible triangulations in a polygon?

In the given picture bellow, it counts the number of different triangloations in a polygon, how do the get to this expression, why is it: $$ {2n-4\choose n-2} $$ and why do we multiply it by ...
1
vote
1answer
407 views

Proving numerical stability of an algorithm.

Let us define $\alpha=x^{2}-y^{2}$ and $\beta=2xy$ for $x,y\in\mathbb{R}$. In order to calculate the $\alpha$ and $\beta$, we use the following algorithm: $$p:=x-y;\quad q:=x+y;\quad \alpha=p\cdot ...
2
votes
1answer
551 views

Choosing permutations with constraints

I have to choose $k$ items out of $n$ choices, and my selection needs to be in the correct order (i.e. permutation, not combination). After I make a choice, I receive a hint that tells me how many of ...
0
votes
1answer
140 views

What kind of algorithm/formula would I need to calculate how many items need to fill requirements?

I need to do some calculations in code but I'm not quite sure what the best mathematical approach is... Say I have data like so: ...
2
votes
2answers
51 views

Is there a general algorithm that can be implemented via a computer program that can identify the function being represented by a graph?

It might help understanding my question to think of the hypothetical situation in which I draw a seemingly random function on a piece of paper (with an accurate coordinate axis already on the paper), ...
0
votes
4answers
551 views

How to understand that sequence is logarithmic?

Let's say I have example of phonebook lookup. I need to find one record in it. I can always divide phonebook into 2 equal parts and try to find a record in that way. ...
1
vote
1answer
462 views

How to convert a sequence of numbers in the formula?

I'm trying to understand different sorting algorithms and their BigO notation. Suppose, I'm using insertion sort and I have the worst case: 6 | 5 | 4 | 3 | 2 | 1 ...
2
votes
1answer
917 views

Recursive FFT java implementation [closed]

Given below is my java program for FFT. For the input {0,2,3,-1} its returns a false output in complex point representation. ...
9
votes
5answers
864 views

Algorithms for “solving” $\sqrt{2}$

The very first words out of my mouth need to be this... "Solving" is the wrong term since I am speaking about irrational numbers. I just don't know which word is the correct word... So that can be ...
0
votes
1answer
251 views

Proof for asymptotic tight bound when $C=a_k/2$

In an algorithms lecture in school theres a proof for asymptotic tight bound like: Take $C=a_k/2$ and show that $f(n) \ge \frac{a_k}{2} n^k$ when $n > N$ for some $N$. $$\begin{align} ...
1
vote
1answer
47 views

Distribution of proportions of each row cell

I'm trying to make sense of some data I have. Below is a simplified version of how data is structured. To get some context, the table shows the distribution of an investor's investments across ...
1
vote
2answers
85 views

How to find on what ranges one sorting algorithm is better than other?

I'm reading the book "Introduction to algorithms" and want to solve one task from it. But don't know the best way how to find solution. The task is: We have 2 sorting algorithms. Сomplexity of first ...
0
votes
1answer
825 views

Multiply two large numbers in under 1000 instructions using reduced ISA with only 7 registers [closed]

Is it possible to multiply two large (15 bit) numbers efficiently (in under 1000 instructions) using the following ISA: ...
0
votes
1answer
805 views

Find median of 2 sorted arrays with different lengths

I'm trying to solve the below problem for my assignment but I have no clue how to find the time algorithm. If I have two arrays of same even length then I get, $T(n) = T(n/2) + \theta(n)$ but what ...
1
vote
2answers
165 views

Removing redundant half-spaces that bound a convex polytope

I am computationally representing a convex polytope in $\mathbb{R}^n$ as a set $A$ of half-spaces that bound it; each such half-space is represented by a row vector $\mathbf{v} = \begin{bmatrix}v_1 ...
0
votes
1answer
58 views

How to calculate the approximate gradient of a series of points?

The situation is this: a series of points are randomly located, a line is needed to represent the gradient of those points. ./ / . . / ./ / . I ...
2
votes
2answers
584 views

Solving recurrences with boundary conditions

I'm trying to follow CLRS ("Introduction to Algorithms") and I just hit a question in a practice assignment I found online that I just can't make any sense of. Consider this problem: Show that ...
1
vote
2answers
59 views

Showing $f(n)$ has upperbound of $O(g(n))$

I am currently enrolled in an algorithms course and was learning about upper, lower and tight bounds of functions. I am confused on how to show that a function $f(n) = O(g(n))$ for some $n > n_0$ ...
0
votes
1answer
111 views

Compute Birthdate From Age

I have an interesting problem. I want to compute a birthdate (Month Date, Year) from a given age. I understand that subtracting the given age from the current date will supply the year of birth, but ...
4
votes
1answer
2k views

Trouble finding closed-form solution to summation

I have this question on my assignment for a computer science course (analysis of algorithms), so any help would be appreciated, but I am not looking for the answer itself. I am trying to find the ...
1
vote
2answers
3k views

How to test if a graph is fully connected and finding isolated graphs from an adjacency matrix

I have large sparse adjacency matrices that may or maybe not be fully connected. I would like to find out if a matrix is fully connected or not and if it is, which groups of nodes belong to a ...
1
vote
1answer
120 views

Help finding Complexity in Big-O notation

I have found the complexity of an algorithm as the expression below. How can I find the complexity in big O notation for such expression? Or prove that it's bounded by $n^3$ or $n^4$. Can I use triple ...
1
vote
1answer
26 views

If I am checking for $s$ divides $n$ on the interval $S = [3, n-x]$, how large can I make $x$ to ensure I have verified $n$ is prime?

$\forall x \in \mathbb{Z}^+$, $x > 1 \longrightarrow x-2$ does not divide $x$ I have not yet proven this, which might be a good aside for my discrete math. One of my current assignments in ...
2
votes
1answer
69 views

Biased linear regression

I have a set $S$ of coordinates $(x,y)$, and am estimating $f(x) = ax + b$ where $a > 0$. I also happen to know that $\forall x,y((x,y) \in S \implies y < f(x))$. The question is how I can ...
2
votes
1answer
103 views

A way to codify (pre-calculatate) if a one Tree Node is a descendant of another

I have a simple, 1-directional tree representing the veins in a human body. It looks somewhat like this (red dots are nodes, blood flow is always downwards, sorry for my drawing): What I need is a ...
4
votes
1answer
93 views

Reordering of a sequence of points

Given a finite sequence of points $\{\boldsymbol{\alpha}_k\}_{k=1}^m$, here $\boldsymbol{\alpha}_k\in \mathbb{R}^n$. My question is: How to find a reordering of ...
0
votes
1answer
2k views

Dominant term and Big Omega

For the given expression, determine the dominant term and then use the dominant term to classify the algorithm in big-O terms and also in $\Omega$-notation. $$n^3+n^2\log_2(n)+n^3\log_2(n)$$ So, I ...
0
votes
1answer
47 views

Probability : Dividing a list into 2 classes

I have a list of integer numbers ($n$). I am dividing it into two parts $n_1$ (smaller) and $n_2$ (bigger) such that the length of $n_1 \ge a*n$; $a$ is positive and $a \lt 0.5$. What is the ...
1
vote
4answers
203 views

How to solve real-time games?

In game theory, we can solve a game by calculating its game tree as backward induction. This method seems to work for turn-based games, but how about real-time games? Are they have game trees? It ...
3
votes
2answers
88 views

Algorithm to find the optimal setup

Suppose I have $2n$ numbers, from which I will compute $n$ sums of two-number pairs. For example, I have $6$ numbers $(1, 2, 3, 4, 5, 6)$ and I can generate three sums of $1+3=4$, $2+6=8$, and ...
3
votes
1answer
1k views

Origin of the Breadth-First Search algorithm

I'd like to know about the history of the breadth-first search algorithm. Can anyone point me to its inventor? It appears that the depth-first search algorithm is attributed to a man named Charles ...
1
vote
1answer
84 views

Finding a distribution for random number generation

I am writing a program for solving the shortest path in travelling salesman problem, with a twist that there are multiple salesmen who partition the cities among themselves, thus creating two part ...
0
votes
1answer
158 views

Asymptotic Complexity Problems with Subtraction

I know that when finding the asymptotic complexity of a given function, you must pay attention to the rate of change in a for loop. For example: for (i = 1 to n) { //some action of constant time ...
1
vote
1answer
216 views

Properties of shortest walks and simple paths during optimization

Let $G=(V,E)$ denote a digraph, $s,t\in V$ two different vertices in $G$ and $w:E\to\mathbb R$ the weighting function for all edges. Moreover $\mathcal K$ denotes the set of all walks, $\mathcal E$ ...
4
votes
0answers
172 views

Use of graph theory to determine tensor contraction ordering

I am considering using a computer program to execute tensor contractions like the following: $\displaystyle \sum_{ij}^{o} \sum_{ab}^{v} \sum_{KL}^{X} B_{ia}^{K} B_{ia}^{L} B_{jb}^{K} B_{jb}^{L} $ ...
0
votes
2answers
196 views

How to prove there is no algorithm for a problem e.g. generating next prime?

Say I want to find the next prime directly without a test. AFAIK there is no known formula. Is it possible that since we've failed to find a formula, then we might be able to prove that there is no ...
0
votes
3answers
261 views

Finding an approximate diagonal in a grid

Imagine a 2 dimensional grid, with a variable size of $ x*y $. For this example of figure 1, let $ x=14; y=5 $. Now one may position "pixels" in this gird. They can only be placed on the grid's points ...