How to make single cycle processor pipelined? I was asked that how can one make a single cycle processor pipelined on a CS course without any specifications regarding the design.

I suppose, that I should answer that what should be changed on architecture level.

I am familiar with the meaning of pipelining.

I came up with the following basic idea: registers should be added to hold the intermediate values between pipelining input and output, which should be controlled by a common clock (including i/o).

Is my idea a plausible answer to the question?

At my level, I do not think that I am supposed to give a working example for it, but I am happy so any.

If every complete operation takes one cycle, then pipelining using the same cycle time won't give you any advantage whatsoever.

What you would do is to split up each operation in various parts. First you make the cycle say four times shorter, so now each operation executes in four cycles. Then you split each operation into say five parts, and you have a first stage doing the first part and moving the results to the second stage, then a second stage doing the second part and moving it to the third stage, and so on. It will take all in all a little bit longer because you need the time to move data from one stage to the next.

And now you have five different stages, you can start pipelining. The first stage does the first part and moves the result to the second stage in the first cycle, and in the second cycle it starts work on the first part of the next instruction and so on.

You win because now the cycle time is four times shorter, so you can do up to four times more operations per second, working on up to five instructions at the same time.


Finding approximately collinear points my issue comes from image processing. The image below is for a better understanding of the problem. I have to detect three dots (shown in black, marked with red arrows). The other points I get from my image after processing it are shown in green. As you can see I get many more points from the image than just the black ones, due to other structures inside the picture. So I've got a set of points and I know that there are at least three of them that are on a curve which is approximately a line and the approximate distance between the points is also known. I need to find these three points from my set.

The algorithm should be able to detect whether there is such a structure in the picture or there isn't one.

A simple algorithm is to iterate over all ways to choose 3 of the points, and test whether those 3 satisfy your criteria (are approximately colinear, have the appropriate distances, etc.).  There are ${n \choose 3}$ such triples, so the running time of this algorithm is $O(n^3)$.

It is possible to improve on that.  Here is an algorithm whose running time is $O(n^2 \log n)$:

For each point $p$:

Sort the points by their slope to $p$.  In other words, for each point $q$, calculate the slope of the line connecting $p$ and $q$, and use this as the key to help you sort the points.
Look for two points $q_1,q_2$ such that the slope of the line connecting $p$ and $q_1$ is approximately the negative of the slope of the line connecting $p$ and $q_2$.  You can check whether such a pair of points $q_1,q_2$ exist by a linear scan over the sorted list built in the previous step.  For each such pair, test whether $q_1,p,q_2$ satisfy your criteria (are approximately colinear, have the appropriate distances, etc.); if they are, output them.

The running time is $O(n^2 \log n)$, since for each iteration of the outer loop you do $O(n \log n)$ work, and the outer loop does $n$ iterations.

The above algorithm sorts the list of points by their slope, to make it easier to find 3 points that are approximately colinear.  You could also sort the list of points by their distance to $p$, to make it easier to find 3 points at the prescribed distances.  It's hard to say a priori which one might work better, but you could certainly try them both.


graph isomorphism completeness of class X and not-X there are many classes of graphs proved GI complete & many questions related to GI on tcs.se eg [1] & many others.

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

[1] open problems related to GI

Apparently, with graphs of class $X$ and not-$X$ you mean graphs that fulfill a property $X$ and those that don't. It is common that say a graph problem has a different complexity when the input graph is restricted to a certain class of graphs. In this sense, graph isomorphism is no different. As for your question, it is easy to come up with plenty of (even large) classes of graphs. For example, consider graphs that have an even number of vertices, and those that don't. Both are GI-complete, so at least in general, there are no implications.

If this is not satisfying, you need to address what you mean by "non-trivial graphs", but I don't think this would turn out to be too fruitful.


Prove that this language is NP-Hard Given
$$\mathrm{\#3SAT} = \{ (w, y) \mid  w\text{ is a $\mathrm{3SAT}$ instance with at least $y$ satisfying assignments}\}\,,$$
prove that $\mathrm{\#3SAT}$ is NP-Hard.

I am currently stuck with this one.

Basically $\mathrm{\#3SAT}$ is the counting version of $\mathrm{3SAT}$ and to me it is seems clear that establishing membership in the language is more complex than establish the classic $\mathrm{3SAT}$ membership.

I'm trying to reason through the prover-verifier paradigm: let's say you have a $\mathrm{3SAT}$ instance, now suppose the certificate for that instance is $n$ bits. It is obvious that the certificate for the same instance but translated into $\mathrm{\#3SAT}$ with let's say $y=10$ would be at least $10n$ bits.  So if the first can be examined in time $t$ then the second will take at least $10t$ and so on. However I am not satisfied with this reasoning, it seems  incomplete and superficial. I would greatly appreciate your advice on how to proceed with this proof. Thanks in advance.

It seems that you're trying to prove that $\#\mathrm{3SAT}$ is in $\mathrm{NP}$. Since $\#\mathrm{3SAT}$ is $\mathrm{\#P}$-complete, and $\mathrm{\#P}$ seems to be harder than anything in the polynomial hierarchy, it's very unlikely that $\#\mathrm{3SAT}\in\mathrm{NP}$.

The error in your attempted proof is that your certificate doesn't have polynomial length. A satisfying assignment has length $\Theta(|x|)$ (the formula can't have more variables than its length, but it could be of the form $(x_1\lor x_2\lor x_3) \land (x_4\lor x_5\lor x_6) \land\dots$). The number $y$ could have any value between zero and $2^{|y|}-1$, so your certificate has length about $|x|2^{|y|}$, which is exponential in the input size.

However, the question asks you to prove that it's $\mathrm{NP}$-hard, not that it's $\mathrm{NP}$-complete. You just need to prove that there's a polynomial-time reduction from some $\mathrm{NP}$-complete problem to $\#\mathrm{3SAT}$.


Generating graphs such as found on Sedgewick's Algorithms book on the MST chapters I always wondered what the algorithm might be to generate graphs such as those found on Sedgewick's algorithms books (consider the picture on the left):

Could any one point me to the name (or algorithm) that creates such a graph over a 2D region? I am not interested in how to draw it or display it (or in any library).

From all I can see the (x, y) points are probably just randomly generated, but the edges between vertices don't seem to be randomly connecting any two vertices. Maybe the closer two veritces are the bigger the odds of a connection existing between them is?

Thanks

It appears to be a random geometric graph. Points are placed at random within an area, according to some distribution, and an edge is added between every pair of points whose distance is less than some threshold.

A common case is to distribute the points uniformly at random within the unit square and add edges between all pairs of vertices that are at distance at most $d$ from each other, for some constant $d$. In other cases, the threshold might depend on the number of vertices.


State complexity of converting epsilon-NFAs to NFAs without epsilon transitions I am well-aware of the result showing that one can convert an epsilon-NFA (that is, an NFA with epsilon transitions) $A$ to an NFA without epsilon transitions $A'$, where $L(A) = L(A')$.

Is there a similar result comparing the state complexities of $A$ and $A'$? That is, if one has an epsilon-NFA $A$ with $n$ states, is it true that there exists an equivalent NFA without epsilon transitions $A'$ that also has $n$ states?

Yes, we can transform an epsilon NFA into a NFA by keeping the same state set, basically adding new edges. If there is an $\varepsilon$ path from state $p$ to state $q$, and an edge from state $q$ to state $r$, then add an $a$ edge from $p$ to $r$. Also, if from state $p$ we can reach a final state then state $p$ can be made accepting. After these two steps we can remove the original $\varepsilon$ edges without changing the language.


Can one determinize finite automata over infinite trees? I'm currently considering deterministic, nondeterministic, universal, and alternating automata over infinite words and trees, with Büchi, co-Büchi, Muller, Rabin, Streett, or parity acceptance conditions.

I know that over words, all these automata accept the same languages, except deterministic and universal Büchi automata, as well as deterministic and nondeterministic co-Büchi automata.

I also know that over trees, nondeterministic and alternating Muller, Rabin, Streett, and parity automata accept the same languages, and strictly more languages than nondeterministic and alternating Büchi automata.

But I hardly know anything about deterministic tree automata, and I'm having a hard time finding more in the literature. And this captures my main question, whether one can determinize nondeterministic automata over infinite trees.

After all, they are definitely used. For example, in reactive LTL synthesis, we often convert the formula to a nondeterministic Büchi word automaton, then to a deterministic parity word automaton, from which we derive a deterministic parity tree automaton.

Also note that I didn't mention the co-Büchi case when it comes to trees. I just know that, again in reactive LTL synthesis, we can alternatively convert the negated formula to a nondeterministic Büchi word automaton, then to a universal co-Büchi word automaton for the original formula, from which we can derive a universal co-Büchi tree automaton. But that alone doesn't really say anything about the relation of deterministic parity tree automata and universal co-Büchi tree automata, or does it?

This may be not explicitly spelled at many places in the literature, as deterministic tree automata are unable to capture specifications that are only expressible in branching-time logics.

Take for instance the property "There exists a node in the tree labeled with atomic proposition $x$" - this is equivalent to the CTL formula $\mathit{EF\,} x$.
This one cannot be represented as a deterministic tree automaton, but is easy to express as a non-deterministic Büchi tree automaton.
The reason is that a tree automaton accepts a tree $\langle T, \tau \rangle$ if all branches in the run tree for $\langle T, \tau \rangle$ are accepting. With non-determinstic tree automata, one can route the obligation to see an $x$ to somewhere in the tree. With deterministic automata, this is just not possible and thus one can only express $\mathit{AF}\, x$ in this form.

Hence, non-deterministic tree automata cannot be determinized in general.


What should I do with a bunch of 16-17 year olds to get them interested in computer science? I'm going to be involved with a sort of 'open day' at my university in a few weeks. As part of this time, I (along with a coworker) am being given a whole bunch of high-school level students for two hours, as well as a computer lab big enough to contain them all, and I have to do some kind of activity or set of activities with them to encourage them to do computer science (at my university, ideally, but in general also). I am at an absolute loss as to what to do here, and welcome any and all suggestions.

You can have them draw pictures using context-free grammar. context free art This also works for people who never programmed before and scales to experienced programmers. The basic language is easy enough to explain in maybe half an hour.
Learning something about geometry using Turtle graphics should be nice too. Logo was designed for children, so highschool students should have no problem. There are nice videos about children using Logo on youtube
If you can get your hands on some MindStorms robots, programming them is lots of fun.
There are a variety of programming games in which you program robots to fight each other, or assembly programs that try to overwrite each other in a virtual machine. Wikipedia on the topic, related stackoverflow question
You can also think about some kind of hardware project. Making a microcontroller blink a LED depending on the number of unread e-mails in your inbox for example.
Have them implement different maze generation algorithms, try to come up with criteria that make mazes "difficult for humans". If time permits extend the algorithms to include not only corridors but also rooms.
Buy a couple of Arduinos and LEDs. Let them program the blinkenlights.


Does $f(n) + g(n) = O(g(n) \cdot f(n))$ hold? I would like to know if this statement is true:
$f(n) + g(n) = O(g(n)\cdot f(n))$.

I thought of giving a counter example by defining:
$f(n) = 3n^2$
; $g(n) = n$ which will give us that $O(3n^3) = n^3$ but i'm not sure if it's possible to say that $O(3n^3) = 3n^2 + n$ because I suspect that it might be right because of the definition of Big O. And if that's right that means that the counter example i gave is not good.

Is this a valid approach?

I don't get what you do with your choice of $f$ and $g$ but they don't work as a counter-example.

Here is how you see that:

$\qquad f(n) + g(n) = 3n^2 + n \in \Theta(n^2) \subseteq O(n^3) = O(f \cdot g)$.

See our reference question on how to show this.

It is easy to see that the same happens for all pairs of increasing functions:

$\qquad f+g \in \Theta(\max(f,g)) \subseteq O(f \cdot g)$.

So if you want to have a chance at disproving the claim, you'll have to look for decreasing functions -- if your definition of Landau symbols admits such.


Why is software emulation of alternative architectures so hard/slow? I recall hearing briefly about this back in one of my CS courses on hardware, but I can't recall many of the details, nor can I find anything online that talks about it. A search on Google only yields a bunch of pages about Android emulators and people complaining that PCSX2 is slow. I'd like to know, in general, why software emulation of hardware is inefficient.

Can anybody point me to a good resource or explain briefly here?

If the underlying machine is similar to the simulated one, you can run most code natively (no speed loss unless there are hard to handle instructions or other characteristics, this is the "virtualization" business). If it is very different, you have to really simulate each instruction (for a cost of half a dozen or so native instructions for a typical machine). If it is important enough, you can use tricks like JIT compilation to native code to speed it up.


Sorting a large list of test scores You have a large list (say N > 10000) of test scores which you would like to sort. The test scores are between 1 and 100. What is quickest way to sort the list?

First thought. We have a O(N log N) bound, but we also have additional information about the quantities in the array, so I think we could do better.

Second thought: should we use hash tables, do we care about duplicates? Cant see how to use hash tables.

Third thought: does this have something to do with radix sorting? no idea.

Fourth thought: Could we sort this list by creating another list, and then pass through the original counting frequencies of elements occured. But would we need another pass to create a larger sorted list, which would be O(N^2). ie too large.

Is this a very easy question or a very hard question?

This is a very easy question, assuming all scores are integers.

Here is the simplest algorithm in plain words. We will initiate count, an integer array of 100 zeros. For each score s, we will add 1 to count[s]. To produce the wanted sorted scores, we will output count[1] 1s, count[2] 2s, ..., and finally count[100] 100s.

This kind of sorting algorithm is called counting sort.

The case of more than $N>10000$ test scores that are between 1 and 100 is a prime usage of counting sort. The time complexity is $O(N)$ and the space complexity  is bounded by some small constant multiple of 100.

You may want to check counting sort for more information.


What does it mean to be "independent of machine model"? I have often heard people mention off-hand that the class $\mathsf{P}$ is "machine-independent", or "independent of machine model", or "invariant under change of machine model" - something to do with subroutines or composition or something. My question is: What precisely does that mean? or, what precisely does it mean to be independent of the choice of machine model?

It makes sense to me that invariance under change of machine model - whatever that means - would make $\mathsf{P}$ a theoretically natural class to study, sort of the same way that Euclidean geometry is interested in the notions which are invariant under similarity, or linear algebra is interested in the notions which do not depend on a particular choice of basis. (The analogy is not entirely accurate, as those fields are only interested in such invariant notions, while computer science is still interested in properties of particular machine models.) While I understand what it means to be independent of the choice of basis, I don't understand what it means to be independent of the choice of machine model. Is there even a unique such concept, or are there several different concepts used in different contexts?

I've talked about $\mathsf{P}$ as a specific example, but what other commonly-studied ideas (in complexity theory or otherwise) are machine-independent in the same sense that $\mathsf{P}$ is? Are there ones that are not?

Thanks for helping to clear this up for me.

The class $\mathsf{P}$ is usually defined as the class of decision problems solvable in polynomial time by (one-tape) Turing machines. However, you get the same class if you replace "one-tape Turing machines" by "multi-tape Turing machines", "RAM machines", "machines running C natively", and many other machines. That's what is meant by the class being independent of the machine model.

Other classes, such as $\mathsf{TIME}(n)$, are very much dependent on the machine model: there are (I think) languages which can be computed in linear time on a two-tape Turing machine but not on a one-tape Turing machine.

The reason we are happy that $\mathsf{P}$ is machine-independent is that it makes $\mathsf{P}$ a very natural class. You don't have to ask yourself whether the correct model is Turing machines with one tape, two tapes, or more: all definitions result in the same class. The same cannot be said about $\mathsf{TIME}(n)$, for example.


Breadth-first forest I was reading CLRS about BFS and DFS, and the algorithms presented therein, which I take to be somewhat standard, constructs a forest in DFS that includes all the nodes, whereas BFS only constructs a tree from a chosen node $s$, and leaves out all the other nodes that are not reachable from $s$.

It seems the BFS can be adapted to construct other trees to include non-reachable nodes from $s$ and form a "BFS forest", analogous to operation of the DFS. What is the reason for constructing a forest in DFS, but only a tree (that excludes unreachable nodes) in BFS?

This asymmetry reflects a "philosophical" difference between the two algorithms.
Let us think for a moment about what each of them is trying to achieve.

DFS investigates properties related to the structure of the graph as a whole: a few examples among the many are finding strongly connected components, topological sorting, finding cycles, testing biconnectivity, testing planarity. In all those cases the output forest has a very direct and concrete meaning. For example, the usual classification of the edges as tree, forward, back or cross tells us something about what these edges "do" in the graph we are exploring.

On the other hand, BFS is normally used to determine distances w.r.t. a pre-selected node; even applications that do not explicitly mention such distances, such as testing bipartiteness, are somewhat related to the general idea of counting the steps taken in a path.

However, distances from different sources behave somewhat inconsistently: reachability sets of different nodes may be intersecting, and distances from the two original roots could be drastically different. Furthermore, when running DFS we don't care where we started searching -- as emphasized by the fact that DFS takes no input other than the graph itself -- but the output of a BFS is a function of its starting node: what would a BFS forest even mean?

Perhaps you might be able to build a structure along the lines of a depth first forest considering the minimum pairwise distances between all nodes, but it would be something very different and you wouldn't be able to get that kind of information from a single breadth first search, anyway.


Is there a fast algorithm for computing the rolling mode of an array of integers? I was wondering if there exists an efficient algorithm for calculating the "rolling mode of an array of integers.

By rolling mode I mean that we have an array of integers of size $n$ and a sliding window of size $k$ and we we want to compute the mode for each window in the array.
 There is an algorithm to do this in $O(n*k)$, by using a hash table in which we store the frequency of each integer. We can update this structure in $O(1)$ time, but to find the integer with max frequency we need $O(k)$ which gives the total running time.
 I was wondering if there exists a faster algorithm(Perhaps a data structure that can index the values both by frequency and value).

Maintain two data structures as you move along.

A hash $H$ table of frequencies.
An array of sets $A$ containing the integers in each frequency. So $A[1]$ is the set of all integers that occur once in the window, $A[2]$ all that occur twice, etc.

When you move the window, you need to do two updates, one to increment a frequency of the new integer and one to decrement the frequency of the integer that left the window. For both the process is similar:

Look up the frequency $f$ of the integer in $H$ in $O(1)$ time.
Remove the integer from set $A[f]$ and add it to $A[f \pm 1]$ in $O(1)$ time (using hash sets).
Increment/decrement the frequency in $H$ in $O(1)$ time.

You don't need to track $A[0]$. The mode is any of the integers in the highest $A[f]$ which is non-empty, which you can keep track of in $O(1)$ time.

The total runtime is $O(n)$.


find if a string is periodic using a suffix tree, and prove it A  string s of  length n is  periodic  if  there  is  a  string $u$ of  length <= n/2 such  that $s = u^ku'$, where  $k$   is an integer >=2, $u^k$ is the concatenation of k copies of  $u$ , and $u'$ is a
prefix of u.

The smallest period of $s$ is the shortest $u$ (largest  $k$) for which this holds.

For example, if s=ACACACACA, then k=4, u=AC, u'=A.

I want a linear-time algorithm for determining if s is periodic.

This SO answer gives a nice lead for a suffix tree solution. I want to use it, but I can't prove that it will work if and only if s is periodic.

Can you sketch it for me?

It's wrong. Consider $aaaabb$, so you'll find that $aaa$ repeat twice and consider it as an answer, while it is obviously not.

Check each suffix with length $n>l\ge\frac{n}{2}$. If it's also a prefix of $s$, $s$ is periodic and $u$ is the prefix with length $n-l$. If you can't find such suffix $s$ is not periodic. The proof is straight forward: $s[i]=s[i+n-l]$ for $1\le i \le l$. So you can easily prove that $s[n-l+1..2(n-l)]=u$, and so on. Since $n-l\le\frac{n}{2}$, $u$ repeat at least twice. The converse is similar, by proving $s[i]=s[i+len(u)]$.

KMP or Z-algorithm are sufficient to do this, but if you really need a suffix tree solution:

Check each node on the path from root to the leaf which represents the whole string. If a node on this path represents a suffix with length $\ge\frac{n}{2}$ (except the whole string), we find the answer. (Note that each node on this path represents a prefix.)


Understanding the P2||CMax scheduling problem I have a problem with understanding the $P_2 \mid \mid C_\max$ problem which is also known as Tasks Scheduling on Multiple Processors.

In fact, in my case I need only one processor (but the problem is usually described for 2 or more so let it be). I understand what is all about: given a set of tasks with constant delay time and priority the algorithm should find the best permutation of them so that the total delay time is the smallest one.

And now is my question: if the delay is constant for each task, so how come different permutations provide different total delay?

Taking apart the notation, here is what we have:

Two identical machines.
$n$ jobs with equal duration $p$.
No release dates or deadlines, i.e. $r_i = 0$ and $d_i = \infty$ for all $i$.
No extra features.
Objective function is maximum completion time.

It is true that all schedules without idle time have the same completion time in this setting. However, it still takes linear time to actually write down a schedule.

I guess this an easy exercise that is supposed to get you accustomed to notation and working in the model, and will maybe be extended to more complicated $\beta$.

Also, algorithms for this problem may be used as a subroutine, for instance for computing lower bounds in branch-and-bound algorithms for $P_2 \mid \beta \mid C_\max$ problems with non-trivial $\beta$.

Note: The number of processors can make the (conjectured) difference between polynomial and NP-complete complexity.


How to find the maximum independent set of a directed graph? I'm trying to solve this problem.

  Problem: Given $n$ positive integers, your task is to select a maximum number of integers so that there are no two numbers $a, b$ in which $a$ is divisible by $b$.

I have to find the Maximum independent set and the size of this set.   The size can be found by König's theorem. But how can I find the Maximum Independent Set (i.e. which vertex are part of the set).

I did some search also and found something here:

If removing a vertex does not change minimum path cover then I can get the desired  result without that vertex.

But I don't understand the underlying theorem. Any help will be greatly helpful.

You are trying to find the width of the poset defined by the given subset of integers and the divisibility relation. The width is the maximum number of anti-chains, which is the same as the maximum set of incomparable elements in the poset.

This corresponds exactly to the maximum independent set in the Comparability Graph, where each integer is a vertex and there is an edge from $u$ to $v$ if and only if $u$ divides $v$.

Finding the maximum independent set in general is a hard problem, but comparability graphs are a special case for which efficient algorithms exist.

Dilworth's Theorem characterizes the width of any poset as a partition of the poset into chains (source to sink paths in the directed comparability graph). Dilworth's Theorem is equivalent toKönig's theorem on Bipartite Matching, which, as you suggested, leads to an algorithm.
The bipartite graph you construct in order to use Konig's theorem and find the maximum independent set via a bipartite matching is described simply in the above Wikipedia link. For completeness, we include it here (in annotated form):

"Define a bipartite graph $G = (U,V,E)$ where $U = V = S$ [the set of integers] and where (u,v) is an edge in $G$ when $u < v \in S$ [integer $u$ divides integer $v$]. By König's theorem, there exists a matching $M$ in $G$, and a set of vertices $C$ in $G$, such that each edge in the graph contains at least one vertex in $C$ and such that $M$ and $C$ have the same cardinality $m$.

"Let $A$ be the set of elements of S that do not correspond to any vertex in $C$; then $A$ has at least $n - m$ elements (possibly more if $C$ contains vertices corresponding to the same element on both sides of the bipartition). Let $P$ be a family of chains formed by including $x$ and $y$ in the same chain whenever there is an edge $(x,y)$ in M$; then $P$ has $n - m$ chains. Therefore, we have constructed an antichain and a partition into chains with the same cardinality."

The set of distinct vertex labels (integers) in $A$ is the answer to your question.

Section 3 of the paper Online Algorithms for Dilworth's Chain Partition by Ikiz and Garg describes two different offline algorithms to compute the chain partition, and thus the independent set you are looking for. One of the algorithms is based on the Bipartite matching method.


How to prove that the dual of the dual of a connected planar graph $G$ is isomorphic to $G$? I find in many references the fact that if $G$ is a connected planar graph, then for any embedding, $G^{**} \cong G$. However, all those references either say that this fact is trivial, or give the proof as an exercice.
I am ok that this is clear on a small graph, with a nice embedding, but how can we prove this property rigorously?

Work In progress.
Feel free to contribute filling up the arguments that are incomplete.

Definitions:
Before proving anything we need to make it precise what is it what we are trying to prove.

Planar graph: A graph that can be embedded in $\mathbb{R}^2$.(1)
Plane graph: A planar graph together with a particular embedding $G\hookrightarrow\mathbb{R}^2$. I will call a plane graph just by the name $G$ of the graph itself. We call faces of a plane graph to the connected components of the complement $\mathbb{R}^2\setminus G$. We can also assume the plane graph embedded in the two dimensional sphere $S^2$. That way we don't need to distinguish one of the faces which will be unbounded in the plane.
Polygon: A simple closed path in a graph without a proper closed subpath.
Cut-set: A minimal set of edges of a graph that, if removed, would increase the number of connected components of the graph.
Combinatorial dual: A graph $G^*$ is said to be a combinatorial dual (sometimes also called algebraic dual) of another graph $G$ if there is a bijection between their edges such that the polygons of one of them correspond to the cut-sets of the other, and vice versa. A graph can have no combinatorial duals, or it can have multiple non-isomorphic combinatorial duals.
Geometric dual: A geometric dual $G^*$ of a plane graph $G$ is a graph obtained by placing a vertex on each face of $G$. There is going to be an edge of $G^*$ for each triple $(f_1,f_2,e)$ where $f_1,f_2$ are faces of $G$ such that their closures contain the edge $e$ of $G$. The edge corresponding to this triple will be embedded in such a ways that it connects the vertices of $G^*$ inside $f_1$ and $f_2$. It will be contained in $f_1\cup f_2\cup e$ and intersects $e$ only at one point that it is not a vertex of $G$. For this definition to make sense a couple of results from topology are needed. In particular, two results that are quite intuitive, but very hard to prove. These are Jordan curve theorem and Jordan-Shoenflies theorem. Using these results it can also be proven that the geometric duals of a plane graph are isomorphic. So, we can talk about the geometric dual of a plane graph.

It is a theorem of Whitney that a graph is planar if and only if it has a combinatorial dual. Moreover, each combinatorial dual of a planar graph arises as a geometric dual of an embedding of the graph in the plane.

$G^{**}=G$
As you see above, this statement can mean different things. It could mean that $G$ is a connected plane graph and we are taking geometric dual a couple of times. It could also mean that $G$ is a planar graph and we are taking geometric dual a couple of times after fixing an embedding. Finally it could mean that we are taking combinatorial dual a couple of times of a connected planar graph.
Note: We also need to use the modern definition of connected in which the empty graph $0$ is not connected. Note that the dual of the empty graph is $K_1$ and the dual of $K_1$ is itself. So, $0^{**}=K_1\not\cong 0$. I am making the clarification because although it is becoming more widespread defining the empty graph as not connected, still not everyone does that.

Geometric double dual.
I think this one is the simplest, assuming that we leave the topological results as known.
Assume that $G$ is a plane graph and $G^*$ is its geometric dual. We assume $G^*$ to be a plane graph, which embedding satisfies the properties that we mentioned in the definition above. Let's do induction.
If $G=K_1$ we have that $G^*=K_1$, just another point of the plane, and therefore $G^{**}\cong G$. Then $G^{**}\cong G$.
We want to assume that the theorem is true for all graphs that have smaller number of vertices or edges than $G$. The following two lemmas allow use to construct the isomorphism by removing vertices of $G$ of degree $1$ or edges that are not cut edges. Then we just extend or modify the isomorphism that we have from the inductive assumption on the smaller graph. The lemmas below are quite intuitive, but they make use of Jordan's curve theorem. So, the main annoying thing to write down the arguments is to make it as explicit as possible the point in which this big theorem is used.
Lemma 1: Assume $G$ is connected plane graph with an edge $e$ that is not a cut edge of $G$. Assume that $(G\setminus e)^{**}\cong G\setminus e$. Then $G^{**}\cong G$.
Proof: Since $e$ is not a cut edge, the two faces2 of $G$ incident with $e$ are different. Call those faces $f_1$ and $f_2$. Deleting $e$ from $G$ fuses $f_1$ and $f_2$ into a single face $f$. Faces of $G$ that are adjacent to $f_1$ or $f_2$ become adjacent to $f$ in $G\setminus e$. In the dual, the vertices $f_1^*$ and $f_2^*$ of $G^*$ get replaced by a single vertex $f^*$ of $(G\setminus e)^*$. Any vertex of $G^*$ that is adjacent to $f_1^*$ or $f_2^*$ is adjacent to $(G\setminus e)^*$. Therefore, the function sending $f^*$ to the identification of $f_1^*$ and $f_2^*$ in $G^*/e^*$ and that is the identity on all other vertices is an isomorphism. ... $\square$
Lemma 2: Assume that $G$ is a plane graph that has a vertex $v$ of degree $1$ and that $(G\setminus v)^{**}\cong G\setminus v$. Then $G^{**}\cong G$.
Proof: Since $v$ has degree $1$, then it is adjacent to only one face $f$ of $G$. If $e$ is the edge of $G$ incident on $v$ and $f^*$ is the vertex in $G^*$ that is in $f$, then there is a loop $e^*$ incident on $f^*$ that contains in its interior $v$ and no other vertex of $G$. Here we are implicitly using Jordan's curve theorem. By assumption $(G\setminus v)^{**}\cong G\setminus v$. By jordan's curve theorem the interior of $e^*$ is a face $v^*$ of $G^*$ and this face is adjacent to exactly another face. Therefore, extending the isomorphism of $(G\setminus v)^{**}$ and $G\setminus v$ by sending $v$ to $v^*$ and $v^*$ to $v$ give us an isomorphism of $G^{**}$ and $G$. ... $\square$
To complete the induction observe that we can apply Lemma 1, if the graph has some non cut-edge. If $G$ has no non cut-edges, then it must be a tree. So, we can apply Lemma 2, as long as $G$ has more than one vertex. If it is a tree and has one vertex, then it is $K_1$, which is the base case.

Combinatorial double dual
For this we use Whitney's theorem. If $G$ is a connected planar graph and $G^*$ a combinatorial dual, then there is an embedding of $G$ and $G^{*}$ such that $G^*$ is the
geometric dual of $G$. From the proof above it follows that $G$ is a geometric dual of $G^*$ and therefore a combinatorial dual of $G^*$. Now assume that $G^{**}$ is a combinatorial dual of $G^*$. Consider an embedding of $G^*$ and $G^{**}$ such that $G^{**}$ is a geometric dual of $G^*$. Using Jordan-Shoenflies theorem we can extend ... [This one seems harder. I don't have a complete plan yet. We probably need to extend the new embedding of $G^{*}$ (in which $G^{**}$ is a geometric dual) to embed also $G$ and show that it is also a geometric dual of $G^{*}$ in this embedding.]
Footnotes:

The topology on the graph is that of a CW-complex.
There are at most two faces incident on an edge. This follows from Jordan-Shoenflies theorem.


Algorithm for constructing BST from post-order traversal Given a post-order traversal of Binary Search tree with $k$ nodes, find an algorithm that constructs the BST.

My Algortihm

  Let $n$ represent the next element to be inserted.

  Let $P(y)$ represent the parent of node $y$.

  We will read the traversal in reverse. The last element of the traversal is the root. Let $l = root$. $l$ will represent the element
  last inserted in the BST (except for the 3rd case below- where it will
  change to the parent).

  Loop the following till there's no element left to be inserted

  if $l<n$ then $n$ is the right child of $l$. For the next insertion,
  $l$ changes to it's right child and $n$ becomes the next element(in
  reverse order of traversal ).
  else, if $l>n$ and $P(l)<n$ then $n$ is the left child of $l$. For the next
  insertion, $l$ changes to it's left child and $n$ becomes the next
  element(in reverse order of traversal).
  else, if $l>n$ and $P(l)>n$ then  $l$ becomes $P(l)$.($n$ hasn't been inserted - we loop with $l$ changed)

  [Let $P(root)=- \infty$, so that the $2^{nd}$ case applies]

Complexity Analysis : Every element  may contribute at max 3 comparisons, 1 each for - left child, right child and for finally leaving i.e. subtree has been constructed. Even if I missed a comparison or two, It should be constant no. of comparisons per element and no. of operations for node construction will also be constant per element. Hence, giving $O(k)$ time complexity.

Actual Question

If the algorithm is correct, I need the correctness proof for it. Yes, I thought I had the proof but then brain got fried and I am stuck and unable to reason succinctly.
If the algorithm is incorrect, then why? And what is time complexity of the most efficient algorithm for the same question?

Also, is the $O(k)$ complexity correctly calculated - irrespective of the correctness of the algorithm?

You are in the right track. But the algorithm is incomplete. You missed the case inserting element on the left sub tree and back.

Here is the modified algorithm: (Changes marked in bold)

  Let $n$ represent the next element to be inserted.

  Let $P(y)$ represent the parent of node $y$.

  Let $g=G(y)$ represent the first node g on the path $y\to root$ such that $P(g)<g$.

  We will read the traversal in reverse. The last element of the traversal is the root. Let $l = root$. $l$ will represent the element last inserted in the BST (except for the 3rd case below- where it will change to the parent). Let $g=root$ tracking $G(l)$, initialize empty stack $stkG$ storing previous $g$'s on current path.
  Loop the following till there's no element left to be inserted

  if $l<n$ then $n$ is the right child of $l$. For the next insertion,
  $l$ changes to it's right child and $n$ becomes the next element(in
  reverse order of traversal ).  Push $g$ on $stkG$, and let $g=l$.
  else, if $l>n$ and $\textbf{P(g)<n}$ then $n$ is the left child of $l$. For the next
  insertion, $l$ changes to it's left child and $n$ becomes the next
  element(in reverse order of traversal).
  else, if $l>n$ and $\textbf{P(g)>n}$ then  $l$ becomes $\textbf{P(g)}$ and pop $g$ from $stkG$.($n$ hasn't been inserted - we loop with $l$ changed)

  [Let $P(root)=- \infty$, so that the $2^{nd}$ case applies]

For correctness, you can prove the following loop invariant:

Root is the first inserted element. for each insertion except root, the parent element has been inserted before.
Each insertion $n$ correctly maintains the order between $n$ and $l$. ($n<l$ if $n$ is left child of $l$, $n>l$ otherwise)
After backtracking step 3, the next insertion always occurs on the left branch.

1 and 3 ensures the post-order traversal, while 2 ensures the BST.

For complexity:

insertion cost: each element is inserted exactly once.
traversal and comparison: the algorithm actually performs a post-order traversal in reverse order, with $O(1)$ comparison on each step.
$g$,$stkG$ maintain cost: each node, which is right child of parent, is pushed and popped from $stkG$ at most once.

Thus the time complexity is $O(k)$.

Alternative algorithm:[1]

Using a recursive procedure:

procedure BST_from_postorder(post, len, target)
/*
input: post[0..len-1] -- (partial) postorder traversal of BST
       len -- length of post to be processed.
       target -- a cutoff value to stop processing
Output: tree_ptr -- pointer to root of tree/sub tree constructed from post[len_rest..len-1]
        len_rest -- remaining length that has not been processed.
*/
 1. if len <= 0 or post[len-1] <= target, then return null.
 2. root <- new Node created from from post[len-1].
 3. (root->right, new_len) <- BST_from_postorder(post, len-1, post[len-1])
 4. (root->left, rest_len) <- BST_from_postorder(post, newlen, target)
 5. return (pointer to root, rest_len)

/* BST_from_postorder(post, length of post, -infinity)
 will return the BST construct from given postorder traversal. */


How does topic or tag suggestion algorithms work? I know it's a keyword based search. But sites like Quora have some good suggesting algorithms where the algorithm understands the intent of question asked rather than just the keywords meanings.

For instance, for a question involving "O(n^2)" it adds 'Algorithms' and 'Computer Science' as topics and for a question involving "limit on friends in Facebook" it adds 'Facebook friends' as a topic. So it's more of a semantic search.

Google search also works on the same principles of semantic search. So how exactly does tag suggestion algorithm work?

Read about topic modeling in natural language processing.  There are many techniques; e.g., LDA is one simple standard approach.


Is my recursive algorithm for Equivalent Words correct? Here is my problem.
Problem
Given two words and a dictionary, find out whether the words are equivalent.
Input: The dictionary, D (a set of words), and two words v and w from the dictionary.
Output: A transformation of v into w by substitutions such that all intermediate words belong to D. If no transformation is possible, output “v and w are not equivalent.”
I need to write both recursive and dynamic programming algorithm. As for recursion, I came up with this algorithm. Is it correct?
 EquivalentWordsProblem(v, w, D)
 1.m <- len (v)
 2.n <-  len (w)
 3.substitutions = [] #array to save substitutions
 4.if m != n:
 5.  return "v and w are not equivalent"
 6.else
 7.for i <- m to 1 <-1 do
 8.  for j <- n to j <- 1 do
 9.    if v[i] != w[j]:
 10.           substituted_word <- v[1…i-1]+v[j] #we substitute v[i] for w[j]
 11.              if substituted_word in D:
 12.                substitutions.append(substituted_word)
 13.                   return EquivalentWordsProblem(v[1…m-i], w, D) #recur on the string of length m - i
 14.   else:
         return EquivalentWordsProblem(v[1…m-1], w, D) #recur on the string decreasing its length by 1
 15.if len(substitutions) != 0:
 16.  return substitutions
 17.else
 18.   return (“v and w are not equivalent”)

Your algorithm is not correct.
Here is a counterexample: $D$ contains the words $aa,bb,ac,bc$; $v=aa$; and $w=bb$.
A transformation is possible $(aa \to ac \to bc \to bb)$ but your algorithm won't find it.


Asymptotic Relationship from Limit F(n) = n-100
G(n) = n-200

I am trying to show the asymptotic relationship between these two functions using limits.

I take the limit n->∞ f(n) / g(n) and I get the result 1 which is constant c.

From the Big O theorem,

From the Big Omege theorem,

My question is: How I supposed to determine whether they are f = O(g(n)) or f = Ω(g(n))

In general, what is a good way to find the relationship between given two functions?

The theorems you quote are unfortunately wrong. As an example, $2 + \sin n = \Theta(1)$ although the limit $\lim_{n\to\infty} \frac{2+\sin n}{1}$ doesn't exist.

Here are some theorems which do hold.

Theorem 1. Let $f,g$ be two functions such that $f(n),g(n)$ are eventually positive. If the limit $c := \lim_{n\to\infty} f(n)/g(n)$ exists then

$f(n) = O(g(n))$ iff $0 \leq c < \infty$.
$f(n) = \Omega(g(n))$ iff $0 < c \leq \infty$.
$f(n) = \Theta(g(n))$ iff $0 < c < \infty$.
$f(n) = o(g(n))$ iff $c = 0$.
$f(n) = \omega(g(n))$ iff $c = \infty$.

Theorem 2. If $f,g$ are two polynomials which are eventually positive, then the limit $\lim_{n\to\infty} f(n)/g(n)$ exists.

Theorem 3. Let $f,g$ be two functions such that $f(n),g(n)$ are eventually positive. Then

$f(n) = O(g(n))$ iff $\lim\sup_{n\to\infty} \frac{f(n)}{g(n)} < \infty$.
$f(n) = \Omega(g(n))$ iff $\lim\inf_{n\to\infty} \frac{f(n)}{g(n)} > 0$.
$f(n) = o(g(n))$ iff $\lim_{n\to\infty} \frac{f(n)}{g(n)} = 0$.
$f(n) = \omega(g(n))$ iff $\lim_{n\to\infty} \frac{f(n)}{g(n)} = \infty$.


Finding recurrence when Master Theorem fails Following method is explained by my senior. I want to know whether I can use it in all cases or not. When I solve it manually, I come to same answer.

$T(n)= 4T(n/2) + \frac{n^2}{\lg n}$

In above recurrence master theorem fails. But he gave me this solution, when

for $T(n) = aT(n/b) + \Theta(n^d \lg^kn)$

if $d = \log_b a$

if $k\geq0$ then $T(n)=\Theta(n^d \lg^{k+1})$

if $k=-1$ then $T(n)=\Theta(n^d\lg\lg n)$

if $k<-1$ then $T(n)=\Theta(n^{\log_ba})$

using above formulae, the recurrence is solved to $\Theta(n^2\lg\lg n)$. When I solved manually, I come up with same answer. If it is some standard method, what it is called ?

OK, try Akra-Bazzi (even if Raphael thinks it doesn't apply...)
$$
T(n) = 4 T(n / 2) + n^2 / \lg n
$$
We have $g(n) = n^2 / \ln n = O(n^2)$, check. We have that there is a single $a_1 = 4$, $b_1 = 1 / 2$, which checks out. Assuming that the $n / 2$ is really $\lfloor n / 2 \rfloor$ and/or $\lceil n / 2 \rceil$, the implied $h_i(n)$ also check out. So we need:
$$
a_1 b_1^p = 4 \cdot (1 / 2)^p = 1
$$
Thus $p = 2$, and:
$$
T(n)
  = \Theta\left(n^2 \left( 1 + \int_2^n \frac{u^2 du}{u^3 \ln u} \right) \right)
  = \Theta\left(n^2 \left( 1 + \int_2^n \frac{du}{u \ln u} \right) \right)
  = \Theta(n^2 \ln \ln n)
$$
(The integral as given with lower limit 1 diverges, but the lower limit should be the $n_0$ for which the recurrence starts being valid, the difference will usually just be a constant, so using 1 or $n_0$ won't make a difference; check the original paper.)

[I've taken the liberty to add this to the Akra-Bazzi examples in the reference question, thanks!]


For every non-trivial language $A$ and every finite strict subset $B \subsetneq A$, it's holds that $A \le_m A \setminus B$ It's claim 1 from Bader Abu Radi's solution to this question.
My solution (have no idea how wrong it is):
$B$ finite $\Rightarrow$ $B\in R \Rightarrow$ exists TM $\langle M_B\rangle$ that halts $B$.
*Wrong from here
Let's define reduction $f$ from $A$ to $A \setminus B$, in the following way $f(\langle M_B\rangle , x)=\langle M_A\rangle$
When $M_A$ implemented on input $w$ like this:

Run $M_B$ on $w$ and answer on the same way

$x\in B \Rightarrow M_B$ accept $x\Rightarrow M_A$ accept $x\Rightarrow x\in M_A$
$x\notin B \Rightarrow M_B$ reject $x\Rightarrow M_A$ reject $x\Rightarrow x\notin M_A$
till here
So the reduction $A \le_m A \setminus B$ true.
As I wrote early not sure how wrong is it, additionaly what're the changes that should be done to proof the second claim ($A \setminus B \le_m A$) from the same answer.
Edit
$f(x)=x'=x\setminus x_B$ (when $x_B$ is all the $x$ that accepted by $M_B$), because $M_B$ halts on $B$ the reduction is applicable and work for any $x$.
It's implemented in the following way:

run $M_B$ on $x$ (halts), if $M_B$ accept, $x'$ reject
otherwise return $x$

If $x\notin A \Rightarrow x'\notin A \setminus B$
If $x\in A$:
$x\in B \Rightarrow M_B$ accept $x \Rightarrow x'$ reject $\Rightarrow x'\notin A\setminus B$
$x\notin B \Rightarrow M_B$ reject $x \Rightarrow x'=x\Rightarrow x'\in A\setminus B$
Is this one correct? Should something be added to it?

As mentioned in the above comment, the format of your reduction is not correct, so you have to take care of that first, and think about it again. Also, the hint I gave in the question that you linked should be enough. Anyway, here is another hint.
Hint: consider the identity reduction that maps every word $x$ to itself, and try to understand why it does not work. Then, think what is the simplest thing you can do in order to fix the identity reduction.


How similar is the Goldwasser-Sipser Set Lower Bound Protocol to the Hashcash/Bitcoin Proof-of-Work? Given a hash function $H:\{0,1\}^*\rightarrow\{0,1\}^n$, a difficulty $d\in\mathbb{N}$, and data $D\in\{0,1\}^*$, the framework of the Hashcash/Bitcoin Proof-of-Work entails finding a nonce $c$ such that $H(c\Vert D)$ starts with $d$ zero’s.  That is to say, Hashcash/Bitcoin Proofs-of-Work appear to find a preimage $c\Vert D$ that partially inverts a hash $H$.  Depending on $d$ and the size of the nonce, it may be impossible to find a nonce $c$ without having to change the data $D$. Currently (Aug. 2017) with Bitcoin, the target difficulty $d$ is, I think, 17 consecutive hexadecimal 0's.

Given a set $S\subseteq\{0,1\}^m$ and a number $K$, the Goldwasser-Sipser Set Lower Bound Protocol is an Arthur-Merlin protocol for Merlin the prover to show Arthur the verifier that $|S|\geq K$.   Letting $k$ be a number such that $2^{k-2}\leq K\leq 2^{k-1}$, Arthur chooses a random hash $H$ from pairwise independent hash function collection, along with a random $y\in\{0,1\}^k$.  Merlin’s goal is to find an $x\in S$ such that $H(x)=y$.  That is to say, Merlin’s goal in the Goldwasser-Sipser Set Lower Bound Protocol is to find a preimage $x$ that inverts a hash function $H$.  The larger the set $S$, the easier it may be to find a preimage.  Indeed, if $S\leq \frac{K}{2}$, then Merlin has a much smaller chance of finding a preimage than if $S\geq K$.  Thus, Merlin may provide evidence to Arthur that $S$ is large.  This may be used, e.g., to show that two graphs are not isomorphic.

My question is: can we reinterpret the Hashcash/Bitcoin Proof-of-Work as a Set Lower Bound?  In other words, can we consider finding a nonce $c$ in the Bitcoin Proof-of-Work as similar to finding a preimage $x$ in the Goldwasser-Sipser Set Lower Bound, which may show that some (arbitrary) set is large?

Or is the similarity between the two not very strong?

EDIT

Following up on D.W.'s answer, I wonder if $D$ could be considered as the input to a test of membership of $x\in S$.  For example, $S$ could be the set of all permutations of two graphs $G_1$ and $G_2$, $D$ might "encode" the two graphs $G_1$ and $G_2$, and $x$ might "encode" a permutation $\pi$ of one of $G_1$ or $G_2$.  The fact that a preimage $x$ was found might indicate that $G_1$ is not isomorphic to $G_2$, because it indicates $S$ is large.

However, I think there may be no easy way to tell what the "encoding" is.  So I wonder if a Proof-of-Work can, by design, be based on some interesting problem in $\mathsf{coNP}$, by having the encodings of the problem specified a-priori.

For example, the adjacency matrix of the two graphs $G_1$ and $G_2$ may be encoded in $D$.  The miner may engage in looking for another graph $G_3$ that is a permutation $\pi$ of one of $G_1$ or $G_2$, such that the hash $H_2$ is $0$.  That is, the miner may treat $G_3=\pi(G_1)$ or $G_3=\pi(G_2)$ as $x$ (i.e. the "nonce" $c$.) The miner may "succeed" if $H(\pi(G_1) \Vert G_1 \Vert G_2)$ begins with $d$ zeroes, or $H(\pi(G_2) \Vert G_1 \Vert G_2)$ begins with $d$ zeroes, thus indicating that the number of permutations of $G_1$ and $G_2$ together is "large" and not "small."

I can see some similarity too, but only in a loose sense; there are also some significant differences.

Here's the similarity.  Define $H_2(x)$ to be the first $d$ bits of $H(x||D)$.  Then you can think of the Bitcoin proof-of-work as being: find $x$ such that $H_2(x)=0$.  This is loosely similar to the Goldwasser-Sipser protocol; you could imagine that Merlin is the bitcoin miner and Arthur is the verifier, and the goal is for Merlin to prove to Arthur that Merlin has probably done at least about $2^{d-1}$ hash computations.  Or, if we let $S$ denote the set of values $x$ such that Merlin has computed $H_2(x)$, you could think of the goal being to prove that $|S|$ is at least $2^{d-1}$ or so.  Now if you imagine that Arthur always chooses $y=0$ in the Goldwasser-Sipser interactive proof, we get the same kind of computation.  So in that sense there is a similarity.

However, the correspondence is imperfect.  The threat models for the two schemes are quite different: Goldwasser-Sipser deals with a Merlin with unbounded computational power, whereas Bitcoin assumes the miner's computational power is limited.  The requirements for the hash function are quite different: Goldwasser-Sipser only needs a pairwise independent hash, whereas Bitcoin needs a cryptographically secure hash.  Also the nature of the set $S$ is different: in Goldwasser-Sipser the set $S$ is well-defined and there is a method specified in advance that Merlin can use to prove that a certain value is an element of the set, whereas in my analogy $S$ is only loosely defined and we don't have a clear way to prove that an element is a member of $S$.


Is this a Fixed Parameter Tractable algorithm? Suppose my algorithm runs in time $O(nL^2)$, where $n$ is the size of the input, and $L$ some other parameter, which can get arbitrarily large w.r.t. $n$. My algorithm does not run in polynomial time, since $L$ can get arbitrarily large w.r.t. $n$. So I'd like to categorize it elsewise.
Fixed Parameter Tractable algorithms, with regards to some defined parameter $k$, run in time $O(f(k)\times n^{O(1)})$, where $f$ is any function.

Would it be correct to state that my algorithm is Fixed Parameter Tractable (FPT) with regards to the parameter $L$?

First and foremost, I would advise having another look at the basic definitions. An FPT instance is identified by a string $x$ and an integer $k$ such that $(x, k)$ is a yes-instance.

Put briefly, if $f(k)$ is not polynomial in terms of $n$ and still depends on $n$, then you cannot obtain an FPT algorithm. We require that $k$ is fixed, or independent of $n$, and thus $f(k)$ is always independent of $n$. However, if $f(k) = n^{O(1)}$, then our FPT algorithm is in fact a polynomial time algorithm. Hence, if $f(k) = O(2^n)$, the answer is definitely no.


Regular Expression: L= {w | every even position of w is '1'} I am trying to solve a regular expression of binary string where every even position is a '1'

I've solved this for an odd position: (1(0+1))*(1+ε)

How would it look like for an even position then? Thanks in advance.

An odd position can either have 0 or 1 and every even position can only have 1. RE for this can be: $$ ((0 + 1)1)^* (\epsilon + (0+1))$$ Note that, it also contains the empty word.


Proving a Greedy Algorithm is Incorrect by Providing Counter Example and Coming up with another correct algorithm I want to come up with a counter example that proves the following greedy algorithm doesn't work and give an alternative correct algorithm. The problem is I have an array of numbers and I want to reach the last element of the array in the minimum number of steps. At each step, I can move to any element with the same value, move forward one, or move backward one. The greedy criterion is to move furthest to the right as much as possible. For example, if we have array {1,2,3,4,1,5}, the algorithm will start at 1 move to 1 before the 5 then moves to 5 with number of steps of 2.

An an example of input instance that proves the given greedy algorithm wrong might be {1,2,1,3,2} where the given algorithm crosses the array in 3 steps whereas there is an optimal solution of moving from 1 to the second 2 right to last 2 in two steps. Now, what is a correct algorithm for solving this problem ?

The fact that you have several potential ways you can move in this problem should be an indicator of how to come up with a counterexample such that using the "greedy" strategy of simply going as far right as possible doesn't yield an optimal solution.

Consider the array, $A = \{1, 2, 1, 3, 2\}$

By the greedy strategy you would end up making the moves in this series:

$1 \xrightarrow{} 1 \xrightarrow{} 3 \xrightarrow{} 2$
$(3$ total moves$)$

However, the optimal strategy would be to make the moves:

$1 \xrightarrow{} 2 \xrightarrow{} 2$  $(2$ total moves$)$

Edit: I guess the question was edited as I was answering the question/after I answered it and we ended up with the same example..? Anyway here's another below:

Consider another counterexample (where backtracking produces a better solution):

$A = \{2, 1, 4, 6, 1, 5, 0, 10, 9, 8, 6\}$

The greedy strategy would yield the path: $2 \xrightarrow{} 1 \xrightarrow{} 1 \xrightarrow{} 5 \xrightarrow{} 0 \xrightarrow{} 10 \xrightarrow{} 9 \xrightarrow{} 8 \xrightarrow{} 6$
$(8$ total moves$)$

Whereas the series of moves: $2 \xrightarrow{} 1 \xrightarrow{} 1 \xleftarrow{} 6 \xrightarrow{} 6$ $(4$ total moves$)$

There's another series of moves resulting in a length $4$ path as well.

Since making the "locally optimal" decision for this problem at each step doesn't yield the optimal solution for the overall problem, this looks like a problem that could be solved using dynamic programming.

Look at it in a top-down fashion. What is the last move we'd want to make to get to the final element of the array, i.e., $a_n$. Recurse on that subproblem. Find a way to develop a solution using memoization (to avoid solving the same subproblem multiple times) or solve it iteratively, in a bottom-up manner. DP can be a bit difficult.


Efficient data structure for storing integers in a range? Say I'm constantly given integers from the range $[1,2^{32}]$ in a random order and have to store these so that when a duplicate arrives I can deal with it. By the end of this algorithm all $2^{32}$ values will have been treated.

What's the best way to store which integers have been treated so far so that we can search if the current integer is a duplicate?

Since you know you're going to have to deal with all $2^{32}$ values eventually, you're going to need at least $2^{32}$ bits of memory, one for each value. The pigeonhole principle means that there's no possible way to store all the information you need with fewer bits than this.

So I recommend a straightforward bitmap. In other words, a simple array of bits. When a new value comes in, see if the corresponding bit is on or not; if it's off, flip it on. This takes the minimum possible amount of space, and is extremely fast (since all you have to do is index into an array).

P.S. You need $2^{32}$ bits specifically because the numbers could appear in any order. This means that there are $2^{2^{32}}$ possible states the program could be in, one for every possible combination of seen and not-seen values. Representing this many states will always take at least $2^{32}$ bits. If you knew the numbers would always come in increasing order, on the other hand, there'd only be $2^{32}$ states to distinguish between (since all you care about is the highest value seen so far), so you'd need a minimum of $32$ bits.


Count paths of length $n$ that a player can take I'm writing a video game, and I'm trying to find an efficient way of calculating this. The goal is to count the number of paths of length $n$ that a character can take, where the character can move left, right, or up. The caveat is that the character cannot go back to the same position in a path.

I've come up with a mediocre brute-force method the count the paths, but any ideas on an efficient way to calculate this?

This is a question in combinatorics, and can be calculated in a closed formula.

The key settings are:

"Down" is not allowed
Visiting previously visited square is not allowed

From the two requirements, we can draw the following conclusions:

Up is always a valid move (since we never went down, going up is essentially revealing a new square)
Left is not valid after Right, but is valid after Up (revealing new row) or after Left (which is essentially unvisited)
Right is not valid after Left, but is valid after Up (revealing new row) or after Right (which is essentially unvisited)

Denote $U$, $L$ and $R$ for Up, Left and Right respectively. We can now represent a path in a string like so: $P = (U,U,U,U,L)$

The question is now: How many valid paths strings of length $n$ are there?

Let $T(n)$ be the number of valid strings of length $n$

If the first move is $U$ then the remaining strings are $T(n-1)$
If the first move is $L$ then the remaining strings are those starting with $L$ or $U$
If the first move is $R$ then the remaining strings are those starting with $R$ or $U$

Looking at strings where the first move is either $L$ or $R$: the remaining strings are: strings starting with $U$ (twice), starting with $L$, or starting with $R$. (simple summation of all the options in 2nd and 3rd bullet).

Note that all the strings starting with $U$ + all the strings starting with $L$ + all the strings starting with $R$ is exactly $T(n-1)$ since the first move is already set.

We are left with one more instance of "all the strings starting with $U$" = $T(n-2)$ (again, first move is set)

Which results the following recursive formula: $$T(n) = 2T(n-1)+T(n-2)$$
where:

$$T(1) = 3, \space
T(2) = 7 $$

Calculations omitted, the closed formula for the relation above is:

$$T(n)= \frac{(1+\sqrt{2})^{n+1}}{2} + \frac{(1-\sqrt{2})^{n+1}}{2} $$


Is the language $\{a^{n^2-1} | n \in \mathbb{N}\}$ context free? and how to prove it? Is the language $\{a^{n^2-1} | n \in \mathbb{N}\}$ context free? and how to prove it?
I think it is, but I could not find a way to prove it by using push down automaton or any other way.

A unary language (a subset of $a^*$) is context-free iff it is regular. This is a special case of Parikh's theorem. It is not too hard to show that a unary language $L$ is regular if and only if there exist $n,m$ such that for all $N \geq n$, $a^N \in L$ iff $a^{N+m} \in L$. See if this condition holds for your language.


How to construct and write down a Turing machine for a given language? In my class we just started learning about Turing machines.  I think I understand the concept but am unsure how to syntactically solve any problem related to one.  I am presented with the problem:

  Build a Turing machine accepting $(b + c)^+$$\#a^+$  (Please comment your
  code. Any uncommented solutions will not be graded.)

I am unsure of how to actually begin devising this machine? Could someone please help get me started?

What all strategies to devise a program for a Turing machine - or for any other machine, for that matter - boil down to is this: learn how to write programs for easy languages, and then use these programs and rules of composition to figure out more complicated ones. Programming languages - including Turing machine programs - expose an interface to the underlying computer, which allows you to perform some limited number of operations. Programming is the art and science of finding a sequence of such operations to solve your problem.

Can you write a Turing machine to recognize $a^+$?
Change the Turing machine in (1) to recognize $\#$ only. Hint: it's a different symbol and you only want one of them.
Change the Turing machine in (1) to recognize $(b + c)^*$. Hint: you'll now take either of two symbols instead of one symbol.
Take the machines from steps (3), (2) and (1). Create a new machine that does what (3) does, but instead of accepting, it does what (2) does, but instead of accepting, it does what (1) does.

In TM pseudocode, what you get is something along the following lines:

Move one cell to the right.
If the cell is $b$ or $c$, move to the right; else, halt reject.
If the cell is $b$ or $c$, move to the right, and repeat this step. Otherwise, if the cell is $\#$, move to the right and go to the next step. Halt reject in any other case.
If the cell is $a$, move to the right; else, halt reject.
If the cell is $a$, move to the right. Else, if the cell is blank, halt accept. Halt reject in any other case.

Those would serve as decent comments, but coming up with the TM and verifying that it works should also accompany any correct answer.


Why is push_back in C++ vectors constant amortized? I am learning C++ and noticed that the running time for the push_back function for vectors is constant "amortized." The documentation further notes that "If a reallocation happens, the reallocation is itself up to linear in the entire size."

Shouldn't this mean the push_back function is $O(n)$, where $n$ is the length of the vector? After all, we are interested in worst case analysis, right?

I guess, crucially, I don't understand how the adjective "amortized" changes the running time.

The important word here is "amortized". Amortized analysis is an analysis technique that examines a sequence of $n$ operations. If the whole sequence runs in $T(n)$ time, then each operation in the sequence runs in $T(n)/n$. The idea is that while a few operations in the sequence might be costly, they can't happen often enough to weigh down the program. It's important to note that this is different from average case analysis over some input distribution or randomized analysis. Amortized analysis established a worst case bound for the performance of an algorithm irrespective of the inputs. It's most commonly used to analyse data structures, which have a persistent state throughout the program.

One of the most common examples given is the analysis of a stack with a multipop operations that pops $k$ elements. A naive analysis of multipop would say that in the worst case multipop must take $O(n)$ time since it might have to pop off all the elements of the stack. However, if you look at a sequence of operations, you'll notice that the number of pops can not exceed the number of pushes. Thus over any sequence of $n$ operations the number of pops can't exceed $O(n)$, and so multipop runs in $O(1)$ amortized time even though occasionally a single call might take more time.

Now how does this relate to C++ vectors? Vectors are implemented with arrays so to increase the size of a vector you must reallocate memory and copy the whole array over. Obviously we wouldn't want to do this very often. So if you perform a push_back operation and the vector needs to allocate more space, it will increase the size by a factor $m$. Now this takes more memory, which you may not use in full, but the next few push_back operations all run in constant time.

Now if we do the amortized analysis of the push_back operation (which I found here) we'll find that it runs in constant amortized time. Suppose you have $n$ items and your multiplication factor is $m$. Then the number of relocations is roughly $\log_m(n)$. The $i$th reallocation will cost proportional to $m^i$, about the size of the current array. Thus the total time for $n$ push back is $\sum_{i=1}^{\log_m(n)}m^i \approx \frac{nm}{m-1}$, since it's a geometric series. Divide this by $n$ operations and we get that each operation takes $\frac{m}{m-1}$, a constant. Lastly you have to be careful about choosing your factor $m$. If it's too close to $1$ then this constant gets too large for practical applications, but if $m$ is too large, say 2, then you start wasting a lot of memory. The ideal growth rate varies by application, but I think some implementations use $1.5$.


Derivation of the energy function of a hopfield network Can someone please point me towards a rigorous derivation of the energy function of a discrete Hopfield network. What I want, is the derivation must start out with the structure of the network and prove that the critical points of the dynamical system can be obtained by minimization of some function (possibly by constructing the Lyapunov function of the dynamical system). I cannot seem to find such a rigorous proof. Thankyou!

I believe what you want to show is that the energy function is monotonically decreasing from time $t$ to time $t+1$ given the state update rules. Since there is only a finite number of states, this means the state must converge to a equilibrium under the given dynamics.

To this end let $\mathbf{s}(t) \in \{0,1\}^n$ be the state of the network at time $t$. We update the network state by picking a unit $s_i(t)$ and updating the state according to
$$
s_i(t+1) = \left\{\begin{array}{r l} 1:& \sum_{j} w_{ij} s_j(t) > 0\\ 0:& \text{otherwise}\end{array}\right.
$$
and define the energy function as
$$
E(\mathbf{s}(t)) = -\frac{1}{2}\sum_i\sum_jw_{ij}s_i(t)s_j(t),
$$
where $w_{ij}$ is the weight between unit $i$ and $j$, $w_{ij} = w_{ji}$ and $w_{ii} = 0$ for al $i$.

WLOG assume we will update the $i^{th}$ unit. First, because of the restrictions on the weights, we may rewrite $E(\mathbf{s}(t))$ as the difference of 2 terms
$$
E(\mathbf{s}(t)) = -\frac{1}{2}\sum_{j\neq i}\sum_{k\neq i}w_{jk}s_j(t)s_k(t) - s_i(t)\sum_jw_{ij}s_j.
$$
Let $c_t = -\frac{1}{2}\sum_{j\neq i}\sum_{k\neq i}w_{jk}s_j(t)s_k(t)$ be the part of the energy function that does not depend on $s_i(t)$. Now if $s_i(t+1) = s_i(t)$ then clearly we have $E(\mathbf{s}(t+1)) = E(\mathbf{s}(t))$, so we only need to consider the 2 other cases.

Case 1: If $s_i(t+1) = 1$ and $s_i(t) = 0$ then it must be that $\sum_{j} w_{ij} s_j(t) = \Delta_t > 0$. So
$$
E(\mathbf{s}(t+1)) = c_{t+1} - \Delta_t = c_t - \Delta_t < c_t = E(\mathbf{s}(t)).
$$
Case 2: If $s_i(t+1) = 0$ and $s_i(t) = 1$ then it must be that $\sum_{j} w_{ij} s_j(t) = \Delta_t \le 0$. So
$$
E(\mathbf{s}(t+1)) = c_{t+1} = c_t \le c_t - \Delta_t = E(\mathbf{s}(t)).
$$
Having considered each case we can conclude that $E(\mathbf{s}(t+1)) \le E(\mathbf{s}(t))$ and is therefore monotonically decreasing.


What is the complexity of a variation of the Coupon collector's problem? I need to know the complexity of the following algorithm:

Draw elements from a set of size $m$, one by one, randomly, with replacement, until coming across $n$ different elements from the set ($n\le m$). We do not care what are the numbers drawn, and halt once $n$ different numbers were seen during this process.

This is a variation of the Coupon collector's problem, where one continues picking until seeing all $m$ elements of the set.

Example:

We draw numbers from the set $\{1,2,3,4,5\}$, $n=3$, $m=5$. The output
$\{1,5,2\}$ is produced by the following series of draws:

$1,1,5,1,5,2$

from the pool $\{1,2,3,4,5\}$. In this case, we halt after $6$ operations.

What is the expected time complexity of this algorithm?

When $m$ is much larger than $n$, the expected number of trials is basically linear in $n$.  We can make this more precise, as shown below.

Let $T_n$ be the random variable which counts the number of trials up to seeing $n$ different elements, where the elements are picked uniformly at random from a set of size $m$.

You can write $T_n$ as the sum of geometric random variables

$$T_n=1+G\left(1-\frac{1}{m}\right)+G\left(1-\frac{2}{m}\right)+...+G\left(1-\frac{n-1}{m}\right)$$

where $G(p)$ is a geometric random variable with parameter $p$ (number of trails up  to the first success, where success happens with probability $p$ (I leave it to you to prove the equivalence).

Using linearity of expectation:

$$\begin{align*}
\mathbb{E}\left[T_n\right]&=\sum\limits_{i=0}^{n-1}\mathbb{E}\left[G\left(1-\frac{i}{m}\right)\right]\\
&=\sum\limits_{i=0}^{n-1}\frac{m}{m-i}\\
&=m\left(\frac{1}{m}+\frac{1}{m-1}+...+\frac{1}{m-n+1}\right)\\
&=m\left(H_m-H_{m-n}\right)
\end{align*}$$

where $H_k$ is the harmonic sum, which satisfies $\frac{1}{2(k+1)}\le H_k-\ln k - \gamma\le \frac{1}{2k}$, where $\gamma$ is the Euler–Mascheroni constant (see Wolfram's page on harmonic numbers). Using these bounds for harmonic numbers we have:

$$\begin{align*}
\mathbb{E}\left[T_n\right]&\le m\left(\frac{1}{2m}+\ln m +\gamma -\left(\frac{1}{2(m-n+1)}+\ln(m-n)+\gamma\right)\right)\\
&\le m\left(\frac{1}{2m}+\ln\frac{m}{m-n}\right)=\frac{1}{2}+m\ln\frac{m}{m-n}.
\end{align*}$$

Note that $m\ln\frac{m}{m-n}=m\ln\left(1+\frac{n}{m-n}\right)\approx n$ when $n\ll m$, so for $m$ much larger than $n$, the expected number of trials is linear in $n$.


Integer Linear Programs: An instance or not? Given a set of integers $\{x_0, x_1, ... , x_{n-1}, x_n\} \subseteq \mathbb{Z}$, a set of integer variables $\{y_0, y_1, ... ,y_{n-1}, y_n\} \subseteq \mathbb{Z}$ and an integer $m \in \mathbb{Z}$ is the following equation an instance of an integer linear program (ILP):

$
(x_1\cdot y_1) + (x_1\cdot y_1) + \cdots + (x_{n-1}\cdot y_{n-1}) + (x_n\cdot y_n) = m
$
i.e. is there an assignment of variables $y_i$ such that the equation is true?
After googling around I noticed that ILPs usually involve maximising or minimising a variable, but that is not what is needed here. If not, could anyone tell me what type of problem this is and if there are any known complexity results?

Your problem has a solution if and only if $m$ is a multiple of the greatest common divisor of $x_1,\ldots,x_n$. You can compute the GCD in polynomial time using the Euclidean algorithm (the version where you divide in each step rather than subtract) applied $n-1$ times.


How to encode a sequence of non-decreasing integers with an integer without redundancy, loops, and recursions How to encode a sequence of n non-decreasing integer of [0, ..., m] fulfilling the following conditions:

no or minimal redundancy
only use 1 integer variable or k independent integer variables with a range of [0, ..., j(k)], It means there exist an inverse function f-1(x) to map the encoded sequence, an integer x of the domain [0, 1, ..., |valid sequence| - 1], back the original sequence.
usual integer operations
no or minimal lookup tables
closed form formula to decode back to the sequence without loops or recursions

For example,

0, 0, 0, 0
0, 0, 0, 1
0, 0, 0, 2
...
0, 0, 0, m
0, 0, 1, 1
0, 0, 1, 2
...
m, m, m, m

The purpose of this counting function is to enumerate all possible values in the non-decreasing integer sequence later being used in constraints.

Let $\mathcal{C}(n,m)$ denote the set of sequences you are interested in, namely non-decreasing sequences of length $n$ consisting of integers from $\{0,\ldots,m\}$, and let $C(n,m) = |\mathcal C(n,m)|$ be the number of such sequences. It is not hard to verify the following recursion:
$$
\begin{align*}
&C(0,m) = 1, \\
&C(n,m) = \sum_{k=0}^m C(n-1,k) \text{ for } n > 0.
\end{align*}
$$
In fact, it is not hard to check that
$$ C(n,m) = \binom{n+m}{m}. $$
But the recursion allows us to rank and unrank sequences. More explicitly, we will now describe a bijection $r_{n,m}$ from $\mathcal C(n,m)$ to $[0,C(n,m))$ (i.e., $\{0,\ldots,C(n,m)-1\}$). The bijection is defined recursively as follows (below, $\lambda$ is the empty sequence):
$$
\begin{align*}
&r_{0,m}(\lambda) = 0, \\
&r_{n,m}(\sigma_1,\ldots,\sigma_n) = \sum_{k < \sigma_n} C(n-1,k) + r_{n-1,\sigma_n}(\sigma_1,\ldots,\sigma_{n-1}).
\end{align*}
$$
This doesn't order the sequences in the order you listed, though one can easily adapt it to your order (by considering the first rather than last element). We can also describe the inverse bijection explicitly:
$$
\begin{align*}
&r^{-1}_{0,m}(0) = \lambda, \\
&r^{-1}_{n,m}(r) = r^{-1}_{n-1,k}\left(r - \sum_{\ell<k} C(n-1,\ell)\right),k, \\ &\qquad \text{ where $k$ is defined by } \sum_{\ell < k} C(n-1,\ell) \leq r < \sum_{\ell \leq k} C(n-1,\ell).
\end{align*}
$$

Finally, if all you want is to list the sequences in order, say the order in your post, then you can use the following simple "counter" algorithm. Start with the all-zero sequence $\sigma_1 = \cdots = \sigma_n = 0$. At each step, find the maximal $i$ such that $\sigma_i < m$ (if $\sigma_1 = \cdots = \sigma_n = m$, we are done). Increase $\sigma_i$, and set all numbers following it to its new value. This will enumerate all sequences in lexicographic order, in amortized time $O(1)$ per sequence.


What's wrong with this substitution for master's method I was hoping to solve the following recurrence by performing a simple substitution followed by the master's method:
$$T\left(n\right)=T\left(n-1\right)+n^2$$
I did
$$S\left(2^n\right)=S\left(2^{n-1}\right)+\left(2^n\right)^2$$
Thus
$$S\left(m\right)=S\left(\frac{m}{2}\right)+m^2$$
Which using the master's method yields
$$T\left(n\right)=\Theta \left(\left(2^n\right)^2\right)$$
However, the correct answer to this is:
$$T\left(n\right)=\Theta \left(n^3\right)$$
So what was wrong with my substitution?

The key thing to note is that you are replacing $T(n)$ function with an exponential $S(n)=2^n$. The variables do not change just the functions. So, $n^2$ stays.


Complexity of multiplying matrix Let's consider the following algorithm to multiply squares matrix:
A is a matrix of NxN.
r_i, r_j defines interval of rows. For example r_i = 2, r_j=3 means the second and the third rows. c_i, c_j means the same as r_i, r_j but for columns. We assume that N = 2^s for some s.

mul(A, B, r_i, r_j, c_i, c_j){
if(r_i != r_j){
   r_m = floor((r_i+r_j)/2)

   mul(A, B,  r_i, r_m, c_i, c_j)
   mul(A, B, r_m+1, r_j, c_i, c_j)
} else if(c_i != c_j){
   c_m = floor((c_i+c_j)/2)
   mul(A, B, r_i,r_j, c_i, c_m)
   mul(A, B, r_i, r_j, c_m+1, c_j)
}else{
 for i = 1 to N:
    C[r_i][c_i] += A[r_i][i] * B[i][c_i]
 }

}

And the most important:

Complexity of that algorithm takes: T(n) = 4T(n/2) + n = O(n^2)

And it is not correct. The correct answer is O(n^3). Why my computation is incorrect.

Your calculation is not right...
$$
U(R,C) = 2U(\frac{R}{2},C)\textrm{ or } 2U(R,\frac{C}{2})\\
U(1,1) = O(n)
$$

Basically, you have $N^2$ unique positions (which you drive your way down to recursively, rather than just looping) - for each of those you do a loop of O(N) so you have $O(N^3)$


How to determine if 2 rays intersect? We are given the 2D coordinates of 2 points: the first point is where the ray starts and it goes through the second point. We are given another ray in the same way. How do we determine if they have a point of intersection? I would like to know the general algorithm and its explanation, don't mind about the extreme cases (e.g. when the rays have the same starting point). P.S. I saw a similar question on another stack exchange, but the answers did were not backed up by explanation.

I'm copying my answer for the similar question - with minimal changes.

The vector equation:
$$P_1 + \alpha * (P_2 - P_1) = P_3 + \beta * (P_4 - P_3)$$
where $P_1 = (x_1, y_1)$ etc., should have a solution, satisfying following conditions:
$$\alpha \ge 0, \beta \ge 0$$
then these two rays $(P_1, P_2)$ and $(P_3, P_4)$ do intersect. However, there are many corner cases here (for example, $P_1 = P_2$ etc.). Also, you can get wrong answers because of the limited precision of your data representation in computer.


Irregularity of $\{ w_1 aa w_2 \mid |w_1| \neq |w_2| \}$ I'm currently struggling to come up with a proof that the following language is irregular:
$$L_2 := \{w_1aaw_2 \in \Sigma^* \mid w_1, w_2\in\Sigma^* \land |w_1| \ne |w_2|\}$$
where $\Sigma = \{a, b\}$.
Now quite intuitively, the language needs to know what $|w_1|$ was in order to compare against $|w_2|$, so it has to be irregular, but I'm failing to formally prove that.
I was able to solve the previous problem from the book, which was proving that (similarly)
$$L_1 := \{w_1aaw_2 \in \Sigma^* \mid w_1, w_2\in\Sigma^* \land |w_1| = |w_2|\}$$
is irregular, which was relatively simple using the pumping lemma.
So I thought maybe there was some kind of connection between the two problems, given that $L_1\cup L_2$ is regular, but there doesn't seem to be any kind of closure property I can robustly employ in order to prove that $L_2$ is irregular.
Any ideas are welcome and many thanks in advance!

For $i \ge 0$ define $w_i = b^i aa$.
For any $i,j \ge 0$ with $i \neq j$ you have that $b^i$ is a distinguishing extension for $w_i$ and $w_j$. Indeed, $w_i b^i \not\in L_2$ but $w_jb^i \in L_2$.
Then the number of equivalence classes of the set $\{ w_i \mid i \ge 0\}$ with respect to the equivalence relation "having a distinguishing extension" is not finite and, by the Myhill-Nerode theorem, $L_2$ is not regular.

Here is an alternative solution that uses closure properties and the pumping lemma following the hint of Hendrik Jan.
Suppose that $L_2$ is regular. Then so is $L' = \overline{L}_2 \cap \{b^i aa b^j\} = \{b^i aa b^i\}$, which is easily shown to be non-regular using the pumping lemma.
Indeed, suppose that $L'$ was regular, and let $p$ be its pumping length. For some $k \in \{1, \dots, p\}$, the word $b^p aa b^p \in L'$ can be written as $b^k b^{p-k} aa b^p$ such that $b^{ki} b^{p-k} aa b^p \in L'$ for every $i \ge 0$. Nevertheless, for $i=0$ we have $b^{p-k} aa b^p \not\in L'$, yielding a contradiction.


To check whether a given number has been computed previously or not Given a 64 bit positive integer. How to determine in the most efficient way whether the given integer has ever been seen or not?

Implementation in C++11 (Please do include this fact, while suggesting your opinions)

Intent: I am generating numbers randomly, by flipping one bit at a time. I need to check every time on generation of a number whether it has been previously generated or not? ex: 1,4,8,16,3,5,9,11,12, .... .

Current Solution:
1.I can create an unordered_map. However, I would be wasting memory for storing the value part which is boolean in this case. And also hashing isnt the cheapest operation and also their is a penalty of rehasing.

Can create a list and keep it sorted. Too expensive operations --Sorting and lookup.

You could use a hashtable to keep track of all values you've seen before.  (You could also use a balanced binary tree data structure, but it will probably be less efficient in practice, due to the overhead of the pointer traversals.)

If you don't mind occasional false positives, you could use a Bloom filter, and that might be even more efficient -- at the cost of occasionally declaring "I've seen this number before!" when you actually haven't.

Questions about specific C++ libraries are off-topic here but can be asked on Stack Overflow once you know what data structure you want to use.


Determining the classification of languages $L_0 = \{ \langle M, w, 0 \rangle \mid \text{$M$ halts on $w$}\}$
  $L_1 = \{ \langle M, w, 1 \rangle \mid \text{$M$ does not halt on  $w$}\}$

  $L = L_0 \cup L_1$

I need to determine where in the hierarchy of languages (recursive, recursively enumerable, not recursively enumerable) $L$ and its complement $\overline L$ belong. I reasoned as follows

$L = \{ \langle M, w, x\rangle  \mid \text{$M$ halts on $w$ when $x=0$, $M$ doesn't halt on $w$ when $x = 1$, $x \in \{0, 1\}$}\}$

$L$ is clearly not recursively enumerable as a Turing machine wouldn't be able accept in all cases.  It can accept only in case the input refers to $L_0$, but can't in case the input refers to $L_1$.

$\overline L = \overline L_0 \cap \overline L_1 = \emptyset$
Thus $\overline L$ is recursive.

Is my reasoning ok? This is a question from a previous exam paper.

Here are two hints

If $\bar L$ would be decidable (recursive), then so would be $L$, and you just argued that $L$ is not even recursively enumerable. Maybe you have a closer look on what $\bar L_0 \cap \bar L_1$ really is. For example
$\bar L_0 = \{ \langle M, w, 0 \rangle \mid \text{$M$ does not halts on $w$}\} \cup \{ \langle M, w, x \rangle \mid x\not=0\} $.
If you want to argue formally correct that a language is not recursively enumerable, or decidable, then try to use a reduction, for example the many one reduction. Reduce  a a problem, whose status you know, to $L$ and you can say something about $L$.


Determining possible data structures given a set of required operations This was an interview question that I was told is supposed to be an open ended discussion of the trade-offs.
You have a collection of comparable objects and want to be able to do the following:
1. Lookup, add, delete objects
2. Get and/or extract Min, max objects
3. Objects should be unique (no duplicates)

A max-heap or min-heap almost fits the criteria except you can only have easy access to either min or max but not both. I ended up saying that if we know if one of max or min is more commonly needed, build a max or min heap.

A hash table is out of the question since the elements are un-ordered although it does have O(1) lookup.

What are the most appropriate data structure(s) in this scenario?

If there is no restriction on execution time or $n$ stays small then a simple unsorted array is always an option. It gives $O(n)$ execution time for all operations except adding an object and removing by swap-with-back-and-pop. As a less obvious bonus iteration over an array is very cache friendly so it will likely outperform nearly everything for small $n$.
When you value lookup more than modification you can sort the array, lookups are now $O(\log n)$ and min and max are $O(1)$. But modifications are now $O(n)$ in all cases however they can be amortized a bit by using a small scratch array on the side that gets merged in periodically for additions and tombstone sentinels for removed elements.
Using a min or max heap will reduce modification time to $O(\log n)$ at the cost of all other operations becoming $O(n)$ except the query for min or max depending on which it is. You can split the data into 2 using a selected pivot element where if smaller then elements get pushed into a min heap and if larger they get pushed into a max heap. Depending on the order of operation you may need to reselect the pivot element is the sizes of the heaps become too unbalanced.

Then there are the node-based solutions:

Linked list (sorted or not) is not useful at all here, you still have $O(n)$ execution time for nearly everything like with unsorted array with additional cache miss and dependent-load costs during iteration and the only bonus you have is that insert and remove can happen in-place. I'm mentioning it here because:
You can use a look-ahead list, essentially a sorted linked list with the addition that each node has a finger table of nodes that lets you skip ahead in the list. modifications and lookups are now $O(\log n)$. However it has an element of randomness (how large each finger table is) that can potentially screw you over and regress performance to $O(n)$ for lookups.
A balanced search tree isn't random in that way and every operation becomes $O(\log n)$ and correct implementation of the balancing routing can be tricky.
you already mentioned why you don't like the hashtable though the $O(1)$ modification and lookup can outweigh the $O(n)$ cost for min/max. Though keep in mind that there are various ways of implementing one each with various benefits and drawbacks.

Those are the basic data structures I'd select between for holding a set of values. If there are other requirements and performance is a big enough issue then I'll go research more exotic options.


Neural network game players and incremental updates Neural networks in recent years have been successfully used for gameplaying. A difference between games and e.g. image processing is that the game boards get updated incrementally. Do any neural network implementations optimize for this fact?

For example, there are 361 squares on a Go board; in a typical turn, only one of those squares will change value. On the face of it, a program like AlphaGo could save time by not redoing the calculations from the other 360 squares each time it looks at a new board position.

On the other hand, if the calculations are being done on a GPU, this optimization involves moving away from the straight vector arithmetic that GPU's do so well, which would offset the efficiency gain.

On the third hand, the potential efficiency gain would become larger as you move to more complex games; how many variables are there in StarCraft?

Has anyone ever done this optimization, or studied it and given reasons for not doing it?

The AlphaGo algorithm does not benefit from this kind of optimization.  It's hard to share an intuition for why without diving into the details of the algorithm, but at a coarse level: a single small change to the board can make a dramatic change to the strategic nature of the position, so it's not clear that one can reuse calculations effectively.  In particular, it sounds like you are assuming that AlphaGo does some computation separately for each square of the board, so we could avoid re-doing the same ones for squares that haven't changed.  However, that's not at all how AlphaGo works, so that kind of optimization is not applicable here.


Regex: Any pair of zeros is before any pair of ones Write a regular expression for all the strings in which every pair of adjacent zeros appears before any pair of adjacent ones. The answer given in the book is:
$$(0+10)^*(00)(1+01)^*(11)(0+10)^*(1+01)^*$$
Is that correct? I fail to see how could you get a string like 10011, but it fits description. I mean even a string like 1 fits a description. So, if this answer is incorrect, then what is a correct answer?
My simple guess is:
$$(\epsilon+1)(0+10)^*(1+01)^*(\epsilon+0)$$

P.S.
Does $(0^*1^*)^*$ generate every possible binary number? If not, what does it generate?

You are correct: the regexp you quote does not match the string $10011$ and that string has the property that every pair of adjacent $0$s occurs before any pair of adjacent $1$s.  But it does match the string $001100$, which fails to have the property!

Your proposed solution matches $11001$ so is also incorrect (the first bracket matches $1$, the second matches $10$, the third matches $01$ and the fourth matches $\epsilon$.

A regexp that does match the required language is
$$0^*(100^*)^*(11^*0)^*1^*\,.$$
It works as follows.

$0^*(100^*)^*$ matches the empty string and any non-empty string that doesn't contain $11$ and that ends with $0$. The string can't contain $11$ because there must be at least one $0$ between every two $1$s.
$(11^*0)^*1^*$ matches every string that begins with $1$ and does not contain $00$, since there must be at least one $1$ between any two $0$s.
Now put the two halves together. If a string has the property that all occurrences of $00$ are before the first $11$, then the section of the string before the first $11$ must either be empty or end in $0$, so it matches the first part of the regexp. The rest of the string contains no occurrences of $00$ so it matches the second part of the regexp.

Note that there are shorter regexps that do the same thing: Yuval Filmus gives $(0+10)^*(1+10)^*$ in a comment to the question. That's a tidier version of the same idea.

And, yes, $(0^*1^*)^* \equiv (0+1)^*$ matches every possible binary string.


why is H = {www | w ∊ (0,1)* } not regular language I know pumping lemma and also know how to prove if languages are not regular or are regular using proof by contradiction methodology. But I am stuck on this one.Especially, I don't know exact string it produces.

$$ H = \{www \mid w ∊ (0,1)^* \} $$

How do I prove this is not regular language? Thanks!

You can use the Myhill–Nerode criterion. Consider the words $0^n1$ for all $n$. These are pairwise inequivalent since $0^n10^n10^n1 \in H$ while $0^m10^n10^n1 \notin H$ if $m \neq n$. Since we have found infinitely many pairwise inequivalent words, it follows that the language is not regular.

As mentioned in the comments, you can probably also use the pumping lemma, but it might take more work.


Access a tree by level without traversing I need a tree structure that works roughly like the following

for each new child I need to match it (with some criteria) with a parent from the previous level only
when the tree is completely initialized, for each leaf I need to find the first parent ancestor that has siblings, i.e. the node just after the branching point.

While the latter is pretty easy with a tipical tree structure, for the first I'd like to just access all nodes of a layer without traversing the whole tree (even with BFS). Does this have a name?

I'm thinking to just keep track of level number for each node and build a second structure to represent levels.

To support the operations mentioned - especially level-order traversal (or walk) - in time bounded by the depth, you don't need an extra attribute for each node.

For a "semi-static" tree¹, you could use an array of nodes to store it:
For every level, keep the index just beyond.
For every node, keep parent, for non-leaf nodes, children ("first" child), too:
siblings are successive nodes with same parent.

For a "dynamic" tree, modify the [typical] tree structure keeping children, siblings and optionally parent to support level-order traversal:
Change sibling to next in same level - not a sibling iff different parent.
You may need support for first in level, or "the list of nodes in the same level" to be circular to be able to access all of them starting from any-one thereof.

[1]: semi-static tree: only structural change is addition of nodes.
(The task sketched may have another restriction: no node with children will get another child once a different node gets one.)
(or even static: [once] the tree is completely initialized)


approximation algorithm with polynomial complexity It might be a silly question, I do take a carefully read about approximation algorithm through coursenotes, but when I saw the words "approximation algorithm with polynomial complexity", I can't understand what it means, I searched a lot and here is my assumption.

First, for some NPc or NP hard problem, we can try to solve them approximately, because there is no optimization algorithm right now. So compared with some opotimal solution theoretically, some optimazation problem can use approximation algorithm to get an approximation solution, such like vertex covering problem.

Then it is the term polynomial complexity, an algorithm is polynomial if for some k>0, its running time on inputs of size n is O(n^k).

So is "approximation algorithm with polynomial complexity" means an approximation algorithm that whose complexity is in polynomial time? So is it means there are approximation algorithm that has other complexity such as exponential complexity.

By the way, through the approximation algorithm for vertex covering problem, I know what the algorithm is (briefly it is takes an arbitrary edge from subset E' of all possible set of edges, add two vertax at set S and remove all edge who has the same vertex with that arbitrary edge and continue until E' is empty). But how to observe it is polynomial complexity or what?

I really apprexiate if someone can solve my confusion.

As you say, we believe there is no polynomial-time algorithm for solving an NP-hard problem. So if we wanted to have a polynomial-time algorithm, it seems like we need to give up the hope of always finding an optimal solution. So you are right: typically, we strive to find approximation algorithms that run in time polynomial in the input size. But sure, there is nothing that prevents you from considering approximation algorithms that run in exponential-time (or for example in FPT-time for some parameter).

Sometimes these approximation algorithms are very simple to state. This is perhaps often the case for greedy algorithms, like the one you mention for vertex cover. To see that it runs in time polynomial in the size of the input graph, you need to perform a runtime analysis in the usual way.


How to model this constraint using integer linear programming? Suppose we have $S=\{1,2,\ldots,n\}$, a binary variable $x$ and an integer $p$. I would like to model the following constraint using integer linear programming:

  If $x = 1$, then there must exists a unique $i\in S$ such that: $x_j=1$ for all $j\in\{i,i+1,\ldots,i+p-1\}$.

How can I do this?

Assuming $x_j$ are binary.

The additional binary variable $y_i$ equals one if and only if when all $j$ are 1.

$$
\sum\limits_{j=i}^{i+p-1}x_j - p+1 \leq y_i \leq \frac{1}{p}\sum\limits_{j=i}^{i+p-1}x_j
$$

Then to have a unique $y_i$ equals one you add
$$
x \leq \sum_{i=1}^n y_i \leq (n-1)(1-x)+1
$$


Local search to find minimum degree spanning tree Suppose for a graph $G=(V,E)$ and a spanning tree T of G, $\Delta(T)$ is the largest degree of a vertex in T, and let $\Delta^*$ be the smallest such quantity over all spanning trees of $G$.

We have the following local search procedure which can changes spanning tree $T$ into a different spanning tree $T'$: We find an edge $e$ not in $T$ and add it to $T$. This results in a cycle $C$ - call its vertices vertices $V(C)$. We then delete an edge in $C$ incident to a vertex in $V(C)$ with highest degree.

My question is this: if $\Delta(T) > \Delta^*$, can we always find an edge $e$ to add, such that the maximum degree of vertices in $V(C)$ is strictly less in $T'$ than it is in $T$?

No, we cannot always find an edge $e$ to add when $\Delta(T) > \Delta^*$.

The graph above was drawn at https://graphonline.ru/en

Here is an counterexample. Let $G$ be the 3-regular graph on the right side that has 14 vertices and 21 edges. Let $T$ be the spanning tree that consists of all the edges in bold. That is, $T$ has all the edges in $G$ except the innermost 7 edges and the edge at the top right. The graph on the left side shows a hamiltonian path of $G$. That is, $\Delta(T)=3$ and $\Delta^*=2$.

Let $e$ be an edge not in $T$. If we add $e$ to $T$, the resulting cycle $C$ contains at least two non-adjacent vertices of degree 3 in $T$. If we further delete any edge in $C$ incident to a vertex in $C$ with the highest degree 3, we obtain graph $T'$.  There is at least one vertex of degree 3 in $T'$. That is, the maximum degree of vertices in $V(C)$ in $T'$ is 3.


Master Theorem Case 3 Regularity Condition In case 3 of the master theorem, we have to show that

$$ af(n/b) \leq cf(n). $$

I don't understand how I can setup this formula. As an example, we have

$$ T(n)=3T(n/4) + n \lg n.$$

In this case $a=3$ and $b=4$.
This gives us $O(n^{0.793})$ which is smaller than $f(n) = n \lg n$ which means case 3.

Now, the solution is:

$$af(n/b)= 3(n/4) \lg(n/4) \leq (3/4)n\lg n.$$

I'm not sure how we got the above? $af(n/b)$ in my book is $3(n/4)$ so where does $\lg(n/4)$ come from? Also, since $f(n)$ is $n \lg n$, shouldn't the evaluation be:

$$3(n/4) \leq n \lg n ?$$

If $f(n) = n\lg n$ then $f(n/b) = (n/b)\lg(n/b)$, and so $af(n/b) = a(n/b)\lg(n/b)$.