Running an algorithm on data remotely and ensuring answer has not been tampered with I´ve been thinking about this particular computing/crypto/database problem for years and I just want to know if there are already solutions to it. To be honest I don´t even know what field this problem belongs to exactly.

In a nutshell: person A has a list of data, another person (B) has an algorithm that gives each item on this list a score and then sums all these scores to provide an overall score for the whole list. How can we run the algorithm on the data list so that the data is kept extremely secure (preferably never leaving person A) but so that person B can be certain the algorithm ran properly and was not tampered with.

Here is an example: Anna and Bob live in a large village. Anna has a list on her computer of all the things she has done in the village, both good and bad. Bob has made a very simple scoring algorithm for such lists, which runs on each item on the list and gives it a score and then adds all these numbers up to give Anna a final score. This score lets Bob know how beneficial Anna is to the village community and is specific to Bobs opinion. (This is more than an example as this is actually the system I want to make)

However Anna does not want to give Bob her list, as then he has access to potentially embarrasing info in there (everyone has skeletons in thier closet). Bob however does not trust Anna to run his algorithms herself, as she may just lie and tell Bob the score was very high so that Bob is more likely to help her.

There are a few solutions I have already thought of, but all have problems:

A. Find a random person to take the data and run the algorithm and send the score back, but it may be difficult to ensure that this random person do not know Anna and try to help her or make a copy of the data and later try to trace it back and blackmail Anna.

B. Let Anna run the algorithm but somehow encode a check code into the scores, for example, instead of rating an event as 1 rate it as 1.0000000000797, in such a way that Bob can later use this as a checkcode to see if the given score is correct. However this check could also be misused by Bob to indicate what specific things Anna has done. Also I can imagine such a system would be trivial to reverse engineer so that Anna can give a false score with a correct checkcode, considering that Anna must have full access to Bob´s algorithm to run it.

C. The village creates a secure server to take such data and algorithms and run them together. However Anna and Bob both don´t really trust anyone enough to do this and not make a copy of the data or modify the scores, unless there is some fundamentally secure architecture for doing so. Also I would prefer this to be a P2P system.

In the crypto community, this task is known as delegated computation, or verifiable delegation. You wish to let the server (the "cloud") to do the work for you, but you also want the cloud to give you some proof that it actually performed the computation (and didn't just output a random output, and ran away with your money).

A pointer, off the top of my head, is "Delegating computation: interactive proofs for muggles" (Goldwasser, Kalai, and Rothblum, J. ACM (62), 2015). Other solutions probably exist, look inside.


Worst-case expected running time for Randomized Permutation Algorithm I have an algorithm which, when given a positive integer N, generates a permutation of the first N integers (from 1 to N) using a method called randInt(x,y). The method randInt(x,y) will generate a random integer between the numbers x and y, provided they are positive integers and y >= x.

The algorithm is given by the following pseudo-code:

1.  if (N <= 0) {
2.     return null
3.  } else {
4.     A := new int[] w/ size N and all cells initialized to 0
5.     a[0] := randInt(1,N)
6.     for (i := 1 to length(A)-1) do
7.        boolean rInA := True
8.        while (rInA) {
9.           rInA := False
10.          int r := randInt(1,N)
11.          for (j := 0 to (i-1)) do
12.             if (r = A[j]) {
13.                rInA := True
14.             }
15.          }
16.       }
17.       A[i] := r
18.    }
19. }
20. return A

My understanding of the algorithm is as follows:

The outermost for-loop will run N-1 times and for each of those iterations a random number is generated and then compared to all the previous cells of A that have been visited in previous iterations. If any of the those cells contain that randomly generated number then that number cannot be used and a new number is randomly generated (in the next iteration of that nested while-loop). This new randomly generated number is then, like before, compared to all the previously visited cells in A to check for duplication. This continues until randInt(x,y) generates a random number that is not already in the first i cells of A.

This leads me to believe that the Worst-case expected running time of the algorithm is something like:
$\sum_{i=1}^{N-1}(\alpha i)$

Now the $\alpha$ here represents the effect the while-loop has on the running time and is the point of uncertainty for me. I know that in the first iteration of the outermost for loop its unlikely that randInt will generate the one integer that A already contains (1/N I believe) so that inner-most for-loop is likely to only execute once. However, by the last iteration (of outer-most for-loop) the probability that randInt generates one of the N-1 integers already in A is $\frac{N-1}{N}$ so because of the while-loop its likely that the inner-most for-loop for that iteration (of the outer-most for-loop) will execute more like n times.

How can I use the probability introduced into the algorithm by randInt to calculate the algorithms run-time?

Firstly I would revise the inner for loop so that checking whether $r$ has been used already, is $O(1)$. As stated, it is $O(n)$.  You could do this by initializing a (1-indexed) boolean array $used[\cdot]$ of length $n$, and setting $used[x]$ equals true whenever you set some $A[i]=x$.

Now the question is how many times may $rand()$ be called in the worst case. Actually, the way the algorithm is set up right now, the worst case is $+\infty$; this is because it's not learning from any of its bad choices of $r$. For instance, if it selects $5$, when $5$ was already in $A$, then the smart thing to do would be never to guess $5$ again. There are ways to achieve this; so if you had some method that never repeated guesses, then you can get $O(n^2)$ worst case runtime.

If you are interested in expected runtime, then you can calculate the expected number of times $r$ is recalculated in any given step: at step $i$, there are $n-i$ good choices, for a success probability of $\frac{n-i}{n}$. The expectation for number of tries to get a first success in a bernoulli variable with probability $p$, is $\frac{1}{p}$. Then if you sum $\frac{n}{n}+\frac{n}{n-1}+\frac{n}{n-2}+\cdots \frac{n}{1}$ you have asymptotic $O(n\log n)$.  This is basically the coupon collector's problem.


Expected weight of euclidean minimum spanning tree on a unit square Suppose I randomly generate $n$ points from the unit square $[0,1]^2$, form a complete graph in which the weight of each edge is just the Euclidean distance between its endpoints, and compute the minimum spanning tree. I noticed empirically that the expected weight scales like $\sqrt{n}$. Using only back of the envelope arguments, how could I derive the $\sqrt{n}$ asymptotic behavior?

When I repeated the experiment in the unit cube $[0,1]^3$, the expected weight scaled like $n^{2/3}$, and when I repeated it on the unit hypercube $[0,1]^4$, the expected weight scaled like $n^{3/4}$. How could I derive this asymptotic behavior?

The following is based on J. Michael Steele's paper proving the rigorous bound.

The pigeonhole principle shows that out of any $n$ points in $[0,1]^d$, there are two at distance at most $O(n^{1/d})$, say at most $c_d n^{1/d}$; the idea is to divide $[0,1]^d$ into small enough boxes, and find a box containing two points. Construct a spanning tree by repeatedly adding an edge corresponding to the two closest points and throwing out one of them. This spanning tree has cost at most
$$
c_d (n^{1/d} + (n-1)^{1/d} + \cdots + 2^{1/d}) \leq c_d \int_2^{n+1} x^{1/d} \, dx = O(n^{(d-1)/d}).
$$

For the lower bound, a similar argument dividing $[0,1]^d$ into small boxes shows that for any $\epsilon > 0$, with probability $1-\epsilon$ there are only $\epsilon n$ many edges whose weight is $O_\epsilon(n^{1/d})$, and so with constant probability any spanning tree has cost $\Omega_\epsilon(n^{(d-1)/d})$. With more work, it follows that the expected weight of a minimum spanning tree is $\Omega(n^{(d-1)/d})$.


Sampling perfect matching uniformly at random Suppose I have a graph $G$ with $M(G)$ the (unknown) set of perfect matchings of $G$. Suppose this set is non-empty, then how difficult is it to sample uniformly at random from $M(G)$? What if I am okay with a distribution that is close to uniform, but not quite uniform, then is there an efficient algorithm?

There is a classical paper of Jerrum and Sinclair (1989) on sampling perfect matchings from dense graphs. Another classical paper of Jerrum, Sinclair and Vigoda (2004; pdf) discusses sampling perfect matchings from bipartite graphs.

Both these papers uses rapidly mixing Markov chains, and so the samples are only almost uniform. I imagine that uniform sampling is difficult.


Basic Myhill-Nerode Theorem Practice I wanted to understand the Myhill-Nerode Theorem so I made up a small example to do so.

  L = (a $+$ b )

Clearly, this language is regular. So, I should be able to establish a finite number of equivalence classes by using this method.

I start with a suffix of length 0, which is only $\lambda$:

a$\lambda$ = a $\in$ L
b$\lambda$ = b $\in$ L

For all suffix strings of length $\nu \gt 0$, both are not elements of L.
Therefore, there are no distinguishable strings. I suspect this means there are 0 equivalence classes, and since 0 is a finite number, the language is regular. What might be missing from this analysis?

Note: I made sure to do some online research already and feel comfortable with the ideas of distinguishable strings. The equivalence class bit is what I probably need some clarification on.

What you show is that $a$ and $b$ belong to the same equivalence class. Indeed, in this case there are exactly three equivalence classes: $\{\lambda\}$, $\{a,b\}$, and $\{ w : |w| \geq 2 \}$ (that's assuming the alphabet is $\{a,b\}$). I'll leave it as an exercise to prove that.

The Myhill–Nerode equivalence classes are intimately related to the minimal DFA. Indeed, given the minimal DFA, the number of equivalence classes equals the number of states, and each equivalence class consists of all strings which end up at that state. That's the quickest way to find the equivalence classes in simple cases such as $a+b$.


Do I have the right definition of VC dimension? I am having some trouble understanding the notion of the VC dimension. The definition I have is the following:

  The VC dimension of a set of hypothesis functions $H$ is the cardinality of the largest set which $H$ can shatter. We say that $H$ shatters some set $S \subseteq \mathcal{X}$ if we can realise any labelings on $S$ using functions from $H$.

To me, this means that for any (countable) set of labels $L \subseteq \mathbb{Z}$, there is some $h \in H$ that provides a surjection $h: S \mapsto T$, where $T \subseteq \mathcal{X}$ with $|T| = |L| \leq |S|$. (There is then a trivial bijection from $T$ to $L$.)

Is this the correct interpretation?

The reason I ask is because the above interpretation leads me to think that the singleton set $H = \{h\}$ has $VC(H) = 1$, since it always sends a single point to a single point, so we can get any labelling we like on this single point by a trivial bijection.

That is, suppose we wanted to label the point $x \in \mathbb{R}$ as $l$, then $h: y \in \mathbb{R} \mapsto 0$ will do since we can just change the name of 0 to $l$. Note that this chosen $h$ does not shatter a two-set from $\mathbb{R}$, since we can only label the points in one distinct way.

However, I have read that the VC of a singleton is 0. I don't understand this.

(I see hypothesis functions $g: \mathcal{X} \to \{1, \dots, n\}$ as belonging to an equivalence class of functions that sends $\mathcal{X}$ to any set of size $n$. Please correct me if this is the wrong intuition.)

A family of hypothesis functions on domain $\cal X$ is a subset of $\{0,1\}^{\cal X}$. A family $H$ shatters a set $S \subseteq \cal X$ if for every subset $T \subseteq S$ there exists a function $h \in H$ such that $h(s) = 1_{s \in T}$ for all $s \in S$, that is, $h(s) = 1$ if $s \in T$ and $h(s) = 0$ if $s \in S \setminus T$.

A singleton family $H$ cannot shatter any non-empty set $S$. Indeed, suppose that $H = \{h\}$ shatters $S \neq \emptyset$, and take any $s \in S$. Taking $T = \emptyset$, we see that $h(s) = 0$, whereas taking $T = S$, we see that $h(s) = 1$.


reduction of independence problem and cluster problem independent problem is: there is a simple and undirected graph, we are looking for the maximum vertex in which there is no edge between any two of them.
cluster problem is: there is a simple and undirected graph, we are looking for the maximum number of the vertex in which there are proximity every two vertexes ( there is an edge between any two vertexes)
how can I reduct independent problem to cluster problem and vise versa?

If i understand your question correctly, given $G$, build a graph $G'$ where $V(G)=V(G')$ and for every $v,u\in V(G)$, $(v,u)\in E(G')\iff(v,u)\notin E(G)$


What happens if we expand the alphabet of a given Turing Machine? If we expanded the alphabet Sigma = { 0, 1, u, > } to Sigma' = { 0, 1, 2, u, > }.    How would the table change?     We're just learning about Turing Machines in class and I'm a bit confused. Is the table in the picture calculated in some way?

That’s a table of transitions, and it determines what the program does when it encounters a given symbol on its tape while in a given state.  This program, if I’m reading it right, accepts strings containing two consecutive 1 symbols before the first space.

If there were another symbol, it would be necessary to define what the program would do on encountering them.  For example, to ignore them, there would be a pair of transitions saying that, if the program is in state s1 and reads a 2, it should stay in state s1 and move to the right, and that if it is in state s2 and reads a 2, it should stay in state s2 and move to the right.


Using finite state machines for lexical analysis I'm a high school student and I'm passionate about everything language related - lexers, parsers, compilers, interpreters and so on. Some time ago I've written a calculator in Python (now willing to use a better language), which uses the Shunting yard algorithm and my own lexer.
So I want to start learning more about this topic and found this Compilers course. I pretty much understand how RegExp are used to specify the language but when the professor started talking about finite-state machines I just got lost in all the theory.
So this is my question: How do I use DFAs and NFAs for lexical analysis ?
What does "state" mean in this context ?

The goal of any parser is to verify that a sequence of characters is a string in a specific language [C, Python, whatever].  In principle, the parser can be written to inspect each character in the sequence directly, but the parser will be more comprehensible and efficient if built to inspect higher-level lexical tokens - names, numbers, quoted-strings, miscellaneous operator symbols, parentheses, etc.  This is where the scanner comes in.  The scanner is essentially a subroutine which the parser calls to read the raw character stream and extract & return the next lexical token.

The scanner is implemented as a DFA which recognizes any token.  Each token type has its own structure as a character sub-sequence, representable as a regular expression which in turn is translated to a simple DFA; for example: a name is (in most languages) a sequence of characters consisting of [letter] followed by zero or more [letter or digit].  The scanner combines the simple DFAs for these expressions into a single DFA for their union.  This is (conceptually) implemented as a simple two-dimensional table, where rows are indexed by character values and columns are indexed by DFA state numbers (actually the rows are usually indexed by character classes - e.g 'letter' instead of 'a', 'b', ...).

Each call to the scanner follows this process: Begin in a common start state (e.g 0), looking at the next character [in the I/O buffer].  Using the lookup table, calculate the next state and 'consume' the next character [typically this means copying the character into the next slot in a buffer].  Repeat until a final state is reached, then return an object identifying the type of lexical token and the value from the buffer.  Example: Suppose the scanner is called when the next few characters are 'foo '.  The machine will move from state 0 to state (say) 11 and copy 'f' to the buffer; then move from state 11 back to state 11 and copy 'o' to the buffer - twice (two 'o'-s); then seeing the space it will move to some final state (say) 12, and return from the call, returning the object [type = NAME, value = 'foo'].  The next call to the scanner will begin where the last ended, looking at that space.

Most scanners do a bit more than this, of course.  In languages with reserved words, when the scanner finishes reading the name, it will typically look up the name in a table of reserved words; if found, it will return an object representing that specific reserved word instead of a generic 'name' object.  The scanner will usually 'eat' all contiguous whitespace without returning any token; similarly for comment text.  And so on and so forth....


Prim's algorithm on graph with weights of only $1$ and $2$ on each edge I have this version of  Prim's algorithm

Prim$(G=(V,E),s\in V,w)\\
1.\ d(s)\leftarrow  0;\forall u \neq s:d(u)\leftarrow \infty\quad \color{red}{O(|V|)}\\
2.\ \forall u \in V:p(u)\leftarrow \text{null}\quad \color{red}{O(|V|)}\\
3.\ s\leftarrow \emptyset,T\leftarrow \emptyset\quad \color{red}{O(1)}\\
4.\ Q \leftarrow \text{Makeheap}(V)\quad \color{red}{O(|V|)}\\
5.\ \text{while}\ Q\neq \emptyset\\
6.\qquad u\leftarrow Q.\text{ExtractMin()}\quad \color{red}{O(\log(|V|))}\\
7.\qquad S\leftarrow S\cup\{u\},\ T\leftarrow T\cup\{(u,p(u))\}\quad \color{red}{O(1)}\\
8.\qquad \text{for each}\ (u,z)\in E,z\in Q\\
9.\qquad\qquad \text{if}\ d(z)>w(u,z)\ \text{then}\\
10.\qquad\qquad\qquad Q.\text{Remove}(z);Q.\text{Insert}(z,w(u,z))\quad \color{red}{O(\log(|V|))}\\
11.\qquad\qquad\qquad d(z)\leftarrow w(u,z),\ p(z)\leftarrow \quad \color{red}{O(1)}\\
12.\ \text{return }T$

Total time: $O(|E|\log(|V|))$

Given a weighted, connected, simple undirected graph $G$ with weights of only $1$ and $2$ on each edge, why in this case the running time of the algorithm is $O(|E|+|V|\log(|V|))$?

I really not understand why the running time is not the same in this case, any help?

The running time depends on how you implement the queue data structure.

Hint: Can you think of any way to implement the queue data structures, so that ExtractMin, Remove, and Insert operations are much faster, if you're given the knowledge that every edge has weight either 1 or 2?


Finding integer square root for large integers [find asymptotic time complexity] So I found this tasks in one book I am practicing from where it says:
"Find a divide-and-conquer algorithm for finding square roots for large integers and along this, find its asymptotic time complexity". Results can be in integer range.
I am not sure which algorithm should I use, but I started with recursive method where I count the medium between two borders and go on until i find the perfect score, or if begin border becomes greater than the end one. What I have problem here is how to measure complexity for this problem and I am not even sure does this method count as divide-and-conquer?

Normally, you don't measure the complexity of a problem before designing an algorithm; instead, you measure the complexity of a particular algorithm.  So, before you get to measuring complexity, the first step is to come up with a specific algorithm.

When you have a specific algorithm in mind, one technique that's useful for analyzing the running time of divide-and-conquer algorithms is to write down a recurrence relation characterizing its running time, and then solve the recurrence.  You can often use the Master theorem to solve the recurrence.

To learn these techniques, see your favorite algorithms textbook, or read the following resources:

How to come up with the runtime of algorithms?
What is the difference between an algorithm, a language and a problem?
Solving or approximating recurrence relations for sequences of numbers
Is there a system behind the magic of algorithm analysis?


Math in computer science is hard? I am in High School (P.R.) and I am a regular person in math. Should I try computer science?

This is a very subjective question, but generally speaking, a computer science degree is (arguably) a mix of the "mathematical" and "engineering" aspects of computer science (there are also "scientific" aspects, but they are hardly usually encountered in undergraduate studies). The shared aspects include basic mathematics such as calculus and linear algebra. "Mathematical" computer science is discrete mathematics, automata theory, computability, computational complexity, algorithms, data structures and so on. "Engineering" aspects include programming computer organization, operating systems, databases, and so on. Advanced topics such as machine learning and computer graphics are (in my view) engineering topics which are relatively mathematical, though usually require continuous mathematics rather than discrete mathematics.

If you agree to this picture, then the conclusion is that computer science is less mathematical than mathematics. Computer programmers typically need to know a very small amount of mathematics. Indeed, even an understanding of mathematical induction is probably beyond what is needed. Most of your fellow classmates will probably have modest mathematical skills, so unless you have mathophobia, I think computer science is within your means.


How to go from a recurrence relation to a final complexity I have an algorithm, shown below, that I need to analyze. Because it's recursive in nature I set up a recurrence relation.

//Input: Adjacency matrix A[1..n, 1..n]) of an undirected graph G
//Output: 1 (true) if G is complete and 0 (false) otherwise
GraphComplete(A[1..n, 1..n]) {
  if ( n = 1 )
    return 1 //one-vertex graph is complete by definition
  else
    if not GraphComplete(A[0..n − 1, 0..n − 1])
      return 0
    else
      for ( j ← 1 to n − 1 ) do
        if ( A[n, j] = 0 )
          return 0
      end
      return 1
}

Here is what I believe is a valid and correct recurrence relation:

$\qquad \begin{align}
  T(1) &= 0 \\
  T(n) &= T(n-1) + n - 1 \quad \text{for } n \geq 2
\end{align}$

The "$n - 1$" is how many times the body of the for loop, specifically the "if A[n,j]=0" check, is executed.

The problem is, where do I go from here? How do I convert the above into something that actually shows what the resulting complexity is?

From what you wrote it seems that for all $k$ you have $T(k)=k-1+T(k-1)$ and $T(1)=0$. Therefore you can get it directly:

$$T(n)=(n-1)+(n-2)+\dots+1+0 = \sum_{k=1}^{n}{(k-1)}=\frac{n(n-1)}{2}$$

So $T(n)$ is in $Θ(n^2)$.


NDFA associated with language L Let A = $(Q, \Sigma, \delta, S, F)$ be a deterministic finite automaton associated with the language
$L \subseteq \Sigma^*$

$L' = \{y \in \Sigma^*:\exists x\in L. |x| = |y|\}$
$L \subseteq L'$

How do I show that there exist a NDFA associated with L' ?

Hint: Replace every transition labelled $a \in \Sigma$ with a transition labelled $\Sigma$.


Can User Level Thread read/write Kernel thread? As far as I read in a OS text book (Operating Systems by Silberschatz) Kernel mode is for privileged task, so it it true to claim that "User Level Thread can read/write Kernel threads" ?
Generally speaking, Is there any kind of protection between user and kernel level threads?

No.  In most operating systems, kernel memory is protected using virtual memory mechanisms, so a user process cannot read or write to kernel memory.
A user thread is part of a user process, and has the same permissions as the process.  So, a user thread will not be able to write to kernel memory.


Proving correctness of search algorithms I've seen correctness proofs for other searching algorithms; however, for this particular algorithm: search in a row-wise and column wise sorted matrix, I'm not able to generate a proper proof.

The algorithm is

Let x = element we're trying to search for in the matrix,
    e = current element we're processing in the array.
1) Start with the top right element.
2) Loop: compare this element e with x
...i) if e = x, then return the position of e, since we found x in the given matrix.
...ii) if e > x then move left to check elements smaller than e (if out of binding of the matrix, then break and return false)
...iii) if e < x then move below to check elements greater than e (if out of binding of the matrix, then break and return false)
3) repeat the i), ii) and iii) until you find the element or return false

Essentially, we start from the top right and traverse to the bottom left, key points being if element we're searching for is smaller then we go left if it's bigger we traverse down.

I'd like to use contradiction by saying the following: "If we traversed all the way to the bottom left of the algorithm and we didn't find the element we're searching (assuming it's in the matrix), then ..."

However, I'm not sure how to properly follow up the "then" because whatever I say is just repeating what the algorithm does, not really proving anything.

Is there a proper way to do this? Perhaps induction? (but this seems ever more complicated)

The idea of the algorithm is to maintain the following invariant:

  If $x$ is in the matrix, then it is in the submatrix whose top right corner is $e$.

The invariant clearly holds in the beginning, since $e$ is the top right corner of the original matrix.

If $e > x$ then all elements below $e$ are also larger than $x$, and so $x$ cannot be contained in that column. Therefore the invariant continues to hold with $e$ replaced with its left neighbor (if $e$ has no left neightbor, we can deduce that $x$ is not found in the matrix).

If $e < x$ then all elements to the left of $e$ are also smaller than $x$, and so $x$ cannot be contained in that row. Therefore the invariant continues to hold with $e$ replaced with its neighbor below (if any).

On an $n \times m$ matrix, this process terminates in at most $n+m$ steps, either finding $x$ or determining that it does not appear in the matrix.


Software for testing graph homomorphism I have graphs $G_k$ and $H_k$ with $|\mathcal{V}(G_k)|=|\mathcal{V}(H_k)|^{2k}=n^{2k}$ with $k\in\Bbb N$ that pass sanity checks such as no-homomorphism lemma. Are there free and easy to use tools to test graph homomorphism from $G$ to $H$?

The best way (in terms of laziness)  is to use the freely available tool Sage which has the best support for graph theory.

Example

sage: G = graphs.PetersenGraph()
sage: G.has_homomorphism_to(graphs.CycleGraph(5))
False
sage: G.has_homomorphism_to(graphs.CompleteGraph(5))
{0: 0, 1: 1, 2: 0, 3: 1, 4: 2, 5: 1, 6: 0, 7: 2, 8: 2, 9: 1}


Should we always think of problems higher in the polynomial hierarchy as harder than problems lower in the hierarchy? This "research vignette" (whatever that is) claims that the polynomial hierarchy

  classifies problems according to a natural notion of logical complexity, and is defined with an infinite number of levels: problems at the zeroth level are the “easiest”, and for every integer $k$, problems at the $(k+1)$-st level have logical complexity “one notch higher” than those at level $k$.

Obviously this is just a heuristic explanation rather than any kind of rigorous claim, but is it true that problems higher in the hierarchy should be thought of as harder than problems lower in the hierarchy?

For example, consider the complexity class BQP. It is not believed to contain NP; in fact, many experts consider (Fig. 3) NP-complete problems to be much harder than the hardest problems in BQP. But the same experts also believe that BQP is not contained within the polynomial hierarchy PH (with Recursive Fourier Sampling as a concrete example of a problem believed to be in BQP \ PH). It therefore seems reasonable to say that for any $n$, there exist problems in $\Sigma_n \setminus \Sigma_{n-1}$ that are easier than RFS.

But putting these two results (that any NP-complete problem is harder than RFS, and that RFS is harder than some problem in $\Sigma_n \setminus \Sigma_{n-1}$ for any $n$) together, we find that there are problems in $\Sigma_1$ (namely, any NP-complete problem) that are harder (in fact, much, much harder) than certain problems in $\Sigma_n \setminus \Sigma_{n-1}$ for all $n$. Therefore, I don't see any way in which the polynomial hierarchy actually ranks problems by complexity.

Is there is mistake in my reasoning? Is there any useful sense in which problems higher up in the hierarchy are always harder than problems lower down? (I know this is a soft question, since there are different ways of formalizing the notion that one problem is "harder" than another. Maybe the answer is just that the PH is one way of ranking certain problems by difficulty, but not generally the best way.)

The quote you give is an informal claim/intuition.  Don't try to read too much into informal claims; they are intended to give you a sense of what's going on, but for specific details, you need to look at the precise technical claim.

I suspect the source of your confusion is that you are using the same phrase  in two or three different ways in different places, without realizing it.  This is the logical fallacy of equivocation.  In particular, I don't think you're using "harder than" in exactly the same way each time you use it.  This then leads to you reaching conclusions that seem absurd or confusing.  One way to remedy the confusion is to understand more clearly exactly what you mean by "harder than", and then walk through your logic.

One possible meaning of "P is harder than Q" is that the "running time of the fastest algorithm to solve P is larger than the running time of the fastest algorithm to solve Q, in some specific theoretical model of computation".  This is a statement about theoretical complexity.  Note that this meaning depends on the model of computation.  P might be harder than Q in one model of computation (e.g., classical computation), but not in another model (e.g., quantum computation).

A second possible meaning of "P is harder than Q" is "Q reduces to P".  This is a theoretical statement, which has implications for the previous statement (if Q reduces to P, then the running time of the fastest algorithm for P can't be too much less than the running time of the fastest algorithm for Q).  Note that this notion of "harder than" is as a partial order.  There might be two problems P,Q such that neither "P is harder than Q" nor "Q is harder than P" are true; the problems might be incomparable.

A third possible meaning of "P is harder than Q" is "in practice it's probably harder (takes more time or costs more) to solve instances of P than instances of Q".  This is a statement about engineering and what is feasible in practice, rather than theory.  For instance, this will depend on whether quantum computers are feasible to build, in practice -- something that no one knows the answer to right now.  If quantum computers are feasible, then we'll discover that factoring is much easier than all NP-complete problems, because a quantum computer can solve factoring quickly but can't solve NP-complete problems quickly (we think).  If quantum computers aren't feasible, then factoring might turn out to be not much easier than some NP-complete problems.

Finally, just because a problem isn't in PH doesn't necessarily mean it is harder than all problems in PH -- so just because Recursive Fourier Sampling is not in PH doesn't necessarily mean it is harder than all problems in PH (in the sense of the existence of a reduction).

As a final complication, Recursive Fourier Sampling is a funny kind of problem.  It's not an ordinary decision problem.  Rather, it's an oracle problem.  Oracle problems can't be directly compared to ordinary problems.


Checking the validity of a pyramid of dominoes I came across this question in a coding interview and couldn't figure out a good solution.

You are given 6 dominoes. A domino has 2 halves each with a number of spots. You are building a 3-level pyramid of dominoes. The bottom level has 3 dominoes, the middle level has 2, and the top has 1.

The arrangement is such that each level is positioned over the center of the level below it. Here is a visual:

         [ 3 | 4 ]
    [ 2 | 3 ] [ 4 | 5 ]
[ 1 | 2 ][ 3 | 4 ][ 5 | 6 ]

The pyramid must be set up such that the number of spots on each domino half should be the same as the number on the half beneath it. This doesn't apply to neighboring dominoes on the same level.

Is it possible to build a pyramid from 6 dominoes in the arrangement described above? Dominoes can be freely arranged and rotated.

Write a function that takes an array of 12 ints (such that arr[0], arr[1] are the first domino, arr[2], arr[3] are the second domino, etc.) and return "YES" or "NO" if it is possible or not to create a pyramid with the given 6 dominoes.

Thank you.

I can think of a brute force solution. Try all 6!*(2^6) options. i.e. create all legal permutations of the pyramid and test each one if it holds the condition. It will take around 50K iterations to do.


Construct a Deterministic Pushdown Automaton for unequal number of elements Can anyone help me construct a deterministic PDA for the following language:

$$L=\{w\in(a,b)^* \mid \#_a(w)\neq \#_b(w)\}$$

Or can anyone check if the following solution is correct?

The answer in that image is actually not a deterministic PDA, because in the definition of DPDA, the transition functions need to satisfy the following rules: 1. $\delta(q, a, b)$ contains at most one element; 2. if $\delta(q,\lambda,b)$ is not empty, then $\delta(q,c,b)$ must be empty for every $c\in\Sigma$. These two rules prevent multiple paths for same input symbol and stack symbol (to make it deterministic). From the PDA in the question, there are some transitions like $\delta(q_0,a,b)$ and $\delta(q_0,\lambda,b)$, which does not satisfy the second rule.
There is one way to get the DPDA for this language $L=\{w: n_a(w)\neq n_b(w)\}$, which is to get the DPDA of the complement of $L$ first, and that is $\bar{L}=\{w: n_a(w)=n_b(w)\}$. Then you can simply convert the final states to non-final states and vice versa. The DPDA for $\bar{L}$ is very similar to the one in the question, except that the transitions from $q_0$ to $q_1$ should be changed to $ \delta(q_0,\lambda,＄)=(q_1,＄). $ After that, changing $q_0$ to a final state and $q_1$ to a non-final state and you will get the correct answer. This method is based on the closure property for DCFL that DCFL is closed under complementation.


Longest AP that can be formed (with difference 1) in an unsorted array of integers By integers, I mean a whole number.

Example:

Input : 2, 4, 7, 9, 3, 1, 11

Output: 1,2,3,4 forms an AP (of difference 1) with length 4.

An obvious solution is to sort the array with a comparison based algorithm O(nlogn) and then do a second scan through the unsorted array to find the longest sequence.

Can we have a better time complexity (at the expense of addition space)?

If you're allowed to use hash tables, you can get a linear time algorithm.

Go over all nodes, putting the unique nodes in a hashtable, and constructing a new array only with the unique values. Now go over the new array and upgrade it to a graph $G = (V,E)$ in which $V$ are the unique values and the edges connect $i$ to $i+1$. Go over the graph, and whenever you see a vertex with no incoming edge, follow the unique path emanating from it and count its length. The answer is the maximal length of such a path.

This solution uses a hashtable to efficiently construct the graph. This suggests that you might not be able to do better than $n\log n$ if you are only allowed to use comparisons. One way to prove it would be by reduction from element uniqueness, which is known to require $n\log n$ comparisons.


Necessities for two undirected graphs being isomorphic As far as I know, for two undirected graphs $G = (V, E) $ and $H = (V', E')$, the following criteria is necessary for them to be isomorphic:

$|V| = |V'|$
$|E| = |E'|$
$G$ has $j$ nodes of degree $k$ $\Leftrightarrow $ $H$ has $j$ nodes of degree $k$

Are there more that are that obvious? Thanks in advance for your help!

For two graphs $G$ and $H$ it is necessary for literally every property that holds of $G$ to also hold of $H$ and vice-versa.  There's no point making a list because everything is in that list.


Are two CCS processes equivalent with respect to weak bisimilarity if and only if they satisfy exactly the same set of HML formulas? I was skimming this recent paper and I was struck by the following statement:

  two processes are equivalent with respect to weak bisimilarity if and only if they satisfy exactly the same set of HML formulas

I have trouble believing it.

I reason that:

weak bisimilarity does not account for tau-transitions and therefore is oblivious to the possibility of livelocks.
I believe the possibility of a livelock can be represented in HML,

and, therefore, a counterexample can be constructed.

Consider these processes:

One = lol.One;
A = lol.omg.A + zomg.A;
B = 'omg.B + 'zomg.B;
Two = (A | B) \ {omg, zomg};

Consider, furthermore, the HML formula

Livelock = max(X. <tau>X);

I believe that this formula is satisfied only by Two, which nevertheless is weakly bisimiliar to One.

I have tried to use the Edinburgh Concurrency Workbench to confirm my reasoning:

agent One = lol.One;
agent A = lol.omg.A + zomg.A;
agent B = 'omg.B + 'zomg.B;
agent Two = (A | B) \ {omg, zomg};
prop Livelock = max(X. <tau>X);
******
echo "Is One strongly bisimilar to Two?";
strongeq(One, Two); ********************* outputs "false"
echo "Is One weakly bisimilar to Two?";
eq(One, Two);       ********************* outputs "true"
echo "Is it the case that One |= Livelock?";
checkprop(One,Livelock);  *************** outputs "false"
echo "Is it the case Two |= Livelock?";
checkprop(Two,Livelock);  *************** outputs "true"

So, is it the case that two processes are equivalent with respect to weak bisimilarity if and only if they satisfy exactly the same set of HML formulas?

If so, why is this true, and what's the flaw in the counterexample, above?
If not, what did the authors mean or what sort of context am I missing? (Or was it a typo?)

(This probably does not fully answer, but I think it can still help)

According to their Def. 4, there is no modality $\langle \tau \rangle$ in their HML logic. Their syntax only allows $\langle\!\langle u \rangle\!\rangle$ where $u \in A \cup\{\epsilon\}$, and $\tau$ is assumed not to be in $A$ (Def. 1), hence $u\neq\tau$.

Also, there seems to be no recursion allowed in their logic.

Further, as far as I can see, in the Concurrency Workbench <a> indicates a strong possibility, while <<a>> indicates a weak possibility.

I can't recall which variant of the HML logic precisely corresponds to weak bisimilarity, but I think that it can't involve a strong <tau> modality since otherwise we would distinguish lol and tau.lol.


Data structure for shopping cart I'm working on an e-commerce application where users can add stand-alone products like speaker or they can add a bundle product like desktop that has options like mouse, keyboard etc. All the products and options are finally added as cart items to the cart.
For example
Desktop
  - Mouse
  - Keyboard
Speaker

After adding above the cart will have items like below,
Shopping Cart
  Line item 1 - Desktop - Parent-Line NULL
  Line Item 2 - Mouse - Parent-Line Item 1
  Line Item 3 - Keyboard - Parent-Line Item 1
  Line Item 4 - Speaker - Parent-Line NULL

If I remove the product desktop from the cart all of it's options should also be removed. At the same time we want to access all the line items as an array too.
For example,
for (var items in shoppingCart.items) {
  console.log(item);
}

// "Desktop", "Mouse", "Keyboard", "Speaker"

If I use an array to store the items then I need to work on the logic to remove the child options on removing parent. I couldn't come-up with an excellent data structure to solve this problem. Any ideas would be very helpful.

A tree data structure is a natural way to store this data.  It supports all of the operations you listed.


Algorithmic type checking for Calculus of Inductive Constructions So from reading "Advanced Topics in Types and Programming Languages" (ATTPL) I know of the calculus of constructions (CoC). It also presents the "algorithmic" type checking rules. Reading Coq's documentation on the Calculus of Inductive Constructions (CioC) you can get a sense of things but it is far from algorithmic. Is there any reference on algorithmic type checking for CioC?

The problem of giving an algorithmic reading to the typing rules in CIC, and dependent type systems in general, is quite subtle.

One recommendation is Randy Pollack's Typechecking in Pure Type Systems, Gille Barthe's Type Checking *Injective Pure Type Systems and McKinna and Pollack's Pure Type Systems formalized.

The first basic idea is to "push" the conversion rule
$$ \frac{\Gamma \vdash t: A\quad A\simeq B}{\Gamma\vdash t : B}$$

into the application rule
$$ \frac{\Gamma \vdash t:A\quad \Gamma\vdash u:A' \quad A\simeq \Pi x: A'.B}{\Gamma\vdash t\ u:B\{x\mapsto u\}}$$

And similarly for "application-like" rules. The theorem is that these modified rules suffice for type-checking (without conversion), with the exception of a possible single application of conversion at the end.

This makes the rules type-directed, which allows a straightforward implementation. There are additional shortcuts which allow skipping verification of $\mathrm{WF}$, for example, if it is known that it is going to be derived later, or it is admissible.

As Luke notes, there is no complete treatment of such shortcuts, and the validity of these is sometimes quite complicated to prove (e.g. the "expansion postponement" rule).

Checking conversion of terms with $\delta$-reductions (defined functions) is a whole bag of worms: when checking

$$ f\ t_1\ldots t_n\simeq f\ u_1\ldots u_n$$

should you just check $t_i\simeq u_i$ for each $i$, or unfold $f$? The answer is, unsurprisingly, it depends. In general clever heuristics are used, e.g. "unfold $f$ if it is a projection, otherwise try checking equivalence of the arguments, and unfold $f$ if that fails".


Survey of informed search algorithms? I'm looking for a list of informed search algorithms, also known as heuristic search algorithms.

I'm aware of:

best-first search

Greedy best-first search
A* search

Are there more best-first algorithm or other informed searches that are not best-first?

That list would be endless ... I will just try to provide a number of representative examples according to different criteria:

Best-first search (BFS): they are complete, i.e., they are guaranteed to find a solution provided that one exists and they are admissible, i.e., they are guaranteed to find the optimal solution provided, again, that one exists. However, they take memory exponentially in the depth of the search tree. Other than Greedy best-first search and A$^*$, pure heuristic search ($f(n)=h(n)$) is often quoted as another BFS algorithm

Depth-first search (DFS): they are not complete, and thus they are not admissible. However, running a sequence of depth-first searches with a threshold that increases monotonically is guaranteed both to be complete and admissible while it takes memory just linear in the depth of the search tree. The most prominent member in this class would be IDA$^*$. However, this is not the only way to guarantee both completeness and admissibility and Depth-First Bround-and-Bound (DFBnB) takes also memory which is linear in the depth of the search tree.

Bidirectional Search (BS): It has been observed that BS saves an exponential amount of time and memory in the case of blind (non-heuristic) search. Many efforts have been invested to reproduce the same result when using heuristic search but it is still an open question how to implement bidirectional search efficiently when using heuristics. James Kwa showed that BS* does not always expand less nodes than a single A$^*$ and Ariel Felner et al. have recently suggested Single-Frontier Bidirectional Search as a way to turn bidirectional search into a unidirectional search.

Perimeter Search (PS): while most people was considering that bidirectional search consists of two searches progressing simultaneously (either in front-to-front or front-to-end fashion), Giovanni Manzini and also Nelson and Dillemburg simultaneously and independently suggested to develop a perimeter around the target node $t$ and then to issue a unidirectional search from the start state $s$. The resulting algorithm is better known as Bidirectional Iterative-Deepening A* BIDA$^*$

Real-Time Search (RTS): in most cases the search is conducted off-line, i.e., the solution is seeked and as once it is found, it is executed. Korf (again) showed that this is not necessarily a limitation and was the first in introducing Real-Time Search for looking for the solution while the agent is moving. The same algorithm was improved and it is known as Learning Real-Time Search. This work started a branch of research which is continued even nowadays and you can find a myriad of algorithms to solve problems in Real-Time search. Very importantly also, this category of algorithms was devised taking minimax as a motif where decisions are taken without ever visiting a goal node. This is, these algorithms are also expected to solve problems which are unsolvable with the previous algorithms.

Moving-Target Search: somehow related to the previous case, but not exactly equal is the case of seeking a moving target while the agent is moving. Originally (as far as I know) Ishida and Korf (get in use to hear from Korf ;) ) suggested an algorithm called exactly like this Moving-Target Search. Ishida continued the work later and some work has been presented in recent years.

Sub-optimal search: most of the algorithms described above (all but RTS) are used to find optimal solutions. However, some algorithms are "extended" to find sub-optimal solutions with guarantees on the error margin. For example, Ira Pohl introduced weighted-A* WA$^*$ which is known to find solutions with a bounded error. There are also a lot of research in this category and one of my favourite algorithms  (among others) is $A_{\epsilon}$

But bear in mind that these are just only a number of prominent examles. The list of algorithms is huge and even the list of categories is quite large (though not impossible to get, of course).

Cheers,


Compressing a bit string when I know how many 1s and 0s there are Say I have a 256 bit bit-string, and I know that there are 16 ones and 240 zeros. I know that this bit string can be compressed, because there are only 256 choose 16 possible strings that satisfy this condition: that's about 2^83.06.
So I know that I should be able to compress this bit string down to 84 bits long. But I don't know how to go about doing it. I tried to make a lookup table, but can't, because it's too big.
Is there a way to quickly perform this compression/decompression?

The operation of translating between combinatorial objects and their indices in some enumeration is known as ranking/unranking (ranking is to convert an object to a number, unranking is the opposite). In your case, you are interesting in ranking/unranking subsets.
Suppose that you are given a subset $S$ of $\{1,\ldots,n\}$ of size $k$, and want to convert it to an integer in $0,\ldots,\binom{n}{k}-1$. If $k = 0$ or $k = n$ then you can just output $0$. Otherwise, we want to put the $\binom{n-1}{k}$ subsets not containing $n$ before the $\binom{n-1}{k-1}$ subsets containing $n$. Therefore:

If $S$ doesn't contain $n$ then you just output the rank of $S$ as a subset of $\{1,\ldots,n-1\}$ of size $k$.
If $S$ does contain $n$, you compute the rank of $S \setminus \{n\}$ as a subset of $\{1,\ldots,n-1\}$ of size $k-1$, and add to it $\binom{n-1}{k}$.

The decoding procedure is very similar. If $k = 0$ you output $\emptyset$, if $k = n$ you output $\{1,\ldots,n\}$, and otherwise:

If the index is less than $\binom{n-1}{k}$, decode it as encoding a subset of $\{1,\ldots,n-1\}$ of size $k$.
Otherwise, subtract $\binom{n-1}{k}$ from the index, decode it as encoding a subset of $\{1,\ldots,n-1\}$ of size $k-1$, and add the element $n$ to the resulting subset.

You can precompute all relevant binomial coefficients to speed things up. In your case, the index is more than 64-bit long, so you will have to work with 128-bit arithmetic somehow, but the resulting algorithm should be reasonably fast.


Page Table Size in a 4 Level Hierarchical Page Table An Intel 64 bit CPU uses a four-level hierarchical page table. Each of the four levels of the page table can contain 512 entries, and the page table size is 4KB. You should be able to see that it cannot actually address 2^64 bytes of virtual memory. If a process on the system used 12MB of text, 5MB of heap and 7MB of stack, calculate the page table size, the number of page table entries required and the number of second level page tables.

Disclaimer: This question is not from an academic assessment. It is a past paper question in preparation for an examination.

If the page table size is 4096 bytes then $\log_2(4096) = 12$. Thus, the offset is 12 bits. Since there are 4 levels in this page table and each level can support 512 entries, the index into each entry is $\log_2(512) = 9$. Thus, you have 4x 9 bit indexes in the virtual address and a 12 bit offset.

One question arises: $9 * 4 + 12 = 48$ bits. But we have 64 bit virtual addresses? What happens to the other 16 bits? I would assume these are zeroed as the 16 most significant bits. Is that correct?

If this is true,  does that mean this paging system can address 2^36 pages of virtual and physical memory, and therefore, it can address at most 2^48 bytes of virtual and physical memory. Is that correct?

Under the assumption outlined above: 12MB of text requires 3072 pages, 5MB of heap requires 1280 pages and 7MB of stack requires 1792 pages.

We know that the address space looks like this:

|----------| 2^36
|  Stack   | (Stack expands down)
|          |
|          |
|          |
|   Heap   | (Heap expands up)
|   Text   |
|----------| 0x0

Since the stack is at the top of the address space, it must have it's own second level page table. However, the program text and heap are at the bottom of the address space. Since each second level page table can address 512GB of memory (512^3 * 4096) the program text and heap can share a second level page table. Then, since each third level page table can address 1GB (512^2 * 4096) the program text and heap can share a third level page table too. Thus, we have 18 page table entries. Since this is a 64 bit architecture, each page table consumes 64 bits, and therefore the size of the page table is $18 * 512 * {64 \over 8} = 72KB$.

4th level can address $512 \times 4096$ bytes,

3rd level can address $512^2 \times 4096$ bytes,

2nd level can address $512^3 \times 4096$ bytes,

1st level can address $512^4 \times 4096$ bytes.

     L1       L2       L3       L4
2^32 |---|--->[---]--->[---]--->[---]   }
     |---|                  --->[---]   }  7MB STACK
     |---|                  --->[---]   }
     |---|                  --->[---]   }
     |---|
     |---|
     |---|
     |---|
     |---|                      L4
     |---|                      |->[---] }
     |---|                      |->[---] } 5MB HEAP
     |---|    L2       L3       |->[---] }
   0 |---|--->[---]--->[---]--->|
                                |->[---] }
                                |->[---] }
                                |->[---] } 12MB TEXT
                                |->[---] }
                                |->[---] }
                                |->[---] }

Key [---] Level in Page Table
     ---> Pointer to Lower Level Page Table

The virtual addresses must be canonical, the top 16 bits are all copies of the 48th bit. Using a non-canonical address (in the sense of using it as an address) generates a #GP. See also, the manual, volume 3, chapters 3 and 4.

That is independent from the maximum physical address, which is not "canonical" in that way but just goes from 0 to some large number determined by MAXPHYADDR. You can find MAXPHYADDR using CPUID:80000008H, the lowest 8 bits in eax. It specifies the bit index in the page table entries (and some other places where you specify a physical address) at which the physical address stops and the reserved region begins. It's at least 36. It could be 48, but that wouldn't have anything to do with the limits on virtual addresses. The page table entry format allows it to go up to 52 (allowing you to address 4PB of RAM), but that hasn't happened yet. Intel seems to like 39 and 46, AMD seems to mostly use 48 now (they've used lower in the past) (source).


Complement DCFGs and handles If I have a DCFG G for some language over {0,1}* and a DCFG H for its complement, with disjoint non-terminals, and a (perhaps partially reduced) string, can they both have a handle for the string? So the right hand sides of these rules would consist of only terminals and one would be a (maybe proper) prefix of the other. I think it's possible but I'm not certain and can't quite show it.

What you want is not necessarily possible. So you have to build grammars
that will make it possible.

Try prefixing both languages by $\{0,1\}^3$ (for example).  That is,
if $L_G$ and $L_H$ are the languages corresponding to your grammars,
consider the languages $\{0,1\}^3$.$L_G$ and $\{0,1\}^3$.$L_H$.

You should be able to build grammars for them, and also prove that
they are complement of each other. You should also be able to show
that since, there are DPDAs recognizing the two languages $L_G$ and
$L_H$, you can build from them DPDAs that recognize your augmented
languages.

If you build the grammars as you should (it is very easy), you will
get your double handle.

The only problem is that, since both handles are on the same side, you
cannot use them for a bicycle, or for a heavy pot.


If $L1⊆L2$, and $L1\not∈RE$, is it possible that $L2∈RE$ If $L1⊆L2$, and $L1\not∈RE$, is it possible that $L2∈RE$ ?

Also I find it hard to find languages that are not in RE at all, I've heard about Arithmetical hierarchy but we didn't really learnt it in class so I guess the solution shouldn't necessarily be correlated to Arithmetical hierarchy.

I know that the $A_{TM}=\{(〈M〉,w): M\ accepts\ w\}$ where M is a Turing machine
then $\overline {A_{TM}}\notin RE$, but it doesn't seem to help.

Yes. Actually, it is even true that for every language $L_1$ there is a language $L_2 \supseteq L_1$ such that $L_2$ is regular.

Proof: Pick $L_2 = \Sigma^*. \square$


A connected acyclic graph has $n-1$ edges Let $G$ be an undirected graph with $n$ nodes. Prove that any two of the following implies the third:

$G$ is connected
$G$ is acyclic
$G$ has $n-1$ edges

Proving $1, 2 \implies 3$
A connected, acyclic graph is a tree. Each node(vertex), except the root, in the tree has exactly one edge going upwards(towards the root), hence it has $n-1$ edges.
The Problem
I'm not able to write a formal proof for the other two. The problem is that here I used the fact that connected, acyclic graph is a tree and then it was easy to prove using properties of a tree, for the other I tried using contradiction but couldn't prove them.
Any hint on how to approach this problem and how to prove $1, 2 \implies 3$ without using the fact that connected acyclic graph is a tree?
Reference
This problem is from Chapter 3 of Algorithm Design by Jon Kleinberg and Éva Tardos. Addison-Wesley

Proving 2,3 implies 1:
We have an acyclic graph $G=(V, E)$ with $n-1$ edges. We want to prove that $G$ is a connected graph.
Assume for the sake of contradiction that $G$ is not connected. This means we have $d>1$ connected components, $G=\{\bigcup_{i=1}^{d}G_i\}$.
Since $G$ is acyclic, each connected component is a tree by definition. Let $V_i$ be the set of vertices of graph $G_i$. Then, the number of edges in $G_i$ is $\mid E_i \mid = \mid V_i \mid - 1$. Thus, the total number of edges in $G$ is
$\mid\ E \mid\ =\sum_{i=1}^{d}\mid E_i \mid =\sum_{i=1}^{d} (\mid V_i \mid-1)=\sum_{i=1}^{d}(\mid V_i \mid)- d = n - d < n -1$.
The last inequality follows because $d > 1$. This is a contradiction that $\mid\ E \mid\ = n-1$.
Proving that 1,3 implies 2: We have a connected graph $G=(V, E)$ with with $n-1$ edges. We want to prove that $G$ is acyclic. I will not write the proof, but I will hint that (one of many possible proofs) you can use induction on the number of vertices. And let your assumption be that given $G$ with $n-1$ vertices and at most $n-2$ edges, then $G$ is acyclic.


Kolmogorov complexity of prefixes of computable sequences Let the characteristic sequence of a set $A ⊆ \mathbb{Z^+}$ be the following infinite binary sequence:
$$χ_A = b_1b_2b_3\ldots,$$
whose $n$th bit is 1 if $n ∈ A$ And 0 otherwise.
Write $χ_{A,n}$ for the first $n$ bits of $χ_A$.
Prove for every decidable set $A \subseteq \mathbb{Z^+}$ there is a constant $c ∈ \mathbb{N}^+$ such that for all $n ∈ \mathbb{Z}^+$ the Kolmogorov complexity of $\chi_{A,n}$ satisfies
$$ C(χ_{A,n})≤\log n+c. $$

Since $A$ is decidable there is a lexicograhic enumerator. Given that, how would I construct a Turing machine $\pi_A$ satisfying $U(\pi_A)= χ_{A,n}$, where $U$ is the universal Turing machine, whose complexity is at most $\log n+c$?

Let $D$ be a decider for $A$, then in order to determine $\mathcal{X}_{A,n}$ it is enough to specify $n$ and an encoding of $D$. Given $D,n$, you can loop over all integers $i\in [n]$ and check whether or not $i\in A$ by simulating $D(i)$. Thus, the overall description of $\mathcal{X}_{A,n}$ consists of $n$, the encoding of $D$ and the encapsulating machine $M$ (described above) which uses $D,n$ to output $\mathcal{X}_{A,n}$. $n$ contributes at most $\log n$ bits to the description, and $D,M$ have some encoding of length $c$ independent of $n$, bounding the overall description length by $\log n + c$.


Difference between a turing machine and a finite state machine? I am doing a presentation about Turing machines and I wanted to give some background on FSM's before introducing Turing Machines. Problem is, I really don't know what is VERY different from one another.

Here's what I know it's different:

  FSM has sequential states depending on the corresponding condition met while Turing machines operate on infinite "Tape" with a head which
  reads and writes.

  There's more room for error in FSM's since we can easily fall on a non-ending state, while it's not so much for Turing machines since we
  can go back and change things.

But other than that, I don't know a whole lot more differences which make Turing machines better than FSM's.

Can you please help me?

The major distinction between how DFAs (Deterministic Finite Automaton) and TMs work is in terms of how they use memory.

Intuitively, DFAs have no "scratch" memory at all; the configuration of a DFA is entirely accounted for by the state in which it currently finds itself, and its current progress in reading the input.

Intuitively, TMs have a "scratch" memory in the form of tape; the configuration of a TM consists both of its current state and the current contents of the tape, which the TM may change as it executes.

A DFA may be thought of as a TM that neither changes any tape symbols nor moves the head to the left. These restrictions make it impossible to recognize certain languages which can be accepted by TMs.

Note that I use the term "DFA" rather than "FSM", since, technically, I'd consider a TM to be a finite-state machine, since TMs by definition have a finite number of states. The difference between DFAs and TMs is in the number of configurations, which is the same as the number of states for a DFA, but is infinitely great for a TM.


Finding two languages satisfying conditions Let $$E_{TM} = \left \{ \langle M\rangle \mid L(M) = \emptyset \right\}$$

  Prove that there are two languages $L_1, L_2$ such that

  $L_1, L_2 $ are infinite.
  $L_1 \cup L_2 = E_{TM}$
  $L_1 \cap L_2 = \emptyset$
  $L_1$ is decidable, $L_2$ is not recognizable.

I'm finding it really hard to find two languages that satisfy these conditions.

Especially the second condition, which two language unify to $E_{TM}$?

A slight improvement:

$L_2 = E_{TM} \backslash L_1 $ (since we require that $L_1 \cap L_2 = \emptyset$).

$L_1$ must be a language of turing machines, i.e. $L_1 = \{\langle M\rangle \mid \dots\} $, so that $L_1 \cup L_2 = E_{TM}$.

So let's set $L_1 =$ $\{\langle M\rangle\mid  C_0\text{ is a reject state}\}$.

The following holds:

$L_1 $ is infinite and decidable (easy to decide given $M$, what the configuration of the first state is).
$L_2 $ is infinite and unrecognizable.


What is the fastest way to input all of 30 million human "go" move into the computer that haven't digitized? What is the fastest way right now to input all of 30 million "go" move from the beginning into the computer that haven't digitized?

The idea is came from Google's AlphaGo

Your bottleneck when doing this will be to gather up all the not yet digitized moves, validate them somehow, and digitize them. Once that is done, reading in the data will be a snap.


Can CNF with an input string be evaluated in logarithmic space? I have been trying to solve satisfiability of

{$<c, w>$ | $c$ is a CNF and $w$ is a binary string which satifies the $c$}.

As first looks to me, it is satisiable in linear time ($O(n)$) since $w$ has lenght $n$.

I tried thinking about whether the space complexity of this problem can be reduced to logarithmic order. But couldn’t end up with an acceptable reason so far. Well, my first thought is the following:

Considering that CNF $c$ is composed of conjuction of some clasuses, it’s possible to write every clauses’s result (0 or 1) to the working tape and after reading the entire string, evaluate those 0’s and 1’s (which correlates with the CNF’s clauses). But this won’t result in a logarithmic space complexity anyway and I think it would be of $O(n/k) = O(n)$ where $k$ is the number of clauses.

Is there an optimize way of solving this in logarithmic space?

Yes, you can decide this language in logarithmic space, using the following algorithm:

for each clause in the CNF:

do a linear scan of $w$ to see if one of the literals in the clause is satisfied; if not, reject

if you got through all the clauses without rejecting, accept

What's the space complexity?  Well, there are at most $n$ clauses, so we need at most $\lg n$ bits to store the loop counter to keep track of which clause we're currently on.  We also need to store the current clause; there are at most $n$ variables in the formula, so we need at most $3 (1+\lg n)$ bits to store the clause.  Therefore, we need at most $O(\lg n)$ bits in total of space.

Of course, the running time is not optimal (it is $O(n^2)$ or so), but that doesn't matter, as we're only counting space complexity.


What Measure of Disorder to use when Analysing Quicksort I'm trying to understand why quicksort using Lomuto partition and a fixed pivot is performing erratically, but overall poorly, on randomly generated inputs.  I'm thinking that even though the inputs are randomly generated, there may be a lot of order to the sequences, but I'm not sure how to measure the level of disorder in the sequences.  I thought about using the number of inversions, but I saw from this other question I asked that that's not really a good measure in this case.

The reason I suspect that my random sequences have a lot of "order" to them is that randomizing the pivot fixes the performance problem.  But theoretically there shouldn't be any performance problem on these supposedly "random" input sequences.

Lomuto vs Hoare
Lomuto partition suffers when sorting equal keys, whilst Hoare partition does not.
Both partition schemes suffer equally when using a pivot distant from the median.

Measure of disorder
The measure of disorder to choose for the purposes of quicksort is simple.
A: How far removed from median is the fixed pivot, compared to random data?
If you insist on using Lomuto partition and if you assume duplicate values are allowed you need to add the following test against randomness:
B: How many duplicate elements are there, compared to random.

Of course it is rather silly to assume that duplicate values are allowed in your data set and still evaluate Lomuto partition, so you should probably either eliminate duplicates beforehand or switch to Hoare partition or assume duplicates are rare.

Both measures are trivial to quantify using statistics.

We can rule out pathological data
Any other deviations from randomness will not matter for the purposes of analysing quicksort. As long as the pivot is close to the median it will perform well on all data that is not pathological.
The distance from random would have to be great indeed to be quicksort-pathological, so we can rule that out.

Never use any fixed pivot(s) in real code
Do note that if you write real code with a fixed pivot*) (whatever that pivot may be) you are opening yourself up to a denial of service attack, because an attacker can insert a pathological value at just that point and thus you should always choose a random element as pivot.

*) or multiple pivots if you choose best of x pivots.


Is there a deterministic algorithm to construct $(n,k)$-universal set of minimum size? Let $S\subseteq \{0,1\}^n$, $S$ is a $(n,k)$-universal set if for every subset of indices $I$ of size $k$, projecting $S$ to $I$ yield the $2^k$ binary strings (all the possible strings of $I$). $S$ is of minimum size if there is no other $(n,k)$-universal set $S'$ where $|S'|<|S|$.

is there a known algorithm to construct a $(n,k)$-universal set in general and of (close-to) minimum size in particular?

Such constructions appear in papers of Seroussi and Bshouty, Alon, and Naor and Naor. See Bshouty for the latest on this topic.


Order a list of edges to make the the complexity of searching for an edge O(lg E) I was reading this article on how to represent graphs, and probably the simplest way to think about it is to have a list of edges, with an edget being usually a list of the vertices that are related (connected).

Now, at a certain point, there's a question:

  How can you organize an edge list to make searching for a particular edge take
  O(lg E) time?

I was thinking to the trivial solution of sorting, but it is not so easy to sort a list of edges. For example, let the following be our initial list of edges:

[[3, 2], [1, 2], [1, 3]]

Now, if we try to sort it by using the first vertex, we obtain:

[[1, 3], [1, 2], [3, 2]]

I am not visualizing well if this search would be O(lg E), where E is the number of edges.

Could you please explain how could we organize the edges in order to have a edge searching algorithm with a time complexity of O(lg E)? And why it should be O(lg E)?

Any total order will do; more is not needed for sorting and searching with binary search in a sorted list.

The lexicographic order would be a canonical choice for sorting tuples.

If your elements are (unordered) sets (e.g. edges of undirected graphs) you can sort them before comparing by the order on tuples as well.


How to cover given entries in a matrix with minimum number of rows and columns? We have a matrix of 0 and 1. We want to cover all the 1's. We can cover a raw or a column with a plate. We want to use the minimum number of plates.

example

0 0 1 0

0 1 0 1

0 0 1 0

0 0 1 0

cover 3rd column and 2nd raw. so two plates.

Let $R=\{r_1, \cdots, r_n\}$ be the set of all rows. Let $C=\{c_1, \cdots, c_m\}$ be the set of all columns. If and only if the matrix entry at row $i$ and column $j$ is 1, we connect $r_i$ with $c_j$ with an edge. Now we have a bipartite graph $G=((R,C), V)$, since there is no edge between two rows nor between two columns.

A vertex cover of $G$ corresponds to a set of selected rows and columns such that each matrix entry of 1 is in at least one of selected rows or columns. So, the problem to find minimum number of covering plates is the same as determining the minimum vertex cover for graph $G$.

Thanks to Kőnig's theorem, for bipartite graph $G$, the number of edges in a maximum matching equals the number of vertices in a minimum vertex cover. So, the problem is shifted to find a a maximum-cardinality matching  of $G$.

There are many efficient algorithms that finds a maximum-cardinality matching in a bipartite graph, such as Ford–Fulkerson algorithm and Hopcroft–Karp algorithm. There are many existing implementations of them in various programming languages that can be easily searched.


Feasible to apply image "interlacing" concept to video streaming for smoother buffering? The current state of video buffering technology is to encode a video multiple times at different resolutions, then when your network speed changes you change which video you are buffering from.

Would it be possible to give this same user experience but implement something like the interlacing method used in PNGs or in progressive JPGs (Adam7 algorithm or similar) to make this work more efficiently?

The basic concept would be that the video is encoded once, at its highest possible quality. Then as your network speed changes you can only download a certain percent of a frame each second. Since the data would be interlaced you would see a lower quality frame from not having enough bandwidth to download it all in a timely fashion.

This would be particularly interesting to see used in video calls so that the video can't stutter, just get worse in quality.

Such a concept exists, for example in MPEG-4 Scalable Video Coding. It's complicated, it comes at a cost in coding efficiency (quality/bitrate), and I don't know of anything that supports it. However it's an area of active research and it might be the way of the future. Given the current state of the art, it's a lot more practical just to do multiple transcodes, segment, and switch between them.


If a language has any single occurrence of a letter, is it not context-free? From what I understand, the rules for CFL from my notes say:

If $L$ is a language and

• for all integers $N$,

• there is a string $w \in L$ of length greater than $N$ such that

• for all ways of writing $w$ as $uvxyz$ with ($v \neq \epsilon$ or $y \neq \epsilon$),

• there is an $i$ such that $u(v^i)x(y^i)z$ is not in $L$,

then $L$ is not context-free.

Does this mean that if we have any equation like:
$L = \{a^m b a^n \mid m = n\}$, then we can use this for example:
$u=a^m, v=b, x=a, y=a^{n-1}, z=null$

Where we any value of i greater than 1 would make the equation invalid?
This gives us $a^m(b^i)(a)((a^{n-1})^i)$ where $b^2$ means that there are two $b$'s, a string that's not accepted in that language.

However, in this case, then a Language $L = \{bcde \mid b = c = d = \epsilon\}$ could be proven as not context free. What am I misunderstanding here?

No: context free languages are closed under union, so for any CFL language $L$, we have $L \cup \{ a \}$ is context free, for any letter $a$.

The trick is that, when applying the pumping lemma, we don't get to choose the length $L$.

For a finite language, you just choose $L$ to be larger than any word in the language, and the pumping lemma trivially holds. (Remember, $a \implies b$ is true whenever $a$ is false).

As an intuition, you can see the "length" part of the lemma as being how long of words we need to get to a part of the automaton with loops, or a part of the grammar with recursion. So the small examples will in general not affect the pumping property.


Is $A=\{ w \in \{a,b,c\}^* \mid \#_a(w)+ 2\#_b(w) = 3\#_c(w)\}$ a CFG? I wonder whether the following language is a context free language:
$$A = \{w \in \{a,b,c\}^* \mid \#_a(w) + 2\#_b(w) = 3\#c(w)\}$$
where $\#_x(w)$ is the number of occurrences of $x$ in $w$.
I can't find any word that would be useful to refute by the pumping lemma, on the other hand I haven't been able to find a context free grammar generating it. It looks like it has to remember more than one PDA can handle.

What do you say?

Yes, $A$ is a CFL.  Use the context free language (with the notation $|x|_0$ meaning what you have as #0's in $x$):

$B=\{x\in \{0,1\}^*:3\cdot|x|_0=|x|_1\}$

and the morphism $f:\{a,b,c\}^*\rightarrow\{0,1\}^*:$ $ f(a)=0, f(b)=00, f(c)=1$

so that

$A=f^{-1}(B)$.

Since the CFL's are closed under inverse morphism, $A$ is a CFL.

The proof that $B$ is a CFL is a bit tricky.  Let's do it for the simpler case $C=\{x:|x|_0=|x|_1\}$, which can fairly easily be generalized to work for $B$ (or use another morphism).

Design a PDA which keeps track of $|x|_0-|x|_1$ at all points of the input, using the stack to keep track of the difference, having read $x$. The PDA accepts only when that difference is zero, that is, the stack is empty. The idea is to push a $0$ on seeing a $0$ on the input string, and pop a $0$ when seeing a $1$ in the input. The problem is that difference might go negative at times, and you can't pop an empty stack. In that case, however, the PDA goes into another mode (a different set of states) where it pushes a $1$ on seeing an input of $1$ and pops a $1$ on seeing an input of $0$.  So the second mode handles the negative case. It alternates between the two modes, accepting only if the stack if totally empty, that is, in-between the modes.

Or, you can do it with the grammar: $S\rightarrow 0S1|1S0|SS|\epsilon$.  That clearly generates only strings of C, but proving that it generates all of $C$ is a bit involved, but here's a sketch, by induction on string length.

An isosymbolic string $x$ (that is $|x|_0 = |x|_1$) could be null, in which case the $\epsilon$ production applies giving the basis of the induction.  Otherwise $x$ either starts and ends in different symbols (one end $0$ and the other end $1$), or the same symbol (both $0$ or both $1$). In the not-equal case, the last production to apply is either the $0S1$ or the $1S0$ production, allowing us to strip off the first and last symbols, getting a shorter isosymbolic string, so the induction applies.

In the equal case, as with the PDA, we keep track of $|y|_0-|y|_1$ as we move from left to right through prefixes $y$ of $x$. If the first and last symbols of $x$ are the same, it's fairly easy to see that that expression must be zero somewhere in the interior of the string. For example, if $x$ starts and ends with $0$, then after the first symbol the difference is $+1$ and before the last symbol it is $-1$, so it must have crossed zero in the interior. Split the string in two at that spot (reversing the $SS$ production) and the two halves, both shorter than $x$, are both isosymbolic.  So the induction works there too, and we are done.


Efficient algorithm for simple constraint satisfaction problem There are

$k$ Boolean variables $x_1, x_2, \dots, x_k$.
$m$ arbitrary subsets of these variables such that sum of each set equals to $1$ (i.e., only one variable is $1$, the others are $0$). E.g., one of $m$ constraints may be $x_1 + x_3 + x_5 + x_6 = 1$.
$n$ arbitrary subsets of these variables such that sum of each set is at least $1$ (i.e., at least one of the variables should be $1$). E.g., one of $n$ constraints may be $x_1 + x_6 + x_8 \geq 1$.

The solutions are not necessary, but I want to know how many solutions exist.

What is an efficient way to calculate the number of solutions?

There is unlikely to be any efficient algorithm.

Your first class of constraints are monotone exactly-1 CNF clauses.  Your second class of constraints are monotone CNF clauses.  The monotone part indicates that negated literals aren't allowed (you can't have $x_1 - x_3 = 1$ or $x_1 - x_4 \ge 1$).

Thus, in the special case where you have only type-2 constraints, the problem becomes #monotone-SAT.  Unfortunately, this problem is known to be hard.  #SAT is #P-complete, and monotone #SAT is #P-complete as well: it is #P-complete even for monotone 2CNF clauses (i.e., type-2 constraints with only two variables).   It is also known that it is NP-hard to approximate the number of solutions.  As a result, there is unlikely to be any  efficient solution unless the number of variables and constraints is fairly small.  Of course, your problem (with a mixture of type-1 and type-2 constraints) is potentially even harder.

So what can you do, to make the best of the situation?

One approach is to code this as an instance of #SAT, and try applying some off-the-shelf #SAT solver.  You can encode type-1 constraints in SAT using the methods described at Encoding 1-out-of-n constraint for SAT solvers.

Or, you could express the constraints as a BDD and then apply model-counting methods for BDDs.  I expect this to perform worse than a #SAT solver, but you could try it.

Another approach is to use an approximation algorithm.  There are existing algorithms for approximate-#SAT, though they too will hit a limit if you have too many variables and/or clauses.


Size of the instance of a problem I am unable to find a clear definition of term "size of the instance" when considering some algorithmic problem. I came accross a definition that said, that "Size of the instance corresponds to the size of the input array of numbers (in case the input is numeric) or size of the representation of the input."

Is the size of the instance simply size of the input? Or is it size of all the structures used in the algorithm (in that case, it would be the space complexity, right?).

Lets explain it on a specific problem:

a) I have an array of n numbers and I have to sort them in non-decreasing order.

So the size of the instance is n (those n numbers I have to sort - using for example BubbleSort). Is the size different for some other sort that uses some additional arrays during the sorting process?

b) Find strong components of a graph with n vertices and m edges.

Is it simply n+m? Or n+2m (if I represent edges by 2*m array)? Or do I have to consider all structures used in my algorithm (in this case it would be Tarjan, I guess).

Thank you for clarification!

Unfortunately, there is no single definition of the size of instance. But if there were, it would be the size of the input in bits. Whenever we talk about Turing machines, we have to slightly change this to the size of the input in tape symbols.

Things get more complicated for models like the RAM machine, in which numbers are opaque. If the input consists of arbitrary-precision numbers, then the inputs size is the number of input numbers. This is again a variation on the earlier definition, since in this model, every memory cell contains an entire number.

Summarizing, the size of the input is always the number of cell / tape positions containing the input, but the interpretation of this quantity depends on the model.

More concretely, in your first example, the input includes the input array of length $n$ as well as the number $n$, so the input length should be at least $n+1$. The model in question here is the RAM model. If it were the Turing machine model, the size of the input would depend on the size of the integers being sorted.

In your second example, it depends on the exact encoding. In the RAM model, you can encode a graph with $n$ vertices and $m$ edge using $O(m)$ cells. In the Turing machine model, you can encode a graph using $O(n^2)$ cells or $O((m+1)\log n)$ cells, using the dense and sparse encodings, respectively. Sometimes the input encoding affects the running time, and in that case the algorithm would expect the input in some specific encoding, and you would get the input length from this encoding. Notice that I don't bother calculating the exact input length – almost always asymptotics are enough.


Where can i find literature about the $\frac{4}{3}$-conjecture for approximation of the Metric TSP? In Graph-Theory there are many ways for efficient approximation-algorithms to solve the Metric TSP. The best solution seems to be the Christofides Heuristic with a factor of 1.5 to the optimal solution. My Teacher said, there would be the so called $\frac{4}{3}$-conjecture, which states: there might be a approximation solution for the metric tsp, that has only a $\frac{4}{3}$-factor.

But i cannot find any literature or further information about this assumption. Maybe you can?

On the Integrality Gap of the Subtour LP for the 1,2-TSP provides some relevant references and discussion in the introduction..


Complexity of multiplying two integers of size $n$ and $m$ The multiplication of two integers of size $n$ can be done in time $O(n \cdot \log n \cdot \log\log n)$ using FFT method.

If the two integers have different sizes $n$ and $m$, does a smaller upper bound using $n$ and $m$ exists ?

The multiplication of two integers of size $n$ and size $m$ in base-2 with $n\le m$ can be done in time
$$O(m\cdot\log n\cdot\log\log n)$$
where the product will be given in base-2 as well.

Here is a sketch of the simple idea to prove the above claim.

Let positive integer $a$ has $n$ digits and positive integer $b$ have $m$ digits in base 2. For simplicity, let $m=kn$ for some integer $k$.
$$b=\sum_{i=0}^{k-1}\sum_{j=0}^{n-1}b_{i,j}2^{in+j}=\sum_{i=0}^{k-1}2^{in}b_i$$
where $0\le b_{i,j}\le1$, $b_i=\sum_{j=0}^{n-1}b_{i,j}2^j$. In other words, $b_{k-1}\cdots b_1b_0$ is $b$ in base-$2^n$.
So $$ab= \sum_{i=0}^{k-1}2^{in}(ab_i).$$

Since both $a_i$ and $b_i$ have $n$ digits, the product $ab_i$ can be computed in $O(n\cdot\log n\cdot\log\log n)$ (using FFT method). Multiplying by factor $k=\dfrac mn$, we see that all summands in the above equality and hence $ab$ can be computed in $O(m\cdot\log n\cdot\log\log n)$. Note that the computation cost of various bookkeeping and additions is not substantial enough to invalidate that bound.

This idea of splitting the bits of the bigger number by the length of the bits of the smaller number is articulated here first in Yuval's comment. That idea is, apparently, folklore among users experienced in algorithms.

If we have a smaller bound for the multiplication of the integers of the same size, we will get a smaller bound for the multiplication of integers of different sizes accordingly. For example, an algorithm by Harvey and van der Hoeven gives bound $O(n\log n\cdot 2^{2\log ^{*}n})$. So we will have bound $O(m\log n\cdot 2^{2\log ^{*}n})$ accordingly.


What kind of formal semantics can describe HTML and CSS? What kind of formal semantics can describe HTML and CSS? Are there endeavours to do this. HTML/CSS layouts are espcially complex, so formalization can be of help.

I think the paper "Automated Reasoning for Web Page Layout" might be interesting to you. This paper defines CSS semantics in order to verify the layout formally. Look at section 3 of the paper for details. This would be one of the ways to express the CSS semantics, although this is a bit different from other semantics for programming languages.


Algorithm Design Patterns vs. Algorithm Strategies vs. Algorithm Design Techniques vs. Algorithm Design Paradigms I often encounter these terms, seemingly bearing same semantics and meaning. I'm almost sure they mean same - the types of Algorithms categorized based on their implementation strategy/paradigm.

Just wondering if I'm right and I get this correct, because, again - in different books/courses these terms are encountered in the same context. I'm kind of a very critical to the exactness of the terms I read.

Could you please confirm or reject my assumption?

Yes, they all refer to a categorization in terms of design paradigms (such as greedy, divide and conquer, dynamic programming, et cetera).


Matrix Inversion in the complexity class $P$ seen as a decision problem If the set $P$ is defined as the set of decision problems that can be solved by a deterministic Turing Machine in polynomial time, and matrix inversion using Gaussian elimination is $O (n^3)$, then how can I relate these two concepts to conclude that inverting a matrix is in $P$?

I suppose I need a way of converting a description of Gaussian elimination into a decision problem? Or maybe I am confused about the fundamentals

Gaussian elimination is an algorithm, you can’t frame it as a problem and thus it can’t be in $P$.

But matrix inversion itself is a problem and its decision version is as follows: “does matrix $M$ have an inverse?”

Gaussian elimination then is one possible way to prove that you can always answer that question in polynomial time, therefore matrix inversion is in $P$.


Efficient alternatives to inclusion-exclusion Say you've got a number of sets $S_1,...,S_n$ given and are supposed to calculate $\,\,\displaystyle\big|\bigcup_{i=1}^n S_i\big|$ .

The basic approach probably would be to use the classic inclusion-exclusion principle $\displaystyle\sum_{\emptyset \not= I \subseteq \{1, \dotsc, n\}} \left(-1\right)^{|I|+1}|A_I|$ , where $A_I = \,\,\displaystyle\bigcap_{i\in I}^n S_i$ .

However, inclusion-exclusion feels like it's terribly inefficient - after all, we need to sum over $\displaystyle\sum_{i=1}^n\binom{n}{i} = 2^n-1$ possible sets.

While I guess that there's no algorithm with polynomial complexity for this problem, I'm curious about alternatives that are more efficient (i.e. have polynomial run time in most cases), or are simply largely different.

I'd be thankful if you could name alternative algorithms or optimizations to inclusion-exclusion.

The particular problem I'm trying to write an algorithm for is unsatisfiability in Propositional logic for formulas in CNF. I.e. we have a finite set of atomic formulas $\{p_1,...,p_m\}$. Over these atomic formulas, the clauses of the CNF of the formula are built after these rules:
For ever atomic formula $p$, there may either appear $p$, $\lnot p$ or none of the two in the clause.

As the whole problem was either $NP$ or $co-NP$, there most likely isn't a polynomial algorithm, but I am struggling to just make it anyhow just a little bit more efficient than inclusion-exclusion (besides using ideas that have little to do with the algorithm itself like pure-literals or pure-clauses).

Yes, each set itself is discrete with each element in the set being specified. One example would be $\{  \{\bar A, B   \},\{B,C   \},\{ A,B  \} \}$. However, to fit the example, the initially given inclusion-exclusion algorithm would need to be modified.

This is the case as every clause in the CNF is a representative for a bigger clause, e.g. in the above example $\{\bar A, B   \}$ stands for
$
\{\bar A, B ,C  \}
\{\bar A, B  ,\bar C \}
$
 and $\{B,C   \}$ stands for
$
\{B,C, A   \}
\{B,C  ,\bar A \}
$

You get the actual set the representative represents by the following algorithm:

Be $M$ a set of the clause, and $S$ our output set. Add $M$ to $S$. Now repeat as long as possible:

  Find an atomic formula $A$ so that $A\notin K$ and $\bar A \notin
 K$ for some $K\in S$. Remove $K$ from $S$.  Add $K\cup \{A\}$
  and $K\cup \{\bar A\}$ to $S$.

Finally, delete all sets in  $S$ where $A,\bar A \in S$ for some $A$ and return $S$.

(An atomic formula in this case is simply any letter somewhere in $M$ without the bar (i.e. $A$ for $\bar A$))

This version of the algorithm however is at this point pretty dumb. You can improve it by not explicitly generating the actual sets and calculate it with the representants and applying some arithmetic instead.

It goes like this:
Let $A_1,...,A_n$ be our atomic formulas that appear in a set of clauses $\mathcal{K}$. For every $K\in\mathcal{K}$ you can calculate how many sets $K$ actually represents by counting the elements of $K$, let's name it $c$, and calculate $2^{n-c}$.
So, we calculate the sum all the way above, i.e. $$\displaystyle\sum_{\emptyset \not= I \subseteq \{1, \dotsc, n\}} \left(-1\right)^{|I|+1}|A_I|\text{ , where }A_I = \,\,\displaystyle\bigcap_{i\in I}^n S_i$$
just that we calculate $|A_I|$ not by $\big|\,\,\displaystyle\bigcap_{i\in I}^n S_i\big|$, but by calculating how many sets $\,\,\displaystyle\bigcup_{i\in I}^n S_i$ represents (with special case $|A_I|=0$, if $A_I$ contains $A$ and $\bar A$ for some atomic formula).

Unfortunately, if the only reasonable method to solve a problem is via inclusion/exclusion, it's going to take $\Omega(2^n)$ time. The reason for this is simple, there are $2^{n}-1$ sets we must inspect (if we don't, then we wouldn't have to do inclusion/exclusion!) So, there are no significant general improvements on inclusion/exclusion.

Asking for an algorithm to "have polynomial run time in most cases" is a rather vague empirical claim that is unfortunately hard to answer precisely and could have little value. A way to make this precise is a probabilistic algorithm. I'm not aware of any probabilistic variants of inclusion/exclusion, but I think that using another method than inclusion/exclusion would be better to create a probabilistic variant.

However, is inclusion/exclusion worthless? No. Often, inclusion/exclusion is used to obtain an algorithm that takes exponential time, but has only polynomial space usage. (sometimes, exponential space is a bigger problem in practice than exponential time!) For instance, the Hamiltonian cycle problem can be solved in $O^*(2^n)$ time but only polynomial space by inclusion/exclusion.

It could be the case that your specific problem has a more efficient solution, but that solution method then is likely very different from inclusion/exclusion.


Indexing billion domain names / strings I am trying to find any datastructure/algorithm suitable to index & retrieve domain names & its associated documents.

The records that need indexing will typically be like:

www.facebook.com, 123
stackoverflow.com, 1231
www.facebook.com, 124
stackoverflow.com, 3456
cdn.facebook.com, 4566
google.com, 903002
google.co.nz, 2342
google.co.in, 84992
google.com, 902002

The retrieval will involve getting all the document ids(not top K but all of them) for a given search.
Since it is content with a structure, people can query using part of domain names.

e.g. search for 'google' will lead to matching of all documents that have
google.co.nz,google.co.in & google.com associated with them.

Assumptions

As far as the distribution goes, less than 30% of the domain names will point to 80% of the documents.
The number of records being indexed will be in hundreds of billions
The index will most likely not fit into memory and will have to be stored in file-system

Initial thoughts

I thought of a solution where the domain names are tokenised(e.g. www.facebook.com gets tokenised into www,facebook,com,facebook.com,www.facebook.com) and hashed.
The hash value lookup leads to all the documents that are part of the hash
Some of the problems I see with this approach are

The values(document ids) are stored multiple times and some of the TLDs/commonly used subdomains(www) will have almost all the entries in them
Removing 1 entry will lead to updating multiple entries & their lists.
Hash collisions can affect the quality of results & hence hash function is quite vital to it
It won't be possible to address mis-spellings or substring search e.g. *goog*
The hash key will have to be 64-bit or more depending on the function

The question is what datastructure/algorithm to use to store & search for documents matching a given domain name.

Alternatively, if the above proposed solution is suitable, what can be a good hashing function given this context.

The standard solution is to build an index: a data structure that maps from search term to all of the records that match that search term.  Your index could be a hashmap or a B-tree, for instance.  In this case, the search terms are things like "google" or "facebook" or "facebook.com", and each one maps to a list of all records that match it.  Thus, facebook.com would be associated with two search terms ("facebook.com" and "facebook") and would be present in two of these lists.

You raised some concerns about this approach, but they are all manageable:

Yes, search terms like "com" will match many records.  You should decide whether searching for "com" is useful or not.  If it's not useful, don't include that in the index: build a list of "stopwords" (e.g., com, org, etc.), and don't include any of them in the index.  For instance, you might decide that the TLD part of a domain name is not one of its matching search terms.
Yes, inserting or removing one record will require updating multiple entries in the index.  But this just isn't that big a deal.  Most domain names have very few components: e.g., "www.google.com" will require changing 2 entries in the index (assuming you have blacklisted "com"), which just isn't that big a deal.
Hash collisions are dealt with using standard methods for building hash tables and just aren't that big a deal.  Or, you can use any other data structure, like a B-tree.
No, this can't handle mis-spellings.  Mis-spellings are an entirely different problem, which require a range of different solutions, and you should ask a separate question about that (but first, study Levenstein distance, metric trees, and data structures for spelling correction and answering nearest-neighbor search in the Levenstein distance metric -- there are a bunch of questions on this site that are relevant).
No, there is no reason that the hash key needs to be 64 bits.  The hash key needs to be at least the number of buckets in your hashtable.

I suggest you read some standard resources on building indices, e.g., in database textbooks, and read about how search engines work.  Those topics are well-studied and those techniques will be applicable to your problem.


Does adding S->SS in a context-free grammar change the language to its Kleene star? Let $L$ be the language generated by a context-free grammar whose start variable is $S$. Does adding $S \rightarrow SS$ in this grammar creating language $L^*$, why? What about grammars in Chomsky normal form?

As chi pointed out in the comment, since $\varepsilon\in L^*$ and $\varepsilon$ may not belong to the new grammar, so adding $S\rightarrow SS$ does not always generate $L^*$. It makes more sense to ask whether it generates $L^+$, so the following answer focuses on $L^+$.

General Form

Consider the following grammar:

\begin{align}
S&\rightarrow aSb\\
S&\rightarrow \varepsilon
\end{align}

It generates the language $L=\{a^nb^n\mid n\in\mathbb{N}\}$.

Now after adding $S\rightarrow SS$ in this grammar, the string $aababb$ can be generated by the grammar but it does not belong to $L^+$.

Chomsky Normal Form

Easy to see $L^+$ can be generated by the new grammar. Now for any string $s$ generated by the new grammar, we can prove $s\in L^+$ by mathematical induction on the depth of its parse tree. Consider the derivation process of $s$.

If the first derivation does not use the rule $S\rightarrow SS$, we can conclude $S$ does not show up in the following derivation since $S$ does not show up in the right hand side of a CFG of Chomsky normal form. As a result, $s\in L$.

If the first derivation uses the rule $S\rightarrow SS$, the strings generated respectively by the two $S$'s in the right hand side must belong to $L^+$ due to inductive assumption, thus $s$, which is formed by concatenating the two strings, also belongs to $L^+$.


Order of a pseudo code I am trying to find order of an bellow algorithm but I have no idea about, the problem like below

we have an array of $n$ element name $T[1...N]$ and we have that $0\leq T[i] \leq i$ and $T[i] \in \mathbb{Z}$ then if we have that $\sum_{i=1}^{n}T[i] = s$ what will be the order of following pseudo code

K := 1
for i = 1 to n do
    for j = 1 to T[i] do
        K := K + T[i]

I should prove it, but I just don't know what should I prove. is it $O(s)$ or $O(n+s)$ or $O(n)$ ? between these three one I need best guess. I just need some suggest to solve this. thanks

First I was thinking that it's $O(s)$ but if $T[i] = 0$ for $1 \leq i \leq n$ then then it should be $O(n)$. after that one of my friend said in fact $s = \frac{n (n + 1)}{2}$ so when we say that it's $O(s)$ in fact it's $O(n^2)$ so that the better answer is $O(s)$ because for some examples $O(n)$ is wrong, for example when $T[i] = i$ for all $i$. I think $O(s)$ should be right answer.

First note that $s \le \frac{n(n-1)}2$, equality need not necessarily hold.

Your observations are all correct:

The addition (and the head of the inner loop) is executed $O(s)$ times.
The head of the outer loop  is executed $O(n)$ times.
Neither $s\in O(n)$ nor $n \in O(s)$ holds for all possible inputs.

In this situation, there are multiple ways to give a bound that holds for all inputs:

You can use the fact that $s \in O(n^2)$ and give $O(n^2)$ as a bound for the algorithm,
you can say that the runtime is in $O(\max\{n,s\})$, or
you can say that the runtime is in $O(n+s)$.

Note that the latter two statements are acually equivalent (i.e. $O(\max\{n,s\})$ and $O(n+s)$ describe the same set of functions).