Mathematics Stack Exchange
Mathematics Stack Exchange

Questions tagged [algorithms]

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

An algorithm is an unambiguous specification of how to solve a class of problems. The study of algorithms is the branch of mathematics that specializes in finding efficient solutions (mostly in the terms of time and space complexity) to various computational problems. It often involves combinatorics, number theory and geometry.

The field also includes data structures, computational models and proofs of lower bounds for certain algorithms.

See also and .

11472 questions
70
votes
4 answers

Why does multiplying a number on a clock face by 10 and then halving, give the minutes? ${}{}$

My daughter in grade 3 is learning about telling time at her school. She eagerly showed me this method she has discovered on her own to tell the minutes part of the time on an analogue clock. I wasn't sure at first because I have never heard about…
Sabeen Malik
  • 657
19
votes
1 answer

reverse (left) arrow in an algorithm?

There is a algorithm, in which author has written steps of algorithm like this, 1.initialization:set up the threshold (th) and maximum iteration number, $I$. $i\leftarrow 0$ 2.calculate x while (x>th) do $i\leftarrow i+1$ ... end while what does…
user2888999
  • 337
18
votes
3 answers

Reducing the time to calculate Collatz sequences

I am solving the classical problem of calculating for which number in an interval $[a,b]$ the Collatz sequence takes the most steps to reach $1$. Is there an algorithm that needs less than $\cal O(n)$ time, to calculate the number of steps to reach…
FUZxxl
  • 9,307
15
votes
2 answers

RGB to HSV Color Conversion Algorithm

I'm a programmer looking to build an RGB to HSV color converter. I found an algorithm, but I have very little mathematical background and I'm not quite sure what's going on with it. A step-by-step breakdown of exactly what is happening would be…
jpppp
  • 153
13
votes
2 answers

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 logarithm, which is defined as follows. Let $\lg^{(i)} n$ be…
NonalcoholicBeer
  • 7,211
11
votes
2 answers

Calculating the shortest distance between n number of points on a scatter graph

This has been bugging me for about two weeks now.. I have a cartesian plane with n number of points randomly placed on it. You can get the coordinates of each point. Now, how do you calculate the shortest distance to connect all of them. ie. A to D…
Rijnhardt
  • 213
11
votes
2 answers

Knuth's mastermind algorithm

I read the other thread regarding Knuth's algorithm and mastermind but I still do not understand quite how it would be implemented. I am confused by the language or my brain is just broken (or both). I understand that you start with a list S of all…
auxwalter
  • 113
10
votes
1 answer

Finding XOR of all subsets

Moderator's note: this is an on going contest problem. Per usual protocol the answers have been hidden and the question is locked until the end date of the contest. (21.03.2014) Given a list containing N integers, How to find the XOR_SUM of all…
user3001932
  • 1,056
10
votes
2 answers

Non-revealing maximum

How can a group of people find out their maximum age without revealing any other information to each other? (Is there a book or web site about such non-revealing algorithms?) Preferably I'm looking for a solution which works for large (e.g. 64-bit…
pts
  • 607
9
votes
5 answers

Does a 15-puzzle always have a solution

For those that are not familiar with (this type of) sliding puzzles, basically you have a number of tiles on a board equal to (n * m) - 1 (possibly more holes if you want). The goal is to re-arrange the tiles in such a way that solves the…
MxLDevs
  • 201
  • 1
  • 2
  • 4
9
votes
2 answers

Can you help me to solve the recurrence relation $T(n) = T(\sqrt n) + 1 $?

I have this recurrence relation to solve : $T(n) = T(\sqrt n) + 1 $ I have tried to expand the recursion but I stopped here: \begin{align} T(n) &= T(n^{\frac12})+1\\ &= T(n^{\frac14})+1+1\\ &\text{after $i$ replacements I have}\\ &=…
user1868607
  • 939
8
votes
3 answers

"Closest pair of points" algorithm

I'm having a problem understanding why I just have to consider the next 7 points in the Closest pair of points - algorithm. Can someone explain it in greater detail?
user11775
  • 333
8
votes
3 answers

Tips for constructing basic loop invariants?

One of the topics that I've struggled to grasp the most in my basic computer theory course is that of making a loop invariant to prove correctness of an algorithm. Even with what should be fairly straightforward algorithms, I just don't really…
Mana
  • 749
8
votes
2 answers

A fast way to generate cyclic strings with few restrictions?

I need an algorithm to produce all strings with the following property. Here capital letter refer to strings, and small letter refer to characters. $XY$ means the concatenation of string $X$ and $Y$. Let $\Sigma = \{a_0,…
Chao Xu
  • 5,768
7
votes
2 answers

Grouping numbers that are "close to each other"

Let's say you have a set of numbers S and you want to obtain subsets of $S$, $s_1,s_2,\ldots, s_i$, where $i < N$. Is there a particular operation that will group the numbers that are "close to each other"? I will give an example to clarify the…
chaimp
  • 173
1
2 3
…
64 65