A* graph search heuristicfor pathfinding A* needs a consistent heuristic to work on a graph.

So I'm not sure if the heuristic of a straight line (bird flight) can be used.

For example: the costs to travel to a neighbors node is always positive.

              GOAL

 --------------------
 |                  |
 |      START       |
 |                  |    where to stripes are obstacles.

Am I correct that this the proposed heuristic isn't consistent here as it has to travel away from the goal first?

Is there a good heuristic for this kind of situation?
Or should I keep it with Dijkstra a forget about A*?

There is nothing wrong with the heuristic function you suggest. Note what the consistency condition actually says: If you have nodes $n_1,n_2$, and the cost of traveling from $n_1$ to $n_2$ is $c$, then the heuristic values need to satisfy a triangle condition: $h(n_1)$ must not be more than $h(n_2)+c$. It is ok for $h$ to underestimate the distance from a node, as it does for your start node (though obviously, the performance of the algorithm can suffer in this case).


Can a Big-Oh time complexity contain more than one variable? Let us say for instance I am doing string processing that requires some analysis of two strings. I have no given information about what their lengths might end up being, so they come from two distinct families. Would it be acceptable to call the complexity of an algorithm $O(n * m)$ or $O(n + m)$ (depending on if we use a naive or an optimized algorithm)?

On a similar vein, let us presume the algorithm we choose actually requires two stages - a setup phase on the first string which allows us to process any number of other strings without incurring that initial cost. Would it be considered appropriate to say it has a $O(n)$ construction followed by any number of $O(m)$ calculations?

Would it be appropriate to just call them $O(n)$ because both calculations are linear?

Yes, of course.  This is fine and perfectly acceptable.  It is common and standard to see algorithms whose running time depends upon two parameters.

For instance, you will often see the running time of depth-first search expressed as $O(n+m)$, where $n$ is the number of vertices and $m$ is the number of edges in the graph.  This is perfectly valid.  The meaning of this is there exists a constant $c$ and numbers $n_0,m_0$ such that the running time of the algorithm is at most $c \cdot (n+m)$, for all $n>n_0,m>m_0$.  In other words, if the exact running time is $f(n,m)$, we say that $f(n,m) = O(n+m)$ if there exists $c,n_0,m_0$ such that $n>n_0$ and $m>m_0$ implies $f(n,m) \le c \cdot (n+m)$.

Yes, it is perfectly appropriate and acceptable to say that the first stage takes $O(n)$ time and the second stage takes $O(m)$ time.

Important: make sure you define what $n$ and $m$ are.  You can't say "this is an $O(n)$ time algorithm" without specifying what $n$ is.  If $n$ isn't specified in the problem statement, you need to specify it.  For instance, see graph algorithms, where we typically define $n = $ # of vertices and $m = $ # of edges.

As far as whether you can call them $O(n)$ time, no, of course not -- unless you somehow know that $m = O(n)$.  Of course, if you know that $m = O(n)$, then it follows that $m+n = O(n)$, so an $O(m+n)$ time algorithm is also an $O(n)$ time algorithm.  But if there is no guarantee that $m = O(n)$, then you cannot call it an $O(n)$ time algorithm.

This is basic stuff.  You'll find it all over algorithms textbooks.


Was multiple inheritance ever implemented by adding redundant data members? In discussions about why most languages which implement inheritance only implement single-inheritance, the question of the precise semantics of overlaps often comes up, and having redundant data members is sometimes given as an example semantic that would be undesirable. Note that this semantic effectively implements inheritance with composition.

Given that "prefer composition over inheritance" seems to be the current prevailing wisdom, having overlaps be redundant doesn't sound as bad as it once did.

So my question is:

Are there any programming languages which implemented multiple inheritance by adding redundant data members? How did that turn out, if so?

It does not matter how you implement multiple inheritance, the inherent issues coming from that still apply.

If $C$ is a class, and $D$ a derived class (subclass), and $d:D$ we can write d.foo() to call a method that can be defined in $D$ (possibly ovverriding $C$'s own method) or the method which is inherited from $C$ (and not overridden). In any case, there a clear choice on which one should be called.

If instead $D$ derives from $C_1,C_2$ then that method might be inherited from both and we need to disambiguate somehow. For instance, d.foo() could be an error now, and we could require something like d.C1::foo() instead. Or we could give priority to the "first" superclass. Or we could require that the definition of $D$ must resolve the ambiguity (e.g. an overridden method is now mandatory). None of this is an ideal solution. Liskov substitution principle for $C_2$ is likely broken by any of these options.

Using composition instead of inheritance, things hardly change. We still need to disambiguate. We can use d.field_c1.foo() instead. We can make $D$ to define a foo() method that chooses according to the wanted priority. We also have the additional option of making $D$ not expose the foo() method at all, but this means that $D$ can no longer be considered a subtype of $C_1,C_2$, not even in some lax sense.

More pragmatically, after decades of being almost dogmatic about OOP, the software engineering community is now coming to a more honest evaluation of it, trying to highlight the advantages without hiding the issues. Inheritance is now still found interesting and useful, but much less so.


HamCycle to HamPath reduction I've seen a reduction that's done by adding another vertex to the graph and creating a path through that vertex.

Why do I need to add a vertex? Cant I just remove an edge? Lets say the graph with the HamCycle is G,s,t when removing the edge between s and t dont I get a path the goes through all the vertexes that's qualified as a Hamiltonian path?

First of all I think that the direction of the reduction of your question is from Hampath to Hamcycle (you prove the NP-hardness of Hamcycle reducing the NP-complete problem Hampath to it).

Now given an instance of Hampath: $G,s,t$:

1) there is an edge between $s$ and $t$
2) there is not an edge between $s$ and $t$

In both cases the extra node $u$ is needed in order to force $s,u,t$ to be consecutive nodes in  the Hamiltonian cycle.

The new graph $G'$ with a new node $u$ and new edges $(s,u), (u,t)$ (in the first case you split the original edge) will have an Hamiltonian cycle iif the original graph $G$ has an Hamiltonian path from $s$ to $t$.

You can "play" with these two graphs:


Algorithm to pack any small boxes into a big box I have a container with a certain dimension. A number of small boxes that may be different in size is to be packed into the container. How to arrange the small boxes such that the container contains as many as possible?

No rotation is allowed.
The heavier boxes must not be on the top of the lighter ones.
Approximation is allowed.

I am looking for the algorithm so I can implement it in a software.

Your problem is called 3D Bin Packing and is indeed an NP problem.

Looking those key words on Google will yield many articles about more or less complex approximation algorithms that can help you solve this problem.


What's the correct algorithm to filter accumulating string concatenations? I have a function that is receiving messages with the following pattern:

(In this picture, "string" and "message" are synonymous.)

I'm only interested in the largest messages, such as these:

over a particular window.

Is there an algorithm that can appropriately filter the messages in the desired manner over a specified window?

Store them in a heap or priority queue, keyed on the size of the message.  This way, if you want the $k$ largest messages, you can keep track of that as each message arrives.  This will require $O(k)$ space to keep track of the $k$ largest messages at each step, and $O(\log k)$ time per message that arrives, so it should be pretty efficient.


What does it mean when saying "we want $\Lambda$ to be $\tilde{O}(1)$ as a function of $M$"? What does it mean when saying "we want $\Lambda$ to be $\tilde{O}(1)$ as a function of $M$"? (it appears on the top of page 12 of this paper)

The notation $\tilde{O}(f(n))$ is not completely standard and is usually defined as $\tilde{O}(f(n)) = O( f(n) \cdot \text{poly} \log f(n))$. The intuition is that it drops factors that are asymptotically not larger than a polylogarithm of the argument. For example, you can write $\tilde{O}(n^2)$ in place of $O(n^2 \frac{\log^3 n}{\log \log n})$.

That said, in your paper $\tilde{O}(f(n))$ seems to be used as a shorthand for $O( f(n) \cdot \text{poly} \log n)$, although I was not able to find a definition within the paper by quickly skimming it. This only differs from the previous definition when $f(n)$ is smaller than or larger than any polynomial.

In the specific sentence you are quoting, the authors want $\Lambda$ to be in $O(\text{poly} \log M)$.


Order of steps in Kosaraju-Sharir The Wikipedia summary of the Kosaraju-Sharir algorithm is as follows:

  Let G be a directed graph and S be an empty stack.

  While S does not contain all vertices.

  Choose an arbitrary vertex v not in S.
  Perform a depth-first search starting at v. Each time that depth-first search finishes expanding a vertex u, push u onto S.

  Reverse the directions of all arcs to obtain the transpose graph.
  While S is nonempty:

  Pop the top vertex v from S.
  Perform a depth-first search starting at v in the transpose graph.
  The set of visited vertices will give the strongly connected component containing v; record this and remove all these vertices from the graph G and the stack S. Equivalently, breadth-first search (BFS) can be used instead of depth-first search.

But in my textbook - Sedgewick's Algorithms (fourth edition) - it describes the steps of the algorithm as follows:

  Given a digraph G, compute the reverse post-order of its reverse digraph. GR
  Run a standard DFS on G, but consider the unmarked vertices in the order just computed instead of the standard numerial order
  The set of all vertices...

The conclusion drawn in the third step is identical, as are the operations performed in the first two steps, but it seems that those two steps are given in opposite orders: Wikipedia tells me to start by doing a DFS on G and then transposing it, doing the second DFS on GR, whereas my textbook suggests that I begin by transposing G, do the first DFS on GR and the second on G.

My primary question is: Am I understanding this correctly, or am I misinterpreting what one or the other is saying?

Secondly: Intuitively, it seems as though these operations are transitive and therefore that these two "different methods" are in fact equivalent, and will always yield the same final result. I've tested this intuition on a couple of digraphs and it seems to hold true - but is it?

Thirdly: Assuming it is, is there any objective reason to prefer one over the other, or is it simply a matter of preference?

  NOTE: As of now, this question is cross-posted on StackOverflow. I'm an established user there, so I know that cross-posting is generally frowned upon, but I've just joined this SE and am curious to gauge the response I get here relative to what I get there. I will delete one or the other after doing so. If you'd like me to do so immediately, please comment.

Yes, you are understanding this correctly.
The set of SCCs of a graph is uniquely determined. So if the algorithms were returning different sets, this would imply that one of them is incorrect. For the Wikipedia version a correctness proof is linked at the bottom of the article. If Sedgewick also gives a correctness proof of his algorithm, these two proofs together imply the property.
Reversing a graph twice will give you the original graph. Thus, if one algorithm performs especially well/bad on a certain graph, the other one will show that performance on the reversal of the graph in question. So neither algorithm will perform better in the general case.

The comment on SO that the WP version does use $O(n)$ extra space for the stack is not entirely correct: Sedgewick also has to store the order of traversal in some way, which wll also take $O(n)$ space (though possibly with a smaller hidden constant). Additionally, you can replace the stack with a different way of storing the order in the WP algorithm as well.


Is this language L regular? Let's say we have the language L = {w $\in$ {a,b}$^*$ : ($\exists n \in \mathbb{N}  $)[$w|_b = 5^n$]}. I want to know if this is a regular language or not. How do I go about doing this? I'm familiar with the Myhill-Nerode theorem but I don't know how to apply it.

You don't need the Myhill-Nerode theorem.
Suppose that $L$ was regular and let $c>0$ be its pumping length.

The word $b^{5^c}$ is in $L$ and therefore there is some positive constant $k \le c < 5^c$ such that $b^{5^c + ik} \in L$ for all integer values of $i \ge -1$.
For $i =1$ you must have $b^{5^c + k} \in L$ which implies that $5^{c} + k$ is a power of $5$.

This is a contradiction since
$
5^ c < 5^c + k < 5^c + 5^c = 2 \cdot 5^c < 5^{c+1}.
$

If you still want to use the Myhill-Nerode theorem you can proceed as follows:
Pick any two non-negative integers $i,j$ with $i<j$ and consider the two words $x= b^{5^i}$ and $x = {5^j}$.  Let $z = b^{4 \cdot 5^i}$. Notice that $xz = b^{5^i + 4 \cdot 5^i} = b^{5^{i+1}} \in L$ while $yz = b^{ 5^j +  4\cdot 5^i} \not\in L$ since $5^j < 5^j +  4 \cdot 5^i < 5^j +  4 \cdot 5^j = 5^{j+1} $. Therefore $z$ is a distinguishing extension for $x$ and $y$ and they cannot belong to the same equivalence class for the relation $R$ defined by $\alpha R \beta$ iff $\alpha \in \Sigma^*$ and $\beta \in \Sigma^*$ have no distinguishing extension. This shows that the number of equivalence classes in the quotient set $L_{/R}$ is not finite and, by the Myhill-Nerode theorem, $L$ is not regular.


Address space definition I'm learning by my self about OS theory and I have some troubles to understand what is a process address space. So far, I came across two definitions of what a process address space is:
1 - The set of virtual addresses available to a process. Hence the address space, would be the numbers from 0x0 to 0x7FFFFFFF.
2 - The virtual memory addressable by a process. I picture it as a set of cells with addresses from 0x0 to 0x7FFFFFFF.

I would like to know which one is correct?
This is important for me because I read sentences like "the address space is organized into pages of 4096 bytes" which makes me lean towards the second definition.

Thank you.

The address space is the space (i.e., set) of addresses – see, e.g., Wikipedia. It's an abuse of terminology to claim that the address space is divided into pages. It isn't: it's the memory addressed by the addresses that's divided into pages.

(This confusion between addresses and the things referred to by addresses is common.  How many times have you heard people say, "I'll give you my email" when they mean "I'll give you my email address"?)


Error in simple mode finding algorithm? I'm working through a few chapters on algorithms from the Discrete Math text by Rosen.

In the solutions manual there is an algorithm (specified in pseudocode) for finding the mode within a list of non-decreasing integers.

Here is the algorithm:

procedure find a mode(a_1, a_2, ... , a_n : non-decreasing integers)
modecount = 0
i = 1
while i <= n
    value = a_i
    count = 1
    while i <= n and a_i == value
        count = count + 1
        i = i + 1
    if count > modcount then
        modecount = count
        mode = value
return mode

Now, I immediately see a problem with this algorithm. For instance, take the list $<1,2,2,2,4,4,4>$ we see that the following steps are followed, counting the element $1$ twice when it only appears in our list once.

Steps below begin upon first entry of the body of the while loop:

Step 1. Assign $a_1=1$ to $value$.

Step 2. Assign $1$ to $count$

Step 3. Check that $i=1 \leq 7$ and that $a_1=1$ equals $1=value$.

Step 4. Increase the value of $count$ by $1$ so that $count := 2$.

But we only have $1$ appearing once in our list and we have counted it twice.

Is my interpretation of this algorithm incorrect? To me $count$ should first be set to $0$.

Yes, you are right.  The pseudocode is clumsy, poorly constructed, and confusing.  At the end of the outer loop, modecount holds the number of times that value appears in the array, plus one.  That's weird and not what you'd expect from the variable name: from the variable name, we'd expect it to hold the number of times value appears (without the plus one).

That said, the algorithm still returns the correct answer: it does indeed return a mode, as claimed.  For example, with your example input, it correctly returns 2.

(Why?  Because the exact value of modecount isn't returned.  It's one too high for every value, so the mode will indeed have the largest value of modecount.)

So while the pseudocode is confusing and poorly constructed, it happens to return the right answer -- i.e., it happens to be a correct algorithm for the "find a mode" problem.  But it's still ugly.  Yuck.  I agree with you that they should have initialized the count to 0, not 1; then the algorithm would be both correct and easier to understand.


Independent set problem I'm referring to a post on a black-box algorithm and the Independent Set problem.
Question

Suppose that someone gives you a black-box algorithm $A$ that takes an undirected graph $G = (V, E)$, and a number $k$, and behaves as follows.

If $G$ is not connected, it simply returns “$G$ is not connected.”
If $G$ is connected and has an independent set of size at least $k$, it returns “yes.”
If $G$ is connected and does not have an independent set of size at least $k$, it returns “no.”

Suppose that the algorithm $A$ runs in time polynomial in the size of $G$ and $k$.
Show how, using calls to A, you could then solve the Independent Set Problem in polynomial time: Given an arbitrary undirected graph $G$, and a number $k$, does $G$ contain an independent set of size at least $k$?

Solution

There are two basic ways to do this. Let $G = (V, E)$; we can give the answer without using $A$ if $V = \emptyset$ or $k = 1$, and so we will suppose $V \neq \emptyset$ and $k > 1$. The first approach is to add an extra node $v^*$ to $G$, and join it to each node in $V$; let the resulting graph be $G^*$. We ask $A$ whether $G^*$ has an independent set of size at least $k$, and return this answer. (Note that the answer will he yes or no, since $G^*$ is connected.)
Clearly if $G$ has an independent set of size at least $k$, so does $G^*$. But if $G^*$ has an independent set of size at least $k$, then since $k > 1$, $v*$ will not be in this set, and so it is also an independent set in $G$. Thus (since we’re in the case $k > 1$), $G$ has an independent set of size at least $k$ if and only if $G*$ does, and so our answer is correct. Moreover, it takes polynomial time to build $G*$ and ask call $A$ once.

My question
I think I don't understand the solution(or the question), like I don't understand why it needs to create a new $G^*$ to check whether $G^*$ has Independent set of size at least $k$. I'm thinking naively if algorithm $A$ can solve this problem, can't we just input $G$ into $A$ to get a result?
I'm learning to prove a problem is NP-complete currently, these steps looks like reduction to me. So, whenever we see a problem like given algorithm $A$ able to solve a graph problem, we always need to create a new graph $G^*$ to verify it?

The reason you can't just take $G$ as an input to $A$ is that (strangely enough) $A$ only works on connected graphs.

You want to prove that if $A$ exists, then Independent Set is solvable in polynomial time.  The reason you can prove that is by using a polynomial time reduction.   You have proved that if $A$ exists, then $A$ can solve Independent Set on any graph by using your trick of adding a universal vertex.

You have also proved that Independent Set on non-connected graphs is not particularly much easier than on connected graphs.


Trouble Replicating Proof of The Lambda Calculus Fixed Point Theorem From pg. 35 of Lambda Calculus and Combinators An Introduction:

  Corollary 3.3.1 in $\lambda$ and $CL$: for every $Z$ and $n \ge 0$, the equation

  $$ xy_1 \ldots y_n = Z $$

  can be solved for $x$. That is, there is a term $X$ such that

  $$ Xy_1 \ldots y_n =_{\beta, w} [X/x]Z. $$

  Proof: Choose $X \equiv \mathsf{Y} (\lambda x y_1 \ldots y_n.Z)$.

Note: In the book, we assume that $\mathsf{Y} \equiv (\lambda ux. xuux)(\lambda ux. xuux)$. Further, for ease of notation, let $V \equiv (\lambda x y_1 \ldots y_n.Z)$.

The problem is that when I check this with my own examples, I'm not getting this result.

For example, suppose that neither $x$ nor any of $y_1, \ldots , y_n$ is in the free variables of $Z$ (to make it easy). Then this theorem asserts that if $X \equiv \mathsf{Y}(\lambda x y_1 \ldots y_n . Z)$, then

$$
Xy_1 \ldots y_n =_{\beta, w} Z
$$

When I check whether this true, I get

$$
(\mathsf{Y}(\lambda x y_1 \ldots y_n . Z))y_1 \ldots y_n = (\mathsf{Y}V)y_1 \ldots y_n = (V\mathsf{Y}V)y_1 \ldots y_n =_{\beta, w} Zy_n
$$

Am I doing something wrong?

$\newcommand{\Y}{\mathsf{Y}}$

Did you leave out any parentheses by any chance? We should take $\Y = (\lambda  u x . x (u u x)) (\lambda  u x . x (u u x))$. Note that $x u u x$ is the same as $(x u u) x$, which is not the same as $x (u u x)$.

We use the abbreviations $V = (\lambda x y_1 \ldots y_n . Z)$ and $X = \Y V$, as in your question. Then we calculate:
\begin{align*}
\Y V
&= (\lambda  u x . x (u u x)) (\lambda  u x . x (u u x)) V \\
&= (\lambda x . x ((\lambda  u x . x (u u x)) (\lambda  u x . x (u u x)) x)) V \\
&= V ((\lambda  u x . x (u u x)) (\lambda  u x . x (u u x)) V) \\
&= V (\Y V)
\end{align*}
and hence
\begin{align*}
X y_1 \ldots y_n
&= \Y V y_1 \ldots y_n \\
&= V (\Y V) y_1 \ldots y_n \\
&= (\lambda x y_1 \ldots y_n . Z) (\Y V) y_1 \ldots y_n \\
&= (\lambda x y_1 \ldots y_n . Z) X y_1 \ldots y_n \\
&= [X/x, y_1/y_1, \ldots, y_n/y_n] Z \\
&= [X/x] Z.
\end{align*}


Greedy algorithm for Set Cover problem - need help with approximation I want to approximate how close is the greedy algorithm to the optimal solution for the Set Cover Problem, which I'm sure most of you are familiar with, but just in case, you can visit the link above.
The problem is NP-Hard, and I'm trying to find a bound on how well does the greedy algorithm perform.
I know it looks a lot, but please bare with me. I pretty much did most of the work, I'm just missing that last small piece.

Here is the pseudo code:

Input: $U$ - set of elements, $F$ - family of sets s.t. $\bigcup_{S\in F}S=U$
Output: $C$ - a family of sets; $C\subseteq F$ s.t. $\bigcup_{S\in C}S=U$

initially C is empty

while U is not empty do:
    choose S from F that maximizes the cover of elements in U
    add S to C
    subtract S's elements from U

return C

The algorithm is pretty straight forward, and it is easy to see that it is indeed polynomial.

This is my attempt to approximate:
Claim 1: In a set $U$ of $m$ objects, that can be covered with $k$ sets, there has to be a set $S\subseteq U$ whose size is at least $\frac{1}{k}m$.
Proof: Trivial. (I decided not to prove it)

A corollary is that given the situation described in that claim, the greedy algorithm will choose a set whose size is at least $\frac{1}{k}m$.

Claim 2: Given a universe $U$, if there exist a cover of size $k$, then after $k$ iterations, the greedy algorithm will cover at least half of the elements, meaning at least $\frac{1}{2}n$ elements.
Proof: By claim 1, in the first iteration the algorithm will cover at least $\frac{1}{k}n$ elements. Upon entering the second iteration, there are at most $n-n\frac{1}{k}$ elements, and so the greedy algorithm will at least cover additional $\frac{1}{k}(n-n\frac{1}{k})$ elements. In general, on the $i$'th iteration, the algorithm will cover $\frac{1}{k}(n-n\frac{i-1}{k})$ elements. So after $k$ iterations:
$$\sum_{i=1}^{k}\frac{1}{k}(n-n\frac{i-1}{k})=\sum_{i=0}^{k-1}\frac{1}{k}(n-n\frac{i}{k})$$
$$=\sum_{i=0}^{k-1}\frac{n}{k}-\sum_{i=0}^{k-1}\frac{ni}{k^2}=n-\frac{n}{k^2}\sum_{i=0}^{k-1}i$$
$$=n-\frac{n}{k^2}(\frac{k(k-1)}{2})=n-\frac{n}{2}(\frac{k-1}{k})\geq\frac{1}{2}n$$

OK, now this is where I need help: I know that in the first $k$ iterations, the algorithm picks at least half of the elements. After another $k$ iterations, another half was covered, out of what's left (meaning another $\frac{1}{4}n$). So in general, I know that the bound is $k\log n$, I just can't figure out how to formalize it.
What formula represents this behaviour? $T(ki)=T(\frac{1}{2^i}n)$ and solve for $i$? It didn't work...
What formula or equation should I solve to actually show that the number of iterations is bounded by $k\log n$?

You have shown that if there is a set cover of size $k$ and there are $n$ elements left uncovered, then the greedy algorithm finds $k$ sets which cover at least $n/2$ elements, and so at most $n/2$ elements are left uncovered. You can prove by induction that if there is a set cover of size $k$ and there are $n$ elements left uncovered, then for each $t$, the first $tk$ sets found by the greedy algorithm cover all but at most $n/2^t$ elements. The idea now is to pick a value of $t$ such that $n/2^t < 1$. Since the number of elements left uncovered by the algorithm is an integer, if the number $m$ of elements left uncovered satisfies $m < 1$, then in fact $m = 0$, i.e., all elements are covered.

As a side note, you can actually improve on your reasoning and show that the first $k$ sets cover at least $(1-1/e)n$ elements, and so leave only $n/e$ elements uncovered. This improves the bound from your $k\log_2 n$ to the sharp $k\ln n$, which is known to be tight (unless P=NP).


Broadcasting on a dynamic grid We are given a $n \times n$ grid, where each node can maintain a single "active" edge with one of its 4 neighbors at each time step. The active edge of each node changes periodically clockwise or anticlockwise, in the sense that if, for example, at time $t$ node $v$ has an active edge with its upper neighbor, and it rotates clockwise, at times $t+1$, $t+2$ and $t+3$ it will maintain an active edge with its right, lower and left neighbors, respectively.

at time $t=0$ node $(i,j)$ holds a message, and at each time step a node that has already received the message can transfer it through an active edge to one of its neighbors, if that neighbor also maintains this edge as active at this time step.

I am looking for sufficient conditions (initial active edges configurations and rotation direction of all the nodes) such that the message can be transmitted to all nodes in the grid. It's clear this is predetermined by the initial conditions, and depends upon the connectivity of a graph G' that represents them (where neighboring nodes that both maintain an edge as active at some time step are connected in G'). Given that G' it's possible to find total broadcasting time by graph traversal (BFS). The main question is how to know if two edges share an active edge at some time step (given that their behavior is cyclic).

Thanks!

Here is how to analyze a starting configuration to determine whether the message will be able to eventually reach all nodes in the grid.

Consider two adjacent nodes $u,v$.  We'll say that these two nodes are connected if at some point during the first four time steps, node $u$'s active edge points to $v$ and node $v$'s active edge points to $u$.  In other words, nodes $u,v$ are connected if one (or both) of the following two conditions holds:

In the initial configuration, $u$'s active edge points to $v$ and $v$'s active edge points to $u$.
$u$ rotates in the opposite direction as $v$.

Construct an undirected graph $G$ with one vertex per node in the cell, and an edge $(u,v)$ between two vertices iff they are connected (per the above definition).  Then a necessary and sufficient condition for the message to be able to reach all nodes in the grid is that the graph $G$ must be connected.

It's also possible to use this kind of analysis to determine the shortest time necessary before the message reaches all nodes, with running time linear in the size of the graph.

In particular, we can build a directed graph $G'$ with one vertex $(i,j,k)$ per cell $(i,j)$ and value $k \in \{0,1,2,3\}$.  (We will interpret $k$ as the time, modulo 4.)  This graph has a directed edge $(i,j,k) \to (i',j',k+1 \bmod 4)$ if $(i,j)$ is adjacent to $(i',j')$ and $(i,j)$'s active edge points to $(i',j')$ at time $k$ and $(i',j')$'s active edge points to $(i,j)$ at time $k$.

Now we use breadth-first search to find the shortest path from $(i_0,j_0,0)$ to every other vertex, where $(i_0,j_0)$ is the cell where the message starts.  We define

$$f(i,j) = \min\{d((i_0,j_0,0),(i,j,k)) : k=0,1,2,3\}$$

where $d(u,v)$ is the length of the shortest path from vertex $u$ to vertex $v$ in $G'$.  Finally, $\max_{i,j} f(i,j)$ is the shortest time necessary for the message to reach all nodes.  The running time of this algorithm is $O(mn)$, i.e., it runs in linear time (linear in the size of the input).


How does one formulate a backtracking algorithm I am new to learning algorithms.
I was reading backtracking algorithm for generating all strings for n bits.
If I dry run the program I know the program is giving right result.
But I didn't understood the logic can anybody please explain? What I mean is what will be be the thought process to arrive at this solution

void binary(int n)
{
    if(n < 1)
        printf("%s\n",A);    // Assume A is a global variable
    else
    {
        A[n-1] = '0';
        binary(n-1);
        A[n-1] = '1';
        binary(n-1);
    }
}

This answer begins with a first section explaining the problem in more
general terms. The direct answer to the question for the example given
by the OP is then given in a second section that illustrate the
discussion in the first.

You may well want to skip the first section and go direcly to the
second one, depending on whether you like to start with basic
principles or with the analysis of an example.

The principles : non-deterministic programming

My description is not intended for this algorithm only, but is more a
general way to design such algorithms.

The key idea is that backtracking is a technique to implement
non-determinism with depth-first exploration of the non-deterministic
space of possibilities.

Non-determinism allows you to separate the logic of the problem from
the non-deterministic exploration of the solution space. It makes
programs clearer, simplifies analysis and proofs of properties. This is
pretty much the same advantage that you get when using non-determinism
in Automata Theory, to simplify the design of automata performing a
given calculation. Non-determinism makes your technical life much easier.

This advantage is such that various programming experts and language
designers have analyzed or experimented with the introduction of a
standard non-deterministic functionality in various programming
languages, not to mention the language Prolog where non-determinism is
a central control feature.

Another advantage of using non-determinism is that it leave open the
implementation technique, that can also use breadth first exploration,
or even dynamic programming (to avoid repeating calculations). And the
handling of non-determinism, such as adding the backtrack control, is
done entirely by the compiler.

An interesting side-point is that BNF, the language of context-free
grammars, can be seen as a simple non-deterministic programming
language to write parsers. And you can compile it fairly simply into a
depth-first parser (some early ones were just that - Ned Irons, 1961),
or a breadth-first one, or a dynamic-programming one (CYK, Earley, and
some others).

However, backtracking requires mastering the state of the environment.
Without going into details, it is much easier to implement it in a
purely functional programming language that has no side-effects
(for example, no assignment to global variables), at least not in the
parts of programs that use non-determinism.

This is not in contradiction with the use of the global variable A
below, which is never read, except to collect the answers.

But it explains why I insist on starting with a recursive
non-deterministic program, rather than with an equivalent iterative
variant.

What is described below could well be done automatically by the
compiler of a non-deterministic language.

Description of the design for the given example

Here is how I would explain the design of this algorithm.

You consider an array A of bits where the permutation is stored before
printing. It can be a global variable.

First you write a non-deterministic algorithm, that will just produce
one permutation, a "random" one, chosen by the god of non-determinism
:)

This is a simple recursive procedure that ask the god's oracle
choose for each bit in succession. The choose oracle return
non-deterministically one of its arguments (here the word oracle is
used in its mythological sense, not in the usual sense of
computability theory). Using recursion is important, as I shall explain later.

void binary(int n)
{
    if(n < 0)
        printf("%s\n",A);    // Assume A is a global variable
    else
    {
        A[n-1]= choose('0','1')
        binary(n-1);
    }
}

You should agree that this algorithm will return one of the
permutation, anyone of them. You could organize the recursion differently, it does not really matter. All that matters is that you may follow any of the possible computations.

What you have done with this program is to prepare for all choices
that will make a permutation.

Then, instead  of making one choice non deterministically, you simply
try them all, one after the other, for each of the calls.

Since you have a list of the possible choices (there can be a variable
number of them), you just try them in succession. You can do that by
having a segment of code for each possible value. But when the
possible values are in a list of variable length, you can just loop
over that list.

Here you have just  2 values, so you just write twice the same code,
once for each of the values, so that:

        A[n-1]= choose('0','1')
        binary(n-1);

becomes

        A[n-1]= '0'
        binary(n-1);
        A[n-1]= '1'
        binary(n-1);

The first call to binary will produce all permutations with '0' in
position n and the second all permutations with '1'.

Instead of choising arbitrarily, you do one, then the other.

There is an invisible trick that helps you. This would be somewhat
harder if you had used an iteration rather than a recursion.

The reason is that, for each former call to choose, you have to
come back to it after trying all possibilities of later choices, and
you have to remember what are the choices you have not tried yet.

This is very easily handled by returns of the recursive call, where
you find the environment and the execution point where you left it, so
that you simply go on.

If you had used an iteration, you would have a beautiful mess managing
the data to recall how far you have dealt with each non-deterministic
choice.

You could have started with a very simple loop, that is also a
non-deterministic way of computing a single permutation.

void binary(int n)
{
    for (i=n-1; i=0; i--) {
        A[i]= choose('0','1')
    }
    printf("%s\n",A);
}

But transforming this program into a deterministic backtracking
program would be a lot harder.

Isolating each non-deterministic choice in a function makes your life
easy.

There is an old classical paper that talks of non-deterministic
algorithms, though I have not looked at it in a very long time, and I
have no memory of how it handles the problem. People were not using
recursion as much in those times. You may want to look at it. Bob
Floyd was one of the pioneers of computer science.

Non-deterministic algorithms, Robert W. Floyd, 1966.

I do not recall where it was published, but it is easy enough to find.

Note: The previous version of the answer was assuming arrays are indexed from 1 to n.  I changed that as it may put off users who recognize the code as C code. The site is normally language agnostic. The program given in the question is missing both A[0] and A[n].


Behavior of non-deterministic Turing Machines after $t_i$ seconds Suppose that I have a non-deterministic Turing Machine $M_1$ and its clone $M_2$. Given a string $x \in \Sigma^*$, it is possible that after $t_i$ seconds $M_1$ accepts $x$ and $M_2$ does not halt ? What happens if i run $M_2$ $2t_i$ seconds?

My approach

It is possible because the transition function $\delta_N$ is a partial function and the machines do random guesses, but it can't be that a machine reject and the other accept. If i run $M_2$ for $2_i$ seconds, the outcomes may be different.

There are no seconds of execution, you might want to use steps instead.
Non-deterministic Turing Machine does not behave randomly at all, so two machines $\mathcal M_1$ and $\mathcal M_2$ (being copy) are identical, they do not in any random way pick the steps, so the simulation on the first one goes like on the second one. At any time after the same number of steps the tape content matches and the current state matches.

In sny transition there might be more than one rule, the NDTM accepts when one of the paths accepts, but these are executed in copied machines. This effectively may mean that the NDTM have "guessed" the next step (counting steps to the accepted path is the shortest possible one if such exist) but it will always be the same one for given configuration. Please note that if you imagine every step as producing copy of the machine with a different transition taken then these copies might differ.

Please read also the difference between non-determinism and randomness


Count elements of a sorted matrix that fall into a given interval I have a $n\times n$ matrix called $M$, and two integers $k_\min$ and $k_\max$.
Each row and each column of M is sorted in the increasing order.

I would like to know if there is way I can count the number of its elements which are inside $[k_\min, k_\max]$, using a $O(n)$ algorithm.

First, notice that you only need to know how to count the number of elements bigger than $k_{min}$, because then, by a very simple transformation, you can count the number of element smaller than $k_{max}$, and compute the desired result : since the set $A$ of element bigger than $k_{min}$ is of the form $[a;max]$, and the set $B$ of element smaller than $k_{max}$ is $[min;b]$, you have $|A \cap B| = |A| + |B| - n^2$

Now, find the last element smaller than $k_{min}$ on the last row, at column $c_0$.
On this last row, exactly $n - c_0$ elements are bigger than $k_{min}$.
On the row above, the last element smaller than $k_{min}$ has to be right to $c_0$, because otherwise, since $M$ is sorted on row and column, you would have a contradiction. Hence, in order to find the last element smaller than $k_{min}$ on this row, you can start at column $c_0$ and go right to find $c_1$.
Then again, the number of elements bigger than $k_{min}$ on this row is $n - c_1$.

Repeating this process, you then sum the number of elements on each row to compute the result, and you'll scan only at most $2n$ elements since the path followed by the algorithm is a path from the point $(0,n-1)$ to the point $(n-1,0)$, going only up and left, and these kind of path have length $2n$.
This is hence indeed an $\mathcal{O}(n)$ algorithm.

EDIT: details added


Difference between fixed-to-variable length codes and variable-to-fixed length codes? I am a bit confused by the difference between the two. Can someone clarify the difference between the two?

A fixed-to-variable length code is a code that takes a string in $\cal X^*$, partitions it into chunks of fixed length $n$, and replaces each chunk $w$ by some codeword $C(w)$ whose length isn't fixed. The classical example is prefix codes. A prefix code such as Huffman's code replaces each symbol $\sigma \in \cal X$ by a codeword $C(\sigma)$, with the aim of minimizing $\mathbb{E}[|C(\sigma)|]$ with respect to some distribution on $\cal X$. We can obtain a better rate by applying Huffman coding on $k$-tuples of inputs. This corresponds to a fixed-to-variable length code that encodes each word $w$ of fixed length $k$ by a codeword $C(k)$.

A variable-to-fixed length code is a code that takes a string in $\cal X^*$, breaks it into pieces of variable length, and replaces each piece into a word of fixed length. The classical example is Lempel-Ziv encoding with fixed dictionary size. Lempel-Ziv breaks its input into chunks, where each chunk extends a word in the dictionary by one symbol. Each chunk is then encoded as an index into the dictionary together with the new symbol. The encoding thus has fixed length, but the chunks vary in length.


Proving regularity via equivalence classes Given two regular languages $L_1$ and $L_2$, we define a new language

$$L=\{w_1w_2\mid \text{ there exist two words } x,y \text{ such that } xw_1\in L_1, w_2y\in L2\}$$

How do I show that $L$ is regular with equivalence classes?

My assignment allows the use of closure properties that all regular languages hold, but I cannot use $\text{rank} (L)$, as in show a limit to the number of equivalence class.

Can someone lead me in the right direction?

If you are allowed to use closure properties (as the formulation in the question suggests) then $xw_1\in L_1$ so $w_1$ is a suffix of $L_1$, similarly $w_2$ is a prefix of $L_2$. Taking suffixes and prefixes is a closure property of regular languages, and so is concatenation. That solves the regularity.

At what level do you want/need equivalence classes for your answer?

(added) For language $K$ its set of prefixes is defined as
$$\mbox{pref}(K) = \{ w \mid \mbox{there exists string $y$ such that } wy\in K  \}$$
precisely as used for $L_2$ in the operation in the question.

Given a finite state automaton for $K$ we get a FSA for $\mbox{pref}(K)$ by making all states final that have a path leading to a final state.

Also $\mbox{suff}(K) = \{ w \mid \mbox{there exists string $x$ such that } xw\in K  \}$.
Similarly one proves closure under suffix by making all states initial. As that is not commonly allowed for FSA that is solved by adding $\varepsilon$-transitions to all other states.

Your language $L$ based on $L_1,L_2$ equals $\mbox{suff}(L_1)\mbox{pref}(L_2)$, the concatenation of a suffix and a prefix language.

I could not find a reference to a question in this forum that dealt with the prefix/suffix operations, perhaps someone can help. Closure under prefix is a special case of closure under quotient.


Destination-based vs source-based routing I understand that destination-based routing builds the "route" from the destination backwards to the source (e.g. if using a spanning tree, then the tree is routed at the destination). With source-based routing the opposite is true: the route is build from the source onwards towards the destination.

However I don't understand the practical difference. How does it make a difference if I base my decision on the source or on the destination. Say, a shortest path algorithm such as Dijkstra's should give the same result regardless?

Could someone explain?

Destination-based routing is the typical, most common type of routing. For this, each message that we send contains the address of the destination and the forwarding decision process makes its forwarding decision solemnly based on this address (and independent of the original sender). i.e. We don't care about who sent the message, only about where it is supposed to go.

So, when constructing a routes, one thing we can do is root a spanning tree at the destination. This creates a path from all possible sources to that destination. This is called a "sink tree".

Source-based routing is the reverse of destination-based routing. The decision process is based on the source address. So, when sending a message, we only include the address of the sender (and not of the destination). The decision on where to forward the message is based on this source address. This means that the source could be sending the message to any host (we don't know exactly who). Therefore we create a spanning tree routed at the source (this is known as a "delivery tree") and the message is thus sent to every child in this tree.

Source-based routing is only really useful for doing some kind of broadcast / multicast (e.g. consider a delivery tree when building a multicast group).


Intuitive way to understand "Run-Length Encoding" Run-Length Encoding is the simple form of lossless data compression in which compression in which runs (execution) of data are stored as a single data value and count rather than as the original run (execution).

Now the definition is there but what's an intuitive way of thinking about this?

"Run" doesn't mean "execution". It means "sequence of identical things", as in "the football team had a run of wins."

So the intuition is simply that it's more efficient to say "ten $a$'s" than "$aaaaaaaaaa$".


Complexity of Problems and Ease of Verification Comparison-based sorting algorithms have a minimum worst-case complexity of $O(n \log n)$, while it is easy to check that an array is sorted in $O(n)$ time.

Are there other problems with proven minimum complexity $O(n^k)$ for some $k > 1$ that can be checked in $O(n)$ time? How high can $k$ get?

Trivial arbitrarily hard example based on the existence of an one-way function $f : \mathbb{N}^k \to \{0, 1\}$. The problem:

  Given a set $S$ of size $n$, can we choose a tuple $t$ formed from $k$ elements of $S$ such that $f(t) = 1$?

Since $f$ is one-way you must check all $n^k$ possible $k$-tuplets of elements from $S$, but checking whether a proposed solution is correct is simply $O(1)$ time.

However, if you're looking for interesting or deep results, I'm afraid you're out of luck. Forget "at least this hard to compute but easy to verify", we barely even have "at least this hard to compute" for almost anything. See this scarce list here.

Why are lower bounds so scarce? Because they essentially require omniscience in a certain subject area. You must prove that no matter how smart, doing better than the lower bound is impossible. It's as if you're simultaneously exploring every possible algorithm, finding their time complexities and showing that they're bigger than the lower bound. It's nearly impossible, which is why we barely have any proofs that go beyond some version of "you must read all input".


Minimizing $\max | x_i - \mu |$ How can we construct an algorithm which finds $\mu$ that minimizes $\max | x_i - \mu |$ in a linear time for an array of numbers $[x_1, x_2, \ldots, x_n]$?

I take $g = \max_{i\in \{1,\ldots,n \} } x_i$ and $l = \min_{i\in \{1,\ldots,n \} } x_i$, and $\mu = l + \frac{(g - l)}{2}$

Is it true and why it minimizes the function?

Since $|x| = \max (x, -x)$ for any $x \in \mathbb{R}$, we have $|x_i - \mu| = \max(x_i - \mu, \, \mu - x_i)$. Therefore,
$$
\max_i |x_i - \mu| = \max \left(\max_i (x_i - \mu), \, \max_i (\mu - x_i) \right) = \max (g - \mu, \, \mu - l),
$$
where $g = \max_i x_i$ and $l = \min_i x_i$.
Finally, the function $\max(g - \mu, \mu - l)$ has minimum at $\mu = \frac{l + g}{2}$.


Which language is accepted by this Muller Automaton? In my opinon the Language recognised is this:

$(a + b)^* (ab)^ω$
but the solution provided is: $(a + b)^* (a + b)^ω$

Did I missunderstand the acceptance condition or is the solution wrong?

My reasoning is:
As far as I understood a Muller Automaton does accept a run if all the set of all infinitely often visited states can be found as acceptance condition.E.g. if a run visits inf. often the states p & r and finitely often q then the set { p , r } has to be one of the set's of the acceptance condition.

I think in this case, that a word has to bounce inf. often between 2 of the 3 states (but is not allowed to visit the 3rd state inf. often). That means that in the end the word has to alternate between a & b inf. often after doing finitely often whatever it want's to do
=> $(a + b)^*$ ( = "do what ever you want to do finitly often and in the end") $(ab)^ω$ (= "iterate between a and b")

The given solution differs from my solution by accepting e.g. the following word:
$aba^ω$

The solution given is incorrect.

The first clue that this might be the case is that $(a+b)^*(a+b)^\omega$ is a strange way to write anything: any finite number of $a$s and/or $b$s, followed by infinitely many $a$s and/or $b$s is just infinitely many $a$s and/or $b$s, so the given language is just a strange way of writing $(a+b)^\omega$.

Muller automata accept if the set of states visited infinitely often is one of the specified sets.
To see that the automaton doesn't accept $(a+b)^\omega$, consider the word $a^\omega$. This is a member of $(a+b)^\omega$ but it's not accepted by the automaton, since the run on that word visits every state infinitely often, and $\{p,q,r\}$ is not an accepting set.

If exactly two of the automaton's states are visited infinitely often, then there must be a point at which the third state is never visited again. From that point onwards, the automaton can only alternate between the remaining two states, so any accepted word must end $(ab)^\omega$. While the automaton is still visiting all three states, it can read in any word so, yes, the accepted language is $(a+b)(ab)^\omega$.


Which of these two functions has a higher order of growth/complexity? Consider the following functions:
$$f(n)=2^{\log^*n} \text{ and } g(n)=\sqrt{2}^{\log{n}}$$
Using $\log{}$ properties I think that $g(n) < f(n)$, since:

$f(n)\sim n$,
$g(n)\sim n^{\frac{1}{2}}$, and
$n^{\frac{1}{2}}<n$.

However the book that I'm reading says otherwise.
What have I gotten wrong?

You have gotten wrong the 1st property, that $2^{\log^*(n)} \sim ~n$.  This is not the case.
The notation $\log^*(n)$ is the iterated logarithm, and the iterated logarithm grows much much slower than the logarithm, so $f$ grows much slower than linearly.


Maximum non-intersecting subset of circles We are given a set of circles, stored by their center points in an array $A$.  In particular, the center of the $i$th circle is at coordinates $(A[i].x, A[i].y)$.  All the circles have radius of $k$.

I want to find a subset of circles such that no circles in this subset intersect with each other, such that this subset is as large as possible.

I'm asked to find a way to solve this using a backtracking algorithm.  Rather than to do it with brute force, is there a effective way to prune some of the branches?

If it were me, I would encode this as an instance of ILP (integer linear programming) and let an off-the-shelf ILP solver deal with the backtracking and pruning.

Introduce $n$ variables $x_1,\dots,x_n$, where $x_i=1$ means that you include the $i$th circle in the subset and $x_i=0$ means you don't include it.  Add the following constraints:

$0 \le x_i \le 1$, for each $i$: this forces each $x_i$ to be either 0 or 1.
$x_i + x_j \le 1$, for each pair $i,j$ of circles that intersect each other: this enforces that you cannot choose two overlapping circles.

Now maximize the value of $x_1+x_2+\dots+x_n$ (this is the objective function).  Ask an ILP solver to find the optimal solution for you.  Internally, the ILP solver will likely use backtracking, pruning, branch-and-bound, and other sophisticated methods.

This will be a very efficient use of your time: rather than trying to program up each of those methods and debug your implementation, you can rely upon an existing well-tested ILP solver.  Also, given the amount of effort that has gone into optimizing ILP solvers, this approach might well perform better than any backtracking algorithm you're likely to come up with.


What is the asymptotic time complexity of the following 2 recurrences? $$T(n) = (\log n) \cdot T(n/\log n) + \Theta(n^i \cdot (\log n)^k)$$

and

$$T(n) = (n\log n) \cdot T(n/\log n) + \Theta(n^i \cdot (\log n)^k)$$

for any given $i$ and $k$.

I think it helps to know that for $0<j\leq 1$

\begin{equation}
\lim_{n\to\infty} \frac{n/n^j}{n/\log n} = 0.
\end{equation}

But what is a simple way to derive the asymptotic time complexity for the two given recurrences?

For the first recurrence, let $n_0 = n$ and $n_{t+1} = n_t/\log n_t$. As long as $n_t \geq \sqrt{n}$, we have $n_{t+1} \leq n_t/\log \sqrt{n_t} = n_t/((1/2)\log n)$, and so we reach $\sqrt{n}$ in $\log_{(1/2)\log n} n \approx \log n/\log \log n$ steps. It takes us another $\approx (1/2) \log n/\log \log n$ steps to get to $\sqrt[4]{n}$, and so on. If you do the calculation in full, you will probably find out that $n_m = O(1)$ for $m = O(\log n/\log\log n)$. In other words, for a constant fraction of the sequence $n_0,\ldots,n_m$, the value of $\log n_t$ is $\Theta(\log n)$. This justifies the approximation $n_t \approx n/\log^t n$. Under this approximation, we find out that (ignoring the $\Theta$)
$$
\begin{align*}
T(n) &\approx n^i \log^k n + \log n \cdot (n/\log n)^i \log^k n + \log^2 n \cdot (n/\log^2 n)^i \log^k n + \cdots \\ &\approx
n^i \log^k n + n^i \log^{k-(i-1)} n + n^i \log^{k-2(i-1)} n + \cdots
\end{align*}
$$
The answer now depends on the value of $i$. If $i > 1$ then the terms keep decreasing, and so we expect $T(n) \approx n^i \log^k n$. If $i = 1$ then the terms are roughly the same size. Since there are roughly $\frac{\log n}{\log \log n}$ of them, we expect the answer to be $T(n) \approx \frac{\log n}{\log \log n} n^i \log^k n$. If $i < 1$ then the terms keep increasing, and so we expect the major contribution to come from $$\log n_0 \log n_1 \log n_2 \cdots T(\mathit{const}).$$ By definition, $\log n_t = n_t/n_{t+1}$, and so
$$
\log n_0 \log n_1 \log n_2 \cdots = \frac{n_0}{n_1} \frac{n_1}{n_2} \frac{n_2}{n_3} \cdots \approx n.
$$
So in this case, $T(n) \approx n$.

If we do the same for your second recurrence, we get
$$
T(n) \approx n^i \log^k n + n \log n \cdot (n/\log n)^i \log^k n + n \log n \cdot (n/\log n) \log n (n/\log^2 n)^i \log^k n + n \log n \cdot (n/\log n) \log n \cdot (n/\log^2 n) \log n (n/\log^3 n)^i \log^k n + \cdots \approx
\sum_{t=0}^m \frac{(n \log n)^t}{\log^{\binom{t}{2}}n} (n/\log^t n)^i \log^k n =
n^i \log^k n\sum_{t=0}^m n^t \log^{-t(i-1)-\binom{t}{2}} n
$$
Let us denote the $t$th term in the sum above by $S_t$. Then
$$
\frac{S_{t+1}}{S_t} = \frac{n}{\log^{i+t+1} n}.
$$
For the largest $t$ we consider, $\log^t n \approx n$, and so we expect the largest term to be near the end. This implies that
$$
\begin{align*}
T(n) &\approx n_0 \log n_0 \cdot n_1 \log n_1 \cdot n_2 \log n_2 \cdots \\ &=
\frac{n_0^2}{n_1} \frac{n_1^2}{n_2} \frac{n_2^2}{n_3} \cdots \\ &=
n_0 n_1 n_2 \cdots.
\end{align*}
$$
The approximation $n_t \approx n/\log^t n$ seems harder to justify in this context, but it should give us a ballpark estimate:
$$
n_0 n_1 n_2 \cdots \approx
n \cdot \frac{n}{\log n} \cdot \frac{n}{\log^2 n} \cdots \approx \frac{n^{m+1}}{\log^{\binom{m}{2}} n}.
$$
We chose $m$ so that $\log^m n \approx n$, and so we expect the ratio to be $n^{\Theta(m)}$. In other words, $T(n) \approx n^{\Theta(\log n/\log \log n)}$.

All the estimates above are non-rigorous, and for this reason, they could be wrong. However, they point the way toward a more rigorous treatment.


Find CSG for $L = \{a^ib^jc^k \mid 0 \leq i \leq j \leq k\}$ I am trying to find a context sensitive grammar for the type-1 language

$L = \{a^ib^jc^k \mid 0 \leq i \leq j \leq k\}$

I can construct the first part with

\begin{align*}
S &\to aSbB \mid B \mid \epsilon\\
B &\to bB \mid \epsilon\\
\end{align*}

but how do I continue from there? I tried

\begin{align*}
S &\to aSbBcC \mid B \mid \epsilon\\
B &\to bBcC \mid \epsilon\\
CB &\to BC \\
C &\to cC
\end{align*}
but this does not seem to work e.g. $S \to aSbBC \to aaSbBCbBC \to aabBCbBC$

$$
\begin{align*}
S &\to XABS' \mid XBS' \mid XS' \mid XAB \mid XB \mid X \mid \epsilon \\
S' &\to ABCS' \mid BCS' \mid CS' \mid C \\ \\
BA & \to AB \\
CA & \to AC \\
CB & \to BC \\ \\
XA &\to aX \\
X &\to Y \\
YB &\to bY\\
Y &\to Z \\
ZC &\to cZ \\
Z &\to c
\end{align*}
$$

For the intuition behind this construction see this question.


Pumping Lemma: is it valid to "multiply the product of powers" in this case? I need to show that

$\qquad \displaystyle S = \{(10^p)^m \mid p \geq 0, m \geq 0\}$

is not a regular language using pumping lemma.

Can I multiply the product of the powers and express it to: $S = \{ 1^m 0^{pm} \mid \dots \}$ and apply the pumping lemma where I pump 1's then say that the language doesn't accept the new string?

You're right, the superscript in this context means concatenation.

To prove a language isn't regular, you use the fact that any regular language can be "pumped". First, find out what "pumping" a word means (I can't do your homework for you), and then show that your language can not be pumped, and thus, can not be regular.  Basically you will take a sufficiently long word that belongs to your language, and show that it cannot be broken up and pumped in such a way that it satisfies the pumping lemma.

Note that the converse of the pumping lemma is not always true: that is, if a language does NOT satisfy the pumping lemma, it may still be non-regular.  For this reason, the pumping lemma is used to exclude a language from a set of languages, and not to include a language in a set of languages (such as regular).  In other words, satisfying the pumping lemma is a necessary, but not sufficient, condition for a language to be regular.


Does every data type just boil down to nodes with pointers? An array or vector is just a sequence of values.  They can surely be implemented with a linked list. This is just a bunch of nodes with pointers to the next node.

Stacks and queues are two abstract data types commonly taught in Intro CS courses.  Somewhere in the class, students often have to implement stacks and queues using a linked list as the underlying data structure, which means we are back to the same "collection of nodes" idea.

Priority queues can be created using a Heap. A heap can be thought of as a tree with the min value at the root.  Trees of all sorts, including BSTs, AVL, heaps can be thought of as a collection of nodes connected by edges.  These nodes are linked together where one node points to another.

It seems like every data concept can always boil down to just nodes with pointers to some other appropriate node.  Is that right?  If it's this simple, why do textbooks not explain that data is just a bunch of nodes with pointers?  How do we go from nodes to binary code?

Well, that is basically what all data structures boil down to. Data with connections.  The nodes are all artificial - they don't actually exist physically. This is where the binary part comes in.  You should create a few data structures in C++ and check out where your objects land in memory.  It can be very interesting to learn about how the data is laid out in memory.

The main reason for so many different structures is that they all specialize in one thing or another. For example, it is typically faster to iterate through a vector instead of a linked list, due to how pages are pulled from memory.  A linked list is better to store larger sized types because vectors must allocate extra space for unused slots (this is required in the design of a vector).

As a side note, an interesting data structure you may want to look at is a Hash Table.  It does not quite follow the Nodes and Pointers system you are describing.

TL;DR: Containers basically all Nodes and Pointers but have very specific uses and are better for something and worse for others.


Decidability of the language of all deterministic LBA where all states are reachable I have a exam task with 3 parts. (b) is no problem. I got a solution for (a) but the way (c) is asked makes me wonder if I even understood (a)

(a) L := { < A > | A is a DFSA, where all states are reachable }. Is L decidable? Why or why not?

(b) M is a DLBA and k is the input length. There exists a function g(M,k) which returns the maximum number of steps a DLBA can possibly do, which halts on an input the size of k. Why?

(c) L' := { < M > | M is a DLBA, where all states are reachable }. Show that L' is semi-decidable. Use g(M,k) from (b)

My solution:

(b) Limited amount of configurations. I get that.

For example how I understand (a):
L is a language and every word of L is the encoding of a FSA. But only FSAs where every state can somehow be reached from the starting state or is the starting state.

So is it decidable?

My answer: Yes, for any word w you could check if its a valid FSA-encoding, if not: reject, if it is: Construct a FSA from this encoding and check if you can reach all states like this:

Mark the starting state;
Repeat until no new marked states:
   Mark all states you can reach from the marked states.
Check if all states are marked.
Reject or Accept

My Question:

Is (c) just semi-decidable and how do I use g(M,k) to show this?
Because I would think I could solve (c) exactly like (a) and show that it is decidable (which would mean it is also semi-decidable)

Edit: Hi, if you give me a downvote I would appreciate a comment on how to improve my questioning. I know it is a long post but I just try to lay out how I understand questions like this to be solved so you can correct me if I have key misunderstandings. I now reduced the amount of questions I asked and the length of my post.

After days of constantly refreshing this page in hope for an answer today I woke up and my very first thought might be it.

If all states are reachable and it is deterministic this means there has to be a set of inputs where every state  will once be reached.

semi-decidable Algorithm:

Validate if DLBA-Encoding and reject if not;     # returns 'no' on bogus
k = 0;
Repeat until every state has been at least once been reached {
   For every possible input w for the DLBA of the length of k {
      Simulate DLBA with w for g(M,k) steps while keeping record of the reached states;
   }
   k++;
}
return 'yes'

It will accept if all states are reachable

It will reject if not a valid DLBA-Encoding

It will run forever if valid DLBA but not all states are reachable

I figured out, that DLBAs can have states where there are a series of transitions leading from the starting state to those but they still can never be reached.
So just looking at transistions isn't enough


How is the difficulty of any problem (not just decition problems) classified? I have been studying Integer Programming and I find out that some optimization problems are referred to as P or NP-Hard, however, as I started to read about it, it turns out that those classes are just for decision problem. Thus:

What does it mean that an optimization problem ($\max\{f(c)\mid x\in X\}$) is NP or NP-Hard if they are not (necessarily) decision problems?
If an optimization problem ($\max\{f(c)\mid x\in X\}$) is not a decision problem, then, how is its difficulty classified?

When we say that the optimization problem $\max \{ f(x) : x \in X \}$ is NP-hard, what we really mean is that the following decision problem is NP-hard:

  Is there an $x \in X$ such that $f(x) \geq y$?

This turns optimization into a decision problem that can be analyzed using the complexity classes you know of.

There are also complexity classes specifically for functions or for optimization problems. Some examples are:

FP, the class of functions computable in polynomial time;
APX, the class of problems that can be approximated in polynomial time, and the associated classes APX-hard and MaxSNP;
PPAD and its friends, classes of problems of the general form "given $x$, find $y$ such that $P(x,y)$", where for each $x$ we are guaranteed that such a $y$ exists.


Understanding $O(2^n)$ time complexity due to recursive functions Consider the following binary recursive fibonassi program:

Algorithm binaryFib(k)  //k is assumed to be non-negative integer
   if (k <= 1)
      return k
   else
      return binaryFib(k-1) + binaryFib(k-2)
end binaryFib

The recurrence relation for above is:

$T(n) = T(n-1) + T(n-2)$

The run time complexity for the same is $O(2^n)$, as can be seen in below pic for $n=8$:

However if you look at the bottom of the tree, say by taking $n=3$, it wont run $2^n$ times at each level:

Q1. Wont this fact have any effect on time complexity or does the time complexity $O(2^n)$ ignores this fact?

Q2. I guess I can rephrase Q1 by eliminating above fact with following recurrence relation: $T(n) = 2 T(n-1)$. Does this recurrence relation still have same $O(2^n)$ time complexity?

Q3. Finally I want to generalize: Does the recurrence relation $T(n)=k\times T(n-1)$ have $O(k^n)$ time complexity?

If you look at the code, it is quite obvious that there are exactly fib(N) - 1 additions. Therefore the time complexity is $\Theta(fib(n))$.


High-level requirements for a Proof of "Saving to the Database" This question is about a few sentence description of what a proof would look like (and technologies / logics involved) for a complex api call through many layers. Trying to get a sense of the techniques and key points to watch out for. I understand it would take a lot of work.

In learning about formal proof and verification, I've come across Operational Semantics, Hoare Logic, and Matching Reachability Logic. All of them are pretty low-level and describe how to prove stuff such as a while loop with a few assignment / arithmetic operations, but that's it.

I am wondering what the general / high-level requirements are to prove something like "saving a record through some https API to the database", where it goes through the network (https) and through a bunch of servers finally arriving at an array of replicated databases like MySQL.

In unit testing, you would simply write a test that the method (let's say save()) creates the record. You would make a database query and see if the record matched the record you thought it would be.

I am wondering what it would entail to write a proof of this (at a high level, just a few sentence description is all). What things would need to be proven. If you can't write a proof, then what if you still wanted to at least partially prove the system's correctness. What it would take.

It seems like you could write a Hoare Logic statement such as:

{P}
save({ type: 'asdf', foo: 'bar', a: 'b' })
{fetch('asdf', 'latest') == { type: 'asdf', foo: 'bar', a: 'b' }}

That's at least better than nothing. But I'm not sure if you can write a proof with just that.

Then to know that it actually was in the database and not in some cache in the browser, you would have to know that fetch had a proof that it went through the network to some API, and that API request went to the database, and the database did whatever. That's basically what I'm wondering, if creating a proof for save starts off with the Hoare Logic statement like above, and then progressively you add more detail to the proof. In this way it's almost developed like via TDD. At some point, then, I'm wondering when you could say "it is proven".

The SoftwareEngineering.SE link gives the wrong answer for the right reasons. You can only ever prove anything with respect to a formal model. Verifying that that formal model accurately captures reality (or at least accurately captures the parts you care about for your purposes) is an informal process. In many applications of formal methods, one of the most time consuming and difficult parts is creating and validating the formal model. For example, for the CompCert project they had to make both a formal model for the behavior of C and a formal model for the behavior of the target processor (at least for the instructions they use). Both of these are massive undertakings on their own.

It makes no sense to "add more detail to the proof". Either a statement has a proof or it doesn't. It's proven if it has a proof. All proofs are equivalent for this purpose. What you can add more detail to is the formal model. Except "add more detail to" has the wrong connotations. You generally want the least detailed model that is accurate and for which you can prove your desired properties, e.g. correctness. The only reasons to change to a more detailed model is 1) you can't actually prove what you want with the original model, 2) the original model is wrong in which case your new model is not compatible with it, or 3) which is really a variant of (1), there is a different program that you could write that exploits those details to achieve the same functional behavior but different non-functional properties such as performance or implementation simplicity. In all these cases we need a new proof because we've changed the statement we're proving: either by changing the program or by changing the assumptions.

There are two aspects to the use of a formal model. First, as far as your program is concerned, it doesn't care if the database saves the data or even if the database exists. It only cares that the operations it uses behave as specified with respect to a given formal model. That formal model can be very high-level and abstract with no reference to any notion of "database" or "network" or "HTTP". However, it will likely be quite complicated to soundly capture the realities of the actual underlying systems. Second, at the systems level, you certainly do care whether the data was committed to the database as opposed to just being stored in some local cache. At the level of the program, there is absolutely no way for you to guarantee this. Your program could always be running in a sandbox that mimics any observable behavior. All you can prove at the program level is that your program will invoke some sequence of operations that putatively will lead to data being committed to the database. At some point you just have to accept based on empirical evidence that the chosen real world implementation faithfully implements the formal model. You can provide an implementation of the primitives of a high-level model with respect to a lower-level formal model that has been proven correct if you want to reduce how much you need to accept without (mathematical) proof.

The current state of play is that most programming languages lack publically available, normative (mechanized!) formal models let alone the underlying hardware. Ipso facto, most standard libraries, applications, operating systems, drivers, etc. are not proven correct since they have nothing with respect to prove their correctness. This is both in the sense that there isn't a formal model of what "correct" even means, nor is there a formal model of the implementation language so that you know what the implementations even do. In other words, in most cases we neither know what an implementation does nor what we even want it to do. This is why the artifacts (and tooling) produced by the CompCert projects and its related projects and by the $\mathbb K$ framework folks and several other groups are so important. Without these artifacts, you either use some massively over-simplified and weakly verified formal model that implicitly assumes millions of lines of codes are "correct" (spoiler: they aren't)1, or you invest man-centuries building a chain of trust. With luck, in the near-ish future some critical mass of formalization will be reached and proving the correctness of your program will become proportional to the complexity of your program and not the entire ecosystem.

1 While using an oversimplified formal model doesn't provide most of the benefits of "provable correctness", it does, in practice, do an excellent job of improving code quality by revealing mistaken assumptions in the code. Of course, the mistaken assumptions in your formal model have to be detected the old-fashioned way for the most part.


What are some concrete examples of what typed lambda constants are? I was reading the following and found the following paragraph that I didn't understand:

  Let us also consider a set Σ of typed λ -constants, that is, pairs σ : t,
  where t is some type. Like for type assignments, we assume that Σ
  does not contain constants with multiple types and let Σ(σ) denote
  the type t such that σ : t ∈ Σ.

can I have some concrete examples of what lambda-constants are?

With the simply-typed lambda calculus, constants are typically basic datatypes. For example, here is a way to encode booleans in this presentation's notation:
$$
\Sigma_B = \{ \mathrm{false} : \mathsf{bool}, \mathrm{true} : \mathsf{bool} \} \cup
           \bigcup_{T:\mathit{Type}} \big\{ \mathrm{if}_T : \mathsf{bool} \rightarrow T \rightarrow T \rightarrow T \big\}
$$
Note that we can't have a single “if” function: there needs to be one per type. To have a single “if” function that works with multiple types, you'd need to switch from the simply-typed lambda calculus to a typed lambda calculus with polymorphism. In the simply-typed lambda calculus, you have separate functions $\mathrm{if}_{\mathsf{bool}}$, $\mathrm{if}_{\mathsf{bool}\rightarrow\mathsf{bool}}$, etc.

The intended execution rules for these constants are
$$
\begin{align}
\mathrm{if}_T \: \mathrm{true} \: M \: N &\longrightarrow M \\
\mathrm{if}_T \: \mathrm{false} \: M \: N &\longrightarrow N \\
\end{align}
$$
But the choice of reduction rules doesn't affect the type theory. (We normally do want them to preserve types, i.e. the subject reduction property.)

For the type $\mathsf{bool}$, the constants $\mathrm{true}$ and $\mathrm{false}$ are known as constructors: they're ways to build new values of this type. The constants $\mathrm{if}_T$ are destructors: they're ways to take a value of this type and analyze it. Intuitively speaking, whenever a type is a ”data type”, it's defined by its constructors and destructors. An example of a kind of type that isn't a data type is function types, but even there you can think of lambda abstraction as a constructor for function types and application as a destructor. Constructors and destructors are a computational notion, not directly related to typing. (They do get related once you start viewing computation as a way to simplify typing proofs.)

Here's a second example with an encoding of signed integers ($\mathbb{Z}$). Note that this is just one possible encoding, a simple one from the typing perspective.
$$
\Sigma_N = \{ \mathrm{0} : \mathsf{int}, \mathrm{S} : \mathsf{int} \rightarrow \mathsf{int}, \mathrm{P} : \mathsf{int} \rightarrow \mathsf{int} \}
$$
This particular signature defines three constructors: $\mathrm{0}$ (zero), $\mathrm{S}$ (successor) and  $\mathrm{P}$ (predecessor).
You may want to combine booleans and integers. For typing purposes you can just put them together, but for computational purposes it's useful to add a way to destruct an integer, e.g. by adding a comparison function. Here I've made the comparison function piggyback on booleans so that it doesn't need to be polymorphic.
$$
\Sigma_{BN} = \Sigma_B \cup \Sigma{N} \cup \{\mathrm{le} : \mathsf{int} \rightarrow \mathsf{int} \rightarrow \mathsf{bool} \}
$$


Efficient algorithm for edit distance for short sequences I have an application that needs to compute billions of levenshtein distance between pairs of strings. The strings are short (70 in length) DNA sequences, consisting only of 4 characters. Also it can be assumed that one of the strings is fixed, i.e., we are comparing one fixed string to a billion other strings.

I know that the dynamic programming implementation of the levenshtein distance is $\mathcal{O}(m n)$, would like to know if there are any room for improvement. I found these two algorithms:

$\mathcal{O}(n + d^2)$ algorithm, in which $d$ is the edit distance by  Berghel et al. However I can't make the assumption that $d$ is small so it might not give any advantage
$log(n)^{\mathcal{O}(1/\epsilon)}$  approximation in $n^{1+\epsilon}$ time by Andoni et al. But I have two concerns regarding this:

Is this algorithm also fast in practice?
Does $log(n)^{\mathcal{O}(1/\epsilon)}$ mean the computed edit distance in worst case is $log(n)^{\mathcal{O}(1/\epsilon)}$ times the actual one? In that case it's too much.

Do you know of any other algorithm/idea/approach that might be applicable?

One approach is to build a Levenshtein automaton for the fixed string (see, e.g., here).  Given a string $x$ and a distance $D$, you can build a DFA that recognizes all strings that are at distance $\le D$ from $x$.  Thus, you can test whether a string is close to $x$ in $O(n)$ time, where $n$ is the length of the string.  I'm not sure what the space requirements are to store the DFA (they are linear in $m,n$, but might be exponential in $D$).

Alternatively, you could use an "early-out" algorithm for computing the edit distance.  You mentioned that you are only interested in the edit distance if it is less than some threshold $D$.  There is an "early-out" algorithm for computing the edit distance whose running time is $O(\max(n,m) \times D)$, which computes the edit distance if it is $\le D$ or else outputs "too big" if it is $>D$.  Basically, you do the standard dynamic programming algorithm for the edit distance, but only compute the elements of the matrix that are $\le D$ away from the diagonal.  In your case this might or might not be better than the other alternatives.


Different context-free grammars for the same language In context-free grammar, are both the following grammars correct for the same language?

$$L = \{a^mb^n : m, n \in N_0 \text{ and } m \ne n\}$$

(grammar one)

$S \to S_1 | S_2$

$S_1 \to A_1B_1$

$A_1 \to aA_1 | a$

$B_1 \to aB_1b | \epsilon$

$S_2 \to A_2B_2$

$A_2 \to aA_2b | \epsilon$

$B_2 \to bB_2 | b$

(grammar two)

$S \to S_1 | S_2$

$S_1 \to \epsilon | aA_1$

$A_1 \to aA_1 | aB_1$

$B_1 \to aB_1b | a$

$S_2 \to \epsilon | A_2b$

$A_2 \to A_2b | B_2b$

$B_2 \to aB_2b | b$

Is there a rule I could use to check whether the grammar is correct for the given language (other than trying all the strings that come to my mind)?

Grammar 1 matches a. Grammar 2 does not. So they are not identical, and at least one of them is not a grammar of your indicated language.

As Yuval Filmus indicates in a comment, the general question of whether two CFGs produce the same language is undecidable. Obviously, it can be decided in certain cases (such as this one); searching for a counterexample is usually straightforward, although it obviously won't terminate if the two grammars turn out to produce the same language.

For simple exercises like this one, you should be able to prove (or disprove) that a grammar produces a given language. A simple technique which often works is induction over the length of the string.


Relative Importance in Graph Theory I am working on an algorithm that ranks a set of nodes in a graph with respect to how relative this node is to other predefined nodes (I call them query nodes). The way how the algorithm works is similar to recommendation algorithms. For instance, if i want to buy an item from an online store, the algorithm will look at my preferences (and/or history of purchased items) and recommend new items for me. Applying this to graph theory, the set of nodes are items and my preferred items are the query nodes. The problem am facing right now is how to benchmark my results (i.e. I want to run recall and precision on my results) but I don't have a ground truth data. My question is: does anyone know a benchmark for this problem, if not, how do you think I can evaluate my results.

Note: My algorithm has nothing to do with recommendation algorithms (i.e. the application is different), but I gave this to deliver the general idea of the RELATIVE IMPORTANCE algorithms. I am looking for any dataset with benchmark that may help me in this context.

Edit: Based on some requests, I will explain my algorithm with more details. The algorithm takes as input: graph (can be directed or undirected, weighted or unweighted), and a set of query nodes (included in the graph). The algorithm will try to rank the nodes in the graph according to their importance with respect to the query nodes. The importance of a node increases as the relationship between it and the query nodes increases. Depending on the application, this relationship is quantified by a value (the weight of an edge) that reflects the level of association between two nodes. For instance, in the DBLP co-authership dataset, the relation between two nodes is the number of common papers between the two nodes (authors). Therefore, in this case, the algorithm will rank the authors in the DBLP graph according to how close they are to all query nodes (the predefined authors).
I hope that this is clear.

Thank you

You can for instance take as ground truth data the movielens dataset, remove some rating links between users and movies. You can rank your algorithm by counting the number of link that you can guess right. Usually machine learning algorithm also guess the rating score.


Are there any coP problems Is there a notion of coP problem?

Also is there a notion of every problem being reducible to one problem in P (like 3SAT in NP completeness)?

Take it as an exercise to prove that P=coP. In fact, any deterministic computation model is closed under complement.

Regarding your second question, P-completeness is a well-studied notion, and there are even books on it. We say that a problem in P is P-complete if every problem in P is logspace-reducible to it. Assuming that NC is different from P, any P-complete problem is not in NC. Back in the day, the class NC was considered to represent what can be solved in parallel, so P-complete problems were interesting since they provably (under the assumption that NC is different from P) couldn't be solved in parallel. Nowadays this interpretation of NC is less popular.

You might be tempted to define P-completeness the same way NP-completeness is defined, that is, using polytime reductions. However, under this definition all non-trivial problems in P are P-complete, the two sole exceptions being the empty language and its complement, another simple exercise.


Finding all solutions to an integer linear programming (ILP) problem My problem is to find all integer solutions to an ILP. As an example, I'm using an ILP with two variables, but I may have more than two variables. I describe the method I currently use to solve this problem near the end, but I'm interested in knowing if there is a proper and efficient algorithm or method for solving this kind of problem.

There is no objective function, but the constraints for this ILP are

$$
\begin{equation}
0 \leq -2x -y \leq 8 \\
0 \leq 1-x+3y \leq 5 \\
0 \leq 2+x-y \leq 2 \\
x,y \in \mathbb{Z}
\end{equation}
$$

Since this ILP has two variables, I can visually inspect the solution region by graphing the lines formed by the constraints, which are

$$
\begin{align}
y &\leq -2x \\
y &\geq -2x-8 \\
y &\geq \frac{1}{3}x - \frac{1}{3} \\
y &\leq \frac{1}{3}x + \frac{4}{3} \\
y &\leq x + 2 \\
y &\geq x
\end{align}
$$

By inspection, there are 6 integer solutions for $(x, y)$: $\{ (0,0), (-1,1), (-1,0), (-2,0), (-2,-1), (-3,-1) \}$.

However, my current method is to use linear programming with non-negativity relaxed and integers from branch-and-cut. I've tried using a set of four objective functions: minimize $x$, maximize $x$, minimize $y$, and maximize $y$. These give a smaller search area as

$$
\begin{equation}
-3 \leq x \leq 0 \\
-1 \leq y \leq 1
\end{equation}
$$

I then iterate over all valid integer tuples in that smaller area and filter it for tuples that satisfy the original constraints. The tuples that remain are all valid integer solutions.

"Linear programming" is an optimisation problem. The problem that you are trying to solve is to count lattice points inside a finite convex rational polytope.

This problem has a polynomial-time algorithm, the general case for which discovered by Alexander Barvinok in 1994. It appears that all modern algorithms are broadly based on this method. Barvinok & Pommershein's 1999 paper, An Algorithmic Theory of Lattice Points in Polyhedra, is probably the best introduction to the theory. (Actually, it appears that Barvinok has subsequently written a book or monograph; that might be even better.)

There are probably more recent developments than I'm aware of, but this will give you a starting point for chasing citations.


For practical computing purposes, every algorithm is O(1)? I am taking a course in algorithm analysis and the professor is arguing that using the negation of the definition for Big O, it can be argued that, for practical computing purposes, both the running time and the memory usage of every algorithm is O(1). How is this possible? How can it be proven?

Sure. Time and memory are both finite, thus $O(1)$. But that isn't a very interesting (useful) result. Complexity is studied precisely because we do care how much time (or memory, or whatever other measure is of interest) algorithms take as a function of the input (size), even if we aren't willing to wait "finite, but very large" time nor to equip the machine with "finite, but very large" memory. We'd want to have an idea of how long we have to wait, or how much memory is enough.


Amount of classes for a semantic segmentation neural network I am currently working on implementation of semantic segmentation of images neural network, and try to implement one of the already existing solution such as Fully Convolutional Neural Network 1.

Data that I am using is based on Pascal-Context dataset [2], which has additional labeling  to original 20-class PASCAL VOC dataset. This results in a dataset with over 450-classes.

Problem

Initial 20-classes do not not match classes that I would like to achieve for indoor scenes. Therefore, I have created a short list of 12-classes that I would like to capture, which are in Pascal Context 450-classes dataset.

I managed to convert the data and now trying to start training. I am following this tutorial [3] on Matlab, which provides an example of an Image with classes overlay and all pixels colored.

However, in my scenario, I only want to be able to distinguish elements such as tvmonitor, sofa, wall and ignoring all other elements, which might be there. Matlab tutorial states: "Areas with no color overlay do not have pixel labels and are not used during training."[

As you can see above, I have two classes present in the picture, but I am not sure whether I should also include class Background, which would put overlay on everything that is not within my list of classes, and include that as an additional class in my training or not.

In summary, I am wondering whether Background needs to be provided as an additional class to my list of the classes that I would like to classify or not, even if this background class usually takes majority of each of images. Would that result in everything being classified as background?

References:

1 https://github.com/shelhamer/fcn.berkeleyvision.org

[2] https://www.cs.stanford.edu/~roozbeh/pascal-context/

[3] https://uk.mathworks.com/help/vision/examples/semantic-segmentation-using-deep-learning.html#d119e321

It's hard to tell whether you are planning on doing image classification or object recognition/detection.

If you're doing image classification, you need each image to have only a single object, and the object needs to be in approximately the same position every time.  You train a neural network to output the label (which object it is).

If you're doing object recognition/detection, in the training set it's not enough to have a label for each image.  Rather, for each image you should have a list of the objects (labels) and the bounding box of each.  Then, you train a neural network to output the label (which object) and location (bounding box) of the object.  That requires a different architecture than object classification.

I suggest you spend some time reading up on object recognition/detection and how to do that with a neural network, since it sounds like you might not be familiar with that yet.

As far as the background class:  I'm assuming you mean a "none-of-the-above" class.  If you are doing image classification and you expect to have some images that aren't of any of the 12 labels, then yes, you should have a 13th label for "none of the above" (i.e., background), and your training set should contain examples of all 13 classes.  If you're doing object recognition/detection, that isn't necessary; instead, typically the training set needs to have realistic images that contain zero, one, or more objects, though that might depend on the specific architecture and approach for object recognition/detection you are using.


Syntax of recurrence formula not clear I have this task for Analysis of Algorithms module in university

$$
\begin{align*}
W, V &= \{v_1, v_2, v_n\}, S = \{s_1, s_2, s_n\}\\
G(W) &= \max~_{i:w_i\leq w} ~\{G(W-s_i) + v_i\}, G(0)=0\\
\end{align*}
$$

I am not sure what does the marked text mean in this recurrence formula. Because I think $W$ is a variable not an array so $i\colon w_i<w$ does not really make sense to me. Could someone please explain this to me?

The notation is a crossover between

$\qquad\displaystyle \max_{i}$

and

$\qquad\displaystyle \max \{ \dots \mid i \}$.

It means the same as

$\qquad\displaystyle \max \{ G(W - s_i) + v_i \mid 0 \leq i \leq n, w_i \leq W \}$,

guessing about the domain of $i$.


Existence / non-existence of a sequence with short longest increasing subsequence and decreasing subsequence? Can there exist any integer sequence $A$ of length $N$ with all unique elements such that the length of its Longest Increasing Subsequence as well as that of its Longest Decreasing Subsequence is less than $ \displaystyle \lfloor \frac{N}{2} \rfloor $?
If yes, then give an example of such a sequence. Otherwise, can anyone present a proof that there cannot exist such a sequence?
(Just to add some substance, can it be shown there can exist such sequences, given any arbitrary value of $ N > 1 $?)

The answer to the OP's question is, no if $N\le 7$ and yes otherwise.

For given any positive integer $r$ and $s$, the celebrated Erdős–Szekeres theorem shows that for any sequence of distinct real numbers with length at least $(r − 1)(s − 1) + 1$ contains an increasing subsequence of length $r$ or a decreasing subsequence of length $s$.
It turns out that bound, $(r-1)(s-1)+1$ is tight. That is, for any positive number $r$ and $s$, there is a sequence of distinct numbers with length $(r-1)(s-1)$ that contains no increasing subsequence of length $r$ and no decreasing subsequence of length $s$.
Here is such an example.
$$\begin{array} {}
&s-1, &s-2, &\cdots,&2, &1\\
&2(s-1), &(s-1)+ s-2,  &\cdots, &(s-1)+ 2, &(s-1)+ 1\\
&\vdots &\vdots &\vdots &\vdots &\vdots \\
&(r-2)(s-1), &(r-3)(s-1)+s-2, &\cdots, &(r-3)(s-1)+2, &(r-3)(s-1)+1\\
&(r-1)(s-1), &(r-2)(s-1)+s-2, &\cdots, &(r-2)(s-1)+2, &(r-2)(s-1)+1\\
\end{array}$$
Consider the numbers above, reading from left to right and then from top to bottom. In other words, the sequence is $s-1$ down to $1$, followed by $2(s-1)$ down to $(s-1)+1$, etc and finally followed by $(r-1)(s-1)$ down to $(r-2)(s-1)+1$, all in step of $1$.
It is easy to see that there is no increasing subsequence of length r and no decreasing subsequence of length $s$.
For example, when $r=s=5$, we have $$4,3,2,1,\ \, 8,7,6,5,\ \,12,11,10,9,\ \,16,15,14,13$$
which does not have increasing subsequence of length $5$ nor decreasing subsequence of length $5$.

If we let $r=s$, the section above implies that, for any positive number $N$, there exists an integer sequence of length $N$ with all unique elements such that the length of its longest increasing subsequence as well as that of its longest decreasing subsequence is at most $\lceil\sqrt N\rceil$. And $\lceil\sqrt N\rceil$ is the tight upper bound.
Since $$\lceil\sqrt N\rceil\ge \lfloor\frac N2\rfloor\ \text{ for all } N\le 7$$ and $$\lceil\sqrt N\rceil\lt \lfloor\frac N2\rfloor\ \text{ for all } N\gt 7,$$
the answer to the OP's question is, no if $N\le 7$ and yes otherwise.
For example, for $N=8$, we have sequence $3,2,1,6,5,4,9,8,7$.


BFGS vs L-BFGS -- how different are they really? I am trying to implement an optimization procedure in Python using BFGS and L-BFGS in Python, and I am getting surprisingly different results in the two cases. L-BFGS converges to the proper minimum super fast, whereas BFGS converges very slowly, and that too to a nonsensical minimum.

QUESTION: From my readings, it seems to me that BFGS and L-BFGS are basically the algorithm (quasi-Newton methods), except that the latter uses less memory, and hence is faster. Is that true? Otherwise, if they are more different, then how so?

Ultimately, I want to figure out if the difference in performance is due to some differences in the actual algorithms, or due to their implementation in the python SciPy modules.

EDIT: I am adding some data to support my claims of divergent behaviour from the two algorithms.

 RUNNING THE L-BFGS-B CODE

       * * *

Machine precision = 2.220D-16
N =          147     M =           10
This problem is unconstrained.

At X0         0 variables are exactly at the bounds
At iterate    0    f=  2.56421D+04    |proj g|=  1.19078D+03
At iterate    1    f=  2.12904D+04    |proj g|=  1.04402D+03
At iterate    2    f=  1.49651D+03    |proj g|=  2.13394D+02
At iterate    3    f=  6.08288D+02    |proj g|=  9.85720D+01
At iterate    4    f=  2.91810D+02    |proj g|=  6.23062D+01
...
At iterate  142    f=  3.27609D+00    |proj g|=  8.80170D-04
Time taken for minimisation: 36.3749790192

*** BFGS code ***

At iterate    1,  f= 21249.561722
At iterate    2,  f= 15710.435098
At iterate    3,  f= 15443.836262
At iterate    4,  f= 15386.035398
At iterate    5,  f= 15311.242917
At iterate    6,  f= 15211.986938
At iterate    7,  f= 15022.632266
...
At iterate  524,  f= 67.898495
...
Warning: Desired error not necessarily achieved due to precision loss.
Iterations: 1239
Time taken: 340.728140116

No, they're not the same.  In some sense, L-BFGS is an approximation to BFGS, one which requires a lot less memory.  BFGS and L-BFGS are explained in great detail in many standard resources.

Very crudely, you can think of the difference like this.  BFGS computes and stores the full Hessian $H$ at each step; this requires $\Theta(n^2)$ space, where $n$ counts the number of variables (dimensions) that you're optimizing over.  L-BFGS computes and stores an approximation to the Hessian, chosen so that the approximation can be stored in $\Theta(n)$ space.  Effectively, L-BFGS uses the approximation $H \approx M^\top M$ for some $k \times n$ matrix $M$ (I think).

Each step of L-BFGS is an attempt at approximating/guessing what the corresponding step of BFGS would do.  However, a single step of L-BFGS takes a lot less space and time than a single step of BFGS.  Consequently, you can do many more steps of L-BFGS within a particular time bound than BFGS.  Therefore, you might find that L-BFGS converges faster, because it can do so many more iterations within a given amount of time than BFGS can.

I don't know what a nonsensical minimum means, or why BFGS would converge to something worse than L-BFGS if both were allowed to run for an unbounded amount of time.


Calculating time complexity of two interdependent nested for loops Consider the following code segment :

for (int i = 1; i <= n; i++ ) {
    for (int j = 1; j <= n; j = j + i ) {
          printf("Hi");
    }
}

Here, the outer loop will execute $ n $ times, but the execution of inner loop depends upon the value of $ i $.

When $ i = 1 $ inner loop will execute $ n $ times.
When $ i = 2 $ inner loop will execute $ \frac{n}{2} $ times.
When $ i = 3 $ inner loop will execute $ \frac{n}{3} $ times.
$ \vdots \ \ \ \ \ \ \ \ \ \ \ \ \ \ \vdots \ \ \ \ \ \ \ \ \ \ \ \ \ \ \  \vdots  $
When $ i = n $ inner loop will execute $ 1 $ time

So complexity will be given by
$$
 \begin{align}
  T(n) &= \frac{n}{1} + \frac{n}{2} + \frac{n}{3} + \cdots + \frac{n}{n}\\
\\
       &= n \left( 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n} \right) \\\\
       &= n \sum_{k = 1}^{n} { \frac{1}{k} }
 \end {align}
 $$
I am not able to solve $ \sum_{k=1}^{n} \frac{1}{k} $. Upon searching I found that it is the $ n^{th} $ Harmonic number ( $ H_n $), but couldn't find any closed formula for it. How can I proceed further to calculate $ T(n) $?

The $n^{th}$ harmonic number can be approximated by the integral $\int_1^n \frac{1}{x} \mathrm{d}x$.

\begin{align}
H_n \approx \int_1^n \frac{1}{x} \mathrm{d}x = \left[ \ln x \right]_1^n = \ln n - \ln 1 = \ln n
\end{align}

The limit of $H_n - \ln n$ is $\gamma \approx 0.577$, which is the Euler-Mascheroni constant.

Therefore, we get
\begin{align}
H_n & = \ln n + \gamma + r(n) \\
r(n) & \in \mathcal{O}\left(\frac{1}{n}\right)
\end{align}

Since $H_n - \ln n$ is not exactly $\gamma$, we need some remainder $r(n)$, whose limit is $0$.

So we get $T(n) = n \ H_n = n\ln n + n\gamma + n \ r(n) \in \mathcal{O}(n \log n)$