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

Finding the upper bound for a number's factors length

Okay, so the title is a bit misleading but I had to keep it short.. Anyhow, if I have a number X what will the length of it's longest two factors be? For example: $X = 10000$ I want $3$ and $3$ ...
0
votes
3answers
52 views

Multiplying array elements

We are given a sorted array containing elements at indices $x_1,x_2,x_3,x_4,....x_n$. We have to find the product $\displaystyle\sum_{i,j,k}x_ix_jx_k$ where $j\geqslant i$ and $k\geqslant j$. For ...
0
votes
0answers
21 views

Determine complexity of algorithm

I have two pieces of code below. a) sum = 0 ; for ( i = 0 ; i < n ; i++ ) for ( j = 1 ; j < n^4 ; j = 4*j ) sum++ ; b) ...
0
votes
1answer
42 views

Fractional Knapsack- explanation

The following algorithm is given: ...
0
votes
1answer
57 views

Complexity of Least Common Multiple

I would like to know the complexity of computing the least common multiple of $n$ natural numbers. Does it depend on Euler's totient function?
2
votes
3answers
85 views

Almost extended Euclidean algorithm - $ax+by=\gcd(a,b)+2$

So I have this equation: $$\eta+2=2g+1n,$$ where $g,n \in \mathbb{N}_{\geq 0}$ and $\eta \in \mathbb{N}_{>0}$. I want to find all possible integer-valued 2-tuples $(g,n)$ that satisfy this ...
0
votes
1answer
28 views

Scheduling: Moore's algorithm

In scheduling we have Moore's algorithm to minimize the the number of late jobs. Because of the EDD-rule (earliest due date first), I guess this algorithm has complexity $\mathcal{O}(n \log n)$. I ...
0
votes
1answer
222 views

Basic idea of proof

I am trying to understand the proof that the expected running time of quicksort is $O(n \log n)$. Could you maybe explain me the basic idea? I am confused right now. EDIT: Suppose that we use the ...
0
votes
3answers
24 views

An upper bound on sorting algorithms

I think I have a proof that $n\ln n$ is optimal for sorting algorithms. See here for a list. It must be greater than $n$ as this is too linear, and the $\ln$ factor comes from the harmonic series, ...
1
vote
0answers
30 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
23 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
20 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
16 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
47 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
32 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
50 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
61 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
39 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
76 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
42 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
23 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
17 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
1answer
172 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
167 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
19 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
73 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
39 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
18 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
200 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
15 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
41 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
60 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
29 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
100 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
21 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
20 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
29 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
22 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
84 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 ...