Can uniqueness of strings (each with an equal number of 1's and 0's) be decided in logspace? Let k be a positive even integer.

Given a list of (k choose k/2) k-sequences, each with an equal number of 1's and 0's, is distinctness decidable in logspace if we're only allowed to read the input once?

In more detail:

Let a sequence have k bits.

Let each sequence have an equal number of 1's and 0's.

There are (k choose k/2) such sequences.

Suppose I have a list of sequences.

Suppose there are (k choose k/2) sequences in the list.

Can we decide each sequence is distinct from the others in logspace?

If we can read the input multiple times, we can use two logspace counters - and ensure each sequence is not equal to the sequences that follow.

What if we're only allowed to read the input once?

Hint: let $n={k \choose k/2}$.  Consider the state of the algorithm after reading $n/2$ of the sequences.  How many possible states are there, that it could be in at that point?


Complexity of edit distance with block operations Consider the following problem. I have a pattern $P$ of length $100$ and a text $T$ of length $n$. I want to find the minimum number of operations to transform $P$ into $T$.  The operations are:

Insert a single character into $P$
Delete a single character from $P$
Substitute a single character in $P$ for another one
Move an entire substring of $P$ to another location in $P$

What is the time complexity of this problem?

What it looks like you are after is the Block Swap edit distance. Here is a paper outlining a polynomial time solution to this problem, An Edit Distance Algorithm with Block Swap . I cant recall the exact time complexity they give in the paper, however it is outlined in there.


Can Java be accurately described as statically and dynamically typed? Java seems to be categorized as a statically-typed language [1], but I'm wondering if it would be accurate to describe it as generally statically-typed but having some dynamic typing because of the run-time type checks performed when downcasts are performed.

Yes, that would be accurate.  Also, array writes involve a runtime type check, to deal with problems associated with covariant array types.


Proving a PDA with CFG Transitions recognizes Context Free Languages I'm working on a proof that deals with a modified PDA, which is identitical to a PDA, but with transitions: \begin{equation*}
a,b \to c
\end{equation*} where $a$ is a context free grammar, instead of just a symbol. The modified PDA then reads a prefix $w'$ of $w$, the suffix of the input stream, where $w' \in L(a)$.

I'm try to prove that the language recognized by this modified PDA is context free, but I'm really stuck. I have no idea how to even get started. If someone could point me in the right direction, I would really appreciate it.

Hint: Try replacing each such transition by an appropriate PDA.


How can the intersection of CFLs and REGs be CFL if REG is a proper subset of CFL? Intersection of CFL and regular is always CFL. But according to Chomsky hierarchy diagram, regular languages lie completely inside CFL.  So, as regular set is completely inside CFL set, their intersection should be regular right ?

Am I interpreting Chomsky diagram wrongly ?

You are confusing two different statements.

$\mathrm{CFL} \cap \mathrm{REG} = \mathrm{REG}$ or, equivalently,
 for all $L_1 \in \mathrm{REG}$ : $L_1 \in \mathrm{CFL}$.
For all $L_1 \in \mathrm{REG}$, $L_2 \in \mathrm{CFL}$ : $L_1 \cap L_2 \in \mathrm{CFL}$.

The first makes a statement on two sets of languages (aka language classes), the second makes one over (many) pairs of sets of strings (aka languages). So in mixing the two, you are creating a type error.

Also, you seem to suggest that if a language is context-free, it's not regular. That is false; we have $\mathrm{REG} \subsetneq \mathrm{CFL}$ (cf. 1.), so showing a language is CFL (using 2.) does not preclude it from being regular. Specifically, it's easy to find examples of a non-regular context-free and a regular language whose intersection is regular.


$\sqrt{n} = \Omega(3^{\log{}n})$ is not true? Why? Had this question on an algorithm exam. Can any one explain why
$\sqrt{n} = \Omega(3^{\log n})$
is false?

We'll start with some arithmetic, and assume the base of the logarithm to be $x$. First, remember the log law:
$$
\log_{a}(b) = \frac{\log_{c}(b)}{\log_{c}(a)}
$$
So
$$
\begin{array}{rl}
3^{\log_{x}(n)} &= 3^{\frac{\log_{3}(n)}{\log_{3}(x)}}\\
&=(3^{\log_{3}(n)})^{1/\log_{3}(x)}
&=n^{1/\log_{3}(x)}
\end{array}
$$
Whether $n^{\frac{1}{2}}$ is in big-omega of this then depends on what $x$ is.

If we make the right and proper computer science assumption that the base 2 logarithm is the only logarithm (that was a joke of course), then $1/\log_{3}(x)=1/\log_{3}(2)\approx 1.6$, which is certainly bigger than $1/2$.

You'd need $x\geq 9$ for the statement to be true.


A Recursive Formula For Generalized Josephus problem The Josephus Problem asks where to start taking out every kth person in the circle consisted of n people, such that you are the last "survivor".

The following recursive formula is given:
$$\begin{align}
f(1,k)&=1, \\
f(n,k)&=((f(n-1,k)+k-1) \bmod n )+1.
\end{align}$$

But this is not enough explanation, so I don't get where does it come from.

Can anyone help?

Let me explain the idea.
Assume that indices start from 0.
Take N = 6 and K = 3
So initial arrangement looks something like

  0->1->2->3->4->5->0.... like a circle.

After round 1 , '2' is eliminated .

  0->1->2->3->4->5->0->1...

  ....(k)->0->1->2->3->

    here (k) denotes the person is killed

Since we ought to start from the last position we killed, so lets look at the updated indices.

  Old Index |  New Index

    3 | 0

    4 | 1

    5 | 2

  and so on....
  looking closely we can easily see after each round

    OldPosition = (newPosition+k)mod N

Where N is the number of people left before the round started.

Also OldPosition signifies f(N,K)

and New Position signifies f(N-1,K) as one person has already been killed.

So putting it back to OldPostion = (newPostion+k) mod N
we get

f(N,K) = ( f(N-1,K)+ K ) mod N

But this is done only if u have indices starting from 0. If u want to rearrange for indices starting from 1, you can rearrange it to get the above result.

I found a beautiful paper on this

http://blue.butler.edu/~phenders/InRoads/MathCounts8.pdf

Hope this helps :)


What's a uniform shuffle? What does it mean exactly a "uniform shuffle" algorithm ?

Is this method considered a uniform shuffle ?

public void shuffle(Comparable[] a) {
    int n = a.length;
    int k, j;
    for (int i = 0; i < n; i++) {
        k = StdRandom.uniform(n); // k in [0, n-1]
        j = StdRandom.uniform(n); // j in [0, n-1]
        exch(a, j, k);
    }
}

A uniform shuffle of a table $a = [a_0, ..., a_{n-1}]$ is a random permutation of its elements that makes every rearrangement equally probable. To put it in another way: there are $n!$ possible rearrangements of $n$ elements and you need to pick one of them uniformly at random.

Many methods for shuffling seem uniform to people but are not and so it is common to see them implemented badly. For instance, shuffling by repeatedly exchanging two randomly chosen elements, as in the question, is not uniform and is also wasteful, as it generates twice as many random numbers as necessary.

A simple algorithm for a uniform shuffle is this:

import random
def shuffle(a):
    n = len(a)
    for i in range(n-1):
        j = random.randint(i, n-1)
        (a[i], a[j]) = (a[j], a[i])

This works in time $\Theta(n)$ as follows: assuming $a_0, ..., a_{i-1}$ are already shuffled, randomly select an element $a_j$ among the remaining $a_i, ..., a_{n-1}$ and exchange it with $a_i$.

To see that the result is uniformly shuffled, observe that initially every element has $\frac{1}{n}$ chance to land in place $0$ and $\frac{n-1}{n}$ to land in one of the remaining places $1, \ldots, n-1$. Therefore place $0$ is uniformly shuffled. In the next step, every element has probability $\frac{1}{n-1} \cdot \frac{n-1}{n}$ to land in place $1$, because this happens when it is not placed at 0 (probabilty $\frac{n-1}{n}$) and it is selected to be at place 1 (probability $\frac{1}{n-1}$). We may proceed inductively: an element lands in place $i$ with probability
$$\frac{n-1}{n} \cdot \frac{n-2}{n-1} \cdot \frac{n-3}{n-2} \cdot \cdots
  \cdot \frac{n-i}{n-i+1} \cdot \frac{1}{n-i} = \frac{1}{n}.$$
The first $i$ factors arise for an element not being placed anywhere among places $0, \ldots, i-1$, and the last one for it being chosen to be placed at $i$.


$\mathrm{\oplus P^{BPP}\subseteq BPP^{\oplus P}}$ Toda showed long ago that $\mathrm{PH\subseteq BP.\oplus P\subseteq BPP^{\oplus P}}$. That somehow describes the power of Parity Non-deterministic Computation.

If we swap the base and the exponent of the relativized class $\mathrm{BPP^{\oplus P}}$ to obtain yet another relativized one, namely $\mathrm{\oplus P^{BPP}}$. Then what have we obtained? A bigger or a smaller class?

You get a smaller one, in words $\mathrm{{\oplus P}^{BPP}\subseteq BPP^{\oplus P}}$. Indeed, the stronger claim that $\mathrm{{\oplus P}^{BPP}\subseteq BPP^{\oplus P[1]}}$ also holds.

Consider a language $L\in \mathrm{{\oplus P}^{BPP}}$, by definition, there exists an oracular non-deterministic machine $N$ and a $\mathrm{BPP}$ machine $M$ such that: on a given input string $x\in \Sigma^*$, we have that $x\in L$ if and only if $N^M(x)$ has an odd number of accepting paths.

Now, we may assume that by repetition and taking majority, the probability of $M$ to produce wrong answer is exponentially small.

The following language $\mathcal{O}$ is in $\oplus P$: on an input string $x\in\Sigma^*$ and a polynomially long random bit string $r$ (i.e. input data is $(x,r)$), simulate $N^M(x)$ where the random coin tosses using inside the oracle calls to $M$ are taken from $r$ one by one from left to right; accept only when the number of accepting paths is odd.

So, on a given input string $x\in\Sigma^*$, we guess a polynomially long random bit string $r$, call the oracle $L\in\oplus\mathrm{P}$ on input $(x, r)$and return the same answer.

Clearly, the probability that the random bit string $r$ makes $M$ produce wrong answer to any oracle call is extremely small. So, w.h.p the answer returned by the only one call to $\mathcal{O}$ is identical to the answer of $N^M(x)$.

Thus, $L\in\mathrm{BPP^{\oplus P[1]}}$. The claim that we obtain a smaller class holds.


Time complexity of function vs return value I came across following problem:

  Find the time complexity of below recurrence relation:

  $T(n)=\begin{cases}
 & 2T(n/2)+C; & n>1\\
 & C;&n=1 \\
\end{cases}$

The solution was given as follows

  $\begin{align}
T(n) & = C+2C+4C+...nC\\
     & = C (1+2+4+...+2^k)  \\
     & = C \left(\frac{1(2^{k+1}-1)}{2-1}\right) \\
     & = C (2^{k+1}-1)   \\
     & = C (2n-1)   \\
     & = O(n)   \\
\end{align}$

I feel above gives order of return value, but not the order of computation involved.

This function makes two recursive calls with argument $n/2$. Each of these two make another two recursive calls, making total 4, with argument $n/2/2=n/4$. Each of these four make another two recursive calls, making total 8, with argument $n/2/2/2=n/8$. And so on. Thus this form complete binary tree. This tree terminates when $n/2^h=1$. That is, when $2^h=n$.
$\therefore $ Height of binary tree $h=\log_2n$.
And the order of computation will be, number of nodes in the complete binary tree for height $h$ which equals $2^{h+1}-1=2^{\log_2n+1}-1=O(2^{\log_2n})$.

Am I correct with this final time complexity and the overall interpretation (of first being the time complexity of the return value and the one which I came up with, the time complexity of computation involved)?

Here is a correct version of your original problem.

  Find the time complexity of an algorithm which takes $T(n)$ time/operations to finish when the input size is $n$, where $T(n)$ satisfies the below initial condition,

  $$T(1) = C$$
  and the below recurrence relation,
  $$T(n) = 2T(n/2)+C\ \text{ if } n>1$$
  for some constant $C>0$.

Another correct version would be "Find the asymptotics in term of big $O$ or $\Omega$ notation for the function $T(n)$ that ...".

My answer is based on the above editions of the your original problem.

Your question and much more beyond have been answered in more generality in this reference question and answer and in particular, by the first case of the master theorem.

Assume throughout this answer and the question that $n$ is a positive integer and "/" is the integer division when it is applied to two positive integers as in Python/Java/C/C++/C#. Without these assumptions, $T(1.5)$ and $T(3)$ may not be defined.

Here is a correct computation.
Suppose $2^h\le n\lt 2^{h+1}$ for some nonnegative integer $h$.
\begin{align}
T(n) & = 2T(n/2) + (2^1-1)C\\
     & = 2(2T(n/4) +C)+ (2^1-1)C\\
     & = 2^2T(n/2^2) + (2^2-1)C\\
     & \cdots\\
     & = 2^hT(1) + (2^h-1)C\\
     & = (2^{h+1}-1)C\\
     & = \Omega(n)
\end{align}
The last equality stands from the fact that $Cn\le (2^{h+1}-1)C\lt 2Cn$.


Problem with Understanding "correlated attributes into a set of values of uncorrelated attributes" in PCA I am studying PCA. I have a problem in understanding the following concept:

What is meant by transforming "correlated attributes into a set of values of uncorrelated attributes" in Principal Component Analysis?

  Principal Component Analysis (PCA) is a mathematical procedure that uses an orthogonal transformation to convert a set of observations of possibly correlated attributes into a set of values of uncorrelated attributes called principal components.

as discussed in the article Weight by PCA (emphasis mine)?

It looks like you are using RapidMiner documentation as a medium to study. If that is case, then the best answer to your question and probably to some other questions of yours should be, I believe, a recommendation of related textbook, tutorial or lecture notes.

For the current question, I recommend you to read a tutorial on Principal Components Analysis by Lindsay I Smith, a tutorial that is self-contained and easy to read.

Now let me get back to you question, assuming we have gone through that tutorial up to and including section 3.1 or any equivalent materials.

  What is meant by transforming "correlated attributes into a set of values of uncorrelated attributes" in Principal Component Analysis"?

That just means, given existing $x$ axis and $y$ axis, and a set of data points with their coordinates (a set of observations of possibly correlated attributes), PCA will produce their eigenvectors and, using these eigenvectors as the new $x$ axis and $y$ axis as well as moving the origin to the center of the data points, obtain the new coordinates of those data points (principal components). The crux of the PCA is that the new $x$ coordinates and the new $y$ coordinates of the data points are 2 uncorrelated variables (uncorrelated attributes) in the sense that their covariance is 0. I am talking about 2-dimensional data for simplicity; PCA applies to 3 or more dimension the same way. In higher dimensions, the new coordinates of the data points are a set of variables every pair between which are uncorrelated.

All these concepts become very much alive and easy to understand once you have gone through several end-to-end computations. That is probably the fastest way to understand these concepts.


In ID3 algorithm, which attribute to choose if information gains are equal? In the ID3 algorithm for building a decision tree, you pick which attribute to branch off on by calculating the information gain. What happens if the calculated information gain is equal for two different attributes? Can you choose either attribute as the new branch?

Yes.  As @Aaron says, it's fine to choose an attribute arbitrarily.

Keep in mind that choosing the attribute with the highest information gain is just a heuristic.  It's a local greedy choice.  There is no guarantee that making the local greedy choice at each level will necessarily give you a global optimum (i.e., the best possible decision tree); indeed, it might not do so.  Instead, it is a heuristic that empirically seems to work pretty well in practice.  Resolving ties arbitrarily is in line with that heuristic.  There are already no guarantees when using this heuristic, so you're not giving up any theoretical guarantees in this way.  The primary focus of this heuristic is to make it efficient to build a decision tree (so you don't have to try all exponentially possible decision trees); resolving ties arbitrarily is in keeping with that focus.


Separation guarantee in Goemans Williamson algorithm In the original paper in Goemans-Williamson paper for max-cut, we need to sample a random vector r and
we output
$$
S = \{i : r^{T}x_{i} \geq 0\}
$$
where $x_{i}$ are column vector of a feasible solution of the SDP relaxation.

My question is are we guaranteed that there exists a certain $r$ such that the output is max-cut ?

Feige and Schechtman, On the optimality of the random hyperplane rounding technique for max cut, constructed a graph on which all $r$ only give an $\alpha$-approximation, where $\alpha$ is the worst-case approximation ratio of the Goemans–Williamson algorithm.


Linked list: advantages of preventing movement of nodes and invalidating iterators on add/remove C++ and Java include native classes for linked lists, C++ std::list and Java LinkedList

For C++ std::list, nodes can be "moved" within a list, or from list to list (if the lists are compatible), via std::list::splice(), which in turn is used by std::list::merge() and std::list::sort().

With Java's native LinkedList, there is no method like splice() to move nodes. Attempting to emulate splice() by using listiterator add(element) and listiterator remove() methods doesn't work because add or remove will invalidate all iterators for a list other than the iterator used to do the add or remove. The indexed based get(index), add(index, element) and remove(index) functions could be used, but have time complexity O(n).

As for C++ std::list versions of add and remove, note that std::list::insert() doesn't invalidate any iterators, and std::list::erase only invalidates iterators that point to deleted nodes, and depending on the compiler, iterator invalidation may only occur with a debug build, while a release build (meant for speed) will not invalidate any iterators.

I ran into this issue with an SE question about implementing a merge sort with Java's native LinkedList. With C++, merge sort can be implemented using iterators using either top down (uses stack to store iterators) or bottom up (uses small (26 to 32) array of iterators), both of which sort a list by moving nodes within the original list via splice(), using the iterators as pointers to sorted run boundaries.

Why does Java's native LinkedList not include a splice method?

Some background on C++ and Java linked lists:

C++ std::list is usually implemented as a doubly linked list. I'm not aware of any exceptions to this, but it's possible since the standard doesn't require specific implementations. std::list is a standalone class. Visual Studio implements std::list as a circular doubly linked list with a dummy node. std::list::end is an iterator to the dummy node.

Java LinkedList is always implemented as a doubly linked list, and part of the ArrayList family of classes.

I think this is due to the differences in the philosophy underlying the design of both programming languages. The C++ philosophy allows data structures to cause undefined behavior as soon as the user violates an invariant, while Java wants to avoid that in all cases. Java aims to raise exceptions when invariants are broken, or, when that can not be detected, to allow unspecified results when the invariant is broken.

This is not just a "C++ vs Java" difference, but a general difference in programming languages between the philosophies "undefined behavior can happen if you're not careful" and "undefined behavior can't happen, ever, and I'll try hard to report errors at runtime".

  Existing iterators, being pointers to nodes, are not invalidated by moving, adding, or removing nodes, as long as the iterators don't point to nodes that are later deleted.

The last part is crucial. C++ can say "iterators are invalidated", while Java wants to detect if those are used after they are invalidated (and raise an exception).

Detection can be expensive, and require each list to be aware of the iterators that are currently scanning the list, so that they can be checked and possibly flagged as invalid. Each list object should have a list of (weak references to) all the active iterators, and check whether they refer to deleted list cells.

Since this would impact performance, a simpler approach is to invalidate all the iterators every time the list is modified. This can be done by storing a single number in both list and its iterators. When the iterator is created, the number is copied from the list. When the list is modified, the number is incremented. When the iterator is used, we quickly compare the two numbers, and throw if they differ.

This is reasonably cheap, even if it's suboptimal because it invalidates all iterators, when that is not really necessary.

There is some middle ground between these two approaches. A Java library could avoid  undefined behavior, and allow the list to be in an invalid state when the invariant is broken, but allow iterators to remain valid in more cases (without trying to check this).
This means that all list methods can potentially throw, or produce invalid results, including failing to terminate. Debugging can be quite hard in such conditions, but that's the price to pay when invariants are not checked early at runtime.


Find distinict elements in an array in $O(n)$ time Given this pseudo-code that finds the number of distinct elements in the given array:
D(A) // A is an array of numbers
U_Size = 1
For i=2 to length(A)
                  U=?
  For j=1 to U_Size
    If A[j]=A[i]
     Then U = FALSE
      j = U_Size
   if U = TRUE
     Then U_Size = U_Size +1
         A[U_Size] = A[i]
return U_Size

Time complexity for that alogrithm is $O(n^2)$

I will need to write 2 new algorithms for the same purpose in $O(n)$ according to one of each of the conditions bellow:

let's say that the numbers are integers only and inside the range of [$10,10n$], without using any sorting method
Now, there is no given range of numbers, and I can use any sorting method I want

MY SOLUTION:
for the first condition, I tried using HashSet, but I think it has a
more sofisticated solution. My pseudo-code:
countDistinctNums(int A[], int n)
  hashSet hs = new Hashset
    for i=0 to n
    // add all the elements to the HashSet
      hs.add(A[i])

    // return the size of hashset as it consists of
    // all unique elements
  Return hs.size();

for the second one, a hash table will be the optimal solution but I
think also one of the linear-sorting methods will be good enough

My questions are:

Does HashSet is a good solution for one of the conditions ( or both )?
How do I implement an HashTable for the solution of the second condition?

For the first task you can use a solution similar to yours.
Let the input array be $A[1, \dots n]$. Create an array $B$ indexed with the integers from $10$ to $10n$ where each entry is a boolean value initially set to false. Then, for each input element $A[i]$, set $B[A[i]]$ to true. At the end of the above loop, return the number of indices $y$ such that $B[y]$ is true. This runs in $O(n)$ worst-case time.
Notice that, depending on how the hashtable is implemented, a hashtable-based solution is not guaranteed to have a worst-case time complexity of $O(n)$. Usually the hash-tables provided by the common programming languages only provide you with expected constant time operations.
Also, if don't have any other information on the values the the input integers, you can't use linear-time sorting algorithms (since their complexity depends on the range of the input values).
Anyway, your solution already works for the general problem in $O(n)$ expected time.
I don't think the general problem can be solved in $O(n)$ worst-case time. According to Wikipedia, there is a lower bound of $\Omega(n \log n)$ on the algebraic decision tree model, and randomness doesn't help.


Dynamic programming rectangular grid You are given a 40x40 grid. Each point of the grid is either 0 or 1. You are also given an infinite amount of 1x40 rectangular slabs.

How to find out the minimum number of slabs required to cover all the points which have a value 1?

NOTE: The 1x40 slabs can overlap with each other.

I'm assuming you're only allowed to use the 1x40 slabs horizontally or vertically. They thus cover entire rows or columns. We can rephrase your problem as minimum vertex cover in a bipartite graph. The bipartite graph consists of 40 row vertices and 40 column vertices. Connect two vertices if the corresponding point in the grid is 1. The minimum number of slabs needed to cover all 1s is exactly the minimum vertex cover in this bipartite graph. In bipartite graphs, minimum vertex cover equals maximum matching, so the problem is algorithmically feasible. In order to find a concrete algorithm, just look for algorithms for solving minimum vertex cover on bipartite graphs.


Proving that quantum circuits not involving entanglement are inefficient I heard in a video that it can be proven that quantum circuits not involving entanglement can be efficiently simulated on a classical computer; i.e., that there is no point to building quantum circuits not involving entanglement. I have heard this referenced elsewhere in google searches, but nowhere can I find this proof mentioned. What is the proof of this?

A general state of $n$ qubits can be written as follows :

$|\psi\rangle = \sum\limits_{x=0}^{2^{n-1}}\alpha_x|x\rangle$

Which means you need $2^n$ complex numbers to describe an arbitrary state of $n$ qubits.

A non entangled state on $n$ qubits can be written in the following way:

$|\psi\rangle = \bigotimes\limits_{i=1}^{n}\left(\alpha_i|0\rangle + \beta_i|1\rangle\right)$

Which means we only need $2n$ complex numbers to describe it. If we assume that we only deal with circuits such that two different qubits are never entangled, this property holds throughout the entire computation.

This is enough to see how to simulate the circuit, always remember the $2n$ complexes describing your non entangled state, and apply the desired operators on specific qubits (remember that it is garunteed that applying cnot will not result in entanglement).

That said, don't take this as evidence to the fact that quantum computing without entanglement doesn't extend classical computation in any way. For example, see this paper (Quantum computation without entanglement, Eli Biham et al). They reproduce some known results in the blackbox model (which are impossible on a classical computer) without entanglement.


Matching points between 2 polygons Given 2 polygons in a plane:

$A : ( (xa_1,ya_1), (xa_2,ya_2), ... (xa_n,ya_n) )$

$B : ( (xb_1,yb_1), (xb_2,yb_2), ... (xb_m,yb_m) )$

Is there a polynomial algorithm to compute a matching $M$ between the points in A and B, such that:

If $(xa_i,ya_i)$ is matched to $(xb_p,yb_p)$ and $(xa_k,ya_k)$ is matched to $(xb_r,yb_r)$, then for $i<j<k$ and $p<q<r$, $(xa_j,ya_j)$ is matched to $(xb_q,yb_q)$.
For $M:\{(i_1,j_1),(i_2,j_2)...\}$ and $|M|=min(n,m)$, $\Sigma_{k=1}^{|M|} distance((xa_{i_k},ya_{i_k}),(xb_{j_k},yb_{j_k}))$ is minimized.

This is a large topic, often called "geometric shape matching." Here is one survey that can lead to many specific algorithms:

  H. Alt and L. J. Guibas. Discrete geometric shapes: Matching, interpolation, and approximation. In J.-R. Sack and J. Urrutia, editors, Handbook of Computational Geometry, pages 121–153. Elsevier Science Publishers B.V. North-Holland, Amsterdam, 2000. doi:10.1016/B978-044482537-7/50004-8

If you have difficulty accessing that chapter, an earlier draft of the survey
is here: PDF download.


Using the Chomsky-Schutzenberger theorem to prove a language is not context-free? The Chomsky-Schutzenberger representation theorem states that a language $L$ is context-free iff there is a homomorphism $h$, a regular language $R$, and a paired alphabet $\Sigma = T \cup \overline{T}$ such that $L = h(D_\Sigma \cap R)$, where $D_\Sigma$ is the Dyck language over $\Sigma$. This is a necessary and sufficient condition for a language to be context-free, so in principle it seems like it should be possible to show that a language is not context-free by showing that there are no valid choices for $h$, $\Sigma$, and $R$ satisfying the theorem.

This earlier question talks about approaches for showing that a language is not context-free, but doesn't mention this approach. Additionally, I can't seem to find any constructive examples of proofs of non-context-freeness along these lines.

Are there any known examples of languages that have been shown not to be context-free by means of the Chomsky-Schutzenberger theorem?

here is a construction not exactly as requested but related/ somewhat similar. the contrapositive of the Chomsky-Schutzenberger theorem can be used to prove a language is not unambiguously CFL. it describes the close connection of the construction to generating functions that yields key insight into the problem.

see ORDINARY GENERATING FUNCTIONS OF CONTEXT-FREE
GRAMMARS / TANNER SWETT, EDWARD ABOUFADEL, sec 2.6 p 6


Is the following langauge in $P$ or $NPC$ Assuming $P \neq NP$ Is the following langauge in $P$ or $NPC$:
$L=\{\langle\phi\rangle\mid\phi$ is a 3CNF formula with an assignment satisfying at least half of the clauses$\}$

The first thing I tried to do is to find a 3CNF formula $\phi$ such that  $\phi \notin L$ and I haven't managed to do so. Is it possible that simply all 3CNF formulas have such an assignment (and so the problem is in $P$) or am I missing something ?

Hint: Take a valuation $v$ satisfying less than half of the clauses. What about $\bar{v}$ the valuation such that $\bar{v}(x)=\neg v(x)$?


What is induced matching, maximum induced matching and mim-width? I understand the concept of induced subgraph, but could not understan what induced matching is. As appears in this paper, it is defined as

  A matching in a graph is an induced matching if it occurs as an
  induced subgraph of the graph.

However, in this paper, there is a slightly different definition:

  A matching in a graph is a set of edges, no two of which meet a common
  vertex. An induced matching M in a graph G is a matching where no two
  edges of M   are joined by an edge of G.

Thus, I am confused since there are no example figures.

Also, there is a term called mim-width, which is maximum induced matching width and few no none examples exist in the literature.

Could you please give some examples for me to clear things out?

Both definitions are the same. An induced matching $M$ in $G$ consists of a set of edges such that $G|_{V(M)} = M$, that is, the subgraph of $G$ induced by the vertices of $M$ is exactly $M$. This is the first definition.

Now it is always the case that $G|_{V(M)} \supseteq M$, so $M$ is an induced matching if $G|_{V(M)}$ contains no other matching, that is, $G$ contains no edge connecting vertices in two different edges of $M$. This is exactly the second definition.

I have never heard of mim-width, so it is safe to assume that it will be defined in any paper which uses it. However, it probably refers to the size (probably number of edges) of the largest induced matching in the graph.


Query Logs and evaluation of search engines I'm taking a course about Information Retrieval and we had a quiz involving the evaluation of search engines.

We had a problematic question regarding "Query Logs" (basically recording the queries that users searched in the past and their response for the queries e.g links clicked), and I hope you can help me figure out the answer:

Using query logs can improve the retrieval efficiency of the search engine by:

A. Learning common typos in queries
B. Learning the connection between pages the users clicked as the result of different queries
C. Saving popular queries in a cache
D. A + B + C
E. A + B + C doesn't affect the efficiency of retrieval
F. The Collection of query logs can't affect the efficiency of retrieval

I circled option D (A+B+C) and I was wrong.

My Lecturer refuses to reveal the correct answer - I can appeal about her decision but I want to be certain I'm correct.

The explanation for my answer: the question talked about improving the retrieval efficiency, and to the best of my knowledge retrieval efficiency is the time measured from when the user clicked "Search" until the user received the results back.

Therefore, I think A is correct because if we learn common typing mistakes in queries we can create a dictionary of those common errors and create spell correction algorithms. For example if many users typed "bast" instead of "best", we can use a data structure similar to a cache. (However, this might require an enormous amount of memory, but the question didn't mention memory efficiency)

I think C is correct because we can save the results of the popular queries in a cache instead of using the (fairly slow) posting file.

B is the only option that I'm not sure why is correct, but I assumed that if A and C are correct, B can be correct.

Could you please tell me what you think about the question and my answers?

Thank you!

I would have selected option C.

I don't think option A is correct.  We probably can learn common typos, but that doesn't affect the time to process a search query, and it's not clear how you'd use that to speed up search queries.  (I'm assuming that "time to process a search query" is what is meant by "retrieval efficiency".)

Similarly, I don't think option B is correct.  We probably can learn the connection between different pages that a user clicked, but that doesn't appear to affect the time to process a search query, as far as I can tell.


Largest subset such that for every two elements one of them divides the other So the problem states:

  An array of $N (1 \leq N \leq 2000)$ natural numbers is given. Find
  the cardinality of the largest subset of that array such that for
  every two numbers $A$ and $B$ either $A|B$ or $B|A$ (or both).

I know you don't like it when people post questions without trying anything, but the only thing I can possibly think of (that would work) is brute force, which would mean exploring every possible subset and then checking the given condition, again, by brute force.

But since the time complexity of subset exploration is $O(2^N)$, and $N = 2000$ in the worst case, this solution becomes pretty useless.

Other thing I had in mind was some kind of divide and conquer algorithm, similar to merge-sort. But I can't think of a way I'd use the results of two (left and right) subarrays to compute the result for their union.

So, any ideas?

Thanks.

EDIT:
The brute force solution I've made that seems to be working (C++):

int largestSubset(const vector<int>&arr, int i, vector<int>&subset, int j){
    if(i == arr.size()){
        //brute force check
        for(int k = 0; k < j; k++){
            for(int s = k + 1; s < j; s++){
                if ((subset[k] % subset[s] != 0) && (subset[s] % subset[k] != 0)){
                    return 0;
                }
            }
        }
        return j;
    }

    //skip the i-th element
    int count1 = largestSubset(arr, i+1, subset, j);
    //include the i-th element
    subset[j] = arr[i];
    int count2 = largestSubset(arr, i+1, subset, j+1);

    return  max(count1, count2);

}

You can do it in $O(N^2)$ like that:

First, sort your array $L$ in increasing order.

Then, for $i \in \{0,\ldots,N-1\}$, let $M[i]$ denote the cardinality of the largest valid subset $S$ such that $L[i]$ is the largest element of $S$.

We can compute $M[i]$ in a dynamic programming fashion:
$$ M[0] = 1$$
$$\forall i \;\; s.t.\;\; 0<i<N-1:
M[i] = 1 + \max_{0\leq j < i\\L[j]\ |\ L[i]}\{M[j]\}$$
(where the max is taken to be equal to $0$ if no $L[j]$ divides $L[i]$)

To see that, notice that it is clear that $M[i] \leq 1 + \max_{0\leq j < i\\L[j]\ |\ L[i]}\{M[j]\}$ as the second largest element in the corresponding subset must divide $L[i]$. Moreover, the fact that the second largest element $L[j]$ divides $L[i]$ and that the subset without $L[i]$ is valid is enough to guarantee that the subset with $L[i]$ is valid, as all elements in the subset are compatible between them and all divide $L[j]$ and thus divide $L[i]$. Thus the dynamic programming formulation is correct.

Then, the value you are looking for is simply the maximum over all $M[i]$'s.

This leads directly to a $O(N^2)$ algorithm as the sorting can be done in $O(N\log(N))$, and finding the maximum in $M$ is done in $O(N)$.


Effectiveness of TLB This is a book question:

  Suppose that a machine has 48-bit virtual addresses and 32-bit
  physical addresses.

  Suppose this same system has a TLB (Translation Lookaside Buffer) with
  32 entries. Furthermore, suppose that a program contains instructions
  that fit into one page and it sequentially reads long integer elements
  from an array that spans thousands of pages. How effective will the
  TLB be for this case?

Answer: I think that we cannot know the effectiveness of the TLB because we do not know the number of instructions the program has. I hope I make sense.

source:
Modern Operating Systems
Question 15, chapter 3
ISBN-13: 978-0-13-359162-0

Assuming size of long is $32$ bits, each page frame in physical memory exactly contain $1$ long number, therefore in $TLB$ at particular instance of time $31$ long integers would be present. Hence, $1$ page fault in every $32$ memory accesses. Now, I am not sure what is criteria of effectiveness here. But $1$ per $32$ memory access seems pretty good.


is this language regular and why pumping lemma doesn't work? I was told that this language is regular but as I can show below, pumping lemma is not working for it. What am I doing wrong? Is this language really regular? Why?

It's a "trick" question. The language is regular because
\begin{align*}
\{aba^{\mathrm{R}}\mid a,b\in\{0,1\}^*\}
    &= \big\{\varepsilon b\varepsilon^{\mathrm{R}}\mid b\in\{0,1\}^*\big\}
       \cup \big\{a b a^{\mathrm{R}}\mid a\in\{0,1\}^+,\ b\in\{0,1\}^*\big\}\\
    &= \{0,1\}^*
       \cup \big\{a b a^{\mathrm{R}}\mid a\in\{0,1\}^+,\ b\in\{0,1\}^*\big\}\\
    &= \{0,1\}^*\,.
\end{align*}


Computationally 'hard' polynomial-time reduction to other NP-complete problems / Hierarchy of NP-complete problems As we all know there exist plenty of polynomial-time reductions from one NP-complete problem to another. Are there any NP-complete problems that have a rather large polynomial bound for reductions to other NP-complete problems, like a poly-time sub-hierarchy of NP-complete problems...?

E.g. lets assume I have NP-complete problem A and B. They are reducible to each other in lets say at most $n^3$. Does there exist a NP-complete problem such that the best known reduction to both A and B (and all other) is, lets say, $n^{100}$.

Question: Are there (non-special-tailored) NP-complete problems with a large best known (deterministic?) polynomial-time reduction?
Question: Is there a upper (deterministic?) polynomial bound for polynomial-time reductions between NP-complete problems

(There is a question here asking for a hierarchy of NP-complete problems but with a different base-problem, so solution does not really answer my question:
Understanding reductions: Would a polynomial time algorithm for one NP-complete problem mean a polynomial time algorithm for all NP-complete problems?)

There are no upper bounds on the complexity of polynomial-time reductions between $\mathrm{NP}$-complete problems, other than that they're in polynomial time.

Let $\mathrm{NP}_k = \mathrm{NTIME}[O(n^k)]\setminus\mathrm{NTIME}[O(n^{k-1})]$. By the nondeterministic version of the time hierarchy theorem, there are problems in $\mathrm{NP}_k$, for all $k$.

Let $X$ be any $\mathrm{NP}$-complete problem. There is some $t$ such that $X\in\mathrm{NTIME}[n^t]$.  Consider some problem $L\in\mathrm{NP}_k$ for some $k>t$.  If we have a reduction from $L$ to $X$ that runs in time $n^r$, then we can solve an instance of $L$ in time $O(n^{rt})$ by first running the reduction, which creates an $X$-instance of length $O(n^r)$, and then solving that instance in time $O((n^r)^t)$.  This contradicts the nondeterministic time hierarchy theorem if $k>rt$.


Understanding connection between length of codeword and hamming distance in Hamming code I came across following in Huffman coding:

  Minimum Hamming distance to correct up to s errors is $2s + 1$ because that way the legal codewords are so far apart that even with $s$ changes the original codeword is still closer than any other codeword.

Then I came across following:

  Consider dataword length of $m$ bits, codeword length of $n$ bits. So redundant check bits will be $n-m = r$. Each of the $2^m$ legal messages has $n$ illegal codewords at a distance of $1$ from it. These are formed by systematically inverting each of the $n$ bits in the $n$-bit codeword formed from it. Thus, each of the $2^m$ legal messages requires $n+1$ bit patterns dedicated to it. Since the total number of bit patterns is $2^n$, we must have $(n+1) 2^m ≤ 2^n$.

Using this information, I took $m=4$ and found that to meet above equation, $n \ge 7$. So with $n = 7$, I prepared Huffman code for $m = 4$ as shown in the image ($d$ are data bits, $c$ are check bits):

The code has hamming distance of 3 which confirms with $2(1)+1 = 3$ as required to correct 1 bit errors.

Q1. But then, how satisfying $(n+1) 2^m ≤ 2^n$ also ensures hamming distance is 3?

Q2. Also what will be equation if I want to correct $k$ bit errors? Will it be $(\binom{n}{k}+1)2^m\leq 2^n$?

The answer to both questions is the sphere-packing bound.

Consider a binary code on $n$ bits with minimum distance $2d+1$ and $M$ codewords. Imagine surrounding each point of the code with a ball of radius $d$, consisting of all points at distance at most $d$ from the point. These balls must be disjoint: if the balls corresponding to $x,y$ contain some point $z$ in common (note that $z$ need not be in the code), then $d(x,y) \leq d(x,z) + d(y,z) \leq 2d$, contradicting the stated minimum distance. Each ball contains $\binom{n}{\leq d} := \sum_{r=0}^{d} \binom{n}{r}$ points, and so
$$ M \times \binom{n}{\leq d} \leq 2^n. $$
This is because there are $M$ disjoint balls, each containing $\binom{n}{\leq d}$ points, while in total there are $2^n$ binary strings of length $n$.


Does a binary code with length 6, size 32 and distance 2 exist? The problem is to prove or disprove the existence of $C$, s.t., $|c| = 6,\forall c\in C$; $|C| = 32$; $d(c_i,c_j)\geq2,1\leq i<j\leq32$. ($d$ stands for hamming distance)

I tried to construct a satisfying code. The best I can get is to let $C = C'\times C'$, a concatenation of $C' = \{000,011,110,101\}$, which is of size 16. 32 happens to be the theoretical upper bound of the size, now I don't know what to do next so as to solve the problem.

Yes, there is such a set. You are actually on the right track to find the following example.
Let $C = \{c : |c|=6 \text{ and there are even number of 1's in c}\}$. You can check the following.

$|C|=32$.
$d(u,v)\geq2$ for all $u,v\in C$, $u\not=v$. (In fact, $d(u,v)=2$ or 4 or 6.)

Here are four related exercise, listed in the order of increasing difficulty. As in the question, only binary code is concerned.
Exercise 1. Give another example of a set of 32 words of length 6 and pairwise distance at least 2.
Exercise 2. Show that there are only two such sets, as given in the answer and in the exercise 1.
Exercise 3. Generalize the above to words of any given length and pairwise distance at least 2. (Hint, $32=2^{6-1}$.)

Exercise 4. (further generalization stated in Yuval's answer) If $A(n,d)$ is the maximum size of a code of length $n$ and minimum pairwise distance $d$, then $A(d,2d)=A(n-1,2d-1)$.


How do I efficiently checking if a string matches any substring in a collection I have a collection of substrings

"this" "is" "a" "antelope"

I need to look at any given string and answer the question "Are any of the given substrings in this string"

So my input string might be

"issue"

Which would be a match because "is" is a substring of "issue"

My first stab at this, I incorrectly turned my collection of substrings into a trie.  That got me nowhere fast as it answered the inverse "is the input string a substring of the given collection".

Is there some algorithm or data structure I can transform my collection into to efficiently answer this question?  I mean, I could do the simple brute force "check the input against every substring" method, but it seems like there is a better way.

In my given example, I would expect that "antelope" would never be checked because "a" covers every case that antelope would. I may even expect that "is" would remove "this" since every case that "this" would find a match "is" would as well.  So it seems like eliminating longer substrings with shorter ones would yield some better performance.

I'm rambling... Anything I should be looking into?

I think the Aho-Corasick algorithm is your best bet here. The algorithm is designed to solve the set matching problem (essentially the one you've defined), in which you want to determine which elements of a set of substrings, L, can be found in a longer string, S.

It runs in time $O(n + m + z)$, where $n = \sum \limits_{l \in L} |l|$ (the total combined length of the substrings in $L$), $m$ is the length of S, and $z$ is the number of matches of $L$ in $S$.


Recurrence relation T(n) = 3T(n-1) + n I'm trying to solve the recurrence relation T(n) = 3T(n-1) + n and I think the answer is O(n^3) because each new node spawns three child nodes in the recurrence tree. Is this correct? And, in terms of the recurrence tree, is there a more mathematical way to approach it?

Using the substitution method, we find out that
$$
\begin{align*}
T(n) &= n + 3T(n-1) \\ &=
n + 3(n-1) + 3^2T(n-2) \\ &=
n + 3(n-1) + 3^2(n-2) + 3^3T(n-3) \\ &= \cdots \\ &=
n + 3(n-1) + 3^2(n-2) + \cdots + 3^{n-1}(n-(n-1)) + 3^n T(0) \\ &=
\frac{3^{n+1}-2n-3}{4} + 3^nT(0) \\ &= \Theta(3^n).
\end{align*}
$$
Even without doing the full calculation it is not hard to check that $T(n) \geq 3^{n-1} + 3^n T(0)$, and so $T(n) = \Omega(3^n)$. A cheap way to obtain the corresponding upper bound is by considering $S(n) = T(n)/3^n$, which satisfies the recurrence relation $S(n) = S(n-1) + n/3^n$. Repeated substitution then gives
$$
\frac{T(n)}{3^n} =\sum_{m=1}^n \frac{m}{3^m} + T(0).
$$
Since the infinite series $\sum_{m=1}^\infty \frac{m}{3^m}$ converges, this implies that $\frac{T(n)}{3^n} = \Theta(1)$ and so $T(n) = \Theta(3^n)$.


How to express a type that represents an associative array whose keys determine the type of the value? I'm fairly new to type systems and theory, so I would appreciate some guidance in a problem that sparked my interest.
I would like to understand what type system features are required so a compiler can enforce that a given key will return a value of the same type as the one the key was associated with in the first place.
A practical version of my problem is to declare a Map in TypeScript that allows a developer experience like in the pseudocode below:
const cache =  new  Map<K,  V>()

cache.set('Foo',  Error('R'))

cache.set('Bar',  1)

cache.get('Foo')  // Return value typed as Error.

cache.get('Bar')  // Return value typed as number.

cache.get('Qux')  // Compilation error.

What would the type of K and V be?

What happens if I try to get Bar before it has been set? If you expect a compilation error, then you are not talking about a single type, but instead a sequence of types, where the type changes after each call to the set method. Look into 'strong update' and 'linear types'.
Why not just use a record type?
type MyRecord = { Foo : Error, Bar : number }


PDA for $L= \{w : n_a(w)+n_b(w) = 2n_c(w)\}$ I'm pretty new to the PDA topic.

How do I construct an NPDA for the language $$L= \{w : n_a(w)+n_b(w) = 2n_c(w)\}.$$

I've tried all the possibilities, but I still somehow end up accepting all words.

The idea is to store a counter $n_a(w) + n_b(w) - 2n_c(w)$ in the stack. If this number is positive, say $x$, we want to have $x$ many P's on the stack (and nothing else). If this number is negative, say $-y$, we want to have $y$ many N's on the stack (and nothing else). Otherwise we want to have a special indicator $O$ on the stack. At the end, we check that the stack consists of $O$.

I'll let you work out the details.


Longest Common subsequence theorem in CLRS In CLRS in the dynamic programming chapter, there  is a theorem about the longest common subsequence prefix that states the following:

Theorem Let the $X=(x_1,x_2,\dots,x_m)$ and $Y=(y_1,y_2,\dots,y_n)$ be sequences, and let $Z =(z_1,z_2,\dots,z_k)$ be their LCS.
If $x_m = y_n$, then $z_k = x_m = y_n$ and $Z_{k-1}$ is an LCS of $X_{m-1}$ and $Y_{n-1}$.

The theorem has two more points but I am interested particularly in the first point, I don't understand why we only consider $Z_{k-1}$ to be the LCS of $X_{m−1}$ and $Y_{n−1}$ and not $Z$ to be the LCS of all of $X$ and $Y$, if already the last element in all sequences match.

The theorem is used to construct a recurrence relation for computing the LCS of $X$ and $Y$. The first point states that if $x_m = y_n$, then one possible LCS of $X$ and $Y$ is an LCS of $X_{m-1}$ and $Y_{n-1}$ together with $x_m$. This is one of the cases in the recurrence relation.

You ask why we are not considering $Z$ as the LCS of $X$ and $Y$. There is no need to consider this, because this is already assumed to hold in the premise of the theorem. Given that, we want to deduce other information, which will later enable us to compute the LCS recursively.


Map overlay, any algorithm for face updating step? In chapter 2 of this book the map overlay algorithm, which takes as inputs two doubly connected edge lists, is explained. "Basically" a line intersection algorithm allows to update both the half edges records and the vertices records. After such step the detection of boundary cycles is applied, and later a graph is built, where each connected component represents a new face record. It is explained how to detect whether a boundary cycle is clockwise or not, but I'm not sure how an overall module that implements this part should work. Say I have a DCEL where the face records are not valid, but both the half-edges and the vertices are, do you know any detailed algorithm the actually build the graph? Even a pseudocode is fine.

I can understand how to implement the boundary cycles detection, I would iterate through the half-edges list, navigate through the "next" record, remove such record from the list and when I reach the initial half-edge I would go to the next half-edge of the list and repeat. I would put such sub list of half edges into another list so I would have a list of boundary cycles. I would also label each element of the boundary cycles list as "clock wise" or "anti-clockwise" based on the trick the book explains. Once I have such a list how do I figure out what boundary cycles are incident to the same face? In practice what's the test applied?

Before we 'fill in' the value for the new faces at the halfedges,  we wait until the rest of the algorithm is finished, so we know which faces are still present in the end and only have to traverse every edge once. We do this by getting the halfedge that we have considered as a 'representative' and traverse the proper cycle until we return at our edge. So, our complexity is bounded by the sum of the faces and the edges, instead of their product, giving $O(n)$ instead of $O(n^2)$.

That book tends to ignore the subtleties that arise in dealing with DCELs. At first, it seems strange that updating faces would take only $O(n)$ time, since the face of the edge would get updated multiple times. Here, $n$ is 'the complexity of the subdivision', i.e. the sum of the edges and faces of the DECL.

However, since we only want to store the final face value at the end, we wait with the updating the face values of the half-edges until we have filled in everything else. We can store the new value at only one half-edge, which will be the 'representative' of that face and maintain a list of those half-edges.

Then, at the final step, we fill in the face values for the cycles of the stored representative edges, by traversing the cycle associated with the half-edge until we return to the edge where we started and remove a (different) representative if we encounter it, since this means that the face it belonged to no longer exists. By doing so for every representative in the correct order (i.e. from the last created face to the first), we avoid traversing cycles for faces that do not occur in the final DECL. So, we are able to check every face and visit all edges after that, which means we get the required complexity of $O(n)$.


Subgraph isomorphism reduction from the Clique problem I was trying to understand the Wikipedia proof for NP-completeness of subgraph isomorphism by reduction from the clique problem. It's really just one sentence:

  Let $H$ be the complete graph $K_k$; then, the answer to the subgraph isomorphism problem for $G$ and $H$ is equal to the answer to the clique problem for $G$ and $k$.

In the subgraph isomorphism problem, $G$ and $H$ are not constrained in any way (e.g., $H$ is not constrained to complete graphs). Yet, in the proof, Wikipedia just states "let $H$ be the complete graph $K_k$". It's not defined what $K_k$ represents or why $H$ suddenly becomes constrained to a complete graph.

The decision version of the clique problem asks whether a given graph $G$ contains a complete graph with $k$ vertices as subgraph. The wikipedia article just explains why the decision version of the clique problem is a special case of the subgraph isomorphism problem. Namely if the graph $H$ is the complete graph with $k$ vertices, then the answer to this special subgraph isomorphism problem is just the answer to the decision version of the clique problem.

This shows that subgraph isomorphism is NP-hard, since the clique problem is NP-complete. But the subgraph isomorphism is obviously in NP, since it a given monomorphism from $H$ to $G$ can efficiently be checked to be a monomorphism. So we can conclude that subgraph isomorphism is NP-complete.


Find the bitwise AND of a subarray closest to given number It was a question I was asked in an online assessment for a company.
Please help me in this question-

Given an array, $A$ of size $N$ and an integer $P$ , find the subarray $B = A[i \dots j]$ such that $i \leq j$ and compute the bitwise value of subarray elements i.e say $K = B[i] \mathbin{\&}B [i+1] \mathbin{\&} \cdots \mathbin{\&}B[j]$.
Output the minimum value of $|K-P|$ among all values of $K$.
Size of array: $1 \leq A.\mathrm{size} \leq 100000$
$0\le A[i]\le 10^8$

I could only think of brute force.

Let f (i, j) = AND ($A_i, A_{i+1}, ..., A_{j-1})$ for $0 ≤ i < j ≤ n$. $f (i, j)$ has the property that whenever $i ≤ i' < j' ≤ j$, $f (i, j) ≤ f (i', j')$.

We also have $f (i, j)$ = AND($(f (i, k), f (k, j)$) for any $0 ≤ i < k < j ≤ n$.

Because of these properties, we get an algorithm slightly better than brute force as follows:

Keep track of the optimal solution so far, initialising with f (0, 1). For 0 ≤ i < n: If $a_i ≤ P$ then check if f (i, i+1) is a better solution. Otherwise, find the largest j such that f (i, j) ≥ P; it may be that j = n. Check if f (i, j) is a better solution. If j < n then check if f (i, j+1) < P is a better solution.

How to find the largest j in O (log n), making the total time O (n log n):

We start by building some tables, calculating all f (i, i+2) for even i, f (i, i+4) for i multiple of 4, f (i, i+8) for i multiple of 8. This is done in O (n) since there are about n values which can each be calculated with a single AND operation.

To find the largest j, we start with j = i+1, f (i, j) = a [i]. If j < n is odd then we can calculate f (i, j+1); if the result is ≥ P then we replace j with j+1, which makes j even. Then if j < n is an odd multiple of 2 we can calculate f (i, j+2); if the result is ≥ P then we replace j with j+1, which makes j a multiple of 4, and so on. This ends with j being a multiple of $2^k$ for some k. Now we try to increase j by $2^{k-1}$, $2^{k-2}$, ..., 4, 2, 1 if the increased j is ≤ n, and f (i, j) ≥ P. The total cost is O (log n) operations.


The height of 5-balnced tree is O(logn) Binary tree with external leaves is a 5-balanced tree if the path from the root to the farthest external leaf is no more than 5 times as long as the path from the root to the nearest external leaf, and if his right and left subtrees are 5-balanced too. Show that the height of such a tree is O(logn).

I was trying to prove it by finding the minimum number of nodes in such a tree with height h and then saying that the height of the tree is at most the log of this number, but I'm not sure how to find it.
Thanks

Suppose that the tree has depth $D$. Then all leaves are at distance at least $D/5$ from the root, which means that the tree contains the full binary tree of depth $D/5$ as a subtree. This implies that $n \geq 2^{D/5}$, and so $D = O(\log n)$.

Note that this argument doesn't use the recursive part of the definition.


About metric TSP instances Christofides' 1.5-approximation considers complete graphs as inputs, and as I understand this is essential. If the input graph is not complete, how can I add new edges with suitable weights such that the resulting complete graph still satisfies the triangle inequality, and, of course, the TSP solution for the complete graph only uses original edges? Thank you.

If the edges don't satisfy the triangle inequality then the problem becomes harder. In your case the non-edges have infinite weight (since you want never to use them), so you can't expect Christofides' algorithm to be useful as such.


Is complement of diagonal language countable? I tried to find out how to arrange the complement of diagonal language, but I failed. So I'm about to believe that it's not a countable language. Could you, please, help me?

A language is a set of finite strings over some finite alphabet $\Sigma$. Therefore, every language is countable. You can see this by considering $\Sigma = \{0, \dots, d\}$ for some $d\in\mathbb{N}$ and now you can associate any string with a natural number written in base $d$.  To avoid the problem that, e.g., $0$ and $000$ denote the same number (and I guess $\epsilon$ counts as zero, too), we actually associate the string $x_1\dots x_n$ with the number $1x_1\dots x_n$. Thus, we have an injection from $\Sigma^*$ to $\mathbb{N}$, so $\Sigma^*$ is countable and so are all its subsets.


Applying Case 3 of Master Theorem to $T(n) = 9T(n/3) + n^3$ Given $T(n) = 9T(n/3) + n^3$,
I know that $a =9$, $b=3$, and $f(n) = n^3$
and $n^{\log_{3}9} = n^2$
thus Case 3 applies: $n^{\log_{b}a} < f(n)$, $n^2 < n^3$.
Can someone explain how to apply the regularity condition and how to check the regularity condition?
$af(n/b) \le cf(n)$ where $c < 1$
I appreciate your help!

Your statement of the regularity condition has a typo: it suffices to show that there exists a constant $c < 1$ such that for large enough $n$,
$$
af(n/b) \leq cf(n).
$$
Substituting $a,b,f$, we have to show that for some constant $c < 1$,
$$
9(n/3)^3 \le c n^3.
$$
You take it from here.


Terminology: words with only terminals vs. words which can contain nonterminals In the context of formal grammars, is there a standard terminology to distinguish

words (i.e., finite sequences of letters/tokens) which only contain terminal letters/tokens, and
words which may contain nonterminals?

I prefer to use the term "word", unqualified, to refer to the former, because I am discussing various ways to produce words over a fixed alphabet $\Sigma$ (of terminals!), the set of nonterminals can vary from grammar to grammar, so words over them only make sense for a particular grammar.  But I would still like to have a term to refer to words which may contain nonterminals: how should I best call them?

"Nonterminal words" isn't a good term because they might turn out to have only terminals; "possibly nonterminal words" or "not necessarily terminal words" is too long and syntactically awkward.  "Word over $\Sigma\cup N$" is, of course, perfectly clear, but sometimes one doesn't want to introduce any symbols.  What other options are available?  From this related question I'm thinking maybe "symbol string" or "symbol word", but I'm not sure whether it's sufficiently distinctive.  Some other possibilities are "generalized word" or perhaps "form" since the generalized words which can be derived from a grammar are called "sentential forms".  Any other idea?

A standard term would indeed be sentential form. I think it can be used on its own, not only bound to a grammar.

It makes more sense when you know that words are also called sentences, probably harking back to the beginnings of formal grammars in the study of natural languages.

That said, there is precedence for pattern in the study of pattern languages. While they work nothing like grammars, mixed strings of alphabet symbols and variables have this name there.


Are all Chomsky-Type3 grammars LL(1)? Referring to this Question, where an answer is stating that all Type 3 languages are LL(1), I'd like to know if all Type 3 grammars are possibly LL(1).

If not, why is it so? Are there maybe ambiguous grammars in the set of the Type 3 grammars?

Chomsky hierarchy is primarily a hierarchy of grammars, not of
languages. As stated in Wikipedia:

  The Chomsky hierarchy (occasionally referred to as
    Chomsky-Schützenberger hierarchy) is a containment hierarchy of
    classes of formal grammars.

Type 3 grammars are characterized by the fact that they have to have
only left linear rules (i.e., productions), or only right linear rules,
plus possibly an empty rule for the initial non-terminal symbol. For
any language, both forms exist.

A rule is left linear iff its right hand side (RHS) is composed of a
terminal symbol, possibly preceded by a single non-terminal.

A rule is right linear iff its right hand side (RHS) is composed of a
terminal symbol, possibly followed by a single non-terminal.

(There are small variants of these definitions, allowing for a
terminal string of any length, instead of a single terminal)

When the language is not finite, some of the rules are necessarily
recursive. But a left linear rules that is recursive is necessarily
left recursive. Hence the grammar is not LL(1).

Hence some type 3 grammars, even with the strict definition above, are
not LL(1).


Does NFA to DFA conversion give the minimal DFA as result? When converting NFA to DFA, do I always get the minimal DFA or not?

No, it is not in general minimal. The standard determinization procedure, the subset construction, always converts an NFA with $n$ states to a DFA with $2^n$ states and there is no reason that this should be minimal.

In practical terms, if you convert an NFA, you'll often find that there are unreachable states in the resulting DFA, which immediately shows that the result is not minimal. For a more extreme example, take any DFA with $n$ states, call it an NFA and determinize it. You now have a DFA with $2^n>n$ states that accepts the same language as it did before, so it's certainly not minimal. (This is a particularly strong example of the first case I mentioned. All states except subsets of size $1$ will be disconnected from the start state, and the states of size $1$ are a copy of the original DFA.)


Why does space(n) <= time(n) imply that TIME(f(n)) is a subset of SPACE(f(n))? The title might be hard to understand, here's a picture of what I don't understand:

And further, why can we conclude this?

I thought about posting to theoretical CS stackexchange but it asks for research level and I don't think this will be accepted

A machine which runs in time $f(n)$ also runs in space $f(n)$, that is, the space used by a machine is always at most the time it uses. In symbols, $\mathrm{space}_M(n) \leq \mathrm{time}_M(n)$.

A machine is in $\mathsf{TIME}(f(n))$ is it runs in time $O(f(n))$. Any such machine also uses space $O(f(n))$ (since the space used by a machine is at most the time it uses), and so it is in $\mathsf{SPACE}(f(n))$. In other words, $\mathsf{TIME}(f(n)) \subseteq \mathsf{SPACE}(f(n))$. This implies that
$$
\mathsf{P} = \bigcup_{k=0}^\infty \mathsf{TIME}(n^k) \subseteq \bigcup_{k=0}^\infty \mathsf{SPACE}(n^k) = \mathsf{PSPACE}.
$$
A similar calculation shows that $\mathsf{EXPTIME} \subseteq \mathsf{EXPSPACE}$.

For the remaining relation, we have to use a different fact about time and space: a machine which uses space $f(n)$ runs in time $O(2^{O(f(n))})$. This is because the number of configurations in a (one-tape) machine which uses space $f(n)$ is $|Q| f(n) |\Sigma|^{f(n)}$, where $|Q|$ is the number of states and $|\Sigma|$ is the size of the tape alphabet. You can check that this implies the remaining containment $\mathsf{PSPACE} \subseteq \mathsf{EXPTIME}$.


Print Binary Tree Diameter Path Diameter of the tree is defined as a long path or route, between any two nodes in a tree. The path may or may not goes through the ROOT.

Print the Longest leaf to leaf path in a binary tree and its length

I worth an algorithm that calculates the diameter in Swift:

func diameter() -> Int {
 return diameterHelper(root).Diameter
}

typealias HeightAndDiameter = (Height: Int, Diameter: Int)

private func diameterHelper(node: TreeNode<T>?) -> HeightAndDiameter {

   guard let node = node else {
     return HeightAndDiameter(Height:0, Diameter:0)
   }

   let left  = diameterHelper(node.left)
   let right = diameterHelper(node.right)

   let height   = max(left.Height, right.Height) + 1
   let diameter = max(left.Height + right.Height + 1, max(left.Diameter, right.Diameter))

   return HeightAndDiameter(Height: height, Diameter: diameter)
}

I have tried to adapt this algorithm, but it doesn't work for all the cases.

  func diameterPath() -> [T] {
    return diameterPathHelper(root).Path
  }

  typealias HeightAndDiameterAndPath = (Height: Int, Diameter: Int, Path: [T])

  private func diameterPathHelper(node: TreeNode<T>?) -> HeightAndDiameterAndPath {

    guard let node = node else {
      return HeightAndDiameterAndPath(0, 0, [])
    }

    let left  = diameterPathHelper(node.left)
    let right = diameterPathHelper(node.right)

    let height = max(left.Height, right.Height) + 1

    if left.Height + right.Height + 1 > max(left.Diameter, right.Diameter) {
      let currentDiameter = left.Height + right.Height + 1
      let path = left.Path + [node.data] + right.Path
      return HeightAndDiameterAndPath(height, currentDiameter, path)

    } else {
      if left.Diameter > right.Diameter {
        return HeightAndDiameterAndPath(height, left.Diameter, left.Path)
      } else {
        return HeightAndDiameterAndPath(height, right.Diameter, right.Path)
      }
    }
  }

One natural approach goes as follows. Compute recursively for each node both the longest leaf-to-leaf path in the subtree rooted at the node, and the depth of the deepest leaf. From this information for the two children of a node you can compute the same information for the node itself. Once you have reached the root, you have obtained your answer.

The above only computes the length of the longest path, but you can actually extract the longest path itself from the data for each node. Details left to you.


The situation when P is a superset of NP Could it be that three languages $A, B, C$ such that $A \subset B \subset C$, and $B \in P$, but $A$ and $C$ are $NP$-complete?

Let $L$ be any NP-complete language over $\Sigma = \{0,1\}$, and take
\begin{align}
A &= \{ 0x : x \in L \} \\
B &= 0\Sigma^* \\
C &= 0\Sigma^* \cup \{ 1x : x \in L \}
\end{align}


Flow Problem in Tripartite Graph Given a Directed Tripartite graph with 3 Groups of vertices {A, B, C} such that:

Edges from A are directed in B.
Edges from B are directed in C.

Objective: Minimize the number of vertices in B (by keeping few and deleting the rest) such that every vertex in C is reachable from every vertex in A.

I think this can be converted into a flow problem but i am not sure how to go about it. Anyone ?

The decision version of this problem is NP-hard (and so NP-complete), by reduction from Hitting Set.

Let $S_1,\ldots,S_m$ be an instance of hitting set. We will have the following vertices and edges:

Vertices $A_i$ for $1 \leq i \leq m$ and $A_{i,j}$ for $1 \leq i \neq j \leq m$.
Vertices $B_u$ for every $u$ in the universe of the hitting set instance, and $B_{i,j}$ for $1 \leq i \neq j \leq m$.
Vertices $C_i$ for $1 \leq i \leq m$ and $C_{i,j}$ for $1 \leq i \neq j \leq m$.
For every $u \in S_i$, edges $A_i \to B_u \to C_i$.
For every $1 \leq i \neq j \leq m$, edges $A_{i,j} \to B_{i,j} \to C_{i,j}$.
For every $1 \leq i \neq j \leq m$, edges $A_i \to B_{i,j} \to C_j$.

Every feasible solution to this instance of your problem has to contain each $B_{i,j}$, since this is the only way to connect $A_{i,j}$ and $C_{i,j}$. Hence every $A_i$ is automatically connected to every $C_j$ for $j \neq i$. In order to connect $A_i$ to $C_i$, we need to have $B_u$ for some $u \in S_i$. Hence the minimal solution contains $m(m-1) + k$ vertices iff the hitting set instance has a minimal solution with $k$ elements.


Compare Complexity of Graph Algorithm Assume I know that there is an algorithm of complexity
$ \mathcal{O}( log ( \vert V \vert^2 \vert E \vert ) ) $
for a Graph $G(E,V)$.

How do I compare this for example to the complexity of
$ \mathcal{O}( \vert V \vert^2 + \vert E \vert ) $ or other complexity algorithms on $G$.

There has to be a connection between $\vert E \vert$ and $\vert V \vert $ if I am right which is needed to solve this. But the only thing I found is $max .\vert E \vert = \frac{\vert V \vert }{2}(\vert V \vert -1)$, what does not help here and in many other cases.

Or should I just assume
$max .\vert E \vert = \frac{\vert V \vert }{2}(\vert V \vert -1)$ and $min.\vert E \vert = \vert V \vert -1$ ?
Btw. must a vertex be connected via an edge to the graph per definition?

First of all $\min (|E|) = 0$ since the graph can be disconnected. $\min(|E|) = |V| - 1$, is true only for connected graphs. Whether a vertex is needed to be connected to the graph depends on the problem being considered. In general, a vertex can be isolated. So, in general, $0 \leq |E| \leq {{|V|}\choose{2}}$, if the graph is not a multi-graph. If the graph is a multi-graph then there is no upper limit to $|E|$.

Secondly if we are comparing $O((\log|V|^2||E|))$ against something like $O(|V|^2+|E|)$, former will be always better than the latter , since $O(\log(|V|^2)|E|) = O(\log|E|+2\log|V|)$.

So the question is, whether to analyze algorithms in terms of $|E|$ (i.e $|E|$ and $|V|$) or only in terms of $|V|$.

Of course what you say about needing to relate $|V|$ and $|E|$ is correct. However, whenever a complexity is stated in terms of $|E|$, it is better than, say, substituting $|V|^2$ for $|E|$. Note that $|E|$ is always $O(|V|^2)$ even for the cases when it is smaller, for example, for trees. $O()$ is upper bound.

If the analysis of an algorithm is in terms of $|E|$ than we get the complexity bound for all the cases, whether the graph is dense or sparse. Thus $|E||V|$-time algorithm is considered better than a $|V|^3$-time algorithm.

In the cases, if the graph is a tree, or a graph with a max degree $d=O(1)$, then $|E|$ is only $O(|V|)$. So, as an example, an $O(|E||V|)$ algorithm will be considered better than $O(|V|^3)$ algorithm. Thus, if we are able to do a tighter analysis, we are sure that the algorithm will fare better in case of non-worst case input.

As pointed by Raphael, $\Theta(|E|)$ is not same as $O(|V|^2)$. $\Theta$ analysis is better wherever applicable. But usually we don't give $\Theta$ analysis, because if we say some algorithm is $\Theta(f(n))$, and for some easy input the algorithm runs in $o(f(n))$ time, our statement will be wrong.


Is deciding if there is a set that is intersected with some given sets and that has at most one common element with other given sets NP-complete? Given 2 collections of ﬁnite sets $A_1,A_2,\ldots,A_m$ and $B_1,B_2,\ldots,B_n$, is there a set $T$ such that: $\left|T \cap A_j\right|\ge 1$, for $j = 1,2,\ldots,m$ and $\left|T \cap B_i\right|\le 1$, for $i= 1,2,\ldots,n$?

I tried doing this problem by considering it as a decision problem (pi).
Please suggest me if you have an approach.

You can reduce 3SAT to this problem by converting each variable $v_i$ to two elements $e_{i1}$ and $e_{i2}$ (one for its positive literal and one for its negative literal) and a set $B_i$ containing $e_{i1}$ and $e_{i2}$, and converting each clause $c_j=l_{j1}\vee l_{j2}\vee l_{j3}$ to a set $A_j$ containing elements representing $l_{j1},l_{j2},l_{j2}$.

Now it's not hard to prove this problem is NP-complete using the reduction above.


Regular expression or automata for language with odd number of 0's and odd number of 1's Let $\Sigma=\{0,1\}$ and $L=\{u \in \Sigma^* : u \text{ has odd number of 0's and odd number of 1's}\}$. How can I build a regular expression or an automaton for this language? I have no idea, and I guess $L$ is not regular, but I haven't been able to prove it with the pumping lemma.

If it is not regular, can you give me a hint to prove it?

Hint: You are trying to solve two problems (i.e., odd number of zeros and odd number of ones) at once. Try to solve each separately instead and then combine the solutions appropriately.


Connection between castability and convexity I am wondering if there are any connection between convex polygon and castable object? What can we say about castability of the object if we know that the object is convex polygon and vice versa.
Let's gather together few basic things that we have to know.

The object is castable if it can removed from the mold.
The polyhedron P can be removed from its mold by a translation in direction $\vec{d}$  if and only if $\vec{d}$ makes an angle of at  least $90^{\circ}$ with the outward normal of all ordinary facets of P.

For a arbitrary object testing for castability has time complexity $O(n^2)$. In my opinion, for a convex polygon if could be improved to linear time, because for every new top facet we should test that the vector $\vec{d}$ makes an angle at least $90^{\circ}$ with outward normal not of all but only of two adjacent ordinary facets of P.
If this is true at least we have improvement in testing for castability in case of convex polygon.
We else can we state about castability and convexity. Especially interesting to know, if castability tells us something about convexity.

This is a proper answer but feel free to correct me I think I did not get the right definitions. This is why I begin with simple facts that should be checked first.

I suppose your are talking about $\vec v$-castability of a "open" polyhedron.

Indeed it seems that no "closed" polyhedron is $\vec v$-castable.
For every $\vec v$, a convex "closed" polyhedron can always be cut into two "open" parts among a plane of normal $\vec v$ that are $\vec v$-castable and $(-\vec v)$-castable.
The test of $\vec v$-castability is in $O(n)$ (even if is not convex)
The problem (Is there a $\vec v$ s.t. $P$ is $\vec v$-castable?) seems to be linearly reducible to the convex hull, which is in $O(n\log n)$:

First consider each outward normal $\vec{n_i}$ into a point of the unit sphere.
Compute $H$ the convex hull of these points.
If the origin $0$ is in $H$ then for all $\vec v$, $P$ is not $\vec v$-castable.
If the origin $0$ is not in $H$ then let $\vec v$ be the vector starting at the projection of $0$ on $H$ and ending at $0$. The vector $\vec v$ defines a half-space containing none of the $\vec{n_i}$ meaning that $(\vec v, \vec{n_i})>90°$.
If the origin $0$ is on the surface of $H$, just take the normal of $H$ in $0$ for $\vec v$.

not in the convex hull iff there exists $\vec v$ such that

If $P$ is convex and "open" (whatever it means), then you only need its "frontier" and the corresponding orientation. You apply the same algorithm as above on the frontier (plus the orientation vector) reducing the complexity. For a polygon it becomes in $O(1)$ if you already know the two segments on the frontier.

Hope this helps.


Suggest how to allocate and deallocate storage for elements within the hash table itself by linking all unused slots into a free list Suggest how to allocate and deallocate storage for elements within the hash table itself by linking all unused slots into a free list. Assume that one slot can store a flag and either one element plus a pointer or two pointers. All dictionary and free-list operations should run in O(1) expected time. Does the free list need to be doubly linked, or does a singly linked free list suffice?

Please tell me if my understanding is correct: each slot in T[0,1,2….m-1] is storing (1) a flag (2) an element (3) 2 pointers
So, instead of the slot T(h(k)) being a pointer to a list, it is able to save one element and then that element points to a list
There is also a “free list”
There is only one flag for each slot T[0,1,2….m-1]
To insert an element ‘x’ we will first check T[h(x.key)] to see if it is free. If it is free then we insert T[h(x.key)] and change the flag = 1
If it was not free, then there is a list, so we insert it at the beginning of the list
To delete we will check x.prev and x.next to see if they are NULL. So when we delete the element ‘x’ we will be left with an empty list at that slot. So we insert T[h(x.key)] into the free list and update the flag to 0 and then delete the element x from the list its stores in
What I don’t understand is the functionality of maintaining a free list?  Is there a single free list for the whole hash table or does each slot have its own free list?  Also why insert the element to be deleted into the free list and then delete it? Why don’t just delete it without using the intermediate free list?
I am unable to visualize the use of the free list as mentioned in the question.

Practical implementations that I have seen worked like this:

In a hash table, a slot is either used (contains a hash value and a value), has been never used, or has been used and emptied, and we need to distinguish this. With no additional space if at all possible.
If the values are pointers, and neither “all bits zero” nor “all bits one” are valid pointers, then we store “all bits zero” or “all bits one” as data to mark a “never used” or “not used anymore” slot.
If (2) doesn’t work: There are many more possible hash values than slots. Therefore most hash values never happen. We pick two random hash values which we store as the hash value to represent “empty” and “not used anymore” slots. As long as these are not used, fine. If they are used, we pick two different random hash values and modify the table accordingly (number of slots used should be less than the square root of possible hash values).

I’ve never seen a “free list” being used, because the hash value determines where an entry needs to be stored. Everyone just uses an array.


Measures of performance in machine learning I'm new to machine learning and struggle to interpret the results I get from different measures of performance. If for several prediction models I have e.g. accuracy, precision, recall, F1, FPR, and MCC and want to find out which model performs best, what do I look for? I would assume accuracy is most important?

Also, what influence does the error have on the interpretation? E.g. method 1 has an accuracy of 87 +- 5% and method 2 has 84 +- 5% I would assume method 1 to be better. Is that correct?

Precision and recall are the two basic measures and most of the other measures can be written in terms of them. If a model has both better precision and better recall, then it can be seen as strictly better than another model. If two models are incomparable in the sense that another has better precision and another has better recall, then it depends on the application which one is better. For some applications it is essential to avoid false positives, and for some applications it is essential to avoid false negatives.


How can a CPU access more memory locations than 2^wordsize? I noticed that CPU's like the 8086 and especially the 8080 have the ability to access more memory than what one would normally assume. The 8080, for example, has an 8-bit word size but can use a 16-bit memory address. From what I understand, a standard instruction has the opcode in the beginning and then the address on which it will work. How then, could a 8-bit processor be able to fit an opcode and 16-bit address in 8-bits?

The 8080, as @TEMLIB pointed out, had 16 bit registers (the program counter, the stack pointer and BC, DE, and HL), and could access 216 bytes of memory.  The 8080 had an 8-bit bus, and for instructions that required 2 bytes of data or address the bus would be used for 2 cycles.

The 8086 is more interesting.  The 8086 had 16 bit registers, but could access 220 bytes of memory.  It did this by using segment registers.  There were four special 16-bit registers, CS, DS, ES and SS and every address was calculated by taking 16 times the appropriate segment register plus the 16-bit offset coming from a "normal" register.  So for example, instruction addresses were all calculated as an offset from CS * 16, and stack references were all calculated as an offset from SS * 16.

Modern 32-bit processors can also sometimes access more than 232 bytes of DRAM through the virtual memory system.  Each running program can access only 232 bytes of virtual memory but the page table entries map to (for example) 36 bit physical addresses, allowing the operating system to run multiple programs simultaneously that collectively can access up to 236 bytes of physical DRAM.


Language decidable or not? I have just began with my course of complexity and computability and I need your experience to help me progress !!

Something is not clear for me:

It is asked to determine if L1 is decidable or not, below the language is an answer given by a student. And I'm not agree with it...

The Rice theorem is given as follow :

I don't get why L1 is decidable since, for me, it looks like the Rice theorem could be immediately applied.

Did I understood very badly or am I right ? In the first case, why ?

Thanks in advance for your help !

Elia

Rice's theorem only applies for nontrivial properties, which are properties which are not always true or not always false. Your property is trivial, since it's always true.


Mathematical proof for why gradient descent algorithm always converges I am currently learning machine learning and I stumbled across gradient descent. I understand why the algorithm always converges to the global/local minimum when the learning rate is small enough in my head, but is there a mathematical proof?

Thank you!

It looks like you put some emphasis on mathematical rigor. It just happens my motto is currently "from math and larger than math".

Yes, there are many mathematical proofs for conclusions along the line that gradient descent method converges to local minimum when the steps are small enough. We will need some precise statement on the condition of $f$ and the steps taken. Let me quote from Wikipedia,

  With certain assumptions on the function $F$ (for example, $F$ convex and $\nabla F$ Lipschitz) and particular choices of $\gamma$ (e.g., chosen either via a line search that satisfies the Wolfe conditions or the Barzilai-Borwein method shown as following),
  $$ \gamma_n=\frac{(x_n-x_{n-1})^T[\nabla F(x_n) - \nabla F(x_{n-1})]}
{||\nabla F(x_n) - \nabla F(x_{n-1})||^2}$$
  convergence to a local minimum can be guaranteed. When the function $F$ is convex, all local minima are also global minima, so in this case gradient descent can converge to the global solution.

For some actual statements and proofs in their full clear detail, you can read a course note by Ryan Tibshirani at CMU. Unfortunately, because of the required mathematical rigor,  they are too long to be included here.


Is this a misleading or undesirable implementation of a hash map? I read a C++ implementation of a hash map here.
https://www.geeksforgeeks.org/implementing-hash-table-open-addressing-linear-probing-cpp/

Let's say key k1 has a hash index of h. Suppose there's a collision with key k2 such that hash(k1) == hash(k2). Then won't the new hash index of k2 become h+1?

Key: k1     Index: h
Key: k2     Index: h+1

Suppose we introduce a third key k3 such that hash(k3) == h+1. Then when we insert k3 into the hash map, its hash index will become h+2.

Key: k1    Hash value: h      Hash table index: h
Key: k2    Hash value: h      Hash table index: h+1
Key: k3    Hash value: h+1    Hash table index: h+2

This can cause the hash indexes for keys to be shifted over 1 in the case of collisions (as seen above), and if collisions happen frequently then they could be shifted over more than once.

Is this a bad implementation of a hash map? From an aesthetic point of view I prefer the linked approach, where each hash node has a pointer to a next node, such that if multiple nodes have the same hash index, they are all part of the same linked list starting at that hash index.

In the linked approach, at least we have the assurance that a key will logically correspond to its hash index in the hash table, even if it's part of a linked list (in which case it doesn't physically correspond, but logically still does, since the head of the linked list is stored there).

Is the implementation of the hash map in GeeksForGeeks bad? Is the linked approach more logical and intuitive? What are your thoughts?

Note: The linked approach I refer to is simply to store a linked list at each hash index in the hash table, such that if multiple keys are hashed to that index, they are stored in this linked list.

As others have indicated, this code example doesn't do resizing, and this is an important part of a "real" dynamic hash table. Whether or not it's "bad" depends on what it's trying to achieve as an example, but it's certainly not code that you should deploy.

Linear probing isn't necessarily a bad idea. After all, it has excellent locality. But since you asked about a specific scenario, let's explore that. The scenario is where you have two keys, k1 and k2, which have the same hash value h, and a third, k3, with the hash value h+1.

Most hash table designs rely on the premise that the hash function is "good". If you have a "good" hash function, this should be a difficult scenario to engineer on purpose, but it's still possible that it happens with high enough probability just by virtue of storing a lot of entries in the hash table.

Consider an open addressing hash table with $m$ slots and $n$ elements in it. Denote the load factor by $\lambda = \frac{n}{m}$. Then if the hash function is "good", and $m$ and $n$ are large enough, the probability that a given slot has $k$ elements that would "naturally" hash to that slot is given by the Poisson distribution:

$$P(k; \lambda) = \frac{e^{-\lambda} \lambda^k}{k!}$$

So the probability that a given slot has at least 2 elements is:

$$P_1 = 1 - P(0; \lambda) - P(1; \lambda)$$

And the probability that the very next slot has at least 1 element is:

$$P_2 = 1 - P(0; \lambda)$$

The probability of this scenario occurring to a given hash slot is:

$$P_1 P_2 = 1 - e^{-\lambda} (\lambda + 2) + e^{-2\lambda} (\lambda + 1)$$

...and so on. Multiply this by $m$ to give the expected number of times this scenario happens for any $m$ and $n$.

(Exercise: Suppose that you have $m$ pigeonholes and $n$ pigeons, and you assign pigeons to pigeonholes randomly and $m$ is large enough. Then the proportion of pigeonholes with $k$ pigeons assigned follows a Poisson distribution. Show that the expected number of "pigeon collisions" is $\frac{1}{2}$ when $n = \sqrt{m}$.)

Remember, though, that short probes aren't necessarily a problem. What you're trying to avoid is long probes. Specifically, you're trying to ensure that the maximum probe length, that is, the largest distance that an entry is from its "home", is small. This number gives the maximum "work" that you may have to do to look for an entry.

In open addressing, it is common practice to keep track of this maximum probe length, and update it when a new element is inserted. This number is used for (at least!) two purposes: to decide when to stop searching, and to decide when to resize the table.


CFL Closure Properties prove or disprove for the following languages I have following statements which I must prove or disprove :

1) Let $L$ be a CFL and $k \in N$ then $L^k$ is also a CFL.
2) $L_1 \subseteq L_2 \subseteq L_3$  are Languages, if $L_1$ and $L_3$ are DCFL, then $L_2$ is also a DCFL

The first one I have no idea how to start or whether it is also a CFL

For the second one I think that this is false, because the CF contains the REG and DCF which means $L_2$ can be a REG-Language or a CFL or DCFL?

Is this right? at least this is how I understand it

1) If $L$ is a CFG then assume $S$ is the start symbol of the grammar rules. Then introduce a new start symbol $S' \rightarrow SS\dots SS$ ($k$ times). So if $w \in L^k$ then $w$ can be written as $u_1u_2\dots u_k$ where $S \Rightarrow^* u_1$, $\dots$, $S \Rightarrow^* u_k$ and so $S' \rightarrow SS\dots S \Rightarrow^* u_1u_2\dots u_k$. Now suppose that $S' \Rightarrow w$. Then since $S' \Rightarrow SS\dots S \Rightarrow^* w$, $w$ clearly in $L^k$. Thus, $L^k$ is CF.

2) $L_1 = \{ 0^i | i \in N\}$, $L_2 = \{ 0^i1^j2^k | i,j,k \in N, i=j \ or  \ j=k\}$, $L_3 = \{ 0^i1^j2^k | i,j,k \in N\}$. Clearly $L_1 \subset L_2 \subset L_3$. But $L_2$ is not CFL, so not DCFL.


Order of a leaf node in B+ Tree Going with the definition, that order of a B+ tree is the maximum number of children a node can have.

What is exactly meant by the order of a leaf node? As per my understanding order of a leaf node is the number of  pairs it can hold.

But in general when order of a B+ tree is defined in a question like, order is 5. Example:https://www.tutorialcup.com/dbms/b-tree.htm . Then we assume the leaf nodes to have keys in [n/2] to n-1(3 to 4).

If we assume the leaf can contain 5 pairs, then the upper limit on keys should be 5 and not 4. Could someone explain why its taken to be n-1 in every B+ tree insertion tutorial.

For a B+ tree the order of a node is the maximum number of keys that it can contain. This satisfies the definition of maximum number of children because for a leaf node number of record pointers(children) is same as number of keys. The last pointer present in a leaf node is not considered a children since it links one leaf to another(is not a record pointer).


Correct term for “string consisting of words” In a paper I am writing I want to make distinction between (1) string consisting of any characters and (2) string consisting of a chain of words from known language, with possible delimiters. My intuitive idea is to simply use string for meaning (1) and text for meaning (2). It sounds a bit naive, but this terminology could work, given that I define it properly in my paper.

Yet I have an uneasy feeling that meaning (2) has fancier name in fields of computer science or computational linguistics. So, what are the precise terms to make distinction between the two types of strings?

UPDATE

Suppose we have an alphabet Σ = {a, b, c, ~}, where ~ is a delimiter symbol, and language L = {aaa, bbb, abc}.

Now, the following strings satisfy definition (1), but not (2):

cba
a
aaaa
a~b~~

And the following strings would satisfy both definitions (because they are made of the words of language L).

aaabbbabc
abc
aaa~bbb~aaa~~~aaa
~
(an empty string)

In some applications my strings could be actual text in a human language like English, Lithuanian or Esperanto. But this is not required. It could also be a DNA chain, a binary file, or anything else. Also keep in mind, that in practical applications the strings would most likely be long (like a journal article, or entire corpus for that matter), so calling it a "sentence" would be a bit of understatement. Meaning of the text is entirely irrelevant here.

So, regarding definition (1) all is clear - I just call it a string on alphabet Σ. Now the core question is this: what do I call the strings from the second example to make them distinct from the first example. My initial idea is to call it a "text". One of the answers proposed "word string", which I like even better. Maybe you have seen other terms being used for such purpose in the literature?

It might seem that I'm in extreme hair splitting mode here. Yet that term will be all over my PhD thesis, very likely including the title. Therefore I really want to get my terminology straight.

If definition (1) is intended for any sequence of characters, I would
simply call it string as you suggest, but I would call it word or
lexeme if it is intended to be words of a language.

Regarding definition (2), it depends again on what you are expecting
to consider. If it is any sequence of words, usually meaningless, with
a variety of separators, the name text would do fine, and I would
not worry too much about computational linguistic since the only
meaningless piece of text that matters in CL is "Colorless green ideas
sleep furiously".

If it is actually intended to be a sentence of a language, then you
might call it sentence. I feel that text would rather be used for
larger pieces of discourse. You should be careful though that is is
not confused with sentence meaning a string of words. Speech
processing people may speak of utterance, but it may be
inappropriate for your use. They use also sentence, which they
structure into word lattice when the separators are not clearly
identified, which amounts to a word sequence or word string if they
are clearly identified.

This disctinction may also depend on whether your separators are one or
many, and whether they have a role.

In other words, it is hard to give you a precise answer without more
details on what you are doing. I first tried, and then realized that
it led me to make unwarranted assumptions about what you are doing.

The one thing that is really important is that you are very clear
about your definitions. And if you can motivate your terminology
choices, that may help the reader. I am still wondering why the borogoves had to be so mimsy.


Extended Compact Genetic Algorithm question I have a question regarding the ECGA algorithm. This is what I'm currently studying. If ECGA builds a model of the parent pool using the 'minimum description length' (MDL) measure, why cannot we simply choose the model which has the most likely fit of the parents?

Thanks.

Read the answer from a thread on Google,
thanks to Jeremy P. Harford. (Posted with permission.)

...You can!  Standardized algorithms can always be altered to better fit your needs.  They're generalized forms, and specific applications will often have better fits.
But when you start talking about likeliness, be careful.  Leveraging Bayes requires recursive optimization regarding which there are (too many) patent trolls and a performance pitfall that can be tricky to avoid.  Plus, further empirical sampling can invalidate your algorithm.
And when I say there are too many patent trolls, understand that people who know nothing about Bayesian statistics nor programming are granted patents by other people who know nothing about Bayesian statistics nor programming.  It's a mess.
In this case, applying Bayes can create two tiers of algorithms that don't always complete.  Depending upon your use case, that can get rather hairy.  It's usually a good idea to implement the generic algorithm first, and then alter it as needed -- kind of like when you replace standard containers with use case optimized custom containers.


Are the two LTL properties $GF(\psi_1 \land F\psi_2 )$ and $GF(\psi_2 \land F\psi_1 )$ equivalent? Is $GF(\psi_1 \land F\psi_2 )$ equivalent to the property $GF(\psi_2 \land F\psi_1 )$?

Attempt:

In the first property each state must eventually see $\psi_1$ and $\psi_2$, in the second property as well each state must eventually see $\psi_1$ and $\psi_2$, as such the two properties must be equivalent. Is this correct?

You are right, but you should prove it.  Here's a proof sketch:

Proof setup:

  Suppose that $GF(\psi_1 \land F\psi_2)$ is true and assume towards a contradiction that $\neg GF(F\psi_1 \land \psi_2)$.

Observations:

  Then there exists a state $s_1$ in which $\neg F(F\psi_1 \land \psi_2)$, which means that every state $s_2 > s_1$ has $\neg(F\psi_1 \land \psi_2)$, which means that for every state $s_2$, either $\neg F\psi_1$ or $\neg \psi_2$.

Contradiction:

  But since $GF(\psi_1 \land F\psi_2)$, there exists a state $s_3 > s_2$ such that $s_3 \vDash \psi_1$ and a state $s_3 > s_2'$ such that $s_3' \vDash \psi_2$, which is a contradiction.

The other direction is identical.


Sampling from a Acyclic Deterministic Finite Automaton Assume you have a finite language $L$ succinctly represented as a acyclic DFA $M$ (models can't be much simpler than that :) ).

  How can we efficiently sample a word from $L$ with uniform distribution?

Note that counting the number of words in $L$ is easily doable in linear time in the size of $M$, which might be useful for the sampling process.

Clarifications:

$L(M)=L$.
$M$ is acyclic (has no loops).
Sampling means you output each word $w\in L$ w.p. $\frac{1}{|L|}$.

Some rough thoughts:

As $M$ is acyclic and deterministic, each word $w$ in $L$ determines a unique path through $M$. Therefore, at each state $q \in Q$, we weight each transition based upon the number of valid subsequent paths (this is the size of the subset of $L$ with a particular prefix). This can be done recursively, and should be linear in the number of transitions.

Then, in order to sample, we can define a function $p: Q\times\Sigma \to R$ that gets us this 'weight' of a particular transition, and use this to define the probability of moving through that transition. At the end of this, rolling a die at each transition should get a normal sample.

I've probably missed something, but it seems like a decent approach.