Questions tagged [mathematical-analysis]

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

Filter by
Sorted by
Tagged with
1
vote
1answer
37 views

Maximum number of similar groups of a given size that can be made from a given array

I am given an array of numbers, not necessarily unique, and the size of a group. Let the array be denoted by $B$ and the size of the group be $A$. I need to find the maximum number of groups with the ...
3
votes
0answers
49 views

Replacing 0x1021 polynomial with 0x8005 in this CRC-16 code

I have some highly optimized code for a CRC-16 implementation. It focuses on speed rather than flexibility, and as a result, it is hard-coded to model the specific unreflected polynomial ...
1
vote
1answer
15 views

How does the forget layer of an LSTM work?

Can someone explain the mathematical intuition behind the forget layer of an LSTM? So as far as I understand it, the cell state is essentially long term memory embedding (correct me if I'm wrong), ...
3
votes
1answer
41 views

Coinduction in mathematical analysis?

Coinduction is a logical principle that is somehow dual to induction. I'm struggling to understand it. Are there any interesting examples of coinduction in analysis? A few examples seem like they ...
0
votes
2answers
69 views

Algorithm to find best solution

I am writing a software as small project in TypeScript/JavaScript and got to a problem i cant solve: A Company makes a new contract with a customer and wants to order materials. There are serval ...
0
votes
0answers
12 views

Growth of n/logn vs n^(1+e) [duplicate]

Is $\Theta(\frac{n}{log(n)})$ faster growing function than $\Theta(n^{1+\epsilon})$, where $\epsilon > 0$?
2
votes
1answer
43 views

Can most programs (except the IO part) be re-written as a sequence of matrix operations?

I got this idea recently. If we do not consider the data IO part of software, imagine the data is in the memory and we need to come out with some decision (which product to recommend to a user, how to ...
0
votes
1answer
59 views

Computer Vision Techniques to find Slope of beach in the 2D Images?

What I am planning to do is to calculate the height and estimate the slope of the segmented Object. The camera will be static and the Object of Interest is the slope of the beach. I am finding harder ...
2
votes
1answer
42 views

Algorithm Analysis of Insertion Sort

Why is the recurrence formula for insertion sort is T(n-1) + n? I understand the T(n-1) part but the why does the cost for ...
-1
votes
1answer
85 views

Can we find every 216 digit number combination? [closed]

This question popped to my head when I watched Pi where the mathematican told the Jews "Didnt you calculate every 216 digit number allready?" So I want to find every possible 216 digit number ...
1
vote
3answers
64 views

How does sum of first $k$ integers equal $k(k+1)/2$ [closed]

According to this video, he explains $$p = k(k+1) / 2$$ Where $p$ is the sum of the first $k$ natural numbers. I understand $k$ means times of repetition and $k+1$ is how it increments, but why does ...
1
vote
0answers
35 views

Algorithm for detecting a finite limit of time-series numbers

Is there a well known and proven algorithm to find the TOP (finite) limit of a set of points, which are time based metrics? I'm looking for an existing implementation, in order not to invent the wheel ...
2
votes
0answers
56 views

Maximizing the product of a set of dot products

So suppose we have a set of vectors $X$ and we want to approximate the maximum of the following: $\prod_{x \in X} b \cdot x$ where the components of $b$ sum to $1$ If it matters the components of ...
2
votes
0answers
29 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
175 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 ...
5
votes
1answer
197 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
58 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
53 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
114 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
504 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
354 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
55 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 ...
3
votes
1answer
152 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
43 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
171 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
38 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
611 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
18 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
282 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, ...
2
votes
1answer
190 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 ...
3
votes
1answer
77 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
2k 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
71 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 ...
-1
votes
1answer
633 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
88 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
370 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
69 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
148 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
4k 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 ...
102
votes
9answers
66k 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
140 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
91 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
84 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
718 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
83 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
289 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 ...
6
votes
2answers
953 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
4k 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
564 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 ...