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
15 views

Explanation of division/reduction in a binary Galois Field using bit-shifts

I've seen a lot of algorithms reducing the result of a multiplication in a Binary Field by using only bit-shifts and XOR. The number of positions to shift seems to be derived from the polynomial, but ...
0
votes
1answer
24 views

What is the formal name of this problem?

I'm doing an assignment and I'm having trouble with this question, could anyone give me the formal name of the problem described so I can research it better? The task is to move a player along a path ...
0
votes
2answers
21 views

Help with algorithm

How can I prove that is true/false $$ f(n)+g(n)=O(f(n)\cdot g(n)) Where f(n),g(n) > 0 $$ I think that if $f(n)=\frac{1}{n}$ and $g(n)=n$ it can't be true but I don't know how to prove it.
0
votes
0answers
13 views

Find an algorithim for parallel time sharing

I am trying to come up with an algorithm to calculate the time spent on multiple tasks, where there is the potential that they can run in parallel. The problem can be summarized as follows: A CPU is ...
1
vote
1answer
24 views

Combinatorics problem

I am trying to solve this question, my solution involves solving a combinatorial problem as follows : Number of arrangements of exactly k distinct elements in n slots such that each one of the ...
0
votes
0answers
40 views

Approximation for fewest incompatibilities in a task scheduling selection algorithm

Suppose you have a task selection algorithm to select the largest subset of tasks that do no overlap. The greedy algorithm that selects tasks based on their finish time will always produce an optimal ...
1
vote
1answer
17 views

Trying to find polynomial-time algorithms for knapsack-like problems

Consider two related problems: You have $n$ cannisters that must go into $m$ trucks that can each carry $k$ cannisters. You require that no truck becomes overloaded, and for each cannister, there is ...
0
votes
1answer
24 views

How can we show that 3-dimensional matching $\le_p$ exact cover?

In exact cover, we're given some universe of objects and subsets on those objects, and we want to know if a set of the subsets can cover the whole universe such that all selected subsets are pairwise ...
0
votes
1answer
17 views

Calculating nCr mod M using inverse multiplicative factors

The method used for calculating nCr mod M is: fact[n] = n * fact[n-1] % M ifact[n] = modular_inverse(n) * ifact[n-1] % M And then nCr is calculated as ...
0
votes
0answers
7 views

Will postorder traversal on a reversed graph provide the same result as a reversed postorder traversal on a usual graph

Will postorder traversal of a reversed graph provide the same result as a reversed postorder traversal on a usual graph? I am trying to understand strong components search algorithm (on coursera) and ...
0
votes
2answers
25 views

Partitioning graph edges into two cycleless sets

Given a directed graph $G=\left(V,E\right)$, provide an algorithm that partitions $E$ into two disjoints sets $E_1,E_2$ such that $E=E_1\cup E_2$ and $G(V,E_1)$, $G(V,E_2)$ have no cycles. The ...
3
votes
2answers
140 views

Need formal mathematical definition of this concept

Assume we have a function $y=f(x)$ that is $\textit{C}^\infty$ and the function has a number of local maximums. Assume there are $k$ such maximums $\{m_1, m_2, m_3, \ldots , m_k\}$ where $f'(m_i)=0$. ...
1
vote
2answers
122 views

Algorithm: Scheduling of Overlapping Intervals

I'm reviewing algorithms, and I've come across this problem. At first, it seemed like an interval scheduling problem to me, but now I think it is a dynamic programming problem. I'm not sure how to ...
0
votes
1answer
39 views

search algorithms performance

A company database has 10,000 customers sorted by last name, 20% of whom are known to be good customers. Under typical usage of this database, 60% of lookups are for the good customers. Two design ...
0
votes
0answers
127 views

Devise an algorithm that find all terms of a finite sequence of integers that are greater than the sum of all previous terms in the sequence.

Devise an algorithm that find all terms of a finite sequence of integers that are greater than the sum of all previous terms in the sequence. I'm not sure how to approach this.
0
votes
1answer
24 views

How to find the largest connected component of an undirected graph using its incidence matrix?

Usually, finding the largest connected component of a graph requires a DFS/BFS over all vertices to find the components, and then selecting the largest one found. Suppose I only have an incidence ...
0
votes
1answer
59 views

Increase by one all edges, Min-Cut, changes or not?

My Friends, as i ask a new question recently, Increase by one, Shortest path, changes the edges or not? i want to ask a related question as a new post Suppose we have a Graph G in which weight ...
0
votes
2answers
37 views

Increase by one, Shortest path, changes the edges or not?

as i read the following text : "Let P be a shortest path from some vertex s to some other vertex t in a graph. If the weight of each edge in the graph is increased by one, P will still be a shortest ...
0
votes
1answer
31 views

Simple Turing Machine

Having a bit of trouble designing a turing-machine which recognizes the following language. The alphabet is $\Sigma$ = {a,b,c}. $$ L_2 = \{wcw^R | w \epsilon \{a,b\}^*\} $$ The part which messes ...
0
votes
1answer
22 views

cubic integral roots

I am trying to find the integral roots (if they exist) of the following polynomial. Additionally, it would be helpful if someone could explain an algorithmic approach to solving this. $$ f(x) = 2x^3 ...
4
votes
3answers
111 views

Using up letters on a refrigerator is NP-complete

You spend some time with your preschool-age daughter trying to use up all of the magnet letters on the refrigerator to spell words that she knows. Formally, you have a set of letters and you are ...
5
votes
1answer
75 views

Constrained Optimizatoin: The Frank-Wolfe Method

A general convex optimization problem is framed as such: $$\min f(x) : x \in \Omega$$ where $\Omega$ is convex. The Frank-Wolfe method seeks a feasible descent direction $d_k$ (i.e. $x_k + d_k \in ...
8
votes
1answer
345 views

Minimal number of rectangles that cover a set of adjacent unit squares

Suppose I have an arbitrary number of adjacent 1x1 squares on a grid (Adjacent defined as "each square shares at least one side with another"). I'm looking for a good way to find the minimal number of ...
1
vote
1answer
52 views

Magic Squares with Random Numbers

I'm trying to solve a problem related to Magic Squares. The thing is: Given a list of n numbers, I need to answer if it is possible to create a magic square with them. These numbers are random (no ...
2
votes
2answers
25 views

Rounding to arbitrary precision

I am dealing with values that come from a measuring instrument. The instrument itself has a certain precision, i. e. it is limited in the resolution of values it can measure. Let's assume the ...
0
votes
1answer
21 views

Merging of height balanced trees

$H_1$ and $H_2$ are two height balanced trees. How can they be merged such the time required for merging them is $O(\log n_1 + \log n_2)$ where $n_1$ and $n_2$ are the number of nodes in the trees ...
0
votes
0answers
46 views

Odds of winning a fight in a text-based game (all formulas are known)

So there's this game where you can choose to fight other players, the fights are automatic and once they've started you can't affect them in any way. Each player has: Health Armor Minimum damage ...
1
vote
0answers
47 views

Combinatorial search by testing sets with fixed number of elements

I am struggling to see the complexity of the following combinatorial search problem. Could anyone help me? Consider a set $I$ of $n$ items known to contain $d$ defectives or less. Assume $d < ...
0
votes
1answer
36 views

how to prove this

Prove that $$\sum_{i=1}^ni^p = \Theta(n^{p+1}) $$for $p \ge 1$ Does $\displaystyle \sum_{i=1}^n i^p = n^p\frac{n^p+1}2$ ? I know that $$\Theta(g(n))=\{f(n): \text{$\exists c_1,c_2 > 0$ and ...
0
votes
0answers
12 views

Breadth First Search - Building All Possible Trees of a Set

Suppose there is a set of values arranged in a binary search tree (BST). I'm trying to write an algorithm that takes in a sequence, and prints all permutations (BSTs) that have that sequence as their ...
0
votes
2answers
62 views

Sorting a list of points in 2-D clockwise

I have number of points with co-ordinate (latitude, longitude) in 2-D: Here is a collection of some points: \begin{array}{ccc} \hline No.& lon & lat \\ \hline 1& 84.07921& 24.49703 ...
0
votes
1answer
64 views

The jelly bean box problem

I believe this is a standard graph theory problem, but I am not sure. I am having a lot of trouble with it though. Give it a go You have n jelly beans. You want to ship them all to a friend. For 1 ≤ ...
0
votes
0answers
9 views

Lemma regarding extended GCD algorithm for polynomials

I am looking at the extended GCD algorithm for polynomials in Wikipedia: https://en.wikipedia.org/wiki/Polynomial_greatest_common_divisor#Euclidean_division and I am trying to prove the following: ...
0
votes
1answer
19 views

Probability of going from node a to node b in an undirected graph.

I have a graph with n nodes. Each of which represents an activity (play, walk, sleep, etc). If I'm standing at node 1 (any), what is the probability of going from 1 to j (another node) if probability ...
1
vote
1answer
34 views

Why test problems in convex optimization are mostly random?

Very often people who compare performance of different algorithms in convex optimization use randomly generated data. For instance, this often happens in compressed sensing and signal processing. Is ...
1
vote
1answer
58 views

Find simple path with the largest sum of weights

In the longest path problem, given a weighted graph G and a starting node v0, find the simple path starting with v0 with the largest sum of weights. Show that the longest path problem is NP-hard in ...
1
vote
1answer
41 views

Tree recursive question: number of nodes and relationship with children

Suppose a given tree T has n1 nodes that have 1 child, n2 nodes that have 2 children, . . . , nm nodes that have m children and no node has more than m children, how many nodes have NO child are there ...
0
votes
0answers
35 views

About Intersection of two convex polytope?

the intersection of two convex hull of two polytope P and Q , is it the convex hull of the intersection of P&Q ? Conv(P) ∩ Conv(Q) = conv(P∩Q) ???.
0
votes
0answers
65 views

Does a greedy task selection algorithm find a c-approximate solution?

A scheduling problem can be stated as: Given a set $\{(s_i,f_i)\}_{1\le i\le n}\}$ of tasks identified by their start and end times, choose the maximum size subset of non-overlapping tasks. ...
0
votes
0answers
37 views

Learning pipeline for developing own optical flow algorithms

I am really sorry if this question is outside of this resource or too silly I am bachelor of computer science and a programmer in small company. And i am faced with the task of developing own custom ...
0
votes
0answers
23 views

DFS and BFS of a rooted tree

I wonder why the rooted tree obtained by applying Dijkrstra's algorithm can be both DFS and BFS tree. I thought the Dijkstra's algorithm was DFS but the answer says the rooted tree should be both ...
8
votes
0answers
92 views

Algorithm to compute fastest method of collecting $k$ re-spawning items which spawn at $n$ specified points

Let $V = v_1, \dots, v_n$ be the locations the items can spawn at, and let $U = u_1, \dots, u_k$ be the current positions of the items. We will assume a new items spawns instantly every time we ...
0
votes
0answers
18 views

Proving regular languages over an alphabet

Language L over alphabet Σ THREE(L) = {abc | a,b,c ∈ Σ and ∃x ∈ Σ∗ s.t. abcx ∈ L} and every String in THREE(L) is exactly 3 characters long I am not sure how to prove that L whenever L is a regular ...
2
votes
1answer
25 views

confudes with Dijkstra's algorithm.

I have tried to understand the question but I got really confused. So starting from node 3, the distance to other nodes are 3 to 1 = 3 3 to 2 = 1 3 to 4 = 4 3 to 5 = 2 3 to 6 = 3 3 to 7 = 2 ...
0
votes
0answers
25 views

How to solve recurrence relation $T(n)=2T(n/2)+4^n$ using characteristic equation method?

With change of variables $n = 2^k$ We get $$T(2^k) = 2T(2^{k-1}) + 4^{2^k}$$ which yields $$S(k) = 2S(k-1) + 4^{2^k}$$ I cannot go further. Here: ...
1
vote
1answer
51 views

Tower of Hanoi Algorithm

I read many articles about the "Towers of Hanoi" algorithm, but i couldn't see any relation to computer science or something else? Is it used somewhere to describe a special problem?
0
votes
0answers
39 views

Finding value of given function with mod M

I want to calculate value of $F(N) = (F(N-1) * (N-R+1)^{(N-R+1)}/R^R)$ % M for given values of N,R and M. Here M need not to be prime. How to approach this question? Please help because if M was ...
0
votes
0answers
61 views

Finding the initial permutation

Assume a permutation P[1], P[2], ..., P[n]. Now we have made N permutations Q[1], Q[2], ..., Q[N], Q[i] is permutation P without element i (we subtract 1 from all elements bigger than i). For ...
1
vote
3answers
16 views

running time of an algorithm

I am trying to prove an algorithm with input size $n$ satisties the recurence relation (for $n>=1$) $T(n) = T(n-1)+n$ and an initial condition of $T(1)=1$ has running time in $Θ(n^2$). By using ...
1
vote
1answer
50 views

Analyzing runtime of a nested for loop

// assume n is a power of 5 for (int i=1; i<n; i=i*5) for (j=i; j<n; j++) sum = i+j; I am supposed to find out how many times each line of code ...