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)

0
votes
3answers
38 views

A lower bound on sorting algorithms

I think I have a proof that $n\ln n$ is optimal in the sense that is it a lower bound for sorting algorithms. See here for a list. It must be greater than $n$ as this is too linear, and the $\ln$ ...
1
vote
0answers
34 views

Factorizing a Polynomial over the Integers

What are the most efficient algorithms to factorize a polynomial over integers, knowing that it has only integer roots? I googled around a lot, but most of the work seems to be around Finite fields. ...
0
votes
0answers
28 views

Optimization Toolbox (fmincon) - How to set logical constraints?

I'm pretty new to Optimization and barely understand it (was about ready to slit my wrist after figuring out how to write Objective Functions without any formal learning on the matter), and need a ...
2
votes
0answers
23 views

Factorization by multiplying and representation as difference of two squares

Definition 1.$$R: \mathbb N \to \mathbb N: \ R(n) = \lceil\sqrt{n}\rceil^2-n.$$ This is the distance from $n$ to the smallest square greater or equal to $n$. Definition 2. Let $a$ be as positive ...
-1
votes
1answer
22 views

How to compute the time complexity for a recurrence relationship?

I have to compute the time complexity for this recurrence relationship: T(n) = \begin{cases} c1, & \mbox{if } n\mbox{ = 1} \\ 8T(n/4) +n +c2, & \mbox{if } n\mbox{ > 1} \end{cases} Can ...
1
vote
1answer
17 views

Computing wavenumbers for discrete Fourier transform

I'm trying to implement a Fortran program to compute the derivative of a function using the FFT. To begin with, just to test my installation of fftpack, I computed the Fourier transform of ...
-1
votes
3answers
52 views

Find Numbers that Start with $3$ and End with $1$ on the given interval [closed]

I am looking for a function / formula that would take in a number and determine whether it starts with 3 and end 1 For example, with 3 digits numbers, I'd like to get $301, 311, 321, 331$ and so on ...
0
votes
1answer
37 views

How does one map a graph into a vector (feature space)?

Assuming there is an undirected weighted graph. How can one convey it's geometrical structure into a feature space? Are there any common practices?
0
votes
0answers
52 views

Solving the recurrence $T(n) = 5T(n/7) +\log n$

I am trying to solve the recurrence $T(n) = 5T(n/7) +\log n$ to find the complexity of an algorithm. Although I solve this immediately with the Master Theorem if I try to solve the recursion I found ...
2
votes
1answer
31 views

Big O notation proof for a divided problem

I have a problem: the algorithm is dividing the given problem into two subproblems - one is 3/5 big and another is 4/5 of the size of the problem - and then merges those two parts together in a linear ...
1
vote
1answer
63 views

Extended Euclidean Algorithm with negative numbers minimum non-negative solution

I came through a problem in programming which needs Extended Euclidean Algorithm, with $a*s + b*t = \gcd(|a|,|b|)$ for $b \leq 0$ and $a \geq 0$ With the help of this post: ...
2
votes
0answers
40 views

${n \choose m}$ on periodic lattice (Bravais)

How can I generate all symmetry-inequivalent selections of m sites on a periodic 2d (Bravais) lattice with n sites? Are there some general results or theorems which may be useful in this type of ...
0
votes
1answer
19 views

Time complexity function

I'm not sure I should post this on the Mathematics website or the Computer science website of Stack Exchange. If I'm wrong I will replace my question. So I'm trying to calculate the time complexity ...
0
votes
1answer
39 views

static offline bipartite graph matching

Consider a static offline bipartite graph where we have complete knowledge of the two sets of vertices $U$ and $V$. Now an edge is drawn between a vertex of $U$ and vertex of $V$ if the difference of ...
3
votes
2answers
77 views

Strategy for selecting the optimal time to check a cooldown timer

This is a hard problem for me to word in the title, so I'll try to do better now. Consider the following "game": You are sitting in a room beside a table. In the middle of the table there exists a ...
1
vote
1answer
45 views

Berlekamp's algorithm

My given problem is to factorize the following polynomial, $f(x)=x^8+x^6+x^4+x^3+1$ over $ F_{2}$ Well, my first step was compute $f'(x)=8x^7+6x^5+4x^3+3x^2+1=x^2+1\mod(f)$ Now i find out that ...
0
votes
1answer
28 views

time complexity of an algorithm

Hi all i'm trying to predict/calculate the time complexity of an algorithm but i'm having some difficulties with the summations the algorithm: ...
1
vote
0answers
20 views

Multi-armed bandit with infinitely-many arms

Has anyone studied variants of the multi-armed bandit algorithm with infinitely many arms? I have a collection of distributions parametrized by an integer $n$. Unfortunately, I can't analytically ...
0
votes
0answers
8 views

Dividing weight (increasing domain) while preserving log-concavity

I have a sequence of $n$ values $p_1,\dots,p_n \in [0,1]$ satisfying (a) $\sum_{j=1}^n p_j = 1$ and (b) $p_j^2 \geq p_{j-1}p_{j+1}$ for $1 < j < n$. I have no control on the values of the ...
8
votes
2answers
306 views

Reorder adjacency matrices of regular graphs so they are the same

Given a matrix A of a strongly $k$ regular graph G(srg($n,k,\lambda,\mu$);$\lambda ,\mu >0;k>3$). The matrix A can be divided into 4 sub matrices based on adjacency of vertex $x \in G$. $A_x$ ...
10
votes
1answer
168 views

All clubs have a member among $n$ people

Let $n \geq 14$ be a positive integer. In a city there are more than $n$ clubs, all of them have exactly 14 members. At each group of $n+1$ clubs there is a person who is member of at least 15 of ...
1
vote
0answers
24 views

Boxcar average algorithm of the specified width.

Ok, I need to write a java algorithm which simulates the SMOOTH function written in IDL where the SMOOTH function is given by $$ R_i = \begin{cases} \displaystyle \frac{1}{w} \sum_{j = ...
1
vote
1answer
11 views

Understanding terminology related to implementing the sobel edge detection algorithm

I'm trying to follow a scholarly paper that discusses a modified implementation of the sobel edge detection algorithm, but I'm not following the terminology 100%. The Sobel detector consists of ...
2
votes
1answer
75 views

Algorithm - Maximum subarrays with sum and OR

I was thinking on the following problem: Given an array A. The value of an interval from i to the index j is defined as follows: Take the maximum value from that interval, and add it to the OR ...
1
vote
0answers
44 views

Distinct pairs formed using repeated sequences

Problem setting: Let $N$ and $M$ be positive integers. Let $I'$ and $J'$ be ordered sets, i.e., sequences, $\{1,2,\ldots,N\}$ and $\{1,2,\ldots,M\}$ , respectively. The sequences are $N$ and $M$ in ...
1
vote
1answer
22 views

nearest-neighbor algorithm efficiency

I'm starting to read Steven Skiena's Algorithm Design Manual, and one of the examples discusses the nearest-neighbor solution to planing a route that visits each in a set of points and ends up back ...
1
vote
3answers
204 views

How to find the inverse of $n\log n$?

So I'm on chapter $1$ of introduction to algorithms & at the end the book proposes a problem: here The answers are there & I was able to work through most of them myself despite my lack of ...
1
vote
0answers
17 views

Calculation of arrival time of messages from 1 source through 2 different routes

I need to simulate sending messages from $A$ to $B$ as follows: Each message is sent $N$ times from $A$ on the same time, passes through a certain route $R_n$ and arrives at $B$. Travel time of $R_n$ ...
1
vote
1answer
42 views

Combinations for pairing groups

I have a little bit of a complex question and I don't know anything about combinatorics, but I'm working on software problem and I'm trying to figure out how my algorithm will scale. I'm having to ask ...
2
votes
1answer
44 views

Speeding up integer division if only certain bits in result are needed

Let's say I need to divide two integers $x$ and $y$, but I only care about the lowest 8 bits of the answer, i.e. I'm calculating: $$r = \frac{x}{y}\,\,\%\,\,256$$where % is the modulus operator. Is ...
2
votes
2answers
62 views

Most efficient algorithm to distribute n n-bit strings among n people

We are given $n$ people, whom we identify with the elements of $[n]=\{1,\ldots,n\}$. We are also given a finite collection $\mathcal{K}$ of subsets of $[n]$. The problem is to (efficiently) ...
2
votes
0answers
33 views

How do I solve the Frenet-Serret equations for the curve, instead the curvature/torsion?

So I happen to be working in a hobby side project which happens to be increasingly convoluted so now, naturally, I have come to the aid of the gurus. It turns out that I am trying to solve the ...
0
votes
2answers
106 views

How to find the greatest prime number that is smaller than $x$? [duplicate]

I want to find the greatest prime number that is smaller than $x$, where $ x \in N$. I wonder that is there any formula or algorithm to find a prime ?
0
votes
0answers
25 views

Proving that each element in reservoir have equal probability of been selected in reservoir sampling?

Here is the description of the algorithm and proof of the correctness The algorithm creates a "reservoir" array of size $k$ and populates it with the first $k$ items of $S$. It then iterates through ...
1
vote
0answers
16 views

Number of number in range $(l, r)$ satisfying XOR constarint

Here's a questions that's been bugging for some time now: Define the set $S_n = \{k \oplus (k + n)\mid k \in \Bbb Z, k ≥ 0\}$ (here, $\oplus$ is bitwise exclusive OR). To put it another way, $x$ ...
0
votes
0answers
21 views

Non-existence of an algorithm that deals with a specific problem in constant time

I want to show that there doesn't exist any algorithm $A$, that satisfies the following three properties altogether: The algorithm $A$ only uses comparisons, allocations, copies etc., so basically ...
1
vote
0answers
15 views

Number of ways to connect sets of k vertices in a perfect n-gon [duplicate]

This is a copy of my post at Mathexchange.com, as my question is still not fully answered and I really wanna find a solution to this. Feel free to refer to there for useful comments and partial ...
28
votes
12answers
2k views

Computing irrational numbers

I am genuinely curious, how do people compute decimal digits of irrational numbers in general, and $\pi$ or nth roots of integers in particular? How do they reach arbitrary accuracy?
0
votes
1answer
52 views

The Change-making problem algorithm proof (at the dynamic programming method)

I saw here the algorithm for the "Change-making problem" (at the dynamic programming method). I saw it here: http://www.columbia.edu/~cs2035/courses/csor4231.F07/dynamic.pdf I'm trying to find a ...
1
vote
2answers
23 views

Expected codelength for Huffman-algorithm with probabilities

I am unable to solve the following problem: Let $$n \geq 2$$ $$p_{1} \geq p_{2} \geq ... \geq p_{n}$$ $$p_{i} = 2^{-k_{i}}$$ with $k_{i} \in \mathbb{N}$ and $\sum_{i=1}^{n}p_{i} = 1$. $p_{i}$ is the ...
4
votes
1answer
93 views

Knight movement on chess field

I had this task in programming competition: There are two knights, which are $(p_1,q_1)$ and $(p_2, q_2)$. $(p,q)$ knight is figure, with p(q)-length first step, and q(p)-length second step in ...
0
votes
2answers
39 views

How to find kth smallest value of a linear equation

Here's a question that was asked in IOITC 2009 India. Even though it should have a solution related to algorithms, yet I post it here as it is pretty "number-theoretic". Indraneel loves posing ...
1
vote
0answers
22 views

Time complexity for the multiplication of three rectangular matrix

For the multiplication of two matrix, one can use the classical methods, such as strassen algorithm, to reduce the time complexity. Here, I just wonder if there is any efficent algorithm aiming at the ...
0
votes
1answer
37 views

How to calculate the number of combinations of $x$ integers, each with a value between $y$ and $z$?

For example, if I have 4 integers, and each can be between 0 and 36, how many combinations are there? If the numbers have appeared before, but in a new order, then this still counts as a new ...
2
votes
1answer
44 views

What's the fastest known running time for a spigot algorithm for computing an arbitrary digit of $\pi$?

That is, for the fastest known algorithm for doing so, how many steps will it compute the $n^{\text{th}}$ digit of $\pi$ in? I know some people define running time as the number of steps it will take ...
5
votes
0answers
113 views

puzzle for Vietnamese eight-year-olds [duplicate]

I read in the Guardian about a puzzle given to 8-year old in Vietnam. Enter the digits 1 to 9 into the following grid so that the equality holds Now, given access to a computer, this can be ...
0
votes
2answers
46 views

Computing expectation exercises; using linearity of expectation and iterator random variables

Disclaimer: This is homework that is overdue by, but I do want to understand it and get through it, so any hints or guidance is appreciated This is for an algorithms class currently dealing with ...
0
votes
0answers
25 views

Algorithm for filling in points around a circle with increasing density

The aim of this question is to decide on the order in which to download a series of high-resolution files that together represent a 720° rotation around an animating object. When all the files are ...
0
votes
0answers
26 views

Algorithm for generating a series of contrasting colours

On a computer screen, colours can be defined as having 0-255 units of red, green and blue. This creates a 3-dimensional colour space with $256^3$ different colours, from 0-0-0 for black to 255-255-255 ...
0
votes
0answers
12 views

Lemke Howson Algorithm Tableau

I am working on an implementation of Lemke Howson Algorithm and I am reading this paper below. http://cnl.gmu.edu/TAVRI/research/LemkeHowson.pdf Can someone please explain why on page 7 they say ...