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).
11,288
questions
0
votes
0
answers
14
views
Efficient algorithms to detect connected components
I am reading the book "Computational Homology" by Tomasz Kaczynski, Konstantin Mischaikow and Marian Mrozek and in several places it says something to the effect of "of course, from the ...
- 177
1
vote
1
answer
21
views
Big-O Notation of $\sum_{i=1}^{n} c \cdot x_i$ vs. $c \cdot \sum_{i=1}^{n} x_i$
We have the following two algorithms and need to determine the big O-notation:
Algorithm 1
$$ \sum_{i=1}^{n} c \cdot x_i $$
Algorithm 2
$$ c \cdot \sum_{i=1}^{n} x_i $$
Although I studied the topic ...
0
votes
0
answers
41
views
Finding the Recurrence Relation of a Method
The answer key states this algorithm is O(log n). I was expecting the recurrence relationship to be T(n) = 2T(n/2) + 2, therefore, the answer key renders my hypothesis as false.
Question: How is this ...
0
votes
1
answer
49
views
Differential privacy- New mechanism that outputs true value with a higher probability
Data comes from the set $X = \{A, C, G, T \}$. Suppose we encode values in X as 2-bit strings, i.e., consider $X = \{ 00,01,10,11 \}$. Consider a mechanism $M(x)$ that for input $x \in X$ uses the ...
- 566
-3
votes
0
answers
26
views
Solving the recurrence relation $\,T(n) = n T(\sqrt n) + n$.
$$T(n)=\begin{cases}2, & \text{if } \, n\le2,\\
nT(\sqrt n) + n, & \text{if } \, n>2 \end{cases}.$$
I have tried it but at last, it is getting very complex. Please help me in solving this.
- 7
-2
votes
0
answers
33
views
Seeking Guidance on Calculating $\phi$ for RSA Encryption
I'm in need of assistance with understanding the process of calculating $\phi$ for RSA encryption. I know that we use the formula:
$$\phi(n) = (p - 1)(q - 1)$$
where ( n ) is the product of two prime ...
- 35
0
votes
0
answers
39
views
How to find out a particular set of permutations cannot generate the whole symmetric group $S_n$
The question is more about the algorithmic side of things. I figure this not-too-inefficient algorithm (if any) in a way is the flip side of the Schreier–Sims algorithm that checks membership of any ...
- 763
2
votes
1
answer
58
views
Identify $d$ heavy coins where $d$ is unknown.
You are given $N$ coins which look identical (assume $N = 2^k$). But actually some of them are pure gold coins (hence are heavy) and the rest are aluminum coins with thin gold plating (light). You are ...
- 165
0
votes
1
answer
31
views
Using Big Oh to prove $f(n)+k$ is $O(g(n))$
Let $f(n)$ and $g(n)$ be positive functions such that $f(n)$ is $O(g(n))$ and $g(n) \ge 1$ for all
$n \ge 1$. Using the definition of “big Oh” show that $f(n) + k$ is $O(g(n))$, where $k > 0$ is ...
1
vote
1
answer
111
views
differential-privacy: show $\epsilon$ -differentially privacy
In this problem we consider a sensitive dataset $x \in \{−1, 1\}^n$. We consider the bounded setting where neighboring n-dimensional datasets differ in one coordinate. $A$ mechanism is available that ...
- 566
0
votes
0
answers
48
views
Ordering algorithms from slowest to fastest
Given functions:
$2^{\lg n} \lg n$
$2^{1000}$
$\lg \lg n$
$n / 1000$
$2^{2^{n}}$
$\lfloor\sqrt{n}\rfloor$
$n^{0.0001}$
$\ln \left(\ln ^{2} n\right)$
$4^{n}$
$\lg ^{100} n$
$n \lg n$
$n \log _{4} n$
...
- 1
0
votes
0
answers
30
views
Isolate variable when rounding
My goal is to isolate frame from this equation:
$$ ms = round(frame * {1\over fps} * 1000) $$
$$ ms \in \mathbb{N} $$
$$ frame \in \mathbb{N} $$
$$ fps \in \mathbb{R+} $$
Note: $ round(0.5) = 1 $
...
- 101
1
vote
2
answers
243
views
Simple iterative method to solve $X-\alpha X^{-1} = A$?
The is a simple iteration to compute $A^{-1}$ by applying Newton's method to
$$X^{-1} = A,$$
namely the iteration
$$X_{n+1} = X_n(2I - AX_n).$$
Is there is similarly simple iteration to solve the ...
- 11.6k
1
vote
1
answer
123
views
Prove or disprove big-O asymptotic notation
1.Let $f_1(n),f_2(n)...f_n(n)...$be an infinite series of functions. $f_i(n)$ belongs to $O(n)$ for all $i$. Let $g(k)= \sum_{j=1}^kf_j(j)$ (i.e. $g(1)=f_1(1),g(2)=f_1(1)+f_2(2)$) then $g(n)$ belongs ...
0
votes
1
answer
94
views
Can we generate a valid $9\times 9$ sudoku using this algorithm?
Begin with a board of $9*9$ cells, each of the cells has no value but is possible to contain a number from $1$ to $9$ (I will call the numbers can be assigned to a cell is guesses; the amount of ...
- 93
1
vote
0
answers
63
views
Solving $T(n) = T(n/2) + T(n/3) + n$
Show that the solution to the recurrence relation
$$T(n) = n \;\;\;\;\text{ for }\; n=1,2$$
$$T(n) = T(n/2) + T(n/3) + n \;\;\;\;\text{ for }\; n > 2$$
is $O(n)$ using substitution.
$$T(n) \leq c\...
- 11
-3
votes
0
answers
78
views
Need help on developing a algorithm for encoding a color with less than 24 bits.
The RGB encoding uses 3 8-bit numbers to encode any color , however I suspect that we may need even less than 24 bits.Here are my thoughts so far.The first number will tell the GCD of the values of ...
- 23
0
votes
0
answers
10
views
Isomorphism of a tuple to maximize similarity to another tuple
I have two tuples, both with N values consisting of K unique values. Both tuples are similar. For example,
A = (1, 1, 0, 0, 2, 2, 2, 2)
and
B = (0, 0, 2, 2, 1, 1, 1, 1)
are both similar, and an ...
2
votes
0
answers
74
views
How to solve linear system starting from approximate solution?
I need to solve a linear system $Ax=b$ many times (billions), each time with small changes in A and b from the previous time. The solution can be approximate, but it needs to be very fast: if $x$ is ...
- 173
0
votes
0
answers
34
views
Show for some n Fermat’s method is faster than reverse trial division
One way to find a nontrivial
divisor of n is Fermat’s factorization method:
Suppose that we have an odd number n > 1 which we know is
composite and not a perfect square.
Calculate $\lfloor \sqrt{n}...
- 182
1
vote
1
answer
60
views
A shuffling algorithm that limits the number of consecutive repetitions?
This question comes from Stack Overflow. I feel that we need more of a mathematical breakthrough, so I forward the question here.
I also found a similar problem that seems to be a special case of this ...
- 11
0
votes
0
answers
13
views
Traversing a binary-tree (heap) data structure (Iteration over pointers to nodes)
I am currently working with heaps and figuring out the details of how they work in a more implementation specific way - still, fairly theoretical/conceptual, without going into the intricacies of (...
- 250
8
votes
0
answers
210
views
Count permutations with given longest increasing subsequence
Problem: Given $n \in \mathbb{Z}_+$ and a set $A \subset \{ 1,\ldots,n \}$ sorted in ascending order, find the number of permutations $\sigma \in S_n$ such that $A$ is a longest increasing subsequence ...
- 3,215
0
votes
2
answers
51
views
Finding the minimum value of K for non-repeated sums
Given a set $A$ containing 10 positive integers, with the largest element denoted as $K$, we calculate all possible sums of elements from set $A$, including sums of 2, 3, 4, and so on, up to all 10 ...
- 143
1
vote
1
answer
27
views
Counting Number of Closed Spaces Formed in a Shape upon Cutting along Known Line
Given a 2-D Shape and the positions of the vertices, or the nature, of this 2-D Shape, on which $n$ cuts are made, and given the equations for these $n$ lines, and the size of the 2-D shape,
How would ...
- 11
2
votes
0
answers
79
views
Finding all possible valid values of a set based on a list of rules.
I'm working on a programming project and I stumbled into a bit of a problem. I think it's not an impossible problem, but I'm guessing it would involve some math. It would be amazing if anyone can ...
- 121
2
votes
1
answer
121
views
Time complexity analysis of Kruskal's Algorithm
Hello I have a doubt about the time complexity of Kruskal's Algorithm.
Symbols:
$E \implies$ Total number of edges in the graph
$V \implies$ Total number of vertices in the graph
$O \implies$ Big $O$ ...
0
votes
0
answers
36
views
Extracting an element from a circular array using purely algebraic means/function?
Please be patient with this as this might appear a somewhat strange Q.
Given a fixed sized circular array $A_0$ with $N$ elements ($5\leq N$). We can choose any reasonable $N$ (either even or odd) ...
-1
votes
0
answers
24
views
Time-Management Function for Chess Engine [closed]
I am trying to program a function that calculates, how much time the engine should consume for calculating the next move.
It's purpose is to make the engine not lose on time or at least try to avoid ...
- 1
1
vote
0
answers
9
views
Computing the p-rank of Divisor class group for function field
In the context of my work, I am trying to develop an algorithm to factorize some operators on algebraic function fields of positive characteristic $p$. To this end I need to be able to compute ...
- 11
0
votes
0
answers
22
views
Approximation factor for TSP algorithm
The literature that I have reviewed shows examples of calculations of known approximation algorithms such as the Christofides' algorithm for the TSP. However, I have not been able to find information ...
0
votes
0
answers
23
views
Firefighter problem - finding min-cut in capacitated network (Help)
As my final project my colleagues and I chose to research the firefighter problem.
We could really use your help in the section of MIN-BUDGET regarding the DirlayNet (Directed layered network) ...
- 1
4
votes
0
answers
48
views
Is there an algorithm to check whether given subgroup contained inside the Frattini subgroup?
I am new to algorithmic group theory. I have the following question:
Let $G$ be a group. The Frattini subgroup of $G$ is the intersection of all maximal subgroup of $G$, denoted by $\Phi(G)$. It is ...
- 135
0
votes
1
answer
62
views
Can an algorithm prove that it produced its own output?
Apologies in advance for my ignorance. I am working on a research question in a different area, and it would be helpful to know the answer to the following question, or even a reference to any such ...
- 31
0
votes
0
answers
45
views
Derivative of Dirac delta
To represent formally the part of an algorithm
if $r \in [0,p (\mathbf{v})]$, set $y = A(\mathbf{v})$; else set $y = B(\mathbf{v})$,
where $\mathbf{v}$ is a vector of parameters and $r$ is a uniform ...
- 668
1
vote
1
answer
42
views
Indexing function for placements of identical balls into distinct boxes.
I am trying to find out if there is a mathematical function which can take n objects and place them in m boxes in a way that is indexed?
For example if I had 3 balls and I wanted them in 4 boxes, the ...
- 111
0
votes
0
answers
22
views
Counting Paths in the XY Plane (Discrete math) [duplicate]
I need help with the following mathematical task:
A particle moves in the xy-plane according to the following rules:
U: (m, n) → (m+1, n+1)
L: (m, n) → (m+1, n-1)
where m and n are integers. I need ...
- 35
1
vote
0
answers
29
views
Counting of Cardinal Trees (Trie) with Degree k and n Nodes [duplicate]
I've been diving into combinatorial problems related to cardinal trees and am trying to ascertain the count of such trees that have a degree k with n nodes. I stumbled upon some leads in "...
- 11
3
votes
1
answer
48
views
Expected Length of Maximum Decreasing Subsequences in Random Sequences
Given $ n $ distinct numbers that are randomly shuffled to form a sequence $ A = [a_1, a_2, \ldots, a_n] $, we select the largest number $ x_1 $ from the sequence. Subsequently, we pick the largest ...
- 1,085
2
votes
2
answers
71
views
Analytic solution for number of paths with length $k$ on an $n \times n$ Chessboard allowing Self-Intersecting?
Consider an $n \times n$ chessboard where the journey begins at the bottom-left corner $(1, 1)$ and concludes at the top-right corner $(n, n)$. How many distinct paths are available that necessitate ...
- 1,085
1
vote
0
answers
48
views
Are there nice inverse functions for the diagonal indexing function $x + (x + y) (1 + x + y) / 2$?
I've been trying to work out nice inverse functions for the x and y coordinate parts of the diagonal indexing function
$$I(x,y) = x + \frac{(x + y) (1 + x + y)}{2},$$
which produces the table
$$\begin{...
- 363
0
votes
0
answers
83
views
Algorithm for non-linear system of equations
I would like some tips in figuring out a good algorithm to find the solution of the following system. Let $\theta$ be a constant in $(0,1)$, let $i,l=1,...,N$, let $a_{l}$ and $b_{i,l}$ be some ...
- 65
0
votes
1
answer
75
views
Prove correctness of algorithm that computes $\lfloor \sqrt{n}\rfloor$
I was looking at exercise 3.29 in V. Shoup's book 'A Computational Introduction to Number Theory and Algebra' (freely available here). The exercise is as follows:
As I'm not very familiar with ...
- 53
3
votes
2
answers
80
views
$\Theta$-notation of the recurrences $T(n) = 3T(n/2 +1) + n$ and $T(n) = 4T(n/2)-4T(n/4)+1$ [closed]
(a) $T(n) = 3T \left ( \frac{n}{2} + 1 \right ) + n$
(b) $T(n) = 4T \left ( \frac{n}{2} \right ) - 4 T \left ( \frac{n}{4} \right ) + 1$
I am really stuck on these two recurrences and finding out ...
- 33
1
vote
0
answers
21
views
Optimal top-k column subset
Let $V$ be a set of vectors over $\mathbb{R}^l$, $l\ge 1$, $\pi_i(V)$ be the permutation of vectors in $V$ such that they are ordered by their $i$th component (descending) in order for $\pi_i(V)(\...
- 113
6
votes
1
answer
74
views
Can a rational number represent the area of square?
Let $r = p/q>0$ be a rational number with $gcd(p,q)=1$.
Is it possible to find a square delimited by pairs of lines ($d_1$, $d_2$) and ($d_3$, $d_4$)
such that :
$d_1 \parallel d_2$ (blue lines) ...
- 99
5
votes
0
answers
173
views
How many Color Balanced sets can you make with n colors?
You have n colors and you make nonempty sets from them. A set of these color sets is color balanced if each color is in the same number of the color sets.
Ex. For <...
- 51
0
votes
1
answer
30
views
How to restrict a graph so that all remaining vertices are reachable from a given set of vertices?
Note: this question is not a duplicate of the following questions:
How to remove vertices from a graph that are not coverable by cliques?
How to remove vertices from a graph while preserving clique ...
3
votes
2
answers
118
views
8 planes tangent 3 spheres in the space
I know it might seem like a trivial question, but I think the result is very long and I wanted a consultation to find a "smart" way to solve it without wasting hours of time on unnecessarily ...
- 2,391
1
vote
0
answers
30
views
How to trim a graph while preserving clique coverage of specific vertices?
Note: this is not a duplicate of the question How to remove vertices from a graph that are not coverable by cliques?. That question is asking how we can remove vertices that are not in a clique, and ...