Weighted Average of Multi-Output Neural Networks [1] discusses how to construct an ensemble of neural networks by giving each network a certain weight $\alpha_i$:
\begin{equation}
f_\mathrm{GEM}(\boldsymbol{x}) = \sum_{i=1}^N \alpha_i f_i(\boldsymbol{x})
\end{equation}
where each $\alpha_i$ is obtained using a correlation matrix which is defined in the following way:
\begin{equation}
C_{ij} = E[m_i(\boldsymbol{x}) m_j(\boldsymbol{x})]
\end{equation}
where $m_i(\boldsymbol{x}) \equiv f(\boldsymbol{x}) - f_i(\boldsymbol{x})$, with $f(\boldsymbol{x})$ being the target function and $f_i(\boldsymbol{x})$ being the output.

I was wondering how should one compute $C_{ij}$ when the neural network has multiple outputs. Would one firstly calculate $\boldsymbol{m}_i(\boldsymbol{x}) \equiv \boldsymbol{f}(\boldsymbol{x}) - \boldsymbol{f}_i(\boldsymbol{x})$ for all examples and then compute $C_{ij} = E[\boldsymbol{m}^T_i(\boldsymbol{x}) \boldsymbol{m}_j(\boldsymbol{x})]$? I tried doing that (with MNIST data) but the accuracy was not better than when taking a simple average of all the networks in the ensemble. I would appreciate any help on this.

[1] M. P. Perrone and L. N. Cooper, "When networks disagree: Ensemble methods for hybrid neural networks," in Artificial
Neural Networks for Speech and Vision. Chapman and Hall, 1993, pp. 126-142.

Background: The simplest method of ensembling is to take an unweighted average of the outputs of the ensembles.  In general, if you want to use a simple ensemble of neural networks for classification, there are two reasonable options:

Average the logits from each model, then apply softmax once to the averaged estimate.
Each model applies softmax to get that model's confidence score, then average the confidence scores from each model.

Both are reasonable approaches.  Both can be used with multi-class classification: you independently average all the logits or confidence scores for each class separately.  You could try both to see which works better.  Personally, I would expect option #2 might work better, but the best test is to try them.

Perrone and Cooper's method: The framework you summarize generalizes the simple method, from an unweighted average to a weighted average, where the weights are calculated in a particular way.  In principle, that theoretical framework can be used for any univariate function, i.e., any function that outputs a real number, as long as we know what the "correct" output is for each instance in the training set.

In the context of multi-class classification with neural networks, you'll only be able to use Perrone and Cooper's method with option #2, i.e., applying it to the confidence scores from the models.  You can still use it in a multi-class classification setting straightforwardly, by applying it separately to each class: to get the confidence score of the ensemble for class $c$, take a weighted average of the confidence scores of each model in the ensemble, with weights derived based on the formulas you listed.  Basically, for 10-class classification, you treat this as 10 separate univariate functions (each class is treated independently).

Caveats: That paper is from 1993.  I don't know if it is the best way to create an ensemble of neural networks.  For one thing, they appear to be using MSE error as their loss.  Early work on neural networks used MSE loss, but since then we have learned that cross-entropy loss typically works a lot better for classification tasks.  I am not sure that their method of computing the weights will "play well" with cross-entropy loss.  So, it's not clear to me that their method will perform better than a simple ensemble (unweighted average) of models trained with cross-entropy loss.  I encourage you to do some experiments before relying too heavily on their approach.


What's an "applicable event" in the context of the FLP paper? I am reading Fischer, Michael J., Nancy A. Lynch, and Michael S. Paterson. "Impossibility of distributed consensus with one faulty process." Journal of the ACM (JACM) 32.2 (1985): 374-382, available here, the paper in which the well known FLP Theorem was proved.

I am having trouble understanding the notion of an "applicable event" used in this paper. Here's a quote from the paper (Section 2):

  Since processes are deterministic, the step is completely determined by the pair $e = (p,m)$, which we call an event. (This "event" should be thought of as the receipt of $m$ by $p$.) $e(C)$ denotes the resulting configuration, and we say that $e$ can be applied to $C$.

I can't understand this definition. When is an event applicable? When is it not applicable?

An event $e$ is applicable in configuration $C$ if it could happen at configuration $C$. Since $e = (p,m)$ means that message $m$ arrives at processor $p$, $e$ is applicable at $C$ if the message queue at $C$ contains the message $m$ directed at $p$. If there is no message directed at $p$ with contents $m$ then $e$ is not applicable at $C$.


heapify last 3 lines I'm following
http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/MIT6_006F11_lec04.pdf

Last 3 lines of heapify pseudocode are:

if largest =! i
    then exchange A[i] and A[largest]
    Max_Heapify(A, largest)

What is the aim of the last line?
Since largest still holds value of largest leaf, which is now root, what would the recursive run achieve? Just an empty run, it seems.Max-heap is already built.

You are asking several related questions. I will only answer the first one. The heapify procedure gets an almost-heap $A$ and a node $i$. The heap property is satisfied for all nodes except for $i$. Heapify proceeds as follows:

Determine the largest child $j$ of $i$.
If $A[i] \geq A[j]$, the heap property is already satisfied.
Otherwise, exchange $A[i]$ and $A[j]$, and run heapify on $A$ and $j$.

After the exchange, the heap property is no longer violated for $i$, but might be violated for $j$. For this reason we have to call heapify recursively on the node $j$.

I suggest you try a few examples and see for yourself that sometimes the recursive call is necessary.


Is it possible to use a copy-on-write strategy to modify a B+ tree? Alright, I'm not sure if this is more of a stack overflow question, but I'm going to try here because you folks seem more suited.

CouchDB makes an interesting claim about using an "append only" B+ tree to index its documents. Specifically...

  "In a B-tree, data is kept only in leaf nodes. CouchDB B-trees append
  data only to the database file that keeps the B-tree on disk and grows
  only at the end. Add a new document? The file grows at the end. Delete
  a document? That gets recorded at the end of the file."

and

  "CouchDB is actually using a B+ tree, which is a slight variation of
  the B-tree that trades a bit of (disk) space for speed. When we say
  B-tree, we mean CouchDB’s B+ tree."

SOURCE: CouchDB Documentation

This paper, describes the problem with an "append only" or "copy on write" implementation of a B+ tree. It suggests that such optimistic concurrency strategies are only available to a standard B tree. Specifically...

  "In a regular b-tree leaves are chained together. This is used for
  tree    rebalancing and range lookups. In a b-tree that is updated
  using copy-on- write leaves cannot be linked together. For example,
  Figure 2 shows a tree whose rightmost leaf node is C and where the
  leaves are linked from left to right. If C is updated the entire tree
  needs to be shadowed. Without leaf-pointers only C, B, and A require
  shadowing."

SOURCE: Rodeh O.

So the actual question...

Is possible to implement a copy-on-write B+ tree?

Yes it is. The trick is to use the size of file (where is the tree stored) as the means of calculating offset of the new root. In other words, when one modifies a leaf, most of the tree wont change and the blocks which do change get appended at the end, with root coming last.

More here: http://www.bzero.se/ldapd/btree.html


What happens under the hood when the process requests operating system to open a file? Suppose a process wish to open a file named test.txt. So it issues a system call requesting Operating system to find the file on disk,and to grab the handle of file to operate on it. My question is how does the operating system actually locates file on disk(Particularly sequence of actions the operating system performs to do this)? How partitions,file systems,directory structures used to accomplish this? (If possible kindly explain with an example)

I'll outline a fictional simplified filesystem for you. There are a few more details, but they are not needed to understand what's going on.

The operating system uses a module called a filesystem.
The filesystem is software that knows how the disk is organized.
It talks to the disk-driver which is software that tells the disk to read of write a particular sector on the disk.

The top down structure goes like this:

string s = ReadTextFileIntoString('c:\documents\test.txt');

//Translates to the following calls.
  Disk = GotoDisk('c:');
  //The root directory is always at sector 512.
  Dir = Disk.ReadDirectoryFromDisk(512);
  Sector = Dir.SearchForFileName('documents');
  if (Sector = -1) then StopWithError;
  Dir2 = Disk.ReadDirectoryFromDisk(Sector);
  Sector = Dir2.SearchForFileName('test.txt');
  if Sector = -1 then StopWithError;
  File = Disk.GetFile(Sector);
  s = File.ReadToString;  /see above.

A disk is made up of sectors, The first sector is 0 and the last is sector how ever many sectors there are on the disk. Say 1.999.999.999 for a 1 terabyte disk. Every sector is 512 bytes large. There are no missing numbers or gaps.
The very first sector, sector 0 holds the master boot record. Which is a small program in 512 bytes that starts up the operating system.
This tiny program knows how to read a sector from the disk and little else.

The disk driver is software that knows how to read and write a sector. That's it.
It has two methods.

ReadSector(sectornumber: integer, Buffer: 512bytes);
WriteSector(sectornumber: integer, Buffer: 512bytes);

Above the disk driver sits the filesystem,

It knows about:

Directories
File Allocation Table - FAT

A directory is a text file with the following structure:

filename1.1024.characters filesize starting-sector DirectoryYN
filename2....

As you can see we know where a file starts. The directory tells us.
But a sector is only 512 bytes. How do we know where the rest of the file is?
Files on disks are not continuous so if the first sector is 5 the rest of the file need not be on sectors 6,7,8 etc. In fact they can be anywhere at all.
To solve this problem there is the FAT The File allocation table.
This is structure to tell which sectors belong to a file.

It looks like this:

0 2 3 3 8 10 -1 -1 -1 -1

Every entry corresponds to a sector.
The 1 first entry is sector 0 (we start counting at 0 in computing).
The second entry is sector 1 etc.
Inside the entry is a reference to the next sector.
If a file has no next sector the entry references itself.
The first entry (in our fictional example) is the boot sector, which is a file 512 bytes long. It has no next sector, so the next sector is itself: 0.
The second entry is the FAT itself. It is a little larger, so it starts at sector 1->2->3->3 the entry for sector 3 points to itself, so there the file ends.
This is how the filesystem knows how to locate a file.
It knows where the file starts and it uses a little table to see where the different sectors after the first are located.

For those sectors that are empty it works the same way, but negative numbers are used. All the writer has to do is locate negative numbers in the file allocation table and write data into those sectors, then update the relevant entries in the FAT and the file is stored.
Note that there are two pieces of information stored a single entry in the table.
The first the the number of the entry, this corresponds with the sector, second it the data inside that entry, this corresponds with where the next sector in the chain is, or whether that sector is free.

An entry in the directory can be another directory (which is really a text file) or a normal file.
The filesystem will load one directory at a time, until it finds the entry for the file, then it will do whatever is requested (read, write, delete).


Efficient algorithm to compute the $n$th Fibonacci number The $n$th Fibonacci number can be computed in linear time using the following recurrence:

def fib(n):
    i, j = 1, 1
    for k in {1...n-1}:
        i, j = j, i+j
    return i

The $n$th Fibonacci number can also be computed as $\left[\varphi^n / \sqrt{5}\right]$.  However, this has problems with rounding issues for even relatively small $n$.  There are probably ways around this but I'd rather not do that.

Is there an efficient (logarithmic in the value $n$ or better) algorithm to compute the $n$th Fibonacci number that does not rely on floating point arithmetic?  Assume that integer operations ($+$, $-$, $\times$, $/$) can be performed in constant time.

You can use matrix powering and the identity
$$
\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n = \begin{bmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{bmatrix}.
$$
In your model of computation this is an $O(\log n)$ algorithm if you use repeated squaring to implement the powering.


Algorithm for solving binary quadratic Diophantine equations (BQDE) and its CTC Consider an equation of the form:

$Ax^2+Bxy+Cy^2+Dx+Ey+F=0$

where A-F are integer coefficients (binary quadratic Diophantine equation). I consider here the most general form, so assume all coefficients are non-zero.

Is there an efficient algorithm which can compute integer solutions for this type of equation?

Yes, such algorithms exist, i.e., if only BDQE has integer solutions, then those solutions can be found computationally, however - in exponential time. There is no polynomial time algorithm to tackle it in the general form (at least on a classical, non-quantum computer).

There's more information in Jeff Lagarias's slides for his talk Complexity of Diophantine Equations.


How to find spanning tree of a graph that minimizes the maximum edge weight? Suppose we have a graph G. How can we find a spanning tree that minimizes the maximum weight of all the edges in the tree? I am convinced that by simply finding an MST of G would suffice, but I am having a lot of trouble proving that my idea is actually correct. Can anyone show me a proof sketch or give me some hints as to how to construct the proof? Thanks!

What follows is taken from Tsuyoshi Ito's comment.

If you know Kruskal’s algorithm for the minimum spanning tree, it is an easy exercise to show that the output of Kruskal’s algorithm is a minimum bottleneck spanning tree. (I think that it is easier than showing that the output of Kruskal’s algorithm is a minimum spanning tree.)


Prove that REG is closed against removing all but lexicographicaly largest words (per length) Let $\Sigma_n = \{0, 1, ... , n-1\}$.  Suppose $L \subseteq$ $\Sigma^*_n$, and let
$\qquad\displaystyle\mathcal{B}(L) = \{ x \in L : x = \textrm{lex}\max L_m, m \in \mathbb{N}_0 \}$,
where $L_m = L \cap \Sigma_n^m$ and $\mathrm{lex}\max$ denoting the lexicographic maximum.
For example, $\mathcal{B}(\{0,1\}^*) = 1^*$ and $\mathcal{B}(\epsilon \cup 1(0 \cup 01)^*) = (10)^*(\epsilon \cup 1)$.  Prove that if $L$ is regular, then so is $\mathcal{B}(L)$.

Any hints?  I was thinking of perfect shuffling $L$ with itself, and then defining a morphism to compare each pair of characters in a shuffle to determine which is the lexicographically greater one.

Here is the basic idea. Suppose that $x0y \in L$. When would $x0y \notin \mathcal{B}(L)$? Exactly when $x1z \in L$ for some $|z| = |y|$. When does that happen? Fix some DFA for $L$, and suppose that after reading $x1$, it is at state $q$. Parikh's theorem shows that the set of lengths $\ell$ such that $x1z \in L$ for some $|z| = \ell$ is eventually periodic, that is, it is of the form $L_0(q) \cup \{k m(q) + a : a \in L_1(q) \text{ and } k \geq 0\}$ for some finite $L_0(q),L_1(q)$. We can further assume that $m(q) = m$ is the same for all states $q$, since there are only finitely many of them and we can take the LCM of the minimal periods.

As we read more and more zeroes, we obtain more and more constraints, which can be summarized in the form: the word cannot end in $\ell$ characters for $\ell \in L_0 + \{ km + a : a \in L_1 \}$. Note that there are only finitely many possibilities for $L_0$ and $L_1$, since $\max L_0 \leq \max_q \max L_0(q)$, and similarly for $L_1$. This means that we can store and maintain this information in a finite state automaton, and use it to decide $\mathcal{B}(L)$.


What is the algorithm for Shannon-Fano code? am I correct? I am wondering what is the true algorithm for the Shannon-Fano code? The the result I am getting based on the Algorithm in Wikipedia page contradicts the supposed/expected length of the produced code. According to the proof of Kraft's inequality,  $l_i = \lceil \log_2{\frac{1}{P_i}} \rceil= \lceil -\log_2{P_i} \rceil$.

  A Shannon–Fano tree is built according to a specification designed to
  define an effective code table. The actual algorithm is simple:

  For a given list of symbols, develop a corresponding list of
  probabilities or frequency counts so that each symbol’s relative
  frequency of occurrence is known.
  Sort the lists of symbols according to frequency, with the most
      frequently occurring symbols at the left and the least common at the
      right.
  Divide the list into two parts, with the total frequency counts of
      the left part being as close to the total of the right as possible.
  The left part of the list is assigned the binary digit 0, and the
      right part is assigned the digit 1. This means that the codes for
      the symbols in the first part will all start with 0, and the codes
      in the second part will all start with
  Recursively apply the steps 3 and 4 to each of the two halves,
      subdividing groups and adding bits to the codes until each symbol
      has become a corresponding code leaf on the tree.

For example:

$S_1 \rightarrow P_{S_1} = \frac{4}{9} \rightarrow Code = 0 \mapsto$ And: $\lceil \log_2{\frac{9}{4}}\rceil = 2 \neq 1$ Bad!

$S_2 \rightarrow P_{S_2} = \frac{2}{9} \rightarrow Code = 10 \mapsto$ And: $\lceil \log_2{\frac{9}{2}}\rceil = 3 \neq 2$ Bad!

$S_3 \rightarrow P_{S_3} = \frac{2}{9} \rightarrow Code = 110 \mapsto$ But: $\lceil \log_2{\frac{9}{2}}\rceil = 3 = 3$

$S_4 \rightarrow P_{S_4} = \frac{1}{9} \rightarrow Code = 111 \mapsto$ And: $\lceil \log_2{\frac{9}{1}}\rceil = 4 \neq 3$ Bad!

We can see that the length of produced Shannon-Fano code is $1$, but it supposed to be $2$. Which mean this algorithm is not correct. What is correct algorithm then?

Additional note: If we look at the example 1 of this document, we can see that the length of $A4$ is supposed to be $3$ not $4$. The same contradiction. Another contradiction in example 1 of this other document. I think it is clear what I am talking about.

More additional note:
Here is the page 45 of this textbook -Information and Coding Theory (Springer Undergraduate Mathematics Series) 2000th Edition

You are confusing "Shannon coding" from "Shannon–Fano coding" (terminology could vary across sources). Per Wikipedia, Shannon–Fano coding is the algorithm you mention, while Shannon coding is any coding assigning a symbol occurring with probability $p_i$ a codeword of length $\ell_i = \lceil \log_2 \frac{1}{p_i} \rceil$. Per Wikipedia, Shannon–Fano coding always leads to codewords whose lengths are within one bit of $\log_2 \frac{1}{p_i}$. This is also a feature of Shannon coding, but the two need not be the same. In particular, Shannon–Fano coding always saturates the Kraft–McMillan inequality, while Shannon coding doesn't.


Finding CNF of $(p \rightarrow q) \rightarrow p$ and $\lnot (q \wedge (\lnot p \rightarrow q)) $ I'm trying to find the CNF of the $(p \rightarrow q) \rightarrow p$ and $\lnot (q \wedge (\lnot p \rightarrow q))$, and afterwards proving it's validity. As i'm new to CNF i wanted to ensure i've found the right CNF before trying to move on, so for $(p \rightarrow q) \rightarrow p$:

the normal from is:
$p \rightarrow q \wedge q \rightarrow p$

and it's valid?

Your formula is incorrect as CNF. Conjunctive normal form (CNF) is a normal form like

$$
  (a_1 \vee \neg a_2 \vee \dots \vee a_n) \wedge (\neg b_1 \vee \dots \vee b_m) \wedge \dots \wedge (c_1 \vee \dots \vee c_l)
$$

therefore a formula in CNF has only literals (i.e. atoms or negated atoms), $\wedge$, and $\vee$. It doesn't have $\to$.

If it's allowed to transform $p \to q$ to its equivalent formula $(\neg p) \vee q$, you can use this for the first step to convert a given formula to a CNF formula.


What is a certificate in plain english? I've got this question from a course:

Show how to efficiently find a certificate for each of the following problems assuming that the decision problem is efficiently solvable.

And it seems like this has been poorly explained and I am getting conflicting answers on how to answer. For explanation purposes I will consider my problem to be f(x) where given a truthy value for x f(x) will output 1 and the opposite for falsey values.
In plain English, a certificate is a variable x such that the verifier for a problem can output 1 or 0.
In the case of f, a certificate would be x=1 or x=0 or similar.
Is this correct?
The problems are made of a few parts:

The problem, given x can we do y.
A certificate, an x.
A verifier, given y is it an actual answer for x.

For example, the compositeness problem, "given an integer $X$, is it composite?" might have a certificate $n_1, n_2$ where $X=n_1n_2$. This certificate would be checkable in time polynomial in the length of the certificate.


Typing dependent pattern matching I'm curious on how to type a dependent pattern matching in a functional language. What should the rule for typing

match e with
| C_1 a_1_1 a_1_2 ... a_1_n1 -> e_1
| C_2 a_2_1 a_2_2 ... a_2_n1 -> e_2
| ...
| C_m a_m_1 a_m_2 ... a_m_nm -> e_m
end

be, where e is of type T, which has constructors C_i for each i.

I think that to prove that the pattern match has a type T', we need to prove
that each e_i has type T' under specific assumptions, but I can't quite pinpoint those assumption to add into the context.

In general matching with dependent types can be quite subtle! You'll note that in the Coq documentation that the extended pattern-matching syntax is

match t as x in T1 return T2 with
    | C1 a1 ... an
    ...

In particular, ommiting any of the as, in or return clauses can prevent type inference of the statement.

Intuitively, if the type of (say) constructor $C_1$ is
$$ \Pi(x_1:A_1)\ldots(x_k:A_k).I\ \vec{p}$$
and the type of the matched term $t$ is
$$ I\ \vec{v}$$
then you get the constraint
$$ \vec{p}[\vec{a}/\vec{x}]\simeq \vec{v}$$
which may lead to an undecidable problem, as explained in Goguen et al.

Then all you need is for each right hand side to correspond to the appropriate instance of the return type. This return type may depend on $t$, so the return clause specifies the pattern of the return type as a function of $x$ (which represents $t$ through the as clause).

More formally, each $e_i$ must have type:

$$ T_2[C_i\ \vec{a}/x]$$

and the type of the whole match expression is
$$ T_2[t/x]$$

More details can be found here.


Finding subset such that one sum is more than target and another sum is less Consider the following problem: Given positive integers $a_1,\ldots,a_n,b_1,\ldots,b_n,A,B$, does there exist a subset $S$ of $\{1,\ldots,n\}$ such that $\sum_{i\in S}a_i\geq A$ and $\sum_{i \in S}b_i\leq B$?

Is this problem NP-hard? I'm thinking there is possibly a reduction from the subset-sum problem, but here there are two lists, and the conditions are inequalities rather than equalities, so I'm not quite sure how to start.

Another remark is that if the condition is just $\sum_{i\in S}a_i\geq A$, then it would be easy because we can check the sum of the whole subset.

Consider what happens if you set $a_i=b_i$ for all $i$.  I expect you should be able to take it from there...


Does a NFA/DFA need a failure state? I'm learning for my exam in theoretical computer science and I'm not sure about it, because I got different sources with different answers. So I wanted to ask here:

If I draw a NFA/DFA and I maybe don't need the transition from a state $z_k \rightarrow z_{k+1}$  with  a $0$ above the alphabet $\Sigma = \{0,1\}^*$ so I only need there a $1$, do I always need a failure state $z_F$ so that $\delta: z_k (0) \rightarrow z_F $. Or can I omit that in the drawing? Or is there a difference between DFA and NFA, so that I need to write this failure function if its an NFA but I can omit it if it's an DFA? In my exercises my prof deducted one point because I had no failure state but just one or two times..

Hope somebody can help

A state in a DFA always needs to have exactly one transition per symbol in the alphabet. I have understood from a few of my classmates that some teachers omit the error-state. I however prefer to show the error-state in graphs, since it simplifies verification of determinism in a graph.

In a NFA there can be no such rule. Therefore it should work to not present a transition for the symbol (0) in this case. If the NFA would be determinized, this non existing transition, along with all other non-looping transitions would point to a error state.


Constructing 2-Universal Families Let H be a class of all functions, mapping M possible keys to N integers. Is it true that H is a 2-universal family? Is it a good idea to use H in applications?
I don't even know where and how to start. Can you give me a hint on how to prove this?
Is it even possible to prove this?

Can you give me a hint on how to prove this?

Let $H$ be a class of all functions which map universe $Z_n$ to $Z_m$. We will assume that, any particular mapping is done by exactly one of the functions in the class.
Total functions in $H$  = number of all possible mappings = $m^n$
Given any distinct keys $x$ and $y$, we need to find number of all possible functions (mappings) in which they collide. The remaining $n-2$ keys have total mappings: $m^{n-2}$. The $(x,y)$ pair can collide by mapping to any of the $m$ slots. So,
Total functions in $H$ where $(x,y)$ collide = $m^{n-2}\cdot m = m^{n-1}$
Thus probability of collision = $m^{n-1} / m^n = 1/m$.


Does Warnsdorff’s algorithm for Knight’s tour problem always gives complete tour I have implemented the basic algorithm. easily available but I am not getting the complete tour.
The visited square never equals N * N;

In general Warnsdorff's rule is just a heuristic that guides the search. It is still possible that the search hits a dead-end and we are forced to backtrack.

So let us consider the $n \times n$ chessboard now.
Warnsdorff's rule (nor any other method) won't find a solution for $n < 5$ as a solution exists precisely when $n \geq 5$. Given that $n \geq 5$, an efficient algorithm based on Warnsdorff's rule is described in [1, Proposition 2.2]. Other independently discovered algorithms that work in linear time are known as well (see e.g., [2]).

[1] Conrad, Axel, Tanja Hindrichs, Hussein Morsy, and Ingo Wegener. "Solution of the knight's Hamiltonian path problem on chessboards." Discrete Applied Mathematics 50, no. 2 (1994): 125-134.

[2] Parberry, Ian. "An efficient algorithm for the Knight's tour problem." Discrete Applied Mathematics 73, no. 3 (1997): 251-260.


Is there any guarantee in asynchronous systems? We know that in an asynchronous system, no assumptions about process execution speeds or message delivery times are made. My question is: can we present any guarantee in asynchronous systems?
Some examples of the guarantees that I'm looking for are:

Consider two processes $p$ and $q$. $p$ sends a message an infinite number of times to $q$. $q$ delivers the message finally if two processes are correct (a process that never crashes is said to be correct).
If 1. is correct, then: no edge-cut in the network persists forever between the correct processes.

Your question is somewhat unclear. In asynchronous systems we normally assume that any message will eventually be delivered after some finite time. It if perfectly feasible to write an algorithm that sends infinitly many messages:
While(true):
   Send a message to p;
   If received message form p do <...>

This is valid and will indeed cause infinite number of message exchange. But the timings of these messages are unknown.
I am not sure what you mean at your second point. If there are no link-failures, all edge-cuts remain alive. As long as the processors are correct, the link will be utilized infinitely often.


Edge contraction in DAG I have a directed acyclic graph whose vertices are either red or black.
I want to perform edge contraction between pairs of red vertices only, and avoid introducing cycles. The goal is to have the fewest number of red vertices remaining (and no cycles. Note that after edge contraction, the resulting self-loop is removed, it does not violate the no-cycles rule).

In the example below, I could merge vertices 1 and 3, or I could merge vertices 3 and 4, but I can't merge all 3 together, since this would introduce a cycle with black vertex 2.

I want to merge as many red vertices as possible, to reduce the number of nodes in the graph. How can I do this efficiently? I don't necessarily need an optimal solution (where optimal => smallest number of remaining vertices). I potentially have 100k nodes, evenly split red and black.

There are 2 optimal solutions for the simple example shown. Here is one.

Here are some pointers to one possible solution, taken from Google's TensorFlow XLA compiler.

Their use case is to partition a computation graph (usually a DAG) into subgraphs and place them on different devices, while satisfying data dependencies and maximizing each subgraph. For instance, in your question, assuming nodes must either be placed on CPU (red) or GPU (black), we would compute subgraph Node{1, 3} on CPU, and then compute Node{2} on GPU, and finally Node{4} on CPU.

The algorithm consists of two parts:

Union-find for keeping track of node merging

Start reading from here, the main loop for contracting edges

An "incremental cycle detection" algorithm

This functionality is implemented in the GraphCycles class
It is based on a dynamic topsort algorithm for DAG as documented here


Decide the set of all Turing machines with $L(M)=\left\{\langle M\rangle\right\}$ How can I prove that the language $L=\left\{\langle M\rangle\mid L(M)=\left\{\langle M\rangle\right\}\right\}$ is not decidable?

When trying to use a diagonal argument, I cannot conclude from $L(M)\ne\left\{\langle M\rangle\right\}$ that $\langle M\rangle\not\in L(M)$.

Also, it seems that I cannot apply Rice's theorem because I can't say anything about the machines' encodings $\langle M\rangle$ in the definition of the set $\mathcal{S}$.

Is there an easy reduction to a known undecidable language?

The recursion theorem states that a Turing machine can get its own description on to its tape. In fact, there is a simple reduction from the acceptance problem (ATM) to this problem.

Assume $L$ is decidable. Suppose I am asked whether a TM $M$ accepts $w$. I will construct a machine $M'$ which on input $x$ checks if $x=\langle M' \rangle$. If it is not $\langle M' \rangle$ it simply rejects $x$. Otherwise it simulates $M$ on $w$, and if $M$ accepts $w$ then $M'$ accepts $x$. So $L(M') = \{ \langle M' \rangle \}$ iff $M$ accepts $w$. Hence we can pass this $M'$ as input to the decider $L$ and obtain answer for "$M$ accepts $w$?". But we know that ATM is undecidable, hence $L$ must be undecidable.


Coloring an interval graph with weights I have an interval graph $G=(V,E)$ and a set of colors $C=\{c_1,c_2,...,c_m\}$, when a color $c_i$ is assigned to a vertex $v_j$, we have a score $u_{ij}\geq 0$. The objective is to find a coloring of $G$ with at most $m$ colors that maximizes the total score (sum of the scores of the vertices).

Do you know about any results in the literature that may help me to find the complexity of this problem?

The sum coloring problem can be reduced to this problem by having $n$ possible colors with weights $u_{ij} = n - i$. Sum coloring is NP-hard for interval graphs.

Source: https://en.wikipedia.org/wiki/Sum_coloring


NFA to DFA accepting states I was working through an NFA to DFA conversion tutorial: where I'm converting the following NFA to a DFA:

I used lazy subset construction which I'm sure the tutorial did as well because we had the same transition table of:

delta      |  0        |  1       |
===========+===========+==========+
{a}        |{a,b,c,d,e}|{d,e}
{a,b,c,d,e}|{a,b,c,d,e}|{b,d,e}
{d,e}      |{e}        |{∅}
{b,d,e}    |{c,e}      |{e}
{e}        |{∅}        |{∅}
{c,e}      |{∅}        |{b}
{b}        |{c}        |{e}
{c}        |{∅}        |{b}

However, there state diagram for the resulting DFA is this:

I'm confused as to why the set {b,d,e} isn't being labeled as an accepting state.

Also, I don't know if I'm allowed to ask this but if there is a place with more NFA to DFA converting practice I'd love to know, right now I'm just using any old study guide I can find on google.

You're right, {b, d, e} should be a final state. Otherwise the DFA would reject 0001 while the "equivalent" NFA accepts it.


Redistribute users over (chat)rooms I'm working on some kind of multiplayer game and for the best experience for the users I want to make sure the rooms are somewhat balanced at all time. By balancing I just mean the amount of users in the room (not score based or anything). I already figured out what the size of rooms should be and how many users there should be per room (based on a fixed maximum number of users per room). For a maximum of 4 users per room I came to the following distributions:

(total users) | (array of rooms (number is amount of users in room))
----------------------------------------------------------------------
4:              [4]
5:              [3, 2]
7:              [4, 3]
9:              [3, 3, 3]
13:             [4, 3, 3, 3]
...

I use the following code/algorithm to determine the distribution:

function calculateRoomDistribution(numUsers, maxUsersPerRoom) {
  const numRooms = Math.ceil(numUsers / maxUsersPerRoom)
  let distribution = []
  for (let i = 0; i < numRooms; i++) {
    distribution[i] = 0
  }
  for (let i = 0; i < numUsers; i++) {
    distribution[i % numRooms]++
  }
  return distribution
}

What I couldn't figure out however, is how to transition from one state to another. Let's say I have 13 users, divided over 5 rooms, respectively 4, 2, 2, 3, 2 users... I want to redistribute them into 4 rooms, with 4, 3, 3, 3 users. How would I approach such a problem? I was thinking of first removing the rooms that already have the right amount of users (4 and 3). That would leave me with [2, 2, 2]. But I noticed I would have to write a lot of edges and exceptions and I have a feeling there must be a smarter way. What type of algorithm am I looking for?

Here is one simple algorithm.  Pick one room that has too many people in it, and one room that has too few people in it, and move one person from the first room to the second room.  Repeat until convergence.


Why isn't converting from an NFA to a DFA working? I am just beginning to learn computation theory. I wrote up a non-deterministic finite automata that accepts strings that contain the substring "abba":

I tried to convert it to a DFA by putting together sets of states in the NFA to be states of the DFA:

However, I just realized that my DFA doesn't accept strings such as "abbaa" that do not end in "abba." That means that my methodology was wrong. Why? I thought it would make sense to combine states of the NFA to make states of the DFA.

Your methodology for creating the DFA from the NFA is fine. The problem is that you started with the wrong NFA (you'll notice that your NFA doesn't accept abbaa either). Try this one instead:


Verifying whether a description of a shortest path tree is actually the shortest path tree in O(V+E) time This is from CLRS problem 24.3-5:

  Professor Gaedel has written a program that he claims implements
  Dijkstra’s algorithm. The program produces $v.d$ and $v.\pi$ for each vertex
  $v \in V$ . Give an $\mathrm{O}(V+E)$ time algorithm to check the output of the
  professor’s program. It should determine whether the $d$ and $\pi$
  attributes match those of some shortest-paths tree. You may assume
  that all edge weights are nonnegative.

All the answers I find online, explain how to solve this problem, but not why their solution is correct.

Let us look at what we need to do:

We need to make sure that for the source node $s$ we have $s.d = 0$ and $v.\pi = \emptyset$. This can be done in $\mathrm{O}(1)$ time.
We need to verify that the $\pi$ table corresponds to a tree. This is simple, we just build the undirected graph corresponding to the $\pi$ table, and then run a DFS traversal to see if the graph has cycles or not. Can be done in $\mathrm{O}(V+E)$ time.
For every node $u$ not reachable from $s$, it must be the case that $u.\pi = \emptyset$ and $u.d = \infty$. Another simple check, find everything you can reach in the tree that you drew in step 2, and for every other node do the checking. Another $\mathrm{O}(V+E)$ term.
For every edge $(u,v)$ in the shortest path tree it must be true that, $v.d = u.d + w(u,v)$. Check to ensure that this is the case. Because the professor might put random guesses for the distance values that turned out to be correct, but they had absolutely no connection to the shortest path tree given.

Everything until this point is 100% simple and clear. But the last point, is what I find difficult to argue about.

Relax every edge of $G$ exactly once, if any distance values change, then the shortest path tree given is wrong, if all stay the same then it is correct.

Why is this true? How to prove that if indeed the shortest path tree is wrong, relaxing every edge of $G$, no matter the order, will definitely improve at least one of the distance values?

Relax every edge of $$ exactly once, if any distance values change, then the shortest path tree given is wrong, if all stay the same then it is correct.

Referring to this statement: As in Bellman-Ford, we run the algorithm $|V|-1$ times to compute the single-source shortest path. After this, we run the same algorithm once to check whether any relaxation happened in the graph. If there was any relaxation that means there is a negative weight cycle, and we return False. That's not exactly the case here, however you get the idea! If the algorithm given by the professor was right, then there shouldn't have any room for relaxation because relaxation means that the current shortest path $\mathrm{delta}(s,v)$ is not the shortest ($d(s,v) > \mathrm{delta}(s,u) + w(u,v)$). Hence, the algorithm was wrong.


How many time and space units does this algorithm take? This is what I counted but I know I'm wrong since my conclusion is not in the choices:

t = time unit
s = space unit
y=1 : 1t & 1s
for 0 <= i <= N : Nt & 1s
y=y*i : 2 reads, 1 write, 1 multiplication therefore 4 time units,
the for loop is thus 4N time units
total time = 4N+1
total space = 2 (because there are only two variables that need to be
stored)

My thoughts about the question
Honestly speaking, this question is really weird. Usually when you ask about the time and space complexity, you mean it in big-O or other asymptotical notation. Not the actual literal number of steps the algorithm takes, since this can change depending on the hardware you are using and a lot of other factors.
So the fact that most answers are with the same asymptotics, it makes absolutely no sense!

My answer to the question
The answer depends on what you define a "time unit" and "space unit". Under normal circumstances, you would say this algorithm takes $\Omega(N\log(N))$ time, and would need $\Theta(N\log(N))$ space as well.
The explanation for that comes from the fact that $y$ at the $k$'th iteration is computed to be $k!$ ($k$ factorial). Saving in memory the value $N!$ needs $\log(N!)=\Theta(N\log(N))$ space, and thus also the running time must be at least $\Omega(N\log(N))$.
An upper bound for the running time depends on the algorithm used for multiplication.

Your answer to the question
Assuming multiplication takes $O(1)$ time, and a single unit of space is defined as a single variable, your solution is correct. This also demonstrates the problem of not using big-O notation, since your answer is correct however it is not one of the listed answers.


Minimum finger search tree complexity Suppose I have an AVL tree with a pointer to the minimal element. I'd like to conduct a search for some key x, which is the $k$-smallest key in the entire tree.
I can do this by "climbing" up the tree's left branch, comparing x with the current key. As long as

  (x > curr.key) && (x > curr.parent.key)

I keep climbing up, but once the second condition is violated, I slide down to the current right-subtree, and from there on it's just a standard BST search.

The claim is that the worst case complexity is always $O(\log k)$, for any $k$. But I can't convince myself this is accurate: if x is larger than the tree's root's key (the median, or equivalently $k > {n\over 2}$), that implies I must have traversed the entire left branch, which for a balanced tree is $O(\log n)$ - and only then I can find x in depth of $O(\log k)$.

Am I looking at this the wrong way?

Yes, you might be looking it the wrong way.

  If $x$ is larger than the tree's root's key (the median, or equivalently $k>n/2$), that implies I must have traversed the entire left branch, which for a balanced tree is $O(\log n)$ - and only then I can find $x$ in depth of $O(\log k)$.

First, let us be accurate. The root's key may not be the median, although it sits roughly in the middle.

Let $r$ be the root node. Let $n$ be the number of nodes in the whole tree and $n_l$ be the number of nodes in the left subtree of $r$. Let $h_l$ be the height of that subtree and $h$ be the height of the tree, so $h\le h_l+2$ since an AVL tree is height balanced.

Suppose $x$ is larger than the root's key.  That means
$$n_l < k \le n.$$ We also have, according to the properties of an AVL tree.
$$\log_2 (n+1)\le h \le h_l+2 \le c\log_2(n_l+2)+b +2\lt c\log_2(k+2)+b +2$$
where $c\approx 1.44$, $b\approx -0.328$. So, for all $k\ge3$,
$$\log_2(n)\le2\log_2(k)$$

So if you have traversed the entire (height) of the left branch in order find the $k$-th smallest element, you will use $O(\log n) = O(\log k)$ steps.

In fact, if we only look at the subtree whose root is the highest node that we will climb to in search of the $k$-th smallest element, we have just proved that the worst case complexity is always $O(\log k)$


What is the formal, rigorous definition of a programming language? In programming language theory, people study the theory behind programming languages. But I have never heard any formal definition of programming languages themselves. What is the formal definition, not of a particular programming language like Python or C++, but of programming languages themselves?

To taper expectations a little bit, I will first note that the term "programming language" is deliberately broad: it is intended to be open to some interpretation. It means, no more and no less, any convention that is used for describing instructions for computers to execute. This includes, for example, not just C++ and Python, but also things like Nondeterministic programming, where we actually don't tell the computer exactly what to do, but give it several alternatives and allow it to choose any one of them; declarative logic languages like Datalog where we give the computer a set of logical axioms and ask it to deduce all the true statements from those axioms; and even very low-level descriptions like Turing machines and electrical circuits, where we give the program explicitly as electrical or mechanical components. All of these are ways of describing instructions to computers, so all are valid programming langauges at very different levels of abstraction.
However, programming languages researchers do generally agree on some common formal components of programming languages that should always be present, and these serve as a general definition. Namely:
every programming language is defined by a syntax and a semantics.

Syntax. This is a formal grammar which gives the set of programs that can be written. Importantly, the formal grammar consists of finitely many syntax elements, which are described in terms of other syntax elements. For example a simple grammar is:
Variable := x | y | z
Term := 0 | 1 | Term + Term | Variable
Program := set Variable = Term | return Term | Program; Program

In this simple language, we have three syntax elements: Variables, Terms, and Programs. In a formal grammar, each syntax element has finitely many cases for how it can be constructed via other syntax elements. For example, a program is either an assignment (setting a variable to equal a term, e.g. set x = x + 1), a return statement, or a sequence of two programs which should be executed one after the other.

Semantics. Syntax is just describing the set of valid programs; but it doesn't say anything about what those programs mean. Semantics is a way of assigning meaning to programs. Unlike syntax, which is almost always given as a formal grammar as above, semantics can be given in at least two different ways: these include "denotational semantics", where we assign a mathematical object such as a function to each program, or "operational semantics", where we describe the execution of a program in a more true-to-life way as a sequence of steps.
To illustrate this, starting with denotational semantics: we would say that the term 3 + 5 + 8 is assigned the meaning of 16. More interestingly, the program set x = x + 3 + 5 is assigned the meaning of the mathematical function mapping every integer to that integer plus 8.
Operational semantics, on the other hand, is very different. We would say that the term 3 + 5 + 8 evaluates to 8 + 8 which in turn evaluates to 16. We would also say that the program set x = x + 3 + 5 in a context where x = 5 evaluates to a context where x = 13. So, instead of giving a meaning to each term or program itself, we give a meaning between terms called "evaluates to": we give a formal definition of what it means for A to evaluate to B in the context C.
In any case, the semantics of a language, whether denotational or operational (or something else) gives meaning to the symbols and allows us to make sense of what programs compute, not just what they look like.

Putting these together, we get the following definition.
Definition:
A programming language consists of (1) a syntax, given as a formal grammar; and (2) a semantics, given either as denotational semantics which gives a meaning to each syntax element, or an operational semantics which says when two programs or program contexts relate.


Where does the need for conditionals (if, switch, jump tables, etc...) truly arise? I know that this question is a bit out-of-the-box, yet i would be glad if someone could help with a good answers for my question because it is something that is troubling my curious mind.

When we program we have no doubt that we need conditionals, like the if statement. I will use the "if" statement as a reference throughout the topic.

I mean, if we have a program like

int main(int argc, char** argv)
{
int n = atoi(*argv);
if(n%2==0)
  printf("even");
else
  printf("odd");
}

Given these conditions, where we can only use what comes after the input is passed to the program to perform our computation, i cannot deny that i need an if statement to distinguish between an even and an odd number. This is just an exemple.

But then i wonder, what if we could mess with what comes before the argument passing occurs?

Let's assume that this program is called oddEven.exe. When the user executes the program by writing oddEven(3) for instance, on the command line, the keyboard sends a signal to the computer with the number 3, which is simply written to memory. No analysis is done on the input, it is simply dumped into memory.

Given this situation, once we run the program, we know only what a number (actually a sequence of characters) was written, but not which one was written. Now let's assume that the hardware itself would be responsible for calling the appropriate branch of the program once the number is written, as if two diferente programs were written.

int mainEven()
{
//code for even numbers;
printf("even");
}

int mainOdd()
{
//code for odd numbers;
printf("odd");
}

The hardware would then be responsible for decoding the signal sent by the keyboard and, treating it as a number, check whether it is odd or even. We could at this point argue that such a machine would make it possible to program without ifs. Yet, haven't we just implemented the if statements at the hardware level? Hence we couldn't get rid of conditionals.

Now, what if the computer was actually made out of several subcomputers, each implementing a diferent branch of the program. We can also see this as if we had 2 computers. Consider that once a button is pushed, computer C1 prints "even" whereas computer C2 prints "odd".

The user would then be responsible for choosing which computer to use based on the output he knows is right for the number he has in mind. At this point, neither the hardware nor the software contain conditionals. Is the problem solved? No! The conditionals are now "running" on the user's brain, who has to decide which computer to use.

My point is, where do conditionals come from? Where do they stop? Can we avoid them somehow? Can you prove me we need them? If we do, why do we put them at the hardware level? Why does the input of a program have to be compared against values to determine the branch to execute?

I am a computer scientist myself, but i feel like i have lost my path once i thought about this subject. I'm having trouble proving that i undeniably need conditionals to perform computation.

I'd be glad for some insightful answers! Thanks in advance

It is certainly possible to avoid all conditionals, but most programmers get majorly annoyed if they try to use functional style on a very large program.

But then, no one ever programs anything serious directly in a Turing machine either.


Which pass do you look at for Radix Sort stability? I know this is a fairly poorly worded question, but I can't think of a better way to phrase it in the title.

So in Radix Sort, you go digit by digit from least significant to most significant, and along the way you are swapping elements around. When considering the case where two digits are the same, do you look at the original array to decide which should come first, or do you look at the previous iteration?

In one case you would have to store the original to look back on, so my guess is it's not that, but I can't tell which provides the correct result by my own examples. Let me know if I need to describe my question better and I will try.

Radix sort always uses the results of the previous pass, not the original array.  It does not attempt to store the original value of the array.  You can find a description of radix sort at Wikipedia or in standard algorithms textbooks, and you'll see that it has this property.

As Wikipedia describes, radix sort is stable if you sort the digits starting from least significant and moving on to most significant.


What is most efficient for GCD? I know that Euclid’s algorithm is the best algorithm for getting the GCD (great common divisor) of a list of positive integers.
But in practice you can code this algorithm in various ways. (In my case, I decided to use Java, but C/C++ may be another option).

I need to use the most efficient code possible in my program.

In recursive mode, you can write:

static long gcd (long a, long b){
    a = Math.abs(a); b = Math.abs(b);
    return (b==0) ? a : gcd(b, a%b);
  }

And in iterative mode, it looks like this:

static long gcd (long a, long b) {
  long r, i;
  while(b!=0){
    r = a % b;
    a = b;
    b = r;
  }
  return a;
}

There is also the Binary algorithm for the GCD, which may be coded simply like this:

int gcd (int a, int b)
{
    while(b) b ^= a ^= b ^= a %= b;
    return a;
}

Your two algorithms are equivalent (at least for positive integers, what happens with negative integers in the imperative version depends on Java's semantics for % which I don't know by heart). In the recursive version, let $a_i$ and $b_i$ be the argument of the $i$th recursive call:
$$\begin{gather*}
  a_{i+1} = b_i \\
  b_{i+1} = a_i \mathbin{\mathrm{mod}} b_i \\
\end{gather*}$$

In the imperative version, let $a'_i$ and $b'_i$ be the values of the variables a and b at the beginning of the $i$th iteration of the loop.
$$\begin{gather*}
  a'_{i+1} = b'_i \\
  b'_{i+1} = a'_i \mathbin{\mathrm{mod}} b'_i \\
\end{gather*}$$

Notice a resemblance? Your imperative version and your recursive version are calculating exactly the same values. Furthermore, they both end at the same time, when $a_i=0$ (resp. $a'_i=0$), so they perform the same number of iterations. So algorithmically speaking, there is no difference between the two. Any difference will be a matter of implementation, highly dependent on the compiler, the hardware it runs on, and quite possibly the operating system and what other programs are running concurrently.

The recursive version makes only tail recursive calls. Most compilers for imperative languages do not optimize these, and so it is likely that the code they generate will waste a little time and memory constructing a stack frame at each iteration. With a compiler that optimizes tail calls (compilers for functional languages almost always do), the generated machine code may well be the same for both (assuming you harmonize those calls to abs).


Bus and System Clocks What is the difference between a Bus clock and a System Clock? Do they function the same way? I have been reading about System clocks but I can't really find anything about bus clocks in my book to compare the two.

In a simple computer architecture with a single active CPU connected to RAM and other passive peripherals by a bus, then there is a timing signal (typically produced by a quartz oscillator) that synchronises the internal operation of the CPU. This clock signal is the system clock.

There may also be a separate timing signal that synchronises the activities of writing to and reading from the bus. This is the bus clock. Because the speed at which data can be reliably transmitted across the bus may be lower than the internal speed at which the CPU runs, the bus clock signal is usually at a lower frequency than the system clock. The bus clock signal may be produced by passing the higher frequency system clock signal through a frequency divider.

In more complex architectures, where there are multiple active components (CPUs, FPUs, graphics cards, memory controllers, I/O controllers) running at different speeds, then the bus clock is often the fundamental synchronising signal, and each component then multiplies the frequency of the bus clock signal by a specific ratio to obtain its internal system clock signal.

For more details see https://anydifferencebetween.com/difference-between-system-clock-and-bus-clock/ and https://en.wikipedia.org/wiki/CPU_multiplier.


Is something more than Turing complete Turing complete? In complexity theory, we do not call a decision problem that is not in NP "NP-complete".

But in computability, do we call a machine model "Turing complete" if it can compute functions which Turing machines can not?

The definition from Wikipedia didn't address this problem explicitly, and likely assumed yes:

  A computational system that can compute every Turing-computable function is called Turing complete (or Turing powerful). Alternatively, such a system is one that can simulate a universal Turing machine.

For example, if there is a system that can:

Compute every Turing-computable function.
Compute the halting problem for a Turing machine.

And nothing else. Is it Turing complete?

Yes. The "complete" in NP-complete and in Turing-complete are two different notions.

For Turing-complete it means (as per the definition in the question) that the system can compute the complete (in the basic English sense) set of Turing computable functions (i.e. it can do at least everything a Turing Machine can).

For NP-complete, it's not obvious that the word has anything to do with its basic English meaning except perhaps in the tenuous sense that the problem has all the complexity inherent in the class, whatever that means.

Another way to express the difference is that NP-complete can be rephrased as "complete for the class NP", whereas Turing-complete does not mean "complete for the class R" (or RE).


how to prove that log(n!) >= c n log(n) for some c >0? as reading the book Algorithms by Dasgupta, C.H Papadimitriou.  on Page 63.

  And it is well known that $\log(n!)≥c\cdot n\cdot\log n$ for some $c > 0$. There are many ways to see this. The easiest is to notice that $n! \ge (n/2)^{(n/2)}$ because $n! = 1 · 2\cdot\cdots\cdot n$ contains at least $n/2$ factors larger than $n/2$; and to then take logs of both sides. Another is to recall Stirling’s formula.

Can someone help to find the proof on $n! \ge (n/2)^{(n/2)}$, or how should we prove it ourselves? As we take log on both side, it became
(assuming that its base is some number constant)  $\log(n!)$ on the left side,  on the right, it became $\log\left((n/2)^{(n/2)}\right)$, further simplify $(n/2)\log(n/2)$ --> $(n/2)\log(n^{-2})$, then finally on the right side: $(-n)\log(n)$. Then we completed the proof (?)

I have two questions, is the proof of $n! \ge (n/2)^{(n/2)}$ corrected?
If so, how can we argue back to   "$\log(n!)≥c\cdot n\cdot\log n$ for some $c > 0$",  if not, how can we proof that "$\log(n!)≥c\cdot n\cdot\log n$ for some $c > 0$"?

$n! = n \cdot (n-1) \cdot ... \cdot 1 \ge n \cdot (n-1) \cdot ... \cdot (n/2) \ge (n/2)^{(n/2)}$

so

$\log(n!)≥c\cdot n\cdot\log n$ for $c \ge 1/2$


Estimating the range of $1$'s in an array of $0$'s and $1$'s I have a large array $A$ that contains something like $[0..1..0..]$. It has a continuous range of $0$'s, followed by a range of $1$'s, and then another range of $0$'s.

This array is large and access is expensive, so I want to use a sampling algorithm to estimate the range $(i, j)$, where $A_i$ is the first $1$ and $A_j$ is the last $1$. Let's say I want to approximate this within an error of $\epsilon n$ where $n$ is the size of $A$, so that I get a range $(i', j')$ where $|i' - i| \leq \epsilon n$ and $|j' - j| \leq \epsilon n$.

What is an algorithm I can use to achieve this?

If c < 0.5 then this can't be done faster than O(n). Assume the array is all zeroes, with a single 1 somewhere in the middle. You have to examine array elements at least until you find the 1, or until you are left with an unexamined subarray of size 2cn. Since you have no clue where the 1 is, it might take n attempts to find a 1, and n - 2cn attempts until you can give a result with an error less than cn in i and j. (If you are left with an interval of size 2cn you just let i = j = middle of the interval).

Obviously if c >= 0.5 then you can let i = j = n/2, and the error is less than cn whatever the correct values are.


Smallest length such that all substrings of that length contain at least 1 common character Given a string, I have to return the smallest possible value of $k$ such that all of its sub-strings of length $k$ have at least one common character. Each sub-string must have the same common character.

Examples:

y d c b f

Answer = $3$ (common character is 'c')

n n n n n n n n n

Answer = $1$ (common character is 'n')

y e y d y e y

Answer = $2$ (common character is 'y')

The only solution I have thought of till now goes like this:

Find all sub-strings of length $x$ from $1$ through $n-1$ (where $n$ is the length of the given string).
Compare the sub-string for common characters (and store which characters are common). As soon as I come across a pair of the sub-string of length $x$ which doesn't have any common characters I move to the next value of $x$. If no such $x$ is found, return $n$.

Is a more efficient solution possible?

An equivalent formulation of your problem is:

  Given a string $S$ of length $n$, what is the minimal $k$ such that there exists an character $s\in S$ such that for all $i\in\{1,\ldots,n\}$, there exists a $j$ s.t. $|i-j|\leq k$ and $S[j]=s$. Report $k+1$.

Your approach seems to take $O(n^4)$ time in the worst case. If you try to see if the above formulation holds for all characters $s\in S$, you should be able to do it in $O(n)$:

Do a single linear scan trough $S$, while maintaining the last index you've seen each of the characters present in $S$ and the maximum gap size for each of those characters. After that, pick the character $s\in S$ with the smallest maximum gap size, this size is the value $k$. (Improved to a single pass thanks to @j_random_hacker's remark)

So, you can solve this problem in $O(n)$ time, which is a lot better than your initial approach. This approach is even asymptotically optimal, as we have to at least scan the entire string in the worst case, so we require at least $\Omega(n)$ time.


Understanding Gustafson's Law Wikipedia says about Gustafsons's law that:

  It may even be the case that $\alpha$ diminishes as $P$ (together with the problem size) increases.

I'm not understanding how $\alpha$ can ever change given it's definition:

$$ \alpha= a / (a + b)$$

I thought that $a$ and $b$ are constants independent of the problem size.

What am I missing?

First I suggest you to read the original article "Reevaluating Amdahl's Law" (CACM'1988) by John L. Gustafson when you have difficulty with the wiki article. Notice that I will use the notations from the original article: $s$ for serial time; $p$ for parallel time; $N$ for number of processors.

In the original article, the author mentioned that Amdahl's Law is based on an unrealistic assumption that "$p$ is independent of $N$", where $p$ is the amount of time spent (by a serial processor) on parts of the program that can be done in parallel.

Then, the author pointed out two key observations:

  In practice, the problem size scales with the number of processors.
  As a first approximation, we have found that it is the parallel or vector part of a program that scales with the problem size.

More explicitly, times for vector startup, program loading, serial bottlenecks and I/O that make up the $s$ (serial) component of the run do not grow with problem size; however, the amount of work that can be done in parallel varies linearly with the number of processors.

As a result, as $N$ (the number of processors; together with the problem size) increases, the portion of parallel time ($p$) increases according to the two observations given above, and the portion ($\alpha$) of serial time ($s$) diminishes (in most/common cases).


Total Number of Bits Needed to Represent a List of N elements This is an excerpt from the algorithms textbook How to Think About Algorithms by Jeff Edmonds (This book is a gem by the way).

I get his conclusion about Merge/Quick/Heap sorts having $O(NlogN)$ operations with respect to $N$, the number of elements in the input list, and at the same time they are linear in the context that they need $O(n)$ opertaions with respect to the number of bits needed to represent the input list. Different models of computation and a good way to describe one algorithm under different models.

But my question is in the line

  Assuming that the $N$ numbers to be sorted are distinct, each needs $logN$ bits to be represented, for a total of $n = \Theta(NlogN)$ bits.

My understanding of this was that with $N$ distinct numbers, we need word size $w = \theta(logN)$, as defined in CLRS. We want the word size to be able to at least index into $N$ different elements but not so big that we can put everything in one word. Also, with $N$ distinct elements, we need $\Omega(logN)$ bits to represent the largest number. Assuming each word will fit in $w$, Edmonds' claim that $n = \theta(NlogN)$ bits made sense. Please correct me if my analysis is wrong up to here.

But when I try to apply this to counting sort, something doesn't seem right. With $N$ again the number of elements in the input and $k$ the value of the maximum element in the list, the running time is $O(N + k)$. Counting sort is linear with respect to $N$, the number of elements in the input, when $k = O(N)$. Using this constraint to represent the input as the total number of bits $n$, I think $n = O(Nlogk) = O(NlogN)$.

So with in the RAM model of computation, how can I express the run-time of counting sort with respect to $n$ bits? Merge/quick/heap sorts had time complexity $O(n)$ with respect to $n$ bits, as was expressed cleanly by Edmonds. I am not sure how to do something similar for counting sort, and maybe possibly for radix sort using counting sort as a subroutine. Any idea how to do this in the two cases when $k = \Theta(N)$ and when this condition is not present? I am suspecting the former will give some kind of polynomial time with respect to $n$ and the latter exponential (hence pseudo-polynomial) time with respect to $n$ bits, but have trouble expressing the mathematics...

In the RAM model of computation, machine words are $\Theta(\log n)$ bits long (where $n$ is the size of the input in bits), and operations on machine words can be done in $O(1)$. Counting sort has running time $O(N + k)$ in the RAM model assuming that each value is $\Theta(\log n)$ bits long.

Let us now consider an array consisting of $N$ values, the maximal value of which is $k$. We would need $\log k$ bits to store each value. Assuming that we use $\Theta(\log k)$ bits per value, the input length is $n = \Theta(N\log k)$ bits, and so a machine word is $\log N + \log\log k + O(1)$ bits long. Let us denote by $w$ the number of machine words needed to store a single entry, which we can calculate by
$$ w = \left\lceil \frac{\log k}{\log N + \log\log k} \right\rceil = \Theta\left(\max\left(1,\frac{\log k}{\log N + \log\log k}\right)\right). $$
The running time of counting sort is $O(Nw + k)$.


Language grammar correction with supervised learning I want to work on automatic grammar correction using machine learning (possibly using recurrent or deep neural networks). The algorithm will be supplied with both corrected and initial documents for supervised learning.

I am now looking for some survey or research papers to start with. I have searched and downloaded tens of articles but none of them seems related.

I would appreciate if someone could provide a few good starting points (papers, books).
also I suspect that I am not using the correct keywords for my search. I'll appreciate if you could also suggest suitable search keywords.

The following paper from 2011 proposes a nice approach for using language modeling to do grammar correction, as well as an evaluation framework.

Park and Levy, Automated whole sentence grammar correction using a noisy channel model. In Proc. 49th Human Language Technologies, volume 1, pp. 934–944. Association for Computational Linguistics, 2011. (Available from the ACM Digital Library.)


Number of paths starting from a given edge using adjacency matrix I want to write the algorithm that takes the adgacency matrix of a directed connected graph without any cycles, then for each edge computes the number of paths starting from that edge. Also note that there is at most one edge between two nodes.
For example consider the graph depicted below:

For instance, we want to count the number of paths starting from edge $b$. They are: $b, bd, bdf, bdfg, bh$. So $F(q0, q2)=5$. ($F$ is the function that runs the counting algorithm). As another example $F(q4, q5)=2$.
Note that I want to count these paths for every two distinct nodes. So the output must be a matrix.
How should I write the algorithm? And what will be the complexity of that?

Note that counting the number of (non empty) paths starting from edge $(q_1, q_2)$ is the same as counting the number of (possibly empty) paths starting from vertex $q_2$. That way, the answer can be given as an array of size $|V|$ for a graph $G = (V, E)$ instead of a matrix of size $|V| \times |V|$.
Knowing that fact, here is an algorithm to compute this array $a$:

compute a topological sort $(v_1, …, v_n)$ of $G$ (this is possible because $G$ is supposed to be acyclic);
for $k$ from $n-1$ to $1$, set $a[v_k] = 1+\sum\limits_{v \text{ adjacent to }v_k} a[v]$, since $(v_k, v)\in E$, that means that $v$ appears after $v_k$ in the topological sort, so the value $a[v]$ has already been computed. Moreover, if the sum is empty, it means that $v_k$ is a sink node, meaning it has no exiting edge, so the only path is the empty path.

The algorithm has a total complexity $O(|V| + |E|)$, which is optimal.
Now, note that the complexity of the previous algorithm suppose you know the adjacency list of the graph $G$. If you only know the adjacency matrix of $G$, then I suggest you first compute the adjacency list of $G$ (time complexity $O(|V|^2)$).


Is it possible to make partition of Quicksort run in O(lg n)? I was thinking maybe I can make it 2T(n/2) + C split the list into two halves and work on them recursively to partition the list.

No.  The partition operation must access every item in the list: if there is any item it does not look at, then you don't know which side of the partition it belongs on.  Consequently, the partition operation cannot run any faster than $O(n)$ time, where $n$ is the length of the list.


Sub-Graph Isomorphism for graphs with multiple edge types and multiple node types I found that there are algorithms like VFlib and LAD filtering for subgraph isomorphism with one edge type. For multiple node types,one idea could be color all node types with the same type and use colored sub-graph isomorphism which is available for VFlib. I was wondering is there any algo specifically for multiple edge types or should I modify existing algo to check for edge types also?

You can replace each edge $(u,v)$ with two edges $(u,t_0)$ and $(t_0,v)$ where $t_0$ is a new vertex (a different one for each edge you replace), and then color the vertex $t_0$ based on the type of the edge $(u,v)$.


Which of $2^{\log_*n}$ and $\log\log n$ grows faster? Function 1: $2^{\log_*n}$

Function 2: $\log(\log n)$

The first function is 2 to the log-star of $n$, the second function is log of log of $n$.
What I need to know is which one is Big-Omega of the other one, which means, which one grows faster. How can I figure that out? I know the definition of log-star (iterative logarithm) but I don't know how to apply it in order to compare the given functions. Could you guys give some help?

Thank you in advance.

Consider $n_k=2^{2^{2^{\cdots}}}$, $k$ levels. Then $\log\log n_k = 2^{2^{2^{\cdots}}}$, $k-2$ levels, while $2^{\log^* n_k} = 2^k$. Does this help?


Mutual exclusion for n processes I want to implement mutual exclusion for $n$ processes. Critical section code:

int turn = 0;        /* shared control variable */

Pi:                  /* i is 0 or 1 */
while (turn != i)
   ;                 /* busy wait */
CSi;
turn = 1 - i;

This solution from this page but it is only made for two processes.

I tried to adapt it for $n$ processes like this:

turn = 0 // shared control variable

i = turn;

while (turn != i);

// CS

turn = (turn + 1) % n;

Does this work?

From my understanding of the 2-processor, if you want to do the same thing you would delete the statement (I truly dont know why you had it. There could be something interesting behind this statement of yours).

 i = turn

and instead, let each of the $n$ processors have an id from $\{1, \dots, n\}$. Then, you would let the processors go in sequence to the critical code. That is, assume a processor $i$ takes the token and left it. Then, it has to wait the other $n- 1$ to take the token if it want to take it again. The problem in this solution is the sequential method of taking the token.

If you want to have something more efficient, then have a look at the Lamport's bakery algorithm. The pseudocode of the algorithm is available in the site you provided, and it is explained in wikipedia. The idea of this algorithm is very simple in fact. There is a queue of processors that want to get the token. These processors enter the queue, and the first come is first served.

In regard to the link you included in your question, this is done by these lines:

number[i] = max(number) + 1;   // enter the queue !
...
...
while (number[j] != 0 && (number[j] < number[i] ||
                         number[j] == number[i] && j < i) )
// wait until your turn comes.
...
Do your critical section ! ...
...
 number[i] = 0;     // go out of the queue ..

Obviously, you can play around with this. But it is a neat way of implementing FIFO requests.


For any language $A$, there is $B$ such that $A \le _T B$ but $B \nleq _T A$ I am trying to come up with a proof for the following:

  For any language $A$, there exists a language $B$ such that $A \le_{\mathrm{T}} B$ but B $\nleq_{\mathrm{T}} A$.

I was thinking of letting $B$ be $A_{\mathrm{TM}}$, but I realize that not all languages are Turing reducible to $A_{\mathrm{TM}}$, so $A \le _T B$ would not hold.
What other choice of $B$ do I have that would allow me to write a TM which uses an oracle for $B$ to decide $A$?

Thanks!

Let $B=A'$, the Turing jump of $A$. This is a basic result in the theory of the Turing degrees.


Is this grammar LR(1) I am reading parser chapter from dragon book and I found a grammar over there -

$ S \rightarrow L=R $

$ S \rightarrow R $

$L \rightarrow *R $

$L \rightarrow id $

$R \rightarrow L $

Now I have created some of its items, not sure if they are correct -

$ I_{0} $

$S' \rightarrow .S  ; \$ $

$S \rightarrow .L=R ; \$ $

$S \rightarrow .R ; \$ $

$ L \rightarrow .*R; \$/= $

$ L \rightarrow .id; \$/= $

$ R \rightarrow .L; \$ $

$ I_{1} $

$ S' \rightarrow S.; \$ $

$ I_{2} $

$S \rightarrow L.=R ; \$ $

$ R \rightarrow L.; \$ $

Now I2 contains Shift reduce conflict but the lookahead symbol that is appearing is creating doubt I mean how $ can be lookahead symbol to shift = sign?

The grammar is LR(1) and LALR(1). It is not, however, SLR(1). The purpose of this example in the Dragon Book is to show a grammar which is LR(1) but not SLR(1).

The items that you've got so far are completely correct. To understand why state $I_2$ is deterministic, you have to understand what the parser has to do.

The parser has to choose between the following two items:

$S \rightarrow L \cdot = R; \{ \$ \} $

$R \rightarrow L \cdot ; \{ \$ \} $

The first one is a shift of a $=$ symbol which will transfer you to a state with the kernel item $S \rightarrow L = \cdot R; \{ \$ \}$. The second one is a reduce which reduces by the production $R \rightarrow L$.

The lookahead set is what the parser expects to see after it has read the whole production, but the dot indicates what the parser expects to see right now. In the case of the first item, it expects to see $=$, then $R$, then $\$$. When constructing the parser actions, the symbol that you're looking for to do the shift is $=$, because that is the symbol which is shifted.

If the second item's lookahead set contained the symbol $=$, then the shift-reduce conflict would not be resolvable and the grammar would not be LR(1), because it would not be clear which direction to take if the next symbol were $=$.

As it is, the state is deterministic. If the next symbol is $=$, shift it and take the first item. If the next symbol is $\$$, reduce.

(Warning: The rest of of this is a slight digression.)

As well as deriving the machine by hand, I fed the grammar into a parser generator (I used yacc, you could use Bison, ANTLR etc) just to be certain. If you do this, then you should be aware that production-quality parser generators sometimes take a shortcut by not consulting the lookahead symbol on reduction if they don't have to.

In this case, if you found yourself in state $I_2$ and the next symbol was $id$, then you may as well reduce, even though you could have detected a syntax error at this point.

There are three main reasons for this.

First, you don't have to check, since the error will eventually be detected when you try to shift the $id$ symbol. Remember, even the LR(0) machine is correct for this grammar, it's just nondeterministic; what we call a "conflict" in LR-speak we would call "nondeterminism" in other kinds of automata. If the decision is already deterministic, using lookahead information doesn't make it more deterministic.

Second, it's expensive to store and check the lookahead set. Even though computers are big these days, smaller is still better. Saving space is good.

Third, and perhaps most importantly these days, in real parsers, you need to report the syntax error to the user in a way that helps them understand what went wrong. The "bigger" the concept that you can use in the report (e.g. "expression" rather than "lvalue"), the more understandable it is. Reducing before reporting helps with this.

So if you feed this grammar into a production parser generator like ANTLR, Bison, or YACC, you will find that the actions for this state basically say "if you see $=$ then shift and go to state X, otherwise reduce". If you were wondering why they don't consult the lookahead set, that's why.

(Digression ends.)


Number of strings accepted by this regular expression This was a question that I got while taking a test at our university. The question paper was taken away after the exams. I remember the question only, not the multiple choices.

If a regular expression is of the form (x+y)*y(a+ab)* , then what is the maximum number of strings with length 4 will bee accepted by its language?

I've tried simplifying the expression, or drawing FSM diagrams but can't figure it out. A little help would be appreciated.

Thank you!

NOTE: I'm assuming + is the union operation, as used here, rather than the Kleene plus or a terminal symbol.

The first step is breaking this RE into three parts: (x+y)*, y, and (a+ab)*. Now consider, how many ways can we make something with less than four characters from each of these?

(x+y)*: one of length 0, two of length 1, four of length 2, eight of length 3
y: one of length 1
(a+ab)*: one of length 0, one of length 1, two of length 2 (aa, ab), three of length 3 (aaa, aab, aba)

Now, how could you combine these to get length 4?

0 from the first (1), 1 from the second (1), 3 from the third (3)
1 from the first (2), 1 from the second (1), 2 from the third (2)
2 from the first (4), 1 from the second (1), 1 from the third (1)
3 from the first (8), 1 from the second (1), 0 from the third (1)

For each of those, multiply the number of possibilities. Taking 1 from the first, 1 from the second, and 2 from the third, for instance, gives 2×1×2=4 possibilities.

The sum of these is the total number of length-4 strings matched by this RE: (1)(1)(3)+(2)(1)(2)+(4)(1)(1)+(8)(1)(1) = 3+4+4+8 = 19.


How to use an old SAT solver to discover a new one, as is done in The Golden Ticket? In Lance Fortnow's book The Golden Ticket, he mentions that once you have a polynomial-time algorithm for an NP-complete problem, you can use it to find a faster algorithm. Can you tell me how that is done? And once that is done, you can use the new algorithm to discover an even faster one ad infinitum, till a fixed point. Below is the exact quote from the book:

  "So what do you ask a genie who will grant you only one wish?" said
  the adviser.

  "I have no idea," replied Steve.

  "You ask for a genie who will grant all your wishes."

  The proverbial light bulb went off in Steve's head. He knew there must
  be some better algorithm for solving clique problems out there
  somewhere, but he couldn't figure it out on his own. But he had the
  genie, the Tsinghua code, which could search an exponential number of
  possibilities quickly. So he wrote up a program that used the
  Tsinghua routines to search for a better algorithm for NP problems.
  He got permission to use the computing resources of the National
  Center for Supercomputing Applications (NCSA), based at the University
  of Illinois. After weeks of processing time his work paid off a little
  bit, finding a new algorithm that had a 5 percent improvement over the
  Tsinghua code--good enough for a research paper but not enough to make
  a real impact.

  His adviser simply said, "Try again using the new code."

  So Steve used his new code to find an even faster algorithm for NP
  problems. A few weeks later he had a 20 percent improvement.

  But his adviser was not impressed. "Try it again."

  Steve replied, "Why don't I just set up the computer to automatically
  keep trying with the new code it finds?"

  The adviser gave that look, the look that told a student he had
  achieved enlightenment, or at least had realized the obvious.

  Steve went back to his office and started the tricky process of
  writing code that searches for faster code, and then used this faster
  code to find even faster code and continue this process until it could
  find no further improvement.

Now focus on SAT. MiniSAT is a fast SAT solver, though not to the point of being polynomial-time.

  How to use MiniSAT to mechanically discover a new SAT solver?

Actually, probably you can't use a SAT solver to find another SAT solver, unless something surprising happens.

If P = NP, then you can.  If P = NP, then the polynomial hierarchy collapses (i.e., P = PH), so there is a polynomial-time algorithm for every problem in PH.  The problem of asking whether there is a faster SAT solving algorithm is essentially a $\Sigma_2$ problem, which is part of the polynomial hierarchy; if the polynomial hierarchy collapses, there's a polynomial-time algorithm for every problem in PH and thus for every problem in $\Sigma_2$.  Thus you can in polynomial time search for a better SAT solver, if P = NP.

But most researchers expect that P is not equal to NP, so this statement is most likely moot and unlikely to be helpful in practice.

If P is not equal to NP, then this reasoning doesn't work.  In fact, many researchers expect that $\Sigma_2$ is even harder than NP (there are problems in $\Sigma_2$ that are harder than any problem in NP), so it would be surprising if there was a simple reduction to express the problem "find me a faster SAT solver" as an instance of SAT.  In particular, SAT solvers can solve SAT, or any other problem in NP -- but in any case, only problems in NP.  If (as we suspect) $\Sigma_2$ is harder than NP, then SAT solvers can't solve problems in $\Sigma_2$.

Of course, we don't actually know.  It's always possible that the conventional wisdom is wrong, and that tomorrow we discover that P is actually equal to NP.  That would be a great surprise, but we can't completely rule it out.

The Golden Ticket is trying to give a deeper understanding of why complexity theorists consider the P vs NP problem so important and so fundamental.  Part of that involves exploring counterfactual worlds and counterfactual assumptions that we suspect are probably false, to see what their consequences would be.

Or, to explain it a different way:

The problem is that finding a better SAT solver is a $\exists \forall $ kind of statement.  The statement is of the form $\exists A \forall x . P(A,x)$, where $P(A,x)$ is the statement that $A$ is fast and correctly solves the SAT instance $x$.  Those kinds of statements can't be solved with a SAT solver.  SAT solvers can solve problems of the form $\exists x. Q(x)$.  However, $\exists \forall$ statements are harder than $\exists$ statements.  This is basically the difference between $\Sigma_2$ and NP.


NP-completeness of triangle removal problem Triangle removal problem states that, given an undirected graph G, can you pick a subset
S of vertices such that removing S will remove all triangles from the old graph and |S| <= k. I was trying to use reduce from vertex cover problem, but every construction I attempted has failed. Here's what I've done:

1) Add extra edges to the graph such that every pair of distinct vertices is connected by an edge (In other words, create a complete graph Kn)

2) Create a subgraph of G, but only composed of vertices with degree at least 2 from the original graph

I found a counter example for each construction, and I can't fully grasp the starting point. The goal is that I want to build some graph out of an old graph such that the every triangle should use at least one vertex in S(solution returned by black box for "triangle removal problem"), but it has to be a vertex  cover for the old graph at the same time. How should I approach this?

Edit:
Current attempt - for every existing edge (u,v) in E in a graph, add a new vertex w and add two new edges (u,w) and (w,v) so that it forms a triangle

Your current attempt (at the time of writing this answer at least) is on the right track, it just needs one more step.

To help understand one way of relating the problems to each other, consider the following alternative way of defining a vertex cover; a vertex cover is a set of vertices whose removal leaves a disconnected graph.

So Vertex Cover is the problem of selecting vertices to remove that gets rid of all edges, whereas your problem is selecting vertices to get rid of triangles.

Thus to convert Vertex Cover to Triangle Removal we need to turn edges in the original graph intro triangles in the new graph (or at least, one sensible way - there could be many reductions).

Hence your construction of adding a vertex for every edge in the graph and making a triangle is heading in the right direction, the only problem is that we could remove the new vertices, and that may mess up our answer (it certainly makes it harder to argue about what the vertex cover should be in the original graph). What we need is a way of preventing the added vertices being selected for removal. To do this, instead of adding a single new vertex, add $k+1$ new vertices!

More precisely (but not completely precisely), given $G$ we construct $G'$ as follows:

For every vertex $v \in V(G)$, there is a vertex $v' \in V(G')$
For every edge $uv \in E(G)$, there is an edge $u'v' \in E(G')$.
For every edge $uv \in E(G)$, there are $k+1$ vertices $\{w_{1},\ldots,w_{k+1}\} \subseteq V(G')$ with the edges $u'w_{i}$ and $v'w_{i}$ in $E(G')$ for all $i$.

I won't go through the full proof that this works, but the general gist is that if we want to get rid of all the triangles attached to $u'v'$, it doesn't really help to take any of the $w_{i}$ vertices as there are too many of them, we eventually have to take at least one of $u'$ or $v'$, but once we take one of those, it deals with all the triangles, so any answer that takes a $w_{i}$ vertex must also take $u'$ or $v'$ (or both) and can be replaced by a smaller solution that takes only $u'$ or $v'$ (or both), so we only have to consider solutions of that form, but then we're basically done - as each edge has triangles, one of the two "original" vertices must be in the triangle removing solution for each edge, and hence is also a vertex cover.

Really you can make the same argument with your construction, but the additional vertices force things and make the argument clearer (you don't have to deal with arguing for alternative solutions and vertex swapping etc. etc.)


Finding issues in concurrent implementation of carpark overflow control Firstly, I am revising for my Concurrent Programming exam and have come across the following question from a previous exam paper. I have attempted to answer it, and will try and convey this effort; I'm very stuck with this question and not sure how to further progress.

Question

This question is from a 2011 Past Paper from my University created by the Examining Body that year.
Examiners: Professor E K Burke
Dr P Sage
and the internal examiners

  A car park has 100 parking spaces. Because of building work max cars must be accommodated in an overflow area which is accessed via the main car park. Entrance to the main and overflow areas is controlled by two automatic barriers as follows.

  When the car park is empty both barriers are closed.
  Normally, the main barrier is raised as a car approaches and is lowered immediately the car has entered.
  An exception occurs immediately after the main car park is full i.e. when it has 100-max cars in it. As the next car approaches the overflow barrier is raised first, then the main barrier is raised. Once the car has entered the main car park the overflow barrier remains raised and the main barrier is lowered. The normal main barrier action described above then resumes.

  Consider the following program which is intended to control the two barriers.

  All instructions, o1, o2, o3, m1, m2, m3 and m4, are atomic. You may assume that $0 < \max \leq 100$.

int #cars=0;

process Main {
while (true)
 {
 m1: <#cars++>;
 m2: <openMainBarrier>;
 m3: <closeMainBarrier>;
 m4: <if (#cars==100)
     break>;
 }
}

process Overflow {
int max;
o1: <input(max)>;
 while (true)
 {
   o2: <if (#cars==100-max+1)  break>;
   o3: <openOverflowBarrier>;
 }
}

  The program terminates only if both processes terminate. Explain why the program may not terminate.
  Explain why, even if the program does terminate, it may not operate as specified.
  By introducing the use of semaphores, ensure that program does terminate and operates as specified. You must only use atomic instructions. You may introduce new additional non-semaphore variables but you must not alter the scope of #cars and max.

My attempt

Most semaphore exercises I have looked at so far often have the main process in a while(true){...} infinite loop, thus, termination has never been an issue before - it is normally not addressed in these short exercises.

It is because of this I am having difficulty trying to produce an answer for 2) and 3). The question does not even appear to address cars leaving the car park, which leads me to understand this isn't an infinite ongoing cycle type process, but will terminate when both car parks reach maximum capacity?

In this instance, the only thing I can think of is that the process will not terminate in the event the main carpark or overflow carpark does not reach capacity, however I feel this answer is not 'clever' enough and I'm worried I may be missing something.

I have attempted 3) as follows but I am worried this is incorrect as I'm not sure if I am supposed to handle cars leaving the car park, or if I am supposed to ignore that in order to force it to terminate.

OverflowCarPark{
int max;
<input (max)>
while(true){
 down(maxFull)
 if(#cars <= 100 + max){
    down(openMainBarrier)
    up(openOverflowBarrier)
 }
  else { break; }
}

MainCarPark{
<cars++;>
while(true){
 if(#cars <= 100){
    up(openMainBarrier)
  } else if (#cars > 100 + max) { break;
  } else {
    up(maxFull);
    down(openOverflowBarrier);
 }
}

What is the recommended approach to dealing with termination here?

For the first task think about what might happen, if the loop in Overflow is not run for each car.

For the second task, look at the following things:

How is the opening and closing of bars linked to arriving cars?
Does the overflow bar really open at the $100-\max$-th car?
The specification requests a specific order of opening and closing the bars. Is this enforced?

In the third task you should address the problems identified in the first two tasks by adding semaphores and possibly additional variables and atomic operations to the code.

Concerning your attempt and the questions therein:

The setting as described assumes that no car leaves the car park.
You may assume that eventually 100 cars will have arrived. (Otherwise you could not ensure termination.)
You should mostly keep the operations m1-m4 and o1-o3 (depending on your approach you might change one or two of them). Just add additional code around and inbetween them, in order to address the problems.
You use $100+\max$ twice, where you probably intended to use $100-\max$.
Using max in Process Main is changing its scope, since in the original code it is a variable local to Process Overflow.
Also your code does not solve most of the problems I hinted at for task 2. (This is no surprise, given that you had not identified them, when writing the code.)


Big O Notation Explained Our teacher gave us the following definition of Big O notation:

O(f(n)): A function g(n) is in O(f(n)) (“big O of f(n)”) if there exist
constants c > 0 and N such that |g(n)| ≤ c |f(n)| for all n > N.
I'm trying to tease apart the various components of this definition. First of all, I'm confused by what it means for g(n) to be in O(f(n)). What does in mean?

Next, I'm confused by the overall second portion of the statement. Why does saying that the absolute value of g(n) less than or equal f(n) for all n > N mean anything about Big O Notation?

My general intuition for what Big O Notation means is that it is a way to describe the runtime of an algorithm. For example, if bubble sort runs in O(n^2) in the worst case, this means that it takes the time of n^2 operations (in this case comparisons) to complete the algorithm. I don't see how this intuition follows from the above definition.

O(f(n)) means the family of function of f(n), a family of function for example could be {n^2, 3*n^2, 6*n^2, ...k*n^2}, for g(n) to be in the O(f(n)), it means that g(n) is less than all elements of f(n) in the long run. In the above example, it could be g(n) = n, versus O(f(n)) = O(n^2), obviously, n^2 is bigger than n for all n in the long run.

Absolute value sign compares the absolute values of these two functions so that even if g(n) is negative, we can compare which negative grows faster i.e. -n^2 grows faster than -n is equivalent to n^2 grows faster than n

n>N means in the long run

Bubble sort runs O(n^2) in the worst case means that Bubble sort can run much faster than O(n^2), but it does not exceed O(n^2). For example, we want to sort two elements {2,1} using bubble sort, obviously this takes 1 operation and that's it, 1 is smaller than n^2.


How come Datagram Packets between same source-destination pair may take different routes? This might be a rookie question, but I wanted to understand the following line.

My book says, each time a host wants to send a packet, it places the address of the destination host in the packet's header. Okay, I understand this.

Also, packets forwarded using destination address have their address mapped to an outgoing interface. Packets between same source destination pair may take different routes.

Why is that? If packets have the same destination address should they not be mapped to the same outgoing interface?

Is there something I have left out or not understood that is leading to this confusion or is there an explanation to this!

Packets are routed individually: each time a router receives a packet, it decides what to do with that packet. It doesn't necessarily make the same decision each time it receives packets for a particular destination. To give a trivial example, somebody might have changed the router's configuration in the time between two packets arriving; a more common example would be a router trying to avoid congested links by sending some packets down a quieter link.


Floating Point Arithmetic with 3 bits mantissa Find all values of $ x ∈ R $ such that x + 1 = 1 in floating point arithmetic with 3 bits mantissa.
How do we represent number 1 in floating point arithmetic with 3 bits mantissa I wonder? After that, I think we can subtract 1 on both side? I am a little confused about representations of numbers in floating point arithmetic with a specific number of bits in mantissa.

The problem is underspecified, but I'll assume IEEE 754 default behavior.
In IEEE 754, at least in space-constrained floating-point formats, a bit is saved by not storing the leading bit of the mantissa, which is always 1. So the representation of the number 1 would have 000 in the three mantissa bits.
The next largest representable number is 1.001 in binary (001 in the mantissa bits). The next smallest representable number I'll leave for you to figure out (it's not 0.111).
In IEEE 754, addition works by calculating the exact sum of the addends over the reals (infinite precision), then rounding to a representable floating-point number. In the default mode (round to even), you round to the nearest representable value, or if you're exactly halfway between representable values, the tie is broken in favor of the one with 0 in the least significant mantissa bit.
If $a$ is the next smallest representable number below 1, and $b$ is 1.001, then sums in the interval $\left[\frac{a+1}2, \frac{1+b}2\right]$ will be rounded to 1. (It's closed on both ends because round-to-even breaks the tie in favor of 1.) From there it's easy to answer the question.