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
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
36 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
43 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
112 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
43 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
23 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
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 ...
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
32 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
20 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
2answers
30 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
62 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
39 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
742 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
25 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
113 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
36 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
52 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
372 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
28 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 ...
-1
votes
1answer
34 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
45 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
28 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
27 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
34 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
18 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
24 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
25 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
86 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 ...
1
vote
1answer
33 views

Where does 13 come from?

I am going over the Rod Cutting Problem Everything makes sense to me until For example, $L$ = {9} has the total cost Cost($L$) = $P$[9] = 13, whereas $L$' = {1,1,1,1,1,1,1,1,1} has the total cost ...
0
votes
0answers
14 views

Asymptotically exact estimation of $T(n/3) + T(2n/3) + \Theta(n)$

I have a problem with asymptotically exact estimation of $$ T(n) = T(n/3) + T(2n/3) + \Theta(n) $$ I know, how to solve $T(n) = T(n/3) + T(2n/3) + n$ (using the recursion tree), but when there is ...
1
vote
0answers
14 views

Do you have to use Latin Squares to solve the Social Golfer's problem?

I'm trying to write a program to solve the social golfers program constrained to a certain number of weeks and so far I've been using the Latin Squares method detailed here: ...
0
votes
1answer
41 views

Is there an algorithm to determine if an arc through 3 points is concave up or concave down?

Armed with only the three points in 2-dimensional space, $X = \{x_1, x_2, x_3\}$, is there a simple inequality or algorithm that can return whether or not an arc $A$ through these three points is ...
0
votes
2answers
33 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 ...
0
votes
0answers
41 views

Node potentials of minimum cost flow successive shortest path algorithm

I have a simple directed graph $G(V,E)$ that has a source $s$ and sink $t$. Each edge $e$ of $G$ has positive integer capacity $c(e)$ and positive integer cost $a(e)$. I am trying to find the minimum ...
3
votes
2answers
38 views

Decidability of predicate calculus with equality only

I read in some books that propositional calculus is decidable (e.g. with truth tables), and predicate calculus is not decidable (as proved by Church and Turing). Unfortunately, I do not exactly ...
0
votes
1answer
37 views

Sequence who converges to $\sqrt{a}$ for every $a\geq0$

If we have: $$x_n=\left\lbrace \begin{matrix} b\in\mathbb{R}\setminus \{0\} & ,n=1 \\ \dfrac{a+x_{n-1}^2}{2x_{n-1}} & , n>1\end{matrix} \right.$$ Then, is easy to prove that $(x_n)\to ...
1
vote
0answers
18 views

Prove that your algorithm is optimal by showing that no other algorithm can solve the problem faster in the worst case.

You are given 5 balls that look identical but one of them has a different weight from the others. You are given a balance scale to find the odd ball. Give an algorithm to solve this task that ...
5
votes
3answers
1k views

One number divisible by all prime factors of another?

Given two numbers $x$ and $y$, how to check whether $x$ is divisible by all prime factors of $y$ or not?, is there a way to do this without factoring $y$?.
2
votes
1answer
140 views

Aliens to the Moon

$N$ Aliens want to reach their Moon ($D$ meters away), but they can only put on each other, making a vertical chain. Every $Alien(i)$ has an height $X(i)$ and a lenght of their arms $Y(i)$. ...
2
votes
1answer
60 views

Solving $T(n) = 3T(n-1)$

How is the constant before the $T$ important to the result from $T(n)$ I know that \begin{equation*} T(n) = T(n-1) + 3 \Rightarrow \theta(n)~\text{and}~T(n) = T(n-1) + n \Rightarrow \theta(n^2) ...
0
votes
1answer
39 views

Multi-level bin-packing problem?

Let us consider we have B Bags and each Bag has some number of Items. The problem is to distribute Bags of Items uniformly across as minimum number of Bins as possible. However, there are two ...
3
votes
3answers
45 views

Prove that Euclid's algorithm computes the GCD of any pair of nonnegative integers

I've been struggling with a basic exercise involving Euclid's algorithm and mathematical induction. Given the following definition of the Euclid's algorithm (in Java): ...
1
vote
1answer
77 views

Struggling with difference between greedy and naive but optimal algorithms? (Graph theory)

I've been thinking about the following problem for quite a while and tried multiple solutions, but I'm having difficulty telling the difference between a greedy algorithm and an inefficient naive ...
0
votes
1answer
33 views

Real logarithm of a real matrix?

What is the real logarithm of \begin{equation} \begin{pmatrix} -1 & 1 & 0 & 0 \\ 0 & -1 & 0 & 0 \\ 0 & 0 & -1 & 1 \\ 0 & 0 & 0 & -1 \end{pmatrix}? ...
0
votes
0answers
38 views

Is the following algorithm for finding the minimum diameter spanning tree correct?

You are given an undirected and unweighted connected graph $G(V, E)$ for which you've been asked to find a spanning tree that has minimum diameter. I have an idea but I'm not sure if it's a ...
0
votes
0answers
80 views

completely stuck on this question about decidability

A decision problem X is as follows: $X = f\langle M \rangle\mid M$ is a program that accepts the empty string. Now, we define another decision problem Y as follows: $Y = f\langle P \rangle ...
4
votes
4answers
258 views

Show the probability that the sum of these numbers is odd is 1/2

Setting Let $S$ be a set of integers where at least one of the integers is odd. Suppose we pick a random subset $T$ of $S$ by including each element of $S$ independently with probability $1/2$, Show ...