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
1
vote
0answers
11 views
Lower bound for Merge Sort running time
I'm trying to prove that the recurrence $T(n)=2T(\left \lfloor \frac{n}{2} \right \rfloor) + n$ is in $\Omega(n \log_2 n)$.
Here's my attempt: Suppose there is some $c>0$ and a positive integer $...
0
votes
0answers
7 views
Transforming one extreme point on the face of a polytope to another
A function $f:2^{[n]} \to \mathbb{R}_{\geq 0}$ is said to be submodular if for each $A, B \subset [n]$, $f(A)+f(B) \geq f(A \cap B) + f(A \cup B)$. An equivalent characterization is that $f$ is ...
0
votes
0answers
30 views
Can someone explain what does log n in $O(\text{log } n)$ mean? I want a deeper explanation.
When I ask this question I'm usually given the response that when you see $O(\text{log } n)$ that means the problem is continually halved.
I want to understand why is this case? Maybe add some ...
1
vote
0answers
26 views
“Deep” mathematical results used in computer-generated imagery
I've been asked by a student if Perlin noise or Marching cubes algorithm could be a good topic for a mathematical project (to study and present some mathematical results). I've looked into the two, ...
0
votes
0answers
21 views
difference between intersecting, weakly and crossing supermodular functions
Am reading some texts on algorithms and I am confused with the differences between these definitions I read in several texts.
Given a set $V$, we have these types of set functions $f:V \rightarrow \...
1
vote
0answers
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, ...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
0
votes
1answer
16 views
Can someone explain me how it's possible to have $bf(n) \in O(f(n))$?
I'm looking up the definition of a smooth function which is composed of two parts:
The function must be eventually non-decreasing.
That $bf(n) \in O(f(n))$ must hold true for $b > 2$ and $b \in ...
0
votes
0answers
15 views
How to solve a homogenous recurrence with a characteristic polynomial of degree 4?
We have the following recurrence:
$t_{n}=\begin{cases}n\\ 2t_{n-1}-2t_{n-3}+t_{n-4}\end{cases}$
if $n= 0$ or $1$ then $t_n = n$ else it's $2t_{n-1}-2t_{n-3}+t_{n-4}$.
The homogenous recurrence is $...
0
votes
0answers
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 ...
0
votes
1answer
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.
...
-1
votes
0answers
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'...
0
votes
0answers
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 ...
1
vote
1answer
14 views
Limitation of comparing functions using asymptotic notation?
I am studying Algorithms on my own from the CLRS book, i.e. Introduction to Algorithms by Cormen etc. I need help to understand some math in the book.
The book says that the functions $$ n $$ and $$ ...
0
votes
2answers
33 views
How to smoothly transition from start number to end number with a certain amount of numbers?
How would I transition from number to number smoothly, for example: Lets say I have a starting number of 3, and a ending number of 34 using only 8 numbers.
How would you make a formula to transition ...
-2
votes
0answers
36 views
How to assign value 1-10 for Spending Habits? [closed]
I am trying to figure out how I can assign a number (1-10) to n-amount of people who are making purchases and spending money. Lets say there are specific purchasable packages, like in-game currency. ...
-1
votes
1answer
33 views
How to Assign a Value 1-10 Over Thousands of Entries??
First, I am not a mathematician. So, have patience with me please. I want to be able to assign a number (1-10) to n-amount of people, based on a given action. If that person does less of that action, ...
0
votes
1answer
24 views
Why is this assumption correct in Laguerre's method?
From Wikipedia:
We then make what Acton calls a 'drastic set of assumptions', that the root we are looking for, say, $x_1$ is a certain distance away from our guess $x$, and all the other roots are ...
1
vote
0answers
9 views
Can someone explain the proof for table expansion when we increase the expansion by tripling instead of doubling?
There is this proof where we have a table that can contains n elements. Each time we completely fill this table we want to transfer the elements to another table where the new table has double the ...
0
votes
1answer
38 views
What is the difference between $O(n + \log n)$ and $O(n + n/2)$?
I've learned that when we see O(log n) we consider that a given problem is halve every time. So having O(n + log n) would be that we first iterate n times once and then the problem is continually ...
0
votes
1answer
40 views
What is an optimal algorithm for dividing N stones into equal piles?
What is the best known algorithm for dividing a string of arbitrary integer length into equal pieces of integer length greater than 1?
In other words if integer N is expressed in unary as N 1's, is ...
2
votes
1answer
36 views
Determining whether an element of a free product of cyclic groups is a commutator.
Let $G=C_{n_1}*\cdots*C_{n_k}=\langle a_1,\cdots,a_k\mid a_1^{n_1}=\cdots=a_k^{n_k}=1\rangle$ be a free product of finitely many finite cyclic groups. Given a word $g=g_1\dots g_n\in G$, is there an ...
0
votes
0answers
19 views
Algorithm to find a random non-negative vector in a given subspace
Given the basis vectors of a subspace, how can I come up with an algorithm to randomly output a vector in this subspace that has all non-negative components.
One idea I have had is to use a weighted ...
0
votes
1answer
24 views
Using Master Theorem when there are more than 1 elements in the f(n)
I'm trying to figure out how you would apply the Master Theorem to these two cases:
$$
\begin{split}
T(n) &= 2 T(n/2) + n \log(n) + 3n\\
T(n) &= 2 T(n/2) + n (\log(n))^2
\end{split}
$$
I have ...
0
votes
0answers
8 views
Optimal substructure of rod cutting?
How do you show the optimal substructure of the rod cutting problem(defined as in https://cs.stackexchange.com/q/97674). I am trying to follow the guideline steps
So suppose someone told us one of ...
2
votes
0answers
14 views
When Alternating Optimization Converges
Let $f(x,y)\mathbb{R}^d\times \mathbb{R}^n\rightarrow [0,\infty)$. Fix $x_0 \in \mathbb{R}^d$ and $y_0 \in \mathbb{R}^n$ every $n \in \mathbb{N}, n>0$ define the sequence iterative
$$
\begin{...
0
votes
0answers
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 ...
0
votes
2answers
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) ...
0
votes
3answers
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:
...
1
vote
2answers
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, ...
0
votes
1answer
14 views
Meaning of f[u] in DFS algorithm
I wonder what the $f[u]$ row means here, in this table that represents the DFS algorithm of the following graph.
I know $u$ is the order of visit of each node, $d[u]$ the cumulative time needed, and $...
0
votes
0answers
23 views
repeating decimals and carmichael function
Wikipedia states here:
For an arbitrary integer $n$ the length $\lambda (n)$ of the repetend
of $1/n$ divides $\phi (n)$, where $\phi$ is the totient function.
In the next section, it defines $\...
0
votes
0answers
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 ...
1
vote
1answer
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,...
2
votes
1answer
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 ...
0
votes
0answers
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.
...
-1
votes
0answers
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)...
0
votes
2answers
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 ...
0
votes
0answers
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 ...
1
vote
0answers
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 ...
1
vote
1answer
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 ...
2
votes
1answer
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 ...
-1
votes
0answers
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 ...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
1
vote
1answer
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, ...
0
votes
1answer
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 ...
-2
votes
0answers
37 views
Create any number with using 1,…,8 or 9 [closed]
I'm trying to create any natural number with just using operators and one digit multiple times.
The number and digit is given.
Allowed operators are: +; -; *; /
You can use brackets as well
...
0
votes
0answers
4 views
How can one prove BSpline results in monotonic function for a monotonic data set? [closed]
I don't understand BSpline in depth but I understood that the Bspline algorithm smoothly fits through a set of data points.
Is there a proof that shows a set of monotonic data sets will result in a ...
