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).

Filter by
Sorted by
Tagged with
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 ...
12345's user avatar
  • 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 ...
Marlon Brando's user avatar
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 ...
anon60707's user avatar
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 ...
Lifeni's user avatar
  • 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.
Raj Ishu's user avatar
-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 ...
Bryan C's user avatar
  • 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 ...
Vincent J. Ruan's user avatar
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 ...
Charlie's user avatar
  • 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 ...
Robert Williams's user avatar
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 ...
Lifeni's user avatar
  • 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$ ...
Gator's user avatar
  • 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 $ ...
jeremie bergeron's user avatar
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 ...
Dirk's user avatar
  • 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 ...
Eric Chen's user avatar
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 ...
Becker's user avatar
  • 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\...
Ninaaaaa's user avatar
-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 ...
Cerise's user avatar
  • 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 ...
Hippopotoman's user avatar
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 ...
Alex I's user avatar
  • 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}...
Mzq's user avatar
  • 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 ...
埃博拉酱's user avatar
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 (...
Michel H's user avatar
  • 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 ...
Benjamin Wang's user avatar
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 ...
Pumbaa's user avatar
  • 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 ...
off oof's user avatar
  • 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 ...
Typhaon's user avatar
  • 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$ ...
Shobhit Tewari's user avatar
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) ...
stack.tarandeep's user avatar
-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 ...
smilly's user avatar
  • 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 ...
raphitek's user avatar
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 ...
Mathematician....'s user avatar
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) ...
Shaggy's user avatar
  • 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 ...
Raman's user avatar
  • 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 ...
Ralph 's user avatar
  • 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 ...
JCW's user avatar
  • 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 ...
Jason M Gray's user avatar
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 ...
Bryan C's user avatar
  • 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 "...
grey bear's user avatar
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 ...
maplemaple's user avatar
  • 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 ...
maplemaple's user avatar
  • 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{...
V. Jackson's user avatar
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 ...
Andres's user avatar
  • 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 ...
gr8's user avatar
  • 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 ...
user123's user avatar
  • 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)(\...
Eli Bixby's user avatar
  • 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) ...
alati ahmad's user avatar
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 <...
ManyCookies's user avatar
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 ...
thunderbird30's user avatar
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 ...
Math Attack's user avatar
  • 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 ...
thunderbird30's user avatar

1
2 3 4 5
226