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)

0
votes
1answer
37 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
0answers
33 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 ...
7
votes
1answer
115 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
1answer
55 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 ...
-7
votes
0answers
61 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
53 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
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
0answers
26 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
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
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 ...
1
vote
1answer
28 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 ...
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 ?
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?
1
vote
1answer
38 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
22 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
37 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? [on hold]

Could you explain me the function of the following two algorithms? ...
1
vote
1answer
51 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 ...
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 ...
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 ...
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. ...
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 ...
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??
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, ...
4
votes
2answers
91 views

Number of solutions of a simple equation

Problem How to count the number of distinct integer solutions $(x_1,x_2,\dots,x_n)$ of the equations like : $$|x_1| + |x_2| + \cdots + |x_n| = d $$ the count gives the number of coordinate points ...
2
votes
1answer
46 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 $ ...
3
votes
1answer
49 views

Knuth's algorithm for Mastermind question

I'm reading about Knuth's algorithm to solve the mastermind game, so I've looked in wikipedia and read the pseudo-code (http://en.wikipedia.org/wiki/Mastermind_(board_game)#Five-guess_algorithm). I ...
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 ...
3
votes
2answers
48 views

Objects into two bags puzzle

I found a maths puzzle somewhere and a part of it as below: Kelly wants to place n objects $a_1,a_2,⋅⋅⋅,a_n$ into two bags. For each $i=1,2,⋅⋅⋅,n$, the weight of $a_i$ is $w_i$ kilograms. The ...
1
vote
0answers
23 views

How quickly can we multiply hypercomplexes?

If we start with a hypercomplex number with $2^n$ entries, how quickly can we multiply it by another hypercomplex number, modulo a prime? EXAMPLE For example, with $n=1$, we get the complex numbers. ...
0
votes
2answers
30 views

Constructing a random sampler from a random coin (algorithm)

This is a problem from Introduction to Algorithms by Cormen et. al. Assume that we can do coin-flips. The problem is to come up with an algorithm that can uniformly sample from the interval $[1,n]$. ...
0
votes
2answers
48 views

Hexagonal Tessellation on a sphere

I want to detect collision of a sphere with another object and to find out(show) the deformation of the sphere. I have come to know that hexagon(regular)tessellation of a sphere is the most ...
1
vote
1answer
23 views

Computable set and its first projection

I got stuck at one of the problems, related to the algorithms theory. How to build a computable set $B \subset N$ so that the first projecton of it (defined as $pr_{1}= \{ x | \exists y (x, y) \in B ...
0
votes
0answers
65 views

Maximum XOR of a set with an integer [closed]

I have to find XOR of a number say $K$ with all the subsets of set $P$ such that $P$ contains all non zero integers (can contain at most 1000 integers), so that my result of XOR should be the maximum. ...
2
votes
1answer
45 views

Weights - Objects into bags puzzle

I found a maths puzzle somewhere and a part of it as below: Kelly wants to place n objects $a_1 , a_2 , ··· , a_n$ into $k > 1$ bags. For each $i = 1 , 2 , ··· , n $, the weight of $a_i$ is $w_i$ ...
1
vote
1answer
31 views

How to determine if the given points form a convex irregular Hexagon.

Say I have a collection of points (x,y). From the given points, I want to determine if it forms a convex irregular Hexagon. My goal is to determine that the points I have gathered form an irregular ...
0
votes
1answer
50 views

sum of mutually exclusive subset

I have to determine that it is possible or not that for a given X and K we can partition a set X into non empty mutually exclusive K subset such that sum of each subset is equal. I have tried a lot. ...
1
vote
1answer
49 views

Is there a general method to find if ideal is maximal

Is there an algorithm to determine if we have been given a ring $A$ and its ideal $I$, whether or not $I$ is a maximal ideal of $A$? I found that sometimes proving that ideal is maximal might be ...
1
vote
0answers
88 views

Counting arrays problem [closed]

Given N, M and D I need to count how many sequence of N elements a[1],a[2].....a[n] can be formed which satisfy these 2 conditions : Each element is between 1 ≤ Ai ≤ M. Greatest common divisor of ...