Questions tagged [mathematical-analysis]

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

Filter by
Sorted by
Tagged with
0
votes
1answer
46 views

Four functions problem

This is not from online contest Hi guys, a friend of mine recently give me this problem that I couldn't figure out an effective way to solve it. Four functions You are given four functions $$ \begin{...
-2
votes
0answers
17 views

What is the Cross Entropy Loss for this output?

Suppose you flip a coin 5 times each with equal probability (let us say 50%, for all 5 coin flips), Would the cross entropy of the function be 1 due to them having no difference in values? Edit: In a ...
1
vote
1answer
25 views

How to use Runge–Kutta methods in a second order ODE

Consider a second order equation $F=ma=m\ddot{x}$. In the language of Euler's method $\ddot{x}(t+dt)=F(t,x(t),\dot x(t))$ $\dot{x}(t+dt)=\dot x(t)+\ddot x(t)dt$ $x(t+dt)=x(t)+\dot x(t)dt$ Basically, ...
-2
votes
2answers
40 views

Solve T(1) = 1 T(n) = T(n-1) + n^2 for n ≥ 2

I am not able to solve the following recurrence relation: $$ T(n) = \begin{cases} T(n-1) + n^2 & \text{if } n \ge 2, \\ 1 & \text{otherwise.}\\ \end{cases} $$ How do I start?
1
vote
1answer
32 views

Number of substrings with exactly k distinct characters

Given a string s and an int k, return an int representing the number of substrings (not unique) of s with exactly k distinct characters. If the given string doesn't have k distinct characters, return ...
0
votes
1answer
90 views

How to derive the worst case time complexity of Heapify algorithm?

I would like to know how to derive the time complexity for the Heapify Algorithm for Heap Data Structure. I am asking this question in the light of the book "Fundamentals of Computer Algorithms&...
0
votes
0answers
28 views

Function notation/mapping for this type of functions?

In short, what is the proper function notation/mapping for this type of functions? From Wikipedia regarding maps: In the communities surrounding programming languages that treat functions as first-...
1
vote
2answers
45 views

A silly doubt on Computer Science Objects: Arrays, Lists, Strings, and Vectors, are they the same concept?

First of all I'm a Physics Student and I've been arguing with my brother concerning the usage and the fundamental meaning of a vector on Computer Science (CS). I) Vectors A vector have a axiomatic ...
3
votes
2answers
541 views

What is the “continuity” as a term in computable analysis?

Background I once implemented a datatype representing arbitrary real numbers in Haskell. It labels every real numbers by having a Cauchy sequence converging to it. That will let $\mathbb{R}$ be in the ...
0
votes
1answer
57 views

Why doesn't diagonalization require taking a limit?

When we quantify infinite sums, we do so by taking the limit as $i$ goes to infinity. For example, we look at $\lim_{n\rightarrow \infty}\sum_{n\in \mathbb{N}}n$, and then we say that this diverges ...
0
votes
2answers
51 views

Why don't they use all kinds of non-linear functions in Neural Network Activation Functions? [duplicate]

Pardon my ignorance, but after just learning about Sigmoid and Tanh activation functions (and a few others), I am wondering why they choose functions that always go up and to the right? Why not use ...
0
votes
1answer
33 views

Computing childrens of ith node of a d-ary tree

Assume that we represent a complete d-ary tree in an array[1,...n] (this is a 1-based array of size n). The formula for indices of children of node no. i is given as: {(1-i)d+2, ... , min{n,(1-i)d+d+1}...
0
votes
0answers
15 views

Why do many floating point numbers appear compact in base16 and base32 representation? (IEEE 754)

Consider 3 randomly chosen floating point values and their base conversions: ...
0
votes
0answers
34 views

If g is a PRG and f is a OWF, is G'(x) = f(g(x)) a PRG?

Just like the title states. If I have a pseudo-random generator $g\colon \Sigma^n \rightarrow \Sigma^{2n}$ and a one-way function $f$, is $g'(x)=f(g(x))$ a pseudo-random generator? And why? My ...
0
votes
1answer
36 views

Show that f(x,y)=x+y (with |x|=|y|) isn't a one way function

I have to prove that the function $f\colon \mathbb N × \mathbb N \to \mathbb N$ defined by $f(x, y) = x + y$ and $|x| = |y|$ isn't a one-way function. How do I go around doing that?
2
votes
2answers
152 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
83 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
73 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
30 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
231 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
36 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
37 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
31 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
271 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
822 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
63 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
77 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
91 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 ...
2
votes
1answer
48 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
137 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
101 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
130 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
41 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
81 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
30 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
285 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
454 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
82 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
65 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
126 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 ...
2
votes
2answers
2k 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
562 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
156 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
48 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
188 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
24 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
822 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....