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
0answers
39 views

Divide and Conquer division algorithm explained

I am trying to understand the divide and conquer algorithm that is used in the GMP bignum arithmetic library. The code is very optimised and that makes it somewhat hard to understand. the doc does ...
0
votes
0answers
11 views

What does “4-universal hash function” mean?

I encountered the notion of 4-universal hash function and I cannot understand what exactly it means. This article https://en.wikipedia.org/wiki/Universal_hashing did not really help to clarify it. ...
4
votes
1answer
33 views

What is the most efficient way to find a penny in an empty field?

Let's say that I'm in a rectangular field,2 miles in width and 3 in length, with a metal detector. I know that somewhere within this field lies a penny, which is equally likely to be at any point. My ...
0
votes
1answer
20 views

Showing there exists a sequence that majorizes another

The exact quantity of gas needed for a car to complete a single loop around a track is distrubuted among $n$ containers placed along the track. Show that there exists a point from which the car can ...
0
votes
2answers
39 views

Is $\sum_{i=1}^{n}\frac{f(c\frac{i}{n})}{f(c\frac{i}{n})+f(c-c\frac{i}{n})}=\frac{1}{2}(n+1)$?

So I was trying some code on Octave. The algorithm is the following $$\sum_{i=1}^{n}\frac{f(c\frac{i}{n})}{f(c\frac{i}{n})+f(c-c\frac{i}{n})}$$ for some $n\in\mathbb{N}$ and $c\in\mathbb{R}$. I ...
1
vote
2answers
42 views

How to find the number of possible solutions of LP problems?

Let us assume that we have a linear optimization problem (LP) that has multiple optimal solutions. I would like to know if there is a solver or an algorithm that can provide the number of optimal ...
0
votes
0answers
15 views

Calculating number of permutations of a matrix with elements being adjacent integers only

I'm trying to write a Python code in order to determine the number of possible permutations of a matrix where neighbouring elements can only be adjacent integer numbers. I also wish to know how many ...
2
votes
0answers
44 views

Integrating sine with Monte Carlo / Metropolis algorithm

I'm learning Monte Carlo / Metropolis algorithm, so I made up a simple question and write some code to see if I really understand it. The question is simple: integrating sine over 0 to PI. The ...
0
votes
0answers
25 views

How to calculate explicitly Cheeger constant (also caled Cheeger number or Isoperimetric number)?

I want to calculate explicitly Cheeger constant (also caled Cheeger number or Isoperimetric number) for a graph G(V, E), but I haven't found any sources, algorithms or examples. I'm using this ...
0
votes
2answers
41 views

Programming language used in Berry Nelson's (Stochastic modeling) book

If anyone has read the book "Stochastic Modeling : Analysis and Simulation by Berry L. Nelson", can you tell me in what programming language are the algorithms written in the book? Here is an example ...
0
votes
0answers
30 views

Why is $f = f_{0} + \sum_{i}\alpha_{i}X_{i} + \frac{1}{2}\sum_{i}^{n} \sum_{j}^{n}A_{ij}X_{i}X_{j}$ the standard quadratic form in n dimensions?

The claim that $$f = f_{0} + \sum_{i}\alpha_{i}X_{i} + \frac{1}{2}\sum_{i}^{n} \sum_{j}^{n}A_{ij}X_{i}X_{j}$$ is the standard quadratic form for $n$ dimensions, where $\alpha$ is some $ 1 \times n$ ...
-1
votes
0answers
44 views

combinatorial design

Prove that there is a (7, 7, 4, 4, 2)- design and that is is unique up to isomorphism. (v,b, r, k, lamda) v, number of treatments or primary factor levels. b, number of blocks K, number of treatments ...
0
votes
1answer
36 views

LU decomposition with pivot

I'm trying to LU decompose, with pivoting, the following matrix ($A=(a_{ij})$): A = [2 1 2; 1 0 3; 4 -3 -1]; % matlab I cannot make out from my literature ...
2
votes
5answers
87 views

Quick way to get closed form for this recurrence?

Is there supposed to be a fast way to compute recurrences like these? $T(1) = 1$ $T(n) = 2T(n - 1) + n$ The solution is $T(n) = 2^{n+1} - n - 2$. I can solve it with: Generating functions. ...
3
votes
0answers
48 views

Match off points into $N$ red/blue pairs with straight lines connecting pairs, so that none of lines we draw intersect

Suppose we are given $2N$ points in the plane (we may assume that no $3$ are collinear). Assume that $N$ of these points are colored red, and $N$ points are colored blue. Can we match off the points ...
2
votes
3answers
40 views

Bezout's Identity proof and the Extended Euclidean Algorithm

I am trying to learn the logic behind the Extended Euclidean Algorithm and I am having a really difficult time understanding all the online tutorials and videos out there. To make it clear, though, I ...
0
votes
0answers
19 views

Maximum PopCount (Hamming Weight) XOR Bitmasks

Give a set of bitmasks, what is the maximum hamming weight that can be achieved by combining any subset of them using the XOR operator? For example, if you had the bitmasks {10110, 01110, 00001} ...
0
votes
1answer
17 views

Multi-commodity flow problem. What if only one commodity? (Context: column generation)

What problem can arise when the number of commodities is only one when looking at a multi-commodity flow problem? This question was asked by my professor in the context of column generation and ...
5
votes
1answer
42 views

Number of the form $2^i3^j5^k$ closest to a given number $n$

How do I find a number of the form $2^i3^j5^k$ closest to a given number $n$, with $i, j, k \in \mathbb{N}$ numerically? Of course, I could try $\lfloor \log_2{n}\rfloor \times ...
1
vote
1answer
18 views

analytical hard sphere collision condition with periodic boundary conditions

Hello Stack Exchange Mathematics, I am curious if there is an analytical or efficient numerical solution for the collision of hard spheres in a rectangular unit cell with periodic boundary ...
0
votes
1answer
18 views

Minimal sum of non-consecutive elements

I have $N$ numbers $a_i$. I want to find the smallest sum of EXACTLY $K$ non-consecutive elements. I know how to solve this in $O(N*K)$ (straightforward dynamic programing) but it is too slow. Anyone ...
0
votes
0answers
17 views

Knapsack problem when the weights are equals to 1.

Knapsack problem: Given a set of $N$ items, each with a weight $w_i$ and a value $v_i$, determine the number of each item to include in a collection so that the total weight is less than or equal to ...
1
vote
1answer
24 views

Why is the little o(h) in the Poisson Process dissimilar to other field's?

I learned about little oh notation in Algorithm class last year. $$ \mbox{if } \lim_{n\to\infty}\frac{f(n)}{g(n)}=0 \mbox{, then } f(n)\in o\big(g(n)\big) \mbox{ or } f(n)=o\big(g(n)\big) \mbox{.} $$ ...
1
vote
1answer
30 views

Show that the harmonic series is $\Theta(\log n)$

Show that the harmonic series is $\Theta(\log n)$. This breaks down to show that $\sum_{i=1}^n\frac{1}{i} = \mathcal{O}(\log n)$ and $\sum_{i=1}^n\frac{1}{i} = \Omega(\log n)$. Following the ...
0
votes
0answers
20 views

How do you find the witness in the definition of Big-O notation?

The question is written like this: Use the definition of "$f$(x) is $O$($g$($x^4$))" to show that the statement $x^4+9^3+4(x)+7$ is $O(x^4)$. My understanding of this question is to find the ...
1
vote
1answer
68 views

What is the shortest LOOP program that outputs 2016? [closed]

Use a minor restriction of the LOOP language described under Wikipedia's "LOOP (Programming Language)". The restriction is to eliminate constants. So, the language contains increment: $x_i++$, ...
1
vote
0answers
27 views

Biggest rectangle inside a random geometric shape

I'm looking for the most efficient algorithm to find the rectangle with the greatest area inside a random geometric shape. The rectangle can be also rotated of course. I am sure that there exists a ...
0
votes
0answers
24 views

Result of LexBFS on an outer-planar graph

Suppose we have an outer-planar graph $G$. Is the following expression true? If yes, please prove it. If no, please give a counterexample. After running LexBFS on $G$, we will have a vertex order ...
0
votes
0answers
13 views

Augmenting an algorithm with a monotonic step

Suppose algorithm $A$ is known to converge to the global maximum from any feasible point. I believe it is the case that if I augment $A$ with a monotonically increasing step $B$, then the new ...
1
vote
0answers
45 views

Number of Hamilton paths in an extremely dense undirected simple graph

What is the fastest way (algorithm) to calculate the number of Hamilton paths in an extremely dense undirected simple graph (approximately 99.99% edges are connected)? I was thinking of the following ...
0
votes
1answer
14 views

Determining the time complexity of a double loop

I'm trying to understand why the time complexity of the following loop: for (int i = 1; i <= MAXN; i++) for (int j = i; j <= MAXN; j += i); is ...
1
vote
0answers
29 views

Making sense of Euclidean Algorithm Proof

Hi I need help understanding this proof for the Euclidean algorithm. Specifically I do not understand what long inequality on the bottom means. Does k refer to an iteration?
2
votes
0answers
46 views

Knuth algorithm on constructing a proof

I'm going through mathematical induction section of Knuth's book "The Art of Computer Programming" (pg. 11). I'm having a hard time understanding Algorithm I on constructing a proof. Here is the ...
1
vote
1answer
65 views

Minimizing computations for evaluating two polynomial simultaneously

I want to evaluate two polynomials $f$ and $g$ simultaneously, on the same input (in a computer program). These polynomial have only coefficients $0, 1, a , b$ and their degree is less than 700. I ...
0
votes
0answers
24 views

What's the efficient algorithm to compare (a subset of) algebraic numbers to zero?

Let $\mathbb{X}$ be a set of numbers that are built out of integers using $+,-,*,/$ and $\sqrt[2]{\phantom{x}}$. Let $x \in \mathbb{X}$. What's the efficient algorithm to check if $x = 0$ or $x > ...
1
vote
1answer
33 views

If I have a vector inside a rectangle, how do I tell which side of the rectangle the vector will hit?

I'm trying to solve an issue where I basically have a vector inside of a rectangle. I want to figure out if the vector continues its trajectory, what side will it strike? The vector is given as an (x, ...
0
votes
1answer
71 views

Solving a Rubik's cube in 20 moves or less

Most "cubers" solve a Rubik's cube in about 60 moves, using special algorithms and quick fingers. But any Rubik's cube can be solved in 20 moves or less (cube20.org). Is it possible that there is a ...
1
vote
0answers
28 views

Algorithm to find a number to divide by

I have a following problem. I have a variable $x$, I have a target value $y = 20$ and I have a ...
4
votes
2answers
76 views

Integer Square Root Algorithm

I'm currently working my way through David M. Bressoud's "Factorization and Primality Testing", and I'm struggling with an exercise (exercise 5.7) that asks the reader to prove that the following ...
1
vote
0answers
53 views

Application of algorithm to sequence

I got this puzzle from a professor. Suppose that we have a sequence $a_1$, $a_2$, .., $a_{200}$ $= 1, -1, 0, ..., 0$ where we have $198$ zeros. Now, we perform this algorithm: we replace $a_i$ with ...
0
votes
1answer
19 views

Sorting Algorithm for weakly ordered list

I am aware of some sorting algorithms and there pros and cons but my question is specifically: What is a good sorting algorithm for a list that is generally but not strictly increasing, i.e. 1 5 4 8 5 ...
1
vote
1answer
46 views

Number of Paths in a Graph

I have an undirected, unweighted graph. Let us fix a vertex and find all distinct paths from that vertex which covers all vertices of the graph. The task is to find the number of possible such paths ...
3
votes
1answer
84 views

How many pawns, bishops, rooks or kings can be put on a $n \times n$ chessboard such that they don't threaten each other?

A friend of mine asked me this question and I know this is not easy to solve. I found some informations similar to this question here: https://en.wikipedia.org/wiki/Eight_queens_puzzle; First of all, ...
0
votes
1answer
22 views

Need help in understanding appoximation for heavy hitters problem

I am reading a paper and do not understand the following "We allow the space used by a solution to grow as $1/ \epsilon $, so as $ \epsilon ↓ 0$ the space blows up..." I do not understand the ...
0
votes
0answers
21 views

Efficient curve fitting, and quantum computers

I have a two part question concerning curve fitting to N parameters using computers. First, is the time to find a curve fit to N data points proportional to N or is it worse? Second, is this class of ...
24
votes
4answers
1k views

Is there a branch of Mathematics which connects Calculus and Discrete Math / Number Theory?

I am asking this question out of both curiosity and frustration. There are many problems in computer science which require you to perform operations on a finite set of numbers. It always bothers me ...
0
votes
0answers
76 views

Find number of valid permutations [duplicate]

I have to find the number of permutations of first N natural numbers such that given C conditions should be satisfied. The C conditons can be like this 1 and 2 not occurs consecutively 4 and 5 not ...
0
votes
1answer
37 views

Is this the correct way to calculate probability?

I'm trying to create an AI for a game I develop but I run into the problem of trying to figure out how to calculate probability. The probability I'm trying to calculate is what is the probability ...
2
votes
2answers
83 views

Deriving a formula/algorithm to find all integers with n digits (abcd…) where a+b+c+d… = a × b × c × d…

a+b+c+d... = a × b × c × d... The sum of the digits equals the product of the digits. I'm currently creating a program in c++ where the user inserts a lower limit m, and a upper ...
1
vote
1answer
39 views

Why does the Master Theorem work for this example but not the other?

So apparently: $T(n) = 2T(n/2) + n / \log n$ doesn't work with the Master Theorem because of the log term. But then: $T(n) = 4T(n/2) + n / \log n$ is $\Theta(n^2)$ even though it's still the same ...