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
51 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
373 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
41 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}, ..., q_{...
0
votes
2answers
108 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 ...
7
votes
1answer
583 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
36 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$ } \end{cases}$$...
1
vote
1answer
33 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 ...
0
votes
3answers
485 views

Efficient algorithm for taking powers of binary numbers?

Is there any efficient algorithm for taking powers of binary numbers? Or even just squaring one? Thanks ahead of time.
1
vote
2answers
54 views

Problem implementing a QR factorization

I'm trying to write a Fortran subroutine to compute a QR factorization using the Householder method. To test my routine, I compute the factorization of the following matrix: $$ A = \begin{pmatrix} ...
-1
votes
2answers
188 views

Writing a GCD of three numbers as a linear combination

i know how to find the $\gcd(5,11,2^{2015}-1)$. but i can't seem to find the linear combination. do you find it the same way we find the linear combination of two integers.
1
vote
1answer
85 views

How to set up this algorithm?

I'm doing a simple budget app, to make some calculations to improve private economy. I've made an option where you can enter the value of the money that are in the bank right now, and how many days ...
1
vote
1answer
96 views

Given that Minimum Spanning Tree is NP-complete show that Hamiltonian Cycle is NP complete

So first of all I know finding MST is in P and is not NP complete. But I checked last year exams from my University and there is a problem: Given that Minimum Spanning Tree is NP-complete show that ...
0
votes
0answers
42 views

Implementing specific SVD algorithms

My goal is to learn to implement the two-sided Jacobi SVD, a method of SVD for bidiagonal matrices, and a method of SVD for tridiagonal matrices. Can anyone recommend a place to learn about these, or ...
1
vote
1answer
25 views

How to efficiently list prime with a very specific property

I noticed that my phone number 06 xx xx xx xx is a prime number. Ok that cool ... But if you had the country code (+33 for france), ...
1
vote
0answers
19 views

Is the mapping achieved by the discrete Frechet Distance the best achievable pair decomposition?

I have the following proble: There are 2 sequences $P$ and $Q$ composed by $M$ and $N$ points respectively. I want to calculate the discrete Frechet distance between them. This operation outputs also ...
0
votes
0answers
20 views

A suitable algorithm to change strings to zero strings

I found a programming exercise I couldn't solve. Namely, I have been given a long binary string and a fixed set of operations. Here, an operation means that it takes a substring and transforms its ...
0
votes
0answers
48 views

How many counts the square number?

For example I have a number is $55$. Can I check this for how many counts number's square create this number. For example I have $55$ So, I know this number total from 5 number, which are $$55 = 1^2+...
0
votes
1answer
26 views

Why is $X_m$ and $Y_m$ not included in the shaded region(where median can lie)?

This problem is from Algorithms, problem 2 The Problem Given two sorted list of numbers $X$[1..$n$] and $Y$[1..n]. we need to come up with a O($\log n$) time algorithm to find the median of the 2$n$ ...
1
vote
0answers
60 views

Squaring a matrix using a linear memory

I have a N x N matrix (let's denote it with A). I want to calculate $A ^ 2$, using $\theta(N)$ memory (speed does not matter as long as it's a polynomial) on one processor. I believe that this can ...
0
votes
1answer
359 views

What algorithm can sort the first sqrt(n) elements of an array in O(n) time?

I want to partially sort an array of $n$ elements to get the first $\sqrt{n}$ elements sorted, and it has to be done in $O(n)$ time. The complexity $O(n)$ seems to imply that it is necessary to go ...
0
votes
1answer
36 views

Finding algorithm to design combinatorics formulae per input data

Problem: calculate how many unique "words" can be made using the letters of your a) name (Kateryna - 8 letters, letter 'a' used twice) b) lastname (Atamanchuk - 10 letters, letter 'a' used 3 times) ...
0
votes
0answers
22 views

Computing efficiently a small base to the power a large number

Is there a fast algorithm to compute an exponential with a small base, (namely , close to 1) For example, computing 1.01 to the power 100?
2
votes
1answer
78 views

The output spanning tree of Kruskal's algorithm is a minimum spanning tree

I want to show that the output spanning tree $S$ of Kruskal's algorithm is a minimum spanning tree, so it is of minimum weight, by contradiction. We suppose that $S$ is not a minimum spanning tree. ...
0
votes
1answer
59 views

Have you seen these integer factorization algorithms before?

I have two algorithms for finding two factors, $p$ & $q$, of a number $N$. The algorithms are (hopefully) obviously related. The pseudo-code for them follows: Algorithm 1 ...
1
vote
1answer
97 views

Summation to Closed Form conversion

I am struggling to understand basics as it related to forming a closed form expression from a summation. I understand the goal at hand, but do not understand the process for which to follow in order ...
0
votes
0answers
83 views

proof that some expected value equal to $\theta (\log n - \log k)$

So here is the problem - Given the following equation: $(c_2\cdot \log n) - (c_1\cdot \log k)\le E(X)\le 1+ (c_1\cdot \log n) - (c_2\cdot \log k)$ When $c_2,c_1\gt0$ and also $c_1\gt c_2$ In ...
5
votes
0answers
70 views

Analysis of sorting Algorithm with probably wrong comparator?

It is an interesting question from an Interview, I failed it. An array has $n$ different elements $[A_1 , A_2, ..., A_n]$ (random order). We have a comparator $C$, but it has a probability $p$ to ...
3
votes
1answer
227 views

The output of Kruskal's algorithm is a spanning tree

I want to show that the output of Kruskal's algorithm is a spanning tree. Let $G$ be a connected, weighted graph and let $S$ be the subgraph of $G$ which is the output of the algorithm. $S$ cannot ...
4
votes
1answer
200 views

Is there a fast divisibility check for a fixed divisor?

Is there a fast algorithm to check if $d \mid n$ is true for varying $n$, if divisor $d$ is fixed? Variable $n$ is a $w$-bit binary integer, $d$ is an integer constant.
6
votes
3answers
465 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
22 views

simple algorithm to go thru all lexicographic permutaions

I'm working thru the euler question 24 (not looking for the answer) and came across this site describing an algorithm to get all the permutaions. Here are the steps they lay out : Steps to ...
1
vote
0answers
47 views

Is there an optimal algorithm to calculate $2^n - 1$ in $\theta(n^n)$

The sequence $(f_{n})_{n \in \mathbb{N}}$ is defined by $f_{0} := 0, f_{1} := 1$ and $f_{n} := 3f_{n-1}-2f_{n-2}$ for $n \in \mathbb{N}_{0} \setminus \{0,1\}$. Is there an algorithm that takes an $n \...
2
votes
4answers
78 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 ...
0
votes
1answer
37 views

Hamilton-like paths in digraph

We are given digraph with two (possibly the same) vertices - let's call them S and F. We are also given some set of vertices W (possibly empty, possibly consisting of all vertices of digraph). We don'...
2
votes
1answer
1k views

Given the graph below, use Dijkstra’s algorithm to find the shortest path (More details included)

So I've found out a few things and was wondering if someone could verify if I'm doing this correctly. So here is an example I've been given: Here is the solution to that example: Now here is the ...
0
votes
1answer
637 views

Need help to understand the solution for NP-completness proof (3CNF <= 0-1 integer-programming problem)

I was trying to solve problem from Cormen page 1100 34.5-2 Given an integer $m * n$ matrix A and an integer $m$-vector $b$, the 0-1 integer- programming problem asks whether there exists an integer $...
1
vote
2answers
123 views

Intersection of integer sets

This is probably a trivial question for mathematicians but I am not seeing how to approach the following problem: Imagine two sets defined by: ...
5
votes
1answer
120 views

Two pawns walking in a complete graph

We have a complete graph $G = \langle V,E\rangle$ with non-negative values on edges. Let $C = \{v_1,v_2,\ldots,v_n\}$ be an ordered collection of $G$'s vertices. At the beginning we have two pawns in $...
3
votes
1answer
70 views

Help understanding the complexity of my algorithm (summation)

As an exercise, I wrote an algorithm for summing the all elements in an array that are less than i. Given input array A, it produces output array B, whereby B[i] = sum of all elements in A that are &...
2
votes
0answers
42 views

Assignment problem, minization of the Standard Deviation

I have an assignment problem. So typically I need to find the optimal combination between two sets of parameters P, M. I know that the Hungarian Algorithm is often privileged for this kind of problem ...
0
votes
0answers
25 views

How to figure out whether PCA can be performed on a data set or not?

I do have idea on the way PCA works but I do not know how to figure out whether a high dimensional data set is suited for PCA compression. I googled for some algorithms but could find any. Are there ...
1
vote
0answers
24 views

Is there any general algorithm to solve such a 3D cutting problem?

Suppose a cuboid $\mathbb{A}$ has $L$,$M$ and $N$ as its length, width and height respectively, where $L\ge{M}\ge{N}>0$; Now we want to cut $\mathbb{A}$ into smaller cuboids with length $x$, width $...
3
votes
1answer
73 views

A result of Erdos: the multiplicative persistence of $n$ is at most $c\ln(\ln n)$

Multiply all the digits of a number $n$ by each other, repeating with the product until a single digit is obtained. The number of steps required is known as the multiplicative persistence of $n$. ...
1
vote
1answer
632 views

How is de = 1 (mod ϕ(n)) calculated

I am reading RSA algorithm. So, I was writing a question but I saw this question and still couldn't understand it. If $$e\cdot d \equiv 1 \pmod{\varphi(n)},$$ then $$ed=k\cdot \varphi(n)+1, \qquad k\...
4
votes
1answer
50 views

Proving a recursive algorithm on a set is true

If I have an algorithm that returns the entry of a set with the largest value, how do I prove the algorithm is true mathematically? (I know I could just write tests for it.) I understand how to use ...
1
vote
1answer
30 views

How to compare times?

i'm looking for an algorithm to compare 2 different time records. My time format is hour:minute:second:nanosec I tried something like this, but its not working well: if (hour <= anotherHour) { ...
0
votes
2answers
137 views

Find Algorithm, Given a List of Arcs, which Maximizes the Number that Fit on a Circle

I'm trying to find an optimal algorithm that, given a list of arcs $(x_i, y_i)$, where $x_i$ and $y_i$ are the starting and ending angle measurements of the arc in radians, maximizes the number of ...
0
votes
1answer
32 views

Elaboration needed on a section of a published paper about dictionary learning

I will be doing my master thesis on dictionary learning, and I am trying to understand basic concepts of the subject reading the following paper: K-SVD: An Algorithm for Designing Overcomplete ...
4
votes
0answers
198 views

Implementing the Risch algorithm to integrate $\dfrac{\log(x)+2}{x^{2}\log^{3}(x)}$

Following the work of Andreas Wurfl i am trying to implement the Risch algorithm on $\int{\dfrac{\log(x)+2}{x^{2}\log^{3}(x)}dx}$ following his method for extensions that are purely logarithmic, we ...