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)

1
vote
0answers
46 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 ...
2
votes
2answers
84 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 ...
2
votes
1answer
26 views

Predicting the increase/decrease of number

I have these entries in my database that looks like this: ...
3
votes
1answer
28 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
22 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 ...
1
vote
1answer
58 views

Determine sign of sum of square roots

Problem Given positive square-free integers $r_i$ and non-zero integers $a_i$, is there an algorithm for determining the sign of $\sum_{i=1}^n a_i\sqrt{r_i}$ without calculating approximations for ...
7
votes
1answer
121 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})$ ...
0
votes
1answer
39 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 ...
1
vote
1answer
52 views

Expected time of Quicksort

I am reading the proof of the theorem: The Algorithm Quicksort sorts a sequence of $n$ elements in $O(n \log n)$ expected time. The proof is this: For simplicity in the timing analysis assume ...
4
votes
1answer
68 views

Checking whether a line segment is above another in $\mathbb{R}^3$

There are two non parallel line segments $U$ and $V$ in $\mathbb{R}^3$, each given by their two end points $u_0, u_1$ and $v_0, v_1$, such that if they are projected into $\mathbb{R}^2$ by their $x$ ...
-7
votes
0answers
63 views

hard question, please help [on hold]

11) Assume a sorted array (A) of size n. Propose an algorithm for finding two elements x and y in A that minimize |x-y|. Your algorithm should run in O(n) time for full credit. (Note: |x-y| represents ...
-1
votes
0answers
22 views

Algorithm for vector space transformation [on hold]

In my text book I've got an example which is as follows: Create an algorithm which calculates coordinates of a point after a space transformation took place. Transformations may be scaling or ...
3
votes
0answers
60 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 ...
1
vote
1answer
459 views

Using BFS or DFS to determine the connectivity in a non connected graph?

How can i design an algorithm using BFS or DFS algorithms in order to determine the connected components of a non connected graph, the algorithm must be able to denote the set of vertices of each ...
0
votes
1answer
21 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
1answer
33 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 ...
0
votes
0answers
27 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
1answer
29 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 ...
1
vote
0answers
12 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
0answers
10 views

Divide the segment into parts with gaussian length distribution

I want to divide the segment having length 2a into N parts with normally distributed lengths. Is there any simple algorithm to do so? i.e how to find the coordinate of i-th point ?
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 ...
2
votes
1answer
22 views

What's the meaning of “reuse space”?

I'm reading this. $\quad \;\;$ What's the meaning of reuse space in here?
2
votes
1answer
48 views
+50

Applying MCMC Metropolis algorithm

I'm interested in all possible paths (on the grid $\mathbb{N}^2 $) that goes from $ (0,0) $ to $ (n, n) $. At each step there are two possibilities: go right or go up. The path is a sequence $ ...
1
vote
1answer
39 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 ...
0
votes
1answer
23 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
38 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 ...
1
vote
1answer
54 views

How does the function work? [closed]

Could you explain me the function of the following two algorithms? ...
0
votes
1answer
33 views

Number pattern prediction algorithm [duplicate]

Since childhood we are all familiar with the task of predicting the next number in a sequence. From something simple like, $2,4,6,...$ and $4,9,25,...$ to something more complex like, ...
1
vote
1answer
22 views

Las Vegas Algorithms

In some notes i'm reading it says that the definition of a Las Vegas Algorithm is An algorithm which always outputs the correct answer but has unbounded running time, with the expected running time ...
4
votes
2answers
568 views

Card Shuffling [SPOJ]

The original question is posted on SPOJ, and included below: Here is an algorithm for shuffling N cards: 1) The cards are divided into K equal piles, where K is a factor of N. 2) The ...
2
votes
3answers
25 views
0
votes
1answer
19 views

A language $L$ is polynomially transformable to $L_0$

Could someone explain to me the following definition?? A language $L$ is polynomially transformable to $L_0$ if there is a deterministic polynomial-time-bounded Turing machine $M$ which will convert ...
5
votes
1answer
49 views

Special case of Minimum Spanning Tree

I have been bashing my head trying to solve the following problem for the past two days, it is a review question in preparation for my exam and I assume something similar will be on it. The problem ...
0
votes
0answers
27 views

Two convex polygon intersection from set of m convex polygons with total n vertices

I have a set of m convex polygons $(p_1,p_2, \ldots p_m)$. $n_i$ is the number of vertices in $p_i$. $\sum_{i=1}^{m} n_i = n$. Each polygon has vertices listed in anti-clockwise direction, starting ...
1
vote
1answer
26 views

Find every possible distribution of the x elements considering a constraint on one of them

Considering a number r of triplets { a, c, i } I'd like to know which procedure / math field should I use to calculate every ...
0
votes
1answer
11 views

wondering about the greedy algorithm to the set cover problem

i'm currently learning about the Set-Cover problem and i have a question about it. Using the greedy algorithm to solve this, some proof says: Since the optimal solution uses k sets, there must some ...
2
votes
1answer
27 views

best possible algorithm for finding out an ordering $i_1i_2..i_n$ such that $b_{i_k}=a_{i_k+1}$ for $k=1$ to $n-1$

Suppose that I have a given set of items $S$. Now I have been given $n$ sequences made using the items in $S$ like $$a_1(...)b_1, a_2(...)b_2,...a_n(...)b_n$$ The sequences have lengths ...
0
votes
3answers
52 views

How to find upper and lower bound without using formula?

I am studying discrete math for tomorrow's exam and got stuck in the below question. I tried to google it and couldn't find anything usefull. Prove the following sum is theta(n^2) (we have to find ...
2
votes
1answer
27 views

NP Solvable in Polynomial Time

I just took an exam and am a little curious about this question (it may not be verbatim, but the idea is clear): TRUE/FALSE: If an NP complete problem can be solved in polynomial time, then P = NP. ...
3
votes
2answers
576 views

maximum flow ford-fulkerson analysis

I am reading about maximum flows in Introduction to algorithms by Cormen etc. Ford-Fulkerson algorithm is given below. FORD-FULKERSON(G, s, t) ...
5
votes
3answers
971 views

Calculate Runge-Kutta order 4's order of error experimentally

The Problem Use the order 4 Runge-Kutta method to solve the differential equation $ \frac{\partial^2 y}{\partial t^2} = -g + \beta e^{-y/\alpha }*\left | \frac{\partial y}{\partial t} \right |^{2} $ ...
10
votes
2answers
820 views

Algorithm(s) for computing an elementary symmetric polynomial

I've run into an application where I need to compute a bunch of elementary symmetric polynomials. It is trivial to compute a sum or product of quantities, of course, so my concern is with computing ...
0
votes
0answers
30 views

Show that it is NP-complete [closed]

Show that the problem of determining whether a regular expression over the alphabet $\{0\}$ does not denote $0^*$ is NP-complete. Could you give me some hints how I could do that??
3
votes
1answer
99 views

What kind of edge do we have?

In order to find the kind of the edges of a graph, at which we applied the Depth-first search algorithm, we could use this: $$\begin{bmatrix} \text{ tree edges: } x \to y & [d[y],f[y]] \subset ...
1
vote
1answer
270 views

How to get numbers with distinct digits within some range?

I have a little program I'm working on for my project (a simple practice in school), part of the program is that it should receive input composed of an array of 7 digit (or less) numbers which should ...
1
vote
0answers
10 views

Asymptotic Notations Iterative Method for Solving Recurrences

Recurrence T(n)= T(n^1\2) + O(lg(lg(n))) The solution suggests substituting m = lg(n) So the recurrence becomes S(m)= S(m\2) + O(lg(lg(m))) Then solving using iterative method for solvng ...
0
votes
1answer
45 views

Find smallest $x$ such that $a^x \equiv b \bmod p$

Problem: How do we find smallest $x$ such that $a^x \equiv b \bmod p$, where $p$ is a prime and $1 \le b,a \le p$ and $a$, $b$, and $p$ are given and fixed. If there is no such $x$, how do we check ...
0
votes
1answer
10 views

Efficient algorithm for slightly generalized attribution problem

I have what I believe is an attribution problem: Given an $m \times n$ matrix, I need to select $p = \min\{m,n\}$ elements maximizing their sum such that they do not share a row or column. More ...
1
vote
2answers
46 views

Avoiding extraneous solutions

When solving quadratic equations like $\sqrt{x+1} + \sqrt{x-1} = \sqrt{2x + 1}$ we are told to solve naively, for example we would get $x \in \{\frac{-\sqrt{5}}{2},\frac{\sqrt{5}}{2}\}$, even though ...
0
votes
1answer
29 views

Shifting Nth Root Algorithm

Does anyone have a very simple dumbed-down explanation of the shifting nth root algorithm on paper (finding an nth root with a method similar to long division)? I know very basic addition, ...