Monotone property of heuristic in $A^*$ algorithm In the $A^*$ algorithm, the optimality of the path is guaranteed when the heuristic has the property of being admissible or monotone\consistent.

I was able to understand the admissible property, however, I am not able to wrap my head as how the monotone property guarantees that any node can be explored only once (i.e., the path that lead to that node has the shortest path). As stated in the wiki page ,

  "If the heuristic $h$ satisfies the additional condition $h(x) \le d(x, y) + h(y)$ for every edge $(x, y)$ of the graph (where $d$ denotes the length of that edge), then $h$ is called monotone, or consistent. In such a case, $A^*$ can be implemented more efficiently—roughly speaking, no node needs to be processed more than once (see closed set below)—and $A^*$ is equivalent to running Dijkstra's algorithm with the reduced cost $d'(x, y) = d(x, y) + h(y) − h(x)$."

When is a node visited twice?
Consider the following graph, where the heuristic satisfies the condition to always underestimate the length, but is not monotonic because $h(b) > d(b,c) + h(c)$.

When we visit $a$, we add $b$ and $c$ to the priority queue with priorities
$$p(b) = d(a,b)+h(b) = 1+8 = 9$$
$$p(c) = d(a,c)+h(c) = 3+1 = 4$$
Obviously, $c$ is visited first despite the shortest path to $c$ is actually via $b$. Later, when we visit $b$, $c$ is visited again from $b$ and has it's total weigth updated to $2$.
Strategy to find the shortest path without visiting a node twice.
If $a\rightarrow b\rightarrow c$ is shorter than $a\rightarrow c$, we want to visit $b$ first, so we reach $c$ from $b$ before reaching it from $a$. If we can ensure this, we don't even need to visit it from $a$ later on, because $a\rightarrow b\rightarrow c$ is shorter anyway.
This boils down to:
If
$$d(a,b)+d(b,c) < d(a,c)$$
is true, we must visit $b$ first.
We can add $h(c)$ on both sides without changing anything.
$$d(a,b)+d(b,c)+h(c) < d(a,c)+h(c)$$
If the monotonic constraint is fulfilled, we can replace $d(b,c)+h(c)$ by $h(b)$, since it's less or equal. The equation
$$d(a,b)+h(b) < d(a,c)+h(c)$$
is still true. This also happens to be the test the $A*$ algorithm uses do decide whether or not it will visit $b$ before $c$. If it is true, it visits $b$ first. This is exacly what we wanted to achive.


Lower bound on algorithm solving certain recurrence I have to find the lower bound of the following recursion:
$A_1 = C_1 = p_1$, $B_1 = D_1 = 1-p_1$, $F_k = A_k + B_k$. Evaluate $F_n$.
\begin{align}
A_{k+1} &= (A_k + 2C_k) p_{k+1} + (1-p_k) p_{k+1}, \\
B_{k+1} &= (B_k + 2D_k) (1-p_{k+1}) + p_k (1-p_{k+1}), \\
C_{k+1} &= C_k p_{k+1} + (1-p_k) p_{k+1}, \\
D_{k+1} &= D_k (1-p_{k+1}) + p_k (1-p_{k+1}).
\end{align}
In this case all numbers of the form $p_i$ are given inputs (there are $n$ of them).
I have to find the lower bound of this algorithm.
Since it's runtime is just $O(n)$ (right?), I know for sure that the maximum possible value of the lower bound is $\Omega(n)$. How would I go about proving/disproving that $\Omega(n)$ truly is the minimum bound  and that $\Omega(n-1)$ is not/is attainable?
The only main method I know for proving stuff like this is an Adversary Argument but after a couple hours of thinking, I still haven't been able to come up with an argument to prove what I want.
Any helps/tips/suggestions would be greatly appreciated.

There's quite a lot of confusion here:

$\Omega(n)$ and $\Omega(n-1)$ are absolutely the same.
You don't an adversary argument to show that this algorithm runs in $\Theta(n)$. It follows immediately from the description of the argument.
There is a difference between analyzing the running time of a particular algorithm and showing that every algorithm that correctly solves a problem must run in at least so many steps.

In order to show that any algorithm computing $F_n$ correctly must run in time $\Omega(n)$, we will show that any such algorithm must read all inputs $p_1,\ldots,p_n$. The starting point is the following observation:

The correct output is different for the instances $p_1=\cdots=p_n=0$ and $p_1=\cdots=p_{i-1}=0,p_i=1,p_{i+1}=\cdots=p_n=0$.

Given that, we can use a simple adversary argument to show that any algorithm correctly computing the function must read all $p_j$. Indeed, run the given algorithm, answering $0$ whenever it queries the value of some $p_j$. If it announces the answer without querying, say, $p_i$, then it cannot tell apart the two instances above, and in particular, its answer will be wrong on at least one of them.


Why is $f(n) = \Theta(g(n))$ where $f(n) = n(n+1)/2$ and $g(n) = \sum_{i=1}^n (n/i)^2$? Why is $f(n) = \Theta(g(n))$ where $f(n) = n(n+1)/2$ and $g(n) = \sum_{i=1}^n (n/i)^2$?

Also, why is $f(n) = \Theta(g(n))$ where $f(n) = n^{\log_49}$ and $g(n) = 3^{\log_2 n}$?

I know what notations mean - I just want to prove them.

Since you get
 $$g(n) = \sum_{i=1}^n (n/i)^2\geq n^2\sum_{i=1}^1 (1/i)^2=n^2\cdot H_n^{(2)}$$

Where $H_n^{(2)}$ is the second generalized harmonic number.

Since
$$\forall n\geq 1:\ \  1 < H_n^{(2)} < \frac{\pi^2}{6}$$

You get that
$$n^2 < g(n) < n^2 \cdot \frac{\pi^2}{6}$$

and $$f(n)=\frac{n(n+1)}{2}\leq \frac{(n+1)^2}{2}\leq \frac{(2n)^2}{2}\leq 2n^2$$
$$f(n)=\frac{n(n+1)}{2} \geq \frac{n^2}{2}$$

Then $$\forall n\geq 1: \frac{3}{\pi^2} g(n) \leq f(n)\leq 2\cdot g(n)$$

And thus $f(n)=\Theta(g(n))$.

As for the second part of the question:

Since $$\forall x,y,z>0:x^{\log_z y}=(z^{\log_z x})^{\log_z y}=z^{\log_z x\cdot {\log_z y}}=(z^{\log_z y})^{\log_z x}=y^{\log_z x}$$ you get that:

$$g(x)=3^{\log_2 n}=n^{\log_2 3}=n^{\log_4 9}$$

And thus $$f(n)=\Theta(g(n))$$


Canonical representation of finite maps on non-overlapping finite rational intervals I would like to have a canonical representation of a map from rational intervals (f, t] with f, t ∈ ℚ to some irrelevant value type. These intervals are non-overlapping and there exist only finitely many such keys in the map. I would like to be able to implement the following functions on this representation:

Lookup by rationals (not by ranges, as it is unclear what exactly that would mean)
Insertion by ranges. This will partial overwrite existing intervals (which are split in the process)
Compare two maps for equality by comparing their representation.
Create an empty map.

Particularly interesting are cases such as inserting two adjacent intervals with the same value V. I think for the map to be canonical, this case would have to be indistinguishable from inserting the joined interval with value V.

As always with (me and) canonical representations, I have failed to come up with any good leads on google (scholar). Is anyone aware of a result for this particular problem? I would be very thankful for any pointers to papers or implementations.

It's possible to build a data structure that in practice has $O(\lg n)$ lookup, $O(\lg n)$ insertion, and $O(1)$ equality-tests.  I'll describe how below.  (If you care about theoretical worst-case complexity, there are some caveats, but those caveats can probably be ignored for practical implementation.)

You can handle the lookup, insertion, and creation operations using a balanced binary search tree on the endpoints of the intervals.  If you have $n$ intervals, you'll have at most $2n$ endpoints, so you have a balanced tree on $O(n)$ leaves.  Lookup and insertion can be done in $O(\lg n)$ time, using an appropriate balanced tree data structure, which is efficient.

Ensuring it has a canonical representation is difficult; I don't know how to do that, while ensuring efficiency.  The standard data structures don't have a canonical representation: there are many possibilities for the structure of the tree, for any given contents, and they use these degrees of freedom to help make the operations efficient.

But we can still support the "equality-test" operation efficient, without needing a canonical representation.  We'll construct a custom hash function, which produces a hash value $H(f)$ based on the contents of the map $f$ (regardless of the underlying structure of the tree or how the map is stored).  Then we can do efficient equality tests: given two maps, we compare their hashes.  If their hashes are different, we know they are different maps.  If their hashes are the same, we can compare them exhaustively; with a reasonable hash function, the chances of two different maps yielding the same hash will have negligible probability.  If you use a cryptographic-strength hash, that possibility is so exponentially rare that you can use a simpler procedure: if the hashes match, then the maps match, and there's no need to check any further.  This yields a procedure that is $O(1)$ time to compare equality in practice.

So how do we build the hash function $H$?  We'll use an associative hash function.  Let $(G,+)$ be an abelian group, and a conventional hash function $h:\{0,1\}^* \to G$.  Suppose the map $f$ maps the interval $[\ell_i,u_i]$ to the value $v_i$ for $i=1,2,\dots,n$.  Then we'll define the hash of $f$ to be

$$H(f) = \sum_{i=1}^n h(\ell_i,u_i,v_i).$$

Notice that the hash value depends only on the map itself, and not on the structure of the tree used to store the map.

We'll update the hash of the map each time that we update the data structure.  This is easy to do, thanks to the structure of $f$ and the fact that $+$ is commutative (since $G$ is abelian).  If the map $f'$ is defined by removing an interval $[\ell,u] \mapsto v$ from the map $f$, then their hashes are related by

$$H(f') = H(f) - h(\ell,u,v),$$

which can be computed in $O(1)$ time.  Similarly for adding an interval that doesn't overlap any other intervals.  Adding an interval that overlaps an existing interval (triggering a split) can be done by deleting the existing intervals and adding in the new intervals.  Each of these operations takes $O(1)$ time.

(Alternatively, you can choose a non-abelian group $G$ and then augment the binary tree: in each node, you store the hash of the map that corresponds to the subtree rooted at that node.  In this way you can update the hash values for all nodes each time you update the tree.)

It remains to instantiate the hash $H$ by choosing an appropriate group $G$ and an appropriate hash $h$.  I suggest that you use a cryptographic hash function for $h$, such as SHA256; that way  you can treat collisions as effectively impossible in practice.  You can find analysis of how to choose the group $G$ in the cryptographic literature: see https://crypto.stackexchange.com/q/11420/351, https://crypto.stackexchange.com/a/17936/351, and https://crypto.stackexchange.com/q/8615/351.


Is finding arbitrary length cycles in a graph NP-Hard? My intuition says yes. I think so because if we could find arbitrary length cycles, couldn't we just look for an n length cycle and then solve HAM-CYCLE? But I saw a post that seems to suggest a polynomial time method for finding cycles! I feel as if perhaps I do not understand something here.

The algorithms mentioned are all fixed-parameter tractable in the size of the cycle.  This means that if you fix the cycle size $k$, there's a polynomial time algorithm for finding the cycle as the number of vertices or edges increases, but the run time still increases exponentially as $k$ increases.  The big-O notation you're looking at only specifies asymptotic run times as the number of edge and vertices increase, but leaves out the possibly large but constant $k!$ factor.


Why can't every computation be expressed in the style of MapReduce? What are the limitations of map reduce in the sense of the types of computations that they can express? Is Map Reduce "turning complete"?

I have been told that map reduce only works on things that can be expressed in the Map and Reduce framework, but my question is, why can't everything be expressed like that?

This might be the reason why Distributed Shared Memory systems like tread marks or IVY started to exist. So that we could express general programs and deal with them in a distributed computing manner.

Can someone give me an example of a task that can be done in a DMS and one that cannot be in map reduce? Or maybe, is there a formal theorem or proof showing what things can't be done in MapReduce but that a general programing language can do? What are the inherit limitations of Map Reduce and why are they the way it is?

In MapReduce you take a big computation and split it up into many small computations that are done in parallel and that don't depend on one another. That way you can use many cores and if one calculation fails, you don't have to redo the entire job, just that small task.

But if you have a problem that can't be broken down into sub-problems that are independent of one another or dependent on some global state, then you are stuck with doing one long big computation and lose the benefits of MapReduce.


Algorithm for creating n-multiset out of x? I have a problem that can be modelled by 15 undistinguishable balls to 21 boxes. The state of a node is defined by indices from 1 to 21 and corresponding values from 0 to 15, with the constraint that the sum of all values is 15. Those are the nodes of my (sparse) graph, the edges are defined by the rule: diminish the (non-null) value of an index by 1 and add 1 to (index +1). The values are the balls, the indices are the boxes.

Following the twelvefold way, i find that i have to create 15-multisets out of 21 and that there are $\binom{n + x - 1}{k}$ possibilities. In my case, those are 3.2E10 which is small compared to 21 to the 15th power (6.8E20) and can be kept in the memory of my machine.

What i now need is an algorithm for the creation of all nodes. The primitive way would be 15 nested loops counting from 1 to 21, inside of all doing some tests if the node is a permutation of (and so identical with) an already created node, but that would be too time-consuming (6E20 possibilities). Is there a faster way, looking only at the 3E10 "real" states?

Every such arrangement of 15 balls to 21 boxes corresponds, in a one-to-one fashion, to a string of the form *|**||||...|*, where there are a total of 35 symbols in the string, exactly 15 stars and 20 bars.  (Think of each * as a ball, and each | as a divider between two boxes.)  These, in turn, correspond to the set of binary strings of length 35 that contain exactly 20 one's, which in turn corresponds to the set of ways to choose a subset of 20 positions out of a set of 35 possibilities.

It follows that you can enumerate the set of valid nodes by enumerating all ways to choose a subset of size 20 that's contained in $\{1,2,\dots,35\}$.  There are standard ways to perform this enumeration.  One way is to use the combinatorial number system, which creates a correspondence between these subsets and integers in the range $\{1,2,\dots,{35 \choose 20}\}$.  See also https://en.wikipedia.org/wiki/Combination#Enumerating_k-combinations, Get a fixed-size family of k-element subsets, https://cs.stackexchange.com/a/72543/755 for more.


Finite languages $L\in RE$ I want to check if I understood it in the right way.
In some example where $L\in RE$ the explanation deal with 2 cases: 1st when $L$ finite and 2nd when $L$ infinite. In the second case $L\in R$, isn't? Is it possible somehow that $L\in RE\setminus R$ be finite?

The answer is no. Every finite language is regular, and thus decidable. Therefore the existence of a finite language $L$ in $ \text{RE} \setminus \text{R}$ is impossible. However, note that there languages $L$ in $\text{RE}\setminus \text{R}$ (e.g., $Halt_{TM}$), and by what we have seen previously, such languages have to be infinite.


How to prove that a constrained version of 3SAT in which no literal can occur more than once, is solvable in polynomial time? I'm trying to work out an assignment (taken from the book Algorithms - by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani, Chap 8, problem 8.6a), and I'm paraphrasing what it states:

  Given that 3SAT remains NP-complete even when restricted to formulas in which
  each literal appears at most twice, show that if each literal appears at most once, then the problem is solvable in polynomial time.

I attempted to solve this by separating the clauses into multiple groups:

Clauses which did not have any variable in common with the rest of the clauses
Clauses which had only 1 variable in common
Clauses which had 2 variables in common
Clauses which had all 3 variables in common

My reasoning was attempted along the lines that the # of such groups is finite (due to the imposed restriction of no literal being present more than once), and we could try to satisfy the most restricted group first (group 4) and then substitute the result in the lesser restricted groups (3, 2 and then 1), but I realized that this wasn't quite getting me anywhere, as this doesn't differ much from the case for the constrained version of 3SAT in which each literal can appear at most twice, which has been proven to be NP-complete.

I tried searching online for any hints/solutions, but all I could get was this link, in which the stated hint didn't make sufficient sense to me, which I'm reproducing verbatim here:

  Hint: Since each literal appears at most once, convert this problem to 2SAT problem - hence polynomial time, if a literal $x_i$ appears in clause $C_j$ and complement of $x_i$ (i.e., $\overline{x_i}$) in clause $C_k$, construct a new clause clause $C_j \lor \overline{C_k}$.

Both $C_j$ and $C_k$ have three literals each - I didn't get how I should go about converting it into 2SAT by doing $C_j \lor \overline{C_k}$ (or $\overline{C_j \lor C_k}$ if I read it incorrectly).

Any help in either decrypting the hint, or providing a path I can explore would be really appreciated.

Without loss of generality, we can assume that each variables appears exactly once positively and exactly once negatively (if a variable only appears once set its value to satisfy the clause and remove the clause). We can also assume that a variable does not appear in a clause more than once (if a variable appears both positively and negatively in a clause, then the clause is satisfied and can be removed). These will not alter the satisfiability.

Now use the resolution rule to eliminate the variables one by one (since each variable appears exactly once positively and once negatively this is a deterministic process).  If at any point we obtain the empty clause the set of clauses is unsatisfiable, otherwise it is satisfiable. This is because:

resolution is a complete propositional proof system (i.e. if a clause is logically implied by the set of clauses then it is derivable from the set of clauses using only the resolution rule),
a set of clauses is unsatisfiable iff it logically implies the empty clause.

This algorithm will take polynomial time since each variable is resolved exactly once.  In particular, each application of resolution will reduce the total number of clauses by one, so the number of clauses does not increase.  For example, applying resolution to $(x \lor B) \land (\overline{x} \lor C) \land \dots)$ yields $(B \lor C) \land \dots$, which has one fewer clause than before resolution.  In contrast, if you applied this to a 3SAT formula with no restriction on the number of appearances of each literal, applying resolution could cause the number of clauses to increase exponentially.


Complexity of the problem to determine if a spanning tree exists inside a connected graph Given a connected graph G, what is the complexity of the problem to determine if a spanning tree with a number of leaves less or equal to k exists inside G? I don't really know how to determine it and how to reach a proper solution to this.

When $k = 2$, this is just the Hamiltonian path problem, which is known to be NP-complete.


Proving that $\{0^{m^2}\mid m\geq 3\}^*$ is regular We know that $L=\{0^{m^2}\mid m\geq 3 \}$ is not a regular language. However $L^*$ is regular because we can generate $0^{120}$ to $0^{128}$ by some concatenations and then any other power of $0$ can be generated just by concatenating $0^9$. Hence we can represent $L^*$ using a FSM.

My Question :

Here I got these numbers $120$–$128$ for $m^2$ by trial and error. Is there any formal method to arrive at these numbers?
If we consider $m^2$ to be a function such that we get $L^*$ is regular, will it also be regular for $m^3$?

Consider the language
$$
L = \{ 0^{m^k} : m \geq m_0 \}.
$$
Since $m_0$ and $m_0+1$ are relatively prime, so are $m_0^k$ and $(m_0+1)^k$. Hence every large enough integer is a non-negative integer combination of $m_0^k$ and $(m_0+1)^k$, implying that
$$L^* \supseteq \{ 0^m : m \geq M_0 \}$$
for some $M_0$, and so $L^*$ is regular. Using the classical formula of the coin problem applied to $m_0^k$ and $(m_0+1)^k$, we can upper bound the optimal value of $M_0$ by
$$
M_0 \leq (m_0^k-1)((m_0+1)^k-1).
$$
For example, the case considered in your post has $k=2$ and $m_0=3$, and this gives the bound $M_0 \leq (3^2-1)(4^2-1) = 120$, which is (apparently) tight in this case.

Recently it has been shown that it is $\Sigma_2^P$ hard to determine the largest integer which cannot be represented as a non-negative combination of given positive integers (Matsubara 2016), though in your particular case the set $\{ m^k : m \geq m_0 \}$ has a lot of structure, and so the problem might be feasible.


Why separate lexing and parsing? It's possible to parse a document using a single pass from a state machine. What is the benefit of having two passes, ie. having a lexer to convert text to tokens, and having a parser to test production rules on those tokens? Why not have a single pass that applies production rules directly to the text?

You don't have to separate them. People combine them into scannerless parsers.

The key disadvantage of scannerless parsers appears to be that the resulting grammars are rather complicated -- more complicated than the corresponding combination of a regular expression doing lexing and a context-free grammar doing parsing on the token-stream. In particular, grammars for scannerless parsing tend towards ambiguity. It's easier to remove ambiguity for grammars working on a token-stream.

A pragmatic benefit of using a dedicated upfront lexing phase is that you don't couple the subsequent parser with lexical detail. This is useful during early programming language development, when the lexical and syntactic details are still changing frequently.


asymptotic growth of n^log log n I'm ordering functions by their asymptotic growth for an assignment and I have verified I have the correct order by using limits, but I'm trying to understand why $n^{log\ log\ n}$ is between $n^3$ and $2^n$. It seems like it should be closer to the order of $n^n$. Can anyone provide some insight on this.

It could help if you wrote $n^{\log\log n}$ as $2^{\log n\log\log n}$. Then it should be clear that $2^{\log n\log\log n} = o(2^n)$. The morale of this is that the base of an exponent doesn't count as much as the exponent itself.


Maximum Changes that don't Break the Build Let's say I have a set of changes, e.g. replacing foo with bar in a codebase, how do I programmatically discover the largest set of replacements that will not break my tests. let's assume that the call-sites are independent.

I can come up with a binary-search-like algorithm which would be worst case O(n) time. Proposed binary-search-like algorithm:

possible_changes = Set(Range(0, n - 1)) // all callsites
working_changes = Set()

while (possible_changes non empty) {
  for (range in possible_changes) {
    remove the range from possible_changes

    if (range causes failures) {
      if (range size == 1) {
        // forget the range
      } else {
        left, right = split the range
        if (range size == 2) {
          if (left does not cause failure) {
            add left to working_changes
            // forget right
          } else if (right does not cause failure) {
            add right to working changes
          }
        } else {
          add left to possible_changes
          add right to possible_changes
        }
      }
    } else {
      add range to working_changes
    }
  }
}

Is there a faster way, besides above to find all changes that would work?

The problem you're trying to solve is undecidable, since you can't tell if any of the changes makes the program go into an infinite loop.


How can I prove $P \rightarrow (Q \rightarrow R)$ is equivalent to $(P \wedge Q) \rightarrow R$ I'm a freshman CS student at my university and i'm struggling with understanding my professor through his thick accent. I've asked him to explain the proof for this multiple times and still have trouble comprehending what he's trying to tell me.

The question is:

Prove that:  $P\rightarrow(Q\rightarrow R)$ is equivalent to $(P \wedge Q) \rightarrow R$

He wants us to prove it using math and goes on to tell me that $P \rightarrow (Q \rightarrow R) = \neg P \vee (\neg Q \vee R)$

From that point on, I was completely lost and unable to follow along.

You could just construct the truth tables for the two formulas: there are only three variables, so the tables are only eight lines.
Use de Morgan's laws, distributivity and so on to rearrange one formula into the other.
Use similar techniques to show that $[P\rightarrow (Q\rightarrow R)] \leftrightarrow [(P\wedge Q)\to R]$ is equivalent to true.
Use similar techniques to show that $[P\rightarrow (Q\rightarrow R)] \leftrightarrow \neg[(P\wedge Q)\rightarrow R]$ is equivalent to false.
Use one of the various propositional proof systems to accomplish one of 2–4, though that sort of thing will probably come up later in your course.


How to prove a side effect in a function I asked a question earlier about Saving to the Database, which was very general and about the requirements for a proof when you go through many layers of non-verified systems such as the network and databases.

In this question I am wondering about a more middle-level proof, this time about transforming an object $f : A \to B$ with side effect $C$. Say I have as input a string $A$, and as output an Abstract Syntax Tree (AST) $B$. All of this happens in memory with a small string of say a few KB. Right now, ignoring all the details of the hardware implementation and all the details of any particular language.

I am wondering at a high level what it takes to prove something like this. Specifically I wanted to focus on side effects in this question. Say during the parse process, we create a global symbol table to store classes. Then as we are parsing through the code and we encounter the class, we add to the symbol table. So instead of $f : A \to B$, we really have:

\begin{align}
  f : A &\to B\\
  &\downarrow\\
  &C
\end{align}

That is for the symbol table $C$ and AST output $B$. Somewhere in the function $f$ implementation there is another function $g : \{C,c\} \to C'$, which adds the new symbol $c$ to $C$.

What I would like to prove (in this question, just at a high level, some key points) is that the function generates the symbol table $C$, even though the output of the function is the AST $B$. In type theory, the proof for AST $B$ could possibly just be the sequence of type definitions and transformations, similar to Hoare Logic. But to prove that the function $f$ has side effect $C$ seems much harder/trickier.

It seems that you have to go and step through the algorithm one step at a time, and (assuming everything is strongly typed), figure out what the "current state" would look like at that point (of the whole program). Then you would compare your pattern (the assertion of the post-condition if it were Hoare Logic) with the current state of the program at that point, and see if it was a match. And see if that stayed true until the end of the function/algorithm. But this sort of seems like it's becoming Model Checking, which I only know the basics about, not sure if that is correct to assume though. Also, this one-step-at-a-time stepping through the algorithm seems like program simulation, so wondering if that is true or not or if simulation has a role here.

So I'm wondering, at a high level, what is required to prove that function $f$ generates a side effect $C$. As a specification, I would write "$f$ generates the symbol table $C$".

If the function has two outputs, a standard way to represent this is as a function $f: A \to (B \times C)$, i.e., $f$ outputs a pair of an AST and a symbol table.

If the function updates an existing symbol table, you could represent this as a function $f : (A \times C) \to (B \times C)$.  It takes as an input a pair of a string and a symbol table, and outputs a pair of an AST and an updated symbol table.

You could also read about monads, which are a way to structure and reason about side effects in a functional programming language.  They are notoriously challenging to understand.

You don't prove a side effect.  You can prove a fact about the possible side effects, but you need to state what you are claiming; a side effect isn't something that can be proven or not.  Similarly, you don't prove a function.  You can prove the correctness of a function, if you specify what correctness means for that particular function, but you don't prove the function.


Is there any practical trick to mentally count in Gray code? When I was fairly young, I taught myself to count in binary. I thought it would be a fun party trick to impress people. I soon found out that it was not.

Over the years I've come to appreciate Gray code/reflected binary code for its property of only flipping one bit for each increment/decrement of the underlying count. But I've always been bothered by the fact that, if I wanted to mentally take any arbitrary Gray code and add or subtract 1 from it, I'd have to either convert it to and then back from its numeric value, or construct a table to work out what the next code should be.

It seems to me that there should be some trick that a person with "average" short term memory and addition skills should be able to do to take any arbitrary value in Gray code and figure out which bit to flip to get the next value... But I've never found it.

Does such a thing exist?

I have a solution that I just found looking at the patterns, and I checked the pattern up to decimal 31 or binary 11111 or Gray 10000, and it worked quite fine, and I am confident enough the answer will carry through larger values too.
Take a Gray code, and count the number of 1's:
Case I:
Odd number of 1's: flip the bit one position before the last '1'.
Case II:
Even number of 1's: flip the last bit.
Examples:

Even case:
After 10100101, the next one is 10100100.

Explanation: there are 4 1's so we apply the even case, i.e., flip the last bit.

After 111011010, the next one is 111011011.

Explanation: there are 6 1's so we again flip the last bit.

Odd case:
After 110111, the next one is 110101.

Explanation: there are 5 1's so we apply the odd case, i.e., flip the bit that lies before the last '1'.

After 1100100, the next one is 1101100.

Explanation: there are 3 1's so we apply the odd case, i.e., flip the bit that lies before the last '1'.
I hope this helps!


If A is reducible to its complement, is the converse true as well? I was reading a proof that said that if $A \le_{m} \bar{A}$, then it can be inferred that $\bar{A} \le_{m} A$ as well. Is this a logical conclusion, and if so, why? I didn't think this followed with languages A and B, but if B is A's complement, can one make such a statement?

In general whenever $A\le_m B$ via computable function $f$, we automatically have $\bar{A}\le_m \bar{B}$ via the same $f$. The reason is that $x\in A\iff f(x) \in B$ implies that $x \in \bar{A} \iff f(x) \in \bar{B}$.


Distinguishing between uppercase and lowercase letters in the "move-to-front" method Is it not necessary to encode both the uppercase and lowercase letter while encoding a message with the move-to-front transform? From an old computer science course exam, the problem was to encode Matt_ate_the_mat starting with an empty list.

Using the author's solution methodology of not taking into account M versus m one arrives at

$C(1)C^∗(M)\\
C(2)C^∗(a)\\
C(3)C^∗(t)\\
C(1)\\
C(4)C^∗(\_)\\
C(3)\\
C(3)\\
C(5)C^∗(e)\\
C(4)\\
C(3)\\
C(6)C^∗(h)\\
C(4)\\
C(4)\\
C(6)\\
C(6)\\
C(6)$

Seeing that move-to-front works best with items that are repeated this works to one advantage as long as the difference between M and m in the original message is not important, correct?

Though would it not change the last encodings if taking into account m to $C(7)C^*(m)$ or was this done for the sake of brevity within the exam?

Though for us, human beings, m and M are the same, for a computer these are two distinct symbols that have no relation whatsoever.

The answer actually depends on the application:

If your application is not case-sensitive, this separation does not matter, and the encoding is correct.
If the application is case-sensitive there must be a distinction between lower case and upper case.

It seems to me that the encoding is more efficient as the number of symbols is smaller, thus maybe it is better to encode upper and lower case as an additional bit rather than having the list to contain 26x2 symbols, but this depends on the distribution of the text you are encoding.


Diameters of isomorphic graphs Is it necessary that two isomorphic graphs must have the same diameter? As far as I know, their adjacency matrix must be retained, and if they have the same adjacency matrix representation, does that imply that they should also have the same diameter?

A graph property is an isomorphism-invariant property of graphs. That is, $P$ is a graph property if $P(G_1) \leftrightarrow P(G_2)$ whenever $G_1$ and $G_2$ are isomorphic.
Any property of graphs which doesn't refer to specific names of vertices is a graph property. This includes all the usual properties of graphs: connectivity, diameter (that is, the property of having diameter $D$), chromatic number (that is, the property of having chromatic number $\chi$), and so on. A property of graphs which is not a graph property is: "vertices 1 and 2 are connected".
Let us show that connectivity is a graph property. In the same way, you can show that diameter is one. Let $G_1=(V_1,E_1)$ and $G_2=(V_2,E_2)$ be two isomorphic graphs. This means that there is a bijection $\phi\colon V_1 \to V_2$ such that $(x,y) \in E_1$ iff $(\phi(x),\phi(y)) \in E_2$. We will show that if $G_1$ is connected then $G_2$ is also connected. The same argument (using $\phi^{-1}$) will show the converse, completing the proof.
Suppose that $G_1$ is connected, and let $a,b \in V_2$. Since $G_1$ is connected, there is a path in $G_1$ between $\phi^{-1}(a)$ and $\phi^{-1}(b)$, say $\phi^{-1}(a),v_1,\ldots,v_\ell,\phi^{-1}(b)$. Then $a,\phi(v_1),\ldots,\phi(v_\ell),b$ is a path in $G_2$ connecting $a$ and $b$.


Which binary search trees have constant time rebalancing time at min/max? Given that I'm already at either the min or the max node of a binary search tree, which balanced variant would require only constant time bottom-up rebalancing after an update (add new min/max, or remove current)?

Consider a constant set of $k$ insertions done directly at the max node, and the left and right sub-trees of the root node ($L$, $R$). If each rebalancing operation required only constant time, then only $O(\frac{log(n)}{k})$ of the inserted elements could be in $L$, since the maximal element is a leaf and the tree is balanced.

While this simple analysis is incorrect for non-constant $k$, the intuition still holds - if rebalancing after max (/min) insertion was always constant, repeated max (/min) insertions would cause $R$ (/$L$) to grow larger, and the tree could not be balanced.


Computing Cardinality of Sumsets using Convolutions and FFT I read somewhere that you can compute the cardinality of sumsets by computing the convolutions of the characteristic vectors of the given sets, and that this can be done efficiently using Fast Fourier Transform. How would this work?

Here is a sketch of the main ideas.  Let $S,T \subseteq \mathbb{N}$ be two multisets of non-negative integers, and define $S+T$ to be the multiset

$$S+T = \{s+t \mid s \in S, t \in T\}.$$

Let $\chi_S$ represent the characteristic vector of a set $S$.  Then

$$\chi_{S+T} = \chi_S * \chi_T,$$

where $*$ is a convolution operator.

The Fourier transform $\mathcal{F}$ has the property that

$$\mathcal{F}(f*g) = \mathcal{F}(f) \times \mathcal{F}(g),$$

where $\times$ represents pointwise multiplication of functions.  Therefore,

$$\mathcal{F}(\chi_{S+T}) = \mathcal{F}(\chi_S) \times \mathcal{F}(\chi_T),$$

and in particular,

$$\chi_{S+T} = \mathcal{F}^{-1}(\mathcal{F}(\chi_S) \times \mathcal{F}(\chi_T)).$$

This gives us a method to compute $S+T$.  We can compute the characteristic vector $\chi_{S+T}$ for the multiset $S+T$ by computing $\mathcal{F}(\chi_S)$, the Fourier transform of the characteristic vector for $S$, and $\mathcal{F}(g)$; multiplying them; and then applying the inverse Fourier transform to the result.  Each of these steps can be implemented efficiently using the Fast Fourier transform.  The end result will be $\chi_{S+T}$, from which we can reconstruct $S+T$ or its cardinality.

The overall running time will be $O(n \log n)$, where $n$ is an upper bound on the largest element of $S,T$.


Is log(n) equivalent to (log(n))^x for big-O analysis? My professor noted that we could treat any logarithmic function with an exponent as equivalent to log(n) for the purposes of big-O analysis.

ie. $(n log(n) + 1)^2 + (log(n) + 1)(n^2 + 1)$

From the left I would get $(n^2)(log(n))^2$ and from the right I would get $(n^2)log(n)$. According to my professor I can just say this function is $O(n^2log(n))$. However, I don't see how these functions grow in the same order. Looking at their graphs it would seem they are quite different.

$f(n)$ is not $O(n^2\log n)$

If we denote $f(n) = (n\log n+1)^2+(log n+1)(n^2+1)$
then:
$$f(n) = n^2 \log^2n + 2n\log n + 1 + n^2\log n + n^2 + \log n + 1 \geq n^2log^2n$$

since all the other terms are obviously greater than 0. Therefore by definition $f(n) = \Omega (n^2log^2n)$. Which strictly means it cannot be bounded from above by anything asymptotically greater.

Note that it also holds that $f(n) \leq 10n^2log^2n$, so $f(n) = O(n^2log^2n)$ and also $\Theta$ of the same.


How to find witnesses for big O I'm having trouble determining the correct way (if there is one) to find the witnesses in any given big O problem.

The example I'm struggling with:
$2^x + 17$ is $O(3^x)$.

I am expected to find two witnesses such that $2^x + 17 \leq C(3^x)$ whenever $x > k$.

Unfortunately, my textbook isn't very clear on how to actually find them and rather suggests to more or less guess until you get both constants to work. It is to my understanding that if one pair exists, infinitely many do.

How do you find these?

In your case finding the witness is easy. We know that for all $x \geq 0$, $2^x \leq 3^x$. Also, for $x \geq 3$, $17 \leq 3^x$. So for $x \geq 3$, $2^x+17 \leq 2\cdot 3^x$.

There is no particular method at work here – just problem solving.


generation-compare-and-swap, or GCAS, in CTries The data structure is used for example in Scala:
https://github.com/scala/scala/blob/v2.12.0-M3/src/library/scala/collection/concurrent/TrieMap.scala

More details in this paper:
http://lampwww.epfl.ch/~prokopec/ctries-snapshot.pdf

The logic I'm confused about is on line 139 in Figure 11 on page 6 of ctries-snapshot.pdf

The code checks if the generation of the root node is the same as the current node before proceeding. To quote the paper,

  The idea is to communicate the intent of replacing the value in the
  I-node and check the generation field in the root before committing
  to the new value

This is the last sentence of the second paragraph in section 4.1 on page 6. The root generation is changed for example when a snapshot is taken (Figure 7 on page 15).

The question is, I don't see any synchronization mechanism that would prevent updates to the root right after the generation check. To use the papers own words, how is "the intent of replacing the value in the I-node" communicated to other threads attempting to update the root node through snapshots? From what I can tell, the root and the I-node in question can be two distinct nodes, and I'm not sure how the CAS's surrounding the generation check can prevent a race.

Nice observation.

To prevent the scenario that you are describing, the actual implementation in the Scala standard library uses a variant of the software RDCSS instruction when reading or modifying the root. Any modification of the root is only successful if the value below the main I-node did not change.

All reads of the root location are in the actual code calls to RDCSS_READ_ROOT:

https://github.com/scala/scala/blob/2.12.x/src/library/scala/collection/concurrent/TrieMap.scala#L694

And all CASes to the root are similarly replaced with an RDCSS. More details about this instruction in this paper:

https://timharris.uk/papers/2002-disc.pdf

I guess this important detail that you noticed (and in fact, you are maybe even the first person to notice so far, besides myself) was left out of the paper to keep the text clear.


"Any problem whose domain is finite is always Decidable", is true or false? Question no:$1$

  "Any problem whose domain is finite is always Decidable"

lets take a TM,$M$ and finite domain of problem i.e. finite set of strings for eg.  {$a,abaa,bba$}, Now the problem "whether $M$ accepts these set of strings or not is decidable or not?"

What I think is, this is Undecidable problem because, if $M$ loops forever any of these string then we not determine whether turing machine accept it or not.so according to this logic above statement is false.

Question no:$2$

Does a single instance of "turing machine's halting problem" is decidable?
As I given above example, I think this is also Undecidable.

It's not so clear what is "a problem whose domain is finite". Let me assume that what is meant by this is a finite language. Every finite language is decidable. The Turing machine compares the input to each word in the language, accepts if it finds a match, and rejects otherwise.

This answers your first question. Your second question is a special case of the first one.


Simply Typed Combinatory Logic? As there is an untyped lambda calculus, and a simply-typed lambda calculus (as described, for example, in Benjamin Pierce's book Types and Programming Languages), is there a simply-typed combinatory logic?

For example, it would seem that natural types for the combinators S, K, and I would be

S : (a -> b -> c) -> (a -> b) -> a -> c
K : a -> b -> a
I : a -> a

where a, b, and c are type variables ranging over some set of types T.  Now, perhaps we could get started with a single base type, Bool.  Our set of types T is then Bool along with whatever types can be formed using the three patterns

(a -> b -> c) -> (a -> b) -> a -> c
a -> b -> a
a -> a

where a, b, c in T.

There would be two new constants in the language.

T : Bool
F : Bool

So, this language consists of the symbols S, K, I, T, and F, along with parentheses.  It has one base type Bool, and the "function types" that can be made from the S, K, and I combinator patterns.

Can this system be made to work?  For example, is there a well-typed if-then-else construction that can be formed from only S, K, I, T, F?

Quick note, I allow parametric polymorphism (System F) in this system so that S, K and I can work over all types.

Notice that without pattern matching, we can't write an if no matter what we do. We have absolutely no operations on booleans. There is no way to distinguish True from False. Instead try

true : a -> a -> a
true = \t -> \f -> t

false : a -> a -> a
false = \t -> \f -> f

Let's let Bool = a -> a -> a for clarity.

 if : Bool -> a -> a -> a
 if = \bool -> \a -> \b -> bool a b

Now it's just a matter of compiling some lambda calculus expressions to combinators, which is pretty trivial.

if : Bool -> a -> a -> a -- Or just Bool -> Bool
if    = I

true : a -> a -> a
true  = K

false : a -> a -> a
false = K I


What happens when time slices are too short or too long? What bad things can occur when the lengths of the time slices in a multitasking system are too small? What can happen when they are too big?  How should the length of the time slice be chosen?

A context switch between two tasks takes a certain amount of time. Let's say that there are two runnable tasks on a particular system. Each context switch will take about the same time, say 0.1ms. If there is a context switch every 10ms, then each task is left to run for 9.9ms, then out of every 1ms period, 99% is spent running the tasks and 1% is spent in context switches. If we increase the frequency of context switching to be every 1ms, then context switches waste 10% of the time. In the extreme case, if we increase again to have a context switch every 0.1ms, then the whole processor time is spent in context switches, there is no time left to run the applications.

Thus, for performance, it is best to have context switches as rarely as possible. This increases the time that is available to actually run applications. However, if context switches are too rare, then there is a delay before an application can react to an external event. This is not a problem for a purely computational program, but it is a problem for a program that does input/output. For example, the frequency of context switches is only once per second, then computational tasks don't waste time, but a network server may take up to one second to reply (or more if there are more than two tasks), an interactive program may take up to one second to react to a keypress, etc.

Thus the operating system scheduler must find a balance between computational performance and reactivity. Sophisticated schedulers try to find out which tasks are computational and which ones are I/O-bound, and give I/O-bound tasks shorter but more frequent time slices and give computational tasks longer but less frequent time slices.


Making a CFG for a^i b^j c^k such that i+k < 3j I have the language $L = \{ a^ib^jc^k \mid i + k < 3j \}$, however I am struggling to convert it to a CFG.

I have thought about solving this for a long time but but this still hasn't gotten me very far

Any help would be appreciated Thanks

$$
\begin{align*}
S \to & AbBC \mid AbBCc \mid AbBCcc \; \mid \\
& aAbBC \mid aAbBCc  \mid aAbbBCcc  \; \mid \\
& aaAbBC \mid aaAbbBCc \mid aaAbbBCcc \\
B \to & bB \mid \epsilon \\
A \to & aaaAb \mid \epsilon \\
C \to & bCccc \mid \epsilon
\end{align*}
$$

The intuition is as follows:

The nonterminal $B$ encodes the fact that we can have any number (possibly 0) of extra occurrences of $b$s in addition to those strictly needed to satisfy $i+k < 3j$.

For every $3$ occurences of a $a$s or $c$s we have to "pay" by adding one $b$ to our word.
The nonterminal $A$ (resp. $C$) represents a triplet of $a$s (resp. $c$s) along with the occurrence of $b$ that is used to "pay" for the triplet.

Clearly, our word might have a number of $a$s (resp. $c$s) that is not a multiple of $3$, however there are only $9$ possible cases for the combinations of the remainders $i \bmod 3$ and $k \bmod 3$.
These cases are explicitly handled in productions from the axiom $S$, in which we make sure to add at least $\left\lceil 1+\frac{(i \bmod 3) + (k \bmod 3)}{3} \right\rceil$ additional "b"s to "pay" for the $(i \bmod 3) + (k \bmod 3)$ extra characters (the $+1$ ensures that the "greater than" in the inequality $i+k < 3j$ is satisfied).


What can this circuit be useful for? I have calculated the boolean functions for $r$ and $f$:
$f = \overline{s_1} \cdot s_0 + s_1 \cdot \overline{s_0}$.
$r = \overline{s_0 \cdot s_1 \cdot s_2 \cdot s_3}$.
Do you have an idea what an application for this circuit can be? I don't know where we would use it.

Good Question. It looks like some kind of ripple counter.  It repeats after 15 steps. Values (consider the outputs to be 8,4,2,1) as 8,4,2,9,12,6,11,5,10,13,14,15,7,3,1.
Zero only for one step after reset, not repeated.


Finding alternative way of combinatorial counting The question is related to databases:

  There is a relation $R(A_1,A_2,...,A_n)$. Every $(n-2)$ attributes of $R$ forms candidate key. Number of superkeys of $R$ are?

I thought if any one of the $(n-2)$ attribute combinations is chosen then the number of superkeys that can be formed with it will be 4, as there will be $2^2$ combinations of remaining two attributes. So I gave answer $nC_{n-2}\times 2^2$.

But then the answer given was $nC_{n-2} + nC_{n-1}+ nC_{n}$ which is also quite obvious. But then I realized that my solution does not equate to this one and that my solution count certain superkeys more than once.

However I am not able to form an equation of the count of those duplicate superkeys so that I can subtract it from $nC_{n-2}\times 2^2$ in order to get another expression for the solution (somewhat inclusion-exclusion approach). What is that expression/equation which counts those duplicate superkeys?

The correct answer can be rewritten as $\frac{n(n-1)}{2} + n + 1$.

Let's call the two remaining attributes $A_k$and $A_l$.

You are counting each combination of $nC_{n-2}$ candidate keys four times: (1) when they are alone, (2) when they are with $A_k$, (3) when they are with $A_l$, (4) when they are with both $A_k$ and $A_l$.

Your formula then boils down to the following sum:

$nC_{n-2} + nC_{n-2} + nC_{n-2} + nC_{n-2}$

The problem is that you are counting each combination in case (2) an excessive number of times, because each $A_k$ appears in $n-2$ additional identical combinations, when it is taken as a part of the candidate key. The same is true for case (3).

There is just one singular combination in case (4), the one with all attributes.

The corrected version of you formula is then:

$nC_{n-2} + \frac{nC_{n-2}}{n-1} + \frac{nC_{n-2}}{n-1} + \frac{nC_{n-2}}{nC_{n-2}}=\frac{n(n-1)}{2} + \frac{n}{2} + \frac{n}{2} + 1=\frac{n(n-1)}{2} + n + 1$


Definition of $\alpha$-approximation I know this question is trivial. But I am looking for a concise formal definition of $\alpha$-approximation.

Is it correct to say that "An algorithm is an $\alpha$-approximation to problem $X$, if for any instance of problem $X$ the solution returned by this algorithm is within a factor $\alpha$ of the optimal solution"?

Any correction on the above definition is welcomed.

There are actually two main types of approximation algorithms: those that return an approximate solution, and those that return the approximate value. In order to explain the difference, let me define the problem more formally. Below everything is stated for minimization problems. It is a simple exercise to generalize everything for maximization problems.

Let me stress that the definitions below are not standard; in fact, there is no standard agreed-upon definition. However, it can be taken as a formal definition without too many complaints from the community, if you find this kind of definition enlightening.

Definition: A minimization problem consists of a tuple $\mathcal{O},\mathcal{S},v$ such that:

$\mathcal{O}$ is the set of instances.
$\mathcal{S}$ is the set of solutions.
$v$ is a function from $\mathcal{O} \times \mathcal{S}$ to $\mathbb{R}_+ \cup \{\infty\}$ (the non-negative reals together with positive infinity) such that for every $o \in \mathcal{O}$ there exists $s \in \mathcal{S}$ such that $v(o,s) < \infty$.

We define $v^*(o) = \inf_{s \in \mathcal{S}} v(o,s)$.

The function $v$ is the value of the given solution for a given instance. The optimal value for the instance is $v^*(o)$. If $v(o,s) = \infty$ then we say that the solution is infeasible for the instance.

(Alternatively, we could have a function $f\colon \mathcal{O} \to 2^{\mathcal{S}} \setminus \{\emptyset\}$ giving the (non-empty) set of feasible solutions, and then $v$ is a partial function $\mathcal{O} \times \mathcal{S} \to \mathbb{R}_+$ such that $v(o,s)$ is defined iff $s \in f(o)$.)

Definition: An $\alpha$-approximation algorithm is an algorithm $A\colon \mathcal{O} \to \mathcal{S}$ that satisfies the following property:

  For all $o \in \mathcal{O}$, $v(o,A(o)) \leq \alpha v^*(o)$.

If $\alpha = 1$, then the algorithm finds an optimal solution.

We are usually interested in polynomial time approximation algorithms. In this case we have to fix an encoding for $\mathcal{O}$ and $\mathcal{S}$, that is, we should treat $\mathcal{O},\mathcal{S}$ not as abstract sets but rather as sets of strings.

Definition: A weak $\alpha$-approximation algorithm (non-standard terminology) is an algorithm $B\colon \mathcal{O} \to \mathbb{R}_+$ such that:

  For all $o \in \mathcal{O}$, $v^*(o) \leq B(o) \leq \alpha v^*(o)$.

Once again, we are usually interested in polynomial time algorithms. Given an $\alpha$-approximation algorithm $A$, we can construct a weak $\alpha$-approximation algorithm $B$ using $B(o) = v(o,A(o))$ (this works assuming $v$ is computable). In many specific case we can also go in the other direction.

In some cases (especially hardness of approximation proofs), when the phrase "$\alpha$-approximation algorithm" has the weaker meaning given in the latter definition.


What's the highest 'order' data structure Not sure exactly how to define this but here's the basis of the question (very loosely)

All lists can be contained in tree's
all trees can be contained in a graph
all graphs can be contained in a multi graph,
and all multigraphs can be contained in a hypergraph (never actually heard of a hypergraph before searching for an answer to this, so may not have it quite right)

So there's a containment hierarchy of 'complexity' of data structures. Is Hypergraph the highest one, is there a proof of this, and is there a name for the study of whatever this is.

By highest one, I mean all structures can be represented as a hypergraph if I chose to. So in any code I could represent all the structures by using a number of hypergraphs (not that I would). tia

[Update] Perhaps an alternative way to ask it is, for any arrangement of data structures consisting of nodes and edges. Does there exist a structure that can't be contained in a hypergraph.

Then there is a second question - is there any data structure which can't be represented using nodes and edges.

Perhaps this is an interesting question with explicit answers, but you probably really have a problem with "exactly how to define this".

A list does not directly corresponds to a unique data structure, nor does a tree. A singly linked list corresponds to a (sufficiently unique) data structure, as does a binary tree. When you say multi graph, you probably want to refer to a quiver, i.e. a directed multigraph (edges with own identity). A binary or ternary quiver would again correspond to a (sufficiently unique) data structure.

However, any sufficiently canonical (and efficient) realization of a (n-ary) quiver as a data structure would probably not match well with the way datatypes are handled in "common" programming languages, where the size of an object with a certain datatype shouldn't depend on the actual content of that object. Therefore, this would be the point at which I would stop to look for a higher order data structure (than a quiver, looking for function like data structures and continuations certainly is useful). My reason for this is that I don't see the practical usefulness of a higher order data structure if it cannot be realized efficiently within "common" programming languages.


simple lower bound for constructing a Spanning tree i have to demonstrate that under the assumptions{Bidirectional Links, Total Reliability (no error during the execution), Connectivity, Distincts ids values, Multiple inititators (entities that starts the algorithm} the problems of constructing a spanning tree takes at least $\Omega(m)$ messages, where $m=|E|$

i tried to solve this problem in this way:

Assume that there exists a correct SPT protocol $A$ thatuses fewer than $m$ messages. This means that there is at least one link in $G$ where no message is transmitted.
Consider an execution of the algorithm on $G$, and let $e = (x, y) \in E$ be
the link where no message is transmitted by $A$.

Now construct a new graph $G^{'}$  from $G$
by removing the edge $e$ and adding a new node $z$ and two new edges $e1 = (x, z)$ and
$e2 = (y, z)$. Set $z$ in a noninitiator status ($z$ does not starts the execution of the algorithm). Run exactly the same execution
of $A$ on the new graph $G$   : since no message was sent along $(x,y)$ in the original execution in $G$, $x$ and $y$ never send a message to $z$ in the current execution in $G^{'}$   ; and since $z$ is not an initiator and does not receive any message, it will not send any message.

At the end of the alghoritm a tree $T$ should have been constructed,
however, $z$ is not part of $T$, and hence $T$ does not span $G$.

in other words $A$ works only if $z$  is in a initiator status, therefore $A$ is not correct.


Prove that the Kolmogorov complexity function cannot be approached from below How would one go about proving that Kolmogorov function $K(x)$ cannot be approached from below by any computable function?

After some research it seems I must show the function $K(x)$ is not lower semi-computable.

Instead, I can do this by showing $-K(x)$ is not upper semi-computable

Intuitively it seems that $K(x)$, the length of the smallest program computing $x$, can always get smaller, but could be approached using a convergent function... but this is clearly not the case, so I'm obviously a bit lost.

I would be very grateful if someone could explain how I might approach such a proof. I'm more interested in the approach, I might encounter similar questions in an upcoming exam.

Thanks a lot.

We can computably approach $K(x)$ from above by trying all programs. Since $K(x)$ is not computable, we cannot computably approach it from below — otherwise it would have been computable.


How to find MST for each source Let's say I have a map with factories and selling points. I want to trace the paths from factories to the selling points with the lower possible cost.
The image bellow is an example of a possible solution for that map, then the output of the algorithm should be two trees with the edges of those trees.

If there is only one factory a possible solution would be using Kruskal's algorithm to find the MST with this factory as source.

¿Is there any algorithm to do so? ¿How would a modification of Kruskal's work?

[EDIT]
I need to find the minimum cost tree from factories to shops but given that there is more than one factory may have unconnected trees as optimal solution.

[EDIT 2]
If an edge is used twice that cost counts only once.

Here is a slight modification of Kruskal's algorithm which can solve this.

Sort all edges by non-decreasing weight.
Maintain a disjoint set union to track which vertices are connected, as usual.
Consider the edges one by one in the resulting order.
If an edge connects two vertices which are already connected, we drop it, as usual.

The difference is as follows: if an edge connects two components such that each already contains a factory, such edge would contribute nothing to our network, so we also drop it.

If an edge connects two components, and at least one of them does not contain a factory, we take the edge and update the disjoint set union, as usual.

Another view with the same result is as follows.
Make an auxiliary vertex, the super-factory.
Add an edge of weight 0 from the super-factory to each of the real factories.
Run Kruskal algorithm on this new graph.

First thing, it will take all our added edges with weight 0.
If the original graph also had such edges, let the algorithm start with our newly added edges. We can do it since the total cost does not depend on the ordering of same-weight edges.

Now, the original condition “each shop must be connected to a factory” got translated to “each shop must be connected to the super-factory”, which is equivalent to just “all vertices must be connected”, which in turn is exactly what Kruskal algorithm will do for us.


How to prove Q1 and Q2 are equal using state equivalence algorithm I was applying state equivalence algorithm in this diagram.
On input a and b Q1 and Q2 are going to different states. Which implies the states are not equal according to the state equivalence algorithm. But they are equal and we knows that , right ? Where am I going wrong ? Please help me how to prove these state are equal using state equivalence algorithm

The algorithm is working fine on this DFA. At step 2 you'll get the table as:

  1 2
1 G G
2   G

G is green.

If there is an unmarked pair (Qi, Qj), mark it if the pair {δ(Qi, A), δ (Qj, A)} is marked for some input alphabet. Where A is set of all inputs.

{δ(1, 'a'), δ(2, 'a')} = {2,1} = {1,2}
{δ(1, 'b'), δ(2, 'b')} = {1,2}

{1,2} or {2,1} is not marked. Hence move to step 4, Combine all the unmarked pair (Qi, Qj) and make them a single state in the reduced DFA.

I prefer the method of partitioning for minimizing the DFA. Consider the following DFA
State transition table for the DFA will be:

   0  1
a  b  c
b  a  d
c  e  f
d  e  f
e  e  f
f  f  f

Draw 0 equivalent partitions, by separating final and non-final states in different sets.
[a b f] [c d e]
Draw 1 equivalent partitions, by taking every possible pair from each set and checking whether their transitions on an input symbol belongs to a single set or not. For example {a,b} on 0 goes to {a,b} and it belongs to a single set [a b f], {a,b} on 1 goes to {c,d} which belongs to 1 single set [c d e], hence {a,b} are 1 equivalent. But {a,f} on 1 goes to {c,f} and it doesn't belong to a single set, hence they are not equivalent. So separate them. (you can check for {b,f},{c,d},{c,e},{d,e} as well, result will be the same)
[a b] [f] [c d e]
Draw 2 equivalent partitions, by repeating the procedure and you'll find nothing is changed. Hence final configuration is reached.
Merge [a b] and [c d e]

In your example: 0 equivalent partitions: [q1 q2] 1 equivalent partitions: [q1 q2]

Hence they are combined.


Finding all rows of 2 variables using Gaussian Elimination Suppose I have a system of linear equations. Using Gaussian elimination, I can determine whether a solution exists, and even find a valid solution.

During the elimination, I can combine rows together, to produce new rows with different number of variables. Is there a method to find all possible rows that contain exactly 2 variables? For example, I may want to find all equalities between variables. This is equivalent to finding all rows that contain exactly 2 variables. Is it possible to do this without trying all (exponentially many) combinations of rows?

For example if I have:

Row 1: A xor B xor C = 1

Row 2: A xor B xor D = 1

I can combine row 1 and row 2 to say that C xor D = 0

If I have a large amount of rows, and they require large combinations of large rows to produce smaller rows, is it trivial or hard to find all rows of size 2? Can I do better than adding random pairs to the system and checking it still has a solution?

If I understand you correctly, you have a matrix $M$ over $GF(2)$ (the field with two elements), and want to find all linear combinations of rows which have weight exactly $2$.

Using Gaussian elimination, you can bring your matrix into echelon form. This makes it easy to determine, for any particular row, whether it is in the span of the rows of $M$. Since there are only $\binom{n}{2}$ many rows of weight $2$, the entire algorithm will run in polynomial time. (It is likely that this can be optimized further.)


How to find the Branch factor of 8 Puzzle I would like to know how to find the average branching factor for 8 puzzle.While referring Artificial Intelligence by George F Luger it says that:

  Suppose,for example we wish to establish the branching factor of the 8-puzzle.We calculate the total number of possible moves: 2 from each corner for a total of 8 corner moves,3 from center of each side for a total of 12, and 4 from the center of the grid for a grand total of 24.This divided by 9,the different possible locations of the blank, gives an average branching factor of 2.67.

Why do we have to divide by 9(possible locations of the blank space) to get the average branching factor.I'm confused with how the blank space affects the branching factor?

The relevance of the blank space is that a move is encoded by the transition of the blank space.  So for example, if the blank space is in the center we have 4 possible moves:

This is what the author is talking about when he says

  "2 from each corner for a total of 8 corner moves."

The blank space is what's in the corner. Here's one of the 4 possible corner positions:

As you can see, when the blank space is in the corner there are two possible transitions.

Continuing,

  "3 from center of each side for a total of 12"

There are 4 centers of a side and each has 3 possible transitions.

I hope this combined with Jeffrey's weighted average explanation answers the question.


Show $x^y$ is a primitive recursive function As this thread title gives away I need to prove $x^y$ to be a primitive recursive function.

So mathematically speaking, I think the following are the recursion equations, well aware that I am assigning to $0^0$ the value $1$, which shouldn't be, since it is an "indeterminate" form.

\begin{cases}
  x^0=1 \\
  x^{n+1} = x^n\cdot x
\end{cases}

More formally I would write:
\begin{cases}
  h(0) = 1 \\
  h(x,y+1) = g(y,h(x,x),x)
\end{cases}

as $g(x_1, x_2, x_3) = h\left(u^3_2(x_1, x_2, x_3),u^3_3(x_1, x_2, x_3)\right)$ and provided $h(x,y) = x \cdot y$ is primitive recursive.

Is my proof acceptable? Am I correct, am I missing something or am I doing anything wrong?

As I wrote in the comments, you haven't actually proved anything.  If you want to prove that $x^y$ is p.r., you need to write it in the scheme form, and then you need to prove that indeed $x^y = f(y,x)$ for your defined $f$ for all $x$ and $y$ (by double induction).

Consider the following definition of $f(y,x) = x^y$:

$f(0,x) = s(z(x))$ (i.e., the successor of the constant zero function).

$f(y+1, x) = u^3_1(u^3_1(x^y, x, y) \cdot x, x, y)$.

I assume now that multiplication, $x \cdot y$ and wrote it infix, and obviously $x^y = f(y,x)$.  The function $u^a_b$ is the $a$-ary projection of $b$.

(Ps. if this doesn't work for you, please post your scheme you want to use, otherwise we cannot do else then guess.)


Extended version of the theory of reals and its decidability It is well-known due to Tarski that the theory of reals $(\mathbb{R},+,\cdot,<,=)$ is decidable. I was asking my self whether one would lose the decidability by adding all real constants. More formally, is the theory $(\mathbb{R},\{\underline{r} \mid r \in \mathbb{R}\} +,\cdot,<,=)$ evaluated in the standard model of the reals decidable? Here, the symbol $\underline{r}$ is such that its interpretation in the standard model is exactly the real $r$.

I guess that the extended version is still decidable, essentially because two reals are different if and only if there exists a rational number between them. Rationals, on the other hand, can be expressed in the usual Tarski fragment.

Can anyone help?

Turing machines, in the classical sense, decide languages of finite strings over finite alphabets. Your logical language has uncountably many constant symbols so you can't even write down all the formulas as strings, let alone ask a Turing machine to decide things about the collection of formulas.


Number of calls with length 2 array in quick-sort I need to find average number of recursive calls in quick-sort with array of length 2. I established and solved the following recursion:

$$T_N = \frac{1}{N}\sum_{k=1}^N\left(T_{k-1}+N_{N-k}\right) = \frac{N+1}{N}T_{N-1} = \frac{N+1}{3}.$$

Where $T_0 = T_1 = 0, T_2 = 1$. But:

\begin{align*}
T_3 &= 1/3(1 + 1) &= 2/3\\
T_4 &= 1/4(2/3 + 1 + 1 + 2/3) &= 5/6\\
T_5 &= 1/5 (5/4 + 2/3 + 2 + 2/3 + 5/4) &= 7/6\\
T_6 &= 1/6(7/6 + 5/6 + (1+2/3) + (1+2/3) + 5/6 + 7/6) &= 11/9
\end{align*}

The results are different. How to do it right?

EDIT: The code for quick-sort in question is:

void quicksort(int[] a, int lo, int hi)
{
  if (hi <= lo) return;
  int i = lo-1, j = hi;
  int t, v = a[hi];
  while (true) {
    while (a[++i] < v) ;
    while (v < a[--j]) if (j == lo) break;
    if (i >= j) break;
    t = a[i]; a[i] = a[j]; a[j] = t;
  }
  t = a[i]; a[i] = a[hi]; a[hi] = t;
  quicksort(a, lo, i-1);
  quicksort(a, i+1, hi);
}

First, note that you can write your recurrence as
$$
T_N = \frac{2}{N}\sum_{i=0}^{N-1} T_i.
$$
Consider now the generating function
$$
T(x) = \sum_{N=0}^\infty T_N x^N.
$$
We calculate
$$
\frac{T(x)}{1-x} = \sum_{N=0}^\infty \sum_{i=0}^N T_i x^N =
\frac{1}{2} \sum_{N=2}^\infty (N+1)T_{N+1}x^N = \frac{1}{2} \sum_{N=3}^\infty NT_Nx^{N-1}.
$$
On the other hand,
$$
\frac{d}{dx} T(x) = \sum_{N=0}^\infty NT_Nx^{n-1}.
$$
We conclude that $T(x)$ satisfies the differential equation
$$
\frac{d}{dx} T(x) = \frac{2T(x)}{1-x} + 2x.
$$
Additionally, $T(0) = 0$. Plugging this into Wolfram alpha, we obtain the solution
$$
T(x) = \frac{x^2(3x^2-8x+6)}{6(1-x)^2}.
$$
Using $1/(1-x)^2 = \sum_{N=0}^\infty (N+1)x^N$, we obtain for $N \geq 3$ that
$$
T_N = \frac{6(N-1)-8(N-2)+3(N-3)}{6} = \frac{N+1}{6}.
$$

Having computed the solution by brute force, it is easy to prove by induction. Suppose that $N \geq 3$. Then
$$
T_N = \frac{2}{N} \sum_{i=0}^{N-1} T_i =
\frac{2}{N} \left(1 + \sum_{i=3}^{N-1} \frac{i+1}{6}\right) =
\frac{2}{N} \left(1 + \frac{(N-3)(N+4)}{12} \right) = \frac{N+1}{6}.
$$


Multiplicative Pure Type Systems All the references about Pure Type Systems I know consider only systems that allow to recover natural deduction systems with additive rules. Is there any variant that allows it to recover natural deduction systems with multiplicative rules? Otherwise, is it just by tradition or by inclination that such a Pure Type System is never considered, or is there any good and deep reason why it is not considered?

The rule from Troelstra and Schwichtenberg that you call multiplicative, namely
$$\frac{\Gamma \vdash A \Rightarrow B \qquad \Delta \vdash A}{\Gamma \cup \Delta \vdash B} \tag{1}$$
is equivalent to the additive formulation because we have weakening. More precisely, the multiplicative and the additive formulations prove the same judgements. In one direction, it is obvious that the additive version
$$\frac{\Theta \vdash A \Rightarrow B \qquad \Theta \vdash A}{\Theta \vdash B} \tag{2}$$
follows from the above multiplicative one, just take $\Gamma = \Delta = \Theta$. In the other direction we can use weakening: assuming there are derivations of
$$\Gamma \vdash A \Rightarrow B \qquad\text{and}\qquad \Delta \vdash A$$
then by weakening there are derivations of
$$\Gamma \cup \Delta \vdash A \Rightarrow B \qquad\text{and}\qquad \Gamma \cup \Delta \vdash A$$
and then by the additive rule (2) we get the desired conclusion
$$\Gamma \cup \Delta \vdash B.$$
So for the most part the difference in formulation is largely stylistic, although the difference may matter when we consider proof complexity, and other apsects of derivations, apart from just derivability.

Let me also say that from the semantic point of view it is a bit simpler to give the semantics of the additive formulation than the multiplicative one. In the additive rule one has to cope with the question on how the meaning of $\Gamma \vdash \mathcal{J}$ for some judgement $\mathcal{J}$ relates to $\Gamma \cup \Delta \vdash \mathcal{J}$. No such consideration is necessary in the additive formulation.


How big is the class of problems that can be analysed to halt with static analysis. Is this class sufficient for any practical purposes? When the halting problem is discussed, often the counterproof consists of some unsolved mathematical problem or a self-reference.

Is the halting problem decidable for pure programs on an ideal computer?

Is this of any relevance for most programms not even remotely dealing with complex math ? I often hear that performing static analysis on any program is useless, because "Halting-problem". I find this argument weak, to make a statement from a few theoretical counter examples to say that static analysis on any programm is useless.

And what about a modified version of the halting problem?

What about outputting those 3 possibilities:

Halts.
Does not halt.
Unknown.

Doesn't this simplify the halting problem enough to make a statement about any program in finite time ?

When you hear about "static analysis" in the context of programming languages, you will often have the three results "passes the test", "doesn't pass the test", "is rejected". In that context, the analysis is supposed to help the software developer. If the developer writes code that is too hard to analyse, that's the developer's problem because he isn't going to get the answer he wants.

As an example, the Java language insists that a variable must be assigned a value before it is accessed. Testing that in general would require solving the halting problem. However, the Java language defines a precise method how it would go about verifying this property, and if your program cannot be analysed by this method, then it is rejected. No attempt at solving the halting problem is made.


Lossless data compression must make some messages longer? I read on Wikipedia and in lecture notes that if a lossless data compression algorithm makes a message shorter, it must make another message longer.

E.g. In this set of notes, it says:

  Consider, for example, the 8 possible 3 bit messages. If one is
  compressed to two bits, it is not hard to convince yourself that two
  messages will have to expand to 4 bits, giving an average of 3 1/8
  bits.

There must be a gap in my understand because I thought I could compress all 3 bit messages this way:

Encode: If it starts with a zero, delete the leading zero.
Decode: If message is 3 bit, do nothing. If message is 2 bit, add a
leading zero.
Compressed set: 00,01,10,11,100,101,110,111

What am I getting wrong? I am new to CS, so maybe there are some rules/conventions that I  missed?

You are missing an important nuance. How would you know if the message is only 2 bits, or if it's part of a bigger message? For that, you must also encode a bit that says that the message starts, and a bit that says it ends. This bit should be a new symbol, because 1 and 0 are already used. If you introduce such a symbol and then re-encode everything to binary, you will end up with an even longer code.


Systematically altering functions Let A and B be two integers, where their size is constrained to 2 bits in binary. There exists a function F, which outputs integers of the same size, where F(A) = F(B) = Y. For example, A = 01, B = 10, and Y = 11.

There exist some possible functions, such as G(X) = X xor 10. Another could be H(X) = X + 01 (ignoring overflow). However, in terms of their results, many of these would essentially be the same function, mapping the same inputs to the same outputs.

What is the "common denominator", so to speak, that would allow seeing all functions as the same?

The purpose of this is to be able to "increment" a function. In the first example, suppose I do not know what F is, and I want to write a program to find it. I know that F(A)=F(B), so I could write a loop to try all the possible functions by "incrementing" the function after each iteration, until the function that has F(A)=F(B) is found. Ultimately this will be used on larger sized, and possibly differently sized, inputs and outputs

You can represent a function by its truth table.  Then, any two functions with the same truth table will be the same function, in the sense that they map the same inputs to the same outputs, so this gives you a way to recognize those.

The truth table has 4 entries, each of which are 2 bits, so the truth table is 8 bits long.  Thus, each function can be associated with an 8-bit binary string, or equivalently, an integer between 0 and 255.  You can "increment" the function by incrementing the corresponding integer and converting it back to a truth table.


Find the maximum number of contiguous occurrences of smaller string s in a larger string l Say we have two strings s and l, and they only have characters 'a' through 'z' (lowercase English alphabet characters). The task is to find the maximum number of consecutive occurrences of s in l.
Ex.
s = "ab"
l = "defgababajklabe"
The answer here would be 2, because there is "abab" which would be 2 consecutive occurrences of string s in l.
My initial thought was to go through each character in l, and try to match the substring starting at that position with s, if it matched we would increment our count and keep track of some global maximum. We would also set the value of our next starting point to one position after the end of this matched portion.
If at any point there is a mismatch, then we wouldn't have to re-check all the previous characters, we would just go to one position after the start point, that would be our new start point.
For example, when processing the given example, we would eventually set start to index 4 (0 based index), and match ab, then set it to index 6 and match ab again, then set index to 8. At that point there would be a mismatch, and we would just start matching again at index 9. There is no need to start over from index 5.
This is my guess, and it appears to work, but I can't seem to prove why this works. Can someone help me understand why this works? Or doesn't work?

You algorithm as described doesn't work.
Consider $s=baab$ and $I=\textrm{baabaabbaab}$. Your algorithm would match $s$ with the first $4$ characters of $I$, and since the next $4$ characters don't match $s$, it would then continue with searching $s$ in $I' = aabbaab$.
There is only one occurrence of $s$ in $I'$ causing your algorithm to return $1$ (while the correct answer is $2$).
Here is a solution for your problem that runs in $O(|I|)$ worst-case time.
We can safely assume $|s| \le |I|$, as otherwise the answer is trivially $0$.
Step 1. Construct a DFA $D$ for the language of all words that end with $s$.
This DFA is essentially a path labelled with the characters in $s$ where the last state is a final state. Additionally, each state has "back-edges" that handle characters different from the (at most one) "forward" edge in the path. These "back-edges" point to the state representing the larger prefix of $s$ that is also a suffix of the string read so far.
This sounds more complicated than it really is, and can be computed in linear time (for any constant-size alphabet). Here is an example for $s=\textrm{abba}$ on the alphabet $\{a,b\}$.

Step 2. Now now create an array $A[1, \dots, |I|]$, and feed each character of $I$ to $D$. Whenever $D$ is in the final state after reading the $i$-th character of $I$ set $A[i]$ to $1$, otherwise set $A[i]$ to $0$.
Step 3. Compute the maximum number of consecutive occurrences of $s$ in $I$ using dynamic programming and the array $A$.
Define $B[i]$ as the maximum number of contiguous occurrences of $s$ in the prefix $I_i$ consisting of the first $i$ character of $I$, with the additional constraint that the last occurrence in the contiguous sequence must end with the last character of $I_i$.
For $i = 0, 1, \dots, |s|-1$ we have $B[i]=0$, while for $i = |s|, \dots, |I|$ we can write:
$$
B[i] = \begin{cases}
0 & \mbox{if $A[i]=0$} \\
1 + B[i-|s|] &  \mbox{if $A[i]=1$}
\end{cases}
= A[i](1+B[i-|s|]).
$$
Then the solution to your problem is then $\ell = \max_{i=0, \dots, |I|} B[i]$ and the $\ell$ consecutive occurrences of $s$ start at character number $\arg \max_{i=0, \dots, |I|} B[i] - \ell |s|$  in $I$.
A naive implementation of the dynamic programming algorithm requires time $O(|I|)$ and space $O(|I|)$.
However, one can observe that the value stored in $B[i]$ is useless after $B[i+|s|]$ has been computed (except for finding $\ell$).
Then, we can replace $B$ with a circular array of length $|s|$ (so that each access to $B[i]$ becomes an access to $B[i \bmod |s|]$) and compute $\ell$ by keeping track of the maximum values of $B[i]$ encountered so far.
Moreover, the array $A$ is not needed as we can run Step 2 and Step 3 in parallel: we feed the $i$-th character of $I$ to $D$ and immediately compute $B[i \bmod |s|]$ depending on whether $D$ is in the final state or not.
With these modifications the algorithm requires $O(|I|)$ time and $O(|s|)$ space.
Finally, notice that we don't really need to explicitly represent $D$: knowing, for each prefix $s'$ of $s$ and each character $c$ of the alphabet, the length of the longest prefix of $s$ that is a suffix of $s \circ c$ is enough (where $\circ$ denotes concatenation). See this chapter from Jeff Erickson's book Algorithms for a way to efficiently compute these quantities.


Question about NP problem certificates and P=NP From my understanding a problem is considered to be in NP time if it can be solved in polynomial time with a non-deterministic Turing machine and verified in polynomial time with a certificate.

My question is whether or not creating an algorithm to determine values accepted by a certificate for an NP problem can itself be considered an NP problem.

This problem is an example of what I had in mind (it's more or less a variation of SAT).

Imagine a padlock with N switches and each switch has a configuration 'UP' or 'DOWN'. The padlock can have anywhere between 1 and $2^N$ solutions (i.e. it may only accept one combination or any number of combinations up to and including all possible combinations) and both the total number of solutions and the solutions themselves are selected at random.

If there are $2^N$ solutions a solution takes $O(1)$ time to find since all inputs are valid.

However, if there is only 1 solution $O(2^N)$ time is required to find it.

If it is accepted that trying all combinations on the padlock requires $2^N$ combinations and that because the solution is random there is no way to guarantee a solution unless $2^N - 1$ combinations are tested by process of elimination.

Because the total number of acceptable solutions is not known until different candidates are tested against the certificate, the problem requires $O(2^N)$ time to solve.

To prove that the problem is solvable in NP, use an NTM to solve the problem by non-deterministically testing all valid combinations and accepting any valid solution. Takes $O(N)$ time to solve since every differing possible bit to test will branch into a new non-deterministic chain.

The certificate for the problem contains acceptable values for each 'swicth' (bit) at each location either 1 for 'UP', 0 for 'DOWN' or 'X' to accept any value at that location and takes $O(N)$ time to verify.

Is this valid?

If I'm correct and the problem above does fit in the class of NP it seems sufficient to prove that $P \neq NP$ but I'm fairly confident I made an error I'm not aware of and I'm not sure if my example can be properly classed as an NP problem.

Your problem is in the black box or oracle setting, that is, you are given access to the input as a black box rather than explicitly. You can contrast your problem with 3SAT, in which the input is a formula. One way to solve 3SAT is to try plugging in solutions at random (or systematically) and checking whether they satisfy the formula. However, better approaches are known, and these approaches use the explicit description of the formula.

The P vs NP question is in the white box setting – concretely, $\mathsf{P} \neq \mathsf{NP}$ is equivalent to the conjecture that no polynomial time algorithm solves 3SAT. Results in black box settings are irrelevant (at least directly) to the P vs NP question.

In the black box model we can also separate P from BPP (at least for promise problems), by considering the problem of finding a zero input for a balanced Boolean function. However, for explicit inputs, it is considered likely that P=BPP. This shows that the black box setting exhibits different behavior than the white box setting.

Black box settings are common in optimization, where often we are looking for algorithms which do not rely on the exact form of the input function. For example, in submodular optimization we are given a submodular function as a black box. One method for proving lower bounds in this area is the indistinguishability method, in which we construct two black boxes which are identical on most inputs but have a very different optimal solution. This method is technically much easier than similar results in the white box setting (for example, in the special case of set coverage functions or cut functions), which rely on PCP theory.


Pass by Value or by Reference and Impure or pure functions Beginner question: I am teaching myself the two passing techniques: Pass by Value and Pass by Reference.

Can Pass by Value change the states of an object? If yes, how? Which of the two techniques changes the states of an object?
Also, are Impure Functions based on Pass by Ref. and Pure Functions on Pass by Value?

I'd be glad if someone clears my concept.

Pass by value and pass by reference are about function calls (method calls in case of OOP).

Pass by value means that variable is copied in function and any changes to variable are visible only within scope, where it was changed, if you pass reference then any modification to variable in the function is preserved after function call.

int x = 5;
void PassByValue(y) {
   y = 6;
  // some code
}
void PassByReference(&y) {
  y = 6;
  // some code here
}
PassByValue(x);
// here x is still 5
PassByReference(ix);
// here x is equal 6

Let O be object {x: 8}, that it's private variable x and setter method O.set(y) with code this.x = y;
If you pass by value or pass by reference, it doesn't matter, the state of object is changed.

Impure function has side effects outside of it's scope, so:

void Impure() {
  x = 6;
}

It does not get any parameters, but changes variable in outer scope, this is side effect.

Another property of impure function is that they do not solely rely on input parameters, one canonical example is:

int rand(int x) {
  return rand() * x;
}

Pure function returns the same result at every call, so for example math functions obey this property.
Any observable side effect: I/O operation, mutation, outer scope modification, network trafic, and so on, are impure.


Efficiently calculating minimum edit distance of a smaller string at each position in a larger one Given two strings, $r$ and $s$, where $n = |r|$, $m = |s|$ and $m \ll n$, find the minimum edit distance between $s$ for each beginning position in $r$ efficiently.

That is, for each suffix of $r$ beginning at position $k$, $r_k$, find the Levenshtein distance of $r_k$ and $s$ for each $k \in [0, |r|-1]$.  In other words, I would like an array of scores, $A$, such that each position, $A[k]$, corresponds to the score of $r_k$ and $s$.

The obvious solution is to use the standard dynamic programming solution for each $r_k$ against $s$ considered separately, but this has the abysmal running time of $O(n m^2)$ (or $O(n d^2)$, where $d$ is the maximum edit distance).  It seems like you should be able to re-use the information that you've computed for $r_0$ against $s$ for the comparison with $s$ and $r_1$.

I've thought of constructing a prefix tree and then trying to do dynamic programming algorithm on $s$ against the trie, but this still has worst case $O(n d^2)$ (where $d$ is the maximum edit distance) as the trie is only optimized for efficient lookup.

Ideally I would like something that has worst case running time of $O(n d)$ though I would settle for good average case running time.  Does anyone have any suggestions?  Is $O(n d^2)$ the best you can do, in general?

Here are some links that might be relevant though I can't see how they would apply to the above problem as most of them are optimized for lookup only:

Fast and Easy Levensthein distance using a Trie
SO: Most efficient way to calculate Levenshtein distance
SO: Levenshtein Distance Algoirthm better than $O(n m)$
An extension of Ukkonen's enhanced dynamic programming ASM algorithm
Damn Cool Algorithms: Levenshtein Automata

I've also heard some talk about using some type of distance metric to optimize search (such as a BK-tree?) but I know little about this area and how it applies to this problem.

What you are interested in are semi-global and/or local alignments. The usual way to compute those is to adapt the dynamic programing algorithm for the Levenshtein distance:

Initialise the first row/column with $0$ (instead of $i$/$j$) if free deletions/insertions are allowed at the beginning.
Select the minimum value from the last row/column as result if free deletions/insertions are allowed at the end.

Different combinations are possible. In your case, assume that $r$ is the horizontal word, you initialise the first row with $0$ (the first column with $i$, no change here) and the result is the minimum of the last row. The result is then the smallest Levenshtein distance between $s$ and any substring of $r$, computed in time and space $O(nm)$.

Now, in order to get scores for all starting positions, note that the computation of semi-global alignments with allowed deletions/insertions at the end conveniently provides the wanted array in the last row/column -- well, almost: that gives you the best matches against prefixes up to position $k$. So in order to get best matches against suffixes from position $k$, reverse both $r$ and $s$.


Generating general term of union of two countably infinite sets I have two sets whose general terms are given as:
$$
\begin{align*}
A &= \{2⋅n \mid n ∊ ℤ\} \\
B &= \{2⋅n + 1 \mid n ∊ ℤ\}
\end{align*}
$$
I want to find the union of these two sets and return the common term of the set, something like $\{n \mid n ∊ ℤ\}$.

I have the following questions:

Given that I can't store the entire sets, what are some efficient ways of merging these two sets?
How can I find the common term of any given sequence?
What would be some other approaches to solve this problem?

I would really appreciate if someone can share some
relevant literature or an algorithm for this question.

Note that the members of the sets need not be integers – they can be rationals too.

In functional programming languages, there is a technique called lazy evaluation, to deal with infinite sets. In lazy evaluation, the sets are used as generators, and the elements of the set are only generated when they are needed.

We can even have lazy operations on lazy data: like lazy union, lazy intersection, and the like, particularly if the lazy generation spits out elements in some order. Particularly, lazy union is very efficient. Lazy intersection and lazy minus are problematic in cases such as yours.


Why is CVAL a P-Complete problem? We've learned in class that CVAL is P-complete. CVAL is the language of all $\langle C,x\rangle$ where $C$ is a formula (a circuit which outputs $0$ or $1$) and $x$ is some input for $C$ such that $C(x) = 1$.

We've done this in the same fashion Michael Sipser does in this paper (accessed Jul 11, 2017).

The reduction itself is pretty much clear. What isn't clear to me is why we can make this reduction in $\mathcal O (\log n)$ space?

It's clear that every cell is dependent on some constant number of cells of the above row (= previous configuration). Yet, one would end up calculating recursively more and more cells, until reaching the very first configuration.

We did learn in class how to evaluate $f_2 (f_1(x))$ effectively, with $\log n$ space - You start with computing $f_2$, and when in need, you "ask" $f_1$ for some symbol. I don't see how to apply it in our case.

I'd be glad for clarificatoins

The reduction doesn't calculate the values of all cells. Rather, it outputs a circuit which calculates (recursively) the values of all cells. You can output the circuit using only logarithmic space, while evaluating it probably requires more space (unless L=P) since CVAL is P-complete.


Is Weighted Vertex Cover NP-Complete? I'm doing practice problems for an upcoming exam and I'm unsure if the following problem is NP-complete. If it is can you please give me a hint as to what problem I should reduce to it. I believe it's NP-Complete and maybe the knapsack problem can be reduced to it but I'm not sure.

  WEIGHTED VERTEX COVER:
  Input: A weighted graph $G$ with integer weight $Wv>1$ on each vertex $v$ and an integer $T$.
  Question: Does $G$ have a vertex cover with total weight at most $T$?

Expanding on Pål GD's hint, you can reduced from the normal, unweighted version of VERTEX COVER.

  VERTEX COVER
  Input: A graph $G$ and an integer $k$.
  Question: Does $G$ have a vertex cover of size at most $k$?

So in this case, you're just counting the number of vertices in the cover. Now to transform this to the weighted version, we just need to add weights to all the vertices such that we can recover the size of the vertex cover from the weight of the vertex cover.

Bigger hint under the spoiler tag, don't mouse over unless you're really stuck.

   What happens if we assign each vertex the same weight (doesn't really matter what it is, as long as they're all the same)? If each vertex has weight $c>1$, what's the weight of a vertex cover of size $k$? What's the size of a vertex cover of weight $T$?


Satisfiability with relational operators instead of boolean variables Question

What is the state of the art for relation/equality satisfiability problems and where can I find papers clearly describing algorithms used (Or even better: implementations of them. Or even better: javascript implementations - I know that's a long shot)?

I.e. How do I solve satisfiability of: x > 10 && y < 5 && x < y

Long introduction

boolean satisfiability

The boolean satisfiability problem is quite well documented. However I cannot find algorithms for cases when propositions are relational operators rather than booleans.

For example:

To find out if a sentence like p && !p has any values of p for which it is true, is well documented and ready-made algorithms exist. Often the sentence is transformed to Conjunctive Normal Form (CNF) and then a CNF-SAT solver is used. For example:

http://logictools.org/index.html

relational/equality satisfiability

However I cannot find algorithms for cases when propositions are relational operators rather than booleans. Think of a statement like x > 10 && !(x < 5) or x > 10 && y < 5 && x < y. This seems a way less studied problem.

For example: Transforming equality logic to propositional logic is very theoretical, I couldn't really understand it and thus use it for implementation.

Solving Satisfiability and Implication Problems in Database Systems actually lead me to a solution. It explains how to solve satisfiability for sentences with only conjunctions. Knowing that, I can transform any sentence to Disjunctive Normal Form (DNF) and apply the algorithm to each conjunction in the DNF. If one of the conjunctions is satisfiable, the whole sentence is.

However, it seems that this is not the most efficient way to solve it. First, this paper is from 1996 and I expect the field to have progressed. Second, converting to DNF is exponentially complex while converting to a equisatisfiable CNF can be done in polynomial time. Most boolean satisfiability solvers seem to convert to CNF and then solve using heavily studied algorithms. It seems a similar approach would be preferable for relational satisfiability.

So my question is: What is the state of the art for relation/equality satisfiability problems and where can I find papers clearly describing algorithms used (Or even better: implementations of them. Or even better: javascript implementations - I know that's a long shot)

I have searched for 2 days in different fields such as SQL query optimizers (contradiction/tautology detection) and theoretical CS but haven't been able to find anything else than the above DNF solution.

Congratulations, you have invented Satisfiability Modulo Theories, also known as SMT. This is a large field of research, and deals with exactly the problem of satisfiability with not just boolean variables, but predicates over some existing logical theories, such as linear integer arithmetic, uninterpreted functions, arrays, etc.

The basic idea is that you alternate between calling a SAT solver and a theory solver. You take your relational formula, and replace every relational statement with a boolean variable, then get a solution from a SAT solver. This gives you a True or False value for each relational statement. You then plug those into your theory solver, which determines if there's a solution that is consistent with the truth value for each relational proposition.

If the solution is valid, then you are done. If it is not valid, then you add the negation of the assignment (or a reduced form) to your original boolean problem, since you know it can't hold, and you repeat until you either the theory solver succeeds or the SAT solver fails.

SMT research doesn't care a ton about theoretical complexity, since everything is NP-hard in the best case, and possibly much worse, depending on your theory. Instead, modern SMT solvers are heavily optimized with heuristics and prunings that allow them to be reasonably fast for common cases.

The two most common SMT solvers are Z3 and CVC4, but I have no clue if either work in JavaScript. Writing an inefficient SMT solver yourself is not too hard, especially if you can use an off-the-shelf SAT solver.