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
0answers
6 views

Given M points and a weighted graph G, map the vertices to distinct points to minimize sum(edge_weight*edge_length)

Given an arbitrary undirected weighted graph G with N vertices, and an arbitrary set of M points P in euclidean 3-space, where M>=N, map the vertices to distinct points such that sum(edge_weight * ...
1
vote
1answer
24 views

What is the name of this kind of factoring algorithm

I just think about algorithm to find factor of number by doing something like guessing last digit of number and increase digit bit by bit Such as, I want to find factor of 749 Algorithm would begin ...
0
votes
1answer
30 views

Is my exam board correct in saying that a variable is a condition? [closed]

A question given in an exam goes as follows: A student is tracing the following algorithm- Start Input N Let A=1, B=1, C=0 Let C = C+A Let D = A +B Print A Let N = N-1 If N ...
1
vote
0answers
23 views

Catalan Number Modulo Prime

What is the fastest method to find the $n$th Catalan number modulo some prime $p$? I was looking at Lucas's method to solve $\binom{2n}{n}$ fast, but not sure if it will work. What is the fastest way ...
0
votes
1answer
13 views

Modular Exponentiation doesn't work on a prime mod?

For 83627264^275372 mod 277 using modular exponentiation, I noticed that things weren't lining up when I checked them on Wolfram. So far I have this: 83627264^1 mod 277 = 133 83627264^2 mod 277 = 238 ...
1
vote
3answers
59 views

Integer solutions to $xyz = w^2(x+y+z)$

I'm looking for a way to enumerate all positive integer solutions of the equation $xyz = w^2(x+y+z)$ where $w \le W$ and $1 \le x \le y \le z$. Could anyone provide a hint at how to approach this? ...
12
votes
0answers
187 views

Dynamically two-coloring a finite graph

Let $G=(V,E)$ be a finite graph whose vertices are going to be colored dynamically. More precisely, consider time periods $t \in \left\{0,1,2\ldots,\right\}$ and for each time $t$ and $i \in V$, let ...
6
votes
0answers
64 views

Heuristics for topological sort

I have a number of modules connected in a Directed Acyclic Graph. My problem is to find an optimal execution order (minimize the total execution time). Any topological sort suffices for a valid ...
0
votes
0answers
14 views

Is the Antikythera Mechanism Turing-Complete?

Is the following Turing-complete? https://en.wikipedia.org/wiki/Antikythera_mechanism As in, it possible to perform all of the operations of a Turing-machine, albeit with finite memory, with this ...
0
votes
0answers
24 views

Rosenbrock function matlab

I am new to MATLAB and I am asked to implement on matlab the following algorithm: for an unconstrained minimisation problem. I am asked to apply the BFGS method with armijo line search ...
-1
votes
2answers
37 views

Algorithms on arrays [closed]

You have an array called $A$ of length $n$ (indexed from $0$), filled with numbers from interval $[1,n]$, not necessarily different. You need to know how many subarrays this array has in which every ...
0
votes
0answers
23 views

Rectangle-Rectangle Intersection Area - Area Only

Suppose I have two rectangles that are not necessarily axis-aligned. What is a fast way to calculate their intersection area? Note that I am aware of convex polygon intersection and area algorithms; ...
-1
votes
0answers
7 views

Optimal locations for vertices of a polygon with given area

I want to find the optimal locations for vertices of a polygon (with area A) such that it is as close as possible to the desired area A'. Please note that the vertices need not be fixed at their ...
1
vote
0answers
15 views

Alpha Max Plus Beta Min Calculation

I read about the Alpha Max Plus Beta Min algorithm described here. Here is a screenshot from the wikipedia page: I think understand what the algorithm is supposed to do. It makes an approximation ...
0
votes
0answers
13 views

Creating a dynamic fee payable to workers

(Imagine) I am an employer who needs 1000 small jobs (all the same) completing by 1000 random people online. My budget is USD2000 so l can only pay USD2 for each small job completed. I have a 48 hour ...
0
votes
0answers
20 views

Pisano Period - Fibonacci

I have to construct an algorithm which will return a fibonacci number mod another integer. I know that i have to implement the Pisano period. I know how to receive it, but the problem comes when I ...
8
votes
1answer
95 views

Most efficient method for computing Singular Value Decomposition of a triangular matrix?

There are several methods available for computing SVD of a general matrix. I am interested in knowing about the best approach which could be used for computing SVD of an upper triangular matrix. ...
0
votes
1answer
34 views

Is there an algorithm or formula that does not involve trial and error to find all solutions to this equation?

I'm trying to write a program that outputs all solutions to the following problem, given any $s$: $$s = n(a + b) + b$$ $$n,a,b,s\in\mathbb{Z}^*$$ However, I can't seem to find any simple way to ...
1
vote
0answers
48 views

How to find several rectangles with minimum area to cover the red cells? [closed]

In Figure 1, (a) is the input mesh, we want to find several rectangles to cover the red cells in (a), at the same time, the sum area of these rectangles should be as small as possible. Figure 1(b) ...
0
votes
1answer
22 views

Show that $f(n) \in \Theta(n^k)$

Let $f(n) = a_0+a_1 n+a_2 n^2+ \cdots +a_k n^k$ be a degree-$k$ polynomial, where every $a_i > 0$. Show that $f(n) \in \Theta(n^k)$. Furthermore, show that $f(n) \notin O(n^{k'})$, for all $k' < ...
0
votes
1answer
23 views

Let $n_1e, n_2e,\ldots,n_ke$ be k numbers, find $e$ if $n_i\in\mathbb{Z}^+$

I have measured a quantized (or discrete) physical quantity. This means that there exists a fundamental quantity $e$ such that the physical quantity is an integer $n$ times the fundamental quantity ...
0
votes
0answers
17 views

upper Hessenberg algorithm

Upper Hessenberg Algorithm Above is an algorithm for reducing a general mxm matrix $A$ into upper hessenberg form. The operation count is ~ $\frac{10}{3}m^3$. I am trying to derive the analogous ...
-5
votes
1answer
41 views

Pseudocode algorithm for the product of the first n positive integers [closed]

This is for discrete mathematics: Write a pseudocode algorithm to compute the product of the first n positive integers. How many multiplications does your algorithm perform? I tried starting off ...
5
votes
1answer
93 views

Complexity of Gaussian Process algorithms is $\mathcal{O}(n^3)$

It is often quoted that the complexity of Gaussian Process algorithms is $\mathcal{O}(n^3)$ due to the need to invert an $n \times n$ matrix, where $n$ is the number of data points. But as far as I ...
0
votes
0answers
13 views

Expectation times of greedy scheduling of tasks $\{t_i\}$ drawn from a distribution $f_T(t)$

I have a question about the parallel scheduling of a set of finite, independent computational tasks with durations $\{t_i\}$ on a set of $c$ computing cores, where we do not know the task durations a ...
1
vote
0answers
16 views

How to enumerate 2D integer coordinates ordered by Euclidean distance?

The square of Euclidean distance between $(x, y)\in\mathbb{Z}^2$ and origin is $d = x^2+y^2$. How to enumerate the coordinates $(x, y)$ in ascending order of $d$? For example, the first 14 sets of ...
1
vote
0answers
53 views

Looking for a perfect square

I have a base number and I add to this number in increments. Is it possible to calculate where is the nearest perfect square without going through all the numbers? Example: Base number 11 Increment ...
0
votes
0answers
15 views

Finding a circuit in a weighted graph with weight closest to desired value

In an edge-weighted graph, is there an algorithm to find a circuit starting from a certain vertex, where the sum of the weights on the circuit is closest to a desired value? For instance, say I want ...
1
vote
0answers
34 views

Practical example of superiority of randomized algorithm

I'm looking for an example to show my students of an algorithm for which randomization of some kind leads to better performance on average. And I don't want that randomization to be of the Monte Carlo ...
0
votes
1answer
39 views

Algorithm for the independent domination number

A dominating set for a graph $G = (V, E)$ is a subset $D$ of $V$ such that every vertex not in $D$ is adjacent to at least one member of $D$. The domination number $γ(G)$ is the number of vertices in ...
0
votes
1answer
53 views

Is $n^2$ bigger than $n\log n $? [duplicate]

How to prove $n^2$ is bigger than $ n\log n $? Do I have to use L'Hôpital's Rule? Can you give me an idea?
0
votes
1answer
46 views

Proof that Gale-Shapley is man optimal

I'm having trouble following this proof that the Gale Shapley algorithm always outputs an optimal matching for men. Overall I find it hard to follow (probably because I find the notion of "optimal ...
1
vote
1answer
60 views

Sum of all numbers less than equal to X relatively prime to all number less than Y

Here's a programming question probably needing lots of math: Given two integers X and Y, you need to find the sum of all positive integers less than or equal to X, which have no divisor smaller ...
0
votes
0answers
13 views

Using radix sort for sorting $n$ real numbers (number of digits is bounded)

Let it be $N$, a set of $n$ real numbers. We will assume that the number of digits for all $n_i$ at $N$ is at most $c=O(1)$. I want to modify radix sort, so that I can sort with it the set $N$ in ...
1
vote
0answers
58 views

number of strings which differ at atmost n positions?

I have been given a string T comprised of only 's','t','u','v' as characters . I want to find numbers of strings with length |T| which differs at atmost n position from T. Also each such string must ...
0
votes
1answer
120 views

Multiply $3$ or more numbers at the same time.

Consider a set of numbers $N \in \Bbb N $ in the range $[1, M[$, where all the numbers are co-prime with $M$ How can we easily multiply certain numbers of that set at the same time, where computation ...
0
votes
0answers
25 views

Determining integer solution for the system of two linear equations

Let $a_1, a_2, \dots a_m$ be unknown non negative integers and $n_1, n_2, \dots n_m$ be strictly increasing sequence of positive integers. How to determine that if the system $$\sum_{i=1}^m a_i = P;\ ...
2
votes
1answer
83 views

Mathematically representing combinations with integers uniquely?

Say I want to pick up $k$ amongst $n$ with respect to order. I am thinking about splitting it into two separate problems. ...
0
votes
0answers
23 views

Algorithmic differentiation graph

I have very basic question about reverse mode algorithm calculation. It is well-known that we calculate derivatives according to chain rule, using sub expressions. I was trying to find kind of proof, ...
1
vote
1answer
32 views

The HITS Algorithm and its Authority Graph

I'm currently reading over this article about the HITS searching algorithm (note that this question doesn't require knowledge of HITS, only that of basic matrix theory). On page 14, Definition 4.3, ...
1
vote
1answer
46 views

Primality testing vs sieve

If the goal is to decompose an integer into its prime factors, is it better to use a sieve (such as the Sieve of Eratosthenes) or trial division up to the square root? Wikipedia has the statement ...
5
votes
0answers
49 views

Are algorithms for elimination of quantifiers over the reals practical?

I wanted to find the semialgebraic set in the $(a_0,a_1,a_2,a_3)$ space that guarantees that there exists at least one real root of the general polynomial equation of degree 4. For that purpose, ...
0
votes
1answer
15 views

Explanation of proof of correctness of Gale-Shapley algorithm

I'm going over a proof that after the Gale-Shapley algo runs, all men and women are matched. From these slides Claim. In Gale-Shapley matching, all men and women get matched. Pf. [by ...
0
votes
0answers
20 views

Placing gas stations

This is similar to a vertex cover problem but it will be smaller than a vertex cover. Think of this problem as you have a map and the vertices are cities and the edges are the roads from one city to ...
2
votes
0answers
51 views

How to model task scheduling with constraints

I am trying to model a task scheduling with constraints, in order to understand which model or algorithm is better suited to compute an optimal solution. Suppose I have $n$ jobs with CPU loads ...
1
vote
0answers
23 views

How can one manually calculate the date conversion to the Hebrew calendar

There already are algorithms that can be used to concert a date from different calendars into the Julian Day Number (JDN) and a JDN into the Hebrew calendar. But how can one calculate the conversion ...
0
votes
0answers
31 views

General Multiplication Algorithm for Finite Field of GF(p^m) for small values of p^m

I am working on a small computer program to generate multiplication table of general finite field in form of GF(p^m) where p is a prime number and m is an integer greater than one. While the special ...
0
votes
0answers
39 views

How to argue a problem is NP

I was given an example where the last letter of the first word is the first letter of the second word and the last letter of the second word was the first letter of the third word and so on... So, ...
4
votes
1answer
53 views

How do I prove that this algorithm about selecting sets of 3 objects works?

I have a selection of balls of different colours. I want to remove selections of three differently coloured balls in order to leave as few as possible. For example if I have 3 red, 4 green, 5 blue ...
0
votes
0answers
14 views

QR algorithm didn't give the expected result

QR Algorithm can be Applied to any Hessenberg Matrix (source) https://en.wikipedia.org/wiki/Eigenvalue_algorithm#Iterative_algorithms $$A_{k-1}=Q_kR_k, ~A_k=R_kQ_k$$ EigenValues = $diag(A_k)$ ...