Questions tagged [mathematical-analysis]
Questions related to mathematical analysis (often called analysis by mathematicians)
121
questions
0
votes
1
answer
53
views
Struggling with Recurrence Relation using Telescoping Approach
I have the following recurrence relation that I am trying to solve using the telescoping approach:
$T(n) =
\begin{cases}
T(\frac{n}{4})+ n^2 & \text{for } n \geq 4
\\
1 & \text{otherwise}
\...
1
vote
1
answer
41
views
Understanding crossover points in efficiency between insertion and merge sorts
Self-taught programmer here. I'm reading CORS, and right at the beginning, question 1.2-2, there asks a question:
For inputs of size $n$, insertion sort runs in $8n^2$ steps, which merge sort runs in ...
0
votes
1
answer
68
views
Consider A Busy Beaver like Turing Machine on a Mobius Strip. Is it equivalent to standard BB number?
I have modified Busy Beaver Turing Machine scenario. Is this new scenario equivalent to the standard one?
Consider a double sided tape twisted it into a mobius strip having P slots in total.
Initially ...
-1
votes
1
answer
261
views
Design an algorithm to predict words based on a skeleton from a given dictionary
I'm working on an algorithm which is permitted to use a training set of approximately 250,000 dictionary words.
I have built and providing here with a basic, working algorithm. This algorithm will ...
0
votes
0
answers
11
views
Clustering data to recover individual functions of a lower-hemicontinuous correspondence/bifurcation diagram
I have a data (from simulations) that is coming from something similar to a bifurcation diagram: it is a lower hemicontinuous correspondence (actually limit points of each branch is included), or in ...
1
vote
1
answer
582
views
Finding equal-sum subsets from two arrays
Consider the following problem: You are given two integer arrays $A$ and $B$ of size $N$ and $M$, respectively. You are guaranteed that $1 <= A[i] <= M$ and $1 <= B[i] <= N$ for all $i$ (...
2
votes
1
answer
81
views
Finding an approximate double-zero using binary search
Let $f$ be a continuous real function on $[-1,1]$. The function is accessible via queries: for any $x$, the value of $f(x)$ can be computed in constant time.
If $f(-1)<0$ and $f(1)>0$, then by ...
0
votes
1
answer
132
views
Is "Bitwise Complement Operator" (~ tilde) distributive?
To be more precise, Is ~(a+b) = ~a + ~b? Here, "~" bitwise NOT operator.
I ran into this question while thinking about ...
-4
votes
1
answer
53
views
How to solve this recurrence relation: T(n) = R(n-1) + n log n R(n) = T(n-1) + n^2
How to solve this recurrence relation:
T(n) = R(n-1) + n log n
R(n) = T(n-1) + n^2
0
votes
0
answers
62
views
Proving an asymptotic bound with induction
Suppose we want to prove by induction that $f(n) \in \Theta(g(n))$. How should the induction proof be set up? I'm tempted to say that the base case should prove that $f(1) \in \Theta(g(1))$ and the ...
0
votes
0
answers
63
views
Why using nC2*1/365 to calculate the birthday paradox is incorrect
The birthday paradox is basically that assume there are 365 days in a year(ignore the effect of Febuary 29th), each person's birthday is uniformly random in these 365 days and independent with others. ...
1
vote
0
answers
48
views
How can I define nested structs as mathematical notation?
My purpose is to write a academic paper related to shared computing more abstractly and I need to refer to these variables in both equation and its corresponding pseudocode.
In my pseudocode I have ...
2
votes
1
answer
29
views
sum of Boolean characters larger degree
I was curious if someone knew the answer/reference for the following. So it is well-known that if $S\in \{0,1\}^n$, then
$$
\frac{1}{2^n}\sum_{x\in \{0,1\}^n} (-1)^{\langle S, x\rangle}=1
$$
if and ...
1
vote
3
answers
132
views
Solve the recurrence $T\left(n\right)\:=\:3T\left(n-1\right)\:+\:3n^2$
I am trying to solve the recurrence
$T\left(n\right)\:=\:3T\left(n-1\right)\:+\:3n^2$
I tried method I saw but I do not fully understand which looks like:
$T\left(n-1\right)\:=\:3T\left(n-2\right)\:+\:...
2
votes
2
answers
149
views
How can I define programming struct variables as mathematical notation?
My purpose is to write a journal paper related to shared computing more abstractly (simply cost model) and I need to refer to these variables in both equation and its corresponding pseudocode.
I want ...
0
votes
3
answers
1k
views
Understanding proof that no DFA can recognize L with fewer than 2^k states
Let Σ = {a, b} and L = {ww | w ∈ Σ∗ and w is of length k}. Show that for each k, no DFA can recognize L with fewer than 2^k states.
What I understand is that we prove this by contradiction. Assume ...
1
vote
1
answer
366
views
Arguing that the inverse of Ackermann function is upper bounded by a logarithmic function (i.e. $\alpha(n) = O(\lg n)$)
The text Introduction to Algorithms by Cormen, et. al. defines the Ackermann Function $A$ as follows:
For integers $k \geq 0$ and $j \geq 1$, we define the function $A_k(j)$
$$A_{k}(j) = \begin{cases}...
3
votes
1
answer
58
views
Recurrence $T(n) = T(n-1) + (-1)^nn$, $T(0) = 1$
I am trying to solve the recurrence $$T(n) = T(n-1) + (-1)^nn, \quad T(0) = 1.$$
I'm stuck in the summation:
\begin{align}
T(n) &= T(n-1) + (-1)^n n \\ &=
T(n-2) + (-1)^{n-1}(n-1) + (-1)^nn \\ ...
2
votes
0
answers
25
views
Is computing subgradients an open research area in Authomatic Differentiation
Large portions of the possible research areas in Automatic Differentiation have broadly defined known solutions; most of which were derived in the 80s and 90s.
Compute vector jacobian products: use ...
5
votes
2
answers
3k
views
How can we count the number of pairs of coprime integers in an array of integers? (CSES)
For reference, I am trying to solve this CSES Problem.
The problem basically states that given up to $10^5$ positive integers in the range $[1, 10^6]$, find the number of pairs of those positive ...
2
votes
3
answers
199
views
What is the asymptotic bound for $T(n)= 3T(\sqrt[3]{n})+n^3$?
What is the asymptotic bound? How do you get to the result?
$$T(n)= 3 \cdot T(\sqrt[3]{n})+n^3$$
4
votes
2
answers
186
views
Precise algorithm for finding higher order derivatives
I'm trying to make an algorithm that finds the first 10 or so terms of a function's Taylor series, which requires finding the nth derivative of the function for the nth term. It's easy to implement ...
0
votes
1
answer
467
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{...
1
vote
1
answer
144
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
2
answers
249
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
1
answer
256
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
1
answer
877
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
0
answers
59
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
2
answers
93
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
2
answers
705
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
1
answer
63
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
2
answers
59
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
1
answer
440
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
1
answer
275
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
1
answer
84
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
2
answers
4k
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
1
answer
252
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
2
answers
221
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
0
answers
53
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
1
answer
823
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
1
answer
52
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
1
answer
104
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
0
answers
49
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) +...
2
votes
1
answer
1k
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
1
answer
3k
views
Replacing 0x1021 polynomial with 0x8005 in this CRC-16 code
I found a highly optimized CRC-16 implementation originally intended for microcontrollers. It is noticeably faster than the traditional method, but is hard-coded to model the specific unreflected ...
1
vote
1
answer
130
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
1
answer
173
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
2
answers
177
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
1
answer
52
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
1
answer
388
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 ...