texts: Proof of a lower bound of the recurrence relation (the CLRS's 4.6-2 exercise)

texts:
I am trying to find a solution to the ex. 4.6-2 of the Introduction to Algorithms by Cormen, Leiserson, Rivest, Stein (the third edition). It requires, for recurrence relations $T(n)=aT(n/b)+f(n)$ where $a\geq 1, b > 1$, $n$ is an exact power of $b$  and $f(n)$ is an asymptotically positive function, to prove that if $f(n) = \Theta(n^{\log_ba}lg^{k}n)$, where $k\geq0$, then $T(n)=\Theta(n^{\log_ba}lg^{k+1}n)$.

Since $T(n) = n^{\log_ba} + g(n)$ where $g(n) = \sum_{j=0}^{\log_b n - 1} a^{j}f(n/b^{j})$, I decided to consider the $g(n)$ function at the first. And I have shown $g(n) = O(n^{\log_ba}lg^{k+1}n)$ already (I think so).

But the doing the proof $g(n) = \Omega(n^{\log_ba}lg^{k+1}n)$ became a challenge for me.

Below is my research (with the simplified assumption $k$ is an integer). By condtition, there is such constant $c$ that

$g(n) \geq$

$c \sum_{j=0}^{\log_b n - 1} a^{j}(n/b^{j})^{log_ba}log^{k}(n/b^{j}) =$

$cn^{\log_ba}\sum_{j=0}^{\log_b n - 1} log^{k}(n/b^{j}) =$

$cn^{\log_ba}\sum_{j=0}^{\log_b n - 1}(logn - logb^{j})^{k} =$

$cn^{\log_ba}\sum_{j=0}^{\log_b n - 1}\sum_{i=0}^{k} {k \choose i}log^{k-i}n(-logb^{j})^{i} =$

$cn^{\log_ba}log^{k}n\sum_{j=0}^{\log_b n - 1}\sum_{i=0}^{k} {k \choose i}(-logb^{j}/logn)^{i} =$

$cn^{\log_ba}log^{k}n \biggl(log_bn + \sum_{j=0}^{\log_b n - 1}\sum_{i=1}^{k} {k \choose i}(-logb^{j}/logn)^{i} \biggr) \geq$

$c'n^{\log_ba}log^{k+1}n - cn^{\log_ba}log^{k}n\sum_{j=0}^{\log_b n - 1}\sum_{i=1}^{k} {k \choose i}(logb^{j}/logn)^{i} =$

$A(n) - B(n) = \Theta(n^{\log_ba}lg^{k+1}n) - B(n)$

Actually I am stuck with it. I can not show that $B(n)$ grows slower than $A(n)$. For instance, since $(logb^{j}/logn)^{i} \le 1$ we are able to enhance our $\geq$ condition by the substitution $B(n)$ to some fucntion $B'(n)$ with the sums of binominal coefficients only. But then finally $B'(n)$ has $n^{\log_ba}log^{k+1}n$.

So how to prove $g(n) = \Omega(n^{\log_ba}lg^{k+1}n)$ ?


texts: Build max heap in which all the nodes at certain level are less than all the nodes at the level before them

texts:
Max-heap is called a "strong" max-heap if all the nodes at certain level are less than all the nodes at the level before them. What is the most efficient way to build such a heap from a given array?

I was thinking about something similar to the regular build heap algorithm: scanning the array from right to left, compare every node to all of the nodes at the level below her, replace her with the max node and continuing until it reaches to the right position. However, I'm not sure How to make it more efficient.
Thanks


texts: Compressing dataset by cartesian products cover

texts:
I have the following problem and I wonder if there exist a solution (or some algorithm to approximate it, even if it's far from optimal, as long as it is tractable) to it.

Say I have a set $V\subseteq I_1\times I_2 \times\dots\times I_n$, all discrete finite subset of, say, integers.

Can I compress the representation of $V$ (which currently use $|V| n$ entries) by representing it as the union of cartesian products of subsets of $V$?

For instance if $V = \{(1,1),(1,2),(1,3),(2,1),\dots,(3,3)\}$ we can also write is as $\{1,2,3\}\times \{1,2,3\}$ which uses fewer entries. We can do unions of those (they can overlap) but we cannot cover more than what's in $V$.

Finally, we allow only partial cartesian products, say $A\times B$ where $A\subseteq I_1\times I_3$ and $B\subseteq I_2\times I_4$. Or even no cartesian product.
Note that under this constraint, $V$ itself is an admissible answer to the problem. But it may certainly be sub-optimal.

Any idea ? I don't even really know where to start or if this problem has a name.

Thanks a lot


texts: Small doubt in vulnerable time of CSMA/CD and pure aloha

texts:
I understand that vulnerable time is the time when collision is possible.

In CSMA/CD, the vulnerable time is Tp because it takes Tp time for bit to travel from source to destination and collision might occur during that time.Here Tp is propagation delay.

Even in pure aloha, I understand how is vulnerable time 2*Tt time is derived. Here Tt is transmission time.

My doubt is why don't we add or consider Tp time in pure aloha and Tt time in CSMA/CD when calculating vulnerable time. Why are we ignoring it ?


texts:
Let there be 2 sets $X$ and $Y$, both are countable (assume the bijection from $\mathbb{N}$ to the respective sets is computable) and infinite. Let $S$ be the set of all possible functions (NOT necessarily computable, i dont care about computability at this point) from $A$ to $Y$ for all $A \subset X$ (Remember that $A$ is not fixed here and it varies to cover all subsets of $X$. Note that $X$ and $Y$ are fixed in this question).I understand that $S$ is uncountable (as the number of subsets of $X$ will be uncountable) and hence all functions in it cannot be computable because there are countable number of computable functions. My question is that if there are indeed uncomputable functions in $S$, can somebody please give me an example of one such function or example of a subset of $S$ which contains only uncomputable functions ?

Thankyou!


texts: My problem: Define two sets P and Q of words (that is, two problems) such that: P is undecidable and not semidecidable, Q is undecidable and semidecidable and P ⊂ Q


texts:
I'm using the Random Forest algorithm for classification. I have some variable to use as features in input, but I was wondering if I can use the output of the classification itself as input.

Suppose, for example, that I want to classify people in two categories : "criminal" or "honest". In order to do that, I have a vector of three features: the name of the city where the person is born, the number of people that committed crimes in the city where the person is born, and the number of people that live in that city.
When I run the algorithm, I will get the classification results $y_1,y_2,...,y_n$ for each input vector $x_1,x_2,...,x_n$.

Now, it would be wrong to add to the input vector a new feature "number of people from the same city who have been classified by the algorithm as criminal"?

My purpose is to run several instances of the algorithm on different datasets and then share the informations gathered in each subset between the different instances.
Does it can make sense?


texts:
I know what computation is in some vague sense (it is the thing computers do), but I would like a more rigorous definition.

Dictionary.com's definitions of computation, computing, calculate, and compute are circular, so it doesn't help.

Wikipedia defines computation to be "any type of calculation that follows a well-defined model."
It defines calculation as "the deliberate process that transforms one or more inputs into one or more results, with variable change." But it seems this definition includes many actions as computations even though they aren't typically thought of as computation.

For example, wouldn't this entail that, say, a bomb exploding is a computation, with the input being the fuse being lighted and the output being the explosion?

So, what exactly is computation?


texts: Deadlock vs "Progress" requirement of the solution to the critical section problem

texts:
I came across following problem:

  Consider following code:

()
{
    [] = ;
    ([]);
    /*   */
    [] = ;
    /*  */
}

  Let flag is declared as Boolean flag[2] and Pi denote one process while Pj denotes other process and i=1-j. Both processes execute concurrently, then does the progress requirement of the solution to the critical section problem satisfied in the above case?

Doubt

The solution says that both processes Pi and Pj can simultaneously execute flag[i]=true and then both may busy wait on while(flag[j]), thus leading to deadlock and hence progress requirement of the solution to the critical section problem is not satisfied.

I know the normal / day to day meaning of "progress" gives us feeling that if there can be deadlock, then there may not be the progress. But Galvin's book defines "Progress" as this:

  If no process is executing in its critical section and some processes
  wish to enter their critical sections, then only those processes that
  are not executing in their remainder sections can participate in
  deciding which will enter its critical section next, and this
  selection cannot be postponed indefinitely.

So I am guessing whether progress has anything to do with deadlock. And whether the code indeed satisfies progress requirement of critical section problem.


texts: Generalization of finding $L_\infty$ centroid in $R^2$ via rotating and minimizing sum of $L_1$ distances

texts:
Given a set of points $x_1, \dots, x_n \in \mathbb{R}^2$, suppose one wants to find:
$\text{argmin}_i \sum\limits_{j=1}^{n} \lVert x_i - x_j\rVert_\infty$
i.e. the point which minimizes the sum of the $L_\infty$ distances to the other points.
One can apply the matrix $R =\left(\begin{smallmatrix}\frac{1}{2} & \frac{1}{2}\\-\frac{1}{2}&\frac{1}{2}\end{smallmatrix}\right)$ to get a new set of points $Rx_1, \dots, Rx_n$, instead minimize:
$\sum\limits_{j=1}^n \lVert Rx_i - Rx_j \rVert_1 = \sum\limits_{j=1}^n \lVert R(x_i - x_j)\rVert_1 = \sum\limits_{j=1}^n \lVert x_i - x_j\rVert_\infty $
Minimizing the sum of $L_1$ distances is pretty easy, while the sum of maxes seems harder.
This was a bit surprising to me. At first I thought it might be because the $L_1$, and $L_\infty$ norms are dual to each other, but in $R^n$ for $n > 2$, the $L_\infty$ norm isn't just a rotation and scaling of the $L_1$ norm.
Is there a way to generalize this into higher dimensions? I'd also be interested in a reference for this method so I could see some discussion of why this property is true in R^2 but not in higher dimensions.


texts: Removing left recursion with terminals only

texts:
I have a grammar:
$G → id > id$
   $| id < id$
   $| G and id$
Does anybody know how I can do left recursive elimination on this one, when it doesn't have any extra non terminals?


texts: What is the advantage of probability algorithm? e.g. Las Vegas. I would also like to know some applications of the randomized algorithms. Are there any recommendable courses or books?


texts: Is single-source single-destination shortest path problem easier than its single-source all-destination counterpart?

texts:
Dijkstra's algorithm (wiki) and Bellman-Ford (wiki) algorithm are two typical algorithms for the single-source shortest path problem. Both of them compute distances for all nodes from source $s$.

  If both source $s$ and destination $t$ are fixed, can we compute the shortest path from $s$ to $t$ without computing distances for all other nodes from $s$?

More fundamentally,

  Is single-source single-destination shortest path problem easier (e.g., in terms of worst-case time complexity) than its single-source all-destination counterpart?


texts:
I am reading the reduction given by Sipser in his textbook "Introduction to the Theory of Computation," on page 303. The reduction is:

\begin{equation} 3SAT \leq_p KCLIQUE \end{equation}

I am really trying to understand everything formally -- putting everything in a strict logical notation helps me learn Math. To clarify, the content of this proof, has not helped me give other reductions because I don't understand one direction of the $\iff$ in the logic of reductions.

In this reduction, $f$ must be s.t:
\begin{equation} w\in 3SAT \iff f(w) \in KCLIQUE \end{equation}
and $f$ computes within a polynomial number of steps of the input size. The polynomial part is easy for me to understand, so no problem here!

I see that the above logical statement is equivalent to:
\begin{equation} w\in 3SAT \implies f(w) \in KCLIQUE \land w\not\in 3SAT \implies f(w) \not\in KCLIQUE\end{equation}
The above just says yes-instances map to yes-instances and no-instances map to no-instances.

It appears that Sipser shows us:
\begin{equation} w\in 3SAT \implies f(w) \in KCLIQUE \land f(w) \in KCLIQUE \implies w\in 3SAT\end{equation}

Which is also equivalent to the above by taking the contrapositive of the second implication.

Here is my understanding of the $\implies$ direction. Given a yes-instance of $3SAT$, show that the reduction $f$ gives us a yes-instance for $KCLIQUE$. This seems completely natural.

I don't really understand the other direction -- namely, given a yes-instance of KCLIQUE we are supposed to show that we get a yes-instance of $3SAT$. However since the reduction goes from $3SAT$ to $KCLIQUE$ i.e. the domain is the language $3SAT$ and the Codomain is the language $KCLIQUE$, I don't understand how we show this.

It appears that the argument is; Our reduction has provided us this graph, from which we can create a satisfying assignment from?

Please help me understand the other direction, and thanks for your time.


texts:
I am a beginner at Java and this code example came up in class:
int horsepower = 15;
      if(horsepower > 15)
         if(horsepower <= 20)
            System.out.println("There is a lot of horsepower");
      else
          System.out.println("The car super fast");

the output is nothing but I can't understand why.
I have 2 questions I would like to clarify:

why did the code under the else statement not get executed?
I understand that without the brackets { }, the if condition can only execute the next statement. In this case, if horsepower variable is 17 instead, will "There is a lot of horsepower." be printed ? I am unsure if the System.out.println("There is a lot of horsepower"); still qualifies as being part of the next statement of the first if condition.

Please advise. Thanks!


texts: Is there a name for an inverted state machine?

texts:
I recently needed something like a state machine, but with a slightly different use case.

In general, I would say a state machine knows about a set of states, and different events. Depending on the current state and the event, a state machine is able to decide if this is a valid event for this state, and to which state it should transition to.

What I need is slightly different: Again, I have a state machine knowing some states, transitions and events, but it does tell me which events have to happen to transition to a certain state.
I already implemented such a machine and posted it for code review.

So, while the first machine is able to tell in which state it is after an event, the second machine is able to tell what has to happen to transition to a state.

According to this, my transition table looks different too.
Instead of having new states in the intersection of current states and events, I'm storing the events in the intersection of current and new states.

Is there a name for this kind of inverted state machine, or is it just another implementation of a finite state machine?


texts: How do you calculate the training error and validation error of a linear regression model?

texts:
I have a linear regression model that I've implemented using Gradient Descent and my cost function is a Sum of Squares Error function. I've split my full dataset into three datasets, a training set, a validation set, and a testing set. I am not sure how to calculate the training error and validation error (and the difference between the two).

Is the training error the Residual Sum of Squares error calculated using the training dataset?
Is the validation error the Residual Sum of Squares error calculated using the validation dataset?
What is the test set for exactly (I've learned the model using the training set, from the textbooks I've read I think this is the set to use to learn the model)?

Any help in clearing up these points is much appreciated.


texts:
How would one write code to find and add the prime numbers between 4 and 5 million? I need a code that can find all such numbers, and then add them together. I'm not too keen on computer science, so I wouldn't know even where to begin. (I'm a math major).

Any help is appreciated. Also any advice on how to compile and run the code would be helpful.

PS I know the answer is one of the following: 294185048443, 303141243820, 294095048847, 277319432363, 453190021165, or 210569014847.


texts: How to show that an MINLP with L0 regularization is NP-hard?

texts:
I am currently working on a project that involves a mixed-integer non-linear optimization problem, and wondering if I can state that this problem NP-hard in a research paper. I'm not looking for a formal proof as much as a reasonable argument and/or a citation.

The MINLP has the following general form:

$\begin{align}
\min_{x} & \quad f(x) + C ~\|x\|_0 \\
\text{s.t.} & \qquad x \in \mathbb{Z}^d \cap [10,10]^d
\end{align}$

where:

$\|x\|_0 = \sum_{i=1}^d 1[x_i \neq 0]$ is the $l_0$-norm
$C > 0$ is fixed constant that represents the $l_0$ regularization parameter
$f: \mathbb{R}^d \rightarrow \mathbb{R}^+$ is a strictly convex non-linear function. In practice, $f$ is a loss function and is part of the input. As an example, consider $f(x) = \log(1+\exp(-x^T z_k))$ where $z_1,\ldots,z_K \in \mathbb{R}^d$ are fixed parameters derived from a dataset.

In practice, I represent and implement this MINLP using the following formulation:

$\begin{align}
\min_{x} & \quad \sum_{k=1}^K v_k + C ~\sum_{i=0}^d y_i & \\
\text{s.t.} &
\qquad  f_k = \log(1+\exp(-x^T z_k)) & \text{for } k = 1,\ldots,K\\
& \qquad |x_i| \leq 10 y_i & \text{for } i = 1,\ldots,d\\
& \qquad x_i \in \{-10,\ldots,10\} & \text{for } i = 1,\ldots,d\\
& \qquad  y_i \in \{0,1\} & \text{for } i = 1,\ldots,d\\
\end{align}$

This formulation requires $K + 2d$ total variables ($f_k, x_i, y_i$) of which $K$ are real and $2d$ are discrete. In addition, it uses $K + 2d$ constraints (this accounts for the fact that we have to express the $|x_i| \leq 10 y_i$ constraints using two constraints, but does not account for the lower and upper bound constraints on $x_i$ and $y_i$).

Some thoughts: I am pretty sure that the problem is NP-hard, since it has the elements of other problems that are NP-hard such as $l_0$ regularization and integer constraints.

The problem can be reformulated as a "convex" MINLP (i.e., an optimization problem with a convex objective function with integer constraints). To see this, just replace the $\|x\|_0$ term in the objective with $\sum_{i=0}^d y_i$ and add the constraints $y_i \in \{0,1\}$ and $|x_i| \leq 10 y_i$ for $i = 1,\ldots,d$ to obtain:

$\begin{align}
\min_{x} & \quad f(x) + C ~\sum_{i=0}^d y_i \\
\text{s.t.} & \qquad x \in \mathbb{Z}^d \cap [10,10]^d \\
& \qquad |x_i| \leq 10 y_i \text{ for } i = 1,\ldots,d \\
& \qquad  y_i \in \{0,1\} \text{ for } i = 1,\ldots,d
\end{align}$

This paper argues that most convex MINLP instances are NP-hard in the introduction, but also that they might be  but says that it might also be instance (since they constitute a wide variety of optimization problems).


texts: I’m trying to understand the task performed by Google’s Sycamore that recently achieved alleged Quantum Supremacy. I’ve read the paper in Nature but the actual task that would have taken 10,000 years to compete is over my head. Is anyone able to explain it in simpler terms?


texts:
In the programming language theory world, there are two important terminologies, i.e syntax, and semantics.
I can understand these two terminologies:
syntax is about sentence's structure (e.g. a valid sentence by some grammar)
semantics is about sentence's meaning (e.g. operational semantics, denotational semantics, etc)
But recently the third word appeared in some PL papers i.e. linguistics, although it is very rare.
What's the meaning of linguistics?
What's the relationship between linguistics and syntax/semantics ?
Thanks.
PS: I'm sorry, I don't know whether it’s suitable to post this question here, because my vision is very narrow...

The following are some PL papers that used this term:
https://users.cs.northwestern.edu/~robby/pubs/papers/aplas2006-fff.pdf
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.23.8118&rep=rep1&type=pdf
Note that this is not a temporary question. The word "linguistic(s)" is not just appeared in these two papers. It also appeared in other papers, but I can't remember all (sorry). Failure to understand the "linguistic(s)" does not affect the understanding of the paper. I am just curious about the meaning of the "linguistic(s)".


texts: Binary search algorithm - worst-case complexity

texts:
I tried to calculate the worst case of binary search (not binary search tree). My calculations:
$$T(n) = T(\frac{n}{2}) + 1$$
$$T(n) = T\left(\frac{n}{4}\right) + (1+1) = T\left(\frac{n}{8}\right) + (1+1+1) = ... = T\left(\frac{n}{2^{k}}\right)+(1\cdot k) $$
$$T(n)=T(1) + (1\cdot k) = c_{1} + (1\cdot k) =  c_{1} + log_{2}n = c_{1}+\frac{log(n)}{log(2)} $$
Finally the complexity should be
$$O(log(n)) $$
Is this a good way to prove the worst case complexity of binary search algorithm? Make I mistakes?


texts: graph isomorphism completeness of class X and not-X

texts:
there are many classes of graphs proved GI complete & many questions related to GI on tcs.se eg [1] & many others.

  suppose a class both $X$ and not-$X$ of graphs are proven GI complete. what are the implications of that?

[1] open problems related to GI


texts:
Consider a bipartite graph G=(U+V,E) and suppose |U|=|V| and that G has a perfect matching. Therefore by P. Hall's condition, for every subsets A of U, the neighborhood N(A) of A has size at least |A|.
I am interested in subsets A for which N(A) has the same cardinality as A. Do they have a name?
It seems that any perfect matching must contain a sub-matching between A and N(A).
Is there an algorithm to identify the largest proper subset of U that has this property?


texts: Calculate Shortest Path (Shortest Time) Through a Store in a Graph

texts:
There is an undirected graph and some of the vertices are said to be stores.
Person A wants to reach to person B with a present. That means person A has to stop by one of the vertices marked as stores and get the present first before ever reaching to person B. Moreover, each store has a specific waiting time, and if the person decides to stop by at that particular supermarket, the waiting time should be included in the shortest path(shortest time).

Well, regular Dijkstra does not work very well because the shortest path may not include any store vertices, so the stores should somehow be incorporated in the algorithm. It is a must to visit one of the vertices marked as a store. But total travel time has to be the minimum.

Only the vertices marked as stores have weights, and it is a must to visit at least one of them.


texts: What is the difference between oblivious and non-oblivious merging, sorting etc

texts: Algorithms can either be oblivious or non-oblivious, but what is the actual difference between the two?


texts: Ordered set transformation data structure

texts:
Assume an ordered set $M = \{\tau_1, \tau_2, ..., \tau_n\}$ and a subset $S = \{\tau_k,\tau_l,...,\tau_m\}\subset M$ where $1\leq k,l,m \leq n$. All the items of $S$ are randomly ordered.

The task is to transform the set $M$ to set $S$ using the least amount of data.

The naive approach is to use a set of indexes $I=\{k, l, ..., m\}$ and take the items from set $M$ and reconstruct $S$. If we assume that $n=65536$ then each index would take $\log_2(n)=16$ bits, using a total of 128KiB. If I am not mistaken this is $\Theta(nlog_2n)$ space complexity.

Are there algorithms or data structures that are able to archive better space complexity characteristics? A possible trade off is false positive probabilities i.e. having to items with the same index (that can detected by using a hash of $S$).

I considered the Bloomier Filter algorithm, where $\tau_j$ is the key and the index is the value, unfortunately the data structure becomes bigger than the naive method.

If it is important, the set items are fixed size 256 bits long (sha256 hashes).


texts: How does (non)deterministic time relate to verifiability?

texts: So far, from all the research I've done, I've come across 2 different ways that NP time is explained. One is that a nondeterministic turing machine is able to solve the problem in polynomial time. It seems like this is the exact same as being able to verify that a result is correct in polynomial time, but not necessarily solve the problem in polynomial time. Both these ideas make sense, but these ideas seem very different to me. One is talking about solvability of a problem in a nondeterministic context while the other is talking about solvability vs. verifiability. Can you please intuitively explain why they're related, and if this relationship between solvability, verifiability, determinism, nondeterminism applies to harder complexity classes such as EXP vs NEXP?


texts: Are deterministic and nondeterministic Cellular Automata equivalent?

texts:
It seems that in CA context nondeterministic (ND) means probabilistic, not ND as in NFSMs. At least I haven't seen a paper or book which discusses NCAs, without talking about probabilistic CAs.

I haven't even found a definition anywhere. It feels like NCAs can't be equivalent to CAs (not in the same lattice at least), even though I can convert a NFSM to a FSM the possibly exponential growth of the required states doesn't fit to the CA definition, it would need a higher dimensional lattice (i.e. more local neighbours).

So, are NCAs and CAs equivalent ? Are there papers or books discussing this ?


texts: Advantages of block-based simulator versus equation-based simulator

texts:
I am mostly using Modelica, an equation-based simulator.

I assume that block-based simulators like Simulink have their strengths and are better at some tasks, but I am wondering what those are. It seems like everything a block based simulator can do, an equation-based simulator can do nearly as well or better. For example, Modelica supports discrete states, directional (causal) links and other block-based features.

I realize that Simulink has a lot of pre-existing models. For example, if you are interested in simulating beam forming, you can buy a beam forming module for Simulink.

However, assuming that I do not want to buy or leverage existing Simulink models, why would I want to bother with Simulink at all? What is the advantage that a block based simulator has?


texts: Number of Hamiltonian cycles on a Sierpiński graph

texts:
I am new to this forum and just a physicist who does this to keep his brain in shape, so please show grace if I do not use the most elegant language. Also please leave a comment, if you think other tags would be more appropriate.

I am trying to solve this problem for which I need to compute the number of Hamiltonian cycles $C(n)$ in the $n$th order Sierpinski-graph $S_n$. (Please also see the above link for the definition and pictures of Sierpinski-graphs)

I have found $C(n)$, but I must have messed up something, because my solution does not match the given value $C(5) = 71328803586048$. My argumentation consists of very basic thoughts, and I cannot find the mistake. Any help is greatly appreciated. Even if it seems lengthy, the thoughts become trivial if you look at the graphs while following.

(a) In a given graph $S_n$ call the outer corners $A,B,C$. Then I define the following quantities:

$N(n) := $ the number of Hamiltonian paths from $A$ to $C$.

$\bar{N}(n) := $ the number of paths from $A$ to $C$ which visit each node once except $B$.

I will also call such paths $N$- or $\bar{N}$-type paths in the following.

(b) It is easy to see that $N(n)=\bar{N}(n)$.

The reason is the following: Consider a $N$-type path. Starting at $A$ this path is of the form $(A,...,X_1,B,X_2,...,C)$. By replacing the segment $(X_1,B,X_2)$ by $(X_1,X_2)$ we obtain a $\bar{N}$-type path. This operation uniquely maps all $N$-type paths to $\bar{N}$-type paths.

(c) We derive the recursion $N(n+1)=2N(n)^3$.

Consider an $N$-type path from $A$ to $B$ and denote the subtriangles at the outer corners $A,B,C$ by $T_A,T_B,T_C$, respectively. It is clear that the $N$-type path will visit each subtriangle exactly once starting from $T_A$ over $T_B$ to $T_C$. Now consider the node $Z$ at which the subtriangles $T_A$ and $T_C$ touch. There are two possibilities, when this point is visited by the path, either (i) before leaving $T_A$ or (ii) after entering $T_C$. In these cases the three subpaths inside $T_A,T_B,T_C$ are of the types (i) $N,N,\bar{N}$ or (ii) $\bar{N},N,N$, respectively. With this in mind we can count

$N(n+1)=N(n)N(n)\bar{N}(n)+\bar{N}(n)N(n)N(n)$ and with (b) we arrive at the upper recursion.

(d) We solve the recursion (c) with $N(1)=1$ and obtain $N(n)=2^{3^0+3^1+...+3^{n-2}}$.

(e) Consider a Hamiltonian cycle in the graph $S_n$. As each of three subtriangles is connected to the others via two nodes only, it is clear that the cycle will enter each subtriangle exactly once via one connecting node, then "fill" it, an finally leave it via the other connecting node. Hence the Hamiltonian cycle in $S_n$ consists of three $N$-type subpaths in the subtriangles which all have the structure of $S_{n-1}$. We can conclude for the number of Hamiltonian cycles

$C(n) = N(n-1)^3$.

However it follows for $n=5$

$C(5) = N(4)^3 = 8192^3=549755813888 \neq 71328803586048$

where the latter should be obtained according to the problem page (link above).

Thanks again for any help or comments.


texts:
Maybe these are silly question. I know almost nothing about computer science, so please let me know in the comment section if I should edit anything or delete it.

Let's say I have a function that randomly selects 8 choices of 0 or 1. Would it be written as one byte together? For example, if all choices came out as 1, would it be written as 11111111?
Also, let's say another function can select the amount of choices. Any between 1 and 8 choices of either 0 or 1. As an example, if 3 choices were selected and all came out as 1, will it be written as 111? If so, how will the program know when to go to the next function in the case that every function had to select between 1 and 8 choices of 0 or 1?


texts: While computing signature matrix in min hashing, can I take nth row of the permutation P in which document d has value 1?

texts:
I am learning about some techniques to find similarity between documents. One of the methods is Min Hashing. According to Min Hashing we can find a signature matrix given a random permutation, P. According to this technique in order to calculate signature matrix, we have to take the index of the first row in which document d has value 1.

Is it necessary to do that? If so, then can anyone please explain why?
If not, can we take any nth row of boolean matrix permutation P?


texts: A binomial random number generating algorithm that works when $Np$ is very small

texts:
I need to generate binomial random numbers:

  A binomial random number is the number of heads in $N$ tosses of a coin with probability $p$ of a heads on any single toss. If you generate $N$ uniform random numbers on the interval $(0,1)$ and count the number less than $p$, then the count is a binomial random number with parameters $N$ and $p$.

In my case, my $N$ could range from $10^3$ to $10^{10}$ and my $p$ is around $10^{-7}$.  Often my $Np$ is around $10^{-3}$.

There is a trivial implementation to generate such binomial random number through loops:

getBinomial(int N, double p):
  x = 0
  repeat N times:
    if getUniformRandom() < p: # getUniformRandom() returns a real number in (0,1)
      x = x+1
  return x

This naïve implementation is very slow, $O(N)$. I tried the Acceptance Rejection/Inversion method [1] implemented in the Colt (http://acs.lbl.gov/software/colt/) lib. It is very fast, but the distribution of its generated number only agrees with the naïve implementation when $Np$ is not very small. In my case when $Np = 10^{-3}$, the naïve implementation can still generate the number 1 after many runs, but the Acceptance Rejection/Inversion method can never generate the number 1 (always returns 0).

Does anyone know what is the problem here? Or can you suggest a better binomial random number generating algorithm that can solve my case?

[1] V. Kachitvichyanukul, B.W. Schmeiser (1988): Binomial random variate generation, Communications of the ACM 31, 216-222.


texts: How to maintain completely dynamic convex hull quickly?

texts:
If there's no deletion, we can use $2$ balanced trees to maintain $2$ half convex hulls(up and down). In this way, we can insert $n$ points in $O(n\log n)$ time.(In the beginning, there are no points)

A completely dynamic convex hull means that I can insert and delete a point without rebuilding the whole convex hull, which costs $O(n)$'s time.

My problem is, is there any solutions to deleting points quickly? Maybe it could be solved with persistent data structures, but up to now, I haven't come up with any concrete method yet.


texts: Proof of correctness of Bottleneck Dijkstra Algorithm

texts:
I am working on a bottleneck multicast tree for which I am using bottleneck Dijkstra algorithm.

My question is

1) bottleneck Dijkstra has the same correctness as that of (simple) Dijkstra or not ?

2) if yes then how and if no then how?

Will be happy to see your responses. Thank you


texts:
We are given two decision problems: $Q_1\colon I_1\to\{0,1\}$ and $Q_2\colon I_2\to\{0,1\}$.

By definition, if there exists a function $f\colon I_1\to I_2$ such that for each $x\in I_1$ we have $Q_1(x)=Q_2(f(x))$ then $Q_1$ can be reduced to $Q_2$ by $f$.

Now suppose that $Q_1$ can be reduced to $Q_2$ by a given $f$. My question is: is that true, that there always exists a function $g\colon I_2\to I_1$ such that for each $y\in I_2$ we have $Q_2(y)=Q_1(g(y))$?

I believe so. Since the reduction of $Q_1$ to $Q_2$ by $f$ can be executed in a finite number of well-described steps and since I know explicitly the mapping: $I_1\to I_2$ I think there has to be a way to "reverse" the operation of reduction. Am I right? Is there a formal proof?


texts: Analysing worst-case time complexity of quick-sort in different cases

texts:
I am trying to understand worst case time complexity of quick-sort for various pivots. Here is what I came across:

When array is already sorted in either ascending order or descending order and we select either leftmost or rightmost element as pivot, then it results in worst case $O(n^2)$ time complexity.
When array is not already sorted and we select random element as pivot, then it gives worst case "expected" time complexity as $O(n \log n)$. But worst case time complexity is still $O(n^2)$. [1]
When we select median of [2] first, last and middle element as pivot, then it results in worst case time complexity of $O(n \log n)$ [1]

I have following doubts

D1. Link [2] says, if all elements in array are same then both random pivot and median pivot will lead to $O(n^2)$ time complexity. However link [1] says median pivot yields $O(n \log n)$ worst case time complexity. What is correct?

D2. How median of first, last and middle element can be median of all elements?

D3. What we do when random pivot is $i$th element? Do we always have to swap it with either leftmost or rightmost element before partitioning? Or is there any algorithm which does not require such swap?


texts: Why pointer dereference was once called "decrement"?

texts:
I'm reading McCarthy's paper Recursive Functions of Symbolic Expressions And Their Computation by Machine, where when the author describes the machine implementation of lists, he writes this:

  a. Representation of S-Expressions by List Structure. A list structure is a collection of computer words arranged as in figure 1a or 1b.  Each word of the list structure is represented by one of the subdivided rectangles in the figure.  The left box in the rectangle represents the address field of the word and the right box represents the decrement field.  An arrow from a box to another rectangle means that the field corresponding to the box contains the location of the word corresponding to the other rectangle.

From further reading it isn't clear why would he use the word "decrement" to mean "a pointer to a memory location where the data associated with the given list element is stored".  It doesn't exactly translate into "dereference" as used today when describing languages s.a. C, but if, in C terms, you were to treat the contents of "decrement" field as a pointer, and then dereference it, you'd get the value of the element.

So, why "decrement"?  Was something really decremented?  Was it due to some particular features of memory layout of IBM 704?


texts: Definitions of Computer Architecture and Computer Organization seems confusing

texts:
So there was this question in one of my class tests. It may seem very simple and straight-forward, but I am unable to catch up with its meaning or explanation. I have referred my textbook of COMPUTER ORGANIZATION AND ARCHITECTURE by William Stallings. But that has just got me more confusing.
The definitions according to my textbook are:

Computer architecture refers to those attributes of a system visible to a programmer or, put another way, those attributes that have a direct impact on the logical execution of a program. Computer organization refers to the operational units and their interconnections that realize the architectural specifications.

I even referred to some websites which students at our university, if not the whole country, mainly depend on, but that didn't me help either.
The question is to mark which of the following is/are true:

Computer Organization refers to the design of functional blocks in a computer system.
Computer Organization is responsible to integrate functional blocks in a computer system.
Computer Architecture refers to the design of components and functional blocks in a computer system.
Computer Architecture concerns with the integration of functional blocks to build a computer system.

My marking was 2nd and 3rd option. My explanation about the same was: architecture would include designing of a structure while organization would be, well, the very English definition of how things are organized in a particular manner. I know this may be wrong, hence I am asking you for an explanation regarding which options are correct. Any help will be appreciated. Thank you.


texts: Best Approach To Parse Human Readable Text To Machine Readable (CSV)

texts:
I am attempting to parse a large amount of text that cannot be readily used by other software due to the human readable design. However, each "section" of the text has the same format. By "section", I mean lines 1-10 (section 1) will have the same format as lines 11-20 (section 2). My plan is to loop through this text and gather all sections into a list. Then convert that list into a CSV.

Example:

####################################
123456789   first-name last-name   2/25/2018
------------------------------------
more-user-info1               12345
other-info1
123                   user-name1
------------------------------------
even-more-data1
####################################
112233445   first-name last-name   1/1/2018
------------------------------------
more-user-info2               78900
other-info2
555                   user-name2
------------------------------------
even-more-data2
####################################
<piece 3 here> ...

So to give you an idea ###... means new section.

My question is what is the best approach to parsing this data? This is just an example, a real section has a lot more data and a lot of edge cases/optional data. This is also coming from a super old program so I am not aware of any blueprint or business rules around the data.

I am currently using regex to find the data I need to store. Are there any options besides regex to parsing non-strictly structured text?


texts: Creating Priority Search Tree bottom up from a Complete Binary Search tree in O(n)

texts:
I have a Complete Binary Search Tree of points ordered(sorted) on the y-axis (such that the point with the mid y of all the points is the root and its left children have decreasing y from the root and its right children have increasing y from the root (recursively and complete)). I want to convert this into a min-heap on the x axis such that it has the property of a Priority Search Tree (where every point to the right of the root has a y value greater than the median y of the all the points set minus the root of the min-heap and everything on the left of the min-heap root has y value less than the median or equal to the median y of the set of all the points set minus the root). And I am looking for an algorithm that runs in O(n) time because I want to implement this into another algorithm.
From Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars: Computational geometry on p. 228 They imply a bottom up construction approach, but I just can't wrap my head around how to due this correctly, and how to prove the implementation is correct. I understand how to convert it to a min-heap using bottom up heap construction, but I don't know how to get the Priority Search Tree property from it.
I have read the following links but none fully answer the question, (don't answer correctness):
How to convert a Complete Binary Tree to a Priority Search Tree in O(n)
Creating a priority search tree to find number of points in the range [-inf, qx] X [qy, qy'] from a set of points sorted on y-coordinates in O(n) time
https://stackoverflow.com/questions/58006779/making-priority-search-tree-with-sorted-y-co-ordinates-in-on-time
Any help will be much appreciated!


texts:
Consider the alphabet E = ${[abc] : a, b, c \in 0,1,...,9)} $  Example [234], [567],
[897] are symbols of the alphabet. For a string $w \in  $  let n(w) denote the number represented by $ w $:  Example for symbol [345], n([345]) = 345.

1) Describe a DFA for the language of strings of the form $[x_0y_0z_0][x_1y_1z_1]    [x_ny_nz_n]$ such that

$n(x_n...  x_1x_0) + n(y_n...  y_1y_0) = n(z_n...  z_1z_0)$

This language corresponds of reading the numbers from right to left and position
by position; this is how we add numbers by hand.Example $[819][606][213]$ is in the language because 268 + 101 =369.

How can we describe something like this? $M = (Q, E, d, q_0, F)$

where Q : ?

E = ${[abc] : a, b, c \in 0,1,...,9)} $

d: ?

$q_0 =  $

F: ?


texts: Recognizing features in images (uncontrolled environment)

texts:
I have been working for some time in several kinds of image recognition. They work well. One example is , character or shape recognition. I have implemented this in an embedded processor and I can recognize shapes and letters with this.

Now I am working on implementing this with a Hololens. Using my algorithms I have already achieved an automatic digitalization of images (meaning that I can convert a image taking by the camera to black and white using automatic thresholds).

My question is the following:

So far my work has been on controlled environments. Meaning that I pointed the embedded camera exactly to a piece of paper with the shapes or characters I wished to recognize.

Now I am working on a uncontrolled environment. The hololens takes photos of the general environment surrounding me. I wish to recognize shapes or letters there but they can be anywhere. The possibilities are more varied than before.

I would like to get advice on how to treat this, where can I find good resources, books tutorials etc to address this problem.

Thanks


texts: transformation of constraint satisfaction to SAT

texts: How can any Constraint satisfaction problem be converted to an instance of Satisfiability? I have a CSP and i know its NP hard to solve it, but i would like to convert to an instance of k-SAT, but im not sure of any algorithm for transformation


texts: I'm to calculate the tag, index and offset for a given setup

texts:
Total Memory size = 65,536 bytes
Number of cache blocks = 32 cache blocks
Cache size = total 512 bytes
So using this info provided I cannot figure out how to calculate the cache block number.
I know if number of cache blocks =2^M then the last M bits is the cache index. But how to calculate the block number? and then finally calculate the bits required for tag index and offset..


texts: Minimization of DFA- one state mark or no mark?

texts:
I want to know, what if the DFA is merged states. So if my DFA starts with q0 and then have (q0,q1) state it goes to with an 'a' for example. How do I do the table filling method.

I tried to rename the merged state, for example turning (q0,q1) to q4 for example. But then the issue is when I try to do the table filling. With the input in the Automaton, I get only one state, sometimes the final state. So do I mark it.

For example, I renamed (q0,q1) to q4. Now in the table, if I want to find out the marking for q0 and q4. With an 'a' I get q4,q4 for both of the state and with 'b' I get nothing from q0 and q2(final state) from q4. I know since q4,q4 does not exist I do not mark. But I only get one state, which happens to be the final state. Do I mark q0,q4 part of the table or do I leave that blank aswell

edit:

q0 --a-> q2(a to itself) --b-> q3(final)<--b--q4

so if i do the table filling method, Myhill Nerode Theorem, say i want to find out where q1, q4 goes with a, q1 goes to q2, q4 goes no where. then for b, q1 goes nowhere and q4 goes to q3(final state). can I mark the table if i only get one final state??


texts:
Why does the following DFA have (to have) the state $b_4$?

Shouldn't states $b_1,b_2,b_3$ already cover "exactly two 1s"?
Wouldn't state $b_4$ mean "more than two 1s", even if it doesn't trigger an accept state?


texts: Algorithm for scheduling timetable for student management system

texts:
I am developing the timetable module for a student management system. I am finding it difficult to design/develop it. It can be assumed that a given teacher is capable of teaching any standard whether it's primary or secondary. Can anybody please help from where to start on this,given the following constraints :

The number of teachers for a particular subject X are less than
number of classes in the school.
All teachers should share equal workload.( This has to be calculated
afresh whenever a teacher goes on leave )
The schedule/timetable should be such that if a teacher of subject X
is on leave then there should be replacement for that, I mean another
teacher of the subject X should be available at that time frame.( In
case multiple teachers of a given subject X are on leave then
scheduling should be efficient )

The only thing I got is to make the timetable such that given a time slot and subject X, only one class can have that subject being taught. It simply means non-overlapping permutations. I don't know if it is correct. The workload sharing problem is more difficult I guess. If details are insufficient, rather than voting it down please add comment so that I can update it.Any valuable suggestion will help


texts: Big theta of function with multiple types of n

texts:
I have the following function:

$\displaystyle\frac{n \cdot 7^n+\frac{8}{n!}}{(n+7) \cdot 7^n}=\Theta(1)$

I don't how they come to this. What is the proper way to analyse a function to theta notation?


texts:
Claim: If we are training a hard-margin SVM on a set of perpendicular training vectors which can either be classified as "positive" or "negative," will every training vector end up being a support vector if the data is linearly classifiable?
I can't seem to come up with a counterexample to this claim. Any ideas?


texts: Is this a correct way to thing about asymptotic notations?

texts: I am reading a book on algorithms. It says that $2n^2+3n+1=2n+\Theta(n)$. For a person like me who has studied some set theory but not from axioms, this notation seems a bit insane. I was wondering why are we allowed to compute a sum of a polynomial and a set. Why not just teach that for every $n\in\mathbb N$ there is a $f:\mathbb N\to \mathbb N$ such that $f\in \Theta(n)$ and $2n^2+3n+1=2n+f$? Is this a formally correct way to think $\Theta$ notation? Or should I learn some other book to learn O-notations, like J.D. Murray: Asymptotic analysis? Or do I have some misunderstanding that becomes clear if I first learn some book of axiomatic set theory?


texts:
Is this language regular?
${w ∈ (a + b)∗ : |u_{a}|>= 2009 · |u_{b}|}$ for every non empty prefix $u$ of string $w$}
I think it's non-regular. I tried concatenation of $L_{prefix} $={${ u : |u_{a}|> 2009 · |u_{b}|}$} and $L_{2}= a^*b^*$.
$L_{2}$ is regular.
I tried to show that $L_{prefix}$ is non-regular using pumping lemma.
for string z= $a^{2009n} b^n$
pumping 'a'
for i=0 : $$ z=uv^iw $$
$$z= uv^0w   $$
$$z=a^{2009n-p} b^n$$
so there is less 'a' than 2009'b'
pumping 'b'
for i=2  $$z=uv^2w $$
$$z=a^{2009n} b^{n+p} $$
again to much 'b' and less 'a' than should be.
So this is non-regular language and concatenation of this two also is non-regular .
Is it correct? Or maybe it's somehow regular?


texts:
This particular language:

$$L = \{ u u^R v \,:\, u, v \in \{0, 1\}^+\}$$

is giving me a lot of trouble.
I highly suspect that its non-regular, considering that $\{ u u^R : u \in \{0, 1\}^+\}$ is non-regular, and I can't seem to reason out a DFA for it.

However, trying to achieve a contradiction with the pumping lemma is giving me a lot of trouble. because of the arbitrary $v$ in the construction.
In particular, if the string starts with $00$ or $11$ it is automatically in the language because we can pick $v$ as the remainder and the first two characters are trivially the reverse of each other.

Issues like this seem to thwart my every attempt at applying the pumping lemma. With $p$ as the pumping length, I tried something like $(01)^p (10)^p 1$ but you can simply pump up the starting character to obtain a string that starts with $00$ (and pumping down also works), so this string doesn't work for contradicting the pumping lemma.

I'm pretty stuck on ideas for strings that will contradict the pumping lemma, so I could appreciate a hint on the problem. (Perhaps it is regular? That's still in the back of my mind too)


texts: What is the difference between Decision Support System and Machine Learning?

texts:
I have started reading about Decision Support Systems which according to wikipedia is "a computer-based information system that supports business or organizational decision-making activities".

I have seen papers suggesting intelligent decision support systems, does that means a DSS necessarily utilizes Machine Learning ? How is a DSS different from Machine Learning or vice versa.


texts: Full circularity vs strong circularity for attribute grammars

texts:
Attributes of an attribute grammar can have a circular dependency. In my compiler construction course I learned, that there are two types of circularity for attribute grammars:

full circularity can be checked in exponential time
strong circularity can be checked in polynomial time

Full circularity implies strong circularity, but not vice versa, so if there is an attribute grammar that is strong circular, it might still not be full circular. Thus, if I reject all strong circular attribute grammars, I might reject some grammars even though they are not full circular. I tried to come up with a dividing example to better understand this case, that is an attribute grammar that is strong circular but not full circular, but with no luck yet.

Question

Is there a dividing example that makes the difference clear?
Are there well known real-world attribute grammars that are strong circular but not full circular?
Would it be a real limitation for a tool to accept only strong non-circular grammars?

I assume the terms strong circularity and full circularity are well known. If they are not you can find the lecture notes here (lecture 12, 13 and 14).


texts: How to determine letter boundaries in Huffman encoded strings?

texts:
I'm trying to understand the Huffman compression algorithm.

Lets assume the word : YESSSS

According to Huffman tree we will get :

S : 4 times -> Code : 0
Y : once    -> Code : 01
E : once    -> Code : 00

at the end YESSSS will become : 01 00 0 0 0 0

So far everything is clear.

Now my problem is in the space between the binary words. How this can be stored in memory ?

In another words ?

How to computer will know that that :

the first character has two bits
the second character has two bits
the fourth other characters has only one bit

Because 01 00 0 0 0 0 doesn't have the same meaning than 01 00 00 00

01 00 0 0 0 0 means : YESSSS
01 00 00 00 means : YEEE

Any ideas please ?


texts: Convolutional Neural Network for Insects

texts:
I've recently started learning CNN's. I need a CNN that is specialized for insects detection. Dead insects will be put on a piece of paper / container, then images will be taken from a same distance, and are at same pixels.

I am expecting to prepare my own training datasets:
- Thousands of images of a particular insect, let's say a housefly
- Each image contains only one housefly
- Consistent lighting for the photos taken

Then, I will start to train the CNN, save the model and so on.
I'm not sure about the following:

During operation of the model, will it still be able to detect the housefly if there are other insects in the image? (not covering the housefly of course)
If I want my model to recognize housefly only, so the training datasets contain housefly only, true or false?
If later I want my model to recognize 2 types of insects, housefly and ant, what type of datasets I need to prepare?
I will eventually need to count the amount of houseflies in an image. Can anyone direct me to a correct path towards feasible methods?
Does anyone has useful resources that explain on how to determine the suitable amount of convolutional layers (CL) and fully-connected layers (FCL)? The default seems to be 2 CL and 2 FCL, but I am wondering why not more than that?


texts:
For the following jobs:

The average wait time would be using a FCFS algorithm:

(6-6)+(7-2)+(11-5)+(17-5)+(14-1) -> 0+5+6+10+13 -> 34/5 = 7 (6.8)

What would the average turnaround time be?


texts: Pseudo code for read operation in an i-node file system

texts:
I would like to know how a pseudocode for the read operation in an i-node file system would look like?
int read(fd, buf, len){}
what do we return exactly, and do we have to check that the file is in a direct block pointer?
Thanks a lot.


texts: Proving Undecidability with reductions - Why do some proofs not use an Oracle?

texts:
I'm specifically referring to this group of questions here: https://www.cs.rice.edu/~nakhleh/COMP481/final_review_sp06_sol.pdf
So as I've learnt it, say we want to prove a new Language L is undecidable using a known undecidable language D, we use Oracle calls to L to solve an instance of D right?
In none of these questions is an oracle used - For example, with L9 :"M' on input w: it
runs M on x and accepts if M halts on x" That's the algorithm; no oracle is used. I understand the reasoning to their solutions, but shouldn't they be using an oracle call? I'm very new to this so sorry if I'm misunderstanding


texts: Interpretation of an asymptotic notation

texts:
Assume that we measure the complexity of an algorithm (for some problem) by two parameters $n$ and $m$ (where $m \le n$). What is the formal interpretation of the following claim: there is no algorithm that solves the given problem in $o(m + \log{n})$?

In particular, does it mean that an $O(\log{n})$ algorithm is possible?


texts: Understanding a paper on polynomial recursion in all finite types

texts:
So I wasn't sure weather or not this counted as "research level" or not but I figured it wasn't so I decided to post it here.
There is a paper by S. Bellantoni et al. called "Higher Type Recursion, Ramification and Polynomial Time (1999)" which can be found here. It mentions a notation of a complete type denoted $!\sigma$ but I am having trouble understanding it. They have a reduction rule for it but I don't understand what the $\kappa$ is doing there or how these things are introduced. The best I can manage is that you can introduce a complete type anytime you want and you can get it's value out by applying some random value. This makes no sense however as this would make it a mere wrapper for incomplete types.
The reduction rule they give is
$(!r)\kappa \to r$
This reduction rule seems to suggest that the $!$ operator is like the K combinator.
They also give the semantics of $!r$ which seems to suggest that there is no difference
$[[!r]]_{!\sigma} = [[r]]_{\sigma}$ (I can't seem to figure out how to write semantic brackets properly)
Another clue as to what this thing means is the following reduction rule
$\mathcal{R} g h !(s_i n) \to h \kappa !(s_i n) !(\mathcal{R} g h !n)$
So it seems tell me that to make a term of complete type I can just use the $!$ operator on a term of incomplete type. It also tells us (where it gives the type of $\mathcal{R}$) that $h$ is of complete type so I can see that to get the corresponding incomplete type out of a complete type I can just apply some random term denoted by $\kappa$.
My interpretation must be wrong however because this would mean that there is no distinguishing difference between complete and incomplete terms.
My best guess is that there is a rule about the number of times incomplete types can be used in an expression that has not been specified as far as I can see. They even give something like this as the intuition of what a complete type is but I see no formal rules on the matter. Did I just miss it?
What does a complete type mean? How does it differ from an incomplete type?


texts:
I know how a Turing machine works, how it accepts a language but in some.

In some scenarios we would like to use counters.
For example, I want to develop a machine that accepts $\{0^{2n} : n \geq 0\}$. How can I count the number of zeroes?

If some one of you could solve the following problem for me it would help my understanding of these matters:

  Design a Turing machine for $L = \{1^{3^n} : n \geq 1\}$.


texts:
Let's say a procedure called 'decision(x,q)' is available as a 'black box'
X is the input set and Q is a real number Q.

I need to design an algorithm that reports "yes" if there exists a subset of X whose total sum is = Q
otherwise, it reports "no".

Running time is not an issue, it just needs to have all actual numbers in the subset  and it can't make more than O(n) calls to the procedure.

I believe this can be solved with dynamic programmming.


texts: I've read that MAJSAT is PP-complete.  Under what type of reduction is this true? What kind of reductions are usually used in order to prove PP-completeness?


texts: How to formulate Traveling Salesman Problem (TSP) as Integer Linear Program (ILP)?

texts:
Consider this distance matrix of an asymmetric TSP instance:
$$
\begin{matrix}
& c_0 & c_1 & c_2\\
c_0 & 0 & 1 & 2\\
c_1 & 2 & 0 & 1\\
c_2 & 1 & 2 & 0
\end{matrix}
$$

One optimal tour (with a total distance of 3) is clearly: $$ c_0 \rightarrow c_1 \rightarrow c_2 \rightarrow c_0$$

Now we can reformulate this as an ILP. Let $e_{i,j}\in\{0,1\}$ denote the presence or absence of the directed edge from $c_i$ to $c_j$ in the tour (0 - edge is not in the tour, 1 - edge is in the tour). Then we obtain the ILP by:

setting the objective $$\text{minimize}\;\;\; 1\cdot e_{0,1} + 2\cdot e_{0,2} + 2\cdot e_{1,0} + 1\cdot e_{1,2} + 1\cdot e_{2,0} + 2\cdot e_{2,1}$$
ensure that we arrive at city $c_i$ from exactly one other city and depart from $c_i$ to exactly one other city
$$\begin{align*}
e_{0,1} + e_{0,2} = 1\\
e_{1,0} + e_{1,2} = 1\\
e_{2,0} + e_{2,1} = 1\\
e_{1,0} + e_{2,0} = 1\\
e_{0,1} + e_{2,1} = 1\\
e_{0,2} + e_{1,2} = 1
\end{align*}$$
ensure we do not find a set of minor tours (we want a complete tour through all 3 cities) by enforcing the following constraints for the artificial variables $u_i$ (Miller-Tucker-Zemlin subtour elimination constraints):
$$\begin{align*}
u_1 - u_2 + 2\cdot e_{1,2} \leq 1\\
u_2 - u_1 + 2\cdot e_{2,1} \leq 1\\
\end{align*}$$

Is this transformation correct? Its probably not because when I try to use a Solver it says that the ILP is infeasible.

I tried to follow the steps on Wikipedia:
https://en.wikipedia.org/wiki/Travelling_salesman_problem#Integer_linear_programming_formulation

Edit 1

We can verify that there must be a solution to the ILP by the following considerations:

There are exactly 2 solutions to the equation system under 2.
$$\begin{align*}
\text{(1)}\;\;\;e_{0,1} = e_{1,2} = e_{2,0} = 1 \land e_{1,0} = e_{2,1} = e_{0,2} = 0\\
\text{(2)}\;\;\;e_{0,1} = e_{1,2} = e_{2,0} = 0 \land e_{1,0} = e_{2,1} = e_{0,2} = 1\\
\end{align*}$$

Since there are 6 variables and each variable can have only 2 values, we can easily verify this by testing all $2^6$ variable assignments.

Now we can observe that either $e_{1,2} = 0 \land e_{2,1} = 1$ or $e_{1,2} = 1 \land e_{2,1} = 0$ holds for the solutions.

In the first case we can satisfy the inequations under 3. by $u_1 = 2 \land u_2 = 1$ in the latter case by $u_1 = 1 \land u_2 = 2$.

Edit 2

This is annoying. I used another tool (LPSolve) to solve the exact same ILP and got the solution instantly. Seems that my transformation was correct and the tool is buggy.


texts: Distinguishability given black box access to the distribution

texts:
Consider two probability distributions $D$ and $U$, over $n$-bit strings, where $U$ is the uniform distribution. We are not given an explicit description of $D$: we are only given black-box access, ie, we are only given a sampling device that can sample from $D$. Consider a sample $z \in \{0, 1\}^{n}$, taken from either $D$ or $U$. We want to know which one is the case, and to do that, we consider polynomial-time algorithms that use the sampling device.
Let the best distinguisher algorithm use the black-box sampling device a polynomial number of times (at most) and get samples $z_{1}, z_{2}, \ldots, z_{k}$ from $D$, for some polynomial $k$. My intuition is that, if this best algorithm decides that $z$ indeed came from $D$, then it must be true that $z_{i} = z$ for at least one $i \in [k]$. In other words, since we know nothing about $D$ or its support, we have to "see" $z$ at least once in the samples we collect from $D$ to ascertain that $z$ indeed came from $D$. How do I mathematically formalize this statement?
Also, does this same intuition hold if we are given a polynomial number of samples as input (taken from either $D$ or $U$) instead of just one and are also given access to a black-box sampler for $D$?


texts: Compiler - Why is the grammar not suitable for shift-reduce

texts:
Consider this example:

stmt => if (expr) stmt | if (expr) stmt else stmt | other

Why can't we use shift-reduce on this?

This is a compiler homework and I really need to answer it.


texts: Keywords for classification of 2D time series data?

texts:
Trying to find the right search terms for literature on classifying 2D time series data.

I am looking at data from positional tracking of a swarm of insects over time. I have example datasets for specific insect behaviors, and I would like to play around with training a classifier on these.


texts:
To answer the question below,

4-SAT: Given a formula in Conjunctive Normal Form, where each clause contains exactly 4 literals, does it have a satisfying truth assignment?

I was going to prove that 4-SAT is in NP-complete. But I saw that the way to prove CNF-SAT is in NP-complete is a bit different to the way of proving 4-SAT is in NP-complete.

Is it sufficient that I just answer that question by proving 4-SAT is in NP-complete?

Thanks in advance!


texts: How can we avoid mistake in LL(1) parse tree?

texts: I'm learning about LL(1) parse tree. We need to find first and follow in order to construct a LL(1) parse tree. Each and every time when I find first and follow I'm missing one or the other terminal as we to back track each production. When makes me end up in wrong LL(1) parse tree. Is there any standardized way to check the first and follow table ?


texts:
My professor mentioned the below statement in class but without a proof. I am trying to prove it for myself as I don't understand 100% why this is always the case.
Given is A, a subset of {0,1}$^*$.

ε $\in\ A^+$ <-> ε $\in\ A$, where ε is the empty word.
I thought of doing a proof by contradiction to show -> by assuming the empty word is not part of A$^+$.

Any help is much appreciated!


texts: Functional Unit and Micro-operations Schematics

texts:
I'm sitting an exam on Computer Architecture in a few days and i'm stuck on a particular type of question.

I'm asked to:

Provide a detailed schematic for a functional unti that implements the following micro-operations

Any help would be great even just a nudge in the right direction.


texts: How to generate graphs with a Hamiltonian path?

texts:
I need to create a graph generator for my next project. Generally algorithms are trying to find a Hamiltonian path in a graph. So I can create a graph generator, generate a graph, and then I can decide whether the graph has a Hamiltonian path or not. If not, I can regenerate the graph but this is not a cool way.

I want my generated graphs that always have a Hamiltonian path. My graph has two additional conditions:

Vertices can only have 2, 3, or 4 edges.
Possible number of vertices follow the sequence 6, 10, 15, 20, 25...n-5,n where n % 5 = 0.

How should I start, and how do I achieve this easily?


texts:
The memory that stores the input is called the input memory. The memory that an algorithm additionally occupies during the computation is called the working memory.

$\textit{Model of Computations}$

Word RAM : This a very well known model of computation.
Read-only word RAM: Where input memory is assumed to be read-only.
Permuted word RAM: Allow input memory to be permuted but not destroyed.
Restore model: This is a variant of permuted word RAM model, where the input memory is allowed to be modified during the process of answering a query, but it has to be restored to its original state afterward.

I know that why word RAM is the interesting model of computation in many cases but I don't have any idea what is the motivation behind studying problems in 3 and 4. Let us take the example of DFS(Depth-first Search). I know that the problem has been studied in word RAM and I also know about the space complexity of it in that model. I recently come across one paper in which DFS (see this) has been studied in 4th model of computation. The result is that DFS and BFS in place memory in linear time.

Question: What is the motivation behind restore model of computation?


texts: Trying to understand interpretation and denotation in FOL

texts:
I am going through the book "Knowledge Representation and Reasoning" by Brachman and Levesque.

So an interpretation $ F $ is defined as a pair $ \langle D,I \rangle $ mapping from a set of objects $ D$ called domain of the interpretation and $ I $ is a mapping called interpretation mapping from the non-logical symbols to functions and relations over $D$.

Then it has been written that   $ I $ will assign meaning to the predicate symbols as follows:

To every predicate symbol  P of arity $n$,  $I[P]$ is an n-ary relation, that is,
 $I[P]$  is contained in $ D \times D \times D \times \dots \times D$.

Now for denotation  it is written that  for an interpretation $ F = \langle D,I \rangle $ we can specify which elements of $ D $ are denoted by variable free term FOL.

And hence the notion of variable assignment  $ \mu $ has been introduced and the following two rules have been introduced:

Given an interpretation  $ F $ and a variable assignment  $ \mu $, the denotation of the term $ t $ is written as $ \|t\|_{F \mu} $ and defined as follows:

If $ x $ is a variable then $ \|x\|_{F \mu} =  \mu [x] $.
If $ t_1 ,\dots,t_n$ are terms and $ f $  is a function symbol of arity $ n $  then  $ \| f(t_1,\dots,t_n)\|_{F \mu} = G( d_1,\dots,d_n) $,
where $ G = I[f] $, and $ d_i =  \| t_i\| _{f \mu} $.

I am a bit confused about how to interpret the last two rules.

So the act of choosing elements from $ D $ to represent the arguments of the function symbol is represented by $ \mu $? Will it be right to say so?

How exactly are $ f $ and $ G $ related?

The output is evaluated by computing $ G $ for values which get substituted  in the argument which is represented in  $ d_i =  \| t_i\| _{f \mu} $ of the second rule.

But I could not understand how are the above two rules recursive?
What exactly should I conclude about the way $ I $, $ G $ , $f$ and $ \mu $ are related to each other and what exactly do they mean?
Is my understanding correct?

Attaching the screenshots from the book:


texts: A path modification problem in directed graphs

texts:
We start with a given finite directed graph. It could represent transitive relations such as:

data transfer paths in social networks,
transportation connections, etc.

Let us use the notation

A->B to denote a directed edge from node A to node B and
A=>B to denote a path from A to B.

Example 1: Social networks. An edge A->B can mean: A can send data to B. So if we have edges A->B and B->C  we have a path A=>C and data can be sent from A to C.

Example 2: Rail connections. An edge A->B can mean: there exists a rail connection from A to B. So if we have edges A->B and B->C  we have a path A=>C and there is a rail connection from A to C.

We would like to locally modify the graph, in order to add or remove directed paths (not just edges). For example, we may wish to add or delete data paths or rail connections. We may wish to make it possible or impossible for C to receive data, directly or indirectly, from A. Or we may wish to make it possible or impossible to go by rail from A to C. We may have several (possibly conflicting) requirements such as these.
Local modifications are rarely possible without implying other changes, some of which can be unwanted.

Adding paths.  Adding a path X=>Y, is simple because it is
sufficient to add an edge X->Y. However by doing this we will also
add paths from all Z such that Z=>X to all W such that Y=>W. Some of
these paths may be unwanted. Is the addition of the new path
important enough to justify the addition of some unwanted paths? Or:
how can the new path be added with a minimal effect on the rest of
the graph?
Removing paths. For example, if we want to remove a path A=>C such
as A->B->C we must remove either A->B or B->C. The removal of either
edge may imply the removal of other paths that contains this edge.
Hence the need of removing certain paths may force the removal of
others, some of which can be wanted. Is the removal of the unwanted
path important enough to justify the removal of the others? If there
is a choice of paths to be removed, which ones to remove? Or: how
can a path be removed with a minimal effect on the rest of the
graph?

So in general, locally adding or removing paths can have ripple effects that can involve other paths, possibly the whole graph. After adding some paths, others should perhaps be removed and after removing some, others should perhaps be added. This becomes messy. If several path constraints are present, the problem may be infeasible. This could perhaps be seen as an optimization problem, where we must weigh the relative importance of paths: of those we explicitly want to add or remove and of those whose addition-removal may result.

This seems an interesting practical problem. How can this problem be formulated in a way that may lead to a solution? Has this problem, or similar ones, already been studied? I have found some literature on the problem of adding-removing nodes, but I have not found any on the problem of adding-removing edges. In any case, this problem is different, as we want to add-remove paths.


texts: Finding the Shortest path in undirected weighted graph

texts: Is there an algorithm for finding the shortest path in an undirected weighted graph?


texts: Is A times B of NP-complete languages A and B necessarily NP-hard?

texts:
If both $A$ and $B$ are NP-complete languages, would $A \times B$ be necessarily NP-hard? Here, $A \times B = \{\langle u,v \rangle \mid u\in A, v\in B\}$.

So my colleague's answer was no, it's not necessarily NP-hard because you can verify in polynomial time that $u \in A$ and the same for $v \in B$, but you see this is not the case I said, and when I tried to explain why this is wrong, I mumbled and stumbled because I suddenly came to realize that I don't really comprehend the concept to its full depth!

Any way I said if $\langle u,v \rangle$ was not NP-hard to decide, then also would the language $A$ for instance, because you can look at $A\times A$ as a reduction from $A$.

My question is, if I'm right what's my colleague's error and how to explain it, and if I'm wrong which I guess I'm not (this far I do know), then what's wrong about my theory?


texts: Applications in Computer Sciences of Partition Functions

texts:
A partition function computes the number of ways an integer $n$ can be represented as the sum of $m$ other integers. For some value $n$, we have a partition function $p(n)$.

These were studied extensively in mathematics by MacMahon, Hardy, Littlewood and Ramanujan. Rademacher provided a way to approximating $p(n)$, improving on a formula by hardy and Littlewood. More recently, K. Ono and A. Wiles have come up with new interesting results.

Are there applications of partition functions in Computer Sciences, perhaps in the theory of elliptic curve cryptography or complexity?


texts: Complexity of computing the antiderivative of a given function

texts:
Disclaimer: I don't know much computational complexity theory. I am nevertheless curious.

If function $f(x)$ has a certain level of computational complexity (which I actually don't know how to measure), what can we then say about the computational complexity of the following indefinite integral?

$$\int f(x) \, \mathrm d x$$

For example, can we say something about how long it takes to approximate the integral of $f$ within an error of $\epsilon$, given that we know how long it takes to compute $f$ within an error of $\epsilon$?


texts: It is possible proove the complexity of each query in a Segment Tree to O(log N) with recursion tree

texts:
Maybe the title is bad format but, I want to ask if is possible proof the Segment Tree complexity with the recursion tree.
In other words I'm making a simple report on segment tree and I want to try to prove with a simple image that the complexity time on each query is O(log N), so to do that I make a simple assertion that if the merge sort complexity is O(N log N) so sort the array, I can say that to traverse only one part of the tree I need only O(log N) time.
And the image that I choose to prove that is the recursion, like the tree below.

I will post also what I'm trying to explain inside the report and maybe there is some different idea to prove that.

p.s: Sorry for the error inside the report image but it is without spell check and I'm a person with a dyslexia problem


texts: Data structures as algorithms themselves

texts:
Can data structures be thought of as algorithms themselves?

For example, I could implement a stack data structure that has certain non-functional characteristics.

Is the separation between data structures and algorithms formally defined?


texts: Solving using the master theorem: T(n)=T(n/2)+n⋅log n and T(n)=T(n/8)+2.n

texts:
Could someone help me with these 2 questions?

I do not understand the case 3

$T(n) = T(n/2) + n \log n$
$T(n)=T(n/8)+2 n$


texts: How to determine $10^{\log n}$ and $3n^2$ which grows faster asymptotically?

texts:
My think is pretty easy that $10^{\log n} = n$, which is growing slower than $3n^2$.

However, many tutorial shows that $3n^2$ ranks before $10^{\log n}$.

I'm really confused.


texts: Computer Architecture, cache hit and misses

texts:
I am currently enrolled in a computer organization and design class, which I am struggling mightily with, and I have a final homework in my class that I need to get a perfect score on. One of the questions covers cache hit-misses, and the lecture we had on the subject was relatively brief. The question I have having issues with is:

A processor has a CPI of 1.4 with level 1 caches with a 100% hit rate. When running benchmarks, the level 1 instruction cache has a 1% miss rate and the level 1 data cache has a 3% miss rate. 30% of the instructions access memory through load and store operations. Main memory has a 50 nano second access time and the clock is running at 2.5 GHz.

What is the actual CPI of the processor with just the level 1 caches?

A level 2 cache is added to the processor.  The hit time of this cache is 1.5 nanoseconds, and it has a global miss rate of 0.5%.  Compute the actual CPI of the processor after the addition of the level 2 cache.

What is the speedup achieved by adding the level 2 cache?

So my first attempt is this:

I-cache miss rate = 1%
D-cache miss rate = 3%
Miss penalty to main memory = main memory access time / clock time
50 ns / .4 ns per clock cycle = 125 clock cycles
Base CPI = 1.4
Load and store = 30% of instructions
Main memory access time = 50 ns
Processor clock = 2.5 GHz

What is the actual CPI of the processor with just the level 1 caches?

Instruction miss cycles = I x 1% x 125 = 1.25 x I
Data miss cycles = I x 30% x 3% x 125 = 1.125 x I
Total number of memory-stall cycles is 2.375 I
Total CPI including memory stalls is 1.4 + 2.375 = 3.775

A level 2 cache is added to the processor.  The hit time of this cache is 1.5 ns and it has a global miss rate of 0.5%.  Compute the actual CPI of the processor after the addition of the level 2 cache.

Secondary cache access time = 1.5ns
Processor clock = 2.5 GHz
Miss penalty for an access to second-level cache = 1.5ns / .4 ns per clock cycle = 3.75 clock cycles
For a two level cache, total CPI is the sum of the stall cycles from both levels of cache and the base CPI
1.4 + (.005 x 125) + (.005 x .3 x 125) + (.01 x 3.75) + (.01 x .3 x 3.75) = 2.26125
*****This is where I'm most unsure. The "global miss rate of 0.5%" is throwing me off, and I'm not sure I performed this calculation correctly.**

What is the speedup achieved by adding the level 2 cache?
3.775 / 2.26125 = 1.67
***This answer is dependent on the result from the calculation above. If I did that wrong, this answer will be different.


texts: Equivalence relation Mathematical base In Computer science

texts:
I have this equivalence relation problem:

Let $R$ and $S$ be two equivalence relations on the same set $A$. Define a new relation $U$ such that $U(x,y) \leftrightarrow [R(x,y) \text{ or } S(x,y)]$. Is $U$ necessarily an equivalence relation?

I said that is was an equivalence relation because $U$ is only true if $R$ or $S$ is true, and only depends on one. I do not know know exactly how to explain it, or prove this. Should I use proof by contradiction to prove this and make the negated statement $!U(x,y) \leftrightarrow {![R(x,y) \text{ or } S(x,y)]}$ and from this we can see that $U$ is an equivalence relation because the negation is saying that $R(x,y)$ or $S(x,y)$ isn't an equivalence when it actually is?

I am kind of stuck so any help is appreciated.


texts: In the PCP, can we remove all dominos with the same top and bottom strings and still get a match?

texts:
Suppose we have an instance P of the PCP, and there exists a match for it.
I am wondering if we remove all dominos that has the same string on the top and bottom, would there still be a match?
My intuition is yes, there would still be a match, but i don't know how to justify.
Can someone please give me some hints or give a counterexample?


texts: Are memcomputing and neuromorphic computing the same thing?

texts:
As the title reads, I’m just trying to understand if there is any difference between memcomputing and neuromorphic computing. If so, what are they?

Memcomputing: https://www.popularmechanics.com/technology/a16308/memcomputer-quantum-computing-alternative/


texts:
Definition from wikipedia:

  A graph is an ordered pair $G = (V, E)$ comprising a set $V$ of nodes together with a set $E$ of edges, which are two-element subsets of $V$.

The set of all finite graphs (modulo isomorphism: we don't want nodes to have identities) is countable and could be enumerated. But what would be an efficient (low-complexity, from a programming point of view) injection from graphs to $\mathbb{N}$?

Edit: Gilles' comment indicates that it is not know whether there is a such function feasible in polynomial time. An example of an exponential-complexity function would be good enough; we can surely do better than a brute enumeration?


texts: Can two distinct strings create the same parse tree for a given grammar?

texts:
More specifically: for any arbitrary CFG, is there guaranteed to exist two distinct strings such that a leftmost parse of both strings creates the same parse tree? If not, does there exist any CFG that has this property?

I know that given a string and a CFG, there may be multiple leftmost parse trees for the same string (if the grammar is ambiguous), but I am unsure if the converse is true.

I suspect the answer is no and I have not come across a case that seems to suggest otherwise, but I cannot think of a rigorous justification.


texts: Why does memory data isn't organized in two or more lines?

texts:
I understand that computer memory data is sequential;
It is one long line organized in one or more address/es, each of which containing one or more fixed size word/s which contain raw data (in an initial manner, just offset value/s, I would assume).
Why does memory data isn't organized in two or more lines (why it's just one long line, or at least, so it would appear, via a user interface such as some text editor)?


texts: How to estimate piece-wise smooth fit to a noisy mask?

texts:
I have a binary mask that originated from a piece-wise smooth curve. Each underlying curve segment is smooth, but connections between segments may or may not be smooth.
The mask is noisy so it might contain several pixels around the underlying curve. Image below shows an example of such input:

I want to estimate a fit to the underlying curve, given this input without any other prior knowledge, that will be able to provide both smooth and non-smooth connections.

I tried several methods polynomial fit, spline smoothing and non-parameteric regression, but was not able to get to the desired output.
See below examples to the results I get - these fits both fail to capture the non-smooth connection on the left, as well as to provide a good fit for the "tail" on the right:

Expected results should behave like the red curve in the image below, where I expect the curve at location 1 to be non-smooth and at location 2 to be smooth.

I'd be happy to get a reference to a suitable algorithm.

P.S.
I posted this on stackoverflow and was advised to post it here, so sorry for the duplicate from there.


texts: Minimum number of steps for a Universal Turing Machine

texts:
Given a Turing Machine M with n states, alphabet A, m variables, a set S indicating the possible values that each variable can take, and an input x, is there a minimum number of steps that M has to take? I'm wondering if it is possible to construct a Turing Machine that takes only one step regardless of any of the aforementioned properties. Or is the number of steps it has to take dependent on one of these properties?

Thank you


texts: Is the P vs NP problem, an NP or co-NP problem?

texts:
A few years ago, a youtube channel named hackerdashery, made an extraordinary youtube video explaining P vs NP, in a semi-vulgarized way  :
https://www.youtube.com/watch?v=YX40hbAHx3s

At 7 minutes and 56 seconds however, he talks about why it is so hard to prove that P $=$ NP or that P $\neq$ NP, and states that proving things is in fact an NP problem (in the video however, he writes down that it is actually a co-NP problem).

Thus, is proving things, in particular P $=$ NP or P $\neq$ NP, an NP or co-NP problem? If so, why? And where could I find more on this?


texts: Why did Google not use an NP problem for their quantum supremacy experiment?

texts:
Reading discussions of the recent quantum supremacy experiment by Google I noticed that a lot of time and effort (in the experiment itself, but also in the excellent blog posts by Scott Aaronson and others explaining the results) is spent on verifying that the quantum computer did indeed compute the thing we believe it to have computed.

From a naive point of view this is completely understandable: the essence of any quantum supremacy experiment is that you have the quantum computer perform a task that is hard for a classical computer to achieve, so surely it would also be hard for the classical computer to verify that the quantum computer did complete the task we gave it, right?

Well, no. About the first thing you learn when starting to read blogs or talk to people about computational complexity is that, counter-intuitive as it may seem, there exist problems that are hard to solve, but for which it is easy to verify the validity of a given solution: the so called NP problems.

Thus it seems that Google could have saved themselves and others a lot of time by using one of these problems for their quantum supremacy experiment rather than the one they did. So my question is why didn't they?

An answer for the special case of the NP problem factoring is given in this very nice answer to a different question: https://cs.stackexchange.com/a/116360/26301. Paraphrasing: the regime where the quantum algorithm starts to out perform the best known classical algorithm starts at a point that requires more than the 53 qubits currently available.

So my follow-up question is: does this answer for the special case extend to all NP-problems where quantum speedups are expected or is it specific to factoring? And in the first case: is there a fundamental reason related to the nature of NP that quantum-supremacy 'kicks in later' for NP problems than for sampling problems or is it just that for NP problems better classical algorithms are available due to their being more famous?


texts: Analyze time series data to get min max over past period of time

texts:
The algorithm should analyze measured time series data in realtime and should check if all values of the specified last period lay inside a specified range. The range is calculated with max-min over the specified time period.

Input data

t        | 10:00 | 10:01 | 10:02 | 10:03 | ... | 19:00 |
Temp [°C]| 40    | 41.3  | 39    | 43    |     | 45    |

Algorithm parameters

Duration D: Past time to check for min/max
Max range R: (max-min) < R

e.g: Check if the temperature was steady within 2 °C for the last hour. D=1hour, R=2°C

The algorithm should check periodically during data acquisition if the condition (all values of the last hour have been inside a range of 2°C) is true.

Other requirements

The sampling time can be from 10Hz to 50kHz.
The time will always be increasing.
Since this algorithm should run in an realtime environment there should be no memory allocations during run time

Possible solutions

At the moment I have two possible solutions but do not like both of them:

Store all values within the duration in a bounded fifo-buffer and perform a min/max check from start to end periodically. I expect this to be the worst solution
Store the tuples in two B-Trees:

There are two indexes

TimeIndex t->(t,v): Index from time to tuple,
ValueIndex v->list(t,v): Index from the value to a list of tuples with this value.

The algorithm will first get all tuples that are outside the time range and remove them in the value index.

Then the value index is updated with the newly measured tuples.

The range can then be determined by looking up the minimum and maximum key in the value index.

I think the second approach is faster but will allocate memory during runtime. Since it should run in a realtime environment I like to avoid allocations.

Is there another possibility with O(log n) and no allocations?


texts: Can big-step semantics express evaluation order?

texts:
Can you express evaluation order using big-step semantics?

For example, in a simple language consisting of only if t then t else t and true and false, we can decide to only step a if then else to one of its branches if its branches are already values.

Can big-step semantics express the same thing?


texts: How to write a regular expression to match a string that starts with the same pattern that it ends with

texts:
Let's say we want to write a regular expression that matches a string that ends with the same pattern that it begins with.

Let's say that we have an alphabet composed of the binary symbols: {0,1}

We should make a regular expression to create a language that is composed of words (W) with the following pattern:

W=w1w2w1 and w1 and w2 are words from the closure of the {0,1} alphabet.

I do not know how to approach this task. I am not convinced it is even possible because there is no way we can memorize anything inside a regex.

The only operators that we should use are the following three:
-Concatenation
-Star (closure)
-OR


texts: Showing that an equivalence relation on programs need not be a congruence

texts:
An optional exercise from Programming Language Foundations asks

  Can you think of a relation on commands that is an equivalence but not
  a congruence?

An equivalence here refers to an ordinary equivalence relation. A congruence refers to an equivalence relation where the equivalence of two subprograms implies the equivalence of the larger programs in which they are embedded, e.g., if $a_1$ and $a_1'$ are equivalent expressions, then so are $(x ::= a_1)$ and $(x ::= a_1')$.

I am unable to think of an example, although I would think one exists. The context of this exercise has to do with an imperative programming language, but an example in another context is welcomed as well.

Any ideas?


texts: Compressing the output of a discrete memoryless channel

texts:
Let $x\in \mathcal{X}$ be a symbol from an input alphabet, let $p(y|x)$ be a conditional probability distribution corresponding to a discrete memoryless channel and let $y\in\mathcal{Y}$ be an output alphabet. Given that the channel has capacity $C$, is it true that one can compress any $n-$bit output to $nC$ bits with error in the compression vanishing as $n\rightarrow\infty$?
The motivation for this comes from the reverse Shannon theorem established in Section IV of https://arxiv.org/pdf/quant-ph/0106052.pdf. To simulate a channel, Alice applies the channel locally and then transfers the output to Bob. She does this in a clever way such that only $2^{nC}$ bits of communication is actually required.
I was wondering if her protocol is equivalent to compressing the channel output and sending it over to Bob.


texts: Are chaotic systems computable in polynomial time

texts:
Suppose the parameters/inputs of the computation include the time at which the configuration of a particular deterministic chaotic system needs to be computed.

Say, for instance, as input we have a start configuration of the chaotic Rule 30 cellular automata and a time-step $t$, and as output, we require the configuration at time-step $t$.

What can be said about the computational complexity of such a computation?


texts: What is the algorithm for Shannon-Fano code? am I correct?

texts:
I am wondering what is the true algorithm for the Shannon-Fano code? The the result I am getting based on the Algorithm in Wikipedia page contradicts the supposed/expected length of the produced code. According to the proof of Kraft's inequality,  $l_i = \lceil \log_2{\frac{1}{P_i}} \rceil= \lceil -\log_2{P_i} \rceil$.

  A Shannon–Fano tree is built according to a specification designed to
  define an effective code table. The actual algorithm is simple:

  For a given list of symbols, develop a corresponding list of
  probabilities or frequency counts so that each symbol’s relative
  frequency of occurrence is known.
  Sort the lists of symbols according to frequency, with the most
      frequently occurring symbols at the left and the least common at the
      right.
  Divide the list into two parts, with the total frequency counts of
      the left part being as close to the total of the right as possible.
  The left part of the list is assigned the binary digit 0, and the
      right part is assigned the digit 1. This means that the codes for
      the symbols in the first part will all start with 0, and the codes
      in the second part will all start with
  Recursively apply the steps 3 and 4 to each of the two halves,
      subdividing groups and adding bits to the codes until each symbol
      has become a corresponding code leaf on the tree.

For example:

$S_1 \rightarrow P_{S_1} = \frac{4}{9} \rightarrow Code = 0 \mapsto$ And: $\lceil \log_2{\frac{9}{4}}\rceil = 2 \neq 1$ Bad!

$S_2 \rightarrow P_{S_2} = \frac{2}{9} \rightarrow Code = 10 \mapsto$ And: $\lceil \log_2{\frac{9}{2}}\rceil = 3 \neq 2$ Bad!

$S_3 \rightarrow P_{S_3} = \frac{2}{9} \rightarrow Code = 110 \mapsto$ But: $\lceil \log_2{\frac{9}{2}}\rceil = 3 = 3$

$S_4 \rightarrow P_{S_4} = \frac{1}{9} \rightarrow Code = 111 \mapsto$ And: $\lceil \log_2{\frac{9}{1}}\rceil = 4 \neq 3$ Bad!

We can see that the length of produced Shannon-Fano code is $1$, but it supposed to be $2$. Which mean this algorithm is not correct. What is correct algorithm then?

Additional note: If we look at the example 1 of this document, we can see that the length of $A4$ is supposed to be $3$ not $4$. The same contradiction. Another contradiction in example 1 of this other document. I think it is clear what I am talking about.

More additional note:
Here is the page 45 of this textbook -Information and Coding Theory (Springer Undergraduate Mathematics Series) 2000th Edition


texts: Take k numbers from the array and xor them with x to get maximum sum

texts:
Given an array A of n numbers and integers k and x. We can perform the following operation any number of times (including zero times). Take exactly k numbers from the array and replace each of them after doing xor with x . For example, we took ith element among k elements, we will replace Ai with Ai ⊕ x . We wish to maximize the sum of elements in the array.

  https://www.codechef.com/problems/LENTMO

I've seen the editorial, I am hoping a simpler explanation here.


texts: Is Max-2SAT with exactly 3 occurrences per variable APX-hard?

texts:
The Max-2SAT problem asks if at least k clauses of a 2CNF formula can be satisfied.

The Max-2SAT(at-most-3) problem is the restriction in which every variable occurs in
at most 3 clauses (counting positive and negative occurrences together).  It is known that this problem is APX-hard, the reference being
this book.  However, I can't access the book, so I can't look at the details.

The Max-2SAT(exactly-3) problem is the restriction in which every variable occurs in
exactly 3 clauses, i.e. no variable occurs only twice.
From this paper, I believe the problem is NP-hard.  But I don't know if it's also APX-hard.
Is it?  Does it follows from the "at-most-3" case?
If not, I'd like to know how many of the n variables occur only twice, and not three times.


texts: Randomized algorithm to compute cover radius?

texts:
I am self-study the book "Geometric Approximation Algorithms" by Sariel Har-Peled. And I stuck on a problem and don't know how to start it.

Let $C$ and $P$ be two sets of point in the plane , such that k = $|C|$ and $n = |P|$. let $r = max_{p\in P}min_{ c \in C } \|c-p\|$ be the cover radius of $P$ by $C$ give a $\mathcal{O}(n+k\log n)$ expected time algorithm that output  a number $\alpha$ such that  $r \leq \alpha \leq 10r$

Any hint for that？


texts: Keeping a binary search tree by splitting nodes (like a B-Tree)

texts:
A B-tree is kept balanced (i.e. all leaves at same depth) by splitting a node when adding a child that won't fit, and propagating this splitting up to the root.

Can the same technique be used to keep a regular binary search tree balanced (since a binary search tree can be viewed as a 2 child maximum B-tree)? If so, does that rebalancing method have a name, and what are its advantages/disadvantages to other ways of keeping a BST balanced, such as Red-Black trees?


texts: Formal definition of an empty stack accepting PDA

texts:
PDA's are usually defined using the 7-tuple convention.

$M=(Q, \Sigma, \Gamma, \delta, q_{0}, Z, F)$

F is the set of accepting states.

I want to design a PDA accepting by empty stack, so using this notation makes no sense, as I don't need F and I want to make the acceptance condition clear.

How is this usually done? Can I just dismiss F?

$M'=(Q, \Sigma, \Gamma, \delta, q_{0}, Z)$


texts: Is the number of inequivalent elementary cellular automata rules really 88?

texts:
Everywhere from Wolfram's "New Kind of Science" (p. 57) to Wikipedia they say that, out of all possible 256 (=2^8) elementary cellular automata rules, 88 are inequivalent (as defined in the Wikipedia article).

Now, the problem is that I am failing to reproduce the 88 number. No matter how I try - I always get 72.

And it gets worse. Sequence A005418 seems to be defined exactly as Wolfram's inequivalence (see the comment: "Number of bit strings of length (n-1), not counting strings which are the end-for-end reversal or the 0-for-1 reversal of each other as different."). And in that sequence at position 8 they also have 72, not 88.

Off course, there is a chance that my program is wrong and/or I do not fully understand the definition of rule equivalence. Therefore I would like to ask someone to reproduce the computations, and either confirm Wolfram's original number 88, or give me the correct number of inequivalent rules (be it 72, or something else).

This problem is important for a research paper I am working on. And it's not very difficult to implement.


texts: Getting maximum consumption in a given interval

texts:
I propose to solve a scenario that is pretty familiar. I hope you can help me.

I have a set of home appliances and their power consumption (in watts).

TV: 250 W
Oven: 2400 W
Washing machine: 500 W

I need a way (an algorithm) to find the maximum power consumption in a given interval.

Given, for example that:

I watch TV from 2 to 4 and from 9 to 11
I put the oven from 2:30 to 3
I put the washing machine from 2 to 4

A set of sample results would be:

from 12 to 2: 250 W (since only the TV is on in the given interval)
from 2 to 5: 3150 W (there is a moment when the 3 appliances are ON)
from 2:30 to 3: 2650 W (oven + TV)

I hope the example is easy to get. Thanks in advance!