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)

1
vote
0answers
11 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 = ...
-2
votes
1answer
14 views

Optimal subset problem [on hold]

Given a finite set: $X=\{x_1, x_2, ..., x_n\}$, $x_i \in U$, where $U$ is some universe of objects, define: $f:P(X) \rightarrow {\rm I\!R}$, where $P(X)$ is the powerset of X, to be some function. ...
1
vote
1answer
10 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 ...
0
votes
1answer
41 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
28 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
13 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
4answers
185 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
38 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
42 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 ...
0
votes
2answers
38 views
2
votes
2answers
53 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
24 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
92 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 ?
1
vote
0answers
16 views

Return random element from array excluding elements from subarray [migrated]

Basically, I need something like this: f(a[], b[]) = random element from a[] which is not in b[] Idea I have is this one: ...
0
votes
0answers
18 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
15 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
18 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
votes
0answers
18 views

We need to find whether there exists such subset of n numbers, that XOR of it's elements is a power of 2 [closed]

For Example; 2 3 1 2 3 2 10 20 First line of input represents test case, First line of each test case represents n, Second line contains n numbers. We need to find XOR of subsets of n numbers is a ...
1
vote
0answers
14 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
1k 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
27 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
21 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
69 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
34 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
18 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
26 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
34 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
111 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
39 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 ...
-1
votes
0answers
15 views

Encode/decode hexadecimal challenge [closed]

So there is or was a sponsored challenge about encode/decode hexadecimal. Why does X becomes Y and is it possible to reverse Y without X? ...
0
votes
0answers
20 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
25 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
9 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 ...
0
votes
0answers
16 views

Enumerating set combinations in an order that maximises the number of previously unseen subsets

Consider a set $S=\{a,b,c,d,e,f,g,h,i,j,k\}$, $\left|S\right|=11$. There are ${11 \choose 5} = 462$ combinations of $S$'s members of size $5$. There are $462! \approx 1.419 × 10^{1032}$ possible ...
2
votes
1answer
28 views

How to show that the Restricted-3-color decision problem is in the polynomial class

I'm struggling to answer a past paper question, which asks to prove that the defined problem is in the polynomial complexity class(P). The question is mentioned below The only strategy I can come ...
0
votes
1answer
17 views

Excluding wrong points in least square method

I am using least square method to find linear equation but getting some problems below. I would like to exclude wrong points before calculating linear line. Is there any idea for this?
0
votes
0answers
25 views

Multiple choice quiz answer calculation

i wasnt sure if this was a question for the MATH section but i am hoping that you guys can help me out. Say you have a multiple choice quiz that consists of 8 ...
0
votes
2answers
28 views

Solving an equation about water filling algorithm.

Recently, I am reading a document about the water filling algorithm. I encounter an equation: $$\sum_{i=1}^r \left[ \mu - \frac{1}{\rho \lambda_i} \right]_+ = 1,\tag{1}$$ where $r$ is a positive ...
0
votes
1answer
43 views

MATLAB: minimize function using x value from previous iteration

I'm trying to develop an algorithm for a proximal point method defined as: $$ \underset{x \in \rm I\!R^n}{\arg\min} f(x) + \lambda g(x) $$ where f(x) is a convex and coercive function and also ...
6
votes
2answers
38 views

If there isn't currently a working algorithm to solve a chess problem and win the game, how do user-vs-computer chess games work?

I was watching a video on Computational Complexity and the lecturer mentioned that "we do not current have a algorithm to allow us to win a game of chess". If so, I'm interested in knowing how chess ...
4
votes
4answers
593 views

A 3rd grade math problem: fill in blanks with numbers to obtain a valid equation

Even though this is a 3rd-grade math problem, people found it extremely hard. Any people have a solution, or algorithm is welcome. I'll try make a program base on the algorithm and see if it's ...
0
votes
0answers
23 views

relation between direct and indirect BFGS algorithm

I am trying to verfiry the calculation of $B^{-1}_{k+1}$ from the Wikipage. I tried using Sherman–Morrison formula twice: ...
3
votes
1answer
96 views

A few questions about KSVD algorithm (dictionary learning) in a paper

To learn more about dictionary learning, I am currently trying to understand the concept in detail and to do so, I've found the following paper quite informative: KSVD: an algorithm for designing ...
0
votes
0answers
35 views

Algorithm for finding zero of an odd function from n-sphere -> R^n

There is a well-known Borsuk-Ulam theorem stating that each continuous mapping $f : S^n \rightarrow \mathbb{R}^n$ that is odd in sence of $f(v) = -f(-v)$ for each $v \in S^n$ (where $-v$ denotes the ...
0
votes
0answers
73 views

Herbrands Algorithms and greek philospher

So the problem states "outline the steps in Herbrands algorithm leading to the proof that the following statement is right. ...
3
votes
0answers
46 views

NP-complete impossible to solve in $O(n)$

NP-complete problems are likely to be unsolvable in polynomial time (although no one proved it yet). My question is, has anybody proved that they are unsolvable in $O(n^d)$ for some concrete small ...
3
votes
2answers
201 views

How to calculate a Modulo?

I really can't get my head around this "modulo" thing. Can someone show me a general step-by-step procedure on how I would be able to find out the 5 modulo 10, or 10 modulo 5. Also, what does this ...
0
votes
1answer
24 views

Hungarian Method Algorithm

I'm trying to implement the Hungarian Method Algorithm but I'm having some trouble assigning zeros when following it through by hand. (Following step 3 here: link) If I have a 5x5 matrix: I go ...
0
votes
1answer
27 views

What is the difference between Dijkstra's method and dynamic programming when finding the shortest root of a path?

I am learning about shortest path algorithm. What is the difference between Dijkstra's method and dynamic programming when finding the shortest root of a path?