In computer science how is using passive voice regarded? A soft question, when I was in high school and in University I took scientific writing classes and people told me I should use passive voice as much as possible to sound objective, but when I entered grad school people told me I should not use passive voice unless I work in Chemistry. So Which one should I follow?

The bottom line advice is: Use whichever voice best aids understanding.

Many people over-use the passive voice, thinking that it makes them sound more scientific.  In practice, it's more common for the passive voice to make sentences harder to follow.

Therefore, as a rough guideline, it's helpful to use the following principle: use the active voice whereever possible.  If you find yourself writing in passive voice, check whether your sentence would be clearer, simpler, or easier to understand if written in the active voice.

I recommend you read style guides on clear writing.  You'll find they tend to warn against over-use of passive voice: active voice often makes sentences simpler, more direct, more forceful, more vivid, and thus both more concise and more memorable.  Strunk & White have some good examples of this guideline; see, e.g., Rule 11 and Rule 12.

There are some special cases where there are conventions or norms within the field that are worth following.  See, e.g.,

Use of “I”, “we” and the passive voice in a scientific thesis
Is it recommended to use “we” in research papers?.


How would I simulate a network to explore the percolation threshold of a network connected by the knight's move? "If we consider the squares of an infinite chess board as nodes of our graph and consider each to be connected to the other eight squares that are a knight's move away from it what is the percolation threshold of this graph?"

Note:One way I have thought about this problem is to try to use vectors: We can think of a knight's move as a vector of the form $<\pm1,\pm2>$ or $<\pm2,\pm1>$ for the eight cases.

In answering this question I think I need to create a simulation. How would I create a program to simulate an infinite board, for instance, and remove random nodes to create a graph with a percolation value.

First of all, you don't simulate an infinite board. You simulate larger and larger boards, until the percolation threshold seems to stabilize. For a given size of board, you need to decide on what event signifies that percolation happens. One common option is that the top of the board is connected to the bottom of the board. For each probability $p$, you estimate the probability that this happens by doing many samplings. You then use binary search to estimate the probability $p_c$.

Here are some more details. Suppose you've decided on some board size. The first step is to compute all the edges, that is all pairs of vertices connected by a knight's move. Given a probability $p$, you run the following experiment many times. Put in each edge with probability $p$ independently. Then check (using DFS/BFS or equivalent) whether the top of the board is connected to the bottom of the board (that is, add a new "top" vertex connected to all vertices at the top of the board, add a similar "bottom" vertex, and check whether the two are connected). Do this many times, and estimate the probability $\theta(p)$ that "bottom" is connected to "top". Then use binary search on $p$ to find a value of $p$ such that $\theta(p) \approx 1/2$, say. This is your estimate for the critical probability.


NP hardness through Restriction Let's say I have a decision problem  $P$ on graphs for which I know that it is NP-hard on graphs with maximum degree $d$. Does this then imply that it is NP-hard on $d$-regular graphs? Although it might seem obviously true, maybe it is inherent in the reduction to show that $P$ is hard, that some vertices have degree less than $d$.

No, it is not true in general.

A general problem being NP-Hard does not imply a specialization will be NP-Hard. It is true the other way round.

For instance, MAX-CUT is NP-Hard for general graphs, but for the class of planar graphs, it is in P.

In your case, the $d$-regular graphs are a special case of graphs of max degree $d$, so NP-Hardness for max degree $d$ is not an automatic proof of NP-Hardness of $d$ regular graphs.

In fact, for a concrete example, look at this cstheory question: Is there a problem that is easy for cubic graph but hard for graphs with maximum degree 3? with the following answer(by David Eppstein) in the affirmative (copied for convenience):

  Here's a reasonably natural one: on an input $(G,k)$, determine
  whether $G$ has a connected regular subgraph with at least $k$ edges.
  For 3-regular graphs this is trivial, but if max degree is 3 and the
  input is connected, not a tree, and not regular, then the largest such
  subgraph is the longest cycle, so the problem is NP-complete.


What are the differences between propositional logic and temporal logic? I am currently studying temporal logic and find it much similar to propositional logic. However, temporal logic seems to be slightly more specific because it encapsulates more precise meaning symbols, like until, eventually, next etc.. My question is are there other major differences with temporal logic and propositional logic? And can everything expressed in propositional logic be expressed in temporal logic too and vice versa? Perhaps, why would one use one over the other or vice versa?

An interpretation in propositional logic consists of assigning a truth value to every variable. In contrast an interpretation of, say, LTL consists of assigning a truth value to every variable at each point in time. So the domain of discourse is different. Propositional logic is about variables having a definite truth value, whereas LTL is about variables having a truth value depending on time.

Everything that can be expressed in propositional logic can also be expressed in LTL, by just always referring to the truth value at time zero. We say that propositional logic is interpretable in LTL. The converse isn't true – you can't express temporal concepts in propositional logic. You use temporal logic when you need to express temporal concepts. In situations where you don't need to express temporal concepts, you use propositional logic.

The language of set theory is rich enough to encompass both propositional logic (and its extension, predicate logic) and temporal logic. However, the language of set theory might be too expressive for your comfort at times (for example, it may be hard to process algorithmically), which is why we are interested in propositional logic and temporal logic.


Hardware protection needed for operating system kernel I have a question related to the hardware protection needed to implement an operating system kernel:

  Identify at least three hardware level mechanisms that are necessary to protect an operating system kernel from malicious or erroneous user programs.

I can't work out what that would be from the Wikipedia article.

The answer is actually none. This is not what your teacher expects in this homework assignment, but it's true.

The problem in process isolation is to protect against processes that try to access resources that they should not (resources that are used by other programs or by the operating system itself). Resources include memory and peripheral devices.

You can design an operating system that verifies all programs before running them, and only runs a program if it can prove to its satisfaction that the program will never attempt to access a resource that it is not allowed to access. Such operating systems are not very common, but they exist, for example some smartcards running Java Card work like this: only Java bytecode applications can be installed on the card, and they have to have been checked and passed by a bytecode verifier.

That being said, most operating systems enforce process isolation by leveraging hardware means. The most important part is the memory protection unit: a hardware component that assigns privilege levels to blocks of memory and ensures that only programs with the appropriate privilege level can access each block. Often memory protection is performed by a memory management unit which combines protection with virtual memory management, but the indirection afforded by virtual memory is not necessary for the protection aspect. There are processors with an MPU but no MMU. The uClinux project is an example of operating system which enforces process isolation and runs on processors with only an MPU.

In order to be of any use, the MPU has to be combined with some mechanism that assigns privilege levels to programs. Most CPU types that allow privilege isolation have at least two modes (sometimes more), which I'll call kernel and user, with kernel being the most privileged. At any time, the CPU is in one mode or the other. The CPU boots in kernel mode.  Switching into kernel mode from user mode always causes a jump to a fixed address. That way, the initial program that is loaded at boot time remains in control of what can be executed in kernel mode. It is up to that program to set up the MPU/MMU so that other programs cannot overwrite kernel code or access peripherals directly, thus enforcing isolation between kernel code and user code. The kernel is also responsible for changing MPU/MMU settings when switching between programs so that programs can only access their own memory and not other programs'.

That's two mechanism. I don't know what your teacher had in mind for the third one.


A clarification on the taxonomy of Evolutionary Algorithms A rather basic question but I am confused about the characterization of a certain local search method which I want to describe in the framework of EAs. In particular, consider an EA which in every step of the evolution has a neighborhood of size 2; one element in the neighborhood is the current hypothesis (hypothesis in the traditional sense of learning theory) and the other element in the neighborhood is another hypothesis that has arisen from the current hypothesis after applying some transformation/mutation.

It is clear that for such algorithms in the neighborhood we can find at most 1 hypothesis that has strictly better fitness compared to our current hypothesis (our current hypothesis is neutral compared to our current hypothesis). Thus, my question is, how would one characterize an algorithm of this form that always picks among the beneficial set if the set is non-empty, otherwise it would pick among the neutral set (at random - or with some prescribed probability distribution)? Note that the neutral set is always non-empty as the current hypothesis is always there. So, can this algorithm be described as a $(1+1)$-EA or should it be described as a $(1, 1)$-EA? Is there a difference between a $(1+1)$-EA and a $(1, 1)$-EA?

And since we are here, if anyone would be able to clarify the following I would be indebted. What is the difference between a $(1+k)$-EA and a $(1, k)$-EA for $k > 1$. As far as I have understood the comma description (i.e. $(1, k)$-EA) refers to the fact that the algorithm picks the most fit hypothesis among the $k+1$ elements in the neighborhood. The understanding that I have for $(1+k)$-EAs is that they pick at random (however that will be defined) among the hypotheses that have strictly larger fitness values compared to the current hypothesis. Is this understanding correct?

Thank you for your time in advance.

I'm not 100% sure I understand your formulation (things like "our current hypothesis is neutral compared to our current hypothesis" are a bit confusing), but if I understand it correctly, it's this:

You have a current solution and at each time step, you generate a new one based on the current one and some random variation operator. If the new one is better than the current one, you accept the new one. Otherwise, you keep the current one.

That's a $(1+1)$-ES.

A $(1,1)$-ES always accepts the new hypothesis/solution, regardless of quality. A $(1,1)$-ES is just a random walk on the graph defined by your variation operator. For a $(\mu$, $\lambda)$-ES, the algorithm generates $\lambda$ hypotheses at each step, and selects the best $\mu$ of them to form the population for the next generation -- the current hypotheses never survive (unless your variation operator produces a copy of one of them). The $(\mu+\lambda)$ strategy takes the best $\mu$ from the union of the current population and the new one.


integer = c lg n (inputs of size n, Cormen 3rd, page 23)? I just started with my "Algorithms" course. But my CS-background is lower than that of an average CS-student (I'm a data science student). Only had intro-2-prog course (Python/Java), that's it.

Cormen states on page 23: "...when working with inputs of size n, we typically assume that integers are represented by c lg n bits..."

How is " c lg n " derived? It's relation to the input size?
What calculation/proof is made here?
Which assumptions should one have to come to this assumption?
Which CS-field/subject (or academic/uni course?) works/operates with this notation, that should be learned prior to the "Algorithms" couse?

lg n is the base-2 logarithm of n, satisfying 2^lg n = n, so about lg n bits (ceil lg n to be exact) are needed for integers that can represent 0..n-1, which suffices for pointers into the input. The authors of CLRS are saying that the word size should be about this much (c lg n). This is arguably reasonable because c lg n-bit words index storage of n^c (so any polynomial in n), and c lg n-bit operations can be synthesized from lg n-bit operations in constant time. If we make the word size much bigger, then the implied data-parallelism starts to distort running times.

The mathematical preliminaries here should be covered in an intro discrete mathematics class.


How can I evaluate an algorithm for a NP-Hard problem? I have written a program to calculate the number of stable partition in a graph.
 ( That is: find which partition of the nodes does not have edges between nodes of the same block. )

The professor, asked me a way to evaluate the performance of my algorithm (not the program), but my algorithm is simply a brute force of all the possible cases, and I don't think you can do any better without heuristics, therefore I think the questions makes no sense (at least to me).

Am I wrong?

It doesn't matter for what the algorithm is for, that is, you can analyze an algorithm for an easy problem (e.g. sorting) just like you would analyze an algorithm for a hard problem (e.g. 3-SAT). So the question does make sense.

Think about how your brute force method works. If you try all partitions of nodes, how many possible partitions are there? This is the way your analysis should work. Given that the problem is NP-hard, one should not expect a polynomial time algorithm though, but that's fine.


Dynamic Programming Travel Planning Problem You want to visit n cities: $0 → 1 → 2 → · · · → n$.

For traveling between city $i$ and $i + 1$ $(0 ≤ i < n) $ you need to choose between two modes of transportation: train or plane. You are starting at the train station of city $0$ and want to end up at the airport of city $n$.

The cost of transferring between the train station and the airport of city $i$, either direction, is $b_i$. The cost of traveling from city $i$ to city $i+1$ via train is $t_i$ and by plane $p_i$.

You need to use to use the plane and train exactly $n/2$ times. Assume that $n$ is divisible by $2$.
Design an $O(n^2)$ dynamic programming algorithm that finds the cost of an optimal solution to the travel planning problem.

What I have so far is what I think is a solution to the problem without considering the $n/2$ constraint.

$Cost(x, i, y) = \begin{cases} \begin{cases}t_i & y=0\\ p_i + b_i & i-y=0 \end{cases} & i=1 \\ min\begin{cases} \begin{cases} min\begin{cases}p_i + Cost(P, i-1,y-1) \\ p_i + b_i + Cost(T, i-1,y-1) \end{cases} & y > 0 \\ inf & y=0 \end{cases} \\ \begin{cases} min\begin{cases} t_i + Cost(T, i-1,y)\\ t_i + b_i + Cost(P, i-1,y) \end{cases} & i-y > 0\\ inf & i-y = 0\end{cases}  \end{cases} & 1 < i < 0  \\ min\begin{cases}p_i + Cost(P, i-1,y-1) \\ t_i + b_i + Cost(T, i-1,y) \end{cases}  & i=n \end{cases}$

The values of $x$ correspond to different scenarios for which station at $i$ you are located at.

$x = P$

$x = T$

The value of $y$ is the number of plane rides and $i-y$ is the number of train rides $0 \le y \le i$

To get the optimal cost with $n/2$ plane rides you would call $Cost(x,i,\frac{x}{2})$

Hint: For each $0 \leq i \leq n$ and $0 \leq t \leq i$, calculate the optimal route between city $0$ and city $i$ using $t$ plane rides and $i-t$ train rides.


An algorithm for comparing a DFA and a regular expression Assuming I have an encoding of a DFA $<M>$ and a regular expression $<r>$, I'm interested in finding an algorithm for comparing whether or not $L(M)=L(r)$.

I have thought about converting $r$ into an NFA, and then converting the NFA to a DFA, but the problem is that this process may result in a totally different DFA.

Another idea I had was to convert the DFA to a regular expression. But with this idea, I have two problems: first is that I'm not sure how exactly is ut done, and second - even if I will succeed in doing so, I might again end up with a totally different regular expression (that has the same language, but written differently).

Obviously, a third approach would be to start looping all over $\Sigma^*$, but this is an infinet process...

Does someone have a different idea or a way to improve my approaches to this problem?

I would like my algorithm to be able to both return "true" if $L(M)=L(r)$ and false otherwise (my third approach can only return false, but will never return true).

This technique I am going to describe works to compare two NFAs. Fortunately, you have mentioned that you know how to convert your regular expression into an NFA and it is trivial to convert your DFA into an NFA. (just treat the DFA as though it were an NFA)

Once you have your two NFAs, add two new symbols to your alphabet: $\$_1$ and $\$_2$. We're going to construct a larger NFA by combining the two NFAs that we have. Add a node (call it $\omega$), and add edges from every accepting node in the first NFA to node $\omega$ labeled with $\$_1$. Now add edges from every accepting node in the second NFA to node $\omega$ labeled with $\$_2$.

Now add another node (call it $\alpha$) and add epsilon-transition edges from $\alpha$ to the initial node in each NFA. (so $\alpha$ has only two edges leaving it). (alternatively, since some people don't like epsilon transitions, you can instead add to $\alpha$ all the outgoing edges of the initial nodes in each original NFA)

Now take this combined graph with the two extra nodes as an NFA: the initial node is $\alpha$, and the only accepting node in the combined graph is $\omega$.

Turn this NFA into a DFA. One side-effect of how we constructed edges into $\omega$ is that the DFA will have only a single accepting state. The two original languages will be identical if and only if in the DFA every edge going to this accepting node is labeled with both $\$_1$ and $\$_2$.

Essentially, what we did was form the languages:
\begin{align}
L_1 &= \{ w \ \$_1 \  | \ w \in L(M)\} \\
L_2 &= \{ v \ \$_2 \  | \ v \in L(r)\}
\end{align}
and then our combined NFA was the NFA for the language $L_1 \cup L_2$. The statement about the edges of the DFA says that there exists some set $A$ such that the language of our DFA is
$$\{a \ x \ | \ a \in A, x \in \{\$_1, \$_2\} \}$$
But this implies that if you stripped the $\$_i$ symbols off the end of the strings in $L_1$ and $L_2$ you'd have the same language.

Incidentally, you can use this DFA for $L_1 \cup L_2$ to easily construct DFAs for $L(M) \cap L(r)$, for $L(M) \cup L(r)$, for $L(M) \setminus L(r)$, for $L(r) \setminus L(M)$, and for the symmetric difference of $L(M)$ and $L(r)$. The exact details are left as an exercise for the reader, but it involves examining nodes with outgoing edges labeled with one of the $\$_i$ symbols, labeling some of those nodes as accepting nodes, and then erasing all edges labeled with the $\$_i$ symbols.

(These won't necessarily be minimal DFAs, even if you minimized the DFA before erasing the $\$_i$ edges. You'll need to apply standard DFA minimization algorithms if you want that.)


Multiple rounds of bipartite matching problem I have a set of investors (say n), and a set of startups (say m). At the start, I have all the investors say either yes or no to the startup (which corresponds to whether they want to interact with them or not).

Now, I have to conduct a networking event of r rounds considering this scenario. In each round, I match investors with startups they want to meet (one investor with one startup). I want to conduct the rounds such that the sum of the startups they met, across all investors, is maximum.

Now, if r=1, this reduces to the maximum bipartite matching problem. Does anyone have any ideas on how to solve this for r>1? I have been thinking along the lines of having the source and sink edge capacities to be r instead of 1, but I am unable to prove that this works.

You can solve this by a mild extension of the standard reduction to network flow: increase the weight of the edges touching the source and the sink to $r$. Any integer flow corresponds to a union of $r$ matchings:

An integer flow corresponds to a bipartite graph of maximum degree $r$.
We can complete this bipartite graph to an $r$-regular bipartite graph by adding vertices and edges:

Add vertices so that both sides have the same number of vertices.
If the graph is not $r$-regular, then there must be two vertices $x,y$ (one on each side) with degree less than $r$. Add $r$ new vertices $x_1,\ldots,x_r$ and $y_1,\ldots,y_r$ to each side (respectively), and connect all of them except $x_1$ and $y_1$. Connect $x$ to $y_1$ and $y$ to $x_1$. This reduces the overall deficiency of the graph $\sum_v (r - \deg(v))$ by 1.

Repeated applications of Hall's theorem shows that the new graph can be decomposed into $r$ perfect matchings.
Restricting these matchings to the original vertices and edges, we obtain a union of $r$ matchings.

Schrijver mentions this problem in his Combinatorial Optimization (Vol 1):

  Corollary 21.4b. Let $G = (V,E)$ be a bipartite graph and let $k \in \mathbb{Z}_+$. Then the maximum size of the union of $k$ matchings is equal to the minimum value of $k|V \setminus X| + |E(X)|$ taken over $X \subseteq V$.

This follows by an application of the min cut max flow theorem.


To check whether the problem of a particular string being a member of CFG G is decidable or not, why can't we use a PDA? Why can't a TM simulate a PDA? Then we can easily construct a PDA P which is made from grammar G. And contruct a TM that simulates P to prove that this problem is decidable.

Consider a pushdown automaton which has an $\epsilon$-transition which adds $A$ to the stack, and another $\epsilon$-transition that removes $A$ from the stack. Clearly, this PDA has accepting computations of unbounded length. There is no a priori bound on the shortest computation needed to accept a string of a certain length (though perhaps you can come up with such a bound if you're smart enough!).

Why is this a problem? Consider a deterministic Turing machine which runs all possible computations of the PDA, accepting if it finds an accepting computation, and rejecting otherwise. If there is no computable upper bound on the length of a computation, then the Turing machine will have to try infinitely many computations in the rejecting case, and so won't halt on rejecting inputs.

The same problem occurs with context-free grammars having unit productions (consider for example a grammar with the productions $A\to B$ and $B\to A$). After removing unit productions and $\epsilon$-productions, the problem goes away, and you can use dynamic programming to decide the language of the context-free grammar. This is (essentially) the CYK algorithm.


Is well-founded recursion enough for practical total functional programming? Total functional programming is a paradigm of non-Turing-complete programming languages where any program that type checks is proven to halt.
Well-founded recursion is a recursive definition of a function such that the definition of $f(x)$ only ever makes a recursive call $f(y)$ when $y<x$ for some well-founded relation $<$.
But the wikipedia page of Total functional programming refers also to other types of provably-terminating recursion:

[Termination is guaranteed by] a restricted form of recursion, which operates only upon 'reduced' forms of its arguments, such as Walther recursion, substructural recursion, or "strongly normalizing" as proven by abstract interpretation of code.

Are there any ways that one can do better than well-founded recursion, for practical total functional programming? I've always thought of well-founded recursion as "the most general provably terminating recursion"

Let's restrict ourselves to the model of Turing machines (or, in general, of state machines). Consider complete states $s_1, s_2$ of the Turing machine (a complete state is a state specifying the full configuration of the Turing machine). We say that $s_1 \gets s_2$ if and only if we transition from $s_2$ directly to $s_1$.
It is easy to see that the Turing machine will terminate from any state if, and only if, $\gets$ is a well-founded relation.
A similar result holds for a strict language based on the $\lambda$-calculus. It's possible to determine whether a given term $T$ will reduce to a normal form by considering the $\beta$-reduction relation $\gets_\beta$ on all terms which $T$ can be reduced to. $T$ will reduce to a normal form under any reduction order if and only if $\gets_\beta$ is well-founded.
Thus, it's really not possible to get any more general than well-founded relations for proving termination.


Algebraic (spectral) algorithms for the minimum spanning tree problem Are there any algorithms that use the spectral properties of a graph to solve the minimum spanning tree problem?

To clarify further what I have in mind, starting with the Laplacian matrix I want to algebraically arrive at the required set of edges. This is opposed to Prim's or Kruskal's algorithm where the result is obtained by operating on the edges/vertices sets directly.

In short: no, not that I know of and I would be surprised if they exist.
For something longer, read on:

I don't think the spectrum of a graph can be of much use in finding an MST. The main reason is this: weights of a graph aren't part of the spectrum of a graph! An MST only makes sense on a weighted graph.

The only thing I see we could try, if all weights are integral, 'unfold' the graph such that all weights are unit-weights (so an edge of weight $32$ becomes $32$ edges and $31$ nodes in them) and mark the original nodes and make a min-cost tree that spans the original edges. After this transformation, the spectrum might contain all relevant info, but this transformation step makes our new graph simply horribly large, so any algorithm based on this will have an awful running time. This is simply a bad idea.

I've never heard of a useful way to 'attach' weights to edges in the adjacency matrix and connect them to the spectral properties, either. It doesn't seem likely to work, although proving a vague method won't work is of course impossible.

Of course, the fact that spectral properties likely aren't useful doesn't mean algebraic methods in general won't work. What is important is that you don't leave the edge weights behind. However, most other algebraic methods are used for exponential time algorithms and I'm not aware anyone has constructed something algebraic for MST.


Looking for a good algorithm to divide the nodes of a complete graph into groups I have a set of locations, around 100, I want to divide into groups.

I say these locations are in a graph because the geometric proximity (straight line distance) doesn't matter to me, and I have a matrix of the distance (non straight line distance) and time, that would take to travel from any location to another. Either one, time or distance, can be used as edge weights for this complete graph.

The idea is to assign a group of locations to a person that will visit the locations in it, (there is no obligation to do a traveling salesmen or visit them in a specific order or to avoid passing on a repeated node).

Ideally these groups have a minimum of 8 locations, and a maximum of 11 locations. (For simplicity maybe a set amount of 10 per group would suffice).
And I want to minimize the sum of weights needed to visit all the nodes in a group at least once.

All locations must belong to one group, and only one group.

Where do i go from here?
I'm kind of rusty on graph theory. Is there a good algorithm for this already? It doesn't need to be optimal and I do understand that this will probably be an NP hard problem and not very efficient.
Because i'm treating it as a graph i keep finding graph algorithms but most i find are not suited for weighted graphs or complete graphs.

One possible approach would be to use local search.  This probably won't find the optimal solution, and there are no guarantees, but if you're lucky, it might find a solution that is decent.

In local search, given a candidate solution, you need a way to randomly pick a neighboring solution.  In the context of your problem, one way to do that might be to pick a pair of groups and a vertex $v$ in the first group, and remove $v$ from the first group and add it to the second group.  (This will only be legal if the first group is not already at the minimum size, and the second group is not already at the maximum size.)

You could then apply a technique like simulated annealing.  You'll probably need to experiment with the tuning parameters, and experiment with the method, to see whether it produces useful solutions or not.

This will require you to be able to quickly compute the effort associated with a single group, given the list of vertices in the group.  You might want to ask separately about that problem.  It sounds related to the Traveling Salesman Problem, which is NP-hard, but there are off-the-shelf solvers that implement sophisticated algorithms for finding a solution, and for the group sizes you are talking about (8-11 vertices), this might be relatively fast.  The twist in your situation is that the TSP doesn't allow visiting a vertex more than once, but it sounds like you are willing to allow repeated visits, so we need to make adjustments to make to allow that.  The following method should suffice: use an all-pairs shortest paths algorithm to compute the distance $d(u,v)$ between each pair of vertices, then replace the edge weight on the edge $u \to v$ with $d(u,v)$, then find the TSP solution; after this adjustment, no repeated visits will be needed any longer.


How to find mean ,max ,min in constant time? I was asked to be able to find minimum, maximum and mean of a large array in constant time. I used 3 variables to track these statistics and updated them on every insert operation. I don't feel like it is the correct answer or maybe there is more nuance. Given that nothing was said about extra space, is this the simplest(and correct) way to do it ?

If you are just given an array and asked to find these statistic there there is no way to do that (unless the size of the array is upper bounded by a constant). An easy way to convince yourself that this is true is noticing that in $O(1)$ time you can only access $O(1)$ entries of the array. Then the maximum, minimum, or median could be in the unread entries (notice that you can safely assume that any $O(1)$-time algorithm always accesses the returned entry).
You talk about "insert operations" which makes me thing that you were actually asked to design a data structure that supports some set of operations, among which there are insertions and reporting the above statistics. If this is the case then the answer depends on how what the other operations are and how much time do you want to spend on those.
If the only updates to the array are insertion then it suffices to keep track of the number of elements, their sum, and the maximum and minimum element after each insertion. This will require $O(1)$ time per insertion and $O(1)$ time to report the statistics.


tcp congestion avoidance I came across this question:

At the beginning of transmission t, a TCP connection in congestion avoidance mode
has a congestion window w = 60 segments.Packet loss is observed during transmission
rounds t, t+10, and t+20 by getting multiple ACKs. What is the congestion window
at the end of round t, t + 10, and t + 20?

If there's no further packet loss, when will the window of w = 60 segments be reached again?

Answer:

Congestion window is halved during transmission round t, leading to w = 30. At the
beginning of transmission round t + 10, the window has increased to w = 40 but it will be
halved again during transmission round t + 10 to w = 20. Similarly, after transmission round
t + 20, the window will be w = 15. With no further packet loss, 45 transmission rounds later
at t + 65, the window will reach again the original size of w = 60.

I know that due to multiple ACKs, packet loss reduces the window size to half. So at t+10, w = 30 makes sense. However, I don't really get the rest. Why does the window size increase by 10? And at t+20, why doesn't it reduce to 10 instead of 15? If someone could explain the steps, that would be great.

When we are in AC mode every rtt(round trip time) the congestion window increase by 1(MSS).
Here our current congestion window(cw) is 60 and we know that during transmission round t we get 3 duplicate acks-so our window is now 30MSS,now we also know that from t to t+1 for instance our window increase by 1,so from t to t+10 our window increases by 10-which means our window is now 40.
We know that during the t+10 round we will get 3 duplicate acks,so now our window will become 40/2=20.
From round t+10 to t+20 our cw increase by 10 more-so now its 30,and in addition we know we will get 3 duplicate acks-which means now our window will be 30/2=15MSS


Selecting a random 'bad' element from an array of $n$ values in $O(n)$ time and $O(1)$ space without knowing how many bad elements or where they are I have an array of elements $A = [x_0, x_1, \ldots, x_n]$, such that for some $0 \leq k \leq \frac{n}{2}$, there are $k$ 'bad' elements in $A$, but I don't know what indices they are at, or indeed, how many there are aside from the given bounds. I have a function which can, in $O(1)$ time, check if something is 'bad' or 'good'. As $A$ is an array, I have the ability to access any element of $A$ in $O(1)$ time if I know the index.

My goal is to devise a procedure which, in $O(n)$ time and $O(1)$ space, returns the index of a randomly-selected 'bad' element in $A$, or $-1$ if no such element exists. Any 'bad' element should have an equal chance of being selected. My current approach was something like this, assuming coin is a procedure that returns 0 or 1 with equal probability:

function randombad(A):
    result := -1
    for (i from 0 to (length(A) -1))
        if (A[i] is bad and result = -1)
            result := i
        else if (A[i] is bad)
            flip = coin()
            if (coin = 1)
                result := i
    return result

However, if $k > 2$, this obviously gives later 'bad' elements a higher chance of being chosen, which is not what I want. Is there a way to do what I want without having to store every 'bad' element as I find them (which violates the $O(1)$ space constraint)?

You can do better than $O(n)$ time: indeed $O(n/k)$ time and $O(1)$ space is achievable, with a perfectly uniform distribution on bad elements.  Let me explain how, by starting with a simple strategy and building up to a solution that meets all of your requirements.

If we didn't have to deal with the possibility that no bad element exists, then a simple (but sub-optimal) method is to apply rejection sampling: repeatedly pick a random element, test if it is bad, and if it is bad, return it.  In other words, you return the first bad element found.

If there is at least one bad element, this method is within a constant factor of optimal; the average running time is $O(n/k)$, and it uses only $O(1)$ space.

The big flaw with this simple approach is that if there are no bad elements, this algorithm runs forever.  Fortunately, we can repair that with a simple fix, and at the same time improve running time to optimal.

Here's how.  Pick a random permutation $\pi$ on $\{1,\dots,n\}$.  Then, sequentially test $A[\pi(1)]$, $A[\pi(2)]$, ..., and return the first bad element you find.  If you have tested all $n$ array elements and found no bad element, terminate and return -1.

This algorithm requires (on average) $\min(n/k,n)$ queries to the oracle, which is optimal -- you can't do better than that.  The space requirement, apart from the time to store $\pi$, is $O(1)$.  This also provides a perfectly uniform distribution on the set of bad points: because it is essentially a rejection sampling strategy, it is correct for the same reason that rejection sampling is.

At this point you might object that storing the permutation $\pi$ explicitly requires $O(n)$ space.  You would be correct, but fortunately there is a fix to that: you can construct a pseudorandom permutation on $\{1,\dots,n\}$ with $O(1)$ space to store it, and $O(1)$ time to evaluate the permutation.  See Lazily computing a random permutation of the positive integers and https://crypto.stackexchange.com/q/20035/351 and links there.  Technically speaking, the space and time to evaluate the oracle is probably more like $O(\log n)$ than $O(1)$, but given that $n\le 2^{64}$ in practice, the difference might or might not be critical.

Caveat: This is an engineering-oriented answer.  From a theoretical perspective, it's probably not fully satisfying.  The use of a pseudorandom permutation means that the distribution on bad instances is not perfectly uniformly random; it is close to random (indistinguishable from random).  Also, I haven't been fully-rigorous about the running time or space requirements for the pseudorandom permutation.  Finally, the use of pseudorandom permutations relies on unproven assumptions (that certain crypto primitives are security).  See the comments for more discussion of caveats.


Why isn't the search space size of TSP $(n-1)!$ instead of $n!$? I'm just learning about the travelling salesman problem, and I've been playing around with it. I'm not sure if what I've found is just a special case or not. My professor says the search space size is $n!$, where $n$ is the number of cities.

Suppose we have a table with cities $A,B,C,D$ on each axis, and the elements represent the distances between cities:

\begin{array}{|c|c|c|c|}
\hline
& A & B & C & D \\ \hline
A&0 & 2& 3&4\\ \hline
B& 2 & 0& 10&5\\ \hline
C& 3 &10 &0 &15\\ \hline
D& 4 & 5& 15&0\\ \hline
\end{array}

From this, I can generate various permutations of possible tours, and their lengths:
$$A \to B \to C \to D \to A : 31$$
$$A \to B \to D \to C \to A : 25$$
$$A \to C \to B \to D \to A : 22$$
$$A \to C \to D \to B \to A : 25$$
$$A \to D \to B \to C \to A : 22$$
$$A \to D \to C \to B \to A : 31$$

Now, it seems to me that each of these permutations is cyclical. In this way, $B \to C \to D \to A \to B : 31 $ and $A \to B \to C \to D \to A : 31$ are equivalent, for example.

So in fact, it doesn't matter which city I choose initially, because the resulting shortest tour will be equivalent to one of the tours above.

And clearly, there are $3!$ of these tours, or $(n-1)!$ of them. So why isn't the search space size $(n-1)!$ instead of $n!$? Maybe there is a problem with my understanding of what search space size is, I'm not sure.

The search space has size $(n-1)!$. You can see this in many ways, for example:

Each tour corresponds to $n$ different permutations, depending on the starting point.
If we start describing the tour at some point $P$ fixed ahead of time, then the tour is given (injectively) by an arbtirary permutation of the remaining $n-1$ points.

The reason that sometimes $n!$ is used is that $n!$ is shorter, and the difference between $n!$ and $(n-1)!$ is not always important.


Can one find an algorithm whose running time is larger than Ackermann's function? Is there an example of an algorithm whose time complexity is strictly larger than Ackermann's function?

$A(n,n)$ is computable. So a trivial algorithm with complexity $O(A(n,n)^2)$ is the following:

Compute $x = A(n,n)$.
Loop $x^2$ times, doing nothing.


Is the set of Turing machines which stops in at most 50 steps on all inputs, decidable? Let $F = \{⟨M⟩:\text{M is a TM which stops for every input in at most 50 steps}\}$. I need to decide whether F is decidable or recursively enumerable. I think it's decidable, but I don't know how to prove it.

My thoughts

This "50 steps" part immediate turns the R sign for me. If it was for specific input it would be decidable. However, here it's for every input. Checking it for infinite inputs makes me think that the problem is co-RE, i.e. its complement is acceptable.

Perhaps, I can check the configurations and see that all configurations after 50 steps don't lead to accept state- how do I do that?

Let's consider the more general problem of machines which stop after at most $N$ steps, for some $N \geqslant 1$. (The following is a substantial simplifcation of a previous version of this answer, but is effectively equivalent.)

As swegi remarks in an earlier response, if the machine stops after at most $N$ steps, then only the cells $0,1,\ldots,N-1$ on the tape are significant.
Then it suffices to simulate the machine $M$ on all input strings of the form $x \in \Sigma^N$, of which there are a finite number.

If any of these simulations fail to enter a halting state by the $N^{\text{th}}\:\!$ transition, this indicates that any input string starting with $x$ is one for which the machine does not stop within the first $N$ steps.
If all of these simulations halt by the $N^{\text{th}}\:\!$ transition, then $M$ halts within $N$ steps on all inputs of any length (of which the substring of length $N$ is all that it ever acts on).


Is the sieve an improvement for prime finding over an optimized algorithm? I don't think it is, as you have to loop through each set multiple times at least.

implementation of sieve in JS - in the answer at the bottom.  The link shows a 10X improvement using sieve.

In this case it is faster b.c. the function changes the integers to bits and is working with bits instead of integers.

But if you look at the structure of the code it has 3 loops.  An optimized non sieve version has only 2 loops.

For example here is an optimized algorithm:

function findPrimes(n){
  const primes = [2];
  label: for(let i = 3; i <= n; i += 2){
    for(let j = 0; j < primes.length; j++){
      if(i % primes[j] === 0) {
        continue label;
      }
    }
    primes.push(i);
  }
  return primes;
}

and here is the sieve method using bit-wise operations.

  "sieve": function sieveOfEratosthenes(n) {
    var sieve = new Int32Array(Math.ceil((n + 1) / 64)).fill(-1);
    var primeVals = [2];

    for (var i = 3; i * i <= n; i += 2) {
      if (sieve[i >> 6] & (1 << (i >> 1 & 31))) {
        primeVals.push(i);

        for (var j = i * i; j <= n; j += i + i) {
          sieve[j >> 6] &= ~(1 << (j >> 1 & 31));
        }
      }
    }

    while (i <= n) {
      if (sieve[i >> 6] & (1 << (i >> 1 & 31))) {
        primeVals.push(i);
      }
      i+=2;
    }
    return primeVals;
  }

Sorry, but you can’t just count loops, the number of loops is totally irrelevant.

If you count nested loops, that is slightly significant but can be very misleading.

You need to count how many iterations a loop performs. In the first example, the number of iterations is up to primes.length, which is around n / log n. In the second example, the number of iterations in the inner loop is less than n / 2i, and i grows quickly.

Add a counter to each function and see how often the inner loop gets executed.

PS. Let n = 1 billion, and print say every 100th prime added to primeVals. Then check how long it takes. The sieve will take a good time. But I can promise you, the “optimised” algorithm will be a lot more than ten times slower.


Multisets of a given set A multiset is an unordered collection of elements where elements may repeat any
number of times. The size of a multiset is the number of elements in it counting
repetitions.

(a) What is the number of multisets of size $4$ that can be constructed from $n$
distinct elements so that at least one element occurs exactly twice?

(b) How many multisets can be constructed from $n$ distinct elements?

For part b, infinite is correct.

For part a, taking $n=3$ and elements $\{1,2,3\}$ we have multisets as:
$\{1,1,2,2\}, \{1,1,3,3\}, \{1,1,2,3\}, \{2,2,3,3\}, \{2,2,1,3\}, \{3,3,1,2\}$, for a total of $6$.

Similarly for $n=4$ and using elements $\{1,2,3,4\}$, we have $18$ multisets. There must be some formula, or we have to develop one!

I am in particular looking for a formula when there is a restriction on the number occurrences in the multiset.

Here is one way to go about your part (a):

There are four places to be filled in the multiset using the $n$ distinct elements. Atleast one element has to occur exactly twice. That would leave 2 more places in the multiset. This means, atmost two elements can occur exactly twice. We can thus divide this into 2 mutually exclusive cases as follows:

Exactly one element occurs exactly twice: Select this element in ${n\choose{1}} = n$ ways. Fill up the remaining two spots using 2 distinct elements from the remaining $n-1$ elements in ${{n-1}\choose{2}}$ ways. Overall: $n \cdot {{n-1}\choose{2}} = \frac{n(n-1)(n-2)}{2}$ ways.
Exactly two elements that occur twice each: These two will fill up the multiset, so you only have to select two elements out of $n$ in ${n\choose 2} = \frac{n(n-1)}{2}$ ways.

Since these are mutually exclusive, the total number of ways to form the multiset is:
$$\frac{n(n-1)(n-2)}{2} + \frac{n(n-1)}{2}$$$$ = \frac{n(n-1)^2}{2}$$

Note, that $n \ge 2$ otherwise no element can be present twice. This is also obvious from the formula (when $n = 0, 1$).

You can check that the formula tallies with your counts.


Find the minimal subset of rows of some matrix such that the sum of each column over this rows exceeds some threshold Let $A$ be a an $n\times m$ real valued matrix. The problem is to find the minimal subset $I$ of rows (if there is any) such that the sum of each column $j$ over the corresponding rows exceeds some threshold $t_j$, i.e. $\sum_{i\in I}A[i,j]>t_j$ for all $j\in\{1,\dots m\}$.

Or, stated as optimization problem:

Let $A\in\mathbb{R}^{n\times m}, t\in\mathbb{R}^m$. Now solve
\begin{align}\min_{\xi\in\{0,1\}^n}&\sum_{i=1}^n\xi_i\\\text{s.t.}&\,A^\top\xi>t\,.\end{align}

Actually, i would need a solution only for $m=2$, but the general might be interesting too.

The general $n \times m$ case is easily seen to be NP-hard by reduction from set cover. Add a column for each element; each row is the indicator function of a subset; set $t_j = 0$ for each column.

A slightly more complicated reduction from subset sum shows that this is NP-hard even for $m = 2$. Suppose we are given a subset sum problem instance where we have a set $B$ of integers and the goal is to find a subset of $B$ that sums to exactly $k$. We reduce this to your problem as follows: for each integer $b \in B$, add $[b, -b]$ as a row to $A$; then set $t_1 = k - 1$ and $t_2 = -k - 1$. This enforces that the sum of the chosen subset must be greater than or equal to $k$ and also less than or equal to $k$, and therefore exactly equal to $k$.

For solving this problem in practice, I would recommend an integer linear programming solver. Most such solvers have direct support for 0-1 variables, so the linear optimization version you describe in the question can be presented to the solver exactly as written.


maximum cardinality weighted matching I am looking for a reference for maximum cardinality weighted matching and the best running time algorithm for it.
Maximum Cardinality Weighted Matching: Given an undirected weighted graph $G(\mathcal{V},\mathcal{E})$ where $\mathcal{V}$ is set of vertices and $\mathcal{E}$ is the set of edges where each edge $(i,j) \in \mathcal{E}$ assigned a positive weight $w_{ij}$. Matching is the subset of edges such that no two edges share a vertex. The maximum cardinality weighted matching is the matching that maximizes the total weight of edges in the subset of matching that maximizes the total number of edges chosen in the matching
I searched but there is always maximum weighted matching which means the matching has maximum weight but may not has maximum cardinality all the time. I appreciate it if you can recommend a reference for the maximum cardinality weighted matching. I want the matching that maximizes the cardinality first then the weigt of the matching.
For example, 1 --- 2 --- 3 --- 4
The weight between 1 and 2 is 1.
The weight between 2 and 3 is 10.
The weight between 3 and 4 is 1.
The maximum cardinality weighted matching I want is 1--2 and 3--4.
The maximum weighted matching outputs 3--4

If you take $S$ to be the sum of all the weights on all the edges in the graph and you add $S$ to all the weights in the graph, then a regular maximum weight matching will find you the matching you are looking for, since now with the large weights on all the edges, it will prefer a matching that uses the most number of edges first.
In your example of 1--2--3--4 with weights 1, 10, 1, here we have $S=12$, so add 12 to all the edges to have edge weights of 13, 22, 13 and now a regular max weight matching would prefer 13+13 over 22.
I'm not sure if it is easy to prove that $S$ is quite big enough, but it should be easy to prove that $mS$ is big enough to all to all edges (that is, sum of all edges times the number of edges).


Is this a legal Fibonacci heap? Imagine a Fibonacci heap with 1 tree: a root node, 4 child nodes (to that root node), with 2 of them being leaves and the other 2 having 1 child each (7 nodes total). Is this a legal Fibonacci heap? In other words, does there exist a series of actions that lead to this sort of heap structure.

My intuition tells me no, because it just seems too "unstructured". On the other hand, it doesn't seem to violate the max degree property or any other basic properties of a Fibonacci heap.

I thought about extracting the minimum and seeing if that'll lead to an illegal heap, but it doesn't seem to be the case.

It's not possible. You propose a root node with degree 4 and size 7 (including itself).

From CLRS 3ed pp 525:

  Lemma 19.4

  Let $x$ be any node in a Fibonacci heap, and let $k = x.degree$. Then $size(x) \geq F_{k + 2}$.

$$
\begin{align}
k & = 4\\
F_{6} & = 8\\
7 & \ngeq 8\\
\end{align}
$$


Can there still be infinite recursion if I remove all left recursion? I have to transform the following grammar into a non left recursive grammar:

S →  aSb | bAS

A →  AaA | bAA | AAa | bAb

This is what I came up with:

A → bAAA’| bAbA’

A’ → aAA’| AaA’| ε

S →  aSb | bAS

As far as I can tell, there is no more left recursion because none of the leftmost symbols on the RHS are the same as the nonterminal on the left. However, assuming S is the starting symbol, there is still infinite recursion because A calls itself repeatedly. Is this expected? Or did I derive the non left recursive grammar incorrectly?

Take a look at the following rule in the original grammar.
$\quad S \to aSb \mid bAS$
If you start generation from $S$, you cannot get rid of $S$.
$\quad A \to AaA \mid bAA \mid AAa \mid bAb $
If you continue applying production rules from a sentential form that contains $A$, you cannot get rid of $A$, either.

These rules are called unproductive rules. Unproductive rules and unreachable rules are called useless rules. You may take a look at this question.

If there are useless rules in the original grammar, there will be useless rules after the transformation by pure left-recursion removal procedure. That is why you see "there is still infinite recursion because $A$ calls itself repeatedly". There is nothing wrong with your transformation to that non-left-recursive grammar.

Those useless production rules can be remove by some algorithms.
We can see that the original grammar in the question will become empty after such cleaning. Indeed, the original grammar generates the empty language, the language that contains no words.


NFA: each block of five consecutive characters contains at least two 0's How can I find an NFA for such a language, considering the alphabet to be {0, 1}. I've tried deriving it from the DFA (@Steven) and the regular expression (@Yuval Filmus), but no luck.

Your DFA is already a NFA, so you're done.


When is bidirectional search unusable? Is there any situation that bidirectional search on a graph is not applicable? for example is there any classes of graph that we can only use ordinary Dijkstra's algorithm, and can not use its bidirectional variant.

The graph may be a dynamic graph.

Yes, a simple one is coming to my mind, a dynamic graph where the search operators are not reversible, i.e. both predecessors and successors of a node in the graph can not be calculated.


How to make Turing machine deterministic? My Turing machine starts with an empty tape. It writes a random word of the set $0^n1^n$ to the tape. Hopefully i made no mistakes.

My question is about the productions coming out of state $q_0$:

$δ(q_0, blank)=(0,R)$ and $δ(q_0,blank)=(blank,L)$. (see image below).

Their purpose is to generate a random amount of $0$ before going to state $q_1$. They are nondeterministic. Is there a workaround to make them deterministic?

I heard that every Turing machine can be made deterministic. But this case is a little bit strange, because instead of testing if a word on the tape is element of a set, it writes a random word of the set to the tape.

If a language is decided by some nondeterministic Turing machine, then it is decided by some deterministic Turing machine. However, not every behavior of a nondeterministic Turing machine can be replicated deterministically, as your example demonstrates.


3SAT analogous problem in P Is there a problem like 3 SAT like problem in P where if we find an algorithm for this problem, we can solve all problems in P?

For instance if we solve this problem in P, may be we can solve prime detection quickly instead of using AKS algorithm or linear programming quickly?

You might find Greenlaw, Hoover and Ruzzo's "Limits to Parallel Computation: P-Completeness Theory" interesting. It obviously goes a lot further than the limits of this question, but most pertinently includes in Appendix A a compendium of P-complete problems in the style of Garey & Johnson. There are far too many to be worth listing here, but some key ("interesting") problems are:

The Circuit Value Problem
Linear Inequalities (this is one way to get a decision version of Linear Programming)
Maximum Flow
Context-free Grammar Membership
Point Location on a Convex Hull


Algorithm to build tri-nodes in MapleStory This problem is originated from the game MapleStory, where the player needs to build "tri-nodes" to enhance there skills, and each skill should appear in two different tri-nodes. For my character, kanna, I want to enhance 9 skills with 6 tri-nodes (2x9=3x6). After thinking a while for an optimal strategy, it seems to me that the problem isn't that easy. I henceforth abstracted it into an algorithm problem showing below. Please let me know if there is anything unclear in the problem description. Thanks.

A card is a tuple of three letters in [a,b,c,d,e,f,g,h,i], and the three letters within a card are different.
For example, (a,b,c) could be a card, but (a,a,c) can't be because there are two same elements.
We can take exactly 6 cards to acquire 3x6=18 letters, and we want each letter in [a..i] appears exactly twice. However, we cannot take two cards that share the same first element. For example, the following set of cards satisfy the requirement. Each letter appeared exactly two times, and the first elements of these cards are unique.
[(a,b,c)(b,c,a)(d,e,f)(e,f,d)(g,h,i)(h,g,i)]
For a deck of $n$ cards ($n$ can be any integer), if there is a set of 6 cards that satisfies the above requirement, we say that this deck is complete, otherwise we say it's incomplete.
Given a deck of cards,

(a) determine if the deck is complete.

if the deck is complete, find an algorithm to

(b) find a solution.
(c) find all solutions.

If the given deck is incomplete, the requirement cannot be satisfied with the cards in the deck. In such case, a randomly generated new card will be added into the deck. The new card is generated randomly, meaning that [a..i] are equally probable at each position of the card tuple (but still the three positions will be different). After adding a random card, if the deck is still incomplete, another new random card will be added again. As such, we can expect that as the number of cards -> $\infty$, the deck will eventually become complete.

(d) Find an algorithm to take $m$ cards ($m<6$) from the deck, such that

$m$ is as large as possible;
each letter appears at most twice;
it is possible to take $(6-m)$ new cards that may be added in the future to satisfy the requirement. List these new cards.

For example, the following deck is incomplete:
(a,b,c)(d,a,e)(f,d,c)(b,e,f)(g,c,b)
We cannot take all of them because there will be more than 2 b's and c's.
we can have two solutions:

(a,b,c)(d,a,e)(f,d,c)(b,e,f)

with the appearance count [a:2,b:2,c:2,d:2,e:2,f:2,g:0,h:0,i:0]
and the needs count [g:2,h:2,i:2]

(d,a,e)(f,d,c)(b,e,f)(g,c,b)
with the appearance count [a:1,b:2,c:2,d:2,e:2,f:2,g:1,h:0,i:0]
and the needs count [a:1,g:1,h:2,i:2]

For the former solution, we want the new cards, for example, (g,h,i)(h,g,i). For the latter one, we want the new cards, for example, (h,a,i)(i,g,h). The possibilities of getting the needed cards might be different.

(e) There might be multiple solutions for (d). Find one that has the maximum possibility to satisfy the requirement with fewest new cards.

Problems (a),(b),(c) can be solved in polynomial time; simply enumerate all possible ways of choosing a subset of 6 cards and test each subset to see whether it satisfies all of the constraints.
If you care about a practical algorithm, I would suggest using a SAT solver.  It is easy to express this problem as an instance of SAT.  Use boolean variable $x_i$ to represent whether the $i$th card in the deck is chosen or not.  Then you can write boolean constraints that express each of your constraints.  I suggest using an off-the-shelf solver like Z3 to solve this instance of SAT; they will tell you whether any solution exists, and if so, give you one example.  If you want to find all solutions, look up algorithms to find all satisfying instances to SAT.
Problems (d),(e) are more challenging but can also be solved in the same way.  Iterate over $m=5,4,3,\dots$ and for each $m$ use a SAT solver to test whether there exists a solution for that value of $m$.  There are at most 120 different cards, so you can imagine having a deck and a sidebar of all the other cards not in the deck; let $x_i$ represent whether the $i$th card in the deck is chosen, and $y_i$ represent whether the $i$th card in the sidebar is chosen, and express as an instance of SAT.


Why is $L= \{ 0^n 1^n | n \geq 1 \}$ not regular language? I'm looking for intuition about when a language is regular and when it is not. For example, consider:

$$ L = \{ 0^n 1^n \mid n \geq 1 \} = \{ 01, 0011, 000111, \ldots \}$$

which is not a regular language. Intuitively it seems a very simple language, there doesn't seem to be anything complicated going on. What is the difference between $L$ and a regular language like:

$$L' = \{ w \mid w \text{ does not contain } 11 \} = \{0,10\}^*\cdot (1 \mid \varepsilon).$$

I know how to prove that $L$ is not regular, using the Pumping Lemma. Here I am looking for intuition about what makes a language regular.

To expand on Artem's comment, note that if we have an $m$ state automaton, at each point we can remember at most $\lg m$ bits of information about the part of input we have read so far. Based on this finite amount of information about the the previous bits of the input, you should be able to end up in the right accepting/rejecting state for all possible ways that the input can continue. If this amount of information is not sufficient to answer correctly then the language is not regular.

For this language we may need $m$ bits of information to be able to correctly answer where $m$ is an arbitrary large number (and therefore can be taken to be larger than $n$ which is fixed since the same atuomaton should work for all inputs).

One way to formally show this is pumping lemma. A more general way that is harder to use is to directly show that the number of equivalence classes of strings w.r.t. the language is not finite (we say strings $x$ and $y$ belong to the same class and write $x\sim y$ if for all strings $w$, $xw \in L$ iff $yw \in L$) which is the same as saying the amount of information that the machine needs to remember is not finite (constant w.r.t. to inputs).


Turing machines without time steps? In "More Is Different," an article about reductionism in science, the author makes the following off hand remark near the end:

  I find that at least one further phenomenon seems to be identifiable and either universal or remarkably common, namely, ordering (regularity or periodicity) in the time dimension... [It] is noteworthy that all computing machines use temporal pulsing.

As far as Turing machines go, this is true since there is a fundamental "time step" during which a symbol is read, the state is changed, and the read/write head moved.  But this got me wondering: are there any non-Turing computing proposals without this fundamental time step?

There are various models of analog computation, which embody computations which neither involve discrete states nor times. One of the more studied models is what might be called "Shannon machines" (after Claude Shannon): the General Purpose Analog Computer (GPAC).

Shannon's original formulation of GPAC could not compute certain functions, including the Gamma function. However, a 2007 paper cited in that Wikipedia article provides a reasonable reinterpretation of GPAC which turns out to be more powerful, enough so that the authors claim that "the GPAC and computable analysis are actually equivalent from the computability point of view, at least in compact intervals."

Claude Shannon is well-known as a pioneer in digital computer design and particularly for his foundational work on information theory, but his genius and sense of whimsy led him to extraordinary achievements in other areas, and analog computation remained an interest throughout his life. One example is his mathematical analysis of juggling, including the construction of a prototype juggling robot. (See here for more information and a brief video including the robot.)


Determining the intersections of a line segment and grid Problem: Given a line segment on the cartesian plane, determine where and which order it intersects a regular grid.  This sounds simple, but is actually quite a tough problem.  It's related to, but distinct from, both Bresenham and supercover.
More specifically, consider:

A line segment with start $(x_1, y_1)$ and end $(x_2, y_2)$
A grid of cells, bounded by all lines $x = k$ and $y = k$ for all integer $k$
Each cell therefore has four boundaries, called North, South, East, and West

The example plot shows the segment from (0.6,0.4) to (-0.2, 2.2) crossing three boundaries.
For a given line segment, we wish to determine the cell boundaries it crosses:

For each boundary type, the number of crossing. {N:2 S:0 E:0 W:1} in the example.
The sequence of crossings. {N, W, N} in the example.
The grid position of each crossing, defined as $(x - floor(x), y - floor(y))$.  Approximately N: (0.35, 1), W: (0, 0.8), N: (0.8, 0) in the example.

I'll note that the problem as-is is not fully defined: line segments starting or ending on a boundary, coinciding with a boundary, and crossing a vertex all need definition.  We can accept any reasonable, consistent definition of these.
Solving #1 is easy:
number of east (west if neg) crossings = floor(x2) - floor(x1)
number of north (south if neg) crossings = floor (y2) - floor(y2)

Solving #2 and #3 is surprisingly hard.  I've come up with three approaches:

Direct.  The ideal would be to calculate this directly (that is, without iteration), similar to the formula for #1.  I have made no progress here.
Iterative.  Determine the next crossing (by trying both directions and determining which is crossed first).  Determine how far along the segment that is.  Repeat until done.  This works, though it lacks elegance or speed.  The other issue is that chopping the segment repeatedly, if not done carefully, can cause inconsistency with floating point calculations leading to missed or double crossings.
Mixed.  Use the calculation above to determine the total number of crossings of each type.  For each, one $(x,y)$ coordinate is an obvious integer, and the other can be solved using simple algebra, as can the length of the segment to that point.  Sort by segment length.

#3 is the best approach so far.  Is it possible to do better?

I suggest using a simple iterative method.
Let's first find the places where it crosses a vertical grid lines.  These are places where the line goes through a point $(x,y)$ where $x$ is an integer.  The points $(x,y)$ on the line can be written in the form
$$(x,y) = (x_0,y_0) + t (x_1-x_0,y_1-y_0),$$
where $(x_0,y_0),(x_1,y_1)$ are the two endpoints of the line and $t \in [0,1]$ is a free variable.  Now this point crosses a vertical grid line if $x$ is an integer, i.e., if $x_0 + t(x_1-x_0)$ is an integer.  This has solutions of the form $t = (i - x_0)/(x_1-x_0)$, where $i$ is an integer with $x_0 \le i \le x_1$.
Therefore, to find all places where the line crosses a vertical grid line, you can iterative over $i$ in the range $\lceil x_0 \rceil,\dots,\lfloor x_1 \rfloor$, and for each such $i$, compute $t = (i - x_0)/(x_1-x_0)$ and then compute the point $(x,y) = (x_0,y_0) + t (x_1-x_0,y_1-y_0)$.  This enumerates all such points on the line.
You can repeat the same for places where the line crosses a horizontal grid line, i.e., where $y$ is an integer.  You can then merge these two sequences, sorting them by increasing value of $t$ (note that no sort operation is needed as the list of horizontal crossings and the list of vertical crossings are both already sorted; you just need to merge these two sorted lists).
The running time is linear in the number of such points.  This is asymptotically optimal; obviously any algorithm to output all such points must take at least $O(1)$ time per point, so needs to take at least linear time.
This does not have problems with accumulation of floating point errors, as far as I can see.  I don't see how this would cause missed or double crossings.  I find it elegant, though of course that is a matter of personal taste.


Formal definition of a language accepted by PDA I am a bit confused on how to give a formal definition of the language accepted by A?

I can describe it by "The language of all strings starting with n-many a's or n-many c's followed by n-many b's" and I have tried to give a formal definition by:

L(A) = {a^n c^n b^n | n ∈ N}

Is that the correct way to define it?

I would say it's $L(A)=\{a^n c^m b^{2n}| n,m \in \mathbb{N}, m \geq 2\}$

For every a push 2 zeros on the stack, so it's for now just called a^n.
The number of c's is m, because it is not related to the number of a's. You can accept any number of c's (larger than 2) no matter how many a's were there.
The number of b's is twice the number of a's because you accept for every 0 on the stack 1 b, but wrote twice 0 for every a on the stack.

In fact the language $L(A)=\{a^n c^n b^n| n \in \mathbb{N}\}$ can't be accepted by any PDA, but only a linear bounded automate(LBA) or a Turingmachine (or other similar models) The reasoning is that if you count the number of a's and want to have the same number of c's and b's later(not mixed) your stack will be empty after you sucessfully counted all the c's and the PDA will have forgotten the number to check whether the b's appear in this number.


"P may collapse" vs. Time hierarchy theorem https://en.wikipedia.org/wiki/P_versus_NP_problem states:

  If graph isomorphism is NP-complete, the polynomial time hierarchy
  collapses to its second level.

They further state that this may be unlikely, but at least it's a possibility. However, https://en.wikipedia.org/wiki/Time_hierarchy_theorem states:

  The theorem also guarantees that there are problems in P requiring arbitrarily large exponents to solve; in other words, P does not collapse to DTIME($n^k$) for any fixed k. For example, there are problems solvable in $n^{5000}$ time but not $n^{4999}$ time.

Why don't the above two quotes contradict each other?

The polynomial hierarchy is not $\mathsf{DTIME}(n^k)$ for various $k$, but rather a polynomial time version of the arithmetical hierarchy.


Probability distribution of runs given k bits set in an n-bit circular buffer Imagine you have a circular buffer holding n bits. You (uniformly) randomly set k of those n bits. (This is without replacement, so you are left with a buffer of n bits of which kbits are set.)

Now you randomly select a location in the buffer. What is the probability distribution of the run of set bits starting at that location? And what is the mean length of said run?

It's trivial that P(k,n,0) = 1 - k/n (that is, the first bit will be set with a probability of k/n, so there's a 1 - k/n chance that it will be unset.).

I think this has something to do with the hyper-geometric distribution, but I am not sure.

Note first that there is no need to randomly select a location in the buffer – we can fix one as we please. From that location, the probability that a run will be at least $t$ long is the probability that the $k$-set includes the first $t$ locations, which is
$$
\Pr[R \geq t] = \frac{\binom{n-t}{k-t}}{\binom{n}{k}}.
$$
Similarly, the probability that a run will be exactly $t$ long is the probability that the $k$-set includes the first $t$ locations but not the one after it, which is
$$
\Pr[R = t] = \frac{\binom{n-t-1}{k-t}}{\binom{n}{k}}.
$$

The expectation of $R$ is
$$
\mathbb{E}[R] = \sum_{t \geq 1} \Pr[R \geq t] = \frac{\sum_{t \geq 1} \binom{n-t}{n-k}}{\binom{n}{k}} = \frac{\binom{n}{n-k+1}}{\binom{n}{k}} = \frac{k}{n-k+1},
$$
using the formula $\sum_{x=r}^m \binom{x}{r} = \binom{m+1}{r+1}$.


Deciding the class of certain languages I am preparing for my exam in Formal languages and Automata theory and I'm looking at some old exam questions right now. I need help with the following question:

  For each of the following languages answer whether it is regular, context-free but not regular, or not context-free. A brief, informal explanation is sufficient.

  $$
  L_3 = \left\{ w \in \{a,b,c,d\}^* \Bigg| \begin{array}{l}
      \text{\(w\) does not have a substring \(aba\),} \\
      \text{each \(a\) in \(w\) is immediately followed by \(b\),} \\
      \text{and \(\#c(w)\) is odd}
    \end{array} \right\}
$$
  $$ \begin{align}
  L_4 &= \{ a^ib^jc^ka^ib^l \mid j \gt l \text{ and } i,l,k \gt 0 \} \\
  L_5 & \text{ is the image of \(L_4\) under the homomorphism }
  h:\{a,b,c,d\}^* \to \{0,1,2\}^* \\ & \text{ such that }
  h(a) = h(b) = 10 \text{ and } h(c) = 210 \text{ and } h(d) = \epsilon \\
  L_6 & \text{ is the image of \(L_4\) under the homomorphism }
  h:\{a,b,c,d\}^* \to \{0,1,2\}^* \\ & \text{ such that }
  h(a) = h(b) = 210 \text{ and } h(c) = h(d) = \epsilon \\
\end{align} $$

Here is my attempt:

$L_3$ is regular. It's the intersection between 3 regular languages. Regular languages are closed under intersection, so the resulting language is regular. The language where $w$ does not have a substring $aba$ is just the complement of the language $aba$, regular languages are closed under complement, so the resulting language is regular. The language with an odd number of $c$ is regular. Hence the resulting language when taking the intersection between these languages is regular.

$L_4$ is not context-free. When reading the first $a$'s we will push the $a$'s onto the stack. Then we will read the first $b$'s and push them onto the stack. Then we will read the $c$'s. When we now read a second group of $a$'s, we will not be able to compare the number with the first $a$'s, because $b$'s are on the top of the stack and if we pop them then we will not be able to compare the number $b$'s in the beginning and the end. Hence, $L_4$ is not context-free.

$L_5$ is context-free but not regular. The language in question looks like this:
$$ 10^{i+j} 210^k10^{i+l} \text{ where } j \gt l \text{ and } i,l, k \gt 0 $$
A grammar can be constructed which generates at least one more $10$ in the beginning of the string than $10$ after $210$.

$L_6$ is regular because it's given by the regular expression:
$$ 210^{2i + j + l} \text{ where } 2i+j+l \text{ is any number } \gt 0$$

Is this correct? Note that informal explanations is sufficient in the answer and that no grammars has to be given.

The answers are correct, but when proving that a language is not regular, or not context-free, it is not enough to show that one attempt does not work. You have to use tools like pumping lemma. For context-free languages, there is a version of pumping lemma which should work here: http://en.wikipedia.org/wiki/Pumping_lemma_for_context-free_languages

Also it's a detail, but in your last argument, $2i+j+l$ is not any number $>0$, it is at least $5$, since $j>l$ and $i,l,k>0$. So your language is $\{(210)^n : n\geq 5\}$, which is indeed regular.


When should I learn artificial intelligence? Straight to the point: I would really like to learn AI.

But I want some advice from experienced CS guys as to when I should jump into Artificial Intelligence.

What prerequisites are needed in order for me to better grasp the AI concepts?

You will need some discrete mathematics. Graphs, trees, and so forth. These are the structures underlying AI.

You will need some programming skills, especially in languages such as Prolog and LISP.
A lot of AI systems are programmed in these languages.

You will need some logic. Propositional and predicate calculus. Their syntax and semantics. Perhaps some modal logic. This will form the basis for learning about knowledge representation, which is at the basis of AI.

During the first two years of a regular computer science degree you usually obtain enough background to start studying AI .

But there is no limit to how complex AI can be. To get deeper into it, you'll need statistics, calculus, matrix algebra, and probably much more. Statistical learning theory (or more simply machine learning) depends on these areas.

My advice. Buy a book on Artificial Intelligence to read in your own time.
A good one is Artificial Intelligence: A Modern Approach by
Stuart Russell and Peter Norvig. Whenever you don't understand something, try to work out what background knowledge you are lacking. Then fill those gaps.


Forest characterization Prove that each property below characterizes forests...

a. every induced subgraph has a vertex of degree at most one.

When proving a characterization, do we have to prove both directions, like an if and only if, or does it suffice to prove only one direction?

"Characterizes" means you must prove "if and only if".


Minimum distance between start and end by going through must visit points in a maze So, suppose i have a maze, which has a start point and an end point, marked with Orange and red respectively and my goal is to find the minimum distance between them. The blocked path is represented by black colour and the open path is represented by white colour . However there are two modification done in this.

There are some cells which are must visit, marked in grey colour.
Any cell can be visited any number of times(even the start, finish and must visit points)

for ex-
  █=Black, ░=white, G=grey, R=Red, O=orange

         ██████                 █████
         ██G███                 █░GG█
MAZE1 => █O░GR█     MAZE2  =>   █O███
         ██G███                 █░░R█
         ██████                 █████

Here in this case ans will be

MAZE1 => M[2][1] => [2][2] => [1][2] => [2][2] => [3][2] => [2][2] => [2][3] => [2][4]  = 7
MAZE2 => M[1][1] => [1][2] => [2][2] => [3][2] => [3][3] => [3][2] => [2][2]            = 6

As you can see, the nodes appear multiple times

First i thought of using recursion technique (backtracking) but couldn't come to an algorithm. and

So i thought of using this way.

I will keep track of all the coordinates of  must visit points, start and end points
Find the distance between each node(like in selection sort we compare each and every term, just like that, we get the minimum distance between each node (using BFS))
Then apply some minimum distance algorithm. I thought of TSP but it says nodes must be visited exactly once.Here it can be multiple times. I found chinese postman problem, but don't know if it can be applied here. Floyd warshall algorithm is there but it doesn't include every point

How should i proceed, any idea?

Most real mazes are trees and there is a polynomial time algorithm for this problem on trees. For ease of description, orient all edges of the tree to point away from the start vertex. Now, for each vertex, delete any child if the subtree rooted at that child contains no vertices that must be visited (i.e., contains no grey or red vertices). The result is a tree where every leaf is grey or red (there may be grey and red vertices in the interior of the tree, too). Now perform a depth-first traversal of the tree, investigating the children of each node in arbitrary order, except that, if one of the children is on the path from the start to the red (end) node, that child is investigated last. If the red node was a leaf, you are done; if not, take the unique path from the leaf you finished at to the red node. The total distance is twice the number of edges in the reduced tree, minus the number of edges on the shortest path from the start to the red vertex.

For general graphs, the problem is NP-hard. Consider the special case where the "maze" actually has no black squares. What we have is, essentially, a so-called rectlinear TSP, where the start, end and grey squares are the "cities". Rectilinear TSP is metric TSP using the Manhattan distance as the metric. The input is a set of points with 2D integer co-ordinates. Observe that metric TSP doesn't care whether you revisit cities or not because it obeys the triangle inequality: if the shortest route from A to B is via C, and the salesman has already visited C, he'll just drive straight past; in the maze world, we don't care whether he stops or not, since he's allowed to stop in a city as many times as he wants. Rectilinear TSP is NP-hard: see Garey, Graham and Johnson, Some NP-Complete Problems (Proc. 8th STOC, pp. 10–22, 1976; ACM DL).

To prove NP-hardness of the maze problem, we need to demonstrate a reduction from rectilinear TSP. This isn't quite trivial because the maze problem has specified and distinct start and end squares but I'm reducing from rectilinear TSP, in which the salesman starts at any city he chooses and returns to that city at the end. But observe that it doesn't matter what the start city is, since the tours ABCDA and CDABC have exactly the same length: forcing the tour to start at a particular city doesn't actually change the answer. So, if I'm allowed to cheat once more and put the red and orange squares in the same place, I'll do that. But you probably mean that squares have a unique colour, so here's the full reduction:

  Take the northern-most of the cities and make it be the start square (if there are multiple cities equally far north, choose any one of them. Make every other city a grey square. Place the end square one square to the north of the start square and colour black the squares north, east and west of the end square. Make every other square white.

Because of the black walls, any route from the start square to the end square must revisit the start square immediately before going to the end. The end square and its black walls are outside the convex hull of the original cities, so no optimal tour of the original cities would have gone through those squares. Therefore, a shortest route from the start square to the end square consists of a solution to the rectilinear TSP problem (a shortest tour from the start city, through all the other cities and back to the start city), followed by the one-square move from the start square to the end square. This completes the reduction.


What types are propositions? In the propositions-as-types paradigm, we are still faced with the question : what types are propositions ? I currently know 3 different answers :

Coq's sort Prop and its typing rule that asserts it is closed under products indexed by abtirary types
$$\frac{A : \mathsf{Type}_i \qquad x : A \vdash B(x) : \mathsf{Prop}}
     {\prod_{x : A} B(x) : \mathsf{Prop}}$$
HoTT's HProp, which are types where all elements are equal, together with the HProp truncation fun A:Type => ∥A∥, which assigns an HProp to each type A.
Coq's new SProp. As far as I understand, SProp is almost the same as HProp, but instead of explicit rewrites, the type checker will be happy to implicitely convert any element of an SProp into another. So I won't discuss SProp anymore here.

I see some common points between Prop and HProp, the main one being that Coq is compatible with the axiom of proof irrelevance, which asserts that all Props are HProps. Also there is the similar guarded match. Coq accepts to destruct a proof of a Prop only when it is proving a Prop. Likewise, the recursion principle of the HProp truncation accepts to lift ∥A∥ -> B into A -> B, only when B is an HProp. Another common point is seen via Coq's extraction mechanism : all proofs of Props will be discarded, because they map to singleton types.

However I don't clearly see how either of these definitions captures the concept of a proposition. A HProp makes some sense to me, because uniqueness allows to interpret inhabitants as mere proofs that the HProp is true. But then one can argue that a proposition does have different proofs, some being simpler than others for example. Or some using more or less axioms than others (constructive proofs versus classical proofs for instance). Concerning Coq's Prop, I understand that it is impredicative, but I don't think it explains enough. And why didn't Coq take proof irrelevance as a hard typing rule (where 2 proofs are the same Prop would be judgementally equal, rather than propositionally equal) ? I think it would be compatible with HoTT, if we redefine eq in sort Type rather than Prop.

Part of the answer might come from the function extensionality axiom. If it is not there, then it is very hard to prove that a type is a HProp. So Coq's Prop might be a way to handle propositions without assuming funext. For instance, the closure of HProp by the forall quantifier needs funext, so Prop's typing rule might be seen as an instance of funext.

Are there other definitions of propositional types ?

The original conception of propositions-as-types did not distinguish propositions and types at all: all types are propositions. Under this view, we may indeed speak of different proofs of a proposition.

One way to understand the differences between different conceptions of propositions-as-types is to view them as capturing different notions of provability and truth:

If we say that Prop = Type then the elements of a proposition are the proofs, so we are capturing proof constructions. We may analyze proofs, and for instance distinguish them according to their size, the assumptions they use, etc.
If we say that Prop = HProp then the elements of a proposition witness existence of proofs (but are not specific proofs), so we are capturing provabillity. We can still discern the reason for a proposition being true, because we can analyze the proof as lons as further constructions do not depend on the choice of proof.
If we use the strict SProp which makes all proofs judgmentally equal (or simply erases proof altogether), then inside type theory we can never "discern" the reasons for a proposition being true, so this is more like truth, i.e., an external reason for something being the case. We do have soundness in the sense that type theory can express semantic entailment, e.g., if $p$ and $q$ are true then so is $p \land q$.

Coqs Prop is conservative in the sense that it makes no commitment as to what Prop is supposed to be. Coq is compatible with the view that Prop is an (impredicative) Type, as well as that it is something like HProp, or even just bool. This is a design decision.


Find minimum number of points which intersect overlapping arcs Say I have a circle of a fixed radius, with overlapping arc intervals along its edge. I want to return a minimum set of Points which intersects all arcs in $n^2$ time.
I'm having some trouble proving that my algorithm works. I'm getting caught up with arc intervals that span $0,2\pi$.
For example I have the intervals (in degrees): [45,90],[315,50],[300,25],[310,350] - when I do a sweep I find that the first degree with the least intersects (2) - is 25 - committing to this yields needing 3 points {25,45,310}, whereas the optimal solution is 2 points {~45,~350}. I'm thinking I can maybe just exclude that angle of the least intersects - but I'm not sure how to prove I won't run into a similar problem with a different set of arcs?
So far I have:
# place Intervals in a minHeap based on "starting" radian/degree O(n)
# i = sweep intervals to find first radian/degree with least intersects O(n)
p = float(+inf)
P = {}
while minHeap is not None:
  I = minHeap.deleteMin()
  if I.start>I.end:
    I.end += 360   # trying to normalize
  end if

  if I.start < i:
    minHeap.insert(new interval with I.start + 360 and I.end +360) #too early to evaluate
  else:
    if I.last <= p:
      p = I.last #looking for the counterclockwise radian/degree which covers most arcs
    end if

    if I.first > p:
      #found an interval out of reach - updating trackers
      p = p % 360 #normalizing
      P[p] = true #will eventually return P
      p = I.last  #updating to the new most counterclockwise rad/degree
    end if
  end if
end while
return P

A little abstraction would help both reasoning about and solving the problem efficiently, I think.
For every point $x$ on the circle, there is some set $S_x$ of pairwise overlapping arcs that intersect this point. Now, if there is some other point $y$ such that $S_x \subseteq S_y$, you can always use $y$ instead of $x$ in a solution to your problem. We can therefore focus on a set of representative points $x_1,\ldots,x_m$ such that each set $S_{x_1},\ldots,S_{x_m}$ is maximal. There are at most $n$ such points (the proof of which I will leave as an excercise) and you should be well able to find this set in $O(n^2)$ time.
Now, if the arcs don't wrap all around the circle, i.e. there is some point on the circle that doesn't touch any arcs, then you can look at the arcs as intervals on a straight line. Given the right infrastructure (you should sort the arcs both by starting and ending angle, again easily doable in $O(n^2)$ time) you can solve this problem greedily in $O(n)$ time (cf. this post).
Finally, to solve the problem, you do as follows: For each $1\leq i\leq m$, you ask the following question: "If i use $x_i$, how many other points must I use in order to cover the arcs that are not in $S_{x_i}$?" These arcs naturally do not wrap around the circle. You can therefore calculate this in linear time, and return the minimum set of points over all tries. Since $m\leq n$, this will only take $n^2$ time in total.


Minimum number of sets of unreachable vertices for directed acyclic graph (DAG) I have a DAG with vertices $V$ and edges $E$.  If $v,w \in V$ are vertices such that $v$ is not reachable from $w$ and $w$ is not reachable from $v$, I will say that $\langle v,w \rangle$ is an unreachable pair.

I want to implement an efficient algorithm which takes this DAG as input, and produces as output a list of sets of pvertices such that:

For each unreachable pair of vertices $\langle v,w \rangle$, at least one of the output sets contains both $v$ and $w$,
Every pair of vertices $v,w$ that are contained in the same output set must be an unreachable pair, and
The number of output sets must be the minimum possible.

Is there a polynomial-time algorithm for this problem?

As an example, we have the following DAG with topologically ordered vertices
A,B,C,D,E:

A is connected to [D, E]
B is connected to [D, E]
C is connected to [E]
D is connected to []
E is connected to []

which means that we have the following unreachable vertex pairs:

1. <A, B>
2. <A, C>
3. <B, C>
4. <C, D>
5. <D, E>

The expected output is composed of the following three vertex sets:

1. {A, B, C}
2. {C, D}
3. {D, E}

The output was not {A,B} {A,C} {B,C} {C,D} {D,E} because the minimum number of  possible output sets is 3 instead of 5 as given above. Otherwise it would satisfy the first two conditions, but not the third condition.

As another example, consider the same DAG vertex set V but where the edge set E is empty. Since all vertex pairs would be unreachable, the expected output is the vertex set V itself.

The problem is fixed-parameter tractable, where the parameter is the number of output sets.

Define an undirected graph $G'$ with an edge $(v,w)$ for each unreachable pair of vertices in the original graph.  Now you want to find a minimal edge clique cover of $G'$.  The minimal edge clique cover problem is fixed-parameter tractable, where the parameter is the number of cliques.

I don't know if there is a polynomial-time algorithm.  The minimal edge clique cover problem is NP-complete for general graphs.  I don't know if $G'$ has any special properties that makes the minimal edge clique cover problem easy on it.  (It's not necessarily chordal, unfortunately.)


Super-strongly connected components? I face a problem that is related to (strongly) connected components. Let $G=(V,E)$ be an undirected graph.

I want to find subgraphs $G_1,G_2, \dots,G_n$ of $G$ such that

they do not overlap (i.e. don't share any nodes)
each two nodes in a subgraph are connected by an edge, i.e. $\forall i \forall n,m\in V_i$ then $\{m,n\}\in E_i$ where $G_i=(V_i,E_i)$.

My question is: How to solve this problem? Is there any specific name of this problem?

Edit: The graph I am dealing with is very sparse. Coloring based approximations may not work as the complement graph would be huge (not able to store it in memory).

This is called the Minimal Clique Cover Problem, and is NP-hard: as a matter of fact, the decision version ("can I do it with only $k$ subgraphs?") is one of Karp's original 21 Problems, the ones that first defined NP-completeness.

Since it's linked to graph coloring, you can't even get a good approximation in polynomial time, unfortunately: everything about this problem is hard.

For further reading, your "super-strongly connected components" are generally called cliques, and a clique cover is a way to "cover" the entire graph with non-overlapping cliques. A minimal clique cover uses the smallest possible number of cliques to do it.


The number of balanced trees with N node and L leaves An algorithm is requested to calculate all balanced binary trees which can be built with $N$ nodes, having exactly $L$ leaves. A balanced tree is a binary tree in which the difference between the heights of the left and right subtrees is at most 1, and the subtrees are themselves balanced.

I tried to use dynamic programming to calculate the number for the subtrees created from any subsequence of $1..N$. However, without building each possible subtree and calculating its height and differentiating the height of the subtrees from each other, it can't distinguish the balanced subtrees. Moreover, the sum of their leaves must be exactly $L$. There are many constraints, and I couldn't come up an algorithm, either a working nor an optimum one.

Could you please guide me?

Source: Assignment of Advanced Algorithms, Fall 2018, Tehran University

Suppose $BTC[H][N][L]$ shows the number of balanced trees with the height $H$, with $N$ nodes and $L$ leaves. Using the following formula, a dynamic programming algorithm can be developed for the problem:

The recursive part:
$\begin{align*}
BTC[H][N][L] = \sum_{h=0}^H\sum_{n=0}^N\sum_{l=0}^L \qquad&(BTC[h-1][n][l]\times BTC[h-1][N-n][L-l])\\
 +&(BTC[h-1][n][l]\times BTC[h-2][N-n][L-l])\\
 +&(BTC[h-2][n][l]\times BTC[h-1][N-n][L-l])
\end{align*}$

The base cases:
$BTC[h][n][l]=\begin{cases}0 & \text{if $h>\log_2n$ or $l>\frac{n}{2}$ or $n=0$ or $l=0$}\\ 1 & \text{if $h=0$}\end{cases}$


Difference between a minimal DFA and a canonical DFA given a language L,a DFA M that recognize L is minimal if M is the DFA with the minimum number of states. In order for this to happen M does not have neither unreachable nor equivalent  states. The minimum DFA will be unique unless the names of states. Now my question is what is the difference between minimal and canonical DFA? They are the same thing?

Yes. The canonical DFA for a regular language $L$ is the automaton that is based on the equivalence classes of the relation defined by $L$, i.e., they cannot be "distinguished" in $L$ by extending them with the same suffix.

It is part of the Myhill-Nerode results that that yields a minimal DFA for $L$.


Is my problem NP-Hard? I have a grocery dotted list of pairs which are missing items that I need and I don't have any of them, so I am going to the supermarket.

Each pair in the dotted list is the name of the missing item that I need and a natural number which is the quantity/amount i.e. how many of this item I need.

I am in the supermarket now and I see an array of packages of items standing on shelf.

There are packages that don't contain items that I don't need and there are packages that contain items that I don't need.

I have enough money to buy all the packages, but if I will do this then I will get items that I don't need, so I don't want to do this.

Surely that I won't buy any package that contains an item that I don't need, but note that I don't want to have too many of any item that I need.

I can peek inside each package to see what items it contains and how many of that item it contains.

I cannot buy partial package, i.e. I cannot for each package decide which items from the package I buy and which I don't buy.

My only choice for each package is either buy the package and get all the items inside or don't buy the package and get nothing from the items that this package  contains.

I want to know if this is possible to buy the packages so I get all what I need exactly as written in my grocery dotted list without having superfluous items that I don't need.

I will bring my mobile phone to the supermarket and once I can peek inside the packages I will run the application that will solve my problem.

I am programmer and I can program this application for my mobile phone with no problem but I want to use a polynomial time algorithm that solves my problem, because I am not going to wait hours, days, months and years until my phone will return me the answer.

But to know if there is polynomial algorithm or not I need to know first if my problem is NP-Hard or NP-Intermediate that polynomial solution is unknown.

Indeed my problem is decision, because I need to decide which packages I buy and which I don't buy and if I have a solution I can verify it in polynomial time, so my problem is indeed in $\mathbb{NP}$, but I don't know if it is in $\mathbb{P}$.

Do you know?

EDIT:

Mathematically my problem is show either:

$A\subset\mathbb{MULTISETS} \land B\in\mathbb{MULTISETS}\vdash\exists C: C \subseteq A \land \displaystyle \biguplus_{D \in C}D=B$

OR

$A\subset\mathbb{MULTISETS} \land B\in\mathbb{MULTISETS}\vdash\nexists C: C\subseteq A \land \displaystyle \biguplus_{D \in C}D=B$

Your problem is NP-complete.

It is a multidimensional generalization of the subset sum problem.  The input to subset sum is a list of integers $a_1, \dots, a_n$ and a target $t$.  The question is whether there's some sublist of the integers whose total is $t$.  This corresponds to the case where your shopping list is just "$t$ apples" and each package on the shelf contains some number of apples.

Having multiple products for sale in the shop certainly can't make the problem any easier.  But it doesn't get any harder, either: it's still in NP because, as you've observed, if somebody tells you "buy this set of packages", you can easily check in polynomial time that this gives you exactly what you want.


prove that l={w ∈ {0, 1}*: n0(w) ≠ n1(w)} is a non regular language? I tried doing this, but kept failing to prove. I know how to prove that the language is nonregular when  n0(w) = n1(w). The following is the proof for n0(w) = n1(w) using pumping lemma:

Assume L is regular. Then, by the Pumping Lemma, there is a natural number m such
that any w ∈ L with |w| ≥ m can be factored as w = xyz with |xy| ≤ m and |y| > 0,
and xyi
z ∈ L, for i = 0, 1...
Pick w = 0^m 1^m.
Then, 0^m 1^m = xyz, where y = 0k, for k > 0.
By the Pumping Lemma, xz ∈ L.
But, n0(xz) does not equal n1(xz).
The assumption that L is regular thus is false.
Hence Proved

However, I don't know how to prove it for when number of 0 is not equal to number of 1.

There are two easy proofs that I will let you work out on your own. The first uses the fact that regular languages are closed under complement, the other uses the Myhill–Nerode criterion.

You can also prove that this language is not regular using the pumping lemma, but the proof is a bit tricky. Let $p$ be the pumping length, and consider the word $w = 0^p1^{p!+p} \in L$. The pumping lemma gives us some decomposition $w = xyz$ with $y = 0^i$ for $1 \leq i \leq p$. Then $xy^{1+p!/i}z = 0^{p!+p} 1^{p!+p} \notin L$.