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
1answer
66 views

Is this a valid example of a poset?

I am trying to understand better the basic concepts of partially ordered sets, and tried my own examples by using modular-arithmetic. For this, I tried to define an algorithm to order integers, here ...
1
vote
0answers
64 views

Complexity of $\gcd$ algorithm

I'm reading a paper in which it's used the fact that a gcd computation of two numbers $(a,n)$, can be done in $O(\log n)$ time, and $[1]$ is referenced for the result. I haven't found that specific ...
0
votes
2answers
46 views

Complexity of recursive algorithm.

An algorithm solves problems of size $n$ by recursively solving two subproblems of size $n - 1$ and then combining the solutions in constant time. What is the algorithms running time? Assume $ ...
0
votes
0answers
152 views

Closest pair points algorithm with Manhattan Distance

According to the solution of closet pair (euclid distance) with divide and conquer algorithm during merge algorithm we prove that for each point at distance d (minimum distance of two different sub ...
2
votes
2answers
132 views

Difference between two solution for Closest pair of points

I'm having a problem with understanding the difference between two solution of of closet pair of point in plane. According to the the Wikipedia when we are merging two planes we need to check at most ...
0
votes
2answers
81 views

Asymptotic Algorithm General Approach to Finding $\Theta$ Bound

I'm working on the following asymptotic algorithm bounds problem Find a $\Theta$ bound for $f(n) = \frac{n^2}{2} - \frac{n}{2}$ So I could find the big-$O$ bound fairly easily $$ 0 \leq ...
0
votes
0answers
27 views

How do I normalize a set of numbers for display on a graph?

I'm trying to display rainfall precipitation intensity on a graph. I have a set of 60 data points, where 0.002 corresponds to drizzle and 0.4 corresponds to heavy rain. But if I just chart that data, ...
3
votes
1answer
87 views

How does $\sum p(k)$ grow asymptotically where $p(k)$ is the smallest prime factor of $k$?

Define $p(k)$ to be the smallest prime $p$ dividing $k$. Define $A(n)=\sum_{k=2}^n p(k)$. How does $A(n)$ grow asymptotically? I am wondering how exactly the naive algorithm for finding all primes ...
0
votes
0answers
36 views

Arithmetic progressions in subset

Let $S$ be a subset of $\{1,\dots,n\}$. Does there exist a good algorithm to find a partition of $S$ into "reasonably long" arithmetic progressions? Many thanks!
2
votes
0answers
28 views

Binary search where the computer may lie upto $k$ times

We are performing a binary search on $n$ elements where the answer to a comparison may be wrong upto $k$ times. What is the time complexity of finding the right element in terms of $n$ and $k$? The ...
1
vote
1answer
308 views

Alternative algorithms for finding the longest path in Directed Acyclic Graphs

I am currently working on the method of finding the longest path in Directed Acyclic Graphs (DAC's). I wonder if there is another way to do it other than topological sorting. Is there any chance using ...
0
votes
2answers
114 views

Better Gaussian Elimination for solving $Ax=b$ [closed]

We know that Gaussian Elimination is very popular method to resolve $Ax=b$. Does anyone know better method than Gaussian Elimination in term of time complexity? Second question,if I assume that A is ...
0
votes
1answer
48 views

In the general number field sieve, do we need to know whether powers of elements in the algebraic factor base divide an element $a+b\theta$?

I'm reading this paper trying to implement the number field sieve. http://citeseerx.ist.psu.edu/viewdoc/download?rep=rep1&type=pdf&doi=10.1.1.219.2389 Let $\theta$ be the root of some monic ...
1
vote
1answer
129 views

NP HARD Problem Longest Path in Graph

I got stuck with this problem since the whole day. When we are finding the longest path in a graph we first do topological sorting and then check the path of adjacent vertices and keep upgrading ...
1
vote
0answers
65 views

How can I get the maximum score without iterating all possibilities?

Suppose I have a set of number $S = \{0,\ldots,n-1\}$. I have to find a partition $$P = {\arg \max}_{P \in \mathcal{P} \text{ and } P \text{ is a partition}} \operatorname{score}(P)$$ A partition ...
2
votes
2answers
151 views

Is this an NP-Complete problem? (unweighted & undirected graph)

G is an unweighted, undirected graph. Then, I cannot prove that [deciding whether G has a path of length greater than k] is NP-Complete. How can I show whether the algorithm is NP-complete or not?
1
vote
1answer
155 views

Algorithm to find max no. of nodes that can be visited

Given an undirected non-weighted graph edges. '1#2', '2#3', '1#11', '3#11', '4#11', '4#5', '5#6', '5#7', '6#7', '4#12', '8#12', '9#12', '8#10', '9#10', '8#9' where ...
1
vote
1answer
175 views

Searching Algorithm

A company database has 10,000 customers sorted by last name, 20% of whom are known to be good customers. When looking up a customer’s record in the database, the good customers account for 60%. Two ...
0
votes
1answer
38 views

queuing problem, related to marriage algorithm

Say we have an nxn matrix and for every entry a_{ij}, it equals 1 if flight j starts after flight i ends. Otherwise it is 0. Suppose the largest matching contains M marriages (i.e. 1's in nxn matrix ...
3
votes
1answer
90 views

Metropolis Hastings

So I have seen the Metropolis Hastings algorithm written 2 ways, and I don't quite understand how they can be equivalent: The first way is by defining the 'acceptance probability' as: ...
3
votes
2answers
430 views

Weakly connected graph test

What is the right algorithm for testing whether the graph is "weakly connected"? The theory says: Oriented graph $G=(V,E)$ is weakly connected graph if and only if for every two vertices $u,v \in ...
0
votes
2answers
130 views

On 2- player game.

Consider the following 2-player game: you start with n tokens on a table, in a single pile. Players alternate turns. On a player's turn, they must choose one pile of their choice, and split it into ...
0
votes
1answer
29 views

How many pickups $K$ should I do to have a $p$% of probability of picking up a divisor of $n$ (if exists) in the interval $[2..\lfloor n/2\rfloor]$?

I am trying to understand if it makes sense an algorithm to decide if a given number $n$ is possibly prime or not by using the divisor function bound defined by professor Jeffrey Lagarias as: ...
2
votes
1answer
55 views

Average case complexity for checking if list is sorted

Consider the obvious algorithm for checking whether a list of integers is sorted: start at the beginning of the list, and scan along until we first find a successive pair of elements that is ...
0
votes
1answer
70 views

Greedy choice property

There are two versions of the Knapsack problem, the integer and the fractional one. The difference between the integer and the fractional version of the Knapsack problem is the following: At the ...
1
vote
1answer
60 views

Find pairs of side integers for a given hypothenuse number so it is Pythagorean Triple

I am trying to find all pairs of side integers (a, b) for a given hypothenuse number n so that (a, b, n) is a Pythagorean triple, i.e.,$ a^2 + b^2 = n^2$ The approach i am using is Sorting the ...
1
vote
1answer
33 views

Summand Evaluation Help

I'm a student currently in an algorithms and data structures class, and my Calculus is unfortunately quite shaky when it comes to summations. As such, I'm struggling to evaluate one of the sum that ...
0
votes
1answer
48 views

Proof approach: A 7x7 matrix with 15 ones can allow at least three marriages

This is quite difficult to prove imho with regards to Hall's Marriage Algorithm I can visualize a number of scenarios that work (i.e. put ones from the first entry to the fifteenth, or across ...
3
votes
1answer
59 views

Counting the number of integers $i$ such that $\sigma(i)$ is even.

Define $\sigma(i)$ to be the sum of all the divisors of $i$. For example, $σ(24) = 1+2+3+4+6+8+12+24 = 60$. Given an integer $n$, how can we count the number of integers $i$, less than or equal to ...
-1
votes
1answer
110 views

Application of the Knapsack Algorithm

I want to apply the Knapsack algorithm at the following: n = 4 (# of elements) W = 5 (max weight) Elements (weight, benefit): (2,3), (3,4), (4,5), (5,6) The ...
1
vote
0answers
71 views

The algorithm yields optimal ternary codes

Steps to build Huffman Tree Input is array of unique characters along with their frequency of occurrences and output is Huffman Tree. Create a leaf node for each unique character and build a min ...
2
votes
1answer
52 views

How to remove fields from sudoku puzzle in such way to assure there's still only 1 solution?

I'm trying to create a Sudoku puzzle (programatically, if that matters). Here's how I do it. STEP 1: Creating an initial set, with unique solution: 123456789 456789123 789123456 ...etc... STEP 2: ...
0
votes
1answer
84 views

Algorithm to distribute numbers so that average of sets is closest to total average

Given a collection of N non-unique decimal numbers d1, d2, d3 ... dN whose average is μT. Assume we distribute d1, d2, d3 ... dN across K sets with sizes s1, s2 ... sK and therefore: $$\sum_{i=1}^K ...
0
votes
1answer
35 views

Trigonometry to radially spread points around a center

I'm having a basic Math problem. I have number of point collections, each with a different amount of points. Let's say one collection has five points and I want them to spread radially around a ...
0
votes
1answer
61 views

3 rotation values to work out rotation in degrees

I am currently working with the Oculus headset and dealing with the Z axis. With the software I have, the values I can retrieve are limited and I was hoping someone could help me find a solution to ...
-1
votes
2answers
360 views

What is the algorithm to add binary numbers with boolean operations? [closed]

What is the algorithm to add up two binary numbers using only boolean operations (negation, conjunction, disjunction) in linear time? Also the program flow needs to be "linear" as well, meaning there ...
0
votes
0answers
36 views

How to solve constrained ode problem

Currently I'm facing question in which let's say I have 3 coupled eqn. \begin{align} x = f(x', z', y', t) \\ y = f(x', y', z', t) \\ z = f(x', y', z', t) \\ \end{align} There is initial ...
0
votes
2answers
94 views

what is the complexity of this type of algorithms (loop bounded)?

I have an algorithm which contains only the instructions of type: $X_i=X_j$ $X_i=X_i+1$ $\text{while }(X_i\le N)\text{ do }\{C\}$ where $C$ is another instruction $N$ is a global constant and ...
0
votes
1answer
20 views

Weighted Random Selection

I read a blog post about a simple algorithm to select a random item from a list, certain items in the list were weighted to increase the chance of it being selected. Add up all the weights. Pick a ...
1
vote
1answer
222 views

Minimize the squared dot product of two specific vectors

Do you think there exists a efficient algorithm(non brute-force) for the following problem. I search the optimal solution for the following problem: Given a vector $u=(u_1, u_2,..., u_k)^T$ with ...
0
votes
1answer
37 views

What is the lower bound for an algorithm that reconstructs a permutation?

In this challenge on codegolf.SE, one has to reconstruct a permutation $p$ of a vector of length $n$ given only a function $P\colon\{0,1\}^n\mapsto\{0,1\}^n$ which applies $p$ to a vector of booleans, ...
0
votes
1answer
97 views

Finding minimum paths in Graph theory

A Canadian postman, rather than returning to the post office $(p)$ after delivering mail along every street in town, wishes to return straight home $(h)$. Let $G$ be a connected graph and $p , h $ ...
0
votes
1answer
43 views

Design an algorithm - Median, computer science

I was wondering if this question belongs here or on StackOverflow, but it is a question of mathematical nature so this seems more appropriate. We have an array $S$ of $n$ different numbers ...
0
votes
1answer
59 views

improved segmented sieve of erastothenes complexity

I improved the segmented sieve of erastothenes , my algorithm doesnt repeat the multiples of primes using the equation $p^{2}_{n}p_{j}+2p_{n}p_{j} \times c =N$ wich shows when at least two multiples ...
0
votes
1answer
37 views

How to “layer” two scale adjustments in a formula?

First: I apologize for the title, I truly don't know what the correct terms to describe my problem are. If I receive suggestions for a more appropriate title or learn some new terms I will revise it. ...
1
vote
1answer
41 views

Why is the time complexity of factorization $2^n$?

Can somebody explain to me why, given the factor value N, the time complexity of a factorization algorithm (N / 2, N / 3, N / 4, ...) is $2^n$ rather than n?
3
votes
0answers
57 views

Check if a point is inside a rotated 2D NACA 0012 airfoil

I've already checked the rotated rectangle problem but this is (I think!) a little more complicated. I have a CFD calculation of a 2D NACA 0012 airfoil and I need to test if a point is inside the ...
4
votes
1answer
66 views

Infine Sequence ${1, 3, 2, 3, 1}$

I have an infine sequence where at the end of which the ones are written. Then till infinity we shall do the next procedure: for each segment with ends a and b (inside which the numbers are absent) we ...
-5
votes
1answer
251 views

Are the propositions right?

I want to choose if the following propositions are true or false and justify the reason for the choice. Polynomial: good, exponential: bad. Radix Sort works correctly if we use any right sorting ...
1
vote
1answer
85 views

Count connected components after $M$ marbles removed

There are $N$ marbles in a line, numbered $1$ through $N$ from left to right. We need to count numbers of ways to remove exactly $M$ marbles such that there are exactly $C$ remaining connected ...