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
1answer
21 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
54 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
53 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
39 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
71 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
37 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
29 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
9 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
18 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
28 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
18 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
46 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
16 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
24 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
0answers
16 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
18 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
24 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
15 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
37 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
31 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
55 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
35 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
45 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
35 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
47 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
11 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
20 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
21 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
27 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): ...
-2
votes
2answers
82 views

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

What is the algorithm to add up 2 binary numbers when the basis is {negation, conjunction, disjunction} in linear time? Also the program needs to be linear as well, meaning there can only be ...
0
votes
0answers
16 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
45 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
7 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
42 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
31 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.
-1
votes
0answers
32 views

The minimum number of machines to install the software on to clean the entire network

A Worm has affected all computers in a companies LAN network. The worm removal software is licensed in such a way that only adjacent machines (connected directly by a cable) can share a copy of the ...
0
votes
1answer
15 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
43 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
28 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
39 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
32 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
36 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
25 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 ...
3
votes
1answer
58 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 ...