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
8 views

Algorithm to determine popularity through sentiment, volume, time, and feedback

I am quite new to this space of ranking algorithms, and I'm faced with a problem. I have the following factors that will determine an entity's "popularity" ranking: Number of occurrences mentioned ...
0
votes
0answers
21 views

Algorithms for Taylor Expansions

Is anything known about fast algorithms for taking symbolic Taylor expansions? I have a homegrown algorithm, but it seems to be exponential in the number of terms requested when operations like the ...
0
votes
0answers
39 views

10-Subset Sum: Given a set of integers K and an integer M, is there a subset of exactly 10 elements of K whose sum equals M?

I understand that the more general Subset Sum problem is NP-complete, but I am under the assumption that this more specific version of the problem can be solved in polynomial time. However, I can't ...
0
votes
0answers
17 views

Algorithm to Find Highest Path in a Directed Acyclic Graph

Let $G=(V,E)$ be a directed acyclic graph. We will define the function $h:V\rightarrow R^+$, where h(v) is the height of v. Let $P=(v_1,...,v_k)$ be a path. We will also define ...
0
votes
0answers
10 views

BFS and bipartites graphs

I have the lemma Lemma. Let G be a connected graph, and let $L_0$, …, $L_k$ be the layers produced by BFS starting at node s. Exactly one of the following holds: (i) No edge of G joins two ...
0
votes
0answers
13 views

Maximizing a Special Node-weight sum on a Directed Acyclic Graph

Given a Directed Acyclic Graph (DAG) $G=(V,E)$, also satisfying that if $(u,v),(v,w)\in E \implies (u,w)\in E$. For $S\subseteq V$, define the following set $\Gamma(S)=\left\{u \in S, \not\exists ...
0
votes
1answer
33 views

Function $(2.2)^n$ — what is it?

The running time of an algorithms is $(2.2)^n$. I have to tell what is the maximum $n$ for reaching 1.000.000 steps. What type of a function is $(2.2)^n$? How its output depends on the input $n$? ...
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
24 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
25 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
24 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
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
22 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
49 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
42 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
35 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
40 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
64 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
14 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
85 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
24 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
48 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
16 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 ...