Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [mathematical-analysis]

Questions related to mathematical analysis (often called analysis by mathematicians)

2
votes
0answers
27 views

The equation for how much data is produced every period [closed]

I am trying to find out how much data we produce to project how much we will produce in the future. I find stuff like this and this: There are 2.5 quintillion bytes of data created each day at our ...
7
votes
4answers
108 views

What is the depth of recursion if we split an array into $\log_2(n)$ with each recursive call?

We have a function which takes an array as input. It breaks an array into $\log_2(n)$ parts with equal sizes where $n$ is the size of the subarray. It keeps breaking each of the subarrays until there ...
3
votes
1answer
30 views

Fixed point of hash

Are hashing algorithms constructed to guarantee that no fixed point exists? My assumption is not, because I don’t see what utility that would have. (Please correct me if I’m wrong.) As such, purely ...
1
vote
2answers
53 views

Is $f(cn)$ always $O(f(n))$ for constant $c$ and any function $f$?

This seems to be true for any function I can think of, but I'm not quite sure how to prove it. Is there a proof of this proposition for any such function or a counter-example?
1
vote
1answer
37 views

Real RAM computational mode

Given a real value $M>0$, I want to compute the greatest value of $\epsilon$ strictly smaller than $M$. Given the assumption that the computational model is Real-RAM, how to find a real number ...
5
votes
1answer
110 views

Complexity of computing the antiderivative of a given function

Disclaimer: I don't know much computational complexity theory. I am nevertheless curious. If function $f(x)$ has a certain level of computational complexity (which I actually don't know how to ...
1
vote
2answers
140 views

What is the exact definition of undirected graph, directed graph, unidirectional graph, bidirectional graph? [closed]

I've read many literature papers, but I still cannot understand their exact formalization definitions. Is their any difference among them or is there any relationship among them?
1
vote
1answer
244 views

Average number of comparisons in sorted insertion

The questions is pretty simple: Given a sorted array of N elements, what is the average number of comparisons made in order to add a new element (let's call it x) in its correct position? I am using ...
0
votes
0answers
49 views

Math behind path tracing

I seem to remember seeing somewhere (many years ago) a writeup of the math behind calculating the outline of Metafont glyphs. The basic idea is you have a "pen" that is a circle or oval, that you ...
4
votes
1answer
149 views

Learning rule of multilayer neural networks

Suppose we have a 2-layer neural network completely connected with $d^{(0)}$ input units, $d^{(1)}$ hidden units and $d^{(2)}$ output units. We consider the error function given by $J(w) = \frac{1}{2}\...
1
vote
2answers
33 views

If we can $\epsilon-$cover one set with $\frac{K}{2}$ elements and another with 2 elements why isn't their set product $2^{\frac{K}{2}}$ cover?

I was reading the following paper on Robustness and Generalization (and covering numbers)and I was reading their example 1: which didn't quite make sense to me. The reason it didn't make sense is ...
3
votes
1answer
164 views

Can someone explain why there are two summations here?

The following quote is from the book "The art of computer programming": (..) sentence would presumably be used only if either $j$ or $k$ (not both) has exterior significance. In most cases we ...
1
vote
0answers
23 views

Minimizing $E_{out}$ theoretically in linear regression

Related to linear regression with noise I've been given the following functional, depending on the function $h$: $$ E_{out}(h) = \int \int (h(x)-y)^2 dx dy$$ I want to prove that the function that ...
1
vote
1answer
37 views

Estimating the run time of a program according to a given CPU performance

When we have a recurrence relation of a program, as an example: T(N) = N log N + 9N + 55 and the CPU capability let's say (10^6) or any other number. What is ...
2
votes
3answers
504 views

Why is the number of comparisons in a BST missing key lookup about 2 ln N?

In (An Introduction to the Analysis of Algorithms) by Philippe Flajolet and Robert Sedgewick it's written that: Insertions and search misses in a BST built from N random keys require ~ 2 ln N (about 1....
1
vote
0answers
17 views

Relationship between lexicographic index of size k (tuple) with that of size(k-1) tuple

Given a non-negative integer $n$ such that $X = \{1,2, \dots, n\}$, a combination of k-tuple and its associated index $pos_k$. How to compute the associated lexicographic index for any subset of the ...
2
votes
0answers
226 views

Analysis of the long division algorithm in the Knuth book (Seminumerical algorithms) 1

I've been reading through the long division algorithm exposed in the Knuth book for a week and I still miss some details. There's an implementation of such algorithm in "Hacker's Delight" by Warren, ...
3
votes
1answer
134 views

Set of all rational numbers less than given computable real number is decidable

Prove that set of rational numbers less than given computable real number is decidable This problem was in my exam yesterday, but I was not able to solve it. However I still want to give it another ...
4
votes
1answer
75 views

Do formulas involving fewer repetitions of variables give higher numerical precision?

I'm having some trouble doing SICP exercise 2.15. Please note that this question is not closed related to Lisp. Instead, it's closely related to numerical analysis. Exercise 2.15. Eva Lu Ator, ...
2
votes
3answers
1k views

Hash function to hash 6-digit positive integers

Let UID denote a unique identifier. UID's are represented as 6-digit positive integers. I want to insert a collection of UID's in a hash table with $M$ buckets, where $M$ is a prime number (for ...
0
votes
0answers
63 views

Yarn Resource Allocation

Say for an example,i have Color codes that are : A , B , C I want to repeat this colors so i ll put them as : 5A , 10B , 10C = 25 So now A will repeat 5 times ,B will repeat 10 times and C will repeat ...
-3
votes
1answer
438 views

Why does russian peasant multiplication work? [duplicate]

can someone provide a proof with induction on why the Russian peasant multiplication work ? if you don't know what that is , here is the algorithm : ...
0
votes
1answer
72 views

Derivative for x-direction for image

I want to ask, consider we want to compute the slope of x-direction of the following step . The slope for it would be $m =\frac{0}{m_2 - m_1} =\frac{0}{5 - 2}$ which is 0. But the derivate for ...
2
votes
2answers
238 views

How to prove with induction [duplicate]

So far I have learned how to write proofs by induction and it went fine until I got this recursive problem, which I'm not quite sure how to begin and how to prove that with induction. ...
0
votes
1answer
68 views

Abs(sum of differences of elements in a sorted array) = array.Max()-array.Min() Why?

I just found out by luck that Abs(sum of differences of elements in a sorted array) = array.Max()-array.Min() For example, Consider a sorted array, {1 43 65 97 ...
2
votes
1answer
131 views

Reference request: Introduction to reinforcement learning with hand calculation examples

For me, the most difficulty when it comes to learning about reinforcement learning is that there is not much to learn in the sense that without running some algorithm, it is very difficult to get a ...
3
votes
1answer
3k views

How to calculate an accurate estimated reading time of text?

I suppose the calculation should not be done by only two factors (average reading speed/words per minute, and word count). But at least by a third parameter, that in my opinion should measure the ...
90
votes
9answers
48k views

How/when is calculus used in Computer Science?

Many computer science programs require two or three calculus classes. I'm wondering, how and when is calculus used in computer science? The CS content of a degree in computer science tends to focus ...
9
votes
2answers
119 views

Decidability of checking an antiderivative?

Let's suppose I have two functions $F$ and $G$ and I'm interested in determining whether $$F(x) = \int G(x)dx.$$ Let's suppose that my functions are composed of elementary functions (polynomials, ...
2
votes
1answer
71 views

Upper bound on the number of triangles in a planar graph

For any $n \geq 4$, I was able to prove that every Apollonian network has $3n - 8$ triangles. An Apollonian network is a planar graph defined by recursively subdividing a triangle by three smaller ...
3
votes
0answers
82 views

Complexity for finding zeroes of sum of cosines

Consider the following equation with variable $n \in \mathbb{N}$: $$\sum \limits_{i=1}^{k} \cos(n\theta_{i}) = 0.$$ Given $\theta_1,\dots,\theta_k$, I'd like to determine whether there exists $n \in ...
1
vote
1answer
509 views

Amortized analysis for doubling resizing array is ~3n

I'm brushing up on stuff related to analysis of algorithms. And I have a question about this PDF I found. This is where I'm confused: Question 2: What if instead we decide to double the size of the ...
4
votes
1answer
63 views

A totally-ordered set of functions

When we analyze algorithms using the $O$ notation, we usually use only a small set of the space of all functions. E.g., we use $\Theta(n)$ but not $\Theta(2n)$, as these two are equally well ...
0
votes
2answers
226 views

Looking for an algorithm to generate an identicon/avatar from genome data

I am looking to develop an app that generates a single identicon image that summarizes the genome information in visual form. Identicons are essentially a visual hash of of data. usually string data ...
5
votes
2answers
717 views

Is Big-Oh notation preserved under monotonic functions?

I was just looking at the big-Oh notation. I wanted to know if the following is true in general $$f(n)=O(g(n)) \implies \log (f(n)) = O(\log (g(n)))$$ I can prove that this is true if $g$ is ...
3
votes
4answers
3k views

Why do Computers use Hex Number System at assembly language?

Why do computer use Hex Number System at assembly language? Why don't they use any other number system like binary, octal, decimal? What thing forced computer designer to use hex system at assembly? ...
6
votes
2answers
539 views

Mathematics Courses for Computer Scientists [closed]

I am looking for standard math courses (Calculus 1, Calculus 2, Linear Algebra, etc.) that were developed specifically for computer scientists, and use computer-science examples for motivation. For ...
0
votes
1answer
314 views

Problem with derivative of sigmoid activation function

I'm following Jeff heatons book 'Introduction to Neural Networks with Java'. To get node deltas, we need to calculate $f'(sum)$. In the very first row for Training Element #1, we need to compute $f'(1....
1
vote
0answers
31 views

Is the moment generating function for a sequence $\{a_n\}$ unique? [closed]

Suppose $\{a_n\}$ is a sequence with moment generating function $A(z)=\sum_{k \ge 0} a_kz^k$. Can a sequence $\{b_n\}$ with $b_n \neq a_n$ for at least one $n\in \mathbb N$ have the same moment ...
3
votes
2answers
157 views

What does it mean to multiply or divide polynomials?

What does it mean to multiply or divide polynomials? I have used them so many times, in error correcting codes, cryptography, etc. but it was never clear to me what would be a graphical ...
8
votes
1answer
273 views

High maths for game theory

I am a starting Ph.D. student in computer science, and I am trying to understand some classic game-theory papers, such as those by Nash, Kalai and Smorodinsky. But I find it hard to understand the ...
3
votes
1answer
79 views

How to compute a level set $A=\left\{ \theta:f\left(\theta\right)\geq a\right\} $

I have a real function $f:\mathbb{{R}}^{d}\mapsto\mathbb{R}$, where $d>1$. The question is how to compute the level set $A=\left\{ \theta:f\left(\theta\right)\geq a\right\} $. I am a statistician ...
1
vote
2answers
65 views

Looking for Rating Functions

I'm looking for something i would call rating functions. I'm searching for some literature about this concept. I'm not really sure about the terminology, but what I mean should be pretty obvious. A ...
0
votes
1answer
393 views

Why is $\sum_{j=0}^{\lfloor\log (n-1)\rfloor}2^j$ in $\Theta (n)$?

I am trying to understand summation for amortization analysis of a hash-table from a MIT lecture video (at time 16:09). Although you guys don't have to go and look at the video, I feel that the ...
5
votes
4answers
6k views

Trigonometry in computer science

What's the use of studying trigonometry in computer science? I mean, is it essential? Does it have a specific application in computer science? Because I can't seem to muster enough motivation for ...
5
votes
3answers
488 views

How to prove $(n+1)! = O(2^{(2^n)})$

I am trying to prove $(n+1)! = O(2^{(2^n)})$. I am trying to use L'Hospital rule but I am stuck with infinite derivatives. Can anyone tell me how i can prove this?
13
votes
2answers
13k views

Why is there the regularity condition in the master theorem?

I have been reading Introduction to Algorithms by Cormen et al. and I'm reading the statement of the Master theorem starting on page 73. In case 3 there is also a regularity condition that needs to be ...
8
votes
1answer
509 views

Given a fast and a slow computer, at what sizes does the fast computer running a slow algorithm beat the slow computer running a fast algorithm?

The source of this question comes from an undergraduate course I am taking, which covers an introduction to the analysis of algorithms. This is not for homework, but rather a question asked in CLRS. ...
0
votes
3answers
57 views

Heuristically determine a value f such that a probability d/f approaches 1/2

We have a set X of N elements. We want to get a new set X' having a size M < N. ...
7
votes
1answer
7k views

Solving $T(n)= 3T(\frac{n}{4}) + n\cdot \lg(n)$ using the master theorem

Introduction to Algorithms, 3rd edition (p.95) has an example of how to solve the recurrence $$\displaystyle T(n)= 3T\left(\frac{n}{4}\right) + n\cdot \log(n)$$ by applying the Master Theorem. I am ...