# 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
Filter by
Sorted by
Tagged with
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 ...
1 vote
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 ...
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 ...
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 ...
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.
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 ...
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 ...
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 ...
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
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 ...
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$ ...
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$ ...
1 vote
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 ...
1 vote
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 ...
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 ...
1 vote
63 views

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 ...
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 ...
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 ...
1 vote
21 views

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