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
2answers
13 views

Growth function and one misunderstanding point?!

I have a question about Growth and Asymptotic notation topic. My question is as follows: $2^n$ > $n^{log_2{(n)}}$ is True. anyone could say how we can deduce that this fact is true?
4
votes
2answers
40 views

Can someone give me some ideas of algorithm for this card question?

Problem There is a $N$ by $1$ long card consisting of $N$ square cards, each having the number $1, 2, \cdots, N$ regardless of the sequence of cards. Find whether or not the long card could be in ...
0
votes
1answer
38 views

Coefficients of a Polynomial Approximation in Minimax Sense

I am working on a Uniform Random Number Generator using a IEEE paper, and I got stuck with the coefficients for a Piecewise Polynomial Approximation using Horner's Rule : $$ y = ((C_d x + C_{d-1})x +...
0
votes
1answer
21 views

Construct a weighted graph under the following conditions:

I need to construct a weighted graph of which neither of the Greedy Algorithms produces a correct answer to the Traveling Salesman Problem. Greedy Algorithms 1) Nearest Neighbor Works as ...
1
vote
0answers
21 views

Monte Carlo Search Tree iterations

I have had this example in my exam last week and I can not figure out how to solve it. I have watched lots of tutorials on Monte Carlo Search Tree but I can't still understand this algorithm properly. ...
2
votes
2answers
520 views

Give an algorithm that computes a fair driving schedule for all people in a carpool over $d$ days

Some people agree to carpool, but they want to make sure that any carpool arrangement is fair and doesn't overload any single person with too much driving. Some scheme is required because none of ...
0
votes
0answers
7 views

How to compare two objects for percentage of equivalence

I'm trying to create a nodeJS application. It allows users to rate a bunch of songs and it stores them in their user profiles. I use this information to compare them to other users, and try to find ...
0
votes
0answers
27 views

How do you solve the following questions on asymptotic analysis. Please share your approach. [on hold]

Check this image: I have read about the three notations but I'm unable to use the concepts to solve questions like this.
3
votes
2answers
81 views

Simplifying polygons

I want to turn digitized polygons into simpler shapes. More precisely, given a noisy closed polyline, I want to fit a polygon to it with an imposed number of sides, such as a triangle or ...
3
votes
0answers
16 views

Factory inspections on a budget

A factory inspector is testing the efficiency of $n$ machines. To pass the inspection, each machine is required to run at or above a certain standard efficiency. The inspector can measure the ...
0
votes
0answers
29 views

Exam Recurrence and Complexity [on hold]

I have an exam coming up in a few days and my prof gave us a couple questions we should know as he will make new questions based on these topics the explanations must be in-depth because it will be a ...
0
votes
1answer
9 views

Why is the running time of the trial division $O(f \cdot (log N)^2)$?

I saw this being cited in a few paper,but none of them seems to explain why this is the case. Maybe because it is quite trivial, but I am not sure why exactly... Here $f$ is the size of the factor. I ...
0
votes
1answer
21 views

Intuition behind this algorithm for finding an Eulerian circuit in a graph?

An Eulerian circuit of a directed graph $G = (V,E)$ is a path that travels through every edge in $E$ exactly once. This algorithm finds such a circuit if it exists. (I am interested in the directed ...
1
vote
1answer
455 views

Computational complexity of Gaussian elimination

If it took me approximately 4 minutes to solve an equatian $Ax=b$ for $x$ (where $A$ is a $3\times3$ matrix and $b$ is a $3\times1$ matrix) using Gaussian elimination, how much longer would it take me ...
-2
votes
2answers
41 views
6
votes
0answers
145 views

A graph problem

Consider the following graph problem. We are given a set of vertices $A_i$, $B_i$, and $C_i$ where $i \in \{1,2,3 \}$. For each vertex, there is a corresponding weight where the weight of vertex $A_i$ ...
0
votes
1answer
19 views

Determining when two binary strings represent the same necklace or when one binary string is periodic

An equivalence relation on binary strings calls two strings equivalent if one can be obtained from the other by a cyclic permutation of the characters. Combinatorialists call the equivalence classes ...
0
votes
0answers
26 views

Chinese Postman Problem - open walk variation

Consider the following variation of the Chinese postman problem (also known as the route inspection problem). Instead of finding the shortest closed walk which traverses each edge at least once, find ...
0
votes
0answers
22 views
0
votes
1answer
27 views

Fast way of suming up polynoms

You probably will think that this question is more about algorithms, but actually i'am searching for right formula. What i want to do is to compute $(A^n + A^{n-1} + .. + A + 1))$ mod $(10^9 + 7)$ ...
3
votes
1answer
540 views

Fast generation of Pareto-distributed randoms.

I'm developing a library of routines for generating random numbers for simulations (it's on GitHub). I've included fast routines for normally distributed and exponentially distributed randoms, using ...
0
votes
0answers
8 views

Acyclic orientation of a mixed graph with minimization of the critical path

I already asked this question as a guest but I was not able to edit it or add comments after I registered with my e-mail address. A apologize for asking the same question again. A mixed graph is a ...
0
votes
0answers
14 views

Finding and proving upper bound of specific function

Following function is given: $$ f : \mathbb{N{}} \rightarrow \mathbb{R^+} , n \mapsto \begin{cases} n! & \text{for } 1 \leq n \leq 17\\ 2^{2^n}& \text{for } 18 \leq n \leq 42 \\ \log_2 n &...
0
votes
1answer
768 views

Dijkstra Algorithm proof

I was studying the proof of correctness of the Dijkstra's algorithm . In the above slide , $d(u)$ is the shortest path length to explored $u$ and $$\pi(v) = \min_{ e\ =\ u,v:u \in S}d(u) + l_e$$ and $...
0
votes
2answers
635 views

Greedy Algorithm, Fewest overlaps

Hi I need help doing this problem. I've been working on it for like 2 hours now and I'm no where. I'm literally about to throw my computer. I've watched youtube videos, reread my notes. The homework ...
9
votes
2answers
123 views

Most efficient method for computing Singular Value Decomposition of a triangular matrix?

There are several methods available for computing SVD of a general matrix. I am interested in knowing about the best approach which could be used for computing SVD of an upper triangular matrix. ...
0
votes
0answers
12 views

Orient edges in a mixed graph to minimize the critical path

3 down vote favorite A mixed graph is a graph that has directed and undirected edges. Is there an efficient algorithm that allows the orientation of undirected edges in a mixed graph in such a way ...
0
votes
0answers
15 views

Genetic algorithm optimize and minimize

I'm using a Genetic Algorithm to increase a certain value and decrease another. I'm trying to find the best parameters for a trading strategy. There are 2 values important for me. The netto profit ...
0
votes
3answers
46 views

How do I find Big O notation for this function?

How do I find Big O notation for this function? $$ n^4+100\cdot(n^2)+50 $$ In the book I am following, I got the following solution: $n^4+100(n^2)+50 \leq 2(n^4) \ \forall \ n \geq 11$ $n^4+100(n^2)+...
0
votes
0answers
7 views

Morphological operations with even sized structuring elements

The well-known morphological operations, such as dilation/erosion, opening/closing, top-hat... , widespread in digital image processing, are defined by means of so-called structuring elements. For ...
1
vote
1answer
62 views

approximate greatest common divisor

I try, without success, to create an algorithm that can compute the average greatest common divisor of a series of integers. For example, I have the following numbers: ...
-1
votes
1answer
20 views

how to get the angle of arc ??

dart game board is divided into sectors by 30 degrees like pizza slice. the given is (x, y) coordinates, and I need to find where coordinates are lying on. how can I get the angle just with ...
2
votes
1answer
114 views

“Practical” Sieve of Eratosthenes from “Primes Numbers - A Computational Perspective”

Consider the following pseudocode for the Sieve of Eratosthenes, giving us the primes up to $N$: 1) List the numbers $2$ to $N$. 2) Let $p=2$. 2) Cross out $p^2$, then cross out $(p+1)p, (p+2)p, (...
-3
votes
0answers
27 views

How to correctly UPDATE the Centroids in the Fuzzy C Means (FCM) algorithm?

ATTENTION TO THE MODERATORS: In a previous time, my question was arbitrarily moved to stackoverflow forum, despite my inquiring to not do it, then it later was deleted from that forum by another ...
0
votes
1answer
475 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 ...
2
votes
0answers
10 views

Is there a known optimal solution for searching an ordered list with non-uniform query cost?

Let $D$ be the set of integers from $1$ to $n$ inclusive for $n \geq 1$, and let $$f(i) = \begin{cases} 0& i \leq k \\ i - k& i > k \end{cases}\,\,\,\forall\, i \in D$$ for some $k \...
1
vote
1answer
44 views

Why does the “printing neatly” algorithm use cubes rather than squares?

In Introduction to Algorithms, 2nd ed. (Cormen, Leiserson, Rivest, and Stein), ch. 15, Dynamic Programming, problem 15-2 Printing neatly (a copy of which is here), the official solution given in ...
2
votes
4answers
8k views

Worst case analysis of MAX-HEAPIFY procedure .

From CLRS book for MAX-HEAPIFY procedure : The children's subtrees each have size at most 2n/3 - the worst case occurs when the last row of the tree is exactly half full I fail to see this ...
1
vote
1answer
394 views

Multiple Choice Knapsack Problem (MCKP) where one class requires more than one item

I have the following problem of which I am attempting to find a near optimal solution: I have one knapsack which can hold a maximum weight. I must select exactly one distinct item from a number of ...
0
votes
0answers
4 views

What is the difference between a MIMO and multiple MISO fuzzy logic classifiers?

If I have 10 independent inputs and 5 independent outputs, can I say that a multiple MISO fuzzy logic classifiers equal to the function of a MIMO fuzzy logic classifier?
6
votes
1answer
594 views

Minimal set of inequalities

I have a set of $m$ linear inequalities in $R^n$, of the form $$ A x \leq b $$ These are automatically generated from the specification of my problem. Many of them could be removed because they are ...
1
vote
1answer
323 views

What happens if we remove the non-negativity constraints in a linear programming problem?

As we know, a standard way to represent linear programs is $$\begin{array}{ll} \text{maximize} & c^T x\\ \text{subject to} & A x \leq b\\ & x \geq 0\end{array}$$ with the associated dual ...
0
votes
2answers
472 views

Write an algorithm to find minimum number from a given array of size ‘n’ using divide and conquer approach.

In Divide and conquer strategy, three main steps are performed: Divide: Divides the problem into a small number of pieces Conquer: Solves each piece by applying divide and conquer to it ...
0
votes
1answer
35 views

A game: When can you merge two directed graphs?

I am trying to consider the conditions under which you can win the following directed graph game: Graph merging game. Fix an acyclic directed graph $G$; its vertex set is $V$, and its edge set is $...
1
vote
4answers
3k views

Vertical Lines & Horizontal Lines and Their Slopes

Hello, in my discrete mathematics for Information Technology, my instructor asked this question of us: Discuss in your own words if it makes sense that a vertical line has an infinite slope and a ...
3
votes
1answer
534 views

How to get numbers with distinct digits within some range?

I have a little program I'm working on for my project (a simple practice in school), part of the program is that it should receive input composed of an array of 7 digit (or less) numbers which should ...
0
votes
0answers
31 views

What is the best time complexity for this case?

I only want to know if the following system has any integer solution or not. Actually, I do not need to know the solution(s), and only need to know the answer of question "Does the system have any ...
0
votes
0answers
28 views

Finding integer solutions to quadratics in the form [duplicate]

In a set containing two different types of elements the probability of randomly choosing two elements of the same type can be expressed as: $$\ \frac nm * \frac {n-1}{m-1} = \frac 1x$$ Where n is ...
2
votes
0answers
23 views

Algorithm similar to the Euclidean algorithm

Given a prime number $p$, and an initial number $1<a<p$, what would be the upper bound on the iteration number of the following algorithm? (1) if $a=1$ then stop (2) else replace $a$ by $p - a\...
1
vote
1answer
18 views

Individually checking constraints for convexity in Optimisation problem valid?

I have a quadratic minimisation problem where both the objective fn and constraints have some quadratic terms. (Such as a throttle variable (continous) * On/Off (integer variable)). My question is: ...