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)

0
votes
1answer
19 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 ...
2
votes
4answers
54 views

Two non-negative functions $\,f,g$, such that $\,f \not\in \mathcal O(g)$ and $ g \not\in \mathcal O(\,f)$

Show that there exist two non-negative functions $\,f,g: \mathbb{N} \rightarrow \mathbb{R}$ such that $\,f \not\in \mathcal O(g)$ and $ g \not\in \mathcal O(\,f)$. It would be easy two find two such ...
2
votes
1answer
54 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 ...
1
vote
2answers
13 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 ...
0
votes
2answers
31 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 ...
10
votes
3answers
942 views

Algorithm(s) for computing an elementary symmetric polynomial

I've run into an application where I need to compute a bunch of elementary symmetric polynomials. It is trivial to compute a sum or product of quantities, of course, so my concern is with computing ...
1
vote
0answers
13 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
24 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 ...
0
votes
0answers
17 views

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

That is, for the fastest known algorithm for doing so, how many steps will it compute the nth digit of π in? I know some people define running time as the number of steps it will take to compute any ...
4
votes
3answers
316 views

Just a 3rd grade math problem in my country. Please help.

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 ...
5
votes
0answers
110 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
36 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 [on hold]

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? ...
2
votes
1answer
307 views

Maximum subarray problem

Given a 2d array N*M made of only 1's and 0's . I need to find a maximum subarray(square or rectangle) between two rows of the given 2d array which has all ones inside it. I need to find count of ones ...
3
votes
2answers
77 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 ...
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
17 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
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
13 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
17 views

Finding regular expressions for which a given Turing machine halts and accepts, halts and rejects, and diverges.

Consider the Turing machine M = (Q,Σ,Γ,δ,q,F) F = {t} Q = {q,r,s,t,v,x} Σ = {a,b,c} Γ = {B,a,b,c} δ = [q,a,q,a,R] [q,b,q,b,R] [q,c,v,b,R] [q,B,r,B,L] [r,a,s,B,L] [r,b,s,B,L] [r,c,s,B,L] ...
3
votes
0answers
32 views
+150

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 ...
2
votes
1answer
27 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 ...
22
votes
6answers
5k views

Efficiently finding two squares which sum to a prime

The web is littered with any number of pages (example) giving an existence and uniqueness proof that a pair of squares can be found summing to primes congruent to 1 mod 4 (and also that there are no ...
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
22 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
26 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
35 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 ...
0
votes
1answer
291 views

Multiple Choice Knapsack Problem (MCKP) where one class requires more than one item

I have the following problem of which I am attempting to find a near optimal solution: I have one knapsack which can hold a maximum weight. I must select exactly one distinct item from a number of ...
2
votes
1answer
337 views

how to show the convergence of an algorithm

I have two unknown variables x and y which are non linear equations to be solved. \begin{eqnarray} y=\frac {|\sin(2x+\theta)|}{\sin x\sqrt{A+2B\cos(2x+\theta)}} \nonumber \\ x=\arccos\bigg( ...
0
votes
4answers
2k views

Co Prime Numbers less than N

I need to find all the numbers that are coprime to a given $N$ and less than $N$. Note that $N$ can be as large as $10^9.$ For example, numbers coprime to $5$ are $1,2,3,4$. I want an efficient ...
2
votes
1answer
62 views

Proof of algorithm refinement

I recently had an interview in which I was asked to produce an algorithm to that computes the pairs of integers, from a list, that add up to a integer k. I then had to increase the time efficiency of ...
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: ...
0
votes
0answers
69 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. ...
0
votes
0answers
18 views

Parallel Algorithm for Donor/Recipient Matching - Graph Matching/Optimization [closed]

This question was cross-posted and answered on Computer Science Stack Exchange. I'm not certain I can accurately describe the problem using my knowledge of discrete math, so pardon any ...
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 ...
2
votes
1answer
47 views

Determine whether two line segments intersect, given that one of them is axis-aligned

I'd like to know if a line segment intersects another, where the 2nd line segment will only be horizontal or vertical. There are similar questions about general line segments, but this constraint ...
3
votes
0answers
43 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
192 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 ...
7
votes
1answer
155 views

Accelerating approximations for arccos

I have recently built a method to accelerate drastically the accuracy of the following approximation of $\arccos(x)$ : $f_n(x)=2^n\sqrt{2-2g^{n-1}(x)}$ where $g(x)=\frac{1}2\sqrt{2+2x}$ and ...
0
votes
1answer
26 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?
1
vote
1answer
32 views

Puzzle 8 Compatible States [closed]

I need to know if is there any algorithm that allows to know beforehand, without searching for every possible solution to the the initial set, if we can reach a second given set. For example: ...
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 ...
3
votes
1answer
32 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)$.
5
votes
1answer
263 views

Algorithm for tetration to work with floating point numbers

So far, I've figured out an algorithm for tetration that works. However, although the variable a can be floating or integer, unfortunately, the variable ...
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 ...
2
votes
1answer
318 views

Fast generation of Pareto-distributed randoms.

I'm developing a library of routines for generating random numbers for simulations (it's on GitHub). I've included fast routines for normally distributed and exponentially distributed randoms, using ...
0
votes
1answer
404 views

Find all “critical nodes” in a graph

Say there is a graph in which every node is connected to every other by some path. How would i find the particular nodes, which if removed would lead to some of the nodes NOT being connected to all ...
0
votes
2answers
29 views

Traveling salesman problem (TSP): what is the Relation with number of vertices and length of the found route?

I know that there are many algorithms (exact or approximate) which implement the traveling salesman problem. I would like to know the relation between the number of the vertices (i.e., the places to ...