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
1answer
72 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
32 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!
-1
votes
5answers
385 views

Count increasing sequences [closed]

Given three positive integers $N, L $ and $R$, we need to find the number of non-decreasing sequences of size at least $1$ and at most $N$, such that each element of the sequence lies between $L$ and ...
2
votes
0answers
21 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
69 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
0answers
26 views

Aligning $2$ Bi-partitite graphs

I am working on finding way to find similarity between nodes in $2$ different bipartite graphs. These $2$ graphs represents links in $2$ different domains. Are there algorithms available which can ...
0
votes
2answers
53 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
39 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
30 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
1answer
55 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
86 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
74 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
76 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
29 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 ...
0
votes
0answers
41 views

binary search worst case for a set database of entries some good some bad

A database has 10,000 sorted entries, 20% known to be good. When looking up a record in the database, the good entries account for 60%. Two design options are considered to store the data in the ...
2
votes
1answer
36 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: ...
0
votes
0answers
14 views

Understanding Postnumbering of DFS

I do not understand how these slides managed to get the postnum table. I would have thought that postnum tells us the order each node was visited during the process of making the DFS tree. I can ...
0
votes
0answers
27 views

Graph Theory: Describing the maximum weight spanning tree

The question states, "Describe an algorithm for finding a spanning tree of maximum weight for a given weighted graph. Prove that your algorithm works." I researched and what I only know so far is ...
2
votes
2answers
35 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
0answers
19 views

How did we get the relation?

The fractional knapsack has the greedy choice property. Proof: Let`s consider that the ratio $\frac{V°}{w°}$ is maximal. This assumption implies that $$\frac{V°}{w°}\geq \frac{v}{w}\text{ for ...
-1
votes
2answers
51 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
18 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
25 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
29 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
0answers
19 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 ...
0
votes
1answer
25 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
0answers
20 views

understanding articulation points

I am learning about articulation points, however I have a hard time understanding the algorithm used to find the points. I found these in my notes. 1) Carry out a depth-first search in G, starting ...
0
votes
0answers
40 views

Why does this matematical pattern occurs here?

The actual question goes like this A room has N (1 to N inclusive) bulbs and N switches. N people go in one by one. 1st person goes in and toggles none of the switches. 2nd person goes in and ...
0
votes
0answers
7 views

How to find a strictly increasing sequence of words $(t_i)_{0\leq i\leq n}$ of maximum length ?

Let $L=\{0,1\}^*$ be the set of all words consisting of $0$ or $1$, we define an order in $L$ by: $$\begin{align}\forall (x,y)\in L^2 && \big( x\leq y&&\Leftrightarrow y=x\text{ or ...
0
votes
1answer
37 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
45 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 ...
0
votes
0answers
78 views

The problem of making change for $n$ using the fewest number of coins

Consider the problem of making change for $n$ cents using the fewest number of coins. Assume that each coin’s value is an integer. Describe a greedy algorithm to make change consisting of quarters ...
-2
votes
1answer
76 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
37 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 ...
-1
votes
1answer
54 views

Knapsack Problem [closed]

There are two versions of the Knapsack problem, the integer and the fractional one. Could you describe them to me?? Which are the differences?? With what type of programming do we solve them?? ...
2
votes
1answer
36 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
55 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
13 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
0answers
25 views

Minimization according to a function

I am working on a simulation project on Matlab/Simulink and I would like to minimize the following function : $min_f \int_{t=0}^{t_1} m(A(t) + \int_{y=0}^{t} B(y) f(y) dy) dt $ With $m : \Bbb{R}^6 ...
0
votes
0answers
32 views

Minimax in the context of Knuth's algorithm for mastermind

I have several questions about using minimax to find a next best guess for knuth's 5 guess algorithm for mastermind: For each possible guess, that is, any unused code of the 1296 not just those in ...
0
votes
1answer
32 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 ...
0
votes
0answers
9 views

Clarification on a rasterizing curve drawing algorithm

The algorithm in question is described in this paper. The author describes the general approach to plotting a curve (page 10): ...
-1
votes
2answers
94 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
17 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
56 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
0answers
9 views

Function to increase entropy for a specific number and seed and reduce it for the rest

Hello I think I am wording the title correctly. I am looking for a function / algorithm that can increase the variability or entropy of a specific number and reducing it for the rest. The function can ...
0
votes
1answer
17 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
49 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
0answers
35 views

On Tree- Doubling Algorithm

Use the Tree-Doubling Algorithm, starting the Euler tour and the Hamilton cycle at the vertex a and resolving any ties alphabetically. Need help to this question. Thanking you.
0
votes
1answer
16 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, ...