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)

2
votes
0answers
31 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 ...
-8
votes
0answers
48 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 ...
-2
votes
0answers
19 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
39 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
19 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
24 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
11 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
27 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
9 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
20 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
20 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
34 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
53 views

How does the function work? [on hold]

Could you explain me the function of the following two algorithms? ...
1
vote
1answer
42 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
31 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
48 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
29 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
90 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
43 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
48 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 ...
0
votes
0answers
20 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
47 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
64 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
30 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 ...
2
votes
1answer
23 views

Newton method why the error is proportional to the square for the error of the last one?

We have learned that the Newton method is used to solve different equations. As I know, this method is iterative, which means that using an estimate point and using a loop, we can get closer and ...
0
votes
1answer
20 views

How to check if a number say 'k' can be formed by adding any number of elements in set/array A?

It is known to me that element 'k' is less than the sum of all elements in the set/array. I know the solution if 'k' can be formed adding any two numbers or three numbers in the set. There are well ...
1
vote
1answer
30 views

Discrete Math: Combinatorics and recursion

Let S be a set of size 37, and let x, y, and z be three distinct elements of S. How many subsets of S are there that contain x and y, but do not contain z? (a) $2^{33}$ (b) $2^{34}$ (c) $2^{35}$ ...