# Tagged Questions

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).

112 views

### Is there a term for $O( (m+n) \log{mn})$ time algorithms?

Is there a term for $O( (m+n) \log{mn})$? I remember seeing it often in some context but can't remember.
78 views

### how to calculate an integer x let x^2+2mx-n is a square number?

Let m, n be positive integers. Let $x^2+2mx-n=p^2$ for some p which is a positive integer. How does one solve for x? Sorry forgot this: x must be an integer.
99 views

### Is there any fast way to get the number of a certain day in a week

I'm realy sorry, if this question is a bit stupid... But this is my first time on mathematics stackexchange. Do you guys now for example, how to know the number of monday in a year?
consider the system given by: $$x'_{1}=9x_{1}+24x_{2}+5\cos t-\dfrac{1}{3}\sin t$$ $$x'_{2}=-24x_{1}-51x_{2}-9\cos t+\dfrac{1}{3}\sin t$$ with initial values $$x_{1}(0)=\dfrac{4}{3}$$ and $$x_2(0)=\... 2answers 3k views ### Meaning of amortized analysis of an algorithm From Introduction to Algorithms by Cormen et al: In an amortized analysis, the time required to perform a sequence of data structure operations is averaged over all the operations performed. ... 1answer 405 views ### How to solve this recurrence T(n)= 7 T (n/2) + 2 \log (n)? Solve this recurrence equation T(n)= 7T (n/2) + 2 \log (n)? Could you please help me to solve it because I have been stuck on it for 2 nights. Thanks in advance. 0answers 190 views ### Why genetic algorithm find maxima/minima of a function I don't know if this is the right place to ask for an answer to this question. If not, I would migrate the question with no problem. Anyway I use genetic algorithm quite often to find maxima and ... 3answers 258 views ### 0-1 knapsack like - the set of all non-contained affordable binary selections This is my first question here, so please go easy on me :) The following problem is – I think - similar to the 0-1 knapsack problem. It's simplified somehow in that each item has only a cost (weight),... 1answer 8k views ### Convert a n by n matrix to upper triangular How can we mathematically and algorithmic-ally convert a n\times n matrix to a upper triangular matrix 1answer 582 views ### Pancake Sort in (n-1) flips I've read in most places that the minimum number of flips in the worst case scenario required to sort a stack by any algorithm is between 15n/14 and 18n/11. But I read here: It was shown in ... 1answer 925 views ### Faster arithmetic with finite continued fractions I was curious about different representations of rational numbers and came across the finite continued fraction (see wp:Finite_continued_fractions ). Note: I will refer to traditional rational ... 1answer 742 views ### Graph Theory: Clique concepts I was trying to solve a basic clique problem but i have stucked at some following points: ... 1answer 2k views ### Is War necessarily finite? War is an cardgame played by children and drunk college students which involves no strategic choices on either side. The outcome is determined by the dealing of the cards. These are the rules. A ... 1answer 54 views ### Median-of-k elements Assume I am given a sequence of n elements (by sequence I mean an ordered set). I want to randomly pick k elements out of these n elements, where k is an odd number \leq n. Then out of ... 1answer 2k views ### Median of medians algorithm I am referring to the algorithm presented here used to find a good pivot: http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm My ... 2answers 119 views ### Bijection f : \mathbb{N} \rightarrow \mathbb{A} from naturals to algebraics I'm doing a presentation on Godel's paper "What Is Cantor's Continuum Problem?", and would like to include a computational demonstration of the countability of the algebraic numbers. I'm looking for ... 1answer 3k views ### Finding common terms of two arithmetic sequences using Extended Euclidean algorithm I have a problem which could be simplified as: there are two arithmetic sequences, a and b. Those can be written as a=a1+m*d1 b=b1+n*d2 I need to find the ... 0answers 412 views ### Pure greedy algorithm I study pure greedy algorithms in different basises. I am interested in 1 one question: is there such a Riesz basis D in Hilbert space and f\in H such that$$||f-G_m(f,D)||>Cm^{-1/2}|f|_{H}$$... 1answer 636 views ### Hamiltonian path in a tournament Exercise: Suggest an effective algorithm finding Hamiltonian path in tournament with n vertices using adjacency matrix T[1..n, 1..n]. Firstly, I proved that such path always exists. It was an easy ... 1answer 409 views ### How to solve/transform/simplify an equation by a simple algorithm? MathePower provides an form. There you can input a formula (1st input field) and a variable to release (2nd input field) and it will output a simplified version of that formula. I want to write a ... 3answers 473 views ### Order of magnitudes comparasions I have a list of order of magnitudes I want to compare. My only idea is using calculus methods (limits , integral, etc...) to assert the functions relation. I need your help with the following. I ... 3answers 88 views ### Big-O compared to a new Operator I'm trying to figure out a new operator compared to the Big O. Suppose we have two positive functions, f(n) and g(n) then we say that f(n) = O^*(g(n)) if there exists a constant  c > 0  ... 1answer 436 views ### Puzzle : Birds on a circular wire The problem is taken from my course on randomized algorithms : There is a circle made of wire. n birds (assume n>2) occupy uniformly random position over it (visualize each bird occupying a point on ... 2answers 18k views ### Explanation on arg min would someone be so kind to explain this to me: Especially the arg min part. (it's from the k-means algorithm) 0answers 88 views ### Solve Ax = b where b are labels instead of values Suppose, there is a system of linear equations Ax = b, where A \in R^{m \times n}, m>n and b_i \in \{l_1,....,l_k\}, i.e. each b_i is a label instead of being a real number. To solve this, ... 2answers 881 views ### What would be the shortest path between 2 points when there are objects obstructing the straight path? How would an algorithm find the shortest distance between 2 points on a horizontal 2d plane , especially when a straight path is not possible? Could it be something on the lines of calculating least ... 1answer 421 views ### Is there a polynomial-time algorithm to find a prime larger than n? Is there a polynomial-time algorithm to find a prime larger than n? If Cramér's conjecture is true, we can use AKS to test n+1, n+2, etc. until the next prime is found, and this method will ... 2answers 411 views ### Computing orbit representatives for a group action Consider the following classic problem in combinatorics: how many neckleces with n black/white beds are there up to rotations? You can formulate the question in the language of group theory: acting ... 1answer 418 views ### Difficulty proving / finding witnesses for the following Functions (Big O and Big Ω and \Theta) I have left with some functions I can't find witenesses for proving Big O and Big Ω and Big \Theta relations. Notice that I should prove the following using the defintion and not any complex ... 1answer 276 views ### Cubic (3-regular) graph spanning tree Considering loop free cubic graphs (graphs where every node has 3 neighboring nodes)： Is is possible to construct a spanning tree that only has nodes with 3 neighbors in the spanning tree or 1 ... 1answer 878 views ### Sub-Graph of a Minimum Spanning tree I am going through all the exercises in my book for revision of a class test next week, and i am really confused about this sub-graph question. Currently my thinking leads me to believe that since ... 0answers 22 views ### Splitting data based on 2 factors I have two sets of data assigned to each parameter. Lets say they are weight and age. If I have 10 people, I want to split them into two groups of 5 each such that each of the groups combined weight ... 2answers 631 views ### Prime one heap Nim I have been working on an interesting problem my lecturer mentioned recently. Prime Nim is a variant of the Nim game where you have a single pile with an arbitrary number n\in \Bbb N+\{0\} of ... 3answers 315 views ### why m power by n equals sum of n numbrs$$m^n=\sum_{i=0}^n(m-1)^i\binom{n}i$$(a) I want to find a formula for the above and then prove it by induction. But there is two variable right those are m and n. I know that this is true, ... 1answer 320 views ### What are the differences between the random walk and the gaussian random walk? I know the random walk mobility model, but I can not understand what are the differences with respect to gaussian random walk. In other words, I know how to implement the two-dimensional random walk: ... 0answers 62 views ### maximizing sum of a 3 numbers to There are n lines of length 90 inches which need to be cut at 1/2 places so that the new parts formed after cut have a total length as close as possible to 90. ... 1answer 681 views ### Help in understanding search of Vantage-Point tree This is my reference: http://stevehanov.ca/blog/index.php?id=130 A vantage-point tree is a way of organizing a set of points so that finding the n-nearest neighbors is as efficient as possible. It ... 1answer 341 views ### Kruskal's algorithm proof I'm having trouble understanding part of the proof of Kruskal's algorithm. In the notes that our professor gave us, he has this: Ok so this is missing some things. Unfortunately the lecture does ... 2answers 979 views ### Enumeration of partitions The Stirling number of the second kind S(n,k), where S(n,k) = \frac{1}{k!}\sum\limits_{j=0}^k(-1)^{k-j}\left(\begin{array}{l}k\\j\end{array}\right)j^n Gives the number of unique unlabeled, ... 1answer 134 views ### Multiplying Polynomials with fewer coefficient multiplications Not sure how this works! Apparently it can be done in 5-6 multiplications Show how to multiply two degree 2 polynomials using fewer multiplications of coefficients than the naive algorithm. 1answer 94 views ### Marching cubes - where does the isosurface cut the edge? I am currently trying to figure out the insane marching cube algorithm (a.k.a. "3D contouring" or "Surface reconstruction"). According to Paul Bourke, The position that it [the isosurface] cuts ... 0answers 88 views ### Optimized Algorithm for Distance Matrix Solution I've been looking for an optimized algorithm for solving a distance matrix (a hollow, skew symmetric matrix), but I haven't been able to find anything but papers discussing repopulating sparse ... 1answer 213 views ### Algorithm to find a derivation in propositional calculus Does such a algorithm exist? I mean given a set of axioms and a rule of inference (e.g. modus ponens) it should create a full derivation of a given theorem (or state that it's impossible). The ... 1answer 168 views ### Bubble sort in two passes In "Mathematics for the analysis of algorithms", I find the following problem. How many permutations on \{1 \dots n\} can be sorted by at most two bubble sort passes? The book later goes on to ... 1answer 216 views ### N piles of hidden cards of known marginal probability distribution, then a card is revealed in one of the piles. I am currently trying to use probability theory to help solve a programming problem involving Monte Carlo Tree Search with Information Sets and have hit a roadblock. The problem can be described as ... 1answer 351 views ### Finding all spanning trees of a strongly connected directed graph I have a strongly connected directed graph with about 10 vertices and 20 edges, and would like to find all spanning trees anchored at each vertex. Is there a systematic way, or a tested program/... 1answer 362 views ### Probability - Expected value of a n random selection Given an integer n, one does n random selections with repetition one after the other. For each selection there are two possibilities a success X and a failure O. For each selection i\le n ... 1answer 233 views ### Topological sort of a subgraph If I have a graph G and a subset G', for all topological sorts S over G, is there a topological sort over G' that is a subset of S? As a software optimization I want to pre-compute S ... 2answers 59 views ### Is there any way to split a number with multiplication of some prime number I am looking for an algorithm which helps me split a number N as such:$$N=p_1^a p_2^b \cdots p_n^z where $N$ is the given number, $p$ is prime numbers smallest to greatest, and $a,b,\cdots,z$ ...
The following was posted from a lecture: "($a^n \bmod N$) has a runtime complexity of $\mathcal{O}(n*|a|*|N|)$ using the brute force method. $Z_1 = a \bmod N$ $Z_2 = (aZ_1) \bmod N$ \$Z_3 = (aZ_2) \...