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
1answer
32 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 ...
1
vote
0answers
13 views

Finding a “special” non singular submatrix

Given a square integer matrix $A \in M_n(Z)$ and two subsets $I, J \subset \{ 1, \ldots, n\}$, we define $A_{I,J}$ as the sub-matrix of $A$ containing the rows (resp. columns) whose index is in $I$ ...
0
votes
2answers
32 views
1
vote
0answers
32 views

Most efficient algorithm to distribute n n-bit strings among n people [on hold]

If there are N people, and a corresponding set of subsets K, what is the most efficient algorithmic approach I can use to give everyone a (not necessarily unique) N-bit string (leading zeroes ...
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
84 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
1answer
14 views

Return random element from array excluding elements from subarray

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
17 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
13 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 [on hold]

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 ...
27
votes
11answers
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
20 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
65 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
33 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
25 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 ...
1
vote
1answer
30 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
14 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
8 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
15 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
23 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
40 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
37 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
494 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
93 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
45 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
198 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?
3
votes
1answer
34 views

Alpha max plus beta min algorithm for three numbers

There exists fast algorithm to approximate length of 2D vector - Alpha max plus beta min algorithm. It says that $\alpha\cdot\max(x,y)+\beta\cdot\min(x,y)\approx\sqrt{x^2+y^2}$ for some constants ...
0
votes
2answers
25 views

How do I compute this recursive function efficiently? [closed]

Let $f(x,y) = xy + f(x-1,y-1) $ where $f$ equals $0$ if either $x$ or $y$ is $0$. Also $x,y$ belong to $\mathbb{N}$. Describe an efficient (less then $O(n)$) algorithm for computing $f(x,y)$.
1
vote
0answers
25 views

Shortest path to find a highway

I remember this as a classic problem, but all Google results are video-game-related, so I guess I should ask it here: An adventurer got lost in the desert, but he knew that there was a highway ...
1
vote
1answer
29 views

Select $k$ non overlapping segments from $n$ points

We have $n$ points , say labeled from $1$ to $n$. We have to select $k$ segments from it so that no $2$ overlap. One possible solution would be by using a recurrence relation $f(k,n)=\sum ...
1
vote
1answer
13 views

Algorithm for creating a list of items with maximum sum of scores

I have a set of items $I\{a,b,c,...\}$. I need to create an ordered list $L$ of a given size $m$. Each combination of item $x$ and index $i$ gives a different score. For example: if I put item $x$ at ...
1
vote
1answer
20 views

Finding $k$-clique in a graph with running time of $|V|^{k-1}$

This is a homework problem. Let's say I have a graph $G$, how can I find a $k$-clique (i.e. a complete graph with $k$ vertices) inside $G$? So far I can think of a naive solution where I check if each ...
0
votes
1answer
19 views

How would you apply the Greedy technique in this situation/why wouldn't it work?

I am going over the Rod Cutting Problem The author states "Selling a rod of length $i$ units earns $P$[i] dollars." Here is the table $P$ for this problem I'am currently going over this question ...
3
votes
2answers
80 views

Finding all k-size subgraphs

I have no experience with advanced combinatorics, but I have to solve a problem that I think I will need advanced combinatorial techniques, correct me if I am wrong. Let $G$ be a large directioned ...