Overflow of integer counter in distributed systems I've just been introduced to Paxos.
There is notion of the of value that is incremented each time a new proposal is send. To provide order for proposals, something like time. What happens when this long or integer value overflows and starts from zero again. The proposed sequence number will become lower than the old one and every proposal will be rejected.

Thank you.

In general:

  Paxos algorithm uses unbounded integers to tag data. In practice,
  however, every integer handled by the processors is bounded by some
  constant $2^b$ where $b$ is the integer memory size. Yet, if every integer
  variable is initialized to a very low value, the time needed for
  any such variable to reach the maximum value $2^b$ is actually way
  larger than any reasonable system’s timescale. For instance,
  counting from $0$ to $2^{64}$ by incrementing every nanosecond takes roughly
  500 years to complete. Such a long sequence is said to be practically
  infinite.

Self-stabilizing systems:

  One particular aspect of self-stabilizing systems is the need to
  re-examine the assumption concerning the use of (practically)
  unbounded time-stamps. While in practice it is reasonable for Paxos to
  assume that a bounded value, represented by 64 bits, is a natural
  (unbounded) number, for all practical considerations, in the scope of
  self-stabilization the 64 bits value may be corrupted by a transient
  fault to its maximal value at once, and still recovery following such
  a transient fault must be guaranteed.

Source: Self-Stabilizing Paxos


How many cookies in the cookie box? -- Tiling stars With holiday season coming up I decided to make some cinnamon stars. That was fun (and the result tasty), but my inner nerd cringed when I put the first tray of stars in the box and they would not fit in one layer:

Almost! Is there a way they could have fit? How well can we tile stars, anyway? Given that these are regular six-pointed stars, we could certainly use the well-known hexagon tilings as an approximation, like so:

Messed up the one to the upper right, whoops.

But is this optimal? There's plenty of room between the tips.

For this consideration, let us restrict ourselves to rectangular boxes and six-pointed, regular stars, i.e. there are thirty degrees (or $\frac{\pi}{6}$) between every tips and its neighbour nooks. The stars are characterised by the inner radius $r_i$ and outer radius $r_o$:

[source]

Note that we have hexagons for $r_i = \frac{\sqrt{3}}{2} \cdot r_o$ and hexagrams for $r_i = \frac{1}{\sqrt{3}} \cdot r_o$. I think it's reasonable to consider these the extremes (for cookies) and restrict ourselves to the range in between, i.e. $\frac{r_i}{r_0} \in \Bigl[\frac{1}{\sqrt{3}}, \frac{\sqrt{3}}{2}\Bigr]$.

My cookies have $r_i \approx 17\mathrm{mm}$ and $r_o \approx 25\mathrm{mm}$ ignoring imperfections -- I was going for taste, not form for once!

What is an optimal tiling for stars as characterised above? If there is no static best tiling, is there an algorithm to find a good one efficiently?

Let me answer your question partially for the hexagram case.

You can make the following tiling

$\hskip1.2in$

By this you will cover 12/14=6/7 of the plane (count the triangles in the dashed quadrilateral).

Is this optimal? I would think so. Although I am not giving a proof I will provide some arguments. One can ask, how good we can fill the space (triangle) in between the pointy spikes. In the above tiling we fill half of it. Can we do better?

$\hskip20mm$

It is possible that two hexagram will intersect this space, but then they cover very little of its area (without proof). If there is only one hexagram intersecting I assume that its tip touches the concave corner of the other hexagram as depicted in the picture. If this would not be the case we can improve by moving the intersecting hexagram to this corner (again no proof here). Under these assumptions it is not hard to see that the case where there is side-to-side contact maximizes the intersection. If you do the math, then you will find out that the area of the intersection equals
$$\frac{\sec ^2(x)}{2 \sqrt{3} \tan (x)+2}.$$

The plot of this function looks like this and shows that our intuition was right.

$\hskip30mm$


Mergesort recurssion tree depth...logs I think some of the log properties are flying over my head but I'm trying to understand how the depth of mergesort is...

$1 + \log_2 n$

I understand that to get the depth, you would have to divide $n$ by $2^x$ but I don't how this leads to the above.

It's probably some simple log principal but I'm not sure.

The merge sort algorithm creates a complete binary tree, which has depth 'd' and at each level, a total of n elements.
So, 2d ≈ n, which implies d ≈ log2 n


If O(log n) vs O(n) is exponential what is O(1) vs O(n)? If one refers to using an O(log n) instead of an O(n) algorithm as an exponential speedup,
how would one refer the speedup gained by using an O(1) algorithm vs an O(n)?

There's no name for that, but the closest would be "infinite" speedup. $O(\log n)$ is considered an exponential speedup over $O(n)$, because $n$ is exponential in $\log n$: if we take the exponential function $f(n)=2^n$, we get $f(\log n)=2^{\log n}=n$.

However, $n$ isn't anything in $1$: there's no way to recover $n$ from $1$, no matter how quickly the function $f$ that we take grows, $f(1)$ will always be a constant (and never equal $n$). As $n\to \infty$, $1$ becomes infinitely smaller than $n$.


Standard Parameters for Genetic Algorithms I'm currently writing my thesis, which uses genetic algorithms at some point.
Now I need to define some parameters for the genetic algorithm

I know that, because of the No Free Lunch Theorem there is no optimal parameter configuration for all problems.

However I do need some default parameters, because finding the optimal parameters is out of scope of my paper.
Also I don't want to use random values as these parameters.

I would prefer to reuse parameters used in some well trusted sources in the field of genetic algorithms.
Then I could rely on these cited sources and reuse these parameters.

I need default values for these parameters:

population size
mutation rate
number of generations

I searched for papers, but am not sure which paper is well-known.
I'm looking for papers that are well-known and have these parameters used.
A online available pdf is preferable.

As you say, there are no universal parameter settings, which means that you won't find a source that cites any such settings. Instead, you find some papers who tune the parameters to their particular problem, and you find many, many others that simply take a "standard" set of parameter settings without much attempt to justify them. In that case, it's not like there's a single authoritative source you can cite -- it's more like bunches of people sort of converge on parameters that seem common to everyone. The best you can really do is to say something like "the parameter values were chosen as being commonly observed in the literature."

Also, it depends not just on the problem, but on the particular structure of your GA. CHC (Eshelman, 1991), for example, is usually used with a population size of 50 (very small by typical standards) and has no conventional mutation operator, but it adds other pieces that make up for it. Genetic programming practitioners often use population sizes in the thousands and use very high mutation rates.

For a "standard GA", if you were to use a population size of 100-200, a mutation rate of 1/L (with L=the length of your encoding, assuming it's discrete), and "enough" generations (more on that in a second), no one would question things too much. However, aside from just citing a random selection of papers, there's not a lot you can point to as justification. Also, some light parameter tuning is almost certainly a better idea if you can afford it at all.

For generation count, the basic rule is to go until you either exhaust the amount of time you have to allot to it or until the algorithm converges, whichever comes first. Of course, these are interdependent. Raising the population size and/or raising the mutation rate will slow convergence, so you still need to tune parameters for the best results.

If you're doing this for research purposes at least, you should also measure the runtime in fitness function evaluations rather than generations. The reason is that if my algorithm finds a solution in N generations, you can almost certainly find a better solution in N generations if you just multiply the population size by 100 or so. You'll get to do about two orders of magnitude more searching than I could do, so the comparison is unfair. Reporting generations used is an automatic red flag in a paper unless the other GA parameters are controlled to a degree that we can be sure that the comparison is apples to apples. Measuring evaluations is much more tightly correlated to wall-clock time than measuring generations, and should essentially always be preferred.


Given a sufficiently powerful computer and model, can dice rolls be predicted? I guess that this is a chaos, randomness and modelling question.  Can it be conceived that a sufficiently powerful (perhaps quantum) computer might be able to accurately predict the scores on a physical die tossed from a cup?

I understand that dice land the way they do because of highly complex and chaotic interactions between the die and whatever it hits.  There is a concept of total physical modelling (that I don't know the technical term for) that aims to model a real item on an atomic level. This would require great computational power and storage.

Is such modelling possible, or are there fundamental (perhaps quantum) nuances that will always prevent this? They say the weather is chaotic and unpredictable, yet the Met Office now says that today's three day forecasts are as accurate as yesteryear's daily forecasts. Advances seem to be possible...

I believe it could be predicted assuming technological limits of sensors and computation were overcome. A die is too large for quantum effects and a simple enough system.

Related paper


Is computational power of Neural networks related to the activation function It is proven that neural networks with rational weights has the computational power of the Universal Turing Machine Turing computability with Neural Nets. From what I get, it seems that using real-valued weights yields even more computational power, though I'm not certain of this one.

However, is there any correlation between the computational power of a neural net and its activation function? For example, if the activation function compares the input against a limit of a Specker sequence (something you can't do with a regular Turing machine, right?), does this make the neural net computationally "stronger"? Could someone point me to a reference in this direction?

Just a note:

rational-weighted recurrent $NN$s having boolean activation functions (simple thresholds) are equivalent to finite state automata (Minsky, "Computation: finite and infinite machines",  1967);
rational-weighted recurrent $NN$s having linear sigmoid activation functions  are equivalent to Turing Machines (Siegelmann and Sontag, "On the computational power of neural nets", 1995);
real-weighted recurrent $NN$s having linear sigmoid activation functions are more powerful than Turing Machines (Siegelmann and Sontag, "Analog computation via neural networks", 1993);

but ...

real-weighted recurrent $NN$s with Gaussian noise on the outputs cannot recognize arbitrary regular languages (Maass and Sontag, "Analog Neural Nets with Gaussian or Other Common NoiseDistributions Cannot Recognize Arbitrary Regular Languages" , 1995);


Proving that L(G) is the language defined by the CFG G I have a context-free grammar defined by the production S:

S → aSbS ∣ bSaS ∣ ε

I need to prove that the CFG "G" can be defined as a language L(G) where

L(G) = {w ∈ {a, b}∗ ∶ na(w) = nb(w)}.

Where na(w) = number of a's in w, and nb(w) is the number of b's in w

How can I go about proving something like this? Is there a method?

Without giving the answer away.

Let us denote $L'$ the language defined by the CFG $S$.

To prove $L'$ = $L$ you must do two things:

prove $w' \in L' \Rrightarrow w'\in L(G)$, meaning $L' \subseteq L(G)$
prove $w \in L(G)\Rrightarrow w\in L'$, meaning $L(G) \subseteq L'$

Combine proofs 1 and 2, and you get that $L' = L(G)$.

The proofs themselves are not hard, since $L'$ has a very specific structure.


Bit complexity of O(1) time range query in a $k$-ary array Consider the following problem:

Let $k$ be a constant. We are given a $k$-ary array $A_{d_1\times\ldots\times d_k}$ of $0$ and $1$'s. Let $N = \prod_{i=1}^k d_i$.

We want to create a data structure by preprocessing $A$ to perform the following type of query operations:

Given the coordinates of a $k$-ary box $D$, is there a $1$ in the box?
Given the coordinates of a $k$-ary box $D$, return the position of a $1$ in the box (if there is one).

The operations must be performed in constant time $O(1)$. The time complexity is measured on a RAM machine. The preprocessing time and space for the data structure are not important for us.

The question is how much space (in bit complexity) do we need to store a datastructure allowing the above operations?

The trivial lower-bound is $N$ bits since the array can be reconstructed for these queries (so the data structure should have at least the same amount of information in it).

The trivial upper-bound is to store the answer to all of the queries. That would need $\prod_{i=1}^k {d_i \choose 2} = \Theta(N^2)$ bits. However we suspect that this can be done much more efficiently.

For example, consider the special case where $k=1$. In this case we can use a succinct RMQ data structure to solve the first problem, and the data structure takes $2N+o(N)$ bits to store.

  What is an efficient data-structure for this task?
  How low can the space complexity (the number of bits) go to support these operations (or just the first operation)?

Update (1/15):
In the special case $k=1$, using $N +o(N)$ bits is sufficient (actually better, $\log {N\choose t}+O(t)$, where $t$ is the number of $1$'s in $A$) by reducing the problem to a predecessor problem and using the reduction from predecessor problem to fully indexable dictionary (FID). See "More Haste, Less Waste: Lowering the Redundancy in Fully Indexable Dictionaries" by Grossi, Orlandi, Raman and Rao (2009).

Update (6/27):
Again by reduce the problem to RMQ. We use a $k$-dimensional RMQ by Yuan and Atallah to get a $O(n\log n)$ upper bound on the amount of space required when $k$ is fixed.

You can save a lot more on memory if you just allow logarithmic time complexity. You can implement a kD segment tree that will need N * 2^k bits memory, and runs in logarithmic time complexity for both subtasks, and linear time complexity for building the tree.

If you strictly want O(1), precompute everything.


Converting a Recurrence Relation to its Closed Form I have a recurrence relation of the form given below (taken from Analysis of Algorithms - An Active Learning Approach by Jeffrey J. McConnell):

$T(n) = 2T(n - 2) - 15 $

$T(2) = T(1) = 40 $

I am asked to find a closed-form for the recurrence relation i.e. to remove the recursive nature of the equations.

Working:
My professor said it would be easier if you could see the patterns taking form if you expand the equations up to a few steps. So,

$T(n) = 2T(n - 2) - 15 $

$= 2(2T(n - 4) - 15) - 15$

$= 4T(n - 4) - 2\times 15 - 15 $

$ = 4(2T(n - 6) - 15) - 2\times15 - 15$

$ = 8T(n - 6) - 4 \times 15 - 2\times15 - 15$

I observe that the coefficient of $T$ in each step is a power of 2. The size of the problem during each recursive call decreases by 2. Also, there is a -15 term multiplied by the next power of 2.

But I am stuck here and do not know how to proceed further i.e. to obtain a closed-form. The book says to consider cases when $n$ is odd and even. But I do not get it at all. Any help would be appreciated.

Note: The material hasn't covered advanced topics like solving recurrence relations yet.

It might be helpful if N is assigned a range of values from 1 to say 7 and evaluated till the recursion end is reached.
also summing together terms with 15 multiples separately and 40 multiple separately, because they are the building blocks from the base case and recursion.

T(1) = 40.

T(2) = 40.

....

T(6) = 2 * ( 2 * 40 - 15 ) - 15
           = 4 * 40 - 3 * 15

T(7) = 2 * ( 2 * ( 2 * 40 -  15 ) -15 ) - 15
           = 8 * 40 - 7 * 15

i think this can help to find the closed form. But i am not an expert in this area.


Showing that an equivalence relation on programs need not be a congruence 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?

Let $x,y$ be two fixed distinct variable names.

Call $P$ and $Q$ equivalent iff $Q$ is obtained from $P$ by optionally swapping the variable names $x$ and $y$. That is, either $Q=P$ or $Q=P\{x/y,y/x\}$ where the latter uses simultaneous substitution.

It is an equivalence. Reflexivity follows by construction. For symmetry, $P\equiv Q$ swaps if $Q\equiv P$ swaps. For transitivity, we consider the four cases: in the swap-swap case we get the same program back.

It is not a congruence since

$$
x:=x+1 \equiv y:=y+1 \quad \mbox{ but }\quad (x:=0;x:=x+1) \not\equiv (x:=0;y:=y+1)
$$

Less formally, you can build many examples as follows. Take $f : \mathbb N \to \mathbb N$ to be a function which does NOT in general satisfy

$$
f(n)=f(m) \implies f(n+1)=f(m+1)
$$

Say, $f$ is a hash function.

Then, we can say $P\equiv Q$ whenever $f(\# vars(P))=f(\# vars(Q))$, where $\#vars$ counts the number of variables.

This is an equivalence (trivially), but not a congruence since if we add another fresh variable to both $P,Q$ we increment their variable count by one, but $f$ does not preserve that value in general.


CNF Generator for Factoring Problems I've been reading these:

Fast Reduction from RSA to SAT
CNF Generator for Factoring Problems (Also have C code implementation)

I don't understand how the reduction from FACT to $3\text{-SAT}$ works. Are there any simple articles in which I can read about it?

My final goal is to eventually implement a reduction from $3\text{-SAT}$ to the undirected Hamiltonian circuit problem.

I don't understand how the reduction from FACT to 3-SAT works. Are there any simple articles in which I can read about it?

Most of the reading material assumes several steps of knowledge.

First, you should read about how logic circuits (logic gates) work.
Optionally learn or use a simple multiplication algorithm. You might want to start with the long-multiplication algorithm that everyone learns in school.
Then research and understand a multiplication circuit, and/or learn how to convert the chosen algorithm to a circuit.
You should now know how to make a simple multiplication circuit (MULT). Next learn to extend it for $n$-bit numbers.
Once you have a circuit, you can force the outputs of the circuit to the $N$ value you want to factor. You do this by taking the $n$ outputs, and point-wise xoring them together with your $N$ value. Set the final output to be true iff $N$ and the MULT output cancel each-other out. You can do this by first oring all the xor results; if they are all $0$, then the output matched $N$ (in this case, set the final output to be $1$, else $0$).
Now you have $\text{Circuit-SAT}$. Learn about $\text{Circuit-SAT}$.
$\text{Circuit-SAT}$ asks if there is an input that can satisfy the output. $\text{Circuit-SAT}$ is an NP-complete problem, that is almost directly convertible to $3\text{-SAT}$ (when you get to this step, you will understand this pretty easily)
There is a straightforward reduction from $\text{Circuit-SAT}$ to $3\text{-SAT}$ available here: Convert Circuit SAT to 3-SAT

You can't get it all in one scoop without talking to someone in-person. Rather you should follow the steps, without skipping. Each of these has "simple" material to learn from; but you'll not find one that teaches you everything in one sitting from the very basics.

Also see Computer Organization - Module II, section 2.5.1 Array Multiplier, which implements a carry-save-array-multiplication circuit:

Looks a lot like grade-school multiplication, doesn't it ...

Each box is (FA means "Full adder", which is also on that page in section 2.2 Serial & Parallel Adder):


Voronoi diagram with given number of vertices and sites I want to draw a Voronoi diagram with 9 sites and with

no vertex,
1 vertex,
4 vertices, and
7 vertices.

How do I approach this question. The one with no vertex is easy, it can be done by collinear points. What about the others.

A figure for each would be appreciated.

Conceptually, it is maybe easier to construct a Delaunay triangulation tessalation. The DT is the dual to the Voronoi diagramm, so you want to limit the number of faces to $0,1,4,7$. This can be achieved by placing some of the vertices of the DT on a circle, or by picking the right number of vertices on the convex hull.

Here is a picture for the 4 vertex case (black DT, red Voronoi diagramm). Play around to get the solutions of 2. and 4. (You already solved 1.)


Local type argument synthesis when type variable does not appear in arguments I am implementing the techniques described in the classic Local Type Inference paper. Specifically, I am implementing the type argument synthesis algorithm from section 3.

My algorithm seems to mostly work, but it doesn’t seem to produce reasonable results when a quantified type variable appears in the result of a function, but not in its arguments. For context, I’ve reproduced the $\text{App-InfAlg}$ rule here:

$$
\dfrac{\begin{align}\tt\Gamma \vdash f \in All(\overline{X}) \overline{T} \rightarrow R \qquad &\tt \Gamma \vdash \overline{e} \in \overline{S} \qquad \lvert\overline{X}\rvert > 0\\
\tt\emptyset \vdash_\overline{X}\overline{S} <: \overline{T} \Rightarrow \overline{C}&\qquad\tt \sigma \in \bigwedge \overline{C} \Downarrow R
\end{align}}
{\tt\Gamma \vdash f(\overline{e}) \in \sigma R \Rightarrow f[\sigma \overline{X}](\overline{e})}
(\text{App-InfAlg})
$$

The most important piece here is the $\tt\emptyset \vdash_\overline{X}\overline{S} <: \overline{T} \Rightarrow \overline{C}$ premise, which invokes the constraint generation algorithm. Importantly, though, it only generates constraints using $\tt\overline{S}$ and $\tt\overline{T}$, which correspond to the argument types (that is, the types to the left of the arrow). This is problematic for types like this, which include type variables that only appear in the result:

$$
\tt All(X, Y)(X) \rightarrow Y
$$

Or, even more simply:

$$
\tt All(X)() \rightarrow X
$$

In this case, my implementation happily infers the type of the above two functions to be $\tt Y$ and $\tt X$, respectively, which are clearly not valid types, since they are type variables that have escaped their scope!

My guess is that my implementation is wrong, and the algorithm accounts for this case. In that situation, I would expect the algorithm to either reject the applications or infer $\tt Bot$ as the result type. However, I don’t see how this could possibly be accounted for, since the algorithmic inference rule only uses $\tt R$ for the purposes of turning the constraints $\overline{C}$ into the substitution set $\sigma$.

How does the algorithm handle this situation?

As a prelude, there is some terminological confusion in your question.  The issue is about a type variable occurring in a result type of a function.  This is fairly minor.  A more serious one is when you say "my implementation happily infers the types of the above two functions to be ...".  What functions?  Functions are terms like (in this case) $\tt fun(x:T)e$ but the rule you quote is actually about function application, i.e. it applies to terms like $\tt f(e)$.  Either way, the two things you present are types not terms.  What you seem to want to say is: given a function $\mathtt{f}\in\tt All(X)()\to X$, the expression $\tt f()$ seems to have the inferred type $\tt X$.

$\tt \sigma \in \bigwedge \overline{C} \Downarrow R$ implies that $\sigma$ is a map for all the variables in $\tt R$ or else it wouldn't even make sense.  Maybe it doesn't make sense, but we see that in the rule you listed the constraint generation step produces a $\mathtt{\bar X}/V$ constraint and the substitution algorithm will thus produce a $\mathtt{\bar X}/V$ substitution which, by definition, has a mapping for each type variable in $\tt \bar X$.  I assume your confusion is that you look at the minimal substitution generating algorithm $\sigma_{C\tt R}$ at the bottom of page 11, note that in your second case, for example, the constraint generation step produces an empty set of constraints and thus the "for each constraint" iterates over an empty set producing a substitution with no mappings which presumably would act as the identity.  However, this would violate the definition of an $\mathtt{\bar X}/V$ substitution.  The detail here is the definition of the empty constraint set.  At the beginning of section 3.3 on page 9 it states:

  The empty $\mathtt{\bar X}/V$ constraint set, written $\emptyset$,
  contains the trivial constraint $\tt Bot <: X_\mathit{i} <: Top$ for
  each variable $\mathtt{X}_i$.

Since the result type is covariant (in a top-level context), we'll get $\tt Bot$ in those cases.  In particular, given that $\mathtt{f}\in\tt All(X)()\to X$, the expression $\tt f()$ will have the inferred type $\tt Bot$.  The produced substitution $\sigma_{\emptyset\tt R}$ will map $\tt X$ to $\tt Bot$.


Expressing an arbitrary permutation as a sequence of (insert, move, delete) operations Suppose I have two strings. Call them $A$ and $B$. Neither string has any repeated characters.

How can I find the shortest sequence of insert, move, and delete operation that turns $A$ into $B$, where:

insert(char, offset) inserts char at the given offset in the string
move(from_offset, to_offset) moves the character currently at offset from_offset to a new position so that it has offset to_offset
delete(offset) deletes the character at offset

Example application: You do a database query and show the results on your website. Later, you rerun the database query and discover that the results have changed. You want to change what is on the page to match what is currently in the database using the minimum number of DOM operations. There are two reasons why you'd want the shortest sequence of operations. First, efficiency. When only a few records change, you want to make sure that you do $\mathcal{O}(1)$ rather than $\mathcal{O}(n)$ DOM operations, since they are expensive. Second, correctness. If an item moved from one position to another, you want to move the associated DOM nodes in a single operation, without destroying and recreating them. Otherwise you will lose focus state, the content of <input> elements, and so forth.

I suggest taking a look at the edit distance algorithm.  Instead of just calculating the distance, you'll want to record your minimum weight path through the array and return that.


Identifying/equating constants in a term rewrite system Suppose we have a term rewrite system $\mathcal{R} = (R, \Sigma)$ with basic rewrite rules $R$ over a signature $\Sigma$. Suppose also that this rewrite system $\mathcal{R}$ is confluent and terminating, and that each constant symbol of $\Sigma$ is a normal form with respect to $\mathcal{R}$.

Now suppose that we want to identify/equate some of the constants of $\Sigma$. For example, if we have two constants $c, d$ in the signature $\Sigma$, then we may want to 'merge' $c$ and $d$ into a single constant $e$ (thereby obtaining a new signature $\Sigma'$ that is the same as $\Sigma$ except that $c$ and $d$ have been replaced by $e$), and then modify the basic rewrite rules in $R$ accordingly (by replacing all occurrences of $c$ and $d$ by $e$).

If we identify/equate some constants of $\Sigma$ in this way, and then modify the rules in $R$ accordingly, so that we obtain a slightly modified term rewrite system $\mathcal{R}' = (R', \Sigma')$, is there any way to prove that $\mathcal{R}'$ will still be confluent and terminating?

Obviously, if $R$ has a rule like $c \to d$ and we merge $c$ and $d$ into the single constant $e$, then this rule will become the rule $e \to e$, and so the resulting system will not be terminating. But this is why I assumed that each constant of $\Sigma$ is a normal form with respect to $\mathcal{R}$ (so that $R$ will not have rules like $c \to d$).

Counterexample:

$f(c) \rightarrow f(d)$

In general, there are some modularity theorems for termination and confluence that may apply if, e.g. your constants do not appear at all in any rule.

There are probably some weaker assumptions that can make this work though.


Strongly connected graph proof Here I have a proof related to strongly connected graph from Algorithms book.

However, when I run DFS on the following 2 strongrly connected graph, I get different result than the proof.

According to property, highest post number in C is bigger than the highest post number in D but it is not. Where am I making mistake?

Your post-traversal numbering of the component $C$ is incorrect. The vertex labeled as $1,6$ was assigned its post-traversal number too early; a depth-first search will also explore the vertices of $D$ before assigning the post-traversal number to this vertex.


Architecture - calculating miss penalty I know that AVG Memory Access Time = Hit time + Miss Rate * Miss Penalty

If I am given the AMAT and miss rate, aswell as the latency to access memory(call this x) how do I calculate the miss penalty & / or Hit Time?

For example:

AMAT = 80 (cycles)
Miss Rate = 0.4
Memory access latency = 60 (cycles)

How do I get miss penalty from this so that I can solve for hit time?

Thanks

Let us assume/understand that "memory access latency" means the "memory access latency" to access the cache when there is a hit. (It appears reasonable to just say "memory access latency" since the latency to access the cache might be (almost) the same whether there is  hit or miss.) Otherwise, there is no solution to this problem or we have to introduce other less straightforward assumptions.

Once we have made that assumption/understanding, the miss penalty is easy to solve.

Miss Penalty = (AMAT - Hit time) / Miss Rate
             = (AMAT - hit-rate * memory-access-latency) / Miss Rate
             = (80 - (1 - 0.4) * 60 ) / 0.4
             = 110

However, it is rather unnatural to interpret "memory access latency" as referring to accessing the cache since by default, "memory" refers to the main memory while the cache memory, L1 memory and L2 memory are referred as cache.

Another plausible situation is the last given condition is, for example, memory access latency = 160 instead of memory access latency = 60. Then we can understand "memory access latency" as, very naturally, the latency to access the main memory when there is a cache miss. I put an emphasis because it is reasonable to assume there is no way to skip the cache (in this kind of exercises). Note that this natural interpretation cannot make much sense originally when the value is 60, which is less than the given "AVG Memory Access Time", 80. I will leave the question as an exercise for you if the last condition is indeed changed to memory access latency when there is miss = 160.

(Yet another way to resolve the situation is to change AVG Memory Access Time = 80 to, for example, AVG Memory Access Time = 30.)

You may check my answer for related information.


In a CSP, what is an extensional constraint? When talking about Constraint Satisfaction Problems (CSP), what does the term extensional constraint mean?

Let $X$ be a finite set of variables, where each variable $x \in X$ has a domain of values. Let $D(x)$ denote the domain of the variable $x$. Let $C$ be a finite set of constraints on the variables.

Each constraint $c \in C$ has a scope, which is a subset of the Cartesian product $D(x_i) \times \cdots \times D(x_j)$. In other words, the scope of the constraints gives the set of legal combinations of values.

An extensional constraint is the relational view of the constraint. It is an explicit listing of the subset of the Cartesian product. You could also have something called an intensional constraint, where the idea is that the values are instead computed by an algorithm.


Sum of k smallest values of affine functions Assume we have a fixed number of $n$ one-dimensional affine functions of the form $f_i(x) = a_i x + b_i$ for $i \in N = \{1,\ldots,n\}$.

Consider some fixed value $k \in \{0,\ldots,n\}$. Let $S_k : \mathbb{R} \mapsto 2^N$ (power set) denote a function mapping some value $x \in \mathbb{R}$ to the set of indices of the $k$ smallest functions at $x$, so for all $x \in \mathbb{R}$, it holds that $|S_k(x)| = k$ and $f_i(x) \leq f_j(x)$ if $i \in S_k(x)$ and $j \notin S_k(x)$.

The question is: If we hold $f_1,\dots,f_n,k$ fixed and allow $x$ to vary, how many different sets can $S_k$ map to? In other words, which cardinality can the image of $S_k$ have?

For $k=0$ or $k=n$, there is only one possible set for all $x$ (either $\emptyset$ or $N$). Similarly, for $k=1$ or $k=n-1$, there are $n$ different sets each (since this is equal to the maximum or minimum element, which can change $n$ times while x increases).

But is there a general formula for arbitrary values of $k$? It seems that the maximum is attained at $k = \frac{n}{2}$.

Note that an upper bound is given by $O(n^2)$ since this is the maximum number of intersection points of the involved functions, which, thus, bounds the number of orderings. However, I think this bound is too rough. In computational experiments I have never seen a value of $2n$ or more.

I recently found out that my problem is known as the k-th level problem, which itself is equivalent to the k-set problem in the dual plane. Since almost 50 years, it is an open problem how many sets there are exactly. At present, the best upper bound is given by $O(n k ^{1/3})$: https://en.wikipedia.org/wiki/K-set_(geometry)


How many possible assignments does  a CNF sentence have? I'm having some trouble understanding the following:

When we look at satisfiability problems in conjunctive normal form, an underconstrained problem is one with relatively few clauses constraining the variables. For eg. here is a randomly generated 3-CNF sentence with five symbols and five clauses. (Each clause contains 3 randomly selected distinct symbols, each of which is negated with 50% probability.)

(¬D ∨ ¬B ∨ C) ∧ (B ∨ ¬A ∨ ¬C) ∧ (¬C ∨ ¬B ∨ E) ∧ (E ∨ ¬D ∨ B) ∧ (B ∨ E ∨ ¬C)

16 of the 32 possible assignments are models of this sentence, so, on an average, it would take just 2 random guesses to find the model.

I don't understand the last line- saying that there are 32 possible assignments. How is it 32? And how are only 16 of them models of the sentence? Thanks.

There are 5 (Boolean) variables in the formula. Each of these could be either true or false. This means that there are $2^5=32$ ways of assigning values to these variables.

Of the 32 possibilities, only 16 of them make the formula true – this would have to be checked by hand (or machine).


Activity Selection and Matroid Theory Many people on different articles suggests that if an optimization problem has a greedy solution, the underlying structure must have matroid property.

I was trying to understand this. So far, I was able to prove that for,

Maximum sum of m integers among n integer.
Minimum spanning tree.

However, The classical greedy algorithm Activity Selection seems to fail having both independence and base exchange property.

Let,
E = {1-3, 2-4, 3-5, 4-6, 5-7}

Now, Take two independent set,
I = {2-4, 4-6} and J = {1-3, 3-5, 5-7}

There is no activity in J which can extend I. Which fails the independence exchange property of matroid, if I understood it correctly. Thus, it is not matroid and shouldn't have a greedy algorithms. But this problem has a greedy solution.

Where am I wrong?

Suppose that $\mathcal{F}$ is a nonempty collection of subsets of a finite set $U$ satisfying the following axiom:

  If $A \in \mathcal{F}$ and $B \subseteq A$ then $B \in \mathcal{F}$.

Consider the following algorithm, which gets as input a weight function $w\colon U \to \mathbb{R}_+$ (here $\mathbb{R}_+$ consists of all positive reals):

Set $S \gets \emptyset$.
While there exists an element $x \notin S$ such that $S \cup \{x\} \in \mathcal{F}$:

Let $x$ be an element of maximum weight among $\{ x : x \notin S \text{ and } S \cup \{x\} \in \mathcal{F} \}$.
Set $S \gets S \cup \{x\}$.

Return $S$.

We say that the algorithm is valid for $w$ if it returns a set $S$ maximizing $\sum_{x \in S} w(x)$ among all $S \in \mathcal{F}$.

  Theorem. The algorithm is valid for all $w\colon U \to \mathbb{R}^+$ iff $\mathcal{F}$ is a matroid.

You can find the proof of this theorem in lecture notes and in textbooks.

The algorithm given above is a specific greedy algorithm. This specific greedy algorithm is optimal if and only if the set system is a matroid. However, the (informal) notion of greedy algorithms encompasses more than just this specific algorithm. The theorem above doesn't apply to these algorithms.

In the two good examples you consider, the corresponding greedy algorithms (or at least one of their variants) are instances of the algorithm above. The same isn't true for the algorithm for your bad example.

For a formalized notion of "greedy-like" algorithms, consult (Incremental) priority algorithms by Borodin, Nielsen, and Rackoff. You can see that is is much more general than the simple algorithm stated above.

Another relevant notion is that of greedoid, for which a theorem similar to the one stated above does hold (see Wikipedia for details).


looking for counterexample for my algorithm for maximum independent set in Bipartite Graph We wish to find the maximum independent set in a bipartite graph. My intuition led me to the following algorithm. (Assume that the bipartite graph is connected and has at least 3 vertices, if not run the algorithm on each component)

Given $G=(L,R,E)$
Let $S$ be the set of vertices with degree $1$. Note that since graph is connected and has at least $3$ vertices, $v,u\in S\implies (v,u)\not \in E$. (If $S$ is empty, go to step $5$)
Add the vertices in $S$ to the independent set. $\forall s\in S$, remove $s$ and neighborhood of $s$ from $G$
If the graph is connected, repeat steps $2-4$. If it is disconnected, repeat the steps $2-4$ for each component.
if $|L| > |R|$, add $L$ to the independent set, else add $R$

Obviously, the output is some independent set, not necessarily the maximum. However, I could neither prove nor come up with an counter example. Any help will be appreciated.
https://cs.stackexchange.com/a/3033 has a answer which does not rely on intuition

Consider the following graph:

None of the vertices has degree 1, so we go straight to step 5. Your algorithm would return 5 as the maximum independent set size, as both $L$ and $R$ have 5 vertices. However, the actual maximum independent set is $\{1, 2, 3, 6, 7, 8\}$, which has 6 vertices.


Describe construction of finite automata that accepts the language Double-Letter(L) Describe construction of finite automata that accepts the language
Double-Letter(L), where Double-Letter(L) is in the language of words
from L, except each letter in the word appears twice. So $abc\in L$
$\iff aabbcc \in $ Double-Letter($L$).
For example if L={a,aa,ab,ba} then Double-Letter(L) = {aa,aaaa,aabb,bbaa}

My idea:
Create states Q that are named s and ss where $s\in \Sigma$. Make states named ss accepting if $ss \in L$
FA illustrated for the example above
What next? is this a good approach? I can't think of the next step on how to construct this doubled DFA for ALL languages.

The idea is to start with an automaton for $L$, and replace each transition labeled $\sigma$ by a path of length 2 both of whose edges are labeled $\sigma$. In order to make it a DFA, we also add a sink state. (This might be unnecessary in your definition of DFA.)

In more detail, suppose we start with a DFA $(Q,q_0,\delta,F)$ for $L$ (here $Q$ is the set of states, $q_0$ is the initial state, $\delta$ is the transition function, and $F$ is the accepting states). We construct a DFA whose set of states is $Q \cup Q \times \Sigma \cup \{q_{\mathit{sink}}\}$, where $\Sigma$ is the alphabet. The initial state is still $q_0$, and the accepting states are still $F$. The transition function $\delta'$ is defined as follows:

$\delta'(q,\sigma) = (q,\sigma)$ (this is a member of $Q \times \Sigma$).
$\delta'((q,\sigma),\sigma) = \delta(q,\sigma)$.
$\delta'((q,\sigma),\tau) = q_{\mathit{sink}}$ if $\tau \neq \sigma$.
$\delta'(q_{\mathit{sink}},\sigma) = q_{\mathit{sink}}$ for all $\sigma \in \Sigma$.

A simpler way of proving that the regular languages are closed under Double-Letter is using regular expressions: given a regular expression for $L$, simply double each letter. This is a special case of closure under homomorphism and regular substitution.


two languages reducible to each other can belong to RE and recursive? If two languages L1 and L2 both are reducible to each other in polynomial time then which of the following is false?

A  L1 is decidable and L2 is undecidable.

B  L1 is recursive and l2 is RE

C  both

D  none of these

I know  that both need  to belong to NP or NP hard if they are reducible to each other.
simply solving one solves other.

If L1 is recursive then L2 also needs to be recursive. in context of P-NP if L1 is decidable and by doing extra polynomial work i can get Turing machine for L2 as well ans vice versa .
why one is  decidable and other is  semi-decidable a true statement?

Reductions are translations between computational problems.  Reductions are used to define the concept of NP-hardness but that doesn't mean that every use of reductions has something to do with NP – analogously, you can translate between English and French but that doesn't mean that every piece of translation has something to do with French.  In this case, there's no reason to assume that we're in the context of P vs NP: the question is in the context of computability theory (what functions can we compute?) not complexity theory (how much resources are required?).

For your question at the end, remember that every decidable language is semi-decidable.

I've no idea what the answer to the multi-choice question is, since it's so badly worded.  Choosing "C", for example, would mean asserting that the statement "both" is false but "both" isn't a statement with a truth value.


How to come up the number of nodes on a given level in heaps? CLRS asked it's readers to prove that there are at most $\lceil n/2^{h+1} \rceil$ nodes of height $h$ in any n-element heap as an exercise. The principle of Mathematical Induction can be used to prove this as explained here.

My question is how one can come up with this formula at first place. Are there any key observations that lead us to this expression initially. And then proof by induction that this will hold true for all positive integer.

You use the principle of scientific induction: you try a few examples and guess a good bound, and then try to prove it. Simultaneously, you try to construct counterexamples. Sometimes your failed attempts at proving a bound help you find a counterexample refuting it.

Often in research one of the hardest steps is to come up with the correct conjectures. This is a creative endeavor and there are no rules which guarantee success. Skill and experience help, but sometimes you just need to be lucky.


Help in understanding the implementation/application of scope trees I’m learning (self-taught) about language implementation and compiler design, and I’m implementing a toy language to cement the concepts in my mind. However, I’m having trouble understanding how scope trees are meant to be used.

In my toy language, I’m using the Visitor pattern to traverse the syntax tree as a simple interpreter. I assign a pointer to a given symbol table to a member of the syntax node to make the various symbols available at “run time”. The symbol tables are hash tables on a stack, and I resolve symbols defined in a parent scope by inspecting the stack.

But the literature I’ve read (specifically Language Implementation Patterns by Terence Parr) talks about a scope tree as a distinct tree structure, like the syntax tree, and traversing the scope tree. Does a scope tree stand separately and alongside the syntax tree, and if so how does one track the current position in the scope tree while traversing the syntax tree? Is it simply a global pointer to a scope node/symbol table that’s adjusted whenever a scope-affecting node is encountered in the syntax tree? Or, Is it okay for the scope tree’s tree structure to be implicitly defined by piggy-backing the syntax tree as I have done? I feel I am polluting the syntax nodes definitions by adding a symbol table member.

My opinion on this is that the scope tree is a derived entity from the syntax tree, therefore as you perform your semantic analysis by walking the syntax tree you create a temporary scope tree on the fly and by doing that, the current position is automatically tracked.

The point is that both the scope tree and the syntax tree have to be married together somehow. As this would allow you to track the position of the symbols in unison. So as you traverse a method called a() on the syntax tree you statically know where to start in the symbol tree.

Note: you do not require a scope tree, you could use a stack but the advantage of the tree is that the storage of the scope is persistent. Therefore for simple validations a stack could be used to determine whether or not a variable is out of scope but for mode advanced analysis problems a scope-tree which behaves like a multidimensional stack would be required.

i.e.:

int a()
{
    int b;
    int c;
    {
       int b;
       int c;
    }
}

int b()
{
     int a;
}

So whenever you go into a function such as a you can create a function node and every time you see a declaration you can create a symbol and add it to the function's scope (push) and when you see a declaration you can resolve it by traversing up the tree.

Language implementation patterns by Terence Parr has a complete example of this and a very useful book.


Can someone help me come up with a formula for calculating the difference in time? So my assignment is to write a program that prompts the user for two different times on the same day (with 0 being midnight, 0700 being 7:00 am and 2200 being 10 pm) and then returns the difference between the two times with the amount of hours and amount of minutes elapsed. For example, if the user inputted 1255 and 1305, the program should return 0 hours and 10 minutes. I'm fine with how to find the number of hours but I cannot come up with a formula for finding the difference in minutes. Here is what I have so far:

    Scanner keyboard1 = new Scanner(System.in);
    System.out.print("Train A departs at: ");
    int a = keyboard1.nextInt();

    Scanner keyboard2 = new Scanner(System.in);
    System.out.print("Train B departs at: ");
    int b = keyboard2.nextInt();

    int difference = Math.abs(a - b);
    int hours = difference / 100;
    int minutes = (I need help here);

    System.out.print("\nDifference: " + hours + " hours and " + minutes + " minutes");

The solution I originally provided here is wrong, the comments on why the question itself is out of scope are interesting though.

      int hours = Math.abs(a - b)/ 100;

    int minutes1 = Math.min(a,b) % 100;
    int minutes2 = Math.max(a,b) % 100;

    int mdifference = ((Math.min(a,b) / 100) == (Math.max(a,b) / 100)) ? minutes2 - minutes1 : (60 - minutes1) + minutes2;

    System.out.print("\nDifference: " + hours + " hours and " + mdifference + " minutes");


Showing a partition-like problem is NP-complete Given a set $A=\{a_{1},a_{2},a_{3},\ldots,a_{n}\}$, then construct  a set $P=\{p_{1}, p_{2}, p_{3}, \ldots , p_{n}\}$ such that

$|p_{i}|=a_{i}$, and
$\sum_{i = 1,}^{n}p_{i} = 0$.

This problem is NP-complete, which I want to prove.

How do I do it?

I am thinking of a reduction from the subset sum problem. But the problem is that because of the mod.

I'm going to make a few guesses as to what you precisely mean, and if they're correct, we can edit the question so everything is clearer. First I'll define what I think you mean with your problem:

  Input: A set of positive integers $A=\{a_{1}, \ldots, a_{n}\}$.
  Question: Is there a set of integers $P = \{p_{1}, \ldots, p_{n}\}$ such that for each $i$  the absolute value of $p_{i}$ equals $a_{i}$ (i.e. $|p_{i}| = a_{i}$) and the sum of the elements of $P$ is zero (i.e. $\sum_{i=1}^{n}p_{i} = 0$)?

Clearly what we want to do is flip the sign on some of the $a_{i}$s and make them negative (or rather $p_{i} = -a_{i}$). Then the question is whether this problem is NP-complete.

Of course the answer is yes, we just need to identify a suitable problem for the reduction. In this case, there's a very simple reduction from the Partition problem:

  Partition
  Input: A set of positive integers $S=\{s_{1},\ldots,s_{n}\}$.
  Question: Is there a partition of $S$ into two disjoint subsets $S_{1}$ and $S_{2}$ such that $S = S_{1} \cup S_{2}$ and $\sum S_{1} = \sum S_{2}$?

The reduction should be pretty clear from here.

Let $S$ be the input to the Partition instance, then we construct an input set $A$ for the new problem by simply setting $A := S$.

Now we just have to show that $S$ is a Yes-instance for Partition if and only if $A$ is a Yes-instance for the new problem.

Assume $S$ is a Yes-instance for Partition, then there are two sets $S_{1}$ and $S_{2}$ that partition $S$ as described, and importantly have the same sum, then in $P$ we can set the elements corresponding to elements of $S_{2}$ to be negative, and we have a solution for the new problem ($P$ is really just $S$ in disguise, now with some signs flipped to negative).

Now assume $A$ is a Yes-instance for the new problem, then there exists a $P$ which is $A$, but with some elements now negative. Then there is some set $P' \subset P$ whose elements are negative and with a little thought we can see that as $\sum P = 0$ hence $\sum (P\setminus P') + \sum P' = 0$. Therefore, more precisely, $\sum_{p \in P\setminus P'} p = \sum_{q \in P'}|q|$. Obviously if then go back to looking at $A$ (which is just $S$ recall), we have a partition suitable for a solution to the Partition instance.

So we have that Partition $\leq_{m}$ "the new problem", which tells us that the new problem is NP-hard. The very last bit is to show that the new problem is in NP, and hence NP-complete. This is of course simple, as all we have to do is observe that we can check a solution in polynomial-time just by:

Adding up $P$ and checking the sum is zero, and
Checking that each element $p_{i}$ is $\pm a_{i}$.

So, now that I've gone a bit overboard, did I guess the details correctly?


Valid orderings for topological sort I am reading Algorithms by Dasgupta et al and the graph section provides an example graph and mentions that there are 4 orderings with one of them being B, A, D, C, E, F.

Are the other 3?

B, A, D, C, F, E
B, D, A, C, E, F
B, D, A, C, F, E

You can answer your own question by checking whether, for each edge $(u,v)$ of the graph, $u$ appears before $v$ in each of the three candidate topological orders that you listed.


What's the complexity of Spearman's rank correlation coefficient computation? I've been studying the Spearman's rank correlation coefficient

$\qquad \displaystyle \rho = \frac{\sum_i(x_i-\bar{x})(y_i-\bar{y})}{\sqrt{\sum_i (x_i-\bar{x})^2 \sum_i(y_i-\bar{y})^2}}$.

for two lists $x_1, \dots, x_n$ and $y_1, \dots, y_n$. What's the complexity of the algorithm?

Since the algorithm should just compute $n$ subtractions, is it possible to be $O(n)$ ?

You have to compute

two averages,
$2n$ differences,
three sums with $n$ summands -- which can be computed in constant time -- each and
one division, one multiplication and one square root.

All of this can be done in linear time if we assume elementary arithmetic operations run in constant time, therefore total time in $O(n)$ is certainly possible. Note that computing the root might screw things up.

Regarding space, you have several options:

Store only the averages, that is two numbers ($O(\log M)$ with $M$ the maximum number). You have to recompute all differences, that is perform a total of $6n$ subtractions.
Store the average and the differences, that is $2n+2$ numbers ($O(n \cdot \log M)$). This saves you $4n$ subtractions.

Which is preferable depends on your context.


Is it possible to solve this problem in less than n^2 time without using additional space? Here's the problem:

Given an array array containing integers, maximize array[i] + array [j] + |i - j| where i and j both range from 0 to length -1. i and j potentially could be the same.

Upon reasoning, I concluded that it is not possible. Am I wrong?

Let’s use $a_i$ for the array. You are interested in
$$
\begin{align*}
\max_{i,j} a_i + a_j + |i-j| &= \max_{i,j} a_i + a_j + \max(i-j,j-i) \\ &=
\max_{i,j} \max((a_i+i)+(a_j-j), (a_j+j)+(a_i-i)) \\ &=
\max \left[ \max_{i,j} (a_i+i) + (a_j-j), \max_{i,j} (a_j+j) + (a_i-i) \right] \\ &\stackrel{(*)}=
\max_{i,j} (a_i+i) + (a_j-j) \\ &=
\max_i (a_i + i) + \max_j (a_j - j).
\end{align*}
$$
The tricky step is $(*)$. The final expression can be computed in linear time and constant space.


Proof of correctness of algorithm Can someone help me prove the correctness of this algorithm:

MUL(a,b)
   x=a
   y=b
   WHILE x≥b DO
      x=x-b
      y=y+1
   IF x=0 THEN
      RETURN(true)
   ELSE
      RETURN(false)

I had to prove that $x_n + b\cdot y_n = a$ by induction, where $x_n$ and $y_n$ are the values of the variable x and y after the loop has iterated n times.

I have done that, but I am not sure how to prove the correctness of the algorithm.

To prove that the algorithm is correct, we assume that the loop invariant  $x_n + by_n = a$  is true per induction.

we have the following two cases:

case 1:

If MUL(a,b) returns true, then $x_n = 0$ and $y_n = n$,

so

$x_n + by_n =a \rightarrow bn = a \rightarrow a$ is a multiplum of b

case 2:

if MUL(a,b) returns false, then $x_n \not= 0$, so we have

$x_n + by_n = a \rightarrow bn \not= a \rightarrow a$ is not a divisor of b.


Variant of the knapsack problem How would you approach the knapsack problem in a dynamic programming situation if you now have to limit the number of item in the knapsack by a constant $p$ ? This is the same problem (max weight of $W$, every item have a value $v$ and weight $w$) but you can only add $p$ item(s) to the knapsack and obviously need to optimize the value of the knapsack.

Do we need a 3rd dimension or we could find an other approach without it. I tried to simply add the number of item in the knapsack in the cell and taking the max value at the end with the number of item <= $p$ but it is not the BEST solution.

Very nice question!

You are twice right:

Propagating the number of items in the knapsack does not lead to optimal solutions.
One solution consists of adding a third dimension. This is rather simple but it is necessary to take some facts into account when doing so. Note however that it is not the only alternative

In the following, I am assuming that you are familiar with the solution based in dynamic programming. In particular, I will not discuss how to traverse the table backwards to determine the solution.

Let us first focus on the typical case: the number of items is unrestricted. In this case, you just build a table $T$ where $T_{i,j}$ contains the optimal value when the overall capacity of the knapsack equals $i$ and only the first $j$ items are considered. From here:

$T_{i,j} =\max\{T_{i,j-1}, T_{i-w_j,j-1}+v_j\}$

where $w_j$ and $v_j$ stand for the weight and value of the $j$-th item respectively. If $C$ is the overall capacity of your knapsack and there are in total $N$ items the optimal solution is given by $T_{C, N}$. This algorithm is known to run in pseudo-polynomial time and one of its beauties is that it only considers those combinations that fit the maximum capacity.

However, this is not enough when adding your constraint: a maximum number of items $p$. The reason is that the previous recurrence formula does not take into account different combinations of items:

First, if $T_{i,j-1}<(T_{i-w_j,j-1}+v_j)$ then $T_{i,j}=(T_{i-w_j,j-1}+v_j)$ so that the $j$-th item is added to the knapsack in spite of the maximum number of items considered, $p$ ---so that you might be violating your constraint. Well, you might be tempted here to apply the preceding formula keeping track of the number of items inserted at each step and do not add others if the number of items currently in the knapsack exceeds $p$ but,
Second, if $T_{i,j-1}>(T_{i-w_j,j-1}+v_j)$ then $T_{i,j}=T_{i,j-1}$ so that this item is not added but that might be a big mistake in case the optimal solution $T_{i,j-1}$ already consists of the maximum number of items to insert into the knapsack. The reason is that we are not properly comparing: on one hand, to preserve the optimal solution consisting of $p$ items selected among the previous $(j-1)$; on the other hand, to insert the $j$-th item and, additionally consider the best subset with $(p-1)$ items among the previous $(j-1)$.

So that a first solution consists of adding a third dimension. For your case, let $T_{i, j, k}$ be the optimal solution when the capacity of the knapsack is $i$, only the first $j$ items are considered and it is not allowed to put more than $k$ items in the knapsack. Now,

If you are computing $T_{i, j, k}$ for a number of items strictly less or equal than the number of items that can be inserted ($j\leq k$) then proceed as usual but using the same value of $k$: $T_{i,j,k} =\max\{T_{i,j-1,k}, T_{i-w_j,j-1,k}+v_j\}$
Now, if you have to compute $T_{i, j, k}$ for a number of items strictly larger than the number of items that can be inserted ($j> k$) then: $T_{i,j,k} =\max\{T_{i,j-1,k}, T_{i-w_j,j-1,k-1}+v_j\}$

The first expression should be clear. The second works since the $(k-1)$-th layer of the table $T$ keeps track of the best combination of $(k-1)$ items among the first $(j-1)$ as required above.

An efficient implementation of this algorithm does not need to compute $T_{i, j, k}$ for all $k$. Note that the preceding recurrence relationships relate layer $k$ with $(k-1)$ and thus, it is possible to alternate between two successive layers (e.g., if you are interested in the optimal solution with $k=4$ you just use two consecutive layers: 0 and 1, 1 and 2, 2 and 3, 3 and 4 and you're done). In other words, this algorithm takes twice the memory required by the traditional approach based on dynamic programming and thus, it can be still run in pseudo-polynomial time.

Be aware, however, that this is not the only solution! And there is another you might find more elegant. In the preceding formulae, we retrieved the optimal solution which consisted of no more than $(k-1)$ items among the first $(j-1)$ as $T_{i, j-1, k-1}$. However, it should be clear that this is precisely equal to $\max\limits_{p=0,j-1}\{T_{i, p}\}$ just by using the original table!! ie., the optimal solution with no more than $k$ items can be also retrieved by considering the optimal solutions with 1 item, 2 items, 3 items, ... $(j-1)$ items ... To make this formulation work you should also keep track of the number of items considered in every partial solution so that you will need two integers per cell. This memory occupation results in precisely the same memory requirements of the algorithm shown above (using a third dimension in the form of layers $k$).

Hope this helps,


Storing the stream in less space Suppose that a stream of data is arriving like $(4,5) (5,6), \cdots ,(7,8)$, where for each particular tuple $(a,b)$, we have $a \in [n]$ and $b \in [k]$. I want to store this stream. In my setting $k = O(n^2)$, and there are no duplicates, so the stream has at most $nk$ pairs.

I want a data structure that supports three operations:

Insert$(a,b)$, for $a \in [n]$ and $b \in [k]$, adds the pair $(a,b)$ to the stream
Search$(a,b)$, for $a \in [n]$ and $b \in [k]$, checks whether the pair $(a,b)$ is in the stream
Delete$(a,b)$, for $a \in [n]$ and $b \in [k]$, removes $(a,b)$ from the stream.

I don't need to preserve the order of the stream.  I'm looking for a data structure where each operation should take $O(1)$ time.  Also I want the space usage to be at most $O(n)$ bits of space.  It is OK if the data structure is probabilistic.

Unfortunately you will always need space $\Omega(nk)$ to support your operations.

Consider all possible contents of your stream, i.e. all subsets of $[n]\times [k]$. There are $2^{nk}$ such subsets. Take two different subsets out of this, lets say $M$ and $M'$. Since the sets are different, there is an element $(a,b)$ which is contained in $M$ but not in $M'$ or the other way around. Now we perform the operation $\mathrm{Search}(a,b)$, for which the answer should be "Yes" for $M$ and "No" for $M'$ (or vice versa). It follows that both sets need a different storage content.

Moreover, this shows that each data structure needs a different storage content for each of the subsets. It follows that each data structure needs $\Omega(nk)$ bits of space to perform your operations (even without the delete operation and without constant time querying).


What is a proof of normalization of Morte? It is said that any term on the calculus of construction halts. I am studying it through  Morte, which is a bare bone implementation of the coc available on github. Is there any simple proof of normalization for the calculus of constructions? If the proof isn't simple, is there an simple intuition behind the result?

I'm afraid there is no simple proof of the normalization for the CoC, as it implies the consistency of a very strong form of logic.

A good reference is Geuvers, A short and flexible proof of strong normalization for the calculus of constructions.

The intuition of the proof is hard to convey, but basically it is shown that for each type $T$, there exists a notion of "term computable at type $T$", which is a predicate, intuitively a subset of the set of $\lambda$-terms. A computable term has good properties, in particular it is always normalizing. Building this notion of computability involves building a kind of model for the CoC, often called a realizability model.

Then it is shown that any well typed term $t:T$ is computable at type $T$.


Calculating the number of unique BST generatable from n keys, why is my number so large I want to find the number of distinct BSTs I can get with 3 unique keys (i.e. 1, 2, 3)

Here's my solution:

In case 1, we have each node have possibility, 3, 2, 1, respectively,
so 3*2*1 = 6 ways
In case 2, we have the same situation, the top node can be 1, 2, 3,
three choices, second node two choices, so and so forth, so I get 6
ways
In case 3, it is same to case 2 and I get 6 ways

In the end I have 6 + 6 + 6 number of the beast = 18 different threes.

(Edited!)

Why does this answer from Stackoverflow based on so called Catalan Number only give me 5 trees?

You overcounted some of the trees and left out two other possibilities. In your Case 1, for example, there is only one possible BST of that form, namely the one with 2 in the root, 1 in the left subtree and 3 in the right subtree (the leftmost tree below). Remember that you have to maintain the binary search tree condition: a node with value $k$ must have each of the values in its left subtree less than or equal to $k$ and each of the values in the right subtree must be greater than or equal to $k$. As a consequence, a BST with node values $\{1, 2, \dotsc,n\}$ must have inorder traversal equal to $\langle1, 2, \dotsc,n\rangle$. When $n=3$, then, we'll have these five BSTS:


Building a perfect hashing table My understanding is that one way to build a perfect hash, as per CLRS, is to use two levels of hashing, with universal hashing functions at each level.

More specifically, CLRS shows that assuming $n$ is the total number of keys, and $n_j$ the number of keys hashed to the value $j$ for the second level, we can then make $m=n$ and $m_j=n_j^2$ to guarantee that the expected number of collisions is < 1/2 in the second level.

However, as far as I understand, collisions are still possible in this second level, so to truly have no collisions in this 2nd level, one may need to try a few hash functions in this level for each value of $j$.

Is my understanding correct? If so, CLRS does not seem to elaborate much on this algorithm. Is it fair to assume that a simple sequence of random "try and error" (i.i.d sampling) of hash functions (in this 2nd level) is "as good as it gets" at least for this perfect hashing design?

As mentioned by the OP in the comments, CLRS is using the ideas of Fredman, Komlós and Szemerédi, Storing a Sparse Table with $O(1)$ Worst Case Access
Time.

Corollary 4 gives a range of parameters for which the construction succeeds with probability $1/2$; this could be amplified to any constant with minimal loss of parameters.

Lemma 2 shows how to derandomize the construction, but the resulting algorithm isn't practical.

You can also probably choose parameters for which the construction succeeds with high probability, in which case you can try your luck and not even check the hash function.


Proving a function is uncomputable I am trying to solve the following problem:

For each Turing machine $M_k$ and each string $x$ in $\{$0,1$\}$$^\ast$ let

$time_k(x)$ = $\{$the number of steps executed by $M_k(x)$ if $M_k(x)$$\downarrow$ (halts), and $\infty$ if $M_k(x)$$\uparrow$ (does not halt)$\}$

Prove that the function $T$: $\mathbb{N}$ $\rightarrow$ $\mathbb{N}$ defined by

$T(n)$ = max$\{$$time_k(x)$ | $0$ $\leq$ $k$ $\leq$ $n$, $x$ $\in$ $\{$0,1$\}$$^\ast$, and $M_k(x)$$\downarrow$ (halts)$\}$

is uncomputable.

So far, I have begun my proof by assuming that $T$ is computable. Thus, there exists a Turing machine $M$ such that for all $n$$\in$$\mathbb{N}$, $M$ produces $T(n)$ on its tape. Thus, we must show that we can decide the Halting Problem if $T$ is computable, which in turn lets us know that $T$ is uncomputable since the Halting Problem is uncomputable.

I do not know where to go from there however. Any help would be greatly appreciated. Thanks in advance.

Hint: Given $T(n)$, any $k \leq n$, and an input $x$, it is enough to run $M_k$ for $T(n)$ steps in order to decide whether it halts on $x$.


Is the set of programs that compute some function other than $h$ recursively enumerable? Let $h$ be a total computable function. Is $S = \{x \mid f_x \neq h\}$
  recursively enumerable?

Originally this was an exercise that restricted $h$ to: $h(x) = x + 1$ . However, it can be formulated as a more general case.

By Rice's Theorem, it is not recursive. Intuitively,

$S$ is not r.e. as if it was, it would mean that we would know that
$f_x(y)$ halts for some input $y$ in order to check if it has a different image of $h(y)$.
$\overline{S}$ is not r.e. as if it was, we would be able to check if $f_x(y)
   = h(y)$ for every input $y$ (we would check equality for infinite inputs).

How would you solve this problem?

Note: I tried something, but I'll post it as an answer. Some thoughts would be great and really helpful. Any approach to this problem using reduction or diagonalization methods would be useful.

The set $S$ is in fact neither c.e. nor co-c.e. You can prove this via an m-reduction to $\overline{TOT} = \{ x | \varphi_x \mbox{ is not total } \}$ (which is also neither c.e. nor co-c.e.).

Define:

$ \varphi_{f(x)}(y)=\begin{cases}
    h(y) & \mbox{if $\forall z\leq y~\varphi_x(y)$ halts}\\
    undefined & \mbox{ow.}
    \end{cases}
    $

Where $f$ is from the s-m-n theorem.

Then you have that $\overline{TOT} \leq_m S$ via $f$ because, for all $x$:

$x \in TOT \iff \forall y~\varphi_x(y) \mbox{ is defined} \iff \forall y~\forall z\leq y~\varphi_x(z) \mbox{ is defined} \iff \forall y~\varphi_{f(x)}(y)=h(y) \iff f(x) \notin S$


What advanced math topics are recommended for computer science? I am enrolled in a computer science degree at the moment. I have looked around trying to find answers, but people tend to ask 'what is the minimum math needed for computer science' as opposed to what is recommended. I am very interested in theoretical computer science topics. My interests sort of jump around but right now I have a distinct interest in cryptography.

I have always loved math. In high school I did advanced math units - equivalent to calc 1 & 2, as well as discrete math. Right now I am doing a linear algebra unit and a calc 3 unit (as well as my cs units). Next semester I will be doing a unit on number theory. But what else? What other units would actually help with computer science? For example, I can't imagine learning about differential equations would be applicable to computer science.

If you want to do theoretical computer science, more math the better. Ultimately, learning math is not so much about learning specific topics, though that is of course important, it is also about gaining mathematical maturity, which means being able to think mathematically, being able to formalise and prove things, being able to abstract away inessential details and capture the essence of a problem. Of course, actually knowing lots of useful theorems is important too.

For crypto you'll need (at least) algebra (group theory etc), number theory, and discrete mathematics. Some logic wouldn't hurt either.

Linear algebra will help with machine learning and computer graphics.

Logic, topology and category theory will help for many Theory B topics (programming language semantics etc).

The list goes on ...


Context free language and the complement of it Given the language $L_1 = \{a^i b^j c^k \mid i \neq j \vee i \neq k\}$, I need to determine whether it is context-free by using the pumping lemma. I must do the same for the complement of this language.

I started off by breaking $L_1$ into two parts, $L_1 = L_2 \cup L_3$, where $L_2 = \{a^i b^j c^k \mid i \neq j\}$ and $L_3 = \{a^i b^j c^k \mid i \neq k\}$, and I proved that both the languages are not context free, hence the union which is $L_1$ is also not context-free. Is this approach of mine correct?

Also would the complement of $L_1$ be $L_1' = \{a^i b^j c^k \mid i = j \wedge i = k\}$ and break down $L_1'$ into two parts $L_2'$ and $L_3'$ and by the closed under intersection rule for context-free languages we know $L_1' = L_2' \cap L_3'$ is not context free.

This how I approached both the parts, and I would like to know if my approach is correct or wrong. Help would be really appreciated.

Sorry, your approach does not work.

Breaking down $L_1$ into two parts is a good idea. Unfortunately you proof these parts are context-free cannot be correct, as one can give a grammar for each of them.

As for the complement, there is no such thing as a intersection rule. The fact that context-free languages are not closed under intersection simply states that there exist two context-free languages the intersection of which is not context-free. The intersection of any random pair of context-free languages can be context-free (e.g., if the intersection is empty).

Back to the drawing board.


What makes Bayesian Networks decomposable into joint trees? Given a Bayesian Network $N$, one can build a junction/joint tree $JT$ over $N$ by applying series of steps (namely, moralisation,triangulation..etc). Then we can use $JT$ to answer queries over $N$.

My question is: what makes BN decomposable into $JT$? The structure (along with the CPTs) must exhibit certain conditions otherwise any graphical model is decomposable.

I found the answer in valuation algebra more specifically in this paper .
They assume the set of functions (i.e. tables/relations/potentials/probability distributions) form a commutative semigroup. There are six axioms that the graphical model/representation should obey in order to use local computations (and thus joint trees). The valuation algebra has three operations:

Labeling: Mapping each potential $\phi$ to its scope $d(\phi)$ (variables that defined it).
Combination: Two potentials $\phi$ and $\psi$ are combined through combination operator $\phi \otimes \psi$ (in BNs $\otimes$ is the multiplication of CPTs).
Marginalization: The usual projection operator (this corresponds to summing up irrelevant variables in BNs).

where the axioms are:

Commutative Semigroup:
it is clear that the set of CPTs represent a commutative semigroup under the combination operator.
Labeling: for two potentials $\phi$ and $\psi$, $d(\phi \otimes \psi)=d(\phi) \cup d(\psi)$
Marginalization: $d(\phi^{\downarrow x})=x$ where $x\subseteq d(\phi)$
Transitivity: $(\phi^{{\downarrow y}})^{\downarrow x}=\phi^{\downarrow x}$ where $x\subseteq y\subseteq d(\phi)$
Combination: $(\phi \otimes \psi)^{\downarrow z}=\phi \otimes \psi^{\downarrow{z\cap y}}$ where $d(\phi)=x,d(\psi)=y$ and $x\subseteq z\subseteq x\cup y$
Domain: $\phi^{\downarrow x}=\phi$

The axioms are clearly satisfied by the nature of multiplication and marginalization over BN CPTs. Really do not know why axiom 6 is there. Sorry for abusing some of the notations.


Does solving subproblems in logspace in different models implies solving original problem in logspace? Let's consider the following situation:

We have a problem $\mathsf{L\text{}}$ . We would like to solve it in $LOGSPACE$. Let assume that our problem $\mathsf{L\text{}}$  can be divided to two parts: $A$ and $B$.

We can solve $A$ using computatation model $M_1$ in $LOGSPACE$.

We can solve $B$ using computation model $M_2$ in $LOGSPACE$, $M_1 \neq M_2$

Does it mean that we  can solve $P$ in $LOGSPACE$ ? Why?

The composition of two logspace functions is again in logspace. This is a classical result that you can try to prove on your own.


How to get the quick answer to the "Is there AT LEAST ONE subset that contains all given elements?" question if the set of subsets is very large? I have a very large amount of objects that look like this:

DataDict = {
id1: {"a": true, "b": true, "bc": true, "hgf": true},
id2: {"bcwe": true, "nKNNn": true, "mjj": true, "AAt": true},
id3: {"h": true, "a": true, "mjj": true, "ABwAU": true},
id4: {"wvzy": true, "zzba": true, "abc": true, "a": true},
...
}

or just (as a set of sets, note that ids may be excluded)

DataSet = {
{"a", "b", "bc", "hgf"},
{"bcwe", "nKNNn", "mjj", "AAt"},
{"h", "a", "mjj", "ABwAU"},
{"wvzy", "zzba", "abc", "a"},
...
}

Let M denote the total number of objects in DataDict (or subsets in DataSet), and let N denote the total number of unique names of properties found in DataDict (or the total number of unique strings found in DataSet).

The question is: given the set of strings {string1, string2, string3, ...}, how to get the Yes/No answer (assuming that there is a way to prepare the “index” for DataSet) to the “Does DataSet contain at least one subset that contains string1 AND string2 AND string3 AND ...?” question as fast as possible?

In another form, the question is: given the array A = [string1, string2, string3, ...], how to build the index (data structure) for DataDict that allows to quickly determine if it contains at least one object obj (I don’t care which object to choose, moreover, I don't want to return this object, all I want is that the function should return true if such an object exists, and false if not) such that DataDict.obj.string1 is true AND DataDict.obj.string2 is true AND DataDict.obj.string3 is true AND ...?

The only way that I see is to build the index like this:

{
"a": [1, 3, 4],
"abc": [4],
...
}

and, for example, if A = ["a", "abc"], then I need to find the intersection of two arrays ([1, 3, 4] and [4]), but stop as soon as one common element is found and return true (if there are no common elements, return false). But these operations are very costly and time-consuming, which often leads to the unacceptable waiting time. Is there a way that guarantees a significantly better performance for all cases?

It would be extraordinarily nice if there exists a solution that (assuming that the index already exists) finds the answers depending on A.length time. The good solutions may depend on log M or log N or even close to log M multipled by log N, but I cannot imagine how to find such a solution...

It's possible to answer such queries in time $O(M^{1 - S/N})$, where $S$ is the size of the subset in the query, using a data structure from Ron Rivest:

Partial-Match Retrieval Algorithms.  Ronald L. Rivest.  SIAM Journal Computing, vol 5 no 1, March 1976.

Basically, you convert each set to a bitvector of length $N$, then use Rivest's partial-match queries.  This is ever so slightly faster than the naive algorithm, whose running time will be about $O(M)$ (or a bit more).

Your idea using indices is another approach that might be faster in practice, especially if most sets are much smaller than $N$.  Note that it's possible to optimize this a bit.  Your index will have, for each string $x$, a list of indices of sets that contain $x$ and the length of that list.  Now, given a set $A$, you can check for each $x \in A$ the length of the corresponding list in the index, and find the shortest such list, and enumerate all entries in that list to see if any of them are a superset of $A$.  See  also https://cstheory.stackexchange.com/q/19526/5038.  I think the worst-case running time is no better than the naive algorithm, but in practice it might perform significantly better.


Solving cycle in undirected graph in log space? Setting

Let:
$$UCYLE = \mathcal \{ <G> ~:~ G \text{ is an undirected graph that contains a simple cycle}\}.$$

My Solution

we show $UCYLE \in L$ by constructing $\mathcal M$ that decides $UCYLE$ using $L$ space.

$\mathcal M = $"On input $<G>$ where $G = (\mathbb V, \mathbb E)$:

For each $v_i \in \mathbb V$, for each $v_j \in Neighbor(v_i)$, store the current $v_i$ and $v_j$.
Traverse the edge $(v_i,v_j)$ and then follow all possible paths through $G$ using DFS.
If we encounter $v_k \in Neighbor(v_i) / \{v_j\}$ so that there is an edge $(v_i,v_k) \in \mathbb E$, then ACCEPT. Else REJECT."

First we claim $\mathcal M$ decides $UCYLE$. First, if there exists a cycle in $G$, then it must start and end on some vertex $v_i$, step one of $\mathcal M$ tries all such $v_i$'s and therefore must find the desired vertex. Next, suppose the cycle starts at $v_i$, then there must exists a starting edge $(v_i,v_j)$ so that if we follow the cycle, we come back to $v_i$ through a different edge $(v_k,v_i)$, so we accept in step three. Since the graph is undirected, we can always come back to $v_i$ through $(v_i,v_j)$, but $\mathcal M$ does not accept this case. By construction, neither does $\mathcal M$ accept if we come upon some $v_k \in Neighbor(v_i)/\{v_j\}$ but there is no edge from $v_k$ to $v_i$.\newline

Now we show $\mathcal M \in L$. First if the vertices are labled $1,\ldots,n$ where $|\mathbb V| = n$, then it requires $log(n)$ bits to specify each $v_i$. Next note in $\mathcal M$ we only need to keep track of the current $v_i$ and $v_j$, so $\mathcal M$ is $2 log(n) = O(log ~n) \in L$.

My Problem

My problem is how do you perform DFS on the graph in $log(n)$ space. For example, in the worst case where each vertex has degree $n$, you'd have to keep a counter of which vertex you took on a particular path, which would require $n \log(n)$ space.

The trick is to use Reingold's result that undirected reachability is in logspace. For each vertex $v$, we check whether the connected component containing $v$ contains a cycle by counting the number of vertices and edges. We do that by going over all vertices $u$, check whether $u$ is reachable from $v$, and if so, increase the vertex counter by 1 and the edge counter by half the degree of $u$. After going over all vertices, we have counted the number of vertices $V$ and edges $E$ in the connected component containing $v$. This component contains a cycle if and only if $E \geq V$.


Pascal FOR loop with context free gramar In Pascal For-do loops, there is a rule stating that one cannot modify the counter variable inside the body of the loop.

To exemplify the rule, take the following Pascal for-do, which is not valid, since the counter variable is being modified inside the loop's body:

for i := 0 to 10 do i := i + 1;

My question is: Is possible to express this rule using context-free grammars?

The answer depends on how you represent variables.

If there are an infinite number of variable names, the answer is no.
If there are a finite number of variable names, the answer is "yes but you never would in practice".

Here's some informal arguments for that:

For the first case, there must be some set of non-terminals which represent valid loop bodies. And for each variable, there must be a non-terminal where you can refer to that variable, and one where you can't. Because of loop nesting, this must be true for any combination of any number of variables i.e. we need a distinct non-terminal for each of an infinite combinations of allowed and not allowed variables.

But, then we have an infinite number of non-terminals, which is not allowed in a context-free grammar.

This is basically because of the "context free" part of CFG. Knowing which variables are allowed and aren't is context, which our grammars are free of.

In the case of a finite number of allowed variables, you basically model it like I said above, with a different non-terminal for each combination of variables. So in terms of computability/expressibility, you you can do it with a context free grammar, in the same way you can model your computer and its 8GB of RAM with a finite automaton. Doing so will explode quickly, and it's not the way you want to do things.


Data structure for maintaining large space-efficient filtered array How does one implement a space efficient data structure that satisfies the requirements below?

You have a large array
You have a filter which tells you which elements in that large array are to be deleted
Lookup of i'th element in the array should be constant time
The space formerly occupied by deleted elements in the array should be available for further use.

I've explored approaches ranging from bloom filters to trees, but they violate one requirement or the other.

EDIT: Further clarification.

Space-efficient: Any space not used by elements of the array that have not been deleted by the filter, which we can term extra space or space for book-keeping, should be $O(1)$. We can probably relax this to allow any solution that gets close to $O(1)$ extra space. $O(n)$ extra space is undesirable.

Array in the context of this problem is an array-like collection where you can get the $i$th element in constant time. You lookup by index here.

I suspect amortized performance bounds should be fine.

The filter takes each element of collection and returns 0/1 corresponding to delete/no delete.

There is a simple and clean solution that satisfies all of your requirements.

To delete elements, you scan the set of array indices (from 1 to $n$), querying the filter on each and deleting each element that is to be deleted, compacting the array as you go (to shift everything after the deleted element forward one slot).  The deletion operation can be implemented in $\Theta(n)$ time, with a single linear scan.  This satisfies all of your requirements.  (Note that you did not specify any restriction on the running time of the deletion operation.)  In particular, it is space-efficient: it does not require any extra space (it has 0 space overhead, since after deletion, all of the space that's not in use for storing undeleted array elements is immediately available for other use).  Looking up the $i$th element of the array takes constant time, thanks to the compaction: you just index into the $i$th element of the compacted array.

If for some reason this solution is not acceptable to you, then you need to re-think the requirements more thoroughly and edit the question to pose the exact set of requirements more carefully.

Given the problem as you've stated it, I don't think it will be possible to do better than this trivial solution.  You can't do better than $\Theta(1)$ time for lookup.  You can't do better than 0 space overhead.  And I don't think you can do better than $\Theta(n)$ time for deletion, given how you specified the interface to deletion (which works by specifying a filter that is an oracle that, on input $i$, tells you whether index $i$ should be deleted or not).  Even just figuring out which elements of the collection to delete requires querying the filter on all $n$ possible indices, which takes $\Theta(n)$ time.  So, I don't think you can do any better than $\Theta(n)$ time for the deletion operation -- and in particular, I don't think you can do any better than the above scheme, at least not with this specification of how the filter is provided.


Is binary-search really required in Chan's convex hull algorithm? I have a little doubt about Chan's algorithm.

From Wikipedia's description we see that the second phase of an algorithm works with $K = \mathrm{ceil}(\frac{n}{m})$ subsets $Q_i$. The goal of the second phase is to compute $m$ points $\{p_1 ... p_K\}$. On $i$-th iteration the candidate $p_i$ is chosen among $\{q_1 ... q_K\}$, where $q_j \in \mathcal{CH}(Q_j)$  is a point such that every other point of $\mathcal{CH}(Q_i)$ lies to the left of line $p_{i - 1}q_j$.

According to the Wikipedia page, each point $\{q_1 ... q_K\}$ of set is searched in $\mathcal{O}(\log m)$ using binary search, which is the main reason that whole second phase takes $\mathcal{O}(Kh + Kh \log m)$, where $h$ is the size of resulting convex hull (which is unknown at the beginning).

I doubt that it is necessary to perform this binary search for every candidate-point $q_i$ on each iteration. I get that, when we just start with $p_0$, there's no other way to do this. What about the following iterations? As I think of it, on each iteration the point $q_i$ either stays the same or it changes to one of the successive point of $Q_i$ in ccw-order. And one point cannot become a candidate more than twice (or even once?). If that is the case, why can't we use $K$-pointer technique and just set $q_i \leftarrow q_{i + 1}$ while $q_i$ is not a tangent line for current iteration. There shouldn't be more than $2m$ candidate changes for each $Q_i$ for all $m$ iterations. Wouldn't the resulting complexity $\mathcal{O}(Kh + Km)$ be better than $\mathcal{O}(Kh + Kh\log m)$?

And some pictures that aren't on wiki page to give a better idea of this second phase.
The first one shows what are the candidates.

And the second one should provide an intuition about choosing $q_i$ for the next iterations.

I think this is correct... see 2. Chan’s Algorithm p4, Remark.

  Remark. Using a more clever search strategy instead of many binary searches one can handle the conquer phase in $O(n)$ time. However, this is irrelevant as far as the asymptotic runtime is concerned, given that already the divide step takes $O(n \log H)$ time.

Anyway, the complexity is bounded by the divide phase.


Is $O(n^{1/2})$ exponential? Is $O(n)$ better than $O(n^{1/2})$? I was just going through some of the primality test algorithms. It seems that the regular one – loop up to square root of $n$ – has running time $O(n^{1/2})$.

Is $O(n^{1/2})$ exponential? And is exponential time better than polynomial always?

A function that is $O(n^{1/2}) = O(\sqrt{n})$ is a polynomial, not an exponential, function of $n$. However, when analyzing the run-time of algorithms, we need to be clear about what $n$ actually is.

Here, $n$ is the (value of the) number whose primality is being tested. However, we measure the run-time of the algorithm in terms of the length of its input in bits. The number $n$ can be represented in $\log n$ bits, which means that the running time of $O(n^{1/2})$ is actually exponential in the length of the input.


How to take complement of a language? I'm stuck on this question about context-free languages and was hoping for some clarification.

$\qquad L = \{a^i b^j c^k \mid  i=j, i=k\}$
is not context-free. Show that its complement is context-free.

I understand that the complement basically means everything not in $L$, that is $A^* \setminus L$. However, I have no  idea how to actually take a complement for a language like  this.

You are right. The complement consists of all strings not in the language. So basically if the language says "all strings such that X holds" the complement is "all strings such that not X holds", the logical negation of X.

In this case the logical negation of "$i=j$ and $i=k$" equals "not ($i=j$ and $i=k$)" or using the Morgan's rule, "$i\neq j$ or $i\neq k$".

But there is a slight catch. Actually the strings in $L$ have an additional explicit condition, they are of the form $a^i b^j c^k$ for some $i,j,k$. That means the actual complement is the union of (1) all strings not of the form $a^i b^j c^k$ (thus, not in $a^* b^* c^* $) and (2) all strings of the form $a^i b^j c^k$ such that "$i\neq j$ or $i\neq k$".

The strings in (1) form the regular language $\{a,b,c\}^* - a^* b^* c^* $ and should not bother you too much. The strings in (2) are treated elsewhere in this forum.


Arithmetic operators and regex Let $L$ be the language over the alphabet $\{0, 1, 2, 3, (,), +, -, *, /\}$, $L$ is the set of operations with correctly formatted natural numbers. A single number is considered to belong to $L$.

2 - - 3 is an incorrect expression, 2 + 3 is correct, 2 + (-3) is correct.
Is it possible to write a regular expression for this language?  If not, why?

I think that it is not possible to write a regular expression for this language, because of the operator / we cannot write 2 / 0 for example and are more than a finite number combinations to make this possible. Is it correct?

You haven't defined your language, but presumably
$$
L \cap [^*0+0](+0])^* = \{ [^n[0+0](+0])^n : n \geq 0 \},
$$
where I replaced parentheses with square brackets. The latter language is essentially $\{a^nb^n : n \ge 0 \}$ in disguise, and so isn't regular. It follows that $L$ isn't regular as well.


How is diagonalization a valid argument for the undecidability of the halting problem? All proofs for the undecidability of the halting problem seem to be based directly or indirectly on self-reference.

def g():
    if halts(g):
        loop_forever()

My question is: how can the input of a TM contain the TM itself and its input?

If the description of the TM has states and transitions, then it has more than its input therefore the input of the TM has infinite size because it contains both the TM and the input.

Try the following code instead:

def quote(s):
    return s.replace("'", "\\'")

def g():
    s = '''
def g():
    s = \'\'\'%s\'\'\'
    if halts(s %% quote(s)):
        while True:
            pass
'''
    if halts(s % quote(s)):
        while True:
            pass

If we add the following halting routine:

def halts(prog):
    print prog
    return False

then we can run g() and see that the input to halts is indeed the code for g():

>>> g()

def g():
    s = '''
def g():
    s = \'\'\'%s\'\'\'
    if halts(s %% quote(s)):
        while True:
            pass
'''
    if halts(s % quote(s)):
        while True:
            pass

A program that prints itself is called a quine. The corresponding result in computability theory is the recursion theorem, which ensures that (in a sense) a program can have access to its own source code.


Is Breadth First Search Space Complexity on a Grid different? Is the Space Complexity O(number_rows + number_cols) for Breadth First Search on a Grid. This is an attempt to show my reasoning:

For example, the flood fill question is described here:

https://www.geeksforgeeks.org/flood-fill-algorithm-implement-fill-paint/

The flood fill algorithm using breadth first search (queue) has space complexity: O(number_rows + number_cols).

Why? Suppose you start at the top left corner (or coordinate (0,0)). Going to the right we will get at most O(number_cols) in the queue. When we reached the end of the column we can then start going down from coordinate (0, 0) giving us O(number_cows + number_cols) in the queue.

Then, is it the case that many of the questions where we use breadth first search on a grid we will get space complexity of O(number_rows + number_cols). For example:

Flood Fill question above,
Maze where we have to find the shortest
path from start to exit,
Finding number of islands (reference below)

But for 3) finding the number of islands, it looks like some people are saying the space complexity is O(number_rows * number_cols) from : https://stackoverflow.com/questions/50901203/dfs-and-bfs-time-and-space-complexities-of-number-of-islands-on-leetcode

On the other hand, I would assume that the space complexity of dfs on a grid is O(number_rows * number_cols)

The questions are as follows based on the above:

Is the space complexity of breadth first search on a grid: O(number_rows + number_cols)?
Is the space complexity of depth first search on a grid: O(number_rows * number_cols)?

Other references:

https://stackoverflow.com/questions/21054959/time-and-space-complexity-for-breadth-first-search

https://stackoverflow.com/questions/4261112/time-and-space-complexities-of-breadth-first-search

It depends what you mean by a "on a grid".

If you mean that you are working with the graph of a complete grid, with number_rows * number_cols vertices (one for each grid point) and an edge between every pair of adjacent vertices:

Yes, that's correct.  The asymptotic time complexity of both is O(number_rows * number_cols), and the asymptotic space complexity is O(number_rows + number_cols) for BFS or O(number_rows * number_cols) for DFS.

If you mean that you are working with a graph that is a subgraph of a complete grid, then:

No, that's incorrect.  The asymptotic time complexity of both is O(number_rows * number_cols), and the asymptotic space complexity of both could be as large as O(number_rows * number_cols), as explained in https://stackoverflow.com/a/50912382/781723.


How can i solve a recursion equation with square root using recursion tree method? $T(n) = \sqrt{2}T(\frac{n}{2}) + \sqrt{n}$

I am trying to solve this question by recursion tree method, do we have any way in which we can draw a recursion tree for this eqn.
I just don't want to use master or extended master theorem

If you apply the recursive formula again to $T(n/2)$ you get the following:
$$ T(n) = \sqrt{2}\cdot T(n/2) + \sqrt{n} \\T(n)= \sqrt{2}(\sqrt{2}\cdot T(n/4) + \sqrt{n/2}) + \sqrt{n} \\T(n)= 2\cdot T(n/4) + 2\sqrt{n}$$

For this formula you are now probably able to draw a recursion tree.


complexity of outputting the union of a collection of subsets of a set This question concerns the time complexity of outputting the unions of subsets of a given set.

Given $m$ subsets of an $k$-element set, can the union of those sets be computed in linear time with respect to $m+k$?  Or $(m+k)p(\log (m+k))$, where $p(x)$ is some polynomial?  Or at least known is there a  subquadratic  algorithm (with respect to $m+k$)?

Any direction on this would be much appreciated.

That's not possible.  Any correct algorithm will have to read all of the input.  The input size is $\Theta(mk)$, so that means any correct algorithm will have to have running time at least $\Omega(mk)$.  $O(m+k)$ and $O(m+k) p(\log(m+k)))$ are not achievable.


Intersection of Turing-recognizable language and regular language True or false:
An intersection of a Turing-recognizable and a regular language is always Turing-decidable.

This was asked on a practice test and the answer is False. Why? I thought regular languages were a subset of decidable languages. So if you intersect regular and recognizable the result would also have to be a subset of decidable.

Is that not correct?

A recognizable language is not necessarily decidable. If you intersect such a language with $\Sigma^*$ it doesn't suddenly become decidable.


where is all deleted data will go from memory system/internet? where is all deleted data will go  from a memory system ?
if it is not deleting actually where it storing ?
i am always wonder about this when we are sending something to a memory system it takes long time (depends up on usb port) and when we are deleting it not taking more than a bling of eyes and disappears actually where it goes ?
** deletion process is happening on both memory device and internet is same or different ** ? can we recover data from internet ?

Deleting is not necessarily destroying data. It can be done (much faster, indeed) by making it inaccessible. You can do it by erasing critical information from the data structures that are used to index the data you want to delete. How exactly this is done depends on how the storage device is organized (formatted).