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
14 views

Finding best local axis system of a set of points

I’m looking for a way to find the best axis system for a set of points and its tessellation – triangles, linking points to each others. The idea is that I’d like to orient a mesh using that axis ...
0
votes
0answers
15 views

How to find the best-case and average-case number of comparisons performed by a comparison tree?

So I'm reviewing some material before a midterm tomorrow and I came across this question: ...
0
votes
1answer
22 views

Polygon Equal Edge Offsetting?

If I have a random polygon of any complexity, be it a square or an irregular 20 sided polygon, how can I scale this up? I know the coordinates of each point on the polygon, but that is all. Another ...
0
votes
1answer
18 views

Implementing a function whose representation has a singularity.

$\newcommand{\R}{\mathbb R}$ Suppose I want to calculate the value of a continuous function $f\colon(a,b) \to \R$, with $a,b\in\R$, where there are functions $g,h\colon (a,b)\to\R$ such that for ...
0
votes
0answers
14 views

Algorithm to get the maximum size of n rectangles that fit into a rectangle with a given width and height

I have the same problem like this guy here, except that I need to change the algorithm posted there to calculate rectangles instead of squares, because I use this to calculate a grid of icons (square ...
0
votes
1answer
32 views

scientific computing problem, error analysis and writing algorithm

For $f(x)=(1-\cos(x))/x^2$, (a) Analytically evaluate $\lim_{x→0} f(x) = L$. (b) As $x→0$, at what rate does $f(x)→L$? (c) Suppose that we are able to represent floating point numbers with $N$ ...
0
votes
1answer
39 views

Proof strategy for propositional logic algorithm

I have to proof the following theorem: Proof that $\eta_1 \vee \eta_2 \equiv DISTR(\eta_1, \eta_2)$. The algorithm DISTR($\eta_1, \eta_2$) is the following: Now I want to use induction to ...
0
votes
0answers
22 views

Clarification about mutually orthogonal latin squares

This question is related to my previous one but different in its substance. I have a several questions that I am not able to find answers to. My understanding of mutually orthogonal latin squares is ...
0
votes
0answers
26 views

Find minimum of the sigma

Is there any polynomial algorithm to finding ${x_1,x_2,\dots,x_n}$ for fixed $a_{i,j},p_{i,j},g_{i,j}$ such that minimize $\sum p_{i,j}c_{i,j}$ where : $a_{i,j}+x_i-x_j\equiv c_{i,j} ...
0
votes
0answers
15 views

Want to factorize one matrix into three, with L1 regularization, which optimization algorithm to choose?

I need to factorize one matrix $R$ into three component: $ R = P^TAQ $, in which I want to apply L1 regularization on $A$ to encourage sparsity, and apply L2 regularization on $P$ and $Q$ to prevent ...
0
votes
0answers
28 views

The complexity of bubble sort and insertion sort for a list with a given number of inversions

Let the length of a list be $n$, and the number of inversions be $d$. Why does insertion sort run in $O(n+d)$ time and why does bubble sort not? When I consider this problem I am thinking of the ...
0
votes
0answers
7 views

Find interval algorithm problem

I have the following arithmetic problem: What is known condition: m,n [a,b) : a mod(m) = 0 , b mod(m) = 0 [x,y) : x mod(n) = 0 , y mod(n) = 0 b < x What must ...
0
votes
0answers
31 views

Calculating the average case complexity for finding the maximum number in an array

Algorithm: Given a non empty array with $N$ Numerical values, the algorithm finds the location LOC and the maximum value MAX of the largest element of DATA. Initialize K:= 1, LOC:=1, ...
0
votes
2answers
38 views

Algorithms for mutually orthogonal latin squares - a correct one?

I am very interested in using mutually orthogonal latin squares (MOLS) to reduce the number of test cases but I struggle to find a way how to implement the algorithm. In an article published in a ...
0
votes
2answers
44 views

Prove or disprove: $g(x) = x^2 - 2x + 1$ monotonically increases for $x > 1$.

I know I can compare $g(x)$ and $g(x+a)$ where $x$ is in the region of interest and $a > 0$, and to expand out the algebra to show that $g(x+a)$ always equals or exceeds $g(x)$ but I'm not ...
1
vote
2answers
93 views

Describe an $O(N)$ time algorithm for determining if there is an integer in a sequence $A$ and an integer in a sequence $B$ such that $x = a + b$

Unfortunately I couldn't make the title for my question long and I didn't really know how to shorten it, so there are some added constraints: Let $A$ and $B$ be two sequences of $n$ integers each, in ...
0
votes
0answers
9 views

How to calculate Weighted Round Robin distribution?

I am trying to workout how to share out apples in multiple baskets in order based on the weight (priority) of each basket. The higher the priority the higher the share of apples a basket gets. ...
1
vote
1answer
14 views

Combining an arbitrary number of integers into one s.th. each can be reconstructed

Let's say I have $k$ integers in the range of $[1,m]$ that I should like to represent as a single integer, such that no two selections of $k$ integers that differ in at least one yield the same result ...
2
votes
3answers
36 views

Finding the prime number $n$: why checking for a divisor between 2 and $\lfloor \frac{n}{2} \rfloor$ is enough?

Let's say I want to check whether 33 (say $n$) is a prime number or not. Instead of checking whether 33 is divisible by a number between 2 and 31 or not, it is sufficient enough to verify that 33 is ...
1
vote
1answer
20 views

Algorithm for factoring large decomposable primes into Gaussian primes

Given a prime $p$ (with residual 1 modulo 4) what is the most efficient algorithm for computing its Gaussian prime factors, assuming $p$ could be large (i.e. perhaps more than 100 bits). ...
2
votes
0answers
36 views

Number of valid sequences!

A sequence consists of 1,-1,2,-2,3,-3. The sequence is considered valid if It's empty If S is a valid sequence the so is "1 S-1","2S-2","3S-3" If S1 and S2 are valid, then so is the sequence formed ...
1
vote
2answers
39 views

How do I solve this problem from graph theory?

Say I have a graph G with n nodes and m edges. Give each edge a capacity. If I am working in discrete time intervals (say days), how do I find the fastest way to move x amount of product from a source ...
1
vote
1answer
37 views

Which way does the Fourier Transform go?

This might be a silly question, but I'm really confused by the way Fourier Transform was taught in my algorithms class, and everything else I found on the internet. The way we defined FT is first ...
0
votes
0answers
14 views

Induction to find string length equivalence

Rewrite system of RRR ≡ NULL, FF ≡ NULL, RRF ≡ FR. Show that each string in {F,R}* is equiv. to one of the six strings: NULL, R, RR, F, FR, FRR. A hint is to use induction and ask if every string of ...
1
vote
0answers
22 views

Shortest path in divisors graph

There is a graph with $N$ vertices numbered from $1$ to $N$. Edge between $a$ and $b$ exists if and only if $a | b$ or $b|a$. If $a|b$ then the weight of the edge is $\frac{b}{a}$. If $b|a$ then the ...
0
votes
0answers
9 views

How to find the K-th thinnest paths in a graph

I'm looking for an algorithm to find the K-th thinnest paths in a directed graph (like Yen's algorithm for shortest paths). By "thinnest" I mean with the lowest weight per edge. For example, in this ...
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
22 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
149 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
25 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
47 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
62 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
66 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
25 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
38 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
41 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 ...