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
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
35 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
15 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
81 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
32 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
35 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
30 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
23 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
33 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
32 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
16 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
928 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
132 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
59 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
34 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
37 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
64 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
30 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
27 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
79 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
242 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 ...
-2
votes
0answers
19 views

Looking for examples of path finding algorithms that use “metagraphs”

I don't think this is the right term (metagraphs), but it seems appropriate. I'm looking for any examples of path finding algorithms that take 2 graphs into account, G1 and G2, where a copy of G2 is ...
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
25 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
26 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
28 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
58 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
40 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
28 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
22 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 ...
0
votes
0answers
9 views

recurrence tree final step - binary search

Starting with the base case and recursive case run times as follows: 􏰀 t(N) = 1 , if N = 1 t(N)= 1+t(N/2) ,ifN > 1 At the end of my tree I have ...
0
votes
0answers
13 views

Examples of Algorithms capable of modifying graph structure?

I'm currently working on a problem where one is presented with 2 connected digraphs (call them G1 and G2), each with an associated set of logical constraints. Each vertex of each graph represents a ...
2
votes
0answers
53 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
18 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 ...
1
vote
2answers
29 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
25 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 ...
0
votes
1answer
31 views

Find all nearest points

I have two sets: $$P = \{p_1, p_2, ..., p_n\}$$ $$Q = \{q_1, q_2, ..., q_m\}$$ For each $p_i$ point I need to find all nearest points in $Q$. I.e., $$p_i \rightarrow \{ q_{i_1}, q_{i_2}, ..., ...
0
votes
2answers
81 views

Minimum number of operations to make all of the strings (objects) the same

Let $A$ be an alphabet, $K$ and $N$ be natural numbers and $X$ be a list of $N$ strings over $A$, each one consisting of $K$ letters. You have one operation ($@f$): convert a string from $X$ to ...
3
votes
1answer
69 views

Algorithm to solve gridlock (traffic jam)

Is there an algorithm for solving a gridlock (traffic jam)? Given a gridlock situation, this algorithm should tell which moves each car should make, and in which order the cars should move, so that ...
0
votes
0answers
25 views

How to approximate a trigonometric to make less computation complexity

I having a trigonometric function such as $$ p_2(s) = \begin{cases} \frac {1}{(2 \pi)^2}(1-\cos (2 \pi s)), & \text{if $s \le1$ } \\ \frac {1}{2 }(s-1)^2, & \text{if $s >1$ } ...
1
vote
1answer
24 views

Origin of divergence in a divergent field (2D)

I have a field of measured vectors, see example of four vectors in image below. If there was no noise they would all point outward exactly from one "central point". i.e. there would be a circle whose ...