Mathematical questions about Algorithms, including the Analysis of Algorithms, Combinatorial Algorithms, proofs of correctness, invariants, and semantic analyses

learn more… | top users | synonyms (1)

6
votes
1answer
145 views

Finding the closest match in a “golden” sequence of points

I am not a mathematician, and corrections are welcome (including tags). Background: For the last few days, i have been interested in the problem of placing points along a line segment (of length ...
6
votes
2answers
429 views

Accelerating Convergence of a Sequence

Suppose I had a monotonically increasing sequence $\{d_{n}\}$ which is also bounded above. The $d_{n}$'s satisfy a given recurrence, however computationally they tend very slowly to the limit. What ...
6
votes
1answer
611 views

How many steps does it take the computer to solve a Sudoku puzzle?

We all know what Sudoku is. Given a Sudoku puzzle, one can use a simple recursive procedure to solve it using a computer. Before describing the algorithm, we make some definitions. A partial solution ...
6
votes
1answer
31 views

Question about Growth Rates

I see in some notes from my instructor in Algorithm course that $\Sigma_{i=0}^{log n} (n/2^i)$ has growth bigger than $\Sigma_{i=1}^{n} (i log i)$. i couldn't understand why? any tutorial or hint?
6
votes
1answer
90 views

Traveling salesman problem: a worst case scenario

For those not familiar with the problem, here is the Wiki article; it can be understood by anyone. I am in particular interested in the nearest neighbor algorithm, also known as the greedy algorithm, ...
6
votes
2answers
365 views

What is mathematically significant about this algorithm?

In this question, a certain algorithm was presented: Start with a deck of $n$ cards. Take the top card off and set it on the table on top of any cards already there Move the new top card ...
6
votes
2answers
212 views

Finding the largest circle that contains a single point in a set (and no other point)

Given a bounded $A \times B$ rectangle with a set of chosen coordinates, generated for example with the command: ...
6
votes
3answers
465 views

Calculating Non-Integer Exponent

I just wanted to directly calculate the value of the number $2^{3.1}$ as I was wondering how a computer would do it. I've done some higher mathematics, but I'm very unsure of what I would do to solve ...
6
votes
1answer
78 views

Maximal Zero Sums Partition

You are given $n$ numbers between $-n$ and $n$, the sum of numbers is $0$. Divide the given sequence on disjoint subsequences in such a way that each subsequence has zero sum. Each element should ...
6
votes
2answers
2k views

Prerequisite mathematics for studying data structures and algorithms

Forgive me if this seems trivial to you. But, I do need your advice. I am self-studying computer programming, now want to study Algorithms and Data Structures. All respected texts in A&DS talk in ...
6
votes
1answer
240 views

Efficiently determining if a discrete log exists

Finding a discrete log in a finite cyclic group, like $(Z_N)^x$, seems hard and in some cases a solution may not even exist. Consider $N=15$ and the generator function $2^k=m \bmod 15$. This will ...
6
votes
2answers
2k views

Solving recurrence $T(n) = T(\lceil n/2 \rceil) + T(\lfloor n/2 \rfloor) + \Theta(n)$

I'm learning algorithms by myself and am using the excellent Introduction to algorithms to do that. It has been quite a long time since I last studied math, so maybe the solution to my problem is ...
6
votes
1answer
796 views

What about Genetic Algorithms from a mathematical point of view?

Last year I've attended an Artificial Intelligence course (it was very simple, just a summary of the main ideas); we've seen what a genetic algorithm is and the idea seems very interesting to me. Now ...
6
votes
1answer
136 views

Bounds on the gaps in a variant of polylog-smooth numbers.

Sorry for the long intro. I think the explanation motivates the question and puts it in context. But if you want to skip the story, then just move on to the grey boxes; they should contain enough ...
6
votes
2answers
546 views

Expected travel time for regularly departing trains

I'm going to ask a very simple practical question, but I believe it has some interesting mathematical properties. The simple variant is: trains depart every $x$ minutes and take $y$ minutes to arrive ...
6
votes
3answers
2k views

how to solve the recurrence $T(n) = 2T(n/3) + n\log n$

How do we solve the recurrence $T(n) = 2T(n/3) + n\log n$? Also, is it possible to solve this recurrence by the Master method?
6
votes
1answer
142 views

How to check if a polytope is a smooth Fano polytope?

Question: We say that a convex lattice polytope $P\subset \mathbb{R}^d$ is a smooth Fano polytope if: The origin is contained in the interior of $P$ The vertices of every facet of $P$ are a ...
6
votes
2answers
326 views

Which features would be interesting for a mathematician in a fractal program?

Many years ago I wrote this fractal generator: http://uberto.fractovia.org/ It was shareware but then I put it as open source. It's written in Delphi, a language that I don't use anymore. So I'm ...
6
votes
1answer
59 views

Hashing With Chaining Collision

We have $1000$ elements with key=1 to 1000, and a hashing function $$ h(i)=i^3 \mbox{ mod } 10 $$ for an array with length $10$ (array index from $0$ to $9$) with chaining method. What is the ...
6
votes
1answer
103 views

Enumerating all antichains in a finite poset

I have some reasonably small finite posets (on less than 20 points) and would like to iterate over all "downsets" in the poset, where a downset is a set closed under ≤ (so if x in X, and y ≤ x, then y ...
6
votes
1answer
240 views

Can we test if a number is a lucky number in polynomial time?

I know primality tests exist in polynomial time. But can we test if a number is a lucky number in polynomial time ?
6
votes
1answer
496 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 ...
6
votes
1answer
179 views

How to study results of Diophantine equation?

I finally managed to learn a bit of number theory and Diophantine equation(with the help of Arturo Magidin's great answer in what type of math is this?). But I'm wondering what's the next step after? ...
6
votes
0answers
42 views

Is there a numeral system that makes both addition and multiplication easy?

Decimal positional notation, the system for writing numbers we all use every single day, makes addition very easy by transforming it from a computation to a repeated operation on individual digits ...
6
votes
2answers
93 views

Eating chocolate game on grid

Given is a chocolate of size $m\times n$. Anne and Birgitte plays a game, with Anne starting. In each turn, the player has to divide the chocolate into two rectangular parts along the lines, and eat ...
6
votes
0answers
47 views

One Simple Code and Problem on Running [closed]

My Stackexchange friends, would you please show the following code how manipulate the n-elements array A?
6
votes
1answer
159 views

Intuition behind accelerated first-order methods

$\newcommand{\prox}{\operatorname{prox}}$ $\newcommand{\argmin}{\operatorname{argmin}}$ Suppose that we want to solve the following convex optimization problem: $\min_{x \in \mathbb{R}^n} g(x) + ...
6
votes
1answer
449 views

Optimal Tic Tac Toe algorithm without lookahead

Is there any algorithm for tic tac toe that does not rely on a lookahead algorithm that is perfect for any sized boards? Edit: For boards larger than $3 \times 3$, we have to find the best move for ...
6
votes
0answers
83 views

Quickest way to solve a matrix one step at a time.

I have a $14\times14$ matrix with a possibility of six states in each position The matrix is random each time. An example matrix would be: $$ \begin{pmatrix} ...
6
votes
0answers
187 views

What's the most efficient algorithm for Divisibility?

What is the most efficient (in time complexity) algorithm known nowadays for the Divisibity Decision Problem: given two integers, say $a$ and $b$, does $a$ divide $b$? Let it be clear that what I ask ...
6
votes
0answers
442 views

Hardness of finding eigenvalues over finite fields

How hard is it (computationally) to find eigenvalues/eigenvectors of matrices over finite fields? Suppose the field has size exponential in the input. (Does the QR algorithm still converge?) How ...
6
votes
1answer
229 views

Factoring some integer in the given interval

Let N be a positive integer. Is there an efficient (i.e. probabilistic polynomial time) algorithm which, on input a sufficiently large N, outputs the full factorization of some integer in the interval ...
5
votes
2answers
481 views

Generate all binary numbers, a single bit flip a time

Is it possible to sequentially generate all $n$-bit configurations (say, the binary representation of a an $n$-digit number), a single bit flip a time, in such a way that no configuration is generated ...
5
votes
9answers
6k views

Fastest Square Root Algorithm

What is the fastest algorithm for finding the square root of a number? I created one that can find the square root of "987654321" to 16 decimal places in just 20 iterations (I'm not ready to release ...
5
votes
6answers
2k views

Calculate $\pi$ to an accuracy of 5 decimal places?

In this message at point 18 I saw following programming question: Given that $\pi$ can be estimated using the function $4(1 – 1/3 + 1/5 – 1/7 + \ldots)$ with more terms giving greater accuracy, ...
5
votes
3answers
1k views

programming brain teaser

Given a programming language where you could make as many variables up as possible and you could only perform these three operators find b-1. ...
5
votes
5answers
277 views

pandigital rational approximations to the golden ratio and the base of the natural logarithm

Steven Stadnicki suggested in a comment that I post the following as a question. The golden ration $\phi$ is given by $$\phi = \frac{1+\sqrt{5}}{2} \approx 1.618033988.$$ A rational approximation is ...
5
votes
2answers
93 views

Can we implement $\omega^{CK}_1$ using $\omega^{CK}_1+1$ as an oracle?

Let $\omega^{CK}_1$ denote the least non-recursive ordinal. Suppose we have an unknown well-ordering of $\mathbb{N}$ of the order type $\omega^{CK}_1+1$ as an oracle. Is it possible to write an ...
5
votes
3answers
7k views

Worst case complexity of the quicksort algorithm

Good evening, I have a doubt concerning the worst case scenario of the quicksort algorithm, based on the number of comparisons made by the algorithm, for a given number of elements. This is part of ...
5
votes
3answers
1k views

What is the most efficient algorithm to find the closest prime less than a given number $n$

Problem Given a number n, $2 \leq n \leq 2^{63}$. $n$ could be prime itself. Find the a prime $p$ that is closet to $n$. Using the fact that for all prime $p$, $p > 2$, $p$ is odd and $p$ is of ...
5
votes
3answers
633 views

knapsack algorithm that looks too good to be true

I have an idea for solving the knapsack problem, but it looks too good to be true. I would like someone to explain potential problems with this approach. I'll give an example: I want to find a subset ...
5
votes
2answers
336 views

How can I reduce a number?

I'm trying to work on a program and I think I've hit a math problem (if it's not, please let me know, sorry). Basically what I'm doing is taking a number and using a universe of numbers and I'm ...
5
votes
1answer
240 views

Is there an efficient algorithm to determine the parity of the longest path in a graph?

Finding the longest path in a graph is intractable problem. Th decision version is $NP$-complete. However, Given a graph, Is there an efficient algorithm to determine the parity of the longest path in ...
5
votes
2answers
509 views

Lights Out Variant: Flipping the whole row and column.

So I found this puzzle similar to Lights Out, if any of you have ever played that. Basically the puzzle works in a grid of lights like so: 1 0 0 00 0 0 00 1 0 0 0 0 1 0 When you selected a ...
5
votes
2answers
139 views

Choosing between $n$ things using dice?

For which $n$ is there a finite algorithm to choose between $n$ things with the same probability using a die? For example, we can choose between 2 things, 3 things, 4 things, 6 things, and 8 things, ...
5
votes
2answers
774 views

Tranforming 2D outline into 3D plane

I am writing a program where I would like to allow the user to draw 4 connecting lines, such as: And convert this shape into a 3D plane. Is this possible? Is there an existing algorithm to do so? ...
5
votes
2answers
214 views

An algorithm for making conditionally convergent series take arbitrary values?

This thread reminded me of an old unsettled question I have. Given an arbitrary conditionally convergent series $\beta=\sum\limits_{k=1}^\infty a_k$ and a target value $\alpha$, is there an algorithm ...
5
votes
3answers
1k 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? ...
5
votes
2answers
3k views

Which is asymptotically larger: $\lg(\lg^* n)$ or $ \lg^*(\lg n)$?

This definition is extracted from "Introduction to Algorithm, 2nd Edition". The iterated logarithm function We use the notation $\lg^* n$ (read "log star of $n$") to denote the iterated ...
5
votes
2answers
3k views

Maximization with xor operator

Few days ago i found task : with given N numbers only one of those numbers doesn't have pair, which one is it? After hours of surfing the net i found that XOR operator is good for that, because ...