How is the formal definition of NP-hard equivalent to this colloquial one? Wikipedia informally describes NP-hard problems as "at least as hard as the hardest problems in NP".

It then states the formal definition: "a problem H is NP-hard when every problem L in NP can be reduced in polynomial time to H".

It doesn't seem obvious to me that those two statements are equivalent. In particular, it's not obvious to me that any problem is always reducible to a "harder" problem.

Why is reducibility an adequate measure of difficulty? To me, the most natural measure of difficulty is worst-case asymptotic complexity. It seems at least plausible to me that there might exist two NP problems A and B which both have the same worst-case asymptotic complexity, and that this complexity is "the worst" possible in NP, but the problems are so different that having an algorithm to solve A is not at all useful for solving B, and so neither problem is reducible into the other.

I assume from the definition of NP-hard that this in fact isn't possible. Why not?

Why is reducibility an adequate measure of difficulty?

It's not; it provides a relative measure of difficulty, relative to the kind of reduction under consideration.

  To me, the most natural measure of difficulty is worst-case asymptotic complexity.

That's the idea, but for NP-complete problems in particular we do not know their (worst-case asymptotic time) complexity. By introducing a relative measure of hardness, we can say "A is at least as hard as B" without knowing how hard either of them really is.

  having an algorithm to solve A is not at all useful for solving B, and so neither problem is reducible into the other.

That's not the idea behind Karp reductions which we use to define NP-hardness. Read up on the definition.

  this complexity is "the worst" possible in NP

There is no such thing as a worst possible complexity; all polynomial complexities are allowed, and there are problems of arbitrary polynomial complexity. You find proofs for this fact in textbooks on the matter.

  It seems at least plausible to me that there might exist two NP problems A and B which both have the same worst-case asymptotic complexity, and that this complexity is "the worst" possible in NP, but the problems are so different that having an algorithm to solve A is not at all useful for solving B, and so neither problem is reducible into the other.

Keep in mind that complexity classes like P and NP are rough; they ignore polynomial factors. So say we have $\Theta(n^k)$ algorithms for NP-complete $A$ and $B$. We know that $A \leq_p B$ and vice versa, but all that tells us that we can use the algorithm for one to solve the other with polynomial overhead. The degree of this overhead is not specified, and may very well be in $\omega(n^k)$.

Bottom line, you have not yet understood/absorbed the basics and struggle with your faulty intuition contradicting statements you find. I recommend you check out our reference material which covers a wide array of basics and common misconceptions.

Keep in mind that the theory around P and NP defines a measure of hardness. There are certainly others, and some are more appropriate for making some decisions than others.


Converting a non-planar graph to planar Suppose that we have a non-planar graph $G$ which is undirected and connected. Our aim is to remove a set of edges and/or a set of vertices and convert make $G$ planar while keeping the connectedness.

Besides connectedness, $G$ is guaranteed to have enough connectivity so that removal of a reasonably small amount of vertices do not disconnect the graph and there are several paths between two specified vertices (removing one or two vertices do not let $G$ be a tree).

I have looked it up on the Internet and could not find any research. Maybe it is because I do not know the proper keywords.

Is there any research on this topic? If so, could you provide a reference?

These problems usually appear under the name "X edge deletion" and "X vertex deletion", where X is the graph class of interest, e.g., X could be "planar". There are also different variants where you allow for say edge addition and deletion (these are "editing problems"), or the operation could be edge contraction and so on.

In other words, you seem to be interested in both planar vertex deletion and planar edge deletion. For starters, you can see [1] and [2] (the problems seem FPT parameterized by the number of operations $k$).

[1] Marx, Dániel, and Ildikó Schlotter. "Obtaining a planar graph by vertex deletion." Algorithmica 62.3-4 (2012): 807-822. -- Non-paywalled version here.

[2] Golovach, Petr A., Pim van’t Hof, and Daniël Paulusma. "Obtaining planarity by contracting few edges." Theoretical Computer Science 476 (2013): 38-46.


Complexity of Integer Division My favourite algorithm textbook: The Algorithm Design Manual S. Skiena.pdf
had this interesting problem:

  1-28. [5] Write a function to perform integer division without using either the / or * operators. Find a fast way to do it.

What's the lower bound for asymptotic complexity of this problem?   `

P.S: I know repeated subtraction with a will work. It has asymptotic linear complexity with b (case where a = 1). However, repeated subtraction has exponential complexity with $n$ where $n$ is the number of bits needed to represent the number. Specifically it is $\Theta(2^n)$. So it is definitely not fast.

Wikipedia has a nice page about the complexity of mathematical operations, and there is also a dedicated page about division. Asymptotically, division has the same complexity as multiplication. The fastest known algorithm, due to Harvey and van der Hoeven, runs in time $O(n\log n)$. However, this algorithm isn't practical (it is not fast in practice, since the integers aren't large enough). Wikipedia lists no known lower bounds, though some people believe that the complexity should be $\Omega(n\log n)$, and there are some bounds in weak models. See for example Lower Bounds for Multiplication via Network Coding by Afshani, Freksen, Kamma, and Larsen.


Prove NLOGSPACE$\subset$PSPACE Condidering the proof, NLOGSPACE$\subset$PSPACE
I wrote following proof:
NLOGSPACE = NSPACE$(\log n)$ $\hspace{15pt} \because$ Definition of NLOGSPACE
NSPACE$(\log n)$ $\subseteq$ DSPACE$(\log^2 n)$ $\hspace{15pt} \because$ Theorem(1)
We let $m = \log n$, then,
DSPACE$(m^2)$ $\subset$PSPACE $\hspace{15pt} \because$ Definition(2)
Therefore, NLOGSPACE$\subset$PSPACE.
Theorem(1):
If $S$ is a space constructible function and $S(n) \ge \log n$, then NSPACE$(S(n)) \subseteq$ DSPACE$(S^2(n))$.
definition(2): PSPACE = DSPACE$(n)$$\cup$DSPACE$(n^2)$$\cup$DSPACE$(n^3)$$\cup$...$\cup$DSPACE$(n^k)$$\cup$...
But I am still not that sure if that "We let $m = \log n$" is ok, is this proving NLOGSPACE$\subset$PSPACE?

What would you think about a proof that says the following?

$NP \subset DTIME(2^n)$
let $m = \log n$, then $DTIME(2^n) = DTIME(m) \subset P$
Therefore $P = NP$

Here, you have indeed $DPSACE(log^2n)\subset PSPACE$ but the argument is weird.
Also please note that Savitch's theorem already proves that $NPSPACE \subset PSPACE$, and you have the result you want, since $NLOGSPACE \subset NPSPACE$.


Is there a strong argument to use shell sort over insertion sort on an array of 10 elements I'm trying to come up with an argument of why shell sort should be used over insertion sort for an array of 10 elements. And I'm wondering if there is one at all. I know that insertion sort is more efficient for the mostly sorted array, but in all other cases the shell sort should be faster. Or there will no significant performance difference for the array of 10 elements?

I have no knowledge about the data of an array.

It's an empirical question. First you need to come up with a probability distribution on arrays, for example the uniform distribution on all permutations of $1,\ldots,n$. For each $n$, you can measure the running time of both algorithms, and see which performs faster. The threshold 10 in reality depends on the implementation and the CPU, and is quoted only because it's a "nice" number, functioning as a rule of thumb.

So far I have assumed you're interested in minimizing the average case running time. If you're interested in the worst case running time, you'll have to run the algorithms on all permutations, which will quickly become infeasible.


NP HARD Problem Longest Path in Graph I got stuck with this problem since the whole day.

When we are finding the longest path in a graph we first do topological sorting and then check the path of adjacent vertices and keep upgrading selecting the maximum of the edge weight or the alternate path from the other vertex.

So, we are able to solve this problem because of topological sorting which can be done only for acyclic graphs. Thus this type of question can be solved only for acyclic graph.

Now, if I present another case. What if all the edge have the same weight and we don't look in the cycle of the graph. Is this solvable. Everytime I think about this I don't see any use of topological sorting if we can choose any source considering we have to choose the maximum number of nodes(longest path).

Is this also NP Hard or can we solve this?

If I understand your problem correctly, it is NP-hard (and so NP-complete) since you can reduce Hamiltonian Path to it. Given an undirected graph, make it into a directed graph by splitting each undirected edge into two directed edges going in both directions, and ask whether there is a path of length $n-1$.


Difference between virtual memory and job pool Both virtual memory and job pools store the processes temporarily on disk and bring them to memory at some later stage, so what is the actual difference in between them?

What I guess is that when a process is just created, it first goes to the job pool and then it is sent to the ready queue. Virtual memory is only used when available memory becomes smaller than the required memory for any process (please correct me if I am wrong).

If this is the case then doesn't it decrease performance? What is the need to store processes in job pool first? Why don't we send processes directly to memory?

Also somewhere it was written as “job contains the list of all the jobs in the system and jobs in the memory are a subset of the jobs in the job pool”. So what is meant by “all jobs in the system” here? Does it mean “all NEW jobs”?

The concept of “job pool” refers to a batch processing system, where jobs are queued to be executed when resources are available. The job pool contains both jobs that are currently executing and jobs that have been scheduled but are not yet being executed. Ancient computers (and some mainframes that are still in operation) worked this way. When a job is executing, it is fully present in memory.

Modern systems don't work that way. Computers that are big enough to run multiple tasks — even many embedded systems — have a memory management unit which translates virtual memory addresses to physical addresses, and the operating system uses that to move each page between memory and disk (this is called swapping or paging). This is an evolution from earlier multiprocessing systems: at first (before the MMU era) processes were swapped as a whole, but nowadays, if there isn't enough memory to fit all currently running processes, the operating system can swap out the parts of processes that aren't currently being used.

Systems designed for large non-interactive computations generally use job management even today. Swapping takes time; if the active processes require more memory than is available to run comfortably, this causes thrashing. To avoid this, job schedulers do use job pools, and arrange to start jobs, and possibly pause them, based on available resources. The system works on top of an operating system based on virtual memory, so once a job is paused it will naturally be swapped out as its pages in RAM are replaced by pages of active jobs.

(Note that job-based management is only marginally relevant to today's computing environment. I wouldn't set much store by a textbook that focuses on that in the 21st century. Virtual memory, on the other hand, is relevant to all but low-end embedded systems.)


Is it possible to encode logical expression and interpret it with SQL? Is it possible without any forms of eval or stored procedures to execute a query, which interprets logical expression, encoded in some way in a table (or two tables) of relational database?

For example, one table can contain a mapping for variable names into their truth values (V1), and another table or two (L1 and L2) - encode logical expressions, eg, in a conjunctive normal form.

Then some clever SQL query will interpret the logical expression from L1-L2, and apply values for variables from V1. (And of course same can also be done for multiple different expressions in the same query).

At first, this seems non-trivial to construct, but SQL has aggregating functions, so theoretically should be possible?

Using disjunctive normal form (DNF) representation. The following 3 tables arrangement seems to solve the problem (NB: using better names for tables, not same as in the question):

> select * from F;
+------+------+
| f1   | f2   |
+------+------+
|    1 |    1 |
|    1 |    2 |
+------+------+

> select * from C;
+------+------+
| c1   | c2   |
+------+------+
|    1 | A    |
|    1 | B    |
|    2 | C    |
+------+------+

> select * from V;
+------+------+
| v1   | v2   |
+------+------+
| A    |    0 |
| B    |    0 |
| C    |    1 |
+------+------+

Where F is a table for formulae, mapping from formula number to a table of conjuncts (C), which has a pointers into table of variables (V). The formula encoded here is (A AND B) OR C.

Doing conjunction is simply a matter of applying min() and disjunction is done by max().

Evaluating formula (number 1 in the example above) can be done by the following query:

> select max(A.v) as result from F, (select min(v2) as v, c1 from C, V
                                     where c2 = v1 group by c1) as A
  where c1 = f2 and f1 = 1;
+--------+
| result |
+--------+
|      1 |
+--------+

The above approach is a bit simplified - NOT is not possible to express, but it is easy to add it as an extra boolean column of table C and XORing it with the variable value.


Problems that are NP but polynomial on graphs of bounded treewidth I heard here that the Hamiltonian cycle problem is polynomial on graphs of bounded treewidth.

I am interested in examples/references to different problems which is essentially hard but having polynomial complexity on graphs of bounded treewidth.

There are probably thousands of examples; there's a short list at ISGCI; the Wikipedia article has plenty of links. Search for "bounded treewidth" and "parameterized complexity treewidth" for many, many more.

Essentially, the problems become easy on graphs of bounded treewidth because:

Although it's NP-complete to determine if a graph has treewidth at most $k$ [1], there is, for every $k$ a linear-time algorithm to compute a tree decomposition of any graph that does actually have treewidth $k$ [2].
Once you have the tree decomposition, you can solve many problems by dynamic programming.

A simple example, which doesn't even use dynamic programming, is the Clique problem. Any clique of a graph must be contained completely in some node of the tree decomposition. That means that a graph of treewidth $k$ can have no clique of size greater than $k+1$ and, to find a clique of size at most $k+1$, you just have to see if each node of the decomposition contains the clique you're looking for. That can be done in linear time if $k$ is a fixed constant, since you're just checking for cliques in $O(n)$ graphs that each have at most $k+1$ vertices.

For a more complicated example, suppose you want to know if a graph $G$ of treewidth 4 is 3-colourable. First, compute the tree decomposition. Each vertex of the tree corresponds to a subgraph of at most 5 vertices of $G$. For each leaf of the tree, compute by brute force all 3-colourings of the corresponding subgraphs. This is in polynomial time because there are at most $n$ leaves, each corresponds to a subgraph with at most 5 vertices and there are at most $3^5=243$ 3-colourings of any such subgraph. Now, for each vertex $v$ of the tree that's adjacent to a leaf, enumerate all the 3-colourings that are compatible with possible colourings of the leaves adjacent to $v$.  (That is, the 3-colourings of the subgraph corresponding to $v$ that can be extended to a 3-colouring of the graph corresponding to $v$ and all its adjacent leaves.) At this point, you can forget about the colourings of the leaves, since everything you need to know about them is now encoded in the distance-1 vertices. Now, iterate up the tree.  You can imagine doing something similar for Hamiltonian path, constructing a path through the whole tree by joining up paths in the subtrees; that's more complicated.

[1] Arnborg, Corneil, and Proskurowski, "Complexity of finding embeddings in a k-tree"., SIAM Journal on Matrix Analysis and Applications 8(2): 277–284, 1987. DOI.

[2] Bodlaender, "A linear time algorithm for finding tree-decompositions of small treewidth", SIAM Journal on Computing 25 (6): 1305–1317, 1996. DOI.


about the complexity of recursive sequence If i have a recursive sequence $a_1=4$ and $a_{n}=a_{n-1}^{2}-2$ in $\mathbb{Z}_{M_{n}}$ where $M_n=2^n-1$

how i can calculate the complexity time of this sequence ? if we put it in the loop for n-1 iteration .

pseudocode :

S=4;
i=2;

While($i<n$,

$S=S^2-2 (\mod M_n)$

If( S==0  then Break[]);

);

im not sure that overall complexity is $O(log^3(M_n))$

I calculated the first few values of your sequence:
$$
4,2,2,2,2,2,2,2,2,\ldots
$$
Indeed, $a_2 = 4^2-2 \bmod{2^2-1} = 14 \bmod{3} = 2$, and henceforward we have $a_{n-1}^2-2 = 2^2-2 = 2$ and so $a_n = 2$.


Is finding all primes less than n, doable in polynomial time? Bear in mind I'm almost a complete noob at complexity theory.

I was reading about how AKS Primality shows that numbers of size n can be shown to be prime or composite in polynomial time. Given that, does that imply finding all prime numbers less than a number n is also doable in polynomial time and thus the algorithm runs in FP. Additionally, does this imply that counting all primes less than n is not in #P?

Any ideas, or comments are appreciated Thanks!

No, it doesn't.  There are exponentially many primes less than $n$, so you can't enumerate them in polynomial time.


Give CFG and PDA for the words that start and end with the same symbol I need to give a PDA and CFG for a language that contains all binary strings that start and end with the same symbol. I've created the CFG with no problem, but I'm stuck with the PDA and don't quite know how to accomplish it.

The best I can figure is that I need to use non-determinism, but I don't quite know how to apply it in this circumstance.

Here's the CFG that I came up with:

\begin{align*}
A &\to 1B1 \mid 0B0 \mid \epsilon\\
B &\to 1B \mid 0B\mid \epsilon
\end{align*}

The PDA, insofar as I managed to come up with:

The notation here, just in case it's not universal: $a,b \to c$ means "When you see symbol $a$, pop symbol $b$ off the stack and push symbol $c$ onto the stack."

Any pointers on how to accomplish this?

A DFA is simple: From start state $A$ on 0 go to $B$, from $B$ with 0 go to $C$ (final), from $B$ with 1 stay in $B$, from $C$ with 0 stay in $C$, from $C$ with 1 go to $B$. Use a mirror for 1.

The PDA is just the DFA which essentially ignores the stack (rewrite the stack start symbol with itself on each move).

A CFG is just:
$$
\begin{align*}
S &\rightarrow 0 A 0 \mid 1 A 1 \mid 0 \mid 1 \\
A &\rightarrow 0 A \mid 1 A \mid \epsilon
\end{align*}
$$
A CFG more in line with the DFA is:
$$
\begin{align*}
S &\rightarrow 0 A \mid 1 B \mid 0 \mid 1 \\
A &\rightarrow 0 A \mid 1 A \mid 0 \\
B &\rightarrow 0 B \mid 1 B \mid 1
\end{align*}
$$


Seeking Alternate Proof Regarding Closure Of Recursively Enumerable Languages So I would like to show that the class of Recursively Enumerable languages are closed under the shrink operation. In other words, $\text{shrink}_a(L) = \{\text{shrink}_a(w)\mid w\in L\}$ and where $\text{shrink}_a(w)$ is the string formed from $w$ by replacing every maximal substring of two or more $a$'s by a single a. For example, $\text{shrink}_a(baaab) = bab$.

So I was browsing around for other examples to study, and I came across the following proof for the prefix operation: Proving that recursively enumerable languages are closed against taking prefixes (the proof given by the user Wu Yin). I thought that this was a very cool way of proving something like this, instead of just directly building an alternate TM. I'm curious to know, can anyone come up with a proof that is of a similar style and flavor to the one pointed above? I would be very curious to see a similar bijective proof regarding countable/uncountable sets!!

This has reminded me that there can be many ways to prove something, so I wanted to see what kind of flavor other people's proofs might have to this sample problem. I find that too often, students (and myself included) get caught up in a single procedure for finding solutions to a particular type of problem and neglect to see other ways of showing the same result.

The question actually is easy, provided you take the right definition. RE languages can be defined using a Turing Machine in two equvalent ways. As an acceptor which accepts words in the language and halts (and may halt or loop otherwise), or as an enumerator, which will write the elements of the language (probably in some weird order) onto the output tape (assuming there is a separate working tape).

Using the latter concept several closure operations of the type you mention are trivialities. If I want to shrink, I start my enumerator, and when it outputs a word of the language apply shrink.


How to construct a sequence of polynomial-time Turing machines I know that similar questions have been asked before but I still wasn't able to find answers to all my questions.

In many proofs in complexity theory we use an enumeration of some $T(n)$-time Turing machines. For simplicity, let's consider polynomial-time TM's. I want to know exactly how we construct such an enumeration.

I know that the following observations are important:

TM's correspond to the natural numbers: each binary sequence (natural number) encodes some Turing machine (if we have a sequence that does not encode a valid TM, we say that it is a trivial machine that halts and rejects on all inputs immediately)
Every TM's is represented by infinitely many strings/natural numbers, because we allow the encoding to end with any number of 0's (that do not matter for the encoding).

So if we want to obtain an enumeration of TM's that halt in polynomial time for some input $x \in \{0,1\}^n$, we can let each TM of our enumeration of all TM's (the natural numbers) run on input $x$, but then with a counter and an extra tape. If the TM hasn't halted in $n^i + i$ steps, with $i$ the length of the sequence that encodes the TM, we remove it from our enumeration. Because every TM is represented by an infinite number of strings, we now have any TM that runs in time $O(n^c)$ for some $c$.

Please tell me if this is not correct.

My confusion lies here: we need TM's that run in polynomial time for all inputs. Do we need to go over all possible inputs? There are only finitely many inputs of length $n$, but how are we sure that some TM does not use more than polynomial time for a larger input? Or is this some trivial consequece from the deterministic nature of Turing machines?

The simplest way is to use timed Turing machines. We enumerate pairs $\langle T_i, P_j \rangle$, where $T_i$ goes over all Turing machines, and $P_j$ goes over all polynomials. The machine corresponding to $\langle T_i, P_j \rangle$ simulates $T_i$ for $P_j(n)$ time steps, and then stops it (unless it already halted).

This is better than your solution, since you have to verify that the given Turing machine runs in time $P(n)$ for some given polynomial, a task which is uncomputable.


Problem with storing an existing triangulation in a DCEL I am trying to store an existing 2D triangulation (of which I have all of the vertices and edges) in a DCEL data structure.

Using the algorithm described in this answer, I was able to store a part of the triangulation, but not the "half-edge" representative for each triangle.

The algorithm is reported below

  Algorithm

  For each endpoint, create a vertex.
  For each input segment, create two half-edges, and assign their tail vertices and twins.
  For each endpoint, sort the half-edges whose tail vertex is that endpoint in clockwise order.
  For every pair of half-edges e1, e2 in clockwise order, assign e1->twin->next = e2 and e2->prev = e1->twin.
  Pick one of the half-edges and assign it as the representative for the endpoint. (Degenerate case: if there's only one half-edge e in the sorted list, set e->twin->next = e and e->prev = e->twin). The next pointers are a
  permutation on half-edges.
  For every cycle, allocate and assign a face structure.

Instruction 5 seems to be easier said than done. How can I ensure that every triangle will have a representative, and that a representative will be assigned only once for each triangle?

Furthermore, in point 6, which cycle is it referring to?

(So far, my implementation is similar to the one provided in the answer.)

The point of a half-edge data structure is that each half-edge is incident to exactly one face, and each face is represented by a list of half-edges given in order around the face. This is different from a normal planar map in which edges are incident to two faces. This can make certain coding tasks easier to deal with. So an (undirected) edge $\{u, v\}$ gets split into two half-edges $uv$ and $vu$ which are directed and twins of each other.

To list all half-edges (in order) incident to a face just requires following next pointers from each edge. Something like:

HalfEdge startEdge = ...some half-edge...
HalfEdge walk = startEdge;
do {
  //... do something here ...
  walk = walk.next;
} while (walk != startEdge);

In a DCEL the code above will walk around all edges in ccw order incident to the face startEdge.

Here is a concrete example:

Suppose we want to represent a triangulation with a single triangle $ABC$ where $A$, $B$, and $C$ are given in ccw order. We create six half edges: $AB$, $BC$, $CA$, $BA$, $CB$, and $AC$.

set the twins: $AB.twin$ = $BA$, $BA.twin = AB$. $AC.twin = CA$, $CA.twin = AC$, $BC.twin = CB$ $CB.twin = BC$.

set the next pointers: $AB.next = BC$, $BC.next = CA$, $CA.next = AB$ $AC.next = CB$ $CB.next = BA$, $BA.next = AC$.

and prev pointers $AB.prev = CA$, $BC.prev = AB$, $CA.prev = BC$, $BA.prev = CB$ $AC.prev = BA$ $CB.prev = AC$.

Now we already have implicitly faces: if we start with $AB$ and chase the next pointers around until we get back to $AB$, we get $AB$, $BC$, $CA$ which represents the interior of the triangle. If we start with $BA$ we get a different list: $BA$, $AC$, $CB$. This list represents the so-called "unbounded" face which is the exterior of our triangle. These are the "cycles" you mentioned. The first cycle is the (cyclic) list $AB\leftrightarrow BC\leftrightarrow CA$ and the second is $BA \leftrightarrow AC\leftrightarrow CB$.

For some applications this is all you need, but for others you may want a structure for storing extra information about the face. Keep in mind that the face is already represented by the double linked list $AB\leftrightarrow BC\leftrightarrow CA$. However we can make two data structures $f_0$ and $f_1$ for storing extra information for the unbounded face $f_0$ and the interior of the triangle $f_1$. We then set pointers again:

$AB.face = f_1$, $BC.face = f_1$, $CA.face = f_1$,
$BA.face = f_0$, $CB.face = f_0$, $AC.face = f_0$.

So now each half-edge points to the face incident to it. But we may also want to start with a face structure and then get a list of its incident half-edges. We already have the half-edges stored as lists, so we just need to point to any arbitrary start of the list, something like:

$f_0.halfEdgeList = BA$

$f_1.halfEdgeList = AB$

So now given a face $f$, we can loop over all its incident half-edges as before:

HalfEdge startEdge = f.halfEdgeList;
HalfEdge walk = startEdge;
do { // ... same as above
  walk = walk.next;
} while (walk != startEdge);

Finally, assuming you already have correctly set the previous, next, and twin pointers for your half-edges, then you could do something like this: when you create a half-edge, initialize its face pointer to 0. Then add all half-edges to a queue.

Note I'm writing pseudo-code, not C++ code here:

while (!queue.Empty()) {
  HalfEdge startWalk = queue.dequeue();
  if (startWalk.face = 0) {
    //This half-edge doesn't have a face yet
    Face f = create_new_face(); //Some function to create a new face and add it to any appropriate lists

    //Now walk around all edges from startWalk setting the face:
    HalfEdge current = startWalk;
    do {
      current.face = f;
      current = current.next;
    } while (current != startWalk);
  }
}

UPDATE: I looked at the link you provided and want to give a bit of terminology. Above I used the terms source and target to refer to the the start and end vertices of the half-edge. In the C++ code you linked to source is called tail, and target is the tail of the twin. So if you have a half edge called halfEdge:

vertex *source = halfEdge->tail;
vertex *target = halfEdge->twin->tail;


Confused about 3rd rule of CFG pumping lemma Let $L = \{\space ww \space | \space w \in \{0,1\}^*$} (need to prove that $L$ is not CFL)

Assuming $L$ is CFL we can use the PL and split $s=uvxyz$ and we choose $s = 0^p1^p0^p1^p$ where $p$ is the pumping length.

Using the 3$^{rd}$ rule, namely $|vxy| \le p$, can I say that $vxy$ can consist only of $0's$ and either pumping up(e.g. $uv^2xy^2z)$ or down ($uxz$) will throw us out of $L$ ?

Remember that the PL is stated for any partition $s=uvxyz$, so it is not enough to show that for one specific partition pumping $v$ and $y$ will exclude the resulting string from $L$. While it is true that $xyz$ can consist only of 0′s, it could also be the case that $xyz$ is of the form $0^i1^j$ for some $i, j < p$, for instance. You must show that pumping excludes the resulting string from $L$ in this (and all possible other) cases as well.


Trying to simplify a particular regular expression The question is as follows

$$(a^* (ba)^* )^* (b+\epsilon) = (a+b)^* (b+\epsilon)\,.$$

But I am unable to solve this regex expression. My answer is as follows:

\begin{alignat*}{2}
(a^* + (ba)^* )^* ( b+\epsilon)\qquad &\text{(using property} (a^* b^*)^* = (a^*+b^*)^* = (a+b)^*\text{)}\\
=(a+ ba)^* ( b+\epsilon)\qquad &\text{(using the above again)}
\end{alignat*}

This is my final answer but it is not as stated on the right side of the proof. So can you tell where am I doing wrong? Is my proof correct?

Assume the notations used in the question is the ones as described in the Wikipedia entry on regular expression for formal language theory. More specifically, it is the variant where "+" is used for alternation. (If you want to interpret the question in the notation used in common programming languages, please check the first version of this answer. Also note this updated answer renders the some comments below outdated. Thanks to the commenters!)

Suppose the task is to determine whether the following equality of regular expressions is correct,
$$(a^* (ba)^* )^* (b\text{+}\epsilon) = (a\text{+}b)^* (b\text{+}\epsilon)$$
then the answer is NO.

Why? Let us consider word $bb$. The right side is, in fact, the set of all words over the alphabet $\{a,b\}$. In particular, the right side contains $bb$. Can the left side contains $bb$? If the first $b$ in $bb$ comes from the part $(b\text{+}\epsilon)$, then it must be the end of the word, but there is another $b$ following the first $b$. If the first $b$ comes from the part $(ba)$, then it must be followed by an $a$, which is not the case.
Since the right side contains $bb$ but the left side does not, the equality cannot hold.

Now suppose the task is to simplify the left side of that incorrect equality,
$$(a^* (ba)^* )^* (b\text{+}\epsilon)$$
then a likely answer is, as given and proved by OP correctly,
$$(a\text{+}ba)^*(b+\epsilon)$$
The equality of these two regular expressions can also be understood easily by observing that the language is the set of all words over the alphabet $\{a,b\}$ that have no two consecutive $b$'s.


Knapsack problem with diminishing prices I wonder if the knapsack problem with diminishing prices is already studied?
The problem is similar to the regular knapsack problem, except the price of each item is a decreasing function of the total size of the already selected items.

Given $n$ items each with size $s_i$ and price $v_i(s)$, where $s$ is the total size of the already selected items, a size limit $S$ and a total price $V$, we want to find a sequence of items $\langle e_1,\cdots,e_k \rangle$ so that $\sum_{i=1}^k s_{e_i} \le S$ and $\sum_{i=1}^k v_{e_i}(\sum_{j=1}^{i-1}s_{e_j})\ge  V$.

The problem is obviously at least as hard as the regular Knapsack problem (i.e., weakly NP-hard). I wonder if the problem is any harder? Can the dynamic programming solution for the regular problem be used for this problem as well.

Consider the special case where $V_i\le v_i(s)< V_i+\epsilon$ such that $\epsilon$ is a very small positive constant, then your problem is equivalent to the regular knapsack problem where item $i$ has price/value $V_i$. So your problem is still NP-hard.


Dempster-Shafer theory initial belief values I am looking to implement D-S Theory in my (computer science) research, I'll be using it to determine the probability that a triggered sensor event is a true positive.

How would you calculate an initial belief value without having the ability to perform data mining on a dataset (a cold start)?

One solution that has been postulated is to use the manufactures performance statistics that the sensors are working correctly and then adjust this over time to take account for false positives. Although this will result is a very high initial belief rate for some sensors (95% belief).

If the 95% (initial) belief corresponds to the probability of a true positive according to the performance statistics, then that seems appropriate to me.


Intersection of two independent sets I am trying to make sure my intuition for the following question from an assignment is correct

Prove or disrove: if $G = (V, E)$ is a graph and $I_1$ and $I_2$ are independent sets in $G$, then $I_1 \cap I_2$ is
an independent set in $G$.

Answer: This statement is true. Consider arbitrary nodes $x, y \in I_1$ and $u, v \in I _2$. Since $I_1$ and $I_2$ are independent sets in $G$, there is no edge between $\{x, y\}$ and there is no edge between $\{ v, u \}$. Similarly, here is no edge between $\{x, u\}$ and $\{v, y\}$ because otherwise, $I_1$ and $I_2$ would have to have nodes that are adjacent two each other. We see that $I_1 \cap I_2 = \emptyset$ and therefore, the statement that $I_1 \cap I_2$ is
an independent set in $G$ is vacuously true.

Is this approah necessarily true for any two independent sets in a graph? I would appreciate any feedback

Your proof is unfortunately wrong. Consider what happens when $I_1 = I_2$, for example.

The essential reason behind the statement is the following more general fact:

  Any subset of an independent set is an independent set.

You can try proving this rigorously.


How to properly calculate the order of growth of an exponential algorithm? I'm reading SICP, and I'm a little bit confuse about this statement:

  Consider the problem of computing the exponential of a given number.
  We would like a procedure that takes as arguments a base b and a
  positive integer exponent n and computes b n . One way to do this is
  via the recursive definition

b n = b ⋅ b n − 1 ,
b 0 = 1

  which translates readily into the procedure

(define (expt b n)
  (if (= n 0)
      1
      (* b (expt b (- n 1)))))

  This is a linear recursive process, which requires Θ ( n ) steps and Θ
  ( n ) space.

I did a tree illustrating the process generated by the procedure:

(expt 2 2)
|
|
|
(expt 2 1)

Which makes the statement "This is a linear recursive process, which requires Θ ( n ) steps and Θ ( n ) space." true. But when I use a substitution model, it seems that requires 0 ( n ^ 2) steps and space:

(expt 2 2)
    (* 2 (expt 2 1))
    (* 2 2)
4

Thank you.

In this answer we assume the arithmetic model of computation, in which each arithmetic operation has cost 1.

The question has bad notation. Define function expt b n to compute b^n as:

expt b 0 = 1
expt b n = b ⋅ expt b (n − 1)

Computing expt b n requires computing n-1, computing expt b (n-1), and multiplying that expression by b. So the cost of expt b n is $2 +$ the cost of expt b (n-1). expt b 0 has cost 0.

Putting the above together, we see the cost of exp b n is $2 +$ the cost of exp b (n-1), $= 4 +$ the cost of exp b (n-2), $\ldots$, $= 2n +$ the cost of exp b 0, $= 2n$.


How To Show That B is Semi-Decidable Given A I am preparing for my Computational Theory final and ran into this exact problem :

B={ x | there exists a prefix of x that is in A}.

Show that B is semi-decidable.  In other words, you need to describe an algorithm M that on input a string x semi-decides if some prefix of x is in A (“semi-decides” means that it is OK if the algorithm loops for strings with no prefix in A). You will assume that you have an algorithm MA that semi-decides A.

Any help would be greatly appreciated!

A language is semi-decidable if there is a Turing machine that halts for all strings in the language, and doesn't halt for strings not in the language.

You are given that $A$ is semi-decidable. Therefore there is a Turing machine $M$ that halts on an input $x$ iff $x \in A$. Your goal is to construct another Turing machine $M'$ that halts on an input $x$ iff one of the prefixes of $x$ is in $A$. In other words, $M'$ should halt on $x$ iff $M$ halts on one of the prefixes of $x$.

You take it from here.


taking school courses efficiently I want design algorithm that allows a student to take important courses quickly up until graduation. no time, room number,  professors needed here. just my selected courses I know will allow me to graduate but how best to take them based on prerequisites. the student can decide how many courses to take a semester. And, you cant take a course's prerequisite and itself
eg cs101 cs102 201 but cs201 cant be taken in the first semester because i have to take its prerequisites first. Additionally prequisites can be  such that 101 and 102 or 101 and 104 are possible choices to take as prerequisites to a course 201. We could also have 101 or 106 and 102 or 105 ossible choices to take as prerequisites to a course 202.

any suggestions and how to go about it. Trees, graph adjacency list

I was thinking topological sort will give a valid ordering but i think i would ran into trouble when placing them in across semesters because topological sort order them linearly eg cs101 cs102 201 but cs201 cant be taken in the first semester because i have to take its prerequisites first. And what about if we have cs 103 cs104 cs202. cs103 and 104 have nothing to do with cs101 102

Form a directed graph of dependencies, with an edge $x\to y$ if course $x$ is a prerequisite for course $y$.  Use Kahn's algorithm to topologically sort the graph.  In particular, in each semester, you take all courses with indegree 0 (i.e., all courses where you've satisfied all prerequisites), then delete those courses from the graph.

This assumes there is no limit on the number of courses you can take in each semester.  Under that condition, it will let you complete your degree in the minimum number of semesters, in an order that respects the prerequisites.

If there is a limit on the number of courses you can take in a semester, the problem is more challenging.    This algorithm will find an order you can take your courses to get your degree, in an order that respects the prerequisites, but it is not necessarily the minimal number of semesters.  If you're in that situation, the best solution may depend on the number of courses you have and whether this is a practical problem you want to solve in real life or a theoretical problem where you care about worst-case asymptotic running time.


Couting Self dual functions The Dual of a Boolean function $F(x_1, x_2, ..., x_n)$, written as $F^D$ is the same expression as that of $F$ with $+$ and $.$ swapped. $F$ is said to be self dual if $$F=F^D$$

How can we count total number of self dual function with $n$ Boolean variables.

I know For $n$ variables total $2^n$ minterms or maxterms are possible and any boolean function can be expressed as combination of minterms or maxterms. But what else is required to count all self dual functions of $n$ variable.

Using de Morgan's laws, we get a more useful characterization of self-dual functions: those are functions satisfying $\lnot F(x_1,\ldots,x_n) = F(\lnot x_1,\ldots,\lnot x_n)$. Suppose that you knew the value of a self-dual function on all inputs in which $x_1$ is false. Can you recover the rest of $F$? Can you deduce the number of self-dual functions?


Explaining the relevance of asymptotic complexity of algorithms to practice of designing algorithms In algorithms and complexity we focus on the asymptotic complexity of algorithms, i.e. the amount of resources an algorithm uses as the size of the input goes to infinity.

In practice, what is needed is an algorithm that would work fast on a finite (although possibly very large) number of instances.

An algorithm which works well in practice on the finite number of instances that we are interested in doesn't need to have good asymptotic complexity (good performance on a finite number of instances doesn't imply anything regarding the asymptotic complexity). Similarly, an algorithm with good asymptotic complexity may not work well in practice on the finite number of instances that we are interested in (e.g. because of large constants).

Why do we use asymptotic complexity? How do these asymptotic analysis related to design of algorithms in practice?

The interesting question is: what is the alternative? The only other method I know is testing/benchmarking. We program the algorithms, let them run on (a representative sample of) the finite input set and compare the results. There are a couple of problems with that.

The results are not general in terms of machines. Run your benchmark on another computer and you get different results for sure, quantitatively, and maybe even qualitatively.
The results are not general in terms of programming languages. Different languages may cause very different results.
The results are not general in terms of implementation details. You literally compare programs, not algorithms; small changes in the implementation can cause huge differences in performance.
If the worst-case is rare, a random input sample may not contain a bad instance. That is fair if you are concerned with average case performance, but some environments require worst-case guarantees.
In practice, input sets change. Typically, inputs become larger over time. If you don't to repeat your benchmark every six months (yes, some data grow that fast), your results are worthless soon¹.

That said, ignoring all kinds of effects and constants in the analysis is typical, but can be called lazy (with respect to practice). It serves to compare algorithmic ideas more than to pinpoint the performance of a given (even pseudocode) implementation. It is well known to the community that this is coarse and that a closer look is often necessary; for example, Quicksort is less efficient than Insertion sort for (very) small inputs. To be fair, more precise analysis is usually hard².

Another, a posteriori justification for the formal, abstract viewpoint is that on this level, things are often clearer. Thus, decades of theoretic study have brought forth a host of algorithmic ideas and data structures which are of use in practice. The theoretically optimal algorithm is not always the one you want to use in practice -- there are other considerations but performance to make; think Fibonacci heaps -- and this label may not even be unique. It is hard for a typical programmer concerned with optimising arithmetic expressions would come up with a new idea on this level (not to say it does not happen); she can (and should) perform those optimisations on the assimilated idea, though.

There are formal, theoretic tools to close the gap to practice to some extent. Examples are

considering memory hierarchy (and other I/O),
analysing the average case (where appropriate),
analysing numbers of individual statements (instead of abstract cost measures) and
determining constant factors.

For example, Knuth is known for literally counting the numbers of different statements (for a given implementation in a given model), allowing for precise comparison of algorithms. That approach is impossible on an abstract level, and hard to do in more complex models (think Java). See [4] for a modern example.

There will always be a gap between theory and practice. We are currently working on a tool³ with the goal to combine the best of both worlds to make sound predictions for both algorithmic costs and runtime (on average), but so far we have not been able to do away with scenarios where one algorithm has higher costs but smaller runtime (on some machines) than an equivalent one (although we can detect that, and support finding the reason).

I recommend for practictioners to use theory to filter the space of algorithms before running benchmarks:

if ( input size forever bounded? ) {
  benchmark available implementations, choose best
  schedule new benchmarks for when machine changes
}
else {
  benchmark implementations of all asymptotically good algorithms
  choose the best
  schedule new benchmarks for when machine changes or inputs grow significantly
}

There can be crazy changes in absolute and relative performance once the number of cache misses increases, which typically happens when inputs grow but the machine stays the same.
As in, leading researchers in the field are not able to do it.
Find the tool here. An example use has been published in Engineering Java 7's Dual Pivot Quicksort Using MaLiJAn by S. Wild et al. (2012) [preprint]
Average Case Analysis of Java 7’s Dual Pivot Quicksort by S. Wild and M. Nebel (2012) -- [preprint]


What equivalence relation does this algorithm produce for an cyclic directed graph with labeled edges? I have a directed graph, which can be cyclic, where each node contains a value.

Nodes are not labeled, and different nodes can contain the same value.

The outgoing edges of a node are ordered, or labeled, (1, 2, 3, ... N), where N is the number of outgoing edges from the node.  (That is, it's a k-ary tree, if such a term can be used for a cyclic structure).

For each node in the graph, I produce a description of that node using the algorithm below.  Nodes are considered the "same" (equivalent) if they end up having the same description.

My motivation is that I'd like to produce a hash value from the description which will be the same for nodes where their value and the subgraph reachable from the node are (recursively) the same... however, if the descriptions are the same, the hash will be the same, so we don't need to worry about the hash.

I describe the data structure reachable from the node in this simple way:

Number the nodes in the subgraph reachable from the node, which I can do in a specific order (such as breadth-first, ignoring nodes already numbered) because the outgoing edges of a node are labeled.
Describe the subgraph reachable from the node by listing the nodes in the subgraph in order by the assigned number, and for each node in the list include in the hash the node's value and for each outgoing edge for the node (in label order), include the number assigned to the tail node of the edge.

For example, for a tree with nodes containing values A, B, C, and D:

I calculate describe A by assigning 0, 1, 2, 3 to the nodes containing A, B, C, D, and describe the values and edges this way:

0: A [1 2 3]
1: B []
2: C [0]
3: D []

Note in particular the outgoing edges from the node containing "A" are ordered (B, C, D), which makes this a unique description of the subgraph (which it wouldn't be if edges were unordered).

And similarly, to calculate the description for C:

0: C [1]
1: A [2 0 3]
2: B []
3: D []

As another example:

both nodes get the same description, because the algorithm produces the same description when run for each node.

Now, I'm assuming I haven't just solved the isomorphism problem for labeled graphs ;-)

Thus I'm guessing this algorithm describes some special case of graph isomorphism easier to solve than the general problem... or, it's not a solution to graph isomorphism because we're comparing nodes not graphs... or the algorithm is flawed doesn't produce the result I think it does! :-)

But I don't know enough computer science to be able to tell which nodes exactly would be characterized as the "same" or "different" by this algorithm.

It might be that different nodes (different in the usual way that you'd typically characterize the isomorphism of labeled graphs) are nonetheless "close enough" for my purposes that I don't mind that they get the same description.

And, if this simple algorithm does produce the result I want, I'd be eager to know if a more efficient algorithm exists.  But I can't ask that question without being able to specify what the simple algorithm does do.

Or, if I did understand what equivalence relation the algorithm produced, I might see that the algorithm was indeed flawed for my purposes.

Can you help?

For graph isomorphism, there are many heuristics that work in well in practice on most graphs.  You could try adapting any of them to your setting.

Here's one example of a simple heuristic that might often work well in practice (but with no guarantees on worst-case performance).  Let $f_0:V \to \mathbb{N}$ be the original values of the graph, so $f_0(v)$ is the value on vertex $v$.  Now construct a new set of values $f_1:V \to \mathbb{N}$ from $f_0$, as follows.  For each vertex $v$, apply your two-step algorithm to get a description for $f$ using breadth-first search---but crucially, stop the breadth-first search after depth 1.  Take the resulting description, hash it with any hash function, and use the resulting hash as $f_1(v)$.  You can do this again, and construct $f_2$ from $f_1$ (note that we are now ignoring the original values on the nodes, and using the values from $f_1$, when computing $f_2$), and then construct $f_3$ from $f_2$, and so on. Do this for a few steps, say 100 steps.  Each iteration can be done in $O(n)$ time, so the total running time will be $O(n)$ to compute all of the values $f_{100}$.

Now we have a nice property: if $f_i(v_1) \ne f_i(v_2)$, then $v_1$ is not equivalent to $v_2$.  Thus, if $f_{100}(v)$ is a singleton ($v$ is the only vertex with that value; i.e., there does not exist $w$ such that $f_{100}(v)=f_{100}(w)$), then there is no need to compute a full description for your $v$.  We can apply your full algorithm to compute a full description for only the vertices $v$ whose value appears multiple times in $f_{100}$.  Heuristically, for most graphs, there probably won't be many of them.  Thus, you won't have to compute the full description for many vertices, and you might avoid quadratic running time.

There are degenerate graphs where this might fall apart, and where the running time becomes quadratic, but for "most" graphs, hopefully this won't happen.


Check if I have a phone number I was recently in an interview and was asked what would be the smallest memory foot print and fastest system to check if a given phone number is in your data store given that all phone numbers will only be 7 digits.

I was told the answer is a byte but, I'm still not 100% sure how this would work and have not been able to find any information on it as of yet. If anyone knows the name of the structure/algorithm or would be willing to explain it I would be very appreciative.

Example data set:
6041234567
6041234568
6041234569
6041234570
6041234571

Output if checking for 6041234569:
True

Output if checking for 6041234580:
False

Edit: Please ask questions so I can try and make my question more clear.
Edit2: I only need to know if the phone number exists. I don't need to get it out.

Rewritten to match the new edited version of the question

What you want to think about is the size of the state for a DFA corresponding to a regular expression to match the number in question.

(I don't know how to draw DFAs here so work with my hand waving if you can.)

Since the thing you are looking for is a constant string the regular expression is just that string, say for example 6041234567. As a DFA this is a start node connected 10 intermediate nodes and a final accepting node. Then each of these nodes connect to the next node if the next character is the right one in the stream or back to the start if it is an incorrect input.  If you ever reach the final accepting node you have found the phone number and can do a happy dance.

That is all a setup for the fact that the only thing that matters state-wise is the current node you are matching on.  In my simple example here there are 12 nodes total, so you really only need 4 bits of data.

So you could have one upped the interviewer and said that in reality all you needed is a single nybble, instead of a whole byte.

A note about loop unrolling and state hiding

You can also achieve this by just writing a long list of checks for each individual digit as David commented above with what appears to be zero state.  But what that long list of checks is really doing is just moving the state into the program counter. You can do that with any fixed length matching problem, it is technically true but not really interesting.

One can also argue that I am moving state into the DFA, how is that represented? That is a fair cop, if one is being super pedantic, we would have to specify things like "A DFA is a 5-tuple consisting of yada yada yada" when we really need that precision.  Unless you were interviewing for a position in CS theory or compiler design no interviewer would be going there.

The reason that I am pretty certain that my answer is the right one in this case is that this question sounds like one that is asked all the time.  About half-way through a Theory of Computation course right after you learn about using DFAs to match REGEXPs you will look into the number of states and how to represent them.  This gives a nice intuition about the complexity and "size" of the various languages they match.  It also nicely segues into the way that removing determinism can greatly shrink the resulting transition graph and going the other way can result in an explosion in the number of states.


What's the time complexity of this algorithm? And Why? I am stuck by analyzing the time complexity of the following algorithm:

def fun (r, k, d, p):
    if d > p:
        return r
    if d = 0 and p = 0:
        r <- r + k
        return r
    if d > 0:
        fun (r, k + 1, d - 1, p)
    if p > 0:
        fun (r, k - 1, d, p - 1)

The root call will be fun (0, 0, n, n), and n is the size of the problem.

I guess that: The recurrence relation is $ T(n, n) = T(n-1, n) + T(n, n-1)$, which is equivalent to $T(2n) = 2T(2n-1) \iff T(m) = 2T(m - 1)$, and so $O(2^m) \iff O(4^n)$.

Is my analysis correct (I know it's not very complete and exact)? If it does have serious flaw, please point it out or show me a correct and complete proof on the time complexity of this algorithm.

The only two arguments relevant to asymptotic analysis are $d$ and $p$. These arguments (virtually) satisfy $d,p \geq 0$ and $d \leq p$ (we need to shuffle the logic in the function slightly to get this). At each point in the execution, you take the current pair $(d,p)$ and then recursively call the function with the pairs $(d-1,p),(d,p-1)$, avoiding pairs which invalidate the constraints stated above.

We can picture the resulting call tree as a path starting at $(0,0)$. Each time you decrease $p$, add a / step. Each time you decrease $d$, add a \ step. The condition $d \leq p$ guarantees that you never go below the X axis. Moreover, you have a "budget" of $n$ of each step. The total number of leaves in this call tree is exactly the Catalan number $\binom{2n}{n}/(n+1) = \Theta(4^n/n^{3/2})$, and this gives us a lower bound on the running time of the function.

To get an upper bound, note that on the way to each leaf we pass through $2n$ nodes, and this gives an upper bound $2n$ larger than the lower bound, i.e., $\Theta(4^n/\sqrt{n})$.

We have a lower bound of $\Omega(4^n/n^{3/2})$ and an upper bound on $O(4^n/\sqrt{n})$. What are the exact asymptotics? They grow like the total number of paths not crossing the X axis which have at most $n$ steps in each direction. Using Bertrand's ballot theorem we can get an exact expression for this:
$$
\sum_{0 \leq d \leq p \leq n} \frac{p-d+1}{p+1} \binom{p+d}{p}.
$$
It thus remains to estimate this sum asymptotically:
$$
\sum_{0 \leq d \leq p \leq n} \binom{p+d}{p} - \sum_{0 \leq d \leq p \leq n} \frac{d}{p+1} \binom{p+d}{d} = \\
\sum_{0 \leq d \leq p \leq n} \binom{p+d}{p} - \sum_{0 \leq d \leq p \leq n} \binom{p+d}{p+1} = \\
\sum_{p=0}^n \binom{2p+1}{p+1} - \sum_{p=0}^n \binom{2p+1}{p+2} = \\
\sum_{p=0}^n \frac{1}{p+1} \binom{2p+2}{p} =
\Theta\left(\sum_{p=0}^n \frac{4^p}{p^{3/2}}\right) =
\Theta\left(\frac{4^n}{n^{3/2}}\right).
$$


Logical and non logical symbols and predicates I am going through the text
from "R.Brachmann and H.Levesque: Knowledge representation and reasoning".
Here it has been described(in page 15) that there are two types of symbols : the logical symbols and the non logical symbols.

Logical symbols are the ones that have a fixed meaning and the non logical ones are the ones having application dependent meaning.

What I find confusing is "variables" having classified as logical ones whereas functions symbols have been classified as non logical ones.

I don't know whether I should be confusing this with the context of programming  languages or not but  variables also don't have fixed meanings and they too are created for application dependent use.

Shouldn't they both be in the same slot?

Now for predicates, I do not understand what exactly is  a predicate? Do predicates mean the same thing as relations like "greater than", "less than"? If yes, then can there be an infinite variety of predicates? I can think of only this "lesser than ", "greater than", "equal to".
What are some more examples of predicates?

P.S : Sorry about the predicate part , perhaps the following link contains a lot about it :
https://stackoverflow.com/questions/6337778/predicate-vs-functions-in-first-order-logic

A predicate is basically a set or a function from your universe $A$ to $\{0, 1\}$ (belongs to the set or not). More examples for that are edge relations or any kind of property you can assign to an object (e.g. male, female when $A$ is the set of all humans).

In FO you can distinguish non-logical symbols from logical symbols by looking at their interpretations via a structure. Constants, functions, and relations are assigned by this structure. Variables are not non-logical symbols because they do not change their meanings when you vary the structure you use for the interpretation of the formula. However, they also have no fixed meaning (compared to $\exists, \wedge, \neg, \ldots$), so you do not have to count them as logical symbols either.

You can probably find other sources, where variables are treated differently.


Cormen RB-DELETE_FIXUP(T,x) when x has no siblings I am working on chapter 13 of CLRS. I am studying how to fix the colors on a red-black tree after deleting a black node.

Suppose we want to delete the node 2. This is a black node. He will be replaced by his rith child in the RB-DELETE algorithm. Because we removed a black node and the node replacing it is black (all NIL are black) then we enter the loop in RB-DELETE-FIXUP. Now this loop immediately asks for x's sibling w to enter different cases. But w in this case would just be 3's right child which is T.nil. It gets even worse from here because we start asking about 3's right child children in case 3 or 4. What's supposed to happen when x does not have siblings?
These are the relevant algorithms:
RB-DELETE-FIXUP(T,x)
1 while x different from T.root and x.color == BLACK
2   if x == x.p.left
3      w = x.p.right
4       if w.color = = RED
5          w.color = BLACK // case 1
6          x.p.color = RED // case 1
7          LEFT-ROTATE(T, x.p)/ // case 1
8           w = x.p.right // case 1
9       if w.left.color == BLACK and w:right:color = = BLACK
10         w.color = RED // case 2
11         x = x.p // case 2
12      else if w.right.color == BLACK
13              w.left.color = BLACK // case 3
14              w.color = RED // case 3
15              RIGHT-ROTATE(T, w)/ // case 3
16              w = x.p.right // case 3
17           w.color = x.p.color // case 4
18           x.p.color = BLACK // case 4
19           w.right.color = BLACK // case 4
20           LEFT-ROTATE(T, x.p) // case 4
21           x = T.root // case 4
22    else (same as then clause with “right” and “left” exchanged)
23 x.color = BLACK

RB-DELETE(T,z)
1 y = z
2 y-original-color = y.color
3 if z.left == T.nil
4      x = z.right
5      RB-TRANSPLANT(T, z, z.right)
6 elseif z.right = = T.nil
7        x = z.left
8       RB-TRANSPLANT(T,z,z.left)
9 else y = TREE-MINIMUM(z.right)
10   y-original-color = y.color
11   x = y.right
12   if y.p = = z
13      x.p = y
14   else RB-TRANSPLANT(T,y, y.right)
15           y.right = z.right
16           y.right.p = y
17   RB-TRANSPLANT(T,z,y)
18   y.left = z.left
19   y.left.p = y
20   y.color = z.color
21 if y-original-color == BLACK
22   RB-DELETE-FIXUP(T,x)

```

Let $x$ denote the node you want to delete and $p(x)$ its parent. If $x$ has no sibling, then it necessarily means that $x$ is a red node, otherwise two path from $p(x)$ could have a different number of black nodes (therefore the tree is not a Red-black tree).
So the situation where $x$ is black and has no sibling can never happen (and the tree in your example is not a Red-black tree).


Best algorithm to find highest possible number of points from unique cards I am looking for the optimum algorithm for the following:

10-15 players
Each player has between 20 and 40 cards.
Each card can have one of up to 200 possible characters, and a separate numerical rating (higher is better). Card's characters may duplicate between players, or in players hands. Ratings are highly unlikely to exactly duplicate, though they may be close.

I need to select 5 'active' cards from each players' hands to meet the following criteria:

All characters must be unique - no duplicates in any of the 'active' cards of any of the players, or across all players.
The total of the players' active cards' ratings must be as high as possible.

Right now I:
1) go through all players and find the highest rated card still available;
2) mark it as active for the player whose card it is; and
3) mark that character as used for all other players (so it doesn't get used again).

Repeat 1-3 until all players have 5 characters
This gives a pretty good result. But what if we had the following:
Player A:
Character 1, rating 100
Character 2, rating 99
Character 3, rating 98

Player B:
Character 1, rating 97
Character 4, rating 2
Character 5, rating 1

For the sake of the example, assume we only need two active cards per players.
If Player A uses Character 1 per my algorithm then:

Player A: Character 1 + 2 = rating 199
Player B: Character 4 + 5 = rating 3
Total rating 201

Instead if Player A doesn't use Character 1 then:

Player A: Character 2 + 3 = rating 197
Player B: Character 1 + 4 = rating 99
Total rating 296

So my algorithm does not produce the best team total rating.
Can anyone suggest a better algorithm, other than just brute force trying all the possible combinations to find the highest total rating? I wonder, for example, if there's something about finding the optimum ratings for each player and then adjusting them to avoid duplication with other players; or perhaps something completely different.

I don't know why D.W. believes this is NP-complete, because it isn't. In order to solve the problem let us first change it (without loss of generality):

For each player only keep the highest rated card of a particular character. The lesser rated card(s) will never be part of the optimal solution.

For each player add a virtual card to their hand for each character they're missing, with rating -1 (or -inf if ratings can be negative). This ensures this card is never picked, but normalizes the problem.

Duplicate each player 5 times.

Negate ratings to turn them into costs.

Let's assume we had $p$ players and $c$ characters in the roster. After this transformation we have a typical assignment problem, where we have $5p$ workers and $c$ tasks. Viewing cards as tasks and 'player hand slots' as workers, we have an associated cost $c(w, t)$ for a worker $w$ and task $t$ combination, and our goal is to minimize the total cost.


What is a stateful computation? I am reading about a specific field of probabilistic programming, and trying to understand what the term "stateful computation" means.

See: http://projects.csail.mit.edu/church/wiki/Simple_Generative_Models

(search for "XRP")

Stateful computation basically means that the model of computation has got a memory storage to store information, and it uses this information to compute. For example, let us say you have a function $f()$ computing something using state information. Then, if you do,

$x_1 = f()$
$x_2 = f()$
$x_3 = f()$
...

$x_1, x_2, x_3,.. $ may be all different. In functions, defined  as mapping in  set theory, we cannot have functions returning different values from different calls. We will need to define something like $\langle y, store_{i+1}\rangle = f(\langle x, store_i\rangle)$ in that case.
 A sample code for $f()$ that is stateful is given below.

function f()
output: integer x;

global integer store initialized to 0;

x = store
increment store by 1
return x

This function will return 1, 2, 3, 4, ..., in sequence when it is called multiple times. Here store is the memory storage it uses to compute differently.

The function can also use other inputs to compute its output, such as events from an event queue, input data, interactive data, etc. but stateful computation must assume an underlying saving of state in the model of computation.

By the way, the model of computation for computers is Turing Machine, which can be thought as stateful computation if you use functions as subroutines, i.e., you do not start Turing machine from beginning at every function call.


Complexity of taking mod This seems like a question that should have an easy answer, but I don't have a definitive one:

  If I have two $n$ bit numbers $a, p$, what is the complexity of
  computing $a\bmod p$ ?

Merely dividing $a$ by $p$ would take time $O(M(n))$ where $M(n)$ is the complexity of multiplication. But can $\bmod$ be performed slightly faster ?

Shoup (Section 3.3.5, Theorem 3.3, p. 62) gives a bound for computing the residue $r$ in time $O(n\log q)$ where $a = q\cdot p +r$ and $\log a = n$.

I guess that if $p$ and $a$ are both roughly $n$ bit numbers, then $q$ (and hence $\log q$) should be rather small, giving $O(n)$.

If $a$ is an $n$-bit number, and $p$ is relatively small, then the multiplication approach should be faster.


Data structure to hold and retrieve points in a plane Definition 1: Point $(x,y)$ is controlling point $(x',y')$ if and only if $x < x'$ and $y < y'$.

Definition 2: Point $(x,y)$ is controlled by point $(x',y')$ if and only if $x' < x $ and $ y' < y$.

I'm trying to come up with data structure to support the following operations:

$\mathrm{Add}(x,y)$ - Adds a point $(x,y)$ to the system in $\mathcal{O}(\log n)$ complexity where $n$ is the number of points in the system.
$\mathrm{Remove}(x,y)$ - Removes a point $(x,y)$ from the system in $\mathcal{O}(\log n)$  complexity where $n$ is the number of points in the system.
$\mathrm{Score}(x,y)$ - Returns the number of points $(x,y)$ controls - number of points that $(x,y)$ is controlled by. Worst case complexity $\mathcal{O}(\log n)$ .

I've tried to solve it using multiple AVL trees, but could not come up with elegant enough solution.

This question appeared on my exams few days ago. The question should have relatively straightforward as it was worth $15/100$ points.
I tried to solve this by several AVL trees but couldn't come up with elegant enough solution.

Hints are welcome.

Solution outline:

We will maintain two AVL trees.

Tree_X: will hold points sorted by their X coordinate.
Tree_Y: will hold points sorted by their Y coordinate.

Each node within both trees will hold the following additional data:

Number of leaves in left sub-tree.
Number of leaves in right sub-tree.

For a point $(x,y)$ we will define regions $A$ ,$B$, $C$, $D$:

Point $(x',y')$ is in $A$ if $x' < x$ and $y' > y$.
Point $(x',y')$ is in $B$ if $x' > x$ and $y' > y$.
Point $(x',y')$ is in $C$ if $x' < x$ and $y' < y$.
Point $(x',y')$ is in $D$ if $x' > x$ and $y' < y$.

Now it is clear that Score(x,y) = |C|-|B|.
However $|A|+|C|$, $|B|+|D|$, $|A|+|B|$, $|C|+|D|$ could be easily retrieved from our two AVL trees, as we will soon see.
And notice that $\frac {(|A| + |C| + |C| + |D|) - (|A| + |B| + |B| + |D|)}{2} = |C|-|B|$

Implementation of required operations:

Add(x,y) - We will add point (x,y) to both of our AVL trees. Since the additional data we are storing is affected only on the insertion path and since the insertion occurs in (logn), the total cost of Add(x,y) is O(logn).
Remove(x,y) - We will remove point (x,y) from both of our AVL trees. Since the additional data we are storing is affected only on the removal path and since the removal occurs in (logn), the total cost of Remove(x,y) is O(logn).
Score(x,y) - I will show how to calculate $|B|+|D|$ as others done in similar way and same complexity costs. It is clear that $|B|+|D|$ is the number of points which satisfy $x' > x$. To calculate this number we will:

Find x in AVL_X. Complexity O(logn).
Go upwards in Tree_X until the root and on each turn right we will sum the number of elements in left sub-tree of the son. Complexity O(logn).

Total cost of Remove(x,y) is O(logn).


Identifying Coffman conditions in a given situation with deadlock Let's suppose there are N processes and we have the following code:

atomic <int> c = 0;
semaphore b = 0;

proc P(i){
   ...
   if(c.getAndInc() < N - 1){
      b.wait();
   }
   else{
      b.signal();
   }
   ...
}

A deadlock will occur as N - 2 processes will be blocked by $ b.wait() $.
I'm trying to identify how the Circular wait condition holds, being a necessary condition as it is.

(Circular wait means that "A set $\{ P_0, P_1, ..., P_n \}$ of waiting processes must exist such that $P_0$ is waiting for a resource held by $P_1$, $P_1$ is waiting for a resource held by $P_2$, ..., $P_{n-1}$ is waiting for a resource held by $P_n$, and $P_n$ is waiting for a resource held by $P_0$". This quote is from the book "Operating System Concepts", by Silberschatz, Galvin and Gagne.)

In other words, as there is deadlock, the circular wait condition must hold, but I just don't see it. Is there anything I am misunderstanding?

Thanks!

Considering the definition of circularity you exposed, it is important to highlight that ownership is not implemented in semaphores (it is for mutexes). So, in a way, each task is waiting for each other because each one has the possibility to "release" (i.e. perform a post to the semaphore since it starts from $0$) the resource (only if the condition inside the "if" is not satisfied). Extending this approach, also the task itself has the possibility to post to the semaphore. Moreover, note that the deadlock is present when $N>2$.


Finding a suitable NP-complete problem for reduction We are given a set of names and a set of papers with names written on each side of the paper (not necessarily different ones and either side of the paper can be empty). Can we place the sheets on a table such that every name shows up? Show that this problem is NP-complete.

I have difficulty in finding out an NP-complete problem from which it can be reduced to this problem.

I tried to reduce vertex cover and set cover problems but i was not successful. I am not sure if i am heading in the right direction.

This is SAT in disguise. Every name corresponds to a clause. Every paper corresponds to a variable. Each side of the paper corresponds to a possible truth assignment to the variable.

If this is unclear, I suggest working out an example.


Separability of the nearest power of two function I have a function $f$ given by

$f(x)=nearest\ upper\ power\ of\ two\ of\ x$

For example, $f(5)=8$ and $f(2)=2$.

Are $f(x \wedge y)$ and $f(x+y\mod{N})$ separable over some operator. For example, could we do:

$f(x\wedge y)=g(x)g(y)$

or

$f(x+y\mod{N})=g(x)\ op\ g(y)$

where $op$ is some arbitrary operator.

In other words, what can be done algebraically with the nearest power of two function?

In Warren's Hacker's delight, we have that the nearest power of two function is given by:

$
f(x)=1<<(32-nlz(x-1)-1)
$

on a 32 bit register and with $nlz$ being the number of leading zeros. Maybe this is of use?

No, $f(x+y)$ is not separable.

Consider: $f(3+5)=8$.  Also $f(3)=4$ and $f(5)=8$.

At the same time, $f(4+5)=16$.  Also $f(4)=4$ and $f(5)=8$.

It follows that $f(x+y)$ is not determined by $f(x)$ and $f(y)$ (consider $y=5$, $x_1=3$, $x_2=4$), so there is no function $h$ such that $f(x+y)=h(f(x),f(y))$.


Can converting NFA to DFA change the language? In the context of studying the conversion from an NFA to the equivalent DFA, I came across the following NFA, which accepts all strings over the alphabet $\{0,1\}$ which contain $01$:

After I converted the NFA to the equivalent DFA, it became:

The issue is that the NFA accepts the string $101$ but the DFA doesn't.
Is my conversion wrong or is there something I am missing about the NFA to DFA conversion?

By definition, two automata are equivalent if they accept the same language.
In your case, the DFA you construct is indeed equivalent to the NFA you start with. Both of them accept all strings starting with $01$. In particular your NFA does not accept $101$.


Average case running time of quick sort How to show that the quick-sort algorithm runs in $O(n^2)$ time on average ?
Because on average, the expected running time is in $O(n\log n)$. The algorithm should not be in exponential time.

It suffices to show that Quicksort runs in time $f(n) = O(n^2)$ in the worst case, since this immediately implies that it also runs in at most $f(n)$ time on average.
The recurrence equation that describes the worst-case running time for Quicksort is
$$
T(n) = T(n-1) + \Theta(n),
$$
which has solution $T(n) = \Theta(n^2)$.


How do I go about constructing a game tree that does not duplicate any states? Many games have states that can be reached via multiple paths in their gametree.

For concreteness, consider the game of tinychess (with the obvious(I hope) rules inherited from chess), which looks like this:

   /---V---V---\
   |   |<K>|   |
   D---+---+---C
   |   |   |   |
   D---+---+---C
   |   | K |   |
   \---A---A---/

When both your own and your opponent's King move left and right (or vice versa) the game has returned to the same state (there is no castling).

The state space of this game is rather small (even if we ignore symmetry) and amounts to only 9*8 + 9 + 9 = 90 states.  But a game may last an infinite number of turns given that the kings can keep moving back and forth.

How do I go about constructing a game tree that does not duplicate any states, for this game, and more generally?

Instead of a tree you use a game graph. You maintain a set of nodes (your game states) and, if you need them, a set of edges you already explored. Each time you want to explore a new edge you check whether it leads to a node in your set of nodes. If it doesn't you just found a new node and have to add it to the set.

Your programming language of choice probably provides an efficient data structure for sets already. If it doesn't, you can use a Hash Map or a Search Tree.

However, for non-toy games (a strange concept, games that are not toys...) I don't think that this will buy you anything. The state space is huge and you can't store any significant part. A small cache of some $k$ states might still work though.


Is the set of strings with equal number of 010’s and 101’s regular? Consider the language $$L = \{ w\in \{ 0, 1\}^*: \#_{010}(w) = \#_{101}(w) \}$$
Is $L$ is regular? If it is not regular, can we prove that using the pumping lemma (only with pumping down)?

Try writing a few words that are contained (and not) in your language. See if you can discern some structure that helps answering your question.

Hint: CS teachers are a devious, sadistic bunch. This might be a trick question...


Question regarding the proof that quadratic probing always finds an empty slot if the table is less than half full to prove this statement I assume the probing function as: $$h(i,x)=h'(x)+i^2 \text{ mod t} $$
And for $0\leq i,j < \frac{t}{2}$; $i\neq j; t \text{ prime}$: $$h(i,x) = h(j,x)$$
This results into $$(i+j)(i-j) \text{ mod t} = 0$$
Which is a contradiction as either $i+j=0$, $i-j =0$ or $(i+j)(i-j)=t$, and because i and j are chosen to be different and positive the first two can not be. Further t is prime and thus can not be written as a factor.
That is what I got so far. Judging by the Wikipedia entry this should suffice to prove the statement, but I fail to see why this actually shows that it always finds an empty slot. In particular because the fact that i and j are smaller than t/2 is not used at all.
Thank your for your input!

Suppose that $t=11$, $i=5$, $j=6$. Then $i+j \bmod t = 0$, and there is no contradiction. However, in this example $i < t/2$ while $j > t/2$. This sort of example cannot happen if $i,j < t/2$, since then $i+j < t$.


MST for a finite number of weights Let $F$ be a finite set of real numbers say $\{w_1,\dots,w_k\}$.

Let $G=(V,E)$ be an undirected connected graph and let $w\colon E\to F$ be a weight function.

Describe a linear time algorithm that will find a Minimum spanning tree in $G$.

Assume that $|V|\gg k$, i.e. the number of vertices is much larger than k.

I know that in such a case we can sort the edges in linear time and then use Kruskal's algorithm, but that will be slightly worse than linear time — $O(|E|\alpha(|V|))$.

I have heard about an approach that uses $|F|$ queue's but I couldn't figure it out, please help.

Summary: An algorithm of linear time in $|E|$ can be given by an implementation of Prim's algorithm where its priority queue is $|F|$ queues of equal-weight edges, assuming $|F|$ is a constant.

We will explicitly let $k=|F|$ be a constant. This constantness is indicated by "in such a case we can sort the edges in linear time.". It is then superfluous to "assume that |V|>>k, i.e. the number of vertices is much larger than k", since the complexity analysis by the big $O$-notations is about the behaviour of the algorithm when the input size increases to infinity, skipping the cases when the input size is not big enough.

Let us sort $F$ by constant time. To each edge with weight $w$ that is the $i$-th smallest in $F$ for some $1\le i\le k$, we will reassign weight $i$. Since comparison compatible weights of edges will lead to the same set of MSTs, this weight reassignment, which is done in linear time of $|E|$, does not affect the correctness of all later arguments. So, we will assume, furthermore, $F=\{1, 2, \cdots, k\}$. (We can, alternatively, add this step to the algorithm below.)

Here is the description of a wanted algorithm in detail (given an undirected connected graph $G=(V,E)$ and a weight function $w:E→F=\{1, 2, \cdots, k\}$). For brevity let us call the algorithm Prim's algorithm with constant queues (PAWCQ). PAWCQ is, most probably, more or less the "approach that uses $|F|$ queues" that is mentioned by the OP.

Create $R$ as an empty list of edges.
Mark all vertices as unvisited.
Create $k$ empty lists of edges $L_1, L_2, \cdots, L_k$.
Select an arbitrary vertex $v_0$. Iterate through all edges incident to $v_0$, putting an edge in $L_i$ if its weight is $i$. Mark $v_0$ as visited.
Repeat the following steps until all $k$ lists are empty:

Find the non-empty list with lowest subscript.
Remove an element from the list just found. Name that element $e$.
If both vertices of $e$ are marked visited, do nothing. Otherwise, let $u$ be the vertex marked unvisited. (The other vertex must be marked visited). Iterate through all edges incident to $u$, putting an edge in $L_i$ if its weight is $i$. Mark $u$ as visited. Add $e$ to $R$.

return $R$.

We can see that PAWCQ is indeed a variation of Prim's algorithm. In particular, it will always terminate in finitely many steps to return an MST of $G$.

The time complexity of PAWCQ is asymptotically  linear in $|E|$ when $G$ is given by its adjacency list (in the usual computation models), since both the insertion of an edge into the constant queues and the removal of an edge from the contant queues take constant time and each edge is inserted once and removed once.

Note that the order in which we remove an element in step $5.2$ does not affect the correctness of the algorithm. We can implement each list as, for example, a FIFO queue or a FILO stack.

Note that we can speedup the algorithm in several places for better performance, such as ending the algorithm as soon as we have collected $|V|-1$ edges. However, none of them will improve the big $O$ complexity since $O(|E|)$ is the best possible.


Similarity between Min-Conflicts and Coordinate Descent in CSPs? I'm currently writing a library that solves a specific type of problem that involves mainly constraint satisfaction.

I have came across the Min-Conflicts Algorithm which proved to be rather efficient in the context of the problem.

However, I have recently chanced upon the Coordinate Descent Algorithm and how strikingly it resembles the Min-Conflicts Algorithm.

Probably the only difference is that in Min-Conflicts, a random variable is selected to be modified at each step whereas Coordinate Descent cycles through the variables.

Am I right to say that apart from this difference, min-conflicts and coordinate descent are essentially equivalent? If so why are classified differently?

Am I right to say that apart from this difference, min-conflicts and coordinate descent are essentially equivalent?

In the same sense that A* and BFS are essentially equivalent except for the choice of which node to visit next, yes.

  If so why are classified differently?

There are some problems for which Min-Conflicts performs asymptotically faster (in the expected-time sense) than Coordinate Descent, and vice versa. Ditto, there are some problems where one (generally) converges and the other (generally) doesn't.


What is "dynamic" about dynamic programming? One of my seniors had a job interview and he was asked why it is called dynamic. He couldn't answer and after he gave up the interviewer said that there's nothing dynamic about it, its just called like that. That is hard for me to believe.

Does it refer to the fact that the subproblems are solved during run-time and used in reaching the final goal? Like dynamic memory allocation that happens during run-time?

[ANSWER]

I should have read this wiki article before asking the question, sorry.

Actually, there is nothing special in the name "dynamic programming"; the technique itself is just about smartly unwinding recursion. See this question and look at @Jeffe answer, in which is reported that Belman choose that name to be intentionally distracting.


Non-recursive (iterative) DFS with $O(n)$ size stack I usually deal with traversal algorithms such as DFS and BFS, and I have to implement them iteratively. However, in case of DFS, one challenge is that the size of stack can be $O(n+m)$ in worst case.

I was wondering if there is an iterative implementation of DFS that requires an $O(n)$ size stack instead of heavy $O(n+m)$ stack. I know that this is a worst case analysis, but I am concerned with this and want this to be really bounded.

Just as a reference, I am copying the algorithm from this solution, where vertices can be pushed into stack more than once and in the worst case, the stack size can be $O(n+m)$:

DFS(source):
  s <- new stack
  visited <- {} // empty set
  s.push(source)
  while (s is not empty):
    current <- s.pop()
    if (current is in visited):
        continue
    visited.add(current)
    // do something with current
    for each node v such that (current,v) is an edge:
        s.push(v)

You can keep only the topmost copy of a node on the stack:

dfs(source):
   s <- empty stack
   visited <- {}
   on_stack <- map<node,stack element>
   s.push(source)
   on_stack.add(source,s.top())
   while s is not empty:
      current = s.pop()
      on_stack.remove(current)
      if visited.contains(current):
         continue
      # handle current
      visited.add(current)
      for v a neighbor of current:
         if on_stack.contains(v):
            stack_element <- on_stack.get(v)
            unlink stack_element from s
         stack.push(v)
         on_stack.add(v,s.top())

If your stack is a linked list, the asymptotic runtime stays the same. I doubt however that it will be much faster in practice unless your graphs are very dense, because the constants involved are much bigger.


How do I verify that a DFA is equivalent to a NFA? I'm learning how to convert NFAs to DFAs and I want to make sure I'm doing it right. Obviously, going back in the other direction isn't a thing. Does anyone know of an algorithm to check that a DFA is equivalent to a NFA?

This is a problematic question. There is a way to check equivalence of automata, which I'll now explain, but I'm afraid it won't help you, as you will see at the end.

Recall that two sets $A$ and $B$ are equal iff $A\subseteq B$ and $B\subseteq A$ (this is the definition of set equality).
Thus, it is enough for you to verify that $L(D)\subseteq L(N)$ and $L(N)\subseteq L(D)$, where $D$ and $N$ are your DFA and NFA, respectively.

But how do you check containment of languages, you might ask. Well, now observe that $A\subseteq B$ iff $A\cap \overline{B}=\emptyset$ (where $\overline{B}$ is the complement of $B$).

Let's consider first checking whether $L(N)\subseteq L(D)$. To do this, you need to complement $D$ (very easy - swap the accepting an rejecting states), then construct the intersection automaton (e.g. with the product construction) with $N$, and check for emptiness, by finding a path to an accepting state.

The converse direction, however, will show why this doesn't help you. In order to check whether $L(D)\subseteq L(N)$, you need to complement $N$. But in order to complement an NFA, you first need to convert it to a DFA, rendering the whole idea pointless.

Essentially, the problem with your question is much deeper: you want to verify that you (an undefined computational model) executed a well-defined algorithm properly. So this is not really a computer-science problem.

I will say this: following the constructions I suggested, it is not hard to conclude that $L(D)\neq L(N)$ iff there is a word of length at most $2^{2n}$ ($n$ being the number of states of $N$) that is accepted by one and not by the other. So you can try all words up to this length.


Is the constant pi (not Raspberry) ever used in general computer science? Is the constant pi (not Raspberry) ever used in general computer science? If so, how so or when is it applicable?

The $\pi$ constant is not used in theoretical computer science due to some intrinsic value or utility of the constant itself.
However, it is (obviously) used in the simulations of physical systems or mathematical equations in which it appears. Precisely for this reason, one of the efforts that computer scientist and mathematicians have made in this regard was to identify new methods and algorithms to be able to generate as many digits of its decimal expansion as possible.

If today we know $\pi$ up to 31.4 trillion decimal places
we owe it to the computational power of electronic systems.


How many times can you divide a list of n elements in 1/2 I am trying to wrap my head around recursion and divide and conquer algorithms. Can someone provide a proof and explanation of how many times a list of n elements can be divided in 1/2 on both sides.. In other words the total number of half divisions in a recursive divide procedure on a list of size n.

You haven't explained what "divide in half" means, but let's assume that it means to divide the list into two halves of as equal size as possible (equal if the number of elements is even, almost equal if it's odd).

You can draw recursive "division in half" as a tree. The root is labelled by the original number of vertices, $n$. A node labelled $1$ is a leaf. Any other node labelled $m > 2$ has two children labelled $\lfloor m/2 \rfloor$ and $\lceil m/2 \rceil$ (this is the "division in half"). As yemelitc shows in their answer, the number of leaves is $n-1$; this is irrespective of the division being "in half". On the other hand, the depth of the tree (number of edges in longest path from root to leaf) is $\lceil \log_2 n \rceil$. You can try to prove this in the case where $n = 2^k$ (you can use induction on $k$).


Algorithm to find number of covering sets UPD: The following problem comes from error correction codes, to be precise -- either maximum-likelihood or belief-propagation decoding when the spectrum of special failing subsets is known (to some extent). Then the failure probability can be formulated as follows.

Let us say the universe set is $\mathcal U = \{1,2,\dotsc,N\}$ and we have $M$ subsets of it: $S_1, S_2, \dotsc, S_M$ ($S_i \subseteq \mathcal U$ for each $i$). Given $W$, find number of $W$-subsets of $\mathcal U$ that cover at least one of $S_1, S_2, \dotsc, S_M$. Mathematically speaking -- find cardinality of the following set:
$$
\{S \subseteq \mathcal U : |S|=W, \exists i \text{ s.t. } S_i \subseteq S\} \,.
$$

NB: union of the sets $S_1, S_2, \dotsc, S_M$ is not necessarily $\mathcal U$.

The algorithm does not need to be the most efficient, as I just need to find these numbers for my other problem. Hence, say, running time of 1 hour is acceptable. (Well, in the worst case, even 1 day might be okay if there is nothing better). The order of parameters I am interested in: $N \approx 200$, $M \leq 50$, $|S_i| \leq 8$, $W \leq 30$.

UPD: It seems that to find exact answer is very hard, therefore I am also interested in good bounds and/or approximations.

Example. $N=4, M=2, S_1=\{1,2\}, S_2=\{2,3\}$.

If $W=1$, the answer is 0: there are no 1-subsets that cover either $S_1$ or $S_2$.

If $W=2$, the answer is 2: $S_1$ and $S_2$ themselves.

If $W=3$, the answer is 3: $\{1,2,3\}$ (covers both $S_1$ and $S_2$), $\{1,2,4\}$ (covers $S_1$), $\{2,3,4\}$ (covers $S_2$).

If $W=4$, the answer is 1: $\mathcal U = \{1,2,3,4\}$ covers anything.

UPD: $M$ is now much smaller.

Is using the Inclusion-Exclusion-Principle (also called Sieve-formula) too inefficient?
According to the principle, if the union of any $L+1$ sets out of $S_{1}, S_{2}, \ldots S_{M}$ is bigger than $W$ then the number you are looking for is
$$
\sum_{n=1}^{L}{(-1)^n \sum_{i_{1},\ldots,i_{n}} \binom{N - |S_{i_{1}} \cup \ldots \cup S_{i_{n}}|}{W -  |S_{i_{1}} \cup \ldots \cup S_{i_{n}}|}}
$$
Edit: The complexity is around $M^{\frac{W}{|S_{i}|}}$ if the $S_{i}$s are close to being disjoint and around $2^M$ if the $S_{i}$s are close to being equal, so probably to big indeed.


What does it mean to have tokens at a state in a balancing network? I was assigned as homework:

  Suppose we have a width-w balancing network of depth $d$ in a quiescent
  state $s$ called $B$. Let $n = 2^d$. Prove that if n tokens enter the network
  on the same wire, pass through the network, and exit, then $B$ will have
  the same state after the tokens exit as it did before they entered.

However, I do not understand what the question is asking (please don't actually do the problem).

I have followed chapter 12 of the art of mutlicore programming, and its still unclear what the question is asking. Let me give you my thoughts (and confusions):

What does it mean by $s$ and $B$? According to the textbook, a balancing network is quiescent if every token that arrived on an input wire has emerged on an output wire (which makes sense because we only care when the tokens pass the network, not their order). Does a quiescent state refer to which cables the tokens have entered? Or since the order doesn't matter it just means that the same number of tokens that entered left the network?

What do they refer to as "a state"? Does it means were the tokens are located and which wires they left or if we only care about quiescent states, that the total number of tokens at the beginning and the end is the same?

It seems that there is a typo – $s$ and $B$ represent the same thing. It looks like the original $s$ was changed to $B$, but the author of the question forgot to delete $s$.

The state of the network is the state of all balancers – which way they point.


Which closure properties are always valid between regular, context-free and non context-free languages? I am making a scheme that respresents some closure properties (union, intersection, complement and concatenation) for regular languages, context-free languages, decidable languages and RE languages. Below you can see my scheme.

I am trying to find all possible internal closure properties of these different languages that will always be valid. E.g., I know that $$\text{Regular language } \cup \text{ CFL } = \text{ CFL } $$
$$\text{Regular language } \cap \text{ CFL } = \text{ CFL } $$
$$\text{Regular language } ^* \text{ CFL } = \text{ CFL } $$
What other internal properties are there between these languages?

I am afraid that there is no better general result than the obvious one.
Assume that $\mathcal K$ and $\mathcal L$ are two families of languages with $\mathcal K\subset \mathcal L$ such that $\mathcal L$ is closed under the operation $\circ$. Then for $K\in\mathcal K$ and $L\in \mathcal L$ we have $K\circ L\in \mathcal L$.
This is obvious, as both $K,L\in \mathcal L$. Usually we can choose simple examples that we can't do better. For instance, choose a "difficult" language in $\mathcal L$, so $L\in \mathcal L \setminus \mathcal K$. Then $L=\varnothing \cup L$, $L=\Sigma^*\cap L$, and $L=\{\lambda\}\cdot L$ show that we cannot do better than $\mathcal L$.


Determining whether the output of an algorithm is constant Suppose I have an algorithm $A$ that is known to halt before $f(n)$ steps for some function $f: \mathbb N \rightarrow \mathbb N$, where $n$ is the size of the input, and output is always either zero or one. Is it a decidable problem to determine whether $A$ always outputs zero?

It's not decidable. Given any program $P$, you can write a program $Q$ running in time (say) $O(n^2)$, which on input $n$ simulates $n$ steps of $P$, and returns 1 if $P$ halted. Then $P$ doesn't halt if and only if $Q$ always outputs 0.

This shows that your problem is $\Pi_1$-hard (since the halting problem is $\Sigma_1$-hard). It is also clearly in $\Pi_1$, and so it is $\Pi_1$-complete. (For the definition of $\Pi_1$, check out the arithmetical hierarchy on Wikipedia.)


LinkedList: Remove the kth node form the end Question: Write a function that takes in the head of a Singly Linked List and an integer k and removes the kth node from the end of the list. The removal should be done in place, meaning that the original data structure should be mutated (no new structure should be created). Furthermore, the input head of the linked list should remain the head of the linked list after the removal is done, even if the head is the node that's supposed to be removed. In other words, if the head is the node that's supposed to be removed, your function should simply mutate its value and next pointer. Note that your function doesn't need to return anything. You can assume that the input Linked List will always have at least two nodes and, more specifically, at least k nodes.
Each LinkedList node has an integer value as well as a next node pointing to the next node in the list or to None / null. if it's the tail of the list.
The Solution:
class LinkedList {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

function removeKthNodeFromEnd(head, k) {
  let first = head;
    let second = head;
    let i = 1;
    while(i <= k){
        second = second.next;
        i++
    }
    if(second == null){
        head.value = head.next.value; // Why can't I do: head = head.next
        head.next = head.next.next;
        return
    }

    while(second.next !==null){
        second = second.next;
        first = first.next;
    }
    first.next = first.next.next;

}

I have understood the above algorithm for the most part. Except why I need to have:
        head.value = head.next.value;
        head.next = head.next.next;

Why can't I just replace the above lines with a single:
head = head.next

head = head.next

would accomplish nothing. It would only change the local variable head.
Read the question again:

Furthermore, the input head of the linked list should remain the head of the linked list after the removal is done, even if the head is the node that's supposed to be removed.

Since you cannot change what node is the head, you change the contents of that node.