Questions tagged [mathematical-analysis]

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

Filter by
Sorted by
Tagged with
2
votes
2answers
108 views

How to solve recurrence. T(n). = T(n-1) + T(n/2) + n?

I am aware that to get a running time by recursion tree method, we need to draw a tree and find: a) number of levels in tree. Since left side of tree decreases by 1 in size, so it's longest path ...
-2
votes
1answer
30 views

Time complexity of trigonometric and inverse trigonometric function [closed]

What is the time complexity of 1.cos(x) 2.acos(x) 3.acos(cos(x)) Please answer
1
vote
2answers
57 views

Decryption of RSA

How can we decrypt an RSA message if we only have the public key? For example, Message: 21556870,12228498 Public Key: ...
0
votes
0answers
21 views

I don't understand formula meaning of computer vision Paper

I am master degree student at Computer Science Department. I started master degree at this year. Now I'm reading two papers about computer vision. Actually before time I didn't have experience about ...
1
vote
1answer
41 views

Why postfix is used more often than prefix expression?

i was reading stack and i came across the infix, preifx and postfix expression.So i understood that why postfix /prefix expressions are preferred over infix expression ( due to its unambiguous nature) ...
-1
votes
1answer
34 views

Finding the count of 0's bounded by all 1's

Given N * M 2-D matrix find out all the 0's which are completely bounded by the all 1's. ( This is not any online platform question ) (This problem statement I faced during an interview). Sub-matrix ...
0
votes
1answer
35 views

Number of permutations of set {1, 2, …, n} for which insertion sort will perform exactly n permutations

I have had the following problem at my last exam: For how many permutations of set {1, 2, ..., n} where n > 2 will insertion sort (without guard element) perform exactly n comparisons. My thinking ...
0
votes
0answers
22 views

Normalizing the Central Difference Method

How could I normalize the 2nd order central difference method? The original function is F(A,B,C,D) and only one variable is varied at a time. ie $F'' = \frac{F(A+\Delta A,B,C,D) - 2\times F(A,B,C,D) +...
1
vote
1answer
45 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
243 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
25 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
54 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
82 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
45 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
89 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
67 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
96 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
65 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
61 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
230 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
263 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
60 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
64 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
119 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
841 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
463 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
56 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
153 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
39 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
723 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
1answer
321 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
232 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
80 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
74 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
670 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
94 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
440 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
152 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
5k 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 ...
108
votes
9answers
71k 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
165 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, ...