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

Determining the minimal number of terms to use in a sum to approximate a number given a tolerance

In page 33-34 of Numerical Analysis by Burden & Faires an algorithm was given to compute the minimal value of $N$ for which $$|\ln{1.5}-P_N(1.5)|<10^{-5}\tag{1}$$,where ...
0
votes
1answer
24 views

ideal number gernerator

I was trying to solve a problem on Hackerearth. Here: https://www.hackerearth.com/problem/algorithm/ideal-random-number-generator/ I solved this partially:https://ideone.com/pXkHwQ (passed three ...
1
vote
1answer
47 views

How do you go about solving this recurrence?

How do you make an estimation for the substitution method, when the recursion tree did not help so much? I have a recurrence $$T(n) = 5\cdot T(n/3) + n (\log n)^2$$ And upon doing the recurrence ...
1
vote
1answer
83 views

Number of binary numbers given constraints on consecutive elements

I've been trying to solve this question for quite a while, given to us by our discrete maths professor. I've been having a hard time in general with it, so I thought I tried looking it up online but ...
0
votes
2answers
32 views

Newton's method for optimization

I have been reading about Newton's method and know that you can use it for optimization problems. However, does Newton's method only guarantee convergence to a local minimum or maximum, or can it be ...
4
votes
1answer
100 views

How to partition $nk$ objects $\frac{1}{n}\binom{nk}{k}$ times, each time making subsets of size $k$, so that no combination of $k$ is repeated.

What is an algorithm to partition $nk$ objects a total of $\frac{1}{n}\binom{nk}{k}$ times, each time making subsets of size exactly $k$, so that no subset of size $k$ is ever repeated? For example, ...
0
votes
0answers
3 views

Convergence in constraint propagation

Introduction To the best of my knowledge, constraint propagation can be thought of (in a very heuristic sense) as a class of algorithms that solve a sort of generalized Sudoku problem. Some initial ...
0
votes
1answer
16 views

an array A[1..N] how many indexes (i,j) are there such that cumulative sum(i,j)%K = 0?

Lets say I have an array A[x1,x2,x3,...xN] of size N. for N = 4 , A = {x1,x2,x3,x4}. [1 based index] Now,I have to tell how many tuples (i,j) are there such that i<=j and cumulative sum(i,j) is ...
2
votes
1answer
23 views

Local Search algorithm: Why is the neighborhood structure $N : S \to 2^S$

I am writing a paper about meta heuristics and in particular local search. My tutor pointed this out: In every source (books, lectures, sites) I looked none explained why it is mapped like that. ...
1
vote
0answers
31 views

how to find out whether a point is surrounded by other points [duplicate]

I want to find out if a point $(x, y)$ is surrounded by a set of points. To understand my problem a short explanation: I am a programmer and I have a function for the user to select objects by ...
1
vote
1answer
22 views

Average case of element comparisons when searching for an element x with a specific probability

I just had a midterm, and unfortunately our professor has stated that he will neither discuss nor post any solutions to the midterm, so I'm posting a question that was on it here in hopes that someone ...
1
vote
0answers
16 views

Applying the convolution theorem in the presence of a twiddle factor

The convolution theorem says that a 2-d cyclic convolution like $C = U \ast V$ can be evaluated more quickly than doing the raw sum $C_{i,j} = \sum_{a,b}^n U_{a,b} V_{i-a,j-b}$ for each point (assume ...
-2
votes
0answers
14 views

Parallel Luby Algorithm för finding Maximal independent set

This the Algorithm of Luby: MIS Luby Algorithm This Algorithm at the end spent O(log n). I want to understand why exactly O(log n), I need also a mathematical prove of this. Also How many ...
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
16 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
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
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
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. ...