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)

2
votes
1answer
45 views

Use induction to prove that any (finite) list is a permutation of itself—in other words, that the permutation relation is reflexive.

I'm having a bit of trouble with starting this proof by induction. I'm given that the definition of a permutation is: List a is a permutation of list b if any of the following are true: • list a and ...
0
votes
1answer
23 views

Definition of a Greedy Algorithm

Consider the following optimization problem: We have n skiers with increasing heights $p_1,...,p_n$ and n skis with increasing heights $s_1,...,s_n$. We want to minimize the average difference ...
0
votes
0answers
29 views

Time complexity of $T(n) = 2^n + 2\sum_{i=1}^{n-2} T(i)$

$$ T(n) = 2^n + 2\sum_{i=1}^{n-2} T(i)$$ $$ T(0) = 1 , T(1) = 2 $$ This is my $T(n)$, and I need to find its time complexity. I know the answer is $T(n) = \theta (n2^n)$, but I have a problem with ...
2
votes
0answers
150 views

Factoring semi-primes, convert algorithm to function [closed]

I found an interesting method of factoring semi-primes when I been searching for ways to predict the mod result of given number. The algorithm This algorithm is ...
0
votes
1answer
23 views

Correctly calculating multiple choice

I am developing a program that allows users to make their own Quiz and then send it to their employees. Now one of the elements that i have is multiple choice (or multiple response if you like). ...
0
votes
0answers
18 views

Normalizing income level by offsetting cost of living index

I am attempting to compare disposable income levels but run into problems when comparing groups from different regions since the cost of living is different. I have a list of cost-of-living index ...
0
votes
1answer
66 views

Getting $B$ from $A = M^t B M$ without inverting $M$

I have got three matrices: $A$ (dimension $n \times n$), $B$ (dimension $m \times m$) and $M$ (dimension $m \times n$). We have $m > n$. This is the relation between these three matrices: $A = M^t ...
2
votes
1answer
26 views

Select two non-empty subset such that S1 ∩ S2 = Ø and |ΣS1 - ΣS2| = m? [closed]

Given a geometric series S of 'n' positive numbers with the first term as 'a' and an integer common ratio 'r' (r > 1), you have to decide whether it is possible to select two non-empty subsets S1 and ...
1
vote
2answers
39 views

Set Covering Problem for Weighted Graph

I am looking for solution of the following problem. Let $G$ be a weighted graph with (positive) weights. The length of a path in a weighted graph is the sum of the weights of the selected edges. The ...
3
votes
0answers
48 views

Exact determinant of a circulant matrix

The wikipedia gives us a formula for the determinant of a circulant matrix. That is: $$\mathrm{det}(C) = \prod_{j=0}^{n-1} (c_0 + c_{n-1} \omega_j + c_{n-2} \omega_j^2 + \dots + c_1\omega_j^{n-1})= ...
1
vote
0answers
65 views

Weak, Regular, and Strong connectivity in directed graphs

There are 3 types of connectivity when talking about a directed graph $G$. 1) weakly connected - replacing all of $G$'s directed edges with undirected edges produces a connected (undirected) graph. ...
0
votes
0answers
15 views

C /matlab/ Algorithm for monotonicity of Ploygon

is there any easy and understand able algorithm to check the monotonicity of random polygon and also help me to code in which language(c or matlab) is beneficial to code the algorithm
2
votes
1answer
34 views

Quasi canonical isomorphisms between finite groups and subgroups of the symmetric group?

I'm implementing finite groups in Forth for my blog and since any group is a subgroup of a permutation group it make sense to let the standard elements be permutation schemas: ...
0
votes
1answer
28 views

What is the monotonicity of a polygon? [closed]

What is the monotonicity of a polygon and why is it necessary to check the monotonicity?
0
votes
0answers
9 views

Searching if a value is returned by a function defined for 2-D lattice points

Two functions $f:(x, y) \rightarrow \Bbb N$ and $g:(x, y) \rightarrow \Bbb N$ are defined where $\Bbb N$ is set of positive integers and $x, y \in \Bbb N$. Properties and relations $g(x, y) \ge ...
0
votes
0answers
68 views

Algorithms in formal logic + ZFC

From my understanding, most of mathematics can be built up assuming a mechanical procedure of manipulating finite strings of symbols according to certain rules. A conventional way to do it is via the ...
0
votes
1answer
23 views

Load balance N customers over K servers with different capacities

Let's say we have N customers that supply a stream of requests, but each customer i supplies different number of requests per minute - $R_i$. All requests are identical in terms of the amount of ...
-1
votes
0answers
30 views

Calculating run times of loops with theta notation using summation

When calculating the run time of programs using asymptotic notation, I know how to set up the sums for things like for loops, but I'm getting stuck on summing them up. ...
0
votes
0answers
41 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
45 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
45 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
42 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$ ...
0
votes
1answer
37 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
4answers
89 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
19 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
19 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 ...