All questions with tag [math: algorithms]


Turing reduction

I'm finding out algorithm concept. Research inquiry is: Are $A$ and also $B$ feasible to make sure that $A\not\le_{tt}B$ (difficult to lower making use of tt), yet $A\le_T B$. Yet I can not consider any kind of instance.
2022-07-25 17:47:10

Finding all possible paths from one corner to the other on a grid, without backtracking

Me once more "new to mathematics guy". Please inform me if the material of my inquiries are not an excellent suitable for the website. I'm currently onto and also it feels like there is some mathematical course searching for strategy I need to make use of. Checking out I've located chart and also tree traversal, djikstras fastest co...
2022-07-25 17:46:51

Truth table reduction

I'm finding out algorithm concept and also the educator asked an inquiry that perplexes me. Do $A$ and also $B$ exist such that $A$ is not to $B$, yet $B$ is fact - table reducible to $A$?
2022-07-25 17:42:49

Towers of Hanoi - are there configurations of $n$ disks that are more than $2^n - 1$ moves apart?

This is a workout from Chapter 1 of "Concrete Mathematics". It worries the Towers of Hanoi. Exist any kind of beginning and also finishing arrangements of $n$ disks on 3 fixes that are greater than $2^n - 1$ actions apart, under Lucas is initial regulations? My first hunch is no, there are no beginning and also finishing arrangemen...
2022-07-25 17:21:28

How to evaluate Θ, or O and Ω from function

I have to evaluate the $ \Theta $, $ O $, $ \Omega $. I all the time I thing that: $$ \sum_{k=1}^nk = \Theta(n) $$ Because I have $ n $ steps. But in some papers I have found that: $$ \sum_{k=1}^nk = \frac{n(n+1)}{2} = \Theta(n^2) $$ So I am really confuse can you please clear up? Also why is $ \ln{n!} $ equal to $ \Theta(n \log{n}) $..
2022-07-25 16:42:26

Steiner Tree Approximation

My question is about a subtlety regarding the $2$-approximation for the Metric Steiner Tree problem. The classical Metric Steiner tree problem: Given a metric space on $n$ points and a subset $S$ of the points, find a tree that spans $S$ with minimal total cost. The classical $(2-\frac{1}{n-1})$-approximation: Take a minimal spanning tree on ...
2022-07-25 13:22:53

Time to resolve a problem of size $1000$ in one second, how time take resolve the same problem of size $10.000$ in $n^2$?

A algorithm call for one 2nd to settle a trouble of dimension $1000$ a neighborhood equipment. How much time time take the very same algorithm to settle the very same trouble for a trouble dimension of $10.000$ if the algorithm call for a symmetrical time to $n^2$? I assume that: T (1000) = 1 2nd, yet I do not recognize just how to develop pa...
2022-07-25 13:20:50

Remove every (k+1) th remaining element in kth pass of natural numbers

In the all-natural numbers collection, we've to remove every 2nd component in the 1st pass. After that in the continuing to be components, remove every 3rd component in the 2nd pass. After that at Kth pass, remove every (k+1) th component from the continuing to be components. The collection will certainly go like this 1, 2, 3, 4, 5, 6, 7, 8, 9,...
2022-07-25 13:16:00

n lines in the plane

Given a layout of n definitely long straight lines in the aircraft, allow them converge in the factors p_i, allow the angles at $p_i$ be $v_i^j$, such that $360=\sum_j v_i^j$. Offered the symptomatic layout, and also some angles, if one is offered the job of computing some $v_m^n$, and also the layout and also angles establish this angle distin...
2022-07-25 12:51:21

Determining the equality of two real numbers

Can the equality of two real numbers always be determined? Let us say that we have derived an expression for a real number X. We also have obtained an (entirely different) expression for a real number Y. Now one mathematician claims that X and Y must necessarily be exactly equal. Another mathematician claims that X and Y can not be equal, howev...
2022-07-25 12:35:38

Adapted Towers of Hanoi from Concrete Mathematics - number of arrangements

I have a doubt concerning an exercise from Chapter 1 of "Concrete Mathematics". Actually, my doubt is in one exercise (exercise 3), but, since it depends on the previous exercise (2), I'm including it here too, with the respective solution that I found. Yes, I know that I could simply check the answer in Appendix A, since "Concret...
2022-07-25 12:32:00

Basic classifier for numeric dataset

I have a set of training information and also I require to construct a classifier with it. There are simply 2 courses of components, and also the values of the features are all integer, like: $$ \ [V_{11}, V_{12}, \ldots, V_{1N}] \in C_1 \\ \ [V_{21}, V_{22}, \ldots, V_{2N}] \in C_2 \\ \vdots \\ \ [V_{M1}, V_{M2}, \ldots, V_{MN}] \in C_M \\ ...
2022-07-25 07:53:23

Convex hull of balls

The convex hull is defined as the smallest convex set containing a set of points. Now we want to generalize it to a set of balls. If these balls have the same radius, then it can be shown that a ball lies on the boundary of the convex hull of balls if and only if its center lies on the boundary of the convex hull of center. My question is: what ...
2022-07-25 07:46:32

Trying to sort the coefficients of the polynomial $(z-a)(z-b)(z-c)...(z-n)$ into a vector

So I have a factored polynomial of the form $(z-a)(z-b)(z-c)\ldots(z-n)$ for $n$ an even positive integer. Thus the coefficient of $z^k$ for $0 \le k < n$ will be the sum of all distinct $n-k$ element products taken from the set $\{a,b,\ldots,n\}$ multiplied by $(-1)^k$, I hope that makes sense, please ask if you need more clarification....
2022-07-25 07:42:35

how to distribute n red and m blue balls in some containers to maximize probability of random picking a red one from them?

This is a meeting inquiry. Offered n red rounds and also m blue rounds and also some containers, just how would certainly you disperse those rounds amongst the containers such that the probability of selecting a red round is made best use of, thinking that the customer arbitrarily picks a container and afterwards arbitrarily selects a round fro...
2022-07-25 07:36:33

Algorithms for finding closed form approximations for integrals (with no closed form solutions)

It is popular that several integrals have no closed form remedies, generally what you would certainly do is address them numerically. My inquiry is if there are algorithms that offer you excellent closed form estimates rather.
2022-07-24 06:40:58

Calculation of Bessel Functions

I want to calculate the Bessel function, given by $$J_\alpha (\beta) = \sum_{m=0}^{\infty}\frac{(-1)^m}{m!\Gamma(m+\alpha +1)} \left(\frac{\beta}{2}\right)^{2m}$$ I know there are some tables that exist for this, but I want to keep the $\beta$ variable (i.e. I want a symbolic form in terms of $\beta$). If there is a way to simplify the summation...
2022-07-24 06:37:36

Sieve of Atkin - algorithm for enumerating lattice points.

Recently, I've been functioning in the direction of applying the Sieve of Atkin with dramatically far better efficiency than the variation found on Wikipedia. From reviewing the initial paper (, it appears the writer takes a various strategy than Wikipedia: wher...
2022-07-24 03:34:37

Pseudo random number generator: Why not to use "too many" random variables in one application

I found statement in an article "Good Practice in ( Pseudo ) Random Number Generation for Bioinformatics Applications" that you should not use too many random variables in a single simulation. Authors says that it maximum number of random values taken from PRNG should be $\frac{p}{1000}$ or even better $\frac{1}{200}\sqrt{p}$. $p$ is t...
2022-07-24 03:25:48

How to solve the Fast Fourier transform

I am researching algorithms concerning FFT and also I was exercising FFT inquiry inquiry is asking What is the FFT of (1, 0, 0, 0)? What is the ideal value of ω in this instance? And also of which series is (1, 0, 0, 0) the FFT? I read guide for this component yet i really did not actually recognize Can any person clarify the means to ad...
2022-07-24 03:23:42