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)

3
votes
0answers
49 views

Add vectors from a set to reach the goal vector, using the minimum possible cost

I am trying to solve a problem in an optimal way. The problem is as follows: We have an n-dimensional space In this space, we have a "finish" point with n coordinates, all non-negative We have a set ...
2
votes
0answers
139 views

subtract a number from its digits until it reaches 0 [closed]

Can anyone help me with some algorithm for this problem? We have a big number (19 digits) and, in a loop, we subtract one of the digits of that number from the number itself. We continue to do this ...
0
votes
0answers
87 views

Big Oh Complexity of the algorithm “for $i=1$ to $z$, for $j = 1-X(i)$ to $Y(i)-n^2$ set $k=0$”

I've got a past paper algorithm question I'm trying to complete. I was hoping you could helped me, if so great if not then it's fine :P if you can keep in mind ironically (yep cs student) I'm not ...
6
votes
1answer
97 views

How to eliminate some edges of a lattice to get exactly k paths?

We have an $n$ by $n$ lattice. We want to find a way to eliminate some edges, so that there are exactly $k$ paths from $(1,1)$ to $(n,n)$ of length $2n-2$. (this means our paths should be NE). I don't ...
2
votes
0answers
110 views

Show that matrices multiplication and LUP decompositions have the same difficulty

Let $M(n)$ be the time to multiply two $n\times n$ matrices, and let $L(n)$ be the time to compute the LUP decomposition of an $n\times n$ matrix. How to show that multiplying matrices and ...
1
vote
0answers
51 views

partitions of finite set in same-size parts having at most one element in common

Given g ≥ 2, k ≥ 1 and a population of p = kg workers, I'm trying to figure out the longest series of work shifts such that: during each shift, all workers work in k teams of g people; any two ...
1
vote
1answer
116 views

general formula for permutations with some ordering

Assume I want all permutations of a set of numbers with certain numbers must go before others. Similar to this question but I'm looking for a more general formula. For example the set ...
0
votes
1answer
23 views

A question about importance sample and Metropolis Algorithm

I am reading this paper by Beichl, I., & Sullivan, F. (2000) on Metropolis algorithm. I understand rejection sample. In the section "The Rejection Sample", I can understand the equation: ...
1
vote
1answer
188 views

Differential problem solving with Euler and Heun methods

I have to write application which solves task presented below. I only know some c# so I will stick to it. It is some kind of homework but I am asking for help with understanding this and advice for ...
4
votes
1answer
55 views

Find an assignment of courses to days so that no student has more than one exam on the same day is NP-complete?

Given a list of $N$ courses, $M$ students, the list of courses each student is taking and an integer $K$ representing the duration of the exam phase, is there an exam schedule consisting of $K$ dates ...
11
votes
4answers
281 views

How to compare products of prime factors efficiently?

Let's say that $n$ and $m$ are two very large natural numbers, both expressed as product of prime factors, for example: $n = 3×5×43×367×4931×629281$ $m = 8219×138107×647099$ Now I'd like to know ...
0
votes
1answer
59 views

Why won't my conjugate gradient algorithm work?

I made this simple Conjugate Algorithm on Matlab n = length(b); r0 = b - A*x0; p0=r0; k=1; n0=(r0')*r0; while n0 >= eps && k <= n ...
0
votes
1answer
46 views

Discrete Math number of multiplications it takes to calculate $x^{15}$

This is in the topic of time complexity and algorithms in my list of problems and I really wanted to figure it out how to take a grip. Here's the problem: Find the number of multiplications needed ...
1
vote
0answers
32 views

Closest pair algorithm in high dimension?

2D case is clear. But with dimensions higher than 2 I should choose a special partitioning hyperplane for the divide and conquer algorithm to get O(n log n). I am confused because to choose this ...
1
vote
1answer
143 views

Detection of self intersection point of curve

What numerical procedure is be adopted to detect self-intersecting parametrized points $ [x(t), y(t) ] $ in $ \mathbb R^2 $ ? Observation : @ roots ( t= 2, t=-1 ) parabola has double value with ...
7
votes
3answers
230 views

Transform polygons into one another?

I am aware that there must be no standard way to achieve this, but I don't know what has been done so far. I feel like I'm missing keywords to investigate further. I have any two 2D polygons $a$ and ...
2
votes
0answers
31 views

What is the most “unbalanced” vector between two given vectors?

Let $\mathbb{R}_+$ be the set of non-negative real numbers. Let $m$ be a positive integer and $\leq_m$ be the product order on $\mathbb{R}_+^m$. Lastly, given a vector $V = (v_1, \dots, v_m) \in ...
1
vote
1answer
82 views

Is there a mathematic expression for this sequence

I want to arrange a sequence from $1$ to $n$, so that every time I (i) remove 1 number and add it to the list; (ii) move the next number to the bottom of the sequence. finally I can get a sequence ...
0
votes
1answer
196 views

sudoku algorithm explanation formula

I'm implementing a sudoku solver using human way algorithm. Which have 3 constraint, different number ini row, cell and box. I googled and I got ...
5
votes
1answer
142 views

Can all math operations be reduced to a sufficiently complex algorithm?

Say I could only perform one operation (addition) from addition I could derive subtraction by adding a negative number. Also, from addition I could derive multiplication, like $ a n $, just add $ a $ ...
0
votes
0answers
59 views

Algorithm-generating algorithm

Is there an algorithm that can create other algorithms based on any number of arguments? For example, a way to determine a function $ f (x) $ from a given input and a given output? I.e. if $ f (2)=4 $ ...
1
vote
1answer
285 views

Give tight asymptotic bounds for the following recurrence. T(n) = 3T(n/3)+log n

Give tight asymptotic bounds for the following recurrence. Justify your answers by working out the details or by appealing to a case of the master theorem $$T(n) = 3T\left(\frac n3\right)+\log(n)$$ ...
1
vote
3answers
62 views

On finding the $n$-th term of an arithmetic progression

Given the common difference $d$, and first term $a$ (say). It is very easy to find the $n$th term of an arithmetic progression. My question is if we are given two common differences say $d_1$ and ...
2
votes
0answers
87 views

Checking if a relation is complete

I have a transitive relation $\subset$ on a (finite and small) set S and a list of pairs $x_i\subset y_i.$ I would like to check if my list is complete in the sense that if $x\subset y$ then there are ...
0
votes
1answer
87 views

Given a set of integers and operators, find if number is obtainable

Let's say I have a set of sequential integers $(x_1,x_2,x_3,x_4,\ldots,x_n)$ and operators $(+,-,\times,/,(,))$ (arithmetic operators and parenthesis). Now say we can have any $t$ numbers from the ...
0
votes
1answer
52 views

How many primes can be represented in JavaScript?

In JavaScript, the largest odd positive number representable is $2^{53}-1$. All integers between 1 and $2^{53}-1$ can be represented without loss of precision. How many prime numbers can be ...
2
votes
1answer
96 views

Max-Cut not optimal solution example?

I currently learning about the Max-Cut problem, but i'm little bit confused about how the 2-approximation algorithm works. The algorithm is as follows: Start with an arbitrary partition Find a ...
4
votes
6answers
845 views

Lottery odds calculated in your head, or pen and paper.

So I am working out the odds for a lottery, picking 4 numbers between 1-35. The equation is: $$\mbox{odds}=\frac{35\cdot 34\cdot 33\cdot 32}{1\cdot 2\cdot 3\cdot 4}=52360$$ Yes, I can work this out ...
3
votes
0answers
36 views

Coefficients of Lagrange resolvent

I'm trying to make sense of some things I read about Galois theory. Let $p$ be a monic polynomial of degree $n$ with known coefficients $a_i$ and unknown roots $x_i$: \begin{alignat*}{2} p(X) &= ...
2
votes
1answer
5k views

The traveling salesman problem is NP-complete Reduction

The traveling salesman problem is NP-complete. Proof: First, we have to prove that TSP belongs to NP. If we want to check a tour for credibility, we check that the tour contains each vertex once. Then ...
4
votes
1answer
43 views

Finding all local $k$-maximums in sequence $a_1, a_2, \ldots a_n$.

For given sequence of numbers $a_1, a_2, \ldots, a_n$ we say that $a_i$ is $k$-local maximum, if $i > k$ and $a_i$ is largest of numbers $a_{i - k}, a_{i-k+1}, \ldots, a_i$. How can we find all ...
0
votes
2answers
58 views

Calculating interaction beween 100 objects with each other.

The other day I was thinking about how many interactions 100 objects would have with each other. By that I mean if we are using a computer to draw the scene with 100 point lights, the total result ...
2
votes
1answer
44 views

Predicting the increase/decrease of number

I have these entries in my database that looks like this: ...
3
votes
1answer
67 views

Finding $m$ largest numbers from union of $k$ sorted lists $A_1, A_2, \ldots, A_k$

We are given $k$ sorted lists $A_1, A_2, \ldots A_k$ with corresponding sizes $n_1, n_2, \ldots n_k$. How can one find $m$ largest elements (numbers) from union of lists $A_1, A_2, \ldots, A_k$? We ...
1
vote
2answers
101 views

Finding median of union of two sorted (ordered) lists

We are given two sorted list of numbers $a_1, a_2, \ldots, a_n$ and $b_1, b_2, \ldots, b_n$. Question is, how to find a median for list $a_1, a_2, \ldots, a_n, b_1, b_2, \ldots, b_n$. Algorithm should ...
0
votes
1answer
47 views

Quicksort-How did we get the relation?

At the proof of the theorem that the expected time of Quicksort is $O(n \log n)$, there is the following sentence: We suppose that the partitions are equally likely, so the possibility that the sizes ...
2
votes
0answers
98 views

Traveling salesman neighborhood

I am solving some TSP problems and i got this one and i am not pretty sure about my answer. By seeing TSP as a formal combinatorial problem, i have that the Feasible solutions $F$ is the set defined ...
10
votes
2answers
324 views

Proving that $T$:$(x_1,…,x_n) \rightarrow (\frac {x_1+x_2}{2},\frac {x_2+x_3}{2},…,\frac {x_n+x_1}{2})$ leads to nonintegral components

Start with $n$ paiwise different integers $x_1,x_2,...,x_n,(n>2)$ and repeat the following step: $T$:$(x_1,...,x_n) \rightarrow (\frac {x_1+x_2}{2},\frac {x_2+x_3}{2},...,\frac {x_n+x_1}{2})$ ...
2
votes
2answers
290 views

Knapsack problem NP-complete

Show that the knapsack problem (Given a sequence of integers $S=i_1, i_2, \dots , i_n$ and an integer $k$, is there a subsequence of $S$ that sums to exactly $k$?) is NP-complete. Hint:Use the exact ...
3
votes
0answers
103 views

a problem about finding an algorithm for a spanning tree in a 3-regular graph

"Consider the connected 3-regular graph G. Find an algorithm that produces a subgraph S of G which is a spanning tree and if you remove S from G then G is divided into some components that each of ...
0
votes
1answer
57 views

Create a map of connected nodes from a list of edges in $O(n^2)$

I have a directed graph. It may or may not be a DAG. I would like to create a map in $O(n^2)$ time to find all nodes that are accessible from a node on a directed path, where $n$ is number of ...
0
votes
0answers
155 views

How do I detect if two polygons overlap each other or not?

I'm developing a game engine. Currently I'm writing the collision detection part. I have to write down an algorithm which detects if two given polygons are overlapping each other or they are separated ...
1
vote
0answers
20 views

Heuristic & Approximation algorithms

I just came to know the definition of r-approximation algorithm. I just want to know whether infinite-approximation algorithm is a heuristic algorithm? Is heuristic algorithm is an ...
0
votes
1answer
60 views

set notation, for indexed family

I'm having trouble to express formally, a trivial algorithm, which is something like this: parameters: a set of students $S$ that have taken a course $c_i$, where course belongs to a of set courses ...
1
vote
1answer
44 views

Questions concerning assumptions to conclude that $\operatorname{P}=\operatorname{NP}$

Suppose you find a reduction from the $k$-vertex-cut problem to the hamiltonian-path problem. In particular, you find an algorithm $A$ that, given the graph $G$ and the number $k$, outputs a ...
2
votes
1answer
34 views

What's the meaning of “reuse space”?

I'm reading this. $\quad \;\;$ What's the meaning of reuse space in here?
1
vote
1answer
59 views

Algorithm for risky investments in banks

I made the following programming question on stack overflow but the users said it was more of math question. Here it is. Situation You start with a fixed amount of money, take it as $\$1000$. You ...
3
votes
5answers
2k views

Does this algorithm find prime numbers only?

I'm writing code to help find prime numbers within a certain range. Here's my general pseudo-code: Iterate through every single number in the range. If the number is 2, 3, 5, or 7; then mark it as a ...
0
votes
1answer
158 views

How to get the maximum and minimum number of length $m$ and the sum of the digits $s$

How to get the maximum and minimum of length $m$ and the sum of the digits $s$ By example: Length: 2 Sum of its digits: 15 Max: 96, Min: 69 Length: 2 Sum of its digits: 2 Max: 20, Min: 11
2
votes
0answers
98 views

How can we find the elements?

I want to describe an algorithm with time complexity $O(m)$ that, given a set $M$ with $m$ numbers and a positive integer $p \leq m$, returns the $p$ closest numbers to the median element of the set ...