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
1answer
91 views

Create a new image from an image set's patterns

So, I'm interested in learning how to detect patterns in a set of images and then use those patterns to create a new image of similar style. For example, say there is a group of 20~ish images ...
1
vote
1answer
162 views

Deterministic algorithm to fit rhombus to set of points

I'm looking for a deterministic algorithm to obtain the best fitting rhombus out of a set of user-drawn points. It need not necessarily be optimal (simple would be better). Thanks.
0
votes
1answer
50 views

Concatenating different “letters” or domains together, so they don't touch

i will try to be short. i need some "formula" or. a described way, how can i concat domains "together" so they dont touch? in a example i will use letters instead of domains, i have: ...
4
votes
0answers
380 views

Smooth numbers algorithm

I am trying to understand quadratic sieve algorithm and now I am thinking of the way to check if number is smooth over a factor base? For example, say I have number $n = 87463$. First,I find bound $B ...
0
votes
1answer
79 views

Estimates of Gaussian Logarithms

I've been implementing logarithmic number system and I came across these functions called Gaussian logarithms: $f(x) = \log(1 + e^x)$. $g(x) = \log(e^x - 1)$ for $x > 0$. $h(x) = \log(1 - e^x)$ ...
5
votes
2answers
247 views

Why does input size matter in NP theory?

When my prof introduced us to the N/NP topics, the first thing he mentioned is input size, which he defines as the number of bytes needed to describe and write a problem's input into a file. Could ...
5
votes
1answer
134 views

Quantum Information: Deutsch-Jozsa Algorithm

There is a step in the construction of this algorithm which I'm not understanding: $\displaystyle \left[\sum_x \frac{| x \rangle}{\sqrt{2^n}}\right]\left[\frac{ | 0 \rangle -| 1 \rangle ...
2
votes
4answers
863 views

Multiplying exponents, solving for n

When solving for n in this equation I get stuck. Question: What is the smallest value of n such that an algorithm with running time of $\ 100n^2 $ runs faster than an algorithm whose running time is ...
1
vote
0answers
737 views

Legendre and Jacobi symbols

I have a problem with Tonelli-Shanks algorithm with numbers $n = 87463$ and $p = 17$. Solutions are supposed to be $x_1 = 7$, $x_2 = 10$, but I get $11$ and $6$. First with sieving I get a list of ...
1
vote
1answer
409 views

Can Horn's algorithm be generalized for all logic expressions?

The following is an algorithm to find truth assignments for Horn Formulas: Input: A Horn Formula Output: A satisfying assignment, if one exists Set all variables to false While ...
2
votes
1answer
80 views

Coloring of graph such that every vertex in graph is either colored or shares an edge with a colored vertex

I'm a bit of a graph theory noob, so please forgive the absence of mathematical rigor in my question. Here it is: Given a graph $G \to (V,E)$, (where every vertex $v$ in $G$ has some weight $w$ ...
0
votes
1answer
532 views

Proving by induction

I'm having a problem relating to proving by induction that the Preorder(T) and Postorder(T) algorithms both print out all the nodes in the tree without repetition. I'm not quite sure where to start.. ...
5
votes
1answer
199 views

What function $f$ such that $a_1 \oplus\, \cdots\,\oplus a_n = 0$ implies $f(a_1) \oplus\, \cdots\,\oplus f(a_n) \neq 0$

For a certain algorithm, I need a function $f$ on integers such that $a_1 \oplus a_2 \oplus \, \cdots\,\oplus a_n = 0 \implies f(a_1) \oplus f(a_2) \oplus \, \cdots\,\oplus f(a_n) \neq 0$ (where the ...
4
votes
1answer
609 views

Roots of rational equation with multiple variables?

Let's say we have a rational polynomial in $k$ variables. We are only interested in rational solutions. If $k = 1$, name the variables ${x}$, if $k = 2$, name them ${x,y}$. For $k = 1$, it can be ...
2
votes
2answers
89 views

Newton algorithm for a function in $\mathbf{R}^n\rightarrow \mathbf{R}$

I am curious on how the Newton algorithm would work to solve an equation of the type: $f(x_1,\dots,x_n)=0$. As far as I understand, in dimension $1$, one solves $f(x)=0$ by starting with some $x_0$, ...
2
votes
2answers
760 views

Fast algorithm for LU factorization

If A is a symmetric matrix, is there a fast algorithm for LU factorization? I know this algorithm for non-symmetric matrix. ...
4
votes
3answers
3k views

What does asymptotically optimal mean for an algorithm?

What does it mean to say that heap sort and merge sort are asymptotically optimal comparison sorts . I know What the Big O , Big Omega($\omega)$ and Theta($\theta$) notations are and I also know ...
0
votes
1answer
62 views

Determing if two k subsets are disjoint given the product of their elements

Consider the following problem (phrased with the use of a black box). You choose $n$ numbers $X = \{x_1,\ldots,x_n\}$ and pass it to a black box that returns a list $Y = \{y_1,\ldots,y_m\}$ where ...
3
votes
1answer
342 views

Least quadratic non residue algorithm

I am trying to implement Tonelli-Shanks algorithm and at one of the steps I have to find the least quadratic non residue. I've searched the web for a while for some kind of algorithm but so far I've ...
0
votes
1answer
300 views

Which one gives better constant factors between heap sort and quick sort?

Heap Sort has complexity $\mathcal{O}(n\lg(n))$ and Quick Sort with some tuning (choosing the pivot in a random order) on average also sorts in $\mathcal{O}(n\lg(n))$ and both of these are tight upper ...
2
votes
3answers
7k 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
2answers
1k views

Explanation of why the height of a binary tree $\theta({lg}(n))$.

From Heap Sort chapter of Introduction to algorithms : Since a heap of n elements is based on a complete binary tree , its height is $\theta({lg}(n))$. I know this is correct but how can this ...
6
votes
2answers
902 views

Algorithm fot planarity test in graphs

I am implementing a graph library and I want to include some basic graph algorithms in it. I have read about planar graphs and I decided to include in my library a function that checks if a graph is ...
3
votes
2answers
277 views

Prime Identification easier than Prime Factorization?

I need an algorithm to decide quickly in the worst case if a 20 digit integer is prime or composite. I do not need the factors. Is the fastest way still a prime factorization algorithm? Or is there ...
4
votes
1answer
130 views

Are there any secure ciphers you can use without a computer?

I have some kids that like encryption schemes such as the Caesar cipher and the Vigenère cipher. I would like to teach them something that's not easily breakable by todays maths and computers, but I ...
4
votes
2answers
4k views

Intuition behind the concept of indicator random variables.

I am studying Randomized Algorithms chapter in the book "Introduction to Algorithms" by Cormen et al. In this chapter the book introduces the concept of an indicator random variable and state that ...
0
votes
1answer
188 views

Number of Rows and Columns in Conway's Game of Life

When trying to program Conway's Game of Life, is it okay to have a grid with unequal number of rows(>=2) and column (>=2) OR Is it mandatory to have equal number of rows and columns?
1
vote
0answers
327 views

Algorithm for intersection between polyline and rectangle?

My problem is simple, and probably obvious from the title itself, but I'll still clarify it a bit: I have a rectangle and a polyline (array of N connected points). I need an optimal algorithm that ...
0
votes
2answers
73 views

Ordered subsets summation

Let $A$ and $B$ two finite ordered sets where $A\subseteq B$. How do I count the number of consecutive and non-consecutive ocurrences of $A$ in $B$? For instance, I have nine ocurrences of set ...
0
votes
2answers
915 views

Newton's method - determine accuracy in calculation

I have almost managed to solve a problem (I think), but I am a bit unsure if my procedure is correct, and my answer is not quite the correct one. Would appreciate any input! The problem is as ...
0
votes
1answer
113 views

Is the result always n+1?

I'm reading a book on algorithms by Kurt Mehlhorn and Peter Sanders. On page 2, the following Theorem is stated: The addition of two n-digit integers requires exactly n primitive operations. The ...
4
votes
4answers
1k views

Newton's method - finding suitable starting point

I have some trouble solving a problem in my textbook: Given the following function: $$f(x) = x^{-1} - R$$ Assume $R > 0$. Write a short algorithm to find $1/R$ by Newton's method applied to ...
5
votes
2answers
423 views

Karatsuba Multiplication

Karatsuba's equation to reduce the amount of time it takes in brute force multiplication is as follows (I believe this is a divide-and-conquer algorithm): $$ x y = 10^n(ac) + 10^{n/2}(ad + bc) + bd ...
0
votes
4answers
2k views

Why there may be no single “maximum” element in a partially ordered set?

From Appendix B.2 (relations) of Introduction to Algorithms by Cormen et al: In a partially ordered set A, there may be no single "maximum" element a such that b R a for all b ∈ A. Instead, there ...
7
votes
3answers
2k views

What's the proof of correctness for Robert Floyd's algorithm for selecting a single, random combination of values?

I read about it in a SO answer: Algorithm to select a single, random combination of values? ...
1
vote
1answer
81 views

minimizing multiplications in computing a polynomial expression

I am looking for an algorithm which presents a given polynomial in many variables (given as a sum of monomials) in a form with the smallest number of multiplications of variables. For example ...
1
vote
0answers
577 views

What is needed to know to study algorithms?

I just started to read Thomas H. Cormen's book "Introduction to algorithms" (2nd edition) and just figured out that from first 40 pages I'd understand about 30%-40%. Can you help to realize what ...
8
votes
1answer
769 views

Why does Strassen's algorithm work for $2\times 2$ matrices only when the number of multiplications is $7$?

I have been reading Introduction to Algorithms by Cormen. Before explaining Strassen algorithm the book says this: Strassen’s algorithm is not at all obvious. (This might be the biggest ...
3
votes
2answers
120 views

Given a list of $2n$ elements, which is the best approach to find the $n$'th largest element?

Given a list of $2n$ elements, we have to find the $n$'th largest element. Which is the best algorithm (Time complexity + comparison) for this particular problem? I know that this could be solved in ...
8
votes
1answer
866 views

Fast algorithms for calculating the Möbius inversion

Recall the Möbius inversion formula: if we have two functions $f,g \colon \mathbf{N} \to \mathbf{N}$ such that $$g(n) = \sum_{k=1}^n f\left(\left\lfloor \frac{n}{k} \right\rfloor\right)$$ holds for ...
3
votes
1answer
163 views

Fundamental Theorem of Algebra. Showing polynomial as product of linear polynomials

Using the division algorithm repeatedly, show $$a_n x^n + a_{n-1} x^{n-1} + \cdots + a_0 = a_n (x-k) (x-j) \cdots (x-b)$$ for $n$ greater than or equal to $1$. My attempt: (Proof by induction) ...
2
votes
1answer
1k views

How many rectangles can fit in a polygon with n-sides?

I am trying to write an algorithm to solve a problem I have. I have a few ideas of what the algorithm might be like but I am posting to see if anyone else has a better more efficient solution or any ...
6
votes
2answers
592 views

Why does the $2$'s and $1$'s complement subtraction works?

The algorithm for $2$'s complement and $1$'s complement subtraction is tad simple: $1.$ Find the $1$'s or $2$'s complement of the subtrahend. $2.$ Add it with minuend. $3.$ If there is ...
1
vote
2answers
159 views

In mathematics, what is meant by induction?

I was going through MIT video lectures on "Introduction to Algorithms " . In order to solve recurrences by substitution the professor says that we can solve them by induction. What is actually the ...
2
votes
2answers
628 views

Determine the number of factors for extremely large numbers.

An offshoot from a related question, is there a way to determine the number of possible factors (odd, even, prime, etc.) for extremely large integers without actually factoring them? Even an ...
1
vote
2answers
258 views

Tournament Algorithm for Quartets

I'm currently trying to find an algorithm to place players during a Mahjong tournament. Here are the requirements : Number of players in the tournament : $n$ with $n \equiv 0 \pmod 4$ Number of ...
2
votes
2answers
416 views

Distance Puzzles?

A man moves 1km east, 2km north, 3km west, 4km south, 5km east, 6km north, 7km west and so on until he travels total of 300km. So what will be the distance from origin?
3
votes
2answers
3k views

How to handle big powers on big numbers e.g. $n^{915937897123891}$

I'm struggling with the way to calculate an expression like $n^{915937897123891}$ where $n$ could be really any number between 1 and the power itself. I'm trying to program (C#) this and therefor ...
0
votes
1answer
254 views

Time units needed to run factor finding algorithm on inputs of length t and time efficiency

For the following algorithm. Initialize i = 1. If i > a then stop. Otherwise, if i divides a then output i. Increment i by 1, and then go to line 2. If it takes one unit of time to execute each of ...
1
vote
1answer
77 views

Does this sequence of operators in Hilbert space, given by an algorithm, terminate

Let $H$ be an infinitedimensional Hilbert space and $T$ a compact selfadjoint operator in it. Consider the following Algorithm: Let $$ H_{1}=H,\ T_{1}=T $$ and let $\lambda_{1}$ be that ...