texts: Generate a Random Diagonally Dominant Matrix

texts:
I would like to write a function to generate a diagonally dominant matrix of random values. What I'm ultimately leading to is writing a code to implement the Jacobi method on this matrix in CUDA for a final project in one of my classes.

The problem is I don't really know how to do this. One idea I had was to create a random number generator and for each row of the matrix I'd check to see if the diagonally dominant criteria is satisfied. Otherwise I'd generate new numbers until it works. Then just repeat this for all the rows of the matrix. Now, I don't necessarily like this idea because for large matrices there is just no way of knowing how long it would take to generate such a matrix. Are there any known methods for creating such a matrix efficiently?


texts: Find combination of vectors from array that sum up to s

texts:
I have an array of $n$ $m$-dimensional vectors (in my case, they're 27 dimensional). I also have an $m$-dimensional vector $s$. I want to find all combinations of $k$ vectors from my array whose vector sum is equal to $s$. How to do this efficiently?

The best I could do is just a brute force which is $O(n^k)$ and impossibly slow.

Any help is appreciated.


texts:
In a CS context, I have often come across the expression to back out meaning to say that a function is returned from before performing its actual task, as in this imaginary code comment:

double divide(double dividend, double divisor) {
  if (divisor == 0) {
    return 0; //divisor is zero => back out early
  }
  return (dividend / divisor);
}

Now I recently came across the expression to bail out in just the very same context. I know that to bail somebody out generally means to provide funds to get someone out of a difficult financial situation, so I was wondering if the writer confused to back out and to bail out or if to bail out really has this meaning, too.

Has any one ever heard or read a native speaker of English say or write to bail out of a function? Or, if you're a native speaker, would you say to bail out is also correct here?


texts: Show that a set is reducible to another set

texts:
Consider an operator $+$ defined on $P(\mathbb{N})$ as follows
$$A + B = \{2x:\ x\in A\}\cup\{2x + 1:\ x\in B\}$$
Show that $A$ is $m$-reducible to $A+B$ and $B$ is $m$-reducible to $A+B$
As per the definition of reducibility $B$ is reducible to $A$ if there exists a total computable function $f$ such that for all $x\in \mathbb{N}$
$$x\in B \iff f(x) \in A$$
My Thoughts:
So, here given any two sets $A$ and $B$ I have to show that $A$ is reducible to $A+B$. That means that I have to come up with a function $f$ such that for all $x\in\mathbb{N}$
$$x\in A \iff f(x)\in A+B$$
If I take the function $f(x) = 2x$, then if $x$ is in $A$ then $f(x)$ is in $A+B$. And if $f(x)$ is in $A+B$ then $f(x)$ must be  $= 2y$ for $y\in A$.
This looks like a correct argument to me, but I am not sure if there are any flaws in it.


texts: Exactly why the time taken by 'memory reads', is not considered while calculating time complexity of an algorithm?

texts:
I am sorry if I sound repetitive(I've asked a similar sounding question earlier - Relevance of memory reads while calculating the time complexity of an algorithm). Actually, it didn't answered my intended query. May be I framed the question inappropriately, and in an unnecessarily complex and indirect way.

In the current/present question, I am referring to the magnetic disk memory as it definitely takes much time, but if the primary memory(RAM) also does take much time relative to processing, then it can too serve the purpose here.

Also, I am specially concerned here with the algorithms where number of memory reads are some function of 'n', instead of being nearly constant(because in latter case, this question is not applicable or doesn't make sense anyway).


texts: Orderability of Belief States in a POMDP?

texts:
Consider a POMDP with integer states $1,2,\ldots,N$, where $N$ is finite. We thus have a complete order over the states.

It seems reasonable to think that belief states for this POMDP may be orderable in some partial order sense.

Does this orderability translate into any structure of the optimal policy? Anyone have any relevant literature?


texts: Is there an efficient solution to the travelling salesman problem with binary edge weights?

texts: Is there a way to solve TSP in polynomial time if there are only two kinds of weights, 0 and 1?


texts: Does there exist a priority queue with $O(1)$ extracts?

texts:
There are a great many data structures that implement the priority-queue interface:

Insert: insert an element into the structure
Get-Min: return the smallest element in the structure
Extract-Min: remove the smallest element in the structure

Common data structures implementing this interface are (min)heaps.

Usually, the (amortized) running times of these operations are:

Insert: $\mathcal{O}(1)$ (sometimes $\mathcal{O}(\log n)$)
Get-Min: $\mathcal{O}(1)$
Extract-Min: $\mathcal{O}(\log n)$

The Fibonacci heap achieves these running times for example. Now, my question is the following:

  Is there a data structure with the following (amortized) running times?

Insert: $\mathcal{O}(\log n)$
Get-Min: $\mathcal{O}(1)$
Extract-Min: $\mathcal{O}(1)$

If we can construct such a structure in $\mathcal{O}(n)$ time given sorted input, then we can for instance find line intersections on pre-sorted inputs with $o\left(\frac{n}{\log n}\right)$ intersections strictly faster than if we use the 'usual' priority queues.


texts:
In ray tracing if we are tracing a ray from camera to the object, then why there is need for light source as in this image and also rays are going towards the light source instead of outgoing from the light source?

Recursive ray tracing associates an entire tree of rays with each image location.
Image from: Physically Based Rendering: From Theory to Implementation
by Matt Pharr, Greg Humphreys, 2010


texts: Between every two MST's there's a series of "nearby" MST's

texts:
Given undirected connected graph $G=(V,E)$ and a weight function $w:E\to\mathbb{R}$, two MST's $T_1, T_2$ are nearby if there exists $e\in T, e'\in T'$ such that $T'=(T-\{e\})\cup\{e'\}$.

Prove that for every $T, T'$ there exists a series of $T=T_1,T_2,...,T_k=T'$ such that every two consecutive MST's are nearby each other.

I started proving it using induction but it didn't work. Assume I have $T,T'$ that has $k+1$ distinct edges each, and I know (by induction assumption) that each two MST's with $k$ distinct edges has a series between them, what can I do next? All I know is that the sum of those $k+1$ edges in each MST is equal.

Thanks.


texts:
I've been trying to figure out what technically makes a tool or program a compiler.

For example, I know that gcc will compile source code to object files or assembly, hence transforming a programming language to a different form by breaking it down into "words" with some lexer and reading the "grammar" of the words with some parser, and finally compiling it.

But is the term compiler limited to transforming specifically programming languages?

For example, there's a tool called doxygen that will read all of the documentation from source code files, break them down, and generate output based on the documentation. Is this considered to be a compiler?


texts: Technique for converting recursive DP to iterative DP

texts:
I'm new to Dynamic Programming and before this, I used to solve most of the problems using recursion(if needed).

But, I'm unable to convert my recursive code  to DP code.

For eg, below is the pseudo-code for Finding longest common-subsequence in 2 strings :

int LCS(i,j):
    if A[i]=='\0' or B[j]=='\0':
        return 0;
    else if(A[i]==B[j]):
        return 1 + LCS(i+1,j+1)
    else:
        return max(LCS(i+1,j),LCS(i,j+1))

Now, I understand the above code and below is its DP equivalent:

//Some initializations are needed which have been skipped
if(A[i]=B[j]):
    LCS[i,j] = 1 + LCS[i-1,j-1]
else:
    LCS[i,j] = max(LCS[i+1,j],LCS[i,j+1])

I'm not able to figure out how did they construct its DP equivalent with the help of the recursion technique?

In the recursion technique, 1 + LCS(i+1,j+1) is written whereas, in DP 1 + LCS[i-1,j-1] has been used.

I am wondering how did they use minus in place of plus and how will I figure out myself(for other programs involving DP) that such adjustments need to be made in the code?


texts:
In my class a student asked whether all finite automata could be drawn without crossing edges (it seems all my examples did). Of course the answer is negative, the obvious automaton for the language $\{\; x\in\{a,b\}^* \mid \#_a(x)+2\#_b(x) \equiv 0 \mod 5 \;\}$ has the structure of $K_5$, the complete graph on five nodes. Yuval has shown a similar structure for a related language.

My question is the following: how do we show that every finite state automaton for this language is non-planar? With Myhill-Nerode like characterizations it probably can be established that the structure of the language is present in the diagram, but how do we make this precise?

And if that can be done, is there a characterization of "planar regular languages"?


texts: An LP with two covering constraints - how to round

texts:
I came across an LP with two covering problems, and I wonder how to
find a good approximation. For the relevant part of the LP: We have
a set $E$ , for each $e\in E$ we have a corresponding set $Y_{e}\subseteq E$.
We have some set fixed size sets $U_{k}\subseteq E$ and we look at
this LP
$$
\min\,\sum_{e\in E}x_{e}c(e)+\sum_{f\in E}y_{f}c(y)
$$
$$
s.t\,\sum_{e\in U_{k}}x_{e}\geq1\,\forall U_{k}
$$
$$
\sum_{e\in Y_{f}}y_{f}\geq x_{e}
$$
$$
x_{e},y_{f}\in[0,1]
$$

If I had just the first constraint this would be an instance of Set-Cover
and we would have a $O(\lg n)$ approximation, the problem is that
we also have to cover each $e$ with a set $Y_{f}$ s.t $e\in Y_{f}$.

My question: How can I find a low cost of $y_{f}$ after
I round the $x_{e}$ variables.

I have three ideas, two of which I can analyze.

First Idea: I'm looking at randomized rounding with the following

Round $x_{e}^{*}$ to $1$ with probability $x_{e}^{*}$
For each $x_{e}^{*}$ that was rounded to $1$ round an element $f\in E$
s.t $e\in Y_{f}$ and $y_{f}^{*}$ is maximal
Repeat the first two steps independently $c\ln(n)$ times

Consider $f$ s.t $y_{f}^{*}$ was rounded to $1$, this means there
is $e\in E$ with $e\in Y_{f}$ s.t $y_{f}^{*}\geq\frac{x_{e}^{*}}{|E|}$.
We rounded from $y_{f}^{*}$ (which lies in $[0,1]$) to $1$ so we
incur a factor of $\frac{1}{y_{f}^{*}}\leq|E|\cdot x_{e}^{*}\leq|E|$
to the cost. We get a $O(\log n)$ bound for the first part of the
sum and $O(|E|)$ for the second part of the sum. In my case $|E|=O(n^{2})$
and we repeat $c\ln(n)$so this is an $O(n^{2}\ln(n))$ approximation.

Second Idea: in the second step round $y_{f}^{*}$ to $1$
with probability $y_{f}^{*}$, and in the third step repeat $c\cdot n^{2}\ln(n)$
times. Since $\sum_{x\in Y_{f}}y_{f}^{*}\geq x_{e}^{*}$ then the
event that $x_{e}^{*}$ was rounded to $1$ and that there is $y_{f}^{*}$
that was rounded to $1$ s.t $e\in Y_{f}$ is $(\sum_{x\in Y_{f}}y_{f}^{*}\cdot x_{e}^{*})\geq x_{e}^{*}$.
If we plug $x_{e}^{*}$ into the set cover analysis we get that the
probability that we have a covering of $x_{e}$ that are covered by
$y_{e}$ as $e^{-c\cdot n^{2}\ln(n)\sum x_{e}^{*}}$. We know that
$\sum_{x\in U}x_{e}\geq1$ and we want a bound for $\sum_{x\in U}x_{e}^{2}\geq1$
which can be given by Cauchy\textendash Schwarz inequality as $(\sum_{x\in U}x_{e})^{2}\leq|U|\sum_{x\in U}x_{e}^{2}$.
Since $|U|\leq|E|=O(n^{2})$ If we plug this back we get a high probability
of the covering - but now the approximation ,which is the number of
repetitions , is $O(n^{2}\ln(n))$ which is the same result.

Third Idea: Create an instance of set cover after the first
step and final an optimal covering of the elements $e$ which we rounded
$x_{e}^{*}$ to $1$ - my problem is I can't compare to the cost of
the objective of the LP we start with but rather just to the goal
of LP of the set cover instance we define.

I would appreciate more ideas or corrections, I hope to reach a ratio
of $O(\ln^{k}n)$ for some constant $k$.


texts: Insertion sort vs Merge sort - memory access

texts:
I am a computer science sophomore doing a data structures and algorithms course. My professor said that insertion sort requires random access, while merge sort does not.

According to him, the insertion step in insertion sort requires random access. But can't it be implemented using sequential access in a linked list, going through each element, and as soon as you find that the element of the next node is more than the element you wish to insert, you squeeze that element after the current element (for ascending order list).

He is almost never wrong, but he also doesn't entertain doubts, due to which I'm forced to ask here. Please let me know. Thanks!


texts: Acoustic source separation with 3 microphones?

texts:
What are currently the state-of-the art algorithms for this purpose? This is an area that I know absolutely nothing about. I'm basically interested in the following two things (which I assume go hand-in-hand):

Source separation
Locating sources

I'm basically trying to build some simple Raspberry Pi based robot that would turn towards a voice and needs to be able to work when background noise is present from multiple sources. Basically I would like to separate different signal sources on the Raspberry Pi, compute their direction, and then do further fingerprinting of the signals to find the one that I want to turn towards (this can be offloaded to a more powerful system over wifi).

Even better would be if someone knows any open source research software for this.


texts: What is the $4k$ kernelization algorithm for Planar Independent Set?

texts:
Chen et al. say that

  The four-color theorem implies a $4k$-kernelization for Planar Independent Det, which is the dual problem of Planar Vertex Cover.

I knew that Vertex Cover has a kernelization with $2k$ vertices.  Furthermore, I know that we have a lower bound which is $n/4$ for IS.

But how to get a $4k$ vertex kernel for Planar IS?  Is there a general rule that when we transform "primal" program to "dual" program, then we have a factor of 2.


texts:
The problem

The input is a list of $N$ cylinders in 3D space, and the output should be a list of $M \leq N(N-1)/2$ pairs of cylinders that intersect. ($M$ depends on the input data, obviously.)

If it matters, the cylinders are very thin (with a diameter less than 1% of the length for all cylinders), and a solution for "rounded cylinders" would work for me (it probably simplifies the geometry calculations). A "rounded cylinder" is a cylinder with half-spheres at the extremities; formally, for a starting point $S$, an endpoint $E$ and a radius $r$, the rounded cylinder $(S, E, r)$ is defined as the set $\{P \mid \exists Q \in [S,E], \|PQ\| \leq r\}$.

The obvious solution

It is easy enough to do in $O(N^2)$ time and $O(max(M, N))$ space: the pseudocode of my current implementation is (for rounded cylinders):

Ncyl = length(cylinder_list)
output = {}
for i = 1, 2, ... Ncyl:
  for j = i+1, i+2, ... Ncyl:
    (S1, E1, r1) = cylinder_list[i]
    (S2, E2, r2) = cylinder_list[j]
    find P∈[S1, E1], Q∈[S2, E2] such that ||PQ|| is minimal  # this is the costly line, says the profiler
    if ||PQ|| < r1 + r2:
      add (i, j) to output
return output

Better performance?

Any algorithm will have a (time and space) worst-case in $O(N^2)$ (at least) because the output list can itself be of that length. However, the above algorithm guarantees $O(N^2)$ time even on "friendly" data because it tests all possible intersections.

In my use case, the cylinders are fairly spread apart in space (the longest cylinder is less than one tenth of the diameter of the whole set of cylinders). Furthermore, they occupy a small fraction of space and $M\sim N$ (for values of $N$ up to 2000 or so, above that it times out). This suggests to me that there could be an improvement by some "sweeping plane" algorithm similar to Bentley-Ottmann. However, I did not find a straightforward way to do Bentley-Ottmann in 3D (in 2D after sweeping you end up ordering points on a line which is easy enough, but in 3D there is no obvious ordering for a plane).


texts:
How can we compute the shortest-path tree of minimum total weight for a given connected graph?

I am using Dijkstra's algorithm to find the shortest-path tree, but there may exist more than one shortest-path tree with different total weights.

The above picture shows one such example (where $a$ represents the starting vertex).

Is there a way to find the shortest-path tree of minimum total weight without inspecting every possible shortest-path tree?


texts: Job Scheduling: Two Resources, Defined Job Length, Defined Earliest Start

texts:
Problem

I stumbled over the following job scheduling problem.

There are two resources, for simplicity I call them ...

CPU_RAM (MAX_CPU_RAM specifies what is available in total)
GPU_RAM (MAX_GPU_RAM specifies what is available in total)

Each job has ...

CPU_RAM requirements
GPU_RAM requirements
a duration, that is the time needed for execution
an earliest start time, i.e. it cannot be executed before that
is known "offline". There are changes (addition/removal, resource usage change) but they are infrequent.

For example,  Job A needs 20MB GPU_RAM, 100MB CPU_RAM and 5 minutes to execute. It cannot be started before 9:00.
There are other jobs  that have different requirements.

Goal

Given the constraints above I want to find a schedule with the earliest completion time.

I don't need a perfect solution as I doubt it would be feasible.
Since there will be roughly 50 jobs, yet up to 200 jobs should be possible.
Instead I am interested in a solution that works in practice.

Execution time should be less than 10 seconds to be feasible.
Yes the domain I am working in is not actually scheduling jobs on a PC.
But scheduling jobs on a PC is easier to describe, than what I am doing.

First Heuristic

The heuristic I am using atm. is quite primitive.

I sort the jobs by their earliest start time.
Then I pick the one that can start earliest and add it to the schedule.
Taking the reduced resources into consideration the possible start times of the remaining jobs are updated.
The job with the earliest possible start time is added. On a tie I take the job that uses most of the RAM for both CPU/GPU.

The problem with that approach is that jobs using less RAM are preferred since they fit easier and thus tend to have lower earliest possible start times.
So I am thinking of making the heuristic more like bin packing, by doing first-fit decreasing.

Research

After the heuristic I looked into The Algorithm Design Manual, if anything there might be of help.

I think pin packing algorithms with 3D boxes might apply. The constraint though would be that each box needs to have a specific alignment. Then one dimension could represent CPU_RAM, the other GPU_RAM and finally one time. Missing in that case would be the earliest start time, which I would have to consider myself when deciding which box can be added next.
Moreover the bin would have to be "open" in one dimension (time).

My google search was not that fruitful though, finding an algorithm that has a specific alignment for the boxes.

Hints/Advice/Feedback

I would be very grateful if you could give me advice of what algorithms, papers, or topics to look into, that can help me fulfil the goal outlined.


texts: Floating point Euclidean norm optimization

texts:
Past few days I've been struggling with floating point number exercises, trying to learn how they work and what are their limitations. The exercise I've encountered today is as follows:

  The Euclidean norm of an n-dimensional vector $x$ with components $x_{1}...x_{n}$ is defined by:
  $$||x||_{2}=\left(\sum_{i=1}^{n} x_{i}^{2}\right)^{1/2}$$ How would you avoid overflow and harmful underflow in this computation?

I've come up with this solution, but I'm not sure if it really makes sense:

  There are some problems with underflow and overflow that can occur when computing Euclidean norm.Firstly, the component $x_{i}$ of the vector can be in the machine range, however its square root might be not. It is possible, that the square of $x_{i}$ can be either too small (underflow - $x_{i}$ considered to be 0) or too large (overflow) or the sum of the squared components can be too large (overflow again).The solution could be implementing an algorithm, that firstly splits the components of the vector 'x' into 3 parts:

  small magnitude numbers, for which underflow might occur: $x_{i}<y$
  medium magnitude numbers, where $y\leq x_{i}<Y$
  large magnitude numbers, for which $x_{i}>Y$

  When $y$ and $Y$ are thresholds set by machine precision limits. Then, small magnitude numbers will be scaled by a scalar $S$ and then their sum of squares 'unscaled' by the same $S$. Similarly, large magnitude numbers will be scaled by an appropriate $s$, and then descaled again.

I've taken the algorithm from this book, but I'm not sure if I understand it correctly and if I explained the solution properly. It would be also helpful to reproduce this algorithm in R language, however, I don't understand the explanation to the point of replicating it.


texts: Equivalent Algorithm with Sharman Morrison inversion

texts:
I am trying to invert a matrix using Woodbury identity. The inversion using Cholesky decomposition has the following pseudo-code:

  For $t=1,2,...$

  $(1)\;\; \text{Read}\;x_t\in\mathbb{R}^n$

  $(2)\;\;D_{t-1}=diag(|\theta_t^1|,...,|\theta_t^n|)$

  $(3)\;\;A_t=A_t+x_tx_t'$

  $(4)\;\;A_{t}^{-1}=\sqrt{D_{{t-1}}}\left(a\mathbf{I}+\sqrt{D_{{t-1}}}A_t\sqrt{D_{{t-1}}}\right)^{-1}\sqrt{D_{{t-1}}}$

  $(5)\;\;\text{Read}\;y_t\in\mathbb{R}$

  $(6)\;\;b=b+y_tx_t$

  $(7)\;\;\theta_t=A_{t}^{-1}b$

  End For

The well known application of Sherman-Morrison on Recursive Least Squares is as follows:

$$A_t^{-1}=(aI+x_tx_t')^{-1}=A_{t-1}^{-1} - \frac{(A_{t-1}^{-1}x_t)(A_{t-1}^{-1}x_t)'}{1+x_t'A_{t-1}^{-1}x_t}$$

where $A_0^{-1}=\frac{1}{a}I$ and we can set $A_t = A_{t-1}+\sum_{t=1}^Tx_tx_t'$, which will lead to time complexity of $O(n^2)$.

  The above technique is mentioned here. The two implementation in $\texttt{R}$ are as follows:

X <-matrix(runif(1000),20,10)
Y<-rnorm(20)
a<- 0.1

Cholsky<-function(X,Y,a){
  X <- as.matrix(X)
  Y <- as.matrix(Y)
  T <- nrow(X)
  N <- ncol(X)
  aI<- diag(a,N)
  bt<- matrix(0,ncol=1,nrow=N)
  for (t in 1:T){
    xt<-X[t,]
    At <- aI + (xt %*% t(xt))
    InvA<-chol2inv(chol(At))
    bt <- bt + (Y[t] * xt)
    theta<- InvA %*% bt
  }
  return(theta)
}
Cholsky(X,Y,a)

Morrison<-function(X,Y,a){
  X <- as.matrix(X)
  Y <- as.matrix(Y)
  T <- nrow(X)
  N <- ncol(X)
  At<-diag(1/a,N)
  bt<- matrix(0,ncol=1,nrow=N)
  for (t in 1:T){
    xt<-X[t,]
    At <- At + (xt %*% t(xt))
    InvA <- At - ((t(xt%*%At)%*%(as.matrix(xt%*%At)))
                    /as.numeric(xt%*%At%*%xt+1))
    bt <- bt + (Y[t] * xt)
    theta<- InvA %*% bt
  }
  return(theta)
}
Morrison(X,Y,a)

  They don't give the same result. So, perhaps I should not expect the implementations to be equivalent.

I was wondering if I could invert the following (for the above case) more efficiently:

$$A_t^{-1}=\left(D_{t-1}^{\frac{1}{2}}A_tD_{t-1}^{\frac{1}{2}}+aI\right)^{-1}$$

where $A_t=A_{t-1}+x_tx_t'$ and $A_0=\mathbf{0}$.

Essentially, I want to invert:

$$M_t=\left(a\mathbf{I}+\sqrt{D_{{t-1}}}x_tx_t'\sqrt{D_{{t-1}}}\right)$$

I say:

$$M_{t}^{-1}=M_{t-1}^{-1}-\frac{(M_{t-1}D_{t-1}^{\frac{1}{2}}x_t)(M_{t-1}D_{t-1}^{\frac{1}{2}}x_t)'}{1+x_t'D_{t-1}^{\frac{1}{2}}M_{t-1}D_{t-1}^{\frac{1}{2}}x_t}$$

where $D_0=diag(\mathbf{1}$). So, $M^{-1}_0=\frac{1}{a}I$

  RLS identity given above $(aI+u_tv_t)^{-1}$ uses $u=A_{t-1}^{-1}x_t,v_t=u_t'$,
  I am using $u=M_{t-1}^{-1}D_{t-1}^{\frac{1}{2}}x_t,v_t=u_t'$

One may write the implementations in $\texttt{R}$ as follows:

X <-matrix(runif(1000),20,10)
Y<-rnorm(20)
a<- 0.1

#Cholesky implementation
X <- as.matrix(X)
Y <- as.matrix(Y)
T <- nrow(X)
N <- ncol(X)
bt<- matrix(0,ncol=1,nrow=N)
At<- diag(0,N)
I<- diag(a,N);Mt<-diag(1/a,N)
theta0<- rep(1,N)
for (t in 1:2){
  xt<-X[t,]
  Dt <- diag(sqrt(abs(as.numeric(theta0))))
  At <- At + (xt %*% t(xt))
  Mt <-  I + (Dt%*%At%*%Dt)
  InvA <- chol2inv(chol( Mt ))
  AAt<- Dt %*%InvA%*% Dt
  bt <- bt + (Y[t] * xt)
  theta0 <- AAt %*% bt
  print(theta0)
}

Above is the correct implementation of the pseudo code. If I swap Mt and InvA in the above code by the following lines, I don't get the same answer.

Mt <-  Mt + (Dt%*%At%*%Dt)
InvA<- Mt - ((t(xt%*%Dt%*%Mt)%*%(as.matrix(xt%*%Dt%*%Mt)))
                   /as.numeric(xt%*%Dt%*%Mt%*%t(as.matrix(xt%*%Dt))+1))

Why is that?


texts: Why is NFA minimization a hard problem when DFA minimization is not?

texts: I know that we can minimize DFAs by finding and merging equivalent states, but why can't we do the same with NFAs?  I'm not looking for a proof or anything like that--unless a proof is simpler to understand.  I just want to understand intuitively why NFA minimization is so hard when DFA minimization is not.


texts: Understanding why ALL_nfa is in co-nspace

texts:
I'm trying to understand Sipser's example showing that $ALL_{nfa} \in Co-NSPACE(n)$, where $$ALL_{nfa} = \{ <A> | A \text{ is an NFA such that } L(A) = \Sigma^*\}.$$

The algorithm can be seen here.

I'm confused by a few things, but mainly what is meant by "nondeterministically select an input symbol"? If I "nondeterministically" choose symbol 'a' and then mark all the vertices I can reach from the current ones by 'a', then don't I possibly miss out on the vertices reachable by 'b'? And even though we repeat this $2^q$ times, what's to stop me from choosing that 'a' transition each time?

If my instincts are correct, then what we are trying to do is convert the nfa to a dfa (which will have at most $2^q$ states). If the dfa has a single reject state, then we know the nfa has a string that will be rejected. However, we would like to do this without actually converting to a dfa, which might require too much space. So the provided algorithm tries to traverse the corresponding dfa graph, without actually building it?


texts:
My computer science professor introduced an interesting game in order to get us (his students) more familiar with the Stack and Queue ADTs.

Game Description

The banana game is played with a container -- e.g., a queue or a stack. The object of the game is to find a sequence of steps that will read a given string (i.e., sequence of letters) and print a given output string. There are 3 types of steps.

IN: Read the next letter from input and insert it into the container.
PR: Read the next letter from input and print it.
EX: Extract a letter from the container and print it.

If such a sequence exists, then we want to find a shortest one. Otherwise we want to briefly and clearly explain why no such sequence exists.
Link to original text: https://www.utsc.utoronto.ca/~nick/CSCA48/banana.html

Since the purpose of the game was only to play it, our professor never discussed any theory, or strategy for the game. Some students have come up with ways to generate solutions (for example by enumerating all sequences of valid moves and seeing if any of the results are equal to the destination string), but being first year students, none of our solutions were particularly novel or interesting. I have searched for a similar game, but my searches have not been fruitful. I am really interested in seeing the minimum time complexity algorithms for:

Finding the shortest solution
Finding out whether a given game is possible
Checking if a given solution is correct

Perhaps there are ways of representing this game that will make these thing easier to do (a graph or a tree)? I have also thought about this as some special version of The Tower of Hanoi (at least for the Stack ADT), but in this game you are not allowed to transfer characters back to the original "peg" so I guess it isn't very helpful. Note: this game can also be played with an ADT called Bucket which can only store one element.


texts: How does the Monte Carlo Tree Search Algorithm Decide When to Expand?

texts: I understand that the MCTS algorithm expands its tree after it has selected the best route to take. However, how does it decide when to end selection and then expand the tree? It cannot just traverse down the whole graph... then it would always produce child nodes at the same place (right?) So, how does the MCTS decide when to produce a child node when traversing down the search tree?


texts: How can I show this language is Regular? (Foundations of computing)

texts:
Σ(alphabet) contains 3x1 column matrices
[[0],[0],[0]], [[0],[0],[1]] , [[0],[1],[0]]... [[1],[1],[1]] such that each
element in the language is a THREE SET
of the columns where the bottom row is the sum of the two top rows

example
[[0],[0],[1]], [[1],[0],[0]] , [[1],[1],[0]] is an element of the Language

BUT

[[0],[0],[1]], [[1],[0],[1]] , [[0],[0],[0]] is not an element of the language.


texts: variable exponent in expression of a formal language

texts:
Take a look at the following expression:

{(AnB)m|n>0,m>0}

Or, to put it simply: the words in the language, have repeating parts consisting of,  some A's followed by a single B.

There are TWO school of thoughts about this, which can be broken down, by this question:
Is the word ABAAB, a part of the language?

I say, that it's not, as each repeating part must have the same number (n) of A's in it.
Others claim that each repeating part can have it's own number of A's

I am willing to concede, that had the expression used +, instead of n>0, then each repeat, could have been different (although, I don't like this concession).

The question is: Is the variable in the inner part "locked", or can that variable have different values in each iteration of the part.

What I'd like, is a credible source that I can point to that explains which way is correct.

(ps, if my understanding of the expression is the correct one, it means the language is not regular; if I am wrong, it is regular).

Thank you all.


texts: My professor claims that inserting the same key into a hash table again will lead to a collision … – Is he really right?

texts:
My whole life I thought

  a collision is a situation that occurs when two distinct pieces of data have the same hash value.

Everything looks a little bit different now: A few days ago we had to analyse common collision resolution strategies to handle the event that at least two keys being hashed to the same slot of an ordinary hash table. As mentioned above, to my knowledge (as well as my intuition) when inserting the very same key $k$ – that is already assigned to a slot of a hash table $T$ – again,  nothing (special) happens and $T$ remains unchanged.

I wonder now, if i misunderstood this basic concept, since my professor claims, that inserting the key $k$ into a hash table $T$ again will lead to a collision anyway and we have to analyse some collision resolution strategies in this case too …

Many thanks in advance for your help and clarification!


texts: Jaccard decay, Jaccard recall, and class-agnostic binary segmentation

texts:
When reading about SiamMask (Wang et al., Fast Online Object Tracking and Segmentation: A Unifying Approach), I encountered the terms "Jaccard decay" and "Jaccard recall".

I know what Jaccard index means, but not sure what is the meaning of Jaccard decay and Jaccard recall, and the difference between these terms.

Also, I don't understand what "class-agnostic binary segmentation for target object" means.


texts:
(I've recently started studying satisfiability problems. I've tried to be as clear as possible, but I'm not sure if all of the terminology used is correct.)

Consider a collection of $n$ Boolean variables, $x_1,\ldots,x_n$ and a function $F$ on this collection of variables, $F(x_1,\ldots,x_n)$. An assignment of true and false values to each Boolean variable is called a satisfying assignment if $F(x_1,\ldots,x_n)$ is true.

I'm interested in functions $F$ that take the form $(x_{i_1}\vee x_{j_1} \vee \cdots \vee x_{k_1})\wedge \cdots \wedge (x_{i_m}\vee x_{j_m} \vee \cdots \vee x_{k_m})$ where indices are allowed to repeat, a so-called Monotone k-SAT function. Perhaps something worth noting is that not all of the clauses contain $k$ variables, but it is known that $k$ is the most number of variables in all clauses.

Question: What sort of bounds on the number of satisfying assignments for $F$ are known? The worst bound is $2^n$; I'm hoping there is something better.

(Note: this builds on an original question graciously answered by Yuval Filmus here: Number of states in an AND-OR DAG)


texts: Intuition behind this specific algorithm for time series

texts:
Going through the EPI book and I need some help understanding this part.

There's a problem, 5.7, that deals with buying and selling twice over a single time-series in order to maximise profit. The input is given as a list of ints. The example they give is:

[12, 11, 13, 9, 12, 8, 14, 13, 15]

So here the maximum profit from a single buy-sell event is 7; buy at 8 and sell at 15. From two buy-sell events it is 10; buy at 9, sell at 12 and buy at 8, sell at 15.

The intuition for a single buy-sell is simple where we just keep track of the minimum element in the list and the difference between the minimum and the current element is the profit.

What I don't understand is how the double buy-sell formula works. The book proposes a solution where two passes are made through the data, a forward and a backward pass. The forward pass uses the same formula as above (single buy-sell), but the backward pass starts at the back of the list and keeps track of the maximum instead. The profits of the backward pass are stored in an array and added to the profits of the forward pass with $M[i] = F[i - 1] + B[i]$, and where $F[-1] = 0$.

Why does the backward pass keep track of the maximum, and how does the formula ensure that we won't buy before the second sale?

Here is the solution code given:

def buy_and_sell_stock_twice(prices: List[float]) -> float:
    max_total_profit, min_price_so_far = 0.0, float('inf')
    first_buy_sell_profits = [0.0] * len(prices)
    for i, price in enumerate(prices):
        min_price_so_far = min(min_price_so_far, price)
        max_total_profit = max(max_total_profit, price - min_price_so_far)
        first_buy_sell_profits[i] = max_total_profit
    # Now for the backwards pass.
    max_price_so_far = float('-inf')
    for i, price in reversed(list(enumerate(prices[1:], 1))):
        max_price_so_far = max(max_price_so_far, price)
        max_total_profit = max(
            max_total_profit,
            max_price_so_far - price + first_buy_sell_profits[i - 1])
    return max_total_profit

I broke down the iterator in the reverse pass and it creates:

[(8, 15), (7, 13), (6, 14), (5, 8), (4, 12), (3, 9), (2, 13), (1, 11)]

The expected backwards pass result is also provided for the sample data:

B = [7, 7, 7, 7, 7, 7, 2, 2, 0]

Looking through the code I can see how the algorithm can be used to populate B. What doesn't make sense is why this backwards pass guarantees the max profit, how it guarantees sane buys and sells, and what the intuition is for doing it this way.

I looked at similar questions but they provide different solutions which work great but don't provide any insight on the book's solution. The book is also not readily available online so there is less content on the material.


texts:
A set $A$ is quasi-reducible to $B$ ($A \leq_Q B$) if there is a recursive function $f$ such that $$x \in A \iff W_{f(x)} \subseteq B$$
Or equivalently $$ x \in \overline{A} \iff W_{f(x)} \cap \overline{B} \neq \emptyset $$
Where $W_{e}$ is the domain of the recursive function of index $e$, i.e. $W_{e} = \{y : \varphi_{e}(y) \downarrow\}$.

Everywhere I look it says the transitivity of the relation is easy to see, but for some reason it doesn't click for me.


texts: Efficient algorithm for "group-sum-min" problem

texts:
Given two finite sets $A, B \subseteq \mathbb{C} \times \mathbb{R}$, each stored as an array, define
$$
S = \{ (z_1 + z_2, x + y, z_1, z_2, x, y) : (z_1, x) \in A, (z_2, y) \in B \}
$$
and
$$
f(s) = \min_{t,z_1,z_2,x,y} \{ t : (s, t, z_1, z_2, x, y) \in S \}
$$
with $f(s) = \infty$ if the feasible set of the above minimum is empty. I would like an efficient algorithm for computing the set
$$
R = \{ (s, f(s), z_1, z_2) : (s,f(s),z_1,z_2,x,y) \in S \text{ for some $x$,$y$ } \}
$$

Of course, a naive $\mathcal{O}(mn ~\log(mn))$ with $m=|A|,~n=|B|$ method follows directly from the definition. Embed the set $S$ to an array of tuples, group by equal values of $z_1+z_2$ by sorting, and within each group choose the element with minimum $x+y$. I am wondering weather a better method is known.

Update

There are two additioal assumption which I believe can lead to a better algorithm.

There is a finite family $F \subseteq \mathbb{C}$ such that if $(z, x) \in A \cup B$ then $z \in F$. The family $F$ is a grid  (or lattice?) in the complex plane, with uniform spacing in each direction. However, the spacing in the real direction can be different from the spacing in the imaginary direction.
Both $|A|$ and $|B|$ are in $\mathcal{O}(|F|)$.

Output-size sensitive complexity bound, which could somehow reduce the dependence on $mn$ would be a tremendous improvement, since the size of the output seems to me as $O(m+n)$.


texts: RNN input shape for sequence generation on Tensorflow

texts:
I would like to train a RNN with LSTM cells in Tensorflow to predict the next word of a sequence. Words are N-length vectors of 0s and 1s. By looking at different tutorials, I saw that the input tensor has a shape like this

seq_input = tf.placeholder(tf.float32, [n_steps, batch_size, seq_width])

However, it is not clear to me what these shapes represent. How do I reshape my input words to match this shape?


texts: Sort array of 5 integers with a max of 7 compares

texts:
How can I sort a list of 5 integers such that in the worst case it takes 7 compares?  I don't care about how many other operations are performed.  I don't know anything particular about the integers.

I've tried a few different divide and conquer approaches which get me down to 8 compares, such as following a mergesort approach, or combining mergesort with using binary search to find the insertion position, but every time I end up with 8 compares worst case.

Right now I'm just looking for a hint, not a solution.


texts: How to predict the number of patients from the number of diagnoses

texts:
I have data on the diagnostic measures that individual patients received that year.
For that individual data, I would like to make a prediction of how many such patients are in the country.　To do so, of course, I have a national number of diagnoses. Which is $y$ (target)
Here are three matrixes, $R$, $X$, $w$.
$R$ is a 7000 x 400000 matrix that stores the number of diagnoses for each patient in a year. 7000 is the number of types of diagnosis, and 400000 is the number of patients.
$X$ is a matrix of 400000x134 and 134 is the number of more common diagnostic types. This matrix stores the number of patient diagnoses for each type.
So, the summation of $R$'s one column and the summation of $X$'s one row must be equal.
$w$ is the weight of 134 diagnostic types.
The speculation I'm about to make comes from the hypothesis that our data has patterns for all patients across the country.
In that case, multiply the $R$ data by the weight of each patient (more specifically, the estimated number of patients nationwide) to get a national estimate for each diagnosis.
This is the formula. $Rp = \hat{y}$ (p is the patient weights)
That is if $p$ is found that minimizes the error between $y$ and \hat{y}, that $p$ is the national estimated number of patients for each patient.
To do that I created $X$ and $w$. $RXw = y$ The final formula is as above. This is because optimizing p with $Rp = y$ will update as many as 400,000 weights. (It seems to be strict in terms of memory)
My optimization plan is as follows.

In the model $RXw = \hat{y}$, optimize to $w$ where the difference between $y$ and $\hat{y}$ is minimized.
Put $X$ in the trained model and find $Xw = p$
But here, there is one big limitation. The model must always give a value greater than or equal to 0.

In that case, it will be activated by a non-linear function, but as you can see by calculation, $Xw$ is not $p$ in that case.
Anyone who has analyzed a case similar to this, do you have a good idea? Again, the constraints must be met.


texts: Given a certain context sensitive grammar, can one find out if a simpler context free grammar exists?

texts: Given a generating grammar, is it possible to reduce it to a context free form, if one exists. One method might seem to be if the context sensitive rules can be reached from higher generating points, in some sense. However, is this an interesting question worth worrying about? Are there practical situations, where there is some benefit in reducing a more complicated language to a context free language?


texts: How to compare conditional entropy and mutual information?

texts:
I am solving a problem of information theory. The problem reads,

  Consider a stationary memoryless channel specified by the channel matrix
  $T = \begin{pmatrix}1-q&q\\r&1-r\end{pmatrix}$. Let the random variables $X$ and $Y$ be the input and the output of T, respectively. Let the input alphabet of $T$ be $\left\{0,1\right\}$ and $Pr(X=0)$ = $p$. Let us denote the conditional entropy $H(Y|X)$ and the mutual information $I(X;Y)$ as $f(p)$ and $g(p)$,respectively.

  Question. Compare the following four quantities $Q_{1},Q_{2},Q_{3},Q_{4}$

  $Q_{1} = f(\alpha u + (1-\alpha)v)$,
  $Q_{2} = \alpha f(u)+(1-\alpha)f(v)$,
  $Q_{3} = g(\alpha u + (1-\alpha)v)$,
  $Q_{4} = \alpha g(u)+(1-\alpha)g(v)$

  where $u,v$ and $\alpha$ satisfy $0<u<v<1$ and $0<\alpha<1$.

I have gotten
$\begin{align}
f(p) &= -pq\log q -p(1-q)\log(1-q) -(1-p)r\log r-(1-p)(q-r)\log(1-r)\\
g(p) &= -\left(p\left(1-q\right)+\left(1-p\right)r\right)\log\left(p\left(1-q\right)+\left(1-p\right)r\right) -\left(pq+\left(1-p\right)\left(1-r\right)\right)\log\left(pq+\left(1-p\right)\left(1-r\right)\right) - f(p)
\end{align}$

using the definitions of conditional entropy and mutual information. Also, by differentiating $g(p)$, I confirmed that g(p) is concave. Therefore, I concluded that $Q_{3} \ge Q_{4}$. Moreover, $Q_{1}=Q_{2}$ since $f(p)$ is a linear function concerning $p$. I cannot get other relations as I thought $g(p)$ can be larger or smaller than $f(p)$ depending on $p$. Can anyone give me any hint?


texts: how long will it take to execute a ten-stage pipeline

texts:
Suppose you design a computer with a ten-stage Pipeline to execute one instruction, with each stage taking 5nsec

A)how long will it take to execute a program that has 30 sequential instructions.
Answer: 195nsec

B) how long will it take to execute a program that has 30 sequential instructions in a non-pipeline computer
Answer: 1500nsec

can some one please help me to understand how was the answer achieved.


texts:
Given a PDA $P=(Q,\sum,\delta,q_0,F)$ construct formally a TM that accepts $L(P)$.

My idea is to construct a Turing machine with 2 tapes, one for the input and the other for the stack. Also to add $q_a$ for accept and $q_r$ for reject and to send to $q_a$ if the TM stops on states in $F$ and send to $q_r$ otherwise.

But I am having a trouble to define new the transition function for the TM: $\delta_M$.


texts: Solving Independent Set through Vertex Cover

texts:
I have an Independent Set problem, in which I have to check if given graph has a IS of given size $k$. I've already written a Vertex Cover algorithm a while back and I hope I can reuse it here. Those algorithms are closely related, since if graph $G = (V, E)$ has IS of size $k$ iff it has VC of size $V - k$. So am I right that I can I just use my VC algorithm with $k' = V - k$?

I've read this and this question and after that I've started doubting that this is that simple.


texts: Equivalene of big O definitions (Limit Definition $\Longleftrightarrow$ Quantifier Definition)

texts:
I need to proof, that both definitions of the Big 0 notation are equiavlent, but I am not sure if my proof works both ways of the equivalence.
Definitions:
Let f,g be functions.

$f(n)\in \mathcal{O}(g)\Longleftrightarrow \exists c>0\exists n_0 \forall n\geq n_0 :f(n)\leq cg(n)$
$f(n)\in \mathcal{O}(g)\Longleftrightarrow \limsup\limits_{n\to\infty}\frac{f(n)}{g(n)}<\infty$

My proof:
$f(n)\in \mathcal{O}(g)\Longleftrightarrow \limsup\limits_{n\to\infty}\frac{f(n)}{g(n)}<\infty$
$\Longleftrightarrow \exists c>0 : \limsup\limits_{n\to\infty}\frac{f(n)}{g(n)}\leq c$
$\Longleftrightarrow \exists c>0\exists n_0 \forall n\geq n_0 : \frac{f(n)}{g(n)}\leq c$
$\Longleftrightarrow \exists c>0 \exists n_0 \forall n\geq n_0 : \frac{f(n)}{cg(n)}\leq 1$
$\Longleftrightarrow \exists c>0 \exists n_0 \forall n\geq n_0 :f(n)\leq cg(n)$
$\Longleftrightarrow f(n)\in \mathcal{O}(g)$
I would like to know, if the conversion is correct or if I made any mistakes.
Thanks in advance!


texts: Prove that a recursive program satisfies a logic predicate with implication and quantifiers by induction

texts:
i have this program to prove:

given the ex3 method below
Suppose that the formal parameter "a" has always at least 2 elements and that a.length > i >= 1
Prove that ex3 satisfies the following predicate:

ex3 (a, i) <==> (for all k 1 <= k <= i ==> a [k-1] == a [k] +1)

 public static boolean ex3 (int[] a, int i) {
       if (i == 1) {
               return a[0]==a[1]+1;
       }
       else {
        return ex3(a, i-1) && a[i-1]==a[i]+1;
    }

 }

1) Write explicitly the basic case P(1) for the proving by induction
2) Write explicitly the inductive case for the proving by induction
3) Prove that the base case P(1) of the proving by induction is true
4) Prove that the inductive case of the proving by induction is true

I made an attempt to prove with induction, but i don't know if it's correct.

The goal is to prove that a recursive function satisfies the given predicate.

For the first request i replaced the index with the min value

For the second request i write the induction case starting from i - 1 to i because is a recursive function

For the third request, i tried to prove the base case in this way:

Link to the image of the proof of the case base part 2

For the last request, i tried to prove the inductive case in this way:

Can somebody say to me if it's correct or what's wrong? Thanks


texts: Why doesn't this quine-less language contradict Kleene's recursion theorem?

texts:
Kleene's recursion theorem implies that every Turing complete programming language that satisfies certain properties have quines. This website claims that this is incorrect, and that there is a Turing complete without a quine.

I give a slightly simplified version of what they gave. Start with a Turing complete programming language $P$. Create a programming language $P'$ that is interpreted according to the following rules:

Try running the program according to the rules for $P$
If the input was empty, and if it outputs it own source code and then would terminate according to the rules of $P$, throw an error instead. We'll call this error a "quine error".

For example, $Python'$ is like $Python$, except that when given no input, if the program outputs its own source, it will throw a quine error instead of terminating normally.

What is the resolution to this apparent paradox?


texts: How to predict the next word in a sentence using N-grams

texts:
How would I go about predicting the next word in a sentence if I have a n-gram model available? A intuitive solution would be to just ask the probability of all the words that can come next and see which has the highest. But this would be dreadfully slow if I have a very large set of n-grams wouldn't it?

If anyone could point me in the right direction that would be great!

Here is what I have so far. We have a data structure and this data structure will allow lookup of context(so the previous words) via hashing. This can be done in O(m) with m the length of the context but since this is always very short it is safe to say lookup can be done in O(1). Now let's say the previous words are "I want to" I would look this up in my ngram model in O(1) time and then check all the possible words that could follow and check which has the highest chance to come next. But with something as generic as "I want to" I can imagine this would be quite a few words. Our application must run on mobile devices so I would like to know if there is a more efficient way to get the word with the highest chance. I was thinking about maybe sorting the ngrams but since we are using some sort of hashtable this isn't really an option.

The more I think about this however the more I realize that even if it would be lets say 500 words that can come next, that this is still a fairly small number and even a slow processor could easily go over those very quickly so maybe I am over thinking things.


texts: Does the pigeonhole principle rule out the possibility of losslessly simulating a universe the size of our own?

texts:
Say you had a very powerful computer and wanted to run a completely lossless simulation of a universe approximately the same size as our own: $10^{80}$ particles.

Each particle in the simulation has properties like velocity, mass, charge, etc. Assuming that your program didn't use any tricks (like compressing this simulated universe by storing groups of 1000 particles as if they were one), does the pigeonhole principle mean that you would need a computer made out of at least $n$ particles to losslessly simulate a universe of $n$ particles?

I say this because I don't see how it's possible to store all of the physical properties of a particle on a piece of hardware without using at least one actual, physical particle.

Am I right about this? Does this mean it would be impossible to ever hope we could create a high resolution, lossless simulation with a number of particles similar to the actual number of particles in our universe?


texts: baz_num_elts exercise from Software Foundations

texts:
I'm at the following exercise in Software Foundations:

(** **** Exercise: 2 stars (baz_num_elts) *)
(** Consider the following inductive definition: *)

Inductive baz : Type :=
   | x : baz -> baz
   | y : baz -> bool -> baz.

(** How _many_ elements does the type [baz] have?
(* FILL IN HERE *)
[] *)

All of the answers I've seen on the Internet say that the answer is 2, and that the elements are x and y. If that's the case, then it's not clear to me what is meant by elements. There are certainly two constructors, but it's impossible to actually create a value of type baz.

It's impossible to create a value of type baz because x has type baz -> baz. y has type baz -> bool -> baz. In order to get a value of type baz we need to pass a value of type baz to either x or y. We can't get a value of type baz without already having a value of type baz.

So far I've been interpreting elements to mean values. So (cons nat 1 nil) and (cons nat 1 (cons nat 2 nil)) would both be elements of type list nat and there would be an infinite number of elements of type list nat. There would be two elements of type bool, which are true and false. Under this interpretation, I would argue that there are zero elements of type baz.

Am I correct, or can someone explain what I'm misunderstanding?


texts: $O(n\log n)$ algorithm for minimizing number of inversions in leaves of complete binary tree

texts:
I'm having trouble making an algorithm to fit these specs:

Given a complete binary tree ($n = 2^d$ leaves) with integers in leaves.
Reading the leaves from left to right makes a sequence of integers (we can assume we have an array)

Goal: How can we minimize the number of inversions in that array only by choosing non-leaf nodes and swapping the the subtrees under the given nodes. For example, if the sequence is (4,2,1,3), then choosing the root (swapping its direct children) followed by choosing the right child of the root (and swapping its direct children) turns the sequence into (1,3,2,4), which has only one inversion. This would be the minimum number of inversions.

My approach: My idea was to use something like merge sort but modified. First i would recursively split the array and then when I merge back together I'd need to change the strategy. For the first level of merges (say I have the integers [2] and [1]) I can simply put those in the correct order because our swapping operation doesn't prevent this.

However, once I have to merge something like [1,2] and [3,4] (and larger groups which are powers of 2), I have to move those groups as single units (because of the operation we have to use). I can't put it in exact order like I want but I was thinking maybe it would be best to merge the larger groups by summing up all the numbers inside the groups and moving the groups with the smallest sums to the left to minimize inversions. That seems inefficient though. All the while I have to somehow count inversions. I'm really kind of lost on what to do besides what I've thought of so far. Would anyone be able to help?


texts: How could I prove that $B$ reduces to $A$ in polynomial time in this case?

texts:
Let $A$ be a decision problem with at least one yes instance and at least one no instance. Also let $B \in \textbf{P}$. How could I prove that B reduces to A in polynomial time?

Thanks in advance.


texts:
Can I solve T(n) = 2T(n − 1) + 1 using the master theorem method?
I don't think it cannot be solved with the master theorem because b=1.
Please let me know, if my guess is wrong.


texts: What data size is sent to and read from physical RAM?

texts: When you have a cache mis, you need to fetch a block from RAM. If said block is 64 bytes big, do you need to have buses that are 512 bits (= 64 bytes) wide to transfer data from the RAM to the cache? And when writing to RAM do you write to the whole 64 byte block?


texts: What is the theoretical speedup with pipeline system over a nonpipelined system?

texts:
What is the theoretical speedup that could be achieved with the pipeline system over a nonpipelined system?

The equation I use for speedup is

$$ S = \frac{nT}{(k+n-1)t}\,$$

where:

$n$ is the number of tasks
$T$ is the time to process a task
$k$ is the number of stages segments
$t$ is the time per stage segment

I dont understand how to use this equation for this particular question.


texts: What is a flow through the cut in the Ford-Fulkerson algorithm?

texts:
In page 12 of the slide, it states flow across a cut $(S, T)$ is $f(S, T) = \sum_{u\in S} \sum_{v\in T} f(u,v) - \sum_{u\in S} \sum_{v\in T} f(v,u)$.

I think the first part $\sum_{u\in S} \sum_{v\in T} f(u,v)$ is the amount of flow entering the network at the source node. The second part $\sum_{u\in S} \sum_{v\in T} f(v,u)$ is the amount of flow leaving the network at the sink node. Shouldn't these two be the same? Why the flow across a cut is the difference of these two?


texts: Determine the number of self-crossings for an irregular orientation of an n-pointed star, whose vertices lie on the boundary of a circle

texts:
I need to create an algorithm that will output the number of self-crossings for an irregular orientation of an n-pointed star, whose vertices lie on the boundary of a circle. The sample input is as follows:

5
24.0
168.0
312.0
96.0
240.0

Where the first integer is n (the number of vertices), proceeded with n lines, each describing the positions of the vertices, taken in order, which form the star. Each vertex is in a unique position on the boundary of the unit circle, specified in degrees from the normal axis. All degree measures will be in the range [0,360).

The sample output for the sample input would be:

5 crossings

To tackle this problem, I was thinking of maybe separating the unit circle into quadrants and determine whether there are crossings depending on the positions of the vertices in their respective quadrants. However, I haven't been able to think of a way to implement this.

I was wondering if anyone could provide perhaps a high-level idea or a push in the right direction which could help me think of an algorithm.

Thank you.


texts: Finding independent sets so that all nodes are hit frequently

texts:
I have a problem, and I appreciate it if you could share your thoughts.

Assume that I have a graph. Assume that I have $k$ iterations. I want to find only one independent set (IS) in the graph in each iteration. Then, I will increase a counter for those vertices that are in the selected IS. Initially, the counter for all vertices of the graph are zero.

With an integer programming formulation, we can choose one independent set (provided that we know the set of all ISs) in every iteration, so that the counter of each vertex $i$ in the graph is at least $r_i$ over $k$ iterations (clearly $r_i \leq k$)? In other words, we can make a plan, with IP, so that each vertex $i$ has been selected $r_i$ times over $k$ iterations. Also, with simple modification, minimum value for $k$ can be included in IP formulation. I aim at finding the minimum $k$ by which all $r_i$'s are satisfied.

Now the main concern is that the above formulation need the set of all ISs as an input. Finding this set, however, is an NP-hard problem. So, I was wondering if there there is any way to bypass the need for having all ISs? For sure, many heuristic algorithms can be developed (one example is proposed in comments below). However, I am interested to find an algorithm for which I can say something analytically, e.g. convergence proof, optimality gap, etc.


texts: Defining function for arithmetic expressions

texts:
I've got these arithmetic expressions
a  ::=  n  |  x  |  a1 + a2  |  a1 ? a2  |  a1 − a2

which are a part of language.
An undefined element is allowed ⊥ which extends the set of intergers to Z∪{⊥}.
Problem:
I need to define the function

A: Aexp → (State → Z∪{⊥})

by defining equations for each form of the arithmetic expression a.
Now I've tried to come up with an solution but I am pretty sure I am wrong and I gotta admit I am pretty stuck.
Some help understanding this problem would be great.


texts: Online algorithm for finding of clique of size k

texts: I am trying to write an online algorithm that can detect cliques of size k. I first start out with a set of vertices. For each iteration, I add an edge. The algorithm will detect the first time an edge would create a clique of size k. What is an efficient algorithm that can complete this task, and what is the time complexity?


texts: What is the depth of a complete binary tree with $N$ nodes?

texts:
This question uses the following definition of a complete binary tree†:

  A binary tree $T$ with $N$ levels is complete if all levels except possibly the last are completely full, and the last level has all its nodes to the left side.

The following is an excerpt from Algorithms:

  It ($\log N$) is also the depth of a complete binary tree with $N$ nodes. (More precisely: $⌊\log N⌋$.)

Why is the above excerpt true?

† Originally defined here


texts: Difference between normal-order and applicative-order evaluation

texts:
The language I'm learning is Scheme and I'm working on an exercise that gives this:

(define (p) (p) )

(define (test x y) (if (= x 0)
                               0
                               y))

Then the question asks to evaluate the expression: (test 0 (p) ) and to comment on the behavior that would be observed under normal - order and applicative order evaluation.

These are my thoughts:

Under normal order, the program would evaluate the subexpressions before proceeding:

Thus ( test 0 (p) ) becomes:

(test 0 p)
( if (= x 0) 0 p))

Returning output 0

The only difference in applicative order would be that the program would run as:

( test 0 (p) ) becomes:

(test 0 (p))
( if (= x 0) 0 (p)))

Returning output 0

Thus (p) would never be evaluated as it won't be needed.

Is this correct? Please let me know as I have almost no experience programming.


texts:
I'm trying to find a way to count distinct simple cycles in a graph in order to prove that $\#CYCLE \in \#P$, if I could represent a distinct cycle, then I'll have a witness.

I saw this question:
Number of cycles in a graph? they mention the reduction from HAM #CYCLE in Counting Complexity by Arora and Barak, but I don't understand how does that help.

You have some directed graph, no one said it has a hamilton cycle, and the gadget doesn't return how many cycles there in the graph or a way to distinguish between them, it just makes all the cycles longer.

So instead, is it possible to use a topological sort to count cycles? since it can detect every cycle, we can use it to distinguish between them.


texts: How does this Turing machine accept $a^n b^n$?

texts:
I'm reading this tutorial from the University of Illinois about Turing Machines, and I don't understand something.

They give a pseudocode algorithm for an machine that accepts strings from the language

$L = {0^n1^n}$

and a diagram of the machine. Both are pictured below:

What I don't understand however is how does this machine know that the number of $0$s are the same as the number of $1$s. I see no mechanism that can do that. All it seems the machine can do is recognize that there are no $0$s after $1$s.


texts: Given a 3D greyscale image (particularly a dental scan) I have localized a jaw on it, i.e. made jaw's voxel intensity values much higher than others. Using this, how can I create a 2D panoramas from that 3D image? I have tried reduce_max across axis but results are far from perfect. Is there a better approach? Thanks in advance for any help!


texts: Why is the lower bound for sorting strings Ω(d + nlogn)?

texts: I'm taking an Advanced Algorithms course. I'm currently studying efficient algorithms for sorting strings. In this chapter, it is provided a lower bound for the time complexity of $\Omega(d + n\log{n})$, where d is the sum of the distinguishing prefixes of all the strings in our set S and n is the cardinality of the strings set S. The book says this is the minimum number of comparisons any algorithm must take, and I cannot figure out why. Can you help me? Thank you.


texts: Check if current interval is overlapping some intervals, or is being overlapped

texts:
Let's say we have array of $K$ integers, and we have given $N$ intervals in the form $l_{i}, r_{i}$, both inclusive, the interval $i$ means that all elements in the range $[l_i, r_i]$ are covered. Our task is to check for any of those $N$ intervals is the interval $i$, or the range $[l_i, r_i]$ being covered twice or more. Look in the examples to make it clear.

Example

$N = 3$, we have the intervals $I = \{ (1, 3), (4, 6), (1, 7) \}$. Let's illustrate the intervals

1 2 3 4 5 6 7 8 9 10...
-----               -> Interval 1
      -----         -> Interval 2
-------------       -> Interval 3

We can see that the elements that are being covered by Intervals 1 and 2, are already covered with Interval 3, so we should return one of those indexes.

Please note that $K = 10^9$, so we cannot store the whole array.

What I think

If we were able to store the whole array of $K$ members, we could easily solve with lazy propagation, and range minimum queries, but since we cannot do that, I think that we should create dynamic segment tree where we will keep only the ranges we need to store the value for.

For example, if we need only the range $[1, 128]$ we do not need to store the ranges $[1, 63]$ and $[64, 128]$. This will save memory and time, but is it enough fast to solve this problem, and what will be the time complexity for this solution if we assume that $N \leq 10^5$.


texts: Does undecidability ever imply unmeasurability and make a notion of probability ill-defined?

texts:
Not sure precisely how to ask this question, but I want to understand if it is meaningful to ask about probabilities when aspects of the definition might be undecidable.  My curiosity extends to potential implications for definitions of entropy in physical systems.  Let me try to get a little more precise about the question, and maybe someone can point me in the direction of papers or textbooks that address the topic, or has an answer themselves.
For example, imagine I have a dynamical system which can be mapped to a universal Turing machine, so there are some input settings where I can map the outputs to Halting vs not.  Now some inputs are chosen at random, and I want to know the probability that the machine halts or not.  Does the fact that knowing if the problem halts on the input or not is undecidable imply that the a probability measure is ill-defined in this case?  Are there any implications for probability of input or output in such a case?


texts:
I've started reading more about statistical learning theory, specifically this paper right here and I cannot understand the following part:

  It turns out the conditions required to render empirical risk
  minimization consistent involve restricting the set of admissible
  functions. The main insight of VC (Vapnik-Chervonenkis) theory is that
  the consistency of empirical risk minimization is determined by the
  worst case behavior over all functions f ∈ F that the learning machine
  could choose. We will see that instead of the standard law of large
  numbers introduced above, this worst case corresponds to a version of
  the law of large numbers which is uniform over all functions in F

The part that is in bold is what I do not get. This part specifically: "Consistency of ERM is determined by the worst case behavior over all functions in function space F, that learning machine could choose". What is exactly meant by the worse case behavior? I tried looking into VC theory and could not find the answer.


texts:
Suppose in an architecture, interrupt driven IO is used. And suppose a program is to be loaded from an IO device into the RAM. I have been studying IO mechanisms and I came to know that upon receiving a request to load a program, the processor generates control signals to the IO module and then the data is loaded into the IO module interface buffer. When its done loading, it will generate an interrupt to CPU.

But how does a complete file or program gets transferred to RAM? I mean does the processor issues requests only for a byte/word transfer at a time and the interrupt is raised each time a word gets transferred from io device to module? Or is it something else? Please help me understand.


texts: approximate line segments from array of unsorted points

texts:
The polygon above is actually a collection of a lot of black points closely packed together. I want to approximate these black points as straight line segments. The black points are not sorted in any order.
What I'm doing right now is sort these points by selecting any random black point and recursively finding the next closest point until no more points are left, the problem with this method is it might produce inaccurate results, if there is a small gap of points somewhere on the shape or dense lump of points somewhere on the shape. After sorting the points by this algorithm I run Douglas–Peucker algorithm to obtain the line segments. Am I doing it right? How can I approach this problem better?


texts:
Let $C$ be a  $[n, k]$ linear code over $\mathbb{F}_q$.

I want to calculate the covering radius of the Hamming codes.

I have thought the following:

Since the Hamming distance is $3$, the coverig radius will always be $3$.

Am I right?


texts: NP completeness of closest vector problem

texts:
Let $\mathcal{B} = \{v_1,v_2,\ldots,v_k\} \in \mathbb{R}^n$ be linearly independent vectors.

Recall that the integer lattice of $\mathcal{B}$ is the set $L(\mathcal{B})$ of all linear combinations of elements of $\mathcal{B}$ using only integers as coefficients. That is $$L(\mathcal{B}) = \{ \sum_{i=1}^k c_i b_i \mid c_i \in \mathbb{Z}\}.$$

The closest vector problem asks us to find a nonzero vector $v \in L(\mathcal{B})$ such that $||v||$ is minimized.

It is apparently well known that this problem is NP-complete though I was not able to find a reduction to any of the "well known" NP-complete problems.

The first proof of this claim seems to be in P. van Emde Boas. "Another NP-complete problem and the complexity of computing short vectors in a lattice"., but I cannot find a copy of this paper.

Can someone give a polynomial reduction of some well known NP complete problem to the closest vector problem?


texts: Are there theoretical reasons for believing that P=NP is harder than other complexity problems?

texts: I have a meta-complexity question: Are there reasons to believe that it is more difficult to prove P != NP than, say PSPACE != EXPTIME or BPP != BQP?


texts: Meaning of type inference rule for abstraction in lambda-calculus

texts:
Below is a snippet about simply typed lambda-calculus from CS152: Programming Languages Lecture 9 | Simply Typed Lambda Calculus, on printed‑page 15, indexed 23.

$$
\frac {\Gamma, x: \tau_1 \vdash e: \tau_2}{\Gamma \vdash \lambda x. e: \tau_1 \rightarrow \tau_2}
$$

I read it as: if from a context $\Gamma$ containing $x$ of type $\tau_1$, follows that an expression $e$ is of type $\tau_2$, then from context $\Gamma$, follows that $\lambda x. e$ is of type $\tau_1 \rightarrow \tau_2$.

How does that differs from this:

$$
\frac {\Gamma \vdash x: \tau_1 \land \Gamma \vdash e: \tau_2}{\Gamma \vdash \lambda x. e : \tau_1 \rightarrow \tau_2}
$$

I understand $x$ is expected to typically appears in $e$ (but need not to), however still not see why the second expression (looking more intuitive to me) is not used instead, and so I suspect I may be not really understanding the notation in the first expression.

Is this the same or is this different? If it is not the same, what's the precise meaning of the former and what's the (different) meaning (if it has one) of the latter? Is the former just a way to underline $x$ may be contained in $e$ (i.e., more matter of style than formal meaning)?


texts: How to cluster a dataset in which each data point is composed of a set of 2-dimensional coordinates

texts:
I have a dataset with totally $1000$ scenarios, each of which is composed of $5$ users' coordinates $(x_i,y_i), \forall i \in \{1,\dots,5\}$. Now, based on users' coordinates, I want to cluster these $1000$ scenarios into 100 clusters. Specifically, if users in two scenarios keep proximal or same coordinates, such two scenarios should be grouped into the same cluster.
My idea is to create a matrix with $1000$ scenarios as rows and $5$ users' coordinates (i.e., $5$ x-coordinates and $5$ y-coordinates) as columns. The matrix will hence have $1000$ rows and $10$ columns. Then, I apply a clustering algorithm such as k-means to cluster these $1000$ scenarios into $100$ clusters.
My concern is how to define a distance or similarity metric based only on these coordinates. Can anyone help me with this? Any comments would be appreciated!


texts: Providing $1^n$ as input to protect against degenerate cases

texts:
The following language is NP-complete:

$$\{ (\alpha, x, 1^n, 1^t): \exists u \in \{0,1\}^n s.t. M_\alpha \text{ outputs 1 on input } (x,u) \text{ within t steps}\}$$

I would like to have a stronger understanding of the $1^n$ and $1^t$ inputs that are provided as auxiliary inputs. Is the above language equivalent to the following one?

$$\{ (\alpha, x, 1^t): \exists \text{ polynomial p and }u \in \{0,1\}^{p(t)} \text{ s.t. } M_\alpha \text{ outputs 1 on input } (x,u) \text{ within t steps}\}$$

I believe this gets around the technicality of allowing certificates that are sufficiently large, but not too large.

As for the $1^t$ input, what is the situation we are trying to protect ourselves against? Why isn't it sufficient to provide $(\alpha, x))$ as inputs and require that $M_\alpha$ run in time $p(|x|)$?


texts: Count nodes within K-distance from all nodes in a set

texts:
The problem is - Given an undirected tree with some marked nodes in a set and a positive number K. We need to print the count of all such nodes which have distance from all marked nodes less than K.

My first approach-

I ran bfs on every from each marked node given in the set and takes the intersection of the respective answers. The time complexity of this solution if there are m notes in the set would be O(m*(V+E)).
Can it be further optimized ?

My second approach-

If I find two nodes from set which are maximum distance from each other, I can say that all the nodes which are a distance less than k from these two nodes will also be at a distance less than k from other marked nodes in the set. Now, I have to apply bfs at only those two extreme nodes. But, the problem is How to find two nodes from set which are maximum distance from each other? I can only think of floyd warshall over here but that would be O(V^3).

What would be the most optimal solution to this problem?


texts: Check if three given vertices from undirected graph belong to a simple cycle in most efficient way

texts:
Is it possible to perform some sort of pre-processing that would allow to answer the question efficiently (fast)?

The graph is connected, undirected, has no self loops neither parallel edges (a cycle is formed by at least three nodes).

Note that this a yes/no query, meaning that I just need to know whether such a cycle exits, which one doesn't matter.

Preprocessing should be efficient as well (ideally less than $O(m^2)$ both time and space) where $m$ is the number of edges.

Edit: The cycle is simple (no vertex in the cycle is repeated)

Edit2: My progress so far and where I'm blocking:

I'm separating the graph into sub-components through articulation points, and then doubling articulation points in each sub-component they originally separated. This came from the following observation: 3 given vertices may belong to a cycle iff they all belong to a component with no articulation points. I have not proved this but I couldn't think of a counter example.

Assuming the observation above is correct (which seems very likely), the problem now is the 3 given vertices in the query may all be articulation points, in which case all of them would belong to several components, which in the worst case could lead to a slow O(n) query time complexity.

Another observation that seem helpful to address the described worst case is: there's at most 1 sub-graph to which 2 given articulation points may both belong to at the same time (I can prove this if needed), the observation easily leads to a worst case pre-processing space and time of $O(n^2)$ (n is number of vertices), versus constant time queries, however $O(n^2)$ preprocessing time is too slow ($O(n^2)$ space is also too greedy). Can preprocessing be improved for a trade off of maybe log(n) query time expense?


texts: How to traverse a graph in reverse with dfs

texts:
So I'm watching Stanford's algorithm lectures and I'm on Kosaraju's algorithm. In the lecture, the algorthm was given in 3 steps: calculate the graph with all arcs reversed, run dfs on reversed graph, run dfs on original graph. Then an optimization was given, which was to instead of using the naive implementation of remaking the entire graph with the arcs reversed, you can instead run dfs on the original graph but going backwards along the arc instead of forward, which simulates running dfs on the reversed graph.

The lecturer made it seems so simple to do this and gave no further explanation. I'm completely stumped on how you can achieve this. Can someone give me some help or point me in the right direction?


texts: Why this Turing machine can't be an acceptor for the following language?

texts:
Given the following language -
$L=\left\{\left\langle M_{1}, M_{2}\right\rangle \mid\left\langle M_{1}\right\rangle \notin L\left(M_{2}\right) \vee\left\langle M_{2}\right\rangle \notin L\left(M_{1}\right) \text { and are TM } M_{1}, M_{2}\right\}$
I know it's in CO-RE but why this is not a good acceptor for the above language?
On input $<M1,M2>$

In parallel simulate M1 on $<M2>$ and M2 on $<M1>$
if one rejects, accept.
if both accept , reject.

according to definition of being acceptor of a language, for any input x that belongs to the language the acceptor accepts which it does it at phase 1. for any input which doesn't belongs to the language we either reject or not halt which is also the case.
what am i missing?


texts:
The below program will read a positive integer from keyboard and print the binary equivalent. This program is using only one variable.

If global variables are not stored in frame stack, how this is working.

#include<stdio.h>
int n;
void binary(n)
{
    if(n>0)
    {
        binary(n/2);
        printf("%d",n%2);
    }
}

void main()
{
    scanf("%d",&n);
    binary(n);
}


texts: Integer Linear programming formulation if then condition

texts:
I want to create constraints such that I can implement the following condition:

Let A be an integer variable >= 0 with an upper bound of 12

I want to introduce the following variable B also an integer:

if A = 1 then B = 0 else B = A


texts: Subset of numbers whose XOR has least Hamming weight

texts: I'm given $n$ numbers (let's say of some 100 bits or so). Is there a way to find a non-empty subset xor of these $n$ numbers which has the least Hamming weight (no. of set bits) in better than $O(2^n)$ complexity? I was thinking of some trie based implementation but don't think that will work at all. Would a dynamic programming approach work by any chance? If possible, a hint would be nice!


texts: Am I allowed to remove left recursion like this?

texts:
I have:

<A> -> <B> <C> <D>
<D> -> <D> <C>
<D> -> lambda

Since <D> goes to lambda, can I just change my language to:

<A> -> <B> <C> <D>
<D> -> <C> <D>
<D> -> lambda

thereby removing the left recursion? If I do the alpha beta removal method it creates an extra state that seems like junk.


texts: Why is static-single assignment preferred over continuation passing style in many industry-used compilers?

texts:
According to the Wikipedia page on static-single assignment (SSA), SSA is used by large and well-known projects such as LLVM, GCC, MSVC, Mono, Dalvik, SpiderMonkey, and V8 while the page on projects using continuation-passing style (CPS) is a bit lacking in comparison.

I have this notion that CPS is preferred by compilers and interpreters that implement primarily functional languages -- particularly, Haskell and Scheme seem to have strong inclinations towards CPS style due to the restrictions on mutation or need for first-class continuation support (I would guess that Smalltalk would possibly need this as well). The major literature that I've encountered that uses CPS seems to be those that are primarily working on Scheme or are related to Scheme in some respect.

Is there any particular reason why SSA is used in industry besides momentum of adoption? SSA and CPS have a close relationship; that means that it would be easy to state either in terms of another, but perhaps the information representation would be less compact or less efficient for CPS.


texts: Where do the length restrictions of the pumping lemma come from?

texts:
For a language $L$ with pumping length $p$, and a string $s\in L$, the pumping lemmas are as follows:

Regular version:
If $|s| \geq p$, then $s$ can be written as $xyz$, satisfying the following conditions:

$|y|\geq 1$
$|xy|\leq p$
$ \forall i\geq 0: xy^iz\in L$

Context-free version:
If $|s| \geq p$, then $s$ can be written as $uvxyz$, satisfying the following conditions:

$|vy|\geq 1$
$|vxy|\leq p$
$ \forall i\geq 0: uv^ixy^iz\in L$

My question is this: Can someone give a concise and clear explanation of how regularity (context-freeness) imply the first and second conditions above? The pumping length is determined by (finite) properties (finite number of states or finite properties of production rules, respectively), the third properties guarantee that a state (production rule) can be skipped or repeated arbitrarily many times, but where do the first and second conditions originate? How are they justified?


texts: understanding kohonen self organized feature maps

texts:
I was learning self organizing feature maps the other day. I want to intuitively understand it because I'm not that good at math. But I still am not very clear about it. I can easily understand choosing a winner neuron and adjusting it's weights according to the sample. But what I cannot understand is the idea of the neighbourhood.

Why not update the winner, the neuron with the closest value to the sample, alone? What is the importance of updating close by neurons with it?

And why should you reduce the neighbourhood as you go on? Why not keep the neighbourhood just fixed at a value?


texts:
I have a problem that goes as follows:

Problem. Suppose we have undirected graph $G$. We denote a $k$-perfect graph as a graph such that $\forall v \in G, degree(v) = k$. Present an algorithm that constructs a subgraph $H$ such that $H$ is $k$-perfect, for $k$ maximized. Do this in $\theta(|V| + |E|)$ time.

I was thinking that perhaps we could borrow techniques from a BFS based topological sort, to work on the "fringe" vertices and continuously cut inwards. Formally, we would identify vertices with small degree and cut them out, but I don't know how to make sure that this doesn't accidentally take out a vertex that would create a $k$ perfect graph of larger $k$, and how to do this without the check for if we're done costing $\theta(V)$.

Have you got any ideas?

Note that we define a subgraph here as: $H = (V', E')$ is a subgraph of $G = (V,E)$ if $V' \subseteq V$ and $E' \subseteq E$. Basically we are allowed to remove both edges and vertices.


texts: Do any industry programming languages use Martin-Löf style identity types?

texts:
Most programming languages have some kind of type systems but are there any programming languages widely used outside of academia (in consumer-oriented tech, finance etc.) that have intensional identity types à la Martin-Löf?
Coq and Agda have identity types but they are primarily used in academia.


texts:
When analyzing an algorithm, the following recurrence relation popped up:

$T(n,d)=2T(n/2,d)+T(n,d-1)+O(dn)$

where $T(n,1)=O(n \log{n})$ and $T(1,d)=O(d)$.

By applying the Master Theorem inductively, for any particular $d$, it holds that $T(n,d)=O(n (\log{n})^d)$. However, it does not necessarily hold that $T(n,d)=O(n (\log{n})^d)$ because the constant hidden by the $O$-notation depends on the value of $d$.

I was hoping that the technically incorrect bound given by repeated application of the master theorem would be good enough. It turns out that this is actually a terrible, terrible bound. The actual values of $T(n,d)$ are orders of magnitude lower from what the asymptotic bound would predict. Does anyone know how to get a better bound?


texts: Does anyone know how efficient was the first Turing machine that Alan Turing made? I mean how many moves did it do per second or so... I'm just curious. Also couldn't find any info about it on the web.


texts: Proving that $ \{u\#v\#w \mid u,v,w \in {a,b,c}*, |u|_a = |v|_b = |w|_c\}$ isn't context-free

texts:
I have a question about the pumping lemma for context-free languages.
I understand the conditions of the pumping lemma.
Assume $L$ is context-free. Let $n>0$ be the pumping length given by the lemma.
$z=uvwxy$ with conditions:

$|vwx|\leq n$

$|vx|\geq 1$

$\forall i >0,  \exists  z= uv^iwx^iy \in L$

But i need to know what are the possible cases for the $vx$, alternatively $vwx$,  so when pumped we can argue it does not  belong to the language, and if the # symbol affects the assumption?
$$L = \{u\#v\#w \mid u,v,w \in \{a,b,c\}^* , |u|_a = |v|_b = |w|_c\}$$
From what I understand, I can assume that $v$ or $y$ are only in first part $u$ or second $v$ or $w$,
but also $vxy$ can be in between $a$'s and $b$'s, including the $\#$ between them.


texts: Algorithms for graph generation using given properties

texts:
There may be a large number of algorithms proposed for generating graphs satisfying some common properties (e.g., clustering coefficient, average shortest path length, degree distribution, etc).

My question concerns a specific case: I want to generate a few undirected regular graphs (i.e., every node in these graphs has the same number of neighbors) with different clustering coefficients and average shortest path lengths. More generally, by fixing a degree distribution, I want to generate graphs with different clustering coefficients and average shortest path lengths.

I wonder what are the well-known algorithms for doing this (or in fact, is there any?), and what are the recommended software for the same purpose?


texts: Smallest multiple of a number that gives a specific remainder modulo another number

texts:
Given three positive integers $a, b$ and $c$, my task to find the smallest positive integer $k$ such that $(k * a) \mod b = c$.
I can obviously try values of $k$ from $1$ and higher, until I find the right value. My question is, can this computation be done in $O(1)$ time? That is, is there a direct way to calculate the smallest integer value of $k$ such that $k*a - c$ is a multiple of $b$?


texts: Compiling an impure language into a pure stack-based language

texts:
For a personal learning and fun project, I build an abstract virtual machine based on a stack. The instructions are simple and act on the top of the stack only. There are also stack operators such as SWAP, DUP or ROT. I have no way to manage memory, pointers, or variables (it's all on the stack after all). Typically, here is a very simple example:

square:
    DUP           -- duplicate the top of the stack
    MUL           -- consumes the first two values at the top of the stack and pushes the product
    RET           -- come back after the last call of `square`.

main:
    PUSH 6        -- pushes `6` on the stack
    CALL square   -- call the label `square`

Such a VM and IR can be related to a concatenative language, which offers the interesting feature of quotations; so this program "becomes" the following:

square == dup mul
main   == 6 square

My question is to what extent this type of VM (and therefore more broadly simple concatenative languages) is limited (or not). Without any use of FFI, I wonder if impure languages can be fully compiled into it, and if so, how?

For example, with a naive and trivial compilation, is the following C-like program compilable in a pure concatenative approach?

void assign_and_double(int *dest_ptr, int src)
{
    *dest_ptr = src * 2;
}

I had imagined a somewhat ridiculous approach that would simulate pointers with quotations: the quotation would represent the address, and the data would be in the quotation, for the example given just above, one could imagine this:

assign_and_double(&num, 4)  ==  4 [num] assign_and_double

But my hunch stopped there...

Thank you if you know how to enlighten me about this!

EDIT

I'm editing my question to give an update on Turing-complete languages.

I suspect my little language to be Turing-complete because it meets the criteria for.

In compilation classes, we are taught how to compile from high level to low level (and/or from "pure to impure"), and in fact my question had more of a "practical" side because I would like to do the opposite. Beyond the fact that it is theoretically possible to compile a complete Turing-complete language to another, I wonder how this could be done. The particular example of pointers (C-like) interested me here (I "target" not to be too broad).

Indeed, I would like to be able to generalize a rough and trivial compilation from a very simple program written in C using pointers to my abstract machine (which may be similar to a concatenative language like Joy (as it is the implementation that inspired me, although Forth is also a close candidate)).

So the question is how to do this, or to make it less vague: what are the tracks to explore?


texts: Minimum-Maximum recursive algorithm with a non-even partition, complexity

texts:
So I have been trying to find the recurrence relation of the following algorithm in order to compute its complexity. The following algorithm describes how to find the minimum-maximum element in an array recursively but instead of partitioning the array into two even sub arrays, this time we divide the array into two sub arrays with one containing the first two elements (low, low+1) and the other the rest elements (low+2, high). Here is the pseudo-code of this algorithm:

MAXMIN (A, low, high)
    if (high − low + 1 = 2) then
      if (A[low] < A[high]) then
         max = A[high]; min = A[low].
         return((max, min)).
      else
         max = A[low]; min = A[high].
         return((max, min)).
      end if
   else
      (max_l , min_l ) = MAXMIN(A, low, low+1).
      (max_r , min_r ) =MAXMIN(A, low+2, high).
   end if

   Set max to the larger of max_l and max_r ;
   Set min to the smaller of min_l and min_r ;

   return((max, min))

The classic divide and conquer algorithm as it follows in pseudocode has the following recurrence relation(as given from my textbook):

T(n) = 2, n=2 or n=1 and T(n) = 2T(n/2)+3, n>2

and the pseudocode:

MAXMIN (A, low, high)
    if (high − low + 1 = 2) then
      if (A[low] < A[high]) then
         max = A[high]; min = A[low].
         return((max, min)).
      else
         max = A[low]; min = A[high].
         return((max, min)).
      end if
   else
      mid = low+high/2
      (max_l , min_l ) = MAXMIN(A, low, mid).
      (max_r , min_r ) =MAXMIN(A, mid + 1, high).
   end if

   Set max to the larger of max_l and max_r ;
   Set min to the smaller of min_l and min_r;

   return((max, min))

So I came to the conclusion that the recurrence relation of the first algorithm should look something like that:

T(n) = 2, n=2 or n=1 and T(n) = T(2) + T(n-2) + 2

which can also be written as:

T(n) = 2 + T(n-2) + 2 <=> T(n) = T(n-2) + 4.

Is my approach correct or did i miss something? I would be glad if someone could help me out!

P.S.: Sorry for my english!


texts:
I have some questions about the ideas proposed in this video.

The speaker shows an array that holds values and pointers, and he also shows a separate "free" linked list, that is updated whenever an item is added/removed.

Why are these used? Doesn't using an array / limiting yourself to a set of free nodes defeat the purpose of a linked list?

Isn't one of the perk of using a linked list the ability to traverse fragmented data?

Why use these free nodes, when you can dynamically allocate storage?

The proposed structure, to me, doesn't seem dynamic at all, and is in fact a convoluted and inefficient array.


texts: Context-free grammar how to have unequal number of a's on either side of b

texts:
I have been trying to create a CFG for the set
$\{w=a^iba^j \mid i \neq j\}$.

To my understanding, there are essentially 2 scenarios, one where there are more $a$s on the left side of $b$, and one where there are more $a$s on the right side of $b$.
So far I have come up with:
\begin{align}
S &= TbR \mid RbT \\
T &= aT \mid \varepsilon \\
R &= TaT
\end{align}
My intention is the have $R$ to always have more $a$s than $T$, however I don't think this is correct as $T$ can be greater than $R$ in this definition, as $R$ could take be just $a$ while $T$ is $aa$.

I need a bit of help defining 2 variables $T$ and $R$, where $R$ always has more $a$s than $T$.


texts:
I know it has been shown that RNNs are Turing complete. So for any Turing machine, there exists a configuration of a RNN that is equivalent to it.

But I'm wondering, is all those configuration reachable through learning/training? i.e. For any Turing machine, does there exist a data set and a training process, which will finish in finite time and generate an equivalent RNN?


texts: Practical application of Finite State Machines

texts:
I am looking for practical applications of Finite State Machines like DFA, NFA, Moore, Mealy machines...

It would be helpful if someone point to examples from Linux Kernel. I know that DFA is used in string matching like KMP algorithm.

What is the significance of NFA, Moore and Mealy machines?


texts:
The Complexity Zoo states that ACC$^0$ is contained in TC$^0$ and links to the paper On ACC and Threshold Circuits.  However, what the linked paper proves is that depth-3 threshold circuits of quasipolynomial size can simulate ACC$^0$ circuits.

Wouldn't it be necessary to prove that constant depth threshold circuits of polynomial size simulate them rather than quasipolynomial?  Is it obvious how to do the simulation with just a polynomial number of gates?


texts: Term for size of maximum independent set

texts:
An independent set is a set of vertices in a graph, no two of which are adjacent.

A maximum independent set is a largest independent set for a given graph G.

Is there a standard term for the size of the largest independent set in a given graph?

If not, what short term can you suggest for this size? Maybe "independence number"?


texts: How can I tell if a bit pattern can represent offset gray-code?

texts:
I have a very poor understanding of gray code in general and I find it to be a difficult thing to learn. While trying to learn about it I stumbled upon this seemingly looking trivial question that I can't answer.
Can the bit pattern 01110011 represent offset gray-code?
What is "gray-code" and how do I construct it and recognize offset gray-code?


texts: How can I parse a boolean expression to group it based on the conjunction?

texts:
I have to design an algorithm to parse an array of terms and conjunctions into a grouped boolean expression. I never studied computer science and don't usually need this for web development, but today is different and I'm stumped.
I'm getting input like so:
a == 1 and b == 2 or c == 3 and d == 4

which I must turn into
(a == 1 and b == 2) or (c == 3 and d == 4)

it must also work with more complex expressionswith nested ors and ands:
a == 1 and b == 2 and c == 3 or d == 4 or e == 5 and f == 6...

which becomes
(a == 1 and b == 2 and c == 3) or (d == 4) or (e == 5 and f == 6)...

Is there a particular algorithm I could use to do this?
I'm using JavaScript if that makes a difference, and this is for an application where the user can enter a search with these terms which I must then translate into groups of terms that are using the same conjunctions (or and and only, there is no not or or not and).
so
a == 1 or b == 2 and c == 3

would become
// a == 1 or (b == 2 and c == 3)
[
  {
     group: {
       link: 'or',
       entries: [
         {
            term: 'a',
            operator: 'equal'
            value: '1'
         },
         {
           group: {
             link: 'and',
             entries: [
               {
                  term: 'b',
                  operator: 'equal'
                  value: '2'
               },
               {
                  term: 'c',
                  operator: 'equal'
                  value: '3'
               },
             ]
          }
       ]
    }
]

Something that confuses me very much is that and groups must be evaluated first, and then ored together.
Any pointers as to how to approach this problem?


texts:
Given $K$...# key values, $n$...# pointers in a node.

I read somewhere, that the maximum depth is defined as $\lceil\log_{\lceil\frac{n}{2}\rceil}(K)\rceil$. However, it is not correct, as I can come up with a counterexample. When the tree is minimum filled, it won't work.
E.g.:

This is a valid $B^+$-tree, the root has at least two childs, each inner node has at least $\lceil n/2 \rceil$ childs and each leaf has at least $\lceil \frac{n-1}{2}\rceil$ record. So, $n=3$ and $K=4$, then $\log_2(4) = 2$. Now, when you fill up the leafs: [1,1,2,2,3,3,4,4], then it is again a valid tree and $K=8$, hence $\log_2(8) = 3$, but same depth.

Notice: I am looking for a formula or explanation but for a $B^+$-tree not a $B$-tree. A source would be nice.


texts: Time complexity of functions that call each other

texts:
I'm having trouble reasoning about the time complexity of these mutually recursive functions. This was asked on SO here but the answer there didn't help me. I tried substituting one of the recurrences in the other but because they are mutually recursive I got stuck. I tried writing out the function calls for x=10 but I'm stuck making sense of that too. How do I go about working through something like this?

int foo(int x)
{
  if(x < 1) return 1;
  else return foo(x-1) + bar(x);
}

int bar(int x)
{
  if(x < 2) return 1;
  else return foo(x-1) + bar(x/2);
}

Edit: With @quicksort's answer I get S(n) = 2*S(n-1) + S(n/2) - S(n/2-1) and if I try to solve it using Wolfram I'm seeing something different: solution . Also, it's not intuitive to me that this is exponential. How does one see that?


texts: Does a time quantum affect priority non preemptive scheduling?

texts:
I am given a list of processes with their arrival time, CPU, time and Priority. The time quantum is given as 2 seconds. A lower priority number translates to a higher priority.

(process #, arrival time, CPU time, Priority)

-P0: 0, 8, 5

-P1: 2, 2, 4

-P2: 4, 1, 6

-P3: 6, 3, 3

So the priority ranks P3,P1,P0, P4.

would my scheduling look like this using the priority non preemptive scheduling algorithm:

P0 P0 P0 P0 P0 P0 P0 P0 P3 P3 P3 P1 P1 P2

I wasn't able to figure this question out on my homework and I wasn't given the solution either. I wasn't sure if the time quantum would affect my scheduling or if I even am understanding the priority non-preemptive scheduling algorithm either.


texts: Function whose domain is strictly included in its range

texts:
Hi I'm doing some exercices on reductions and one of them is like this:

My problem rather than doing the reduction is understanding it. For the positive case I want that if Mx(x) never stops then p's domain has to be strictly included in q's domain which has to be stricly included in p's range. Am I wrong? Therefore Dom(p) has to be stricly included in Range(p), right?

Let's forget about reductions for a moment, my problem here is: is there any function $f(x)$ whose domain is strictly included in its range?

We would want to have $Dom(f(x)) = \{1\}$ and $Range(f(x)) = \{1, 2\}$ That would mean that 1's image has to be 1 AND 2 :/

What am I doing wrong?

Thanks for your time and have a nice day! :D


texts: Minimum spanning tree formulation as integer program

texts:
The minimum spanning tree problem can be solved in polynomial time via Kruskal's or Prim's algorithm. However, every integer program I have seen that corresponds to the MST problem require a constraint for every subset of vertices, so the number of constraints would be exponential.

That makes me wonder, is it is possible to write down the constraints for a IP corresponding to MST such that the number of constraints is polynomial in the number of vertices? Furthermore, if it is possible, does it hold that every problem in P can be written as a LP with at most polynomial number of constraints?

Thank you very much!