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)

2
votes
1answer
80 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
27 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
75 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
207 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
65 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 ...
5
votes
4answers
2k 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 correct....
1
vote
0answers
34 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: $$\left(\underbrace{B-\frac{1}{s^tBs}Bss^tB}_{=:A}+\frac{1}{s^ty}yy^t\right)^{-...
2
votes
1answer
204 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
50 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 ...
3
votes
0answers
70 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 $d$?...
4
votes
3answers
34k 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
89 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
407 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?
4
votes
1answer
203 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 $\...
-1
votes
2answers
30 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
43 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
59 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 i*f(k-1,n-...
1
vote
1answer
27 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
41 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
38 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
123 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
36 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 ...
1
vote
0answers
40 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: http://mathpages.com/home/...
0
votes
1answer
66 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
88 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 relationship between the number of the vertices (i.e. the places ...
3
votes
2answers
75 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
40 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
34 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
2k 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
69 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
68 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
336 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
264 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
57 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}? \end{...
0
votes
0answers
105 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 correct ...
4
votes
4answers
364 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
179 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 $g^n=g\...
1
vote
1answer
64 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
60 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
34 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
242 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
69 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
87 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
34 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
37 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] [s,a,x,a,...
4
votes
1answer
39 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 ...
2
votes
0answers
95 views

Efficient computation of matrix determinant in finite ring

I am trying to implement generalization of Hill cipher. My idea is very simple: the size of key matrix should be arbitrary number not only three. All steps of this cipher is trivial except computation ...
1
vote
0answers
52 views

Learning Booth's Algorithm, I Can't Find the Issue on Final Result

I am practicing using Booth's Algorithm to multiply a positive number and a negative number (specifically the problem is $-12 \times 4$). I have included my attempt, but I can't find the issue. If ...
2
votes
2answers
49 views

Simple Adding and Subtracting algorithm to get a current amount

So this is my first post and its probably a really dumb question but I cannot get my head around a proper algorithm to handle the following situation. I have a dataset that contains employees who ...
1
vote
1answer
379 views

0/1 knapsack upper bound

I'm new to the 0/1 knapsack problem and I've ordered my nodes into profit/weight as: Knapsack max weight: 12 ...