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

8,985 questions
Filter by
Sorted by
Tagged with
11 views

13 views

### Does there exist any accelerated algorithm where the rate of convergence is measured in terms of the iterates?

This question is related to this Established results on the convergence rate of iterates for Accelerated Gradient Descent? Consider the problem $$\min_{\mathcal{X}} f(x)$$ where $f$ is convex, ...
24 views

### How does this proof that demonstrate that if $f(n) \in O(n)$ then $[f(n)]^2 \in O(n^2)$ work?

I'm given the following proof but I have problems with it: Suppose that $f \in O(n)$ then by definition there exist $c \in R^+$, $m \in N$ such that $f(n) \geq cn$ for all $n \geq m$. We therefore ...
21 views

### Solve a fraction without any operator in the denominator

(Skip to the last paragraph if you don't want the context) I'm working on a program where I need to deal with big numbers (10,000,000+), and I need fractions. Computers lose accuracy when doing ...
16 views

23 views

### Time taken for a block to slide down a composite slope

Suppose you had a list of numbers that define the y-coordinates of N points in space [y1, y2 ... yn] that are joined up to make a composite "slope" made of various line segments; the horizontal ...
24 views

### Laguerre's method explanation

Can anyone please explain the steps of Laguerre's method? I searched for it but I couldn't really understand them. I am a high school student and things in Wikipedia didn't really help me understand. ...
31 views

### Constructing the divisors from the prime decomposition

I'm searching for a fast method to construct the set of all divisors (for one cell numbers) and since I have a very fast routine to get a list of the prime numbers in the decomposition (Pollard Rho) I'...
11 views

### Can Quadratic Probing Result in Infinite Loop?

I don't know if this question belongs on MSE, but I've had no luck on SO. I understand the definition of Load Factor and how Quadratic Probing works. But what happens in the case where quadratic ...
14 views

21 views

### Carry function definition

I have an algorithm which needs to perform many additions and multiplications. Since am trying to concatenate many numerical values in a big integer variable, i need to make some thoughts about carry ...
54 views

### Algorithm to compute nth root (radical) $\sqrt[n]{p(X)}$ of polynomial

I am making a symbolic computation library which supports symbolic polynomials (both univariate and multivariate) and among other things I would like to support (possibly truncated) nth root (radical) ...
39 views

### Show that solution of $T(n)=T(n-2)+2\log n$ is $O(n\log n)$

I am solving this question from solution manual, but stuck at this point: ...
47 views

### If $n$ is coprime to 10, then $1/n$ produces a repeating decimal.

EDIT: I have changed the title (twice). I am getting my terms and symbols jumbled up in my head. I hope that I have asked a clear question now. Here are three statements that I believe to be true, ...
14 views

29 views

### Write an algorithm to find a path that traverses all edges of directed graph G exactly once… [duplicate]

...You may visit nodes multiple times, if necessary. Show the run time complexity of your algorithm. This graph is not necessarily strongly connected, but starting from a node there should exist such ...
15 views

### Finding an algorithm that after removing k edges we get an acyclic graph

Assuming there's an algorithm that can decide belonging to ACYCLIC in polynomial time. How can I use this algorithm in another algorithm that upon the input of a directed graph and a positive number k,...
22 views

### Find the probability that the 2nd and 3rd order statistics are compared in the QuickSelect algorithm

A description of QuickSelect: In the selection problem, we have a list of numbers and want to find the ith order statistic. That's the ith smallest value, which is the value such that i-1 other ...
20 views

### Need help on algorithm homework which is a probability theory problem

I've got an algorithm homework and it looks like a pure probability problem, I currently got stuck on solving it. I'll rephrase it to an easier-to-understand problem and show where I am struggling. ...
130 views

### given points in coordinate axes,find the number of right angled triangles that can be formed

My approach:- I separated the x coordinates and y coordinates in 2 separate arrays..then i used the idea of pythagoras theorem by selecting three vertices(1 from x axis and 2 from yaxis and vice versa)...
35 views

### Find a function which grows slower (but not by a polynomial factor slower) than $n^{\log_27}$

So if I divide $f(n) = n^{\log_27}$ by $log_27$, it should be growing slower than $f(n)$ (and still not by a polynomial factor). $g(n) = f(n)/\log_27$ Is my assumption true? If not what should I do ...
24 views

### Discrete Kalman Filter Algorithm

Can someone explain me the chapter 4.1.4 The Discrete Kalman Filter Algorithm in the pages 22 upto 24 in th Link below: https://www.cs.unc.edu/~tracker/media/pdf/SIGGRAPH2001_CoursePack_08.pdf I ...
25 views

### small-omega notation : $\omega(1)$

Q) For parameters $'a'$ and $'b'$ both of which are $\omega(1)$, Now, consider the recurrence $T(n) = T(n^{\frac{1}{a}}) + 1$ with base condition $T(b) = 1$ then $T(n)$ is ? Here, I am not getting ...
35 views

### Algorithm to adjust the impact of quantity

I have the problem specified here. After some research I have found this approach to overcome the issue. What about having a scaling factor to adjust the impact of quantity (total) of individual ...
40 views

### Infinite binary strings that are “geo guessable”

This is sort of inspired by the game “geo guesser” where you are placed on the surface of the earth and you have to recognise where you are on the planet. I have been considering something like this ...
21 views

### How to write formula to count the signal

I am stuck with two questions. I need to write the formula for generation of a coil(it's a term i am using but can also be taken as x) on my sensor basis i.e if the sensor is on and the force is ...
43 views

### Recurrence using Master Theorem and Back-Substitution

Q) For parameters 'a' and 'b' both of which are $\omega(1)$, Now, consider the recurrence $T(n) = T(n^{1/a}) + 1$ with base condition $T(b) = 1$ Then $T(n)$ is : I am not getting the meaning of ...
7 views

### Searching triplets from two arrays

Given two arrays a and b of size 10^6. I have to choose one element from a and two elements from b such that. a[i] * a[i] = b[j] * b[k]. How do I count all these ...
22 views

### (Functional) space of all lambda types (algorithms)?

The most simplest notion of the algorithm is some kind of function with input and output. Input and output can be very sophisticated mathematical objects (not only numbers), but the is irrelevant, ...
22 views

### minimal vertex cover and P=NP

could someone please explain to me why the following occurs? let function f be a function that finds the minimal vertex cover. meaning: f(G,v)=minimal vertex cover that v belongs to (the graph is ...