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)

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
61 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
736 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
356 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
43 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
23 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
85 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
13 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
40 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
76 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
32 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 ...
7
votes
1answer
157 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 ...
1
vote
1answer
30 views

Switching lights in a matrix

I'm interested in papers and articles on the following problems (not necessarily solutions). At least is there a name to these that I can lookup ? Say that $a_{ij} \in \{-1, +1\}$ for $1 \leq i, j ...
0
votes
2answers
30 views

Analysis of Algorithms - Big O Notation Equivalences - Limits

Please see below block question from review for test. True Or False? Justify Your answers A) is 2^(n+1) = O($2^n$) B) is 2^2n = O($2^n$) C) is log($n^2$) = O(logn) D) is ...
0
votes
1answer
29 views

Where does the root of this tree come from?

I am doing a practice question from Midterm Dynamic Programming The Problem : Consider a row of n numbers a1, ..., an. The numbers are all positive, and n is even. We play a game against an ...
1
vote
1answer
72 views

How to find worst case in chain matrix multiplication

The question we got was Determine a worst-case parenthesization of the matrix-chain product whose sequence of dimensions is (5, 2, 3, 10, 4, 6, 7, 8). what i dont understand is how do we determine ...
2
votes
1answer
44 views

Wouldn't this Greedy Algorithm achieve the highest possible of money in this situation?

I am doing a practice question from Midterm Dynamic Programming The Problem : Consider a row of n numbers a1, ..., an. The numbers are all positive, and n is even. We play a game against an ...
1
vote
0answers
31 views

people passing a bridge (a proof for a greedy algorithm)

the problem some people are passing a bridge . each one takes a different time to pass . assume the people are sorted by their passing time increasingly . these are the conditions of passing the ...
0
votes
1answer
33 views

Looking for algorithms capable of modifying graph structure

I realize this is a quite a general request. I'm just looking for examples of path searching algorithms for directed graphs which are capable of utilizing simple modifications (adding vertices, adding ...
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] ...
4
votes
1answer
24 views

Find the “surface vertices” of a collection of points.

I am currently doing some experiments in order to simulate liquids. I have a collection of 3D points that interact with each other to form a body of water. I would like to form a mesh from these ...