Definition of Strongly Parsimonious Reduction There is a well known definition of parsimonious reduction.

The standard definition of parsimonious reduction is very intuitive. It simply means that the two problem have the same number of solutions, when on input of one of them we applied function $f$.

We say there is a parsimonious reduction from #A to #B if there is a polynomial time transformation $f$ such that for all $x$, $|\{y,(x, y) \in  A\}| = |\{z : (f(x), z) \in B\}|$.

I am interested in definition of strongly parsimonious reduction.

The only definition I found:

"Strongly parsimonious reduction of $R'$ to $R$ is a parsimonious reduction $g$ that is coupled with an efficiently computable 1-1 mapping of pairs $(g(x), y) \in R$ to pairs $(x, h(x, y)) \in  R'$ (i.e., $h$ is efficiently computable and $h(x, ·)$ is a 1-1 mapping of $R(g(x))$
to $R'(x)$). For technical reasons, we also assume that $|g(x)| ≥ |x|$ for every $x$."

The problem is I simply don't understand what this definition means. I tried to separate it to smaller block, but so far with no success. According  to the definition there are two function $g(x)$ and $h(x,y)$ are they are applied simultaneously to two different problem $R$ and $R'$. How the usages of two function can be explained. What is the difference between two reduction, parsimonious reduction  and strongly parsimonious reduction.

I would appreciate any help in understanding the definition of strongly parsimonious reduction.

A search problem is defined by a relation like $R$. The task is given an input $x$ find a solution $y$ s.t. $R(x,y)$ is true.

A counting problem is defined as counting the number of solutions of a search problem, i.e. given an input $x$ we want to compute the number of $y$s s.t. $R(x,y)$ holds. The counting problem associated with search problem $R$ is denoted by $\#R: \Sigma^* \to \mathbb{N}$, $x \mapsto \#y: R(x,y)$.

A parsimonious reduction $f$ between counting problems only needs to preserve the number of $y$s, i.e. for all $x$,

$$\#y:R(x,y) = \#z:S(f(x),z)$$

A strongly parsimonious reduction has an the extra property that you mentioned. The meaning of the property should become clear if you look at it in the following way:

  Assume that we want to use the search problem $S$ to solve the search problem $R$.
  On an input $x$ for $R$, we first compute $g(x)$ which is an input for $S$.
  Then we use $S$ to find an $S$-solution $y$ for $g(x)$, i.e. $(g(x),y)\in S$.
  Finally we compute $h(x,y)$ to obtain an $R$-solution for $x$.

Now if we want to preserve the number of solutions between these two search problems, we can make sure that for every $x$, the function $h(x,\cdot)$ that computes an $R$-solution for $x$ from an $S$-solution $y$ for $g(x)$ is a bijection.

The difference should be clear now: not only the number of $R$-solutions for $x$ and $S$-solutions for $g(x)$ are equal, there is an efficient bijection between those solutions.


Deciding whether a given language is regular I am struggling with a homework assignment. This next question seems to be pretty easy, once I get what I feel like I'm missing now. Anyway, here goes:

  Decide if the following language is regular or not and prove your
  claim.

  $$L=\{a^{i_{1}}ba^{i_{2}}ba^{i_{3}}ba^{i_{4}}ba^{i_{5}}ba^{i_{6}}ba^{i_{7}}b|i_{1}>i_{2}>i_{3}>i_{4}>i_{5}>i_{6}>i_{7};i_{1}<100\}$$

So, how do I go about doing so? Is there a thumb rule that might help? I was trying to use the pumping lemma to prove that it is not regular, but couldn't do it. I'm not even sure it really is not regular.

Any suggestions?

Hint: Consider how many words are in $L$. The answer will then be immediate.


Exponential reduction vs Polynomial Reduction I'm having trouble understanding reduction. Lets say you have a decision problem A that is NP-Complete. Also, another problem B the can be reduced from A.

What can you say about B if:

1) The reduction is done in polynomial time
2) The reduction is done in exponential time

I know that if A is reduced to B means that if we knew how to solve B, then solving A would be easy. But I don't understand what 1 & 2 signify.

Would it be right to say that for 1)
B is in the same Class as A

And for 2)
That B > then NP-Complete?

In fact, depending on the class you want to reduce to, you need to be careful about the reduction you are doing.

For instance to preserve the class $P$, you need to do $LOGSPACE$-reductions.
For the class $NP$, you need $P$-reductions.

I'm also afraid that you reverse the reductions: to show that a problem $B$ is in $NP$, you need to reduce it (polynomially) to a problem $A$ in $NP$. Meaning that if you to how to solve $A$ in $NP$, then you can solve $B$ by reducing it to $A$.

So to sum up, if $B\leq_P A$ and $A\in NP$, then $B\in NP$. Indeed the NP algorithm is clear: perform your reduction (polynomial time) and then solve the instance of $A$ you reduced to (in $NP$).

However, if the reduction is exponential, then we cannot say anything about $B$, except that it is in $EXPTIME^{NP}$, i.e. you can solve it in exponential time with an $NP$ oracle. It is in fact the same that just saying $B\in EXPTIME$, since the NP oracle does not add power.


The idea behind the state of Imperative languages I was reading about programming paradigms and I have a question about the state when speaking about Imperative languages. What does it mean to change the program's state? Is it just an abstract idea? I know that C is in the Imperative paradigm (In fact in the Procedural paradigm), so it has a state, but I don't understand how it is expressed in language. Is there a special space in memory that contain 1 or 0? But then, what 0 and 1 represent?

If for example we have:

int x = 5;
printf("%d,5);

How the state will be affected by each line? Also, why Functional languages does not have one and what is the impact of having one.

As you can see, I'm a bit confused about the idea behind the state. I think that a small example make a bit clear.

I also read the previous thread from the second site, but it didn't help me to understand.

The simplest kind of state is the configuration of memory. In C this memory is accessed through variables (and arrays and pointers, but let us ignore those), so the state is the values of variables.

For example, suppose we have variables x and y whose values are 23 and 42 respectively (and no other variables). Then we could write the state as
$$[x \mapsto 23, y \mapsto 42]$$
If we run the program

x = 1 + y

the state will change to $[x \mapsto 43, y \mapsto 42]$. When we declare a local variable, the state will be extended temporarily with that variable.

There are many other kinds of state, such as:

in an object-oriented language each object has its own state, namely the values of its attributes
a finite state automaton has states, obviously

In general, there is going to be a set $S$ of all possible states. For instance, 1 GB of memory corresponds to $S$ with $2^{2^{30}}$ elements because that's how many states there are for 1 GB of memory. A program which uses state and computes a value of type $A$ can then be thought of as a function $S \to A \times S$: it takes the initial state $s \in S$ and returns a pair $(a, s')$ where $a$ is the computed value and $s'$ the final state.

It is not true that functional languages have no state! The pure functional languages such as Haskell and do not have built-in state, but other functional languages do have state. For instance OCaml and SML both have references, which are just mutable memory locations, so they have state. Racket and Scheme have state as well, and they are functional languages.

Perhaps a clarification is in order: a language is functional if functions are values, which means that we can do with functions whatever we can do with other values (pass them around, make arrays of functions, etc.). For some reason people often confuse pure and functional languages.

Supplemental: Since we're on the brink of a religious war about "Does C++/Java/whatever have first-class functions?", let me throw the first grenade. For a language to be functional the following have to be possible:

Read an integer n from standard input and create a list or an array of functions $[f_1, \ldots, f_n]$ where $f_i(x) = x + i$. This disqualifies C.
Allow function abstractions in the sense that it is possible to create a function based on a function rule, written as $\lambda x . E$, or $x \mapsto E$, or lambda x: E. Very importantly, there must be no scoping limitations on the abstraction, which means that $E$ may refer to any variables that are in scope. This disqualifies Java and C++.

There are fundamental mathematical reasons why function abstraction must be unrestricted. With restricted function abstraction we just don't get what is mathematically called a "function". We get something else, but not functions.


How exactly does on describe the formal semantics of the Applied $\pi$-Calculus? In "Mobile Values, New Names, and Secure Communication", Abadí and Fournet describe thet Applied-$\pi$-Calculus. Although I understood a great part of the description of the Applied $\pi$-Calculus, I'm still a bit confused as to what exactly its formal semantics consists of.

The authors define (on page 2):

  A signature $\Sigma$ consists of a finite set of function symbols, such as f, encrypt, and pairm each with an arity.

On page 3, they say that

  Given a signature $\Sigma$, we equip it with an equational theory, that is, with an equivalence relation on terms that is closed under substitution of terms for variables.

Then they proceed, still on page 3, to define Structural equivalence, which also is an equivalence relation, but defined on extended processes and not terms.

So after reading the paper a number of times and consulting some other resources on the Internet, I have concluded that the semantics of the $\pi$-Calculus depends on a given signature (and hence is "parametrized" in a sense); and that it is composed of:

the signature and its equational theory, which is provided by us, depending on the application context (I may include symmetric cryptography functions and some equations modeling their behavior, and no asymmetric constructions at all, for example);
the structural equivalence relation for processes;
the internal reduction relation (structural semantics used for plain processes);
the reduction relation including interaction with the environment.

Is this correct, or did I miss anything?

You are roughly correct. From an operational point-of-view, applied-$\pi$ is 'just' a $\pi$-calculus where interesting  values (rather than just pure names) can be communicated.

Note that in process theory we usually care about coarser notions of equality, such as observational equivalence. This is defined in Section 4.1. Alas observational equivalence is hard to work with in practise due to the universal quantification over all contexts, so we define a second relation which is easier to deal with, in this case  labelled bisimilarity. In order to do this, we need labelled transitions rather than reductions. We must show that  these two forms of computation coincide.

To make matters even more complicated, Theorem 1 which claims that observational equivalence coincides with labelled bisimilarity is wrong.


Is Quantum Computer analog? We used to have analog computers several decades ago. Modern days computers are Digital. What about Quantum computers? Is it analog or digital? I am asking this since qubit can be many things at the same time.

No, quantum computers are not the same as analog computers (at least in principle).

Analog computers simulate the (mathematical) problem to be solved by
building a physical system that obeys the same constraints/laws as the
mathematical problem. The answers are obtained by observing and
measuring the behavior of the physical simulation. Its accuracy is
that of the simulation (there may be parasitic effects), the accuracy
of the initial conditions, the setting of problem parameters in
particular, and the measurement on the result.

Accuracy may also be limited by the scale range of applicability of
the phenomena used for the simulation. For example, if the answer is
given by a level of water in some container, you may be limited by
capillarity effects (which can be accounted for to some extent) and by
the fact that measuring water level with more accurcy that the
diameter of a molecule may not be very meaningful.

I used to think that a major difference is that analog computing is in principle
based on the simulation of continuous laws, involving reals, while
digital computing operates exclusively on countable sets. But, in the light of current knowledge in computing theory, this
distinction is probably naive because I suspect that physics could be
formalized as well using only computable reals, of which there is only
a countable number.

Quantum computing will mainly allow you to do several digital computations in
parallel (to state it simply). It is always a finite cross product of
several computations, and hence stays in the countable realm. You may
think of it as the cross-product construction of an automaton that
simulates two or more computations of simpler automata (though it is
even less general than that from what I understand of it). These
finite cross product constructions never leave the countable realm.


treewidth of a given graph Is the treewidth of this graph equal to 2?

I have tried to prove it through the definition of a tree decomposition.

If its not correct can someone give any hints?

In the survey Treewidth, partial $k$-trees, and chordal graphs by Pinar Heggernes, we have the following lemma, whose proof is given as an exercise.

  Lemma. Let $(\{X_i \mid i \in I\}, T = (I, M))$ be a tree decomposition of $G = (V, E)$, and let $K \subseteq V$ be a clique in $G$.  Then there exists an $i \in I$ with $K \subseteq X_i$.

Prove this lemma, and conclude that, as Yuval answered,

  Corollary. For every graph $G$, $tw(G) \geq \omega(G) - 1$.

Conclude that the treewidth is at least three.

The treewidth happens to be at most three as well, but that's a different exercise.


Bottom-up algorithm to build subset of maximum weight I have this problem of obtaining a subset of maximum weight from a given array of size n (the i-th element is the weigth of the item i) - lets call it P. The only restriction is defined by an array R of size n: for each j in R[i] we have that  the subset can not contain both P[i] and P[j].
How do I build a DP bottom-up solution for this problem?

This is the maximum-weight independent set problem, which is known to be NP-hard.  Therefore, there is unlikely to be any efficient solution. However, you could use any of the standard algorithms for this problem, if you're willing to accept an exponential-time algorithm.


Why are Red-Black trees so popular? It seems that everywhere I look, data structures are being implemented using red-black trees (std::set in C++, SortedDictionary in C#, etc.)

Having just covered (a,b), red-black & AVL trees in my algorithms class, here's what I got out (also from asking around professors, looking through a few books and googling a bit):

AVL trees have smaller average depth than red-black trees, and thus searching for a value in AVL tree is consistently faster.
Red-black trees make less structural changes to balance themselves than AVL trees, which could make them potentially faster for insert/delete. I'm saying potentially, because this would depend on the cost of the structural change to the tree, as this will depend a lot on the runtime and implemntation (might also be completely different in a functional language when the tree is immutable?)

There are many benchmarks online that compare AVL and Red-black trees, but what struck me is that my professor basically said, that usually you'd do one of two things:

Either you don't really care that much about performance, in which case the 10-20% difference of AVL vs Red-black in most cases won't matter at all.
Or you really care about performance, in which you case you'd ditch both AVL and Red-black trees, and go with B-trees, which can be tweaked to work much better (or (a,b)-trees, I'm gonna put all of those in one basket.)

The reason for that is because a B-tree stores data more compactly in memory (one node contains many values) there will be much fewer cache misses. You could also tweak the implementation based on the use case, and make the order of the B-tree depend on the CPU cache size, etc.

The problem is that I can't find almost any source that would analyze real life usage of different implementations of search trees on real modern hardware. I've looked through many books on algorithms and haven't found anything that would compare different tree variants together, other than showing that one has smaller average depth than the other one (which doesn't really say much of how the tree will behave in real programs.)

That being said, is there a particular reason why Red-black trees are being used everywhere, when based on what is said above, B-trees should be outperforming them? (as the only benchmark I could find also shows http://lh3lh3.users.sourceforge.net/udb.shtml, but it might just be a matter of the specific implementation). Or is the reason why everyone uses Red-black trees because they're rather easy to implement, or to put it in different words, hard to implement poorly?

Also, how does this change when one moves to the realm of functional languages? It seems that both Clojure and Scala use Hash array mapped tries, where Clojure uses a branching factor of 32.

To quote from the answer to “Traversals from the root in AVL trees and Red Black Trees” question

  For some kinds of binary search trees, including red-black trees but
  not AVL trees, the "fixes" to the tree can fairly easily be predicted
  on the way down and performed during a single top-down pass, making
  the second pass unnecessary. Such insertion algorithms are typically
  implemented with a loop rather than recursion, and often run slightly
  faster in practice than their two-pass counterparts.

So a RedBlack tree insert can be implemented without recursion, on some CPUs recursion is very expensive if you overrun the function call cache  (e.g SPARC due to is use of Register window)

(I have seen software run over 10 times as fast on the Sparc by removing one function call, that resulted in a often called code path being too deep for the register window.   As you don't know how deep the register window will be on your customer's system, and you don't know how far down the call stack you are in the "hot code path", not using recursion make like more predictable.)

Also not risking running out of stack is a benefit.


Computing a pre-topological sort using a BFS/a queue Computing a topological sort in a DAG using a queue simply amounts to putting the nodes with indegree 0 in a queue, and going through the queue removing these nodes from the graph and adding the nodes that are newly with indegree 0.

This of course does not apply to computing a pre-topological order in a general graph, that is, an order satisfying:

    If $u\leadsto v$ and not $v \leadsto u$, then $u$ appears before $v$.

Such an order is used for instance in Kosaraju's algorithm, and the wikipedia page states:

  As given above, the algorithm for simplicity employs depth-first
  search, but it could just as well use breadth-first search as long as
  the post-order property is preserved.

I believe that what is meant by "the post-order property" is just the pre-topological property.

Question:  How can one compute a pre-topological order using a BFS(-like) algorithm?

For post-order see: https://en.wikipedia.org/wiki/Tree_traversal#Post-order.

The algorithm just says perform step 2 using BFS traversal rather than DFS traversal, and then let $L$ be vertices of BFS in the postorder. After that perform step 3 to compute SCCs.


Is the difference of a non-recursive and recursive set recursive? I have two sets B which is recursively enumerable and is not recursive, and A which is recursive. Is $A-B$ recursive and / or recursively enumerable? What about $B-A$?

$B-A$ is obviously recursively enumerable (to generate its elements, I can generate B's elements and check if they are in A).

If A is the empty set or $A \cap B$ is the empty set, it's easy. Otherwise, I believe $B-A$ is not recursive (I can't tell if a number is in B, since B is not recursive) and $A-B$ is not recursively enumerable (I can generate A's elements, but I can't check if they are in B), so it's not recursive either.

Am I wrong? How can I actually (and formally) prove any of those?

The empty set is recursive, hence B cannot be the empty set.

You are right the B-A is recursively enumerable.

You cannot prove B-A is not recursive for a good reason: it may be
recursive. Maybe you can imagine an example of A recursive, B
not recursive, and B-A recursive. Hint: it is not even necessary that
B be recursively enumerable, or A recursive.

Proof that $B-A$ can have properties more specific than recursively
enumerability (i.e. compatible with being recursively enumerable),
indpendently of the properties of B.

   Consider 2 disjoint alphabets $\Sigma$ and $\Sigma'$, such that
 $\Sigma\cap\Sigma'=\emptyset$. Take $C=\Sigma'\,^*$ and
 $A=\Sigma^*$. Let $E$ be a non-recursive language in $\Sigma^*$. Let
 $B=C\cup E$. Then $B$ is a non-recursive language on the alphabet $\Sigma\cup\Sigma'$, because $C$ is recursive (trivially). Now you can see that $B-A=C$ since substracting $A$ removes precisely $E$, i.e. all words in B that are in $\Sigma^*$. So you have $B$ non-recursive, and both $A$ and B-A are recursive. Here I chose $A$ recursive. But I could have chosen any non-recursive language on $\Sigma^*$ that contains $E$.

Similarly, you cannot prove anything about A-B. Think why.


Can an algorithm run in "O(n/a)" time? On one hand, it seems to make no sense, because of the following:

When expanded, the claim $f(n,a) \in O(n/a)$ would be

  There exist $C > 0$, $n_0$, and $a_0$ such that if $n \geq n_0$ and $a \geq a_0$, then $f(n,a) \leq C \cdot n/a$.

Now, given any $\epsilon > 0$, we can find an $a_\epsilon \geq a_0$ such that
$C \cdot n_0/a_\epsilon < \epsilon$, and thus $f(n_0, a_\epsilon) < \epsilon$.

So for any $\epsilon$, there is an input, with $n = n_0$ and $a = a_\epsilon$, at which the algorithm takes less than $\epsilon$ time to run.
But any nontrivial algorithm performs at least one operation, regardless of the input. So this seems nonsensical.

On the other hand, you can imagine someone saying that some approximation algorithm runs in time "$O(n/a)$", where $n$ is the size of the input and $a$ is the maximum multiplicative error.

And in fact, there is a paper in which an algorithm is claimed to run in "$\tilde{O}(\frac{n}{A^3 \epsilon})$" time. (Yes, I know $\tilde{O}$ is different from $O$). I asked a longer question about that
here. This question is an attempt to isolate the core confusion there.

For approximation algorithms, the algorithm must return an answer within a factor of $1\pm\epsilon$ of the true value. As such, smaller values of $\epsilon$ correspond to better approximations. As such, a running time that's polynomial in $n$ and $1/\epsilon$ is what you'd intuitively look for: it's saying that a better approximation (smaller $\epsilon$, so larger $1/\epsilon$) will take more time, but not by an unerasonable amount.

Also, note that we typically have an upper bound on $\epsilon$. For example, suppose we want to approximately compute the distance between two distinct vertices in a connected graph. We know the distance must be between $1$ and $n$ the number of vertices) so if we just want an approximation within $1\pm\epsilon$ and $\epsilon\ge\sqrt{n}$, we can just return $\sqrt{n}$.


What if traversal order of two of pre-order, in-order and post-order is same? Supposing a tree T has the identical:

Pre-order traversal and in-order traversal
Pre-order traversal and post-order traversal
In-order traversal and post-order traversal

How does T look like?

From the previous discussion in SO, I learned that pre- and post-order are same iff. only one node is in the T.

How about the left two conditions?

I suppose that only purely left-skewed tree can make post- and in-order the same, and only right-skewed tree can make pre- and in-order the same.

Am I on the right way?

Edit: To avoid being solely a 'yes' or 'no' problem, the actual doubt is that how to prove this statement, but I have a idea about the proofs using contradiction. So maybe this problem is a little redundant.

A proper proof uses the recursive definitions of the tree-orders. Here is a sketch.

For inorder the recursive definition is: in(left) - root - in(right).
For postorder we similarly have: post(left) - post(right) - root.

Look at the position of root in both orders. If we want this to be the same we need to have there are no nodes in in(right) which means the right subtree (at the root) is empty. Same for the root at other levels.


Equivalence between MIN UNCUT and MIN-CSP_XOR In this paper

  Agarwal, Amit, et al. "O (√ log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems." Proceedings of the thirty-seventh annual ACM symposium on Theory of computing. 2005.

Agarwal et al. claim that the following two problems are equivalent.

  Consider boolean variables $b_1,\dots ,b_n$ and a set of constraints of the form $b_i \oplus b_j = 0$ and $b_i \oplus b_j = 1$. The goal is to minimize the number of unsatisfied constraints.

and

  Given a graph $G=(V,E)$ find a cut that minimizes the number of uncut edges.

If constraints were only of the form $b_i \oplus b_j = 1$, the equivalence is straightforward. However, if we also consider constraints of the form $b_i \oplus b_j = 0$, the first formulation seems more general to me.

How are these equivalent?

Suppose we are given a set of constraints of the form $b_i \oplus b_j = c$. We construct a graph with one vertex corresponding to each $b_i$. For each constraint of the form $b_i \oplus b_j = 1$, we add an edge $\{i,j\}$. For each constraint of the form $b_i \oplus b_j = 0$, we add a new vertex $x$, and two edges $\{i,x\},\{j,x\}$.

We can think of a cut as a partition of the vertices into two parts. For a constraint of the form $b_i \oplus b_j = 1$, the constraint is unsatisfied iff $i,j$ belong to the same part iff $\{i,j\}$ is uncut. For a constraint of the form $b_i \oplus b_j = 0$, there are two cases:

If the constraint is unsatisfied, then $i,j$ belong to different parts, and so exactly one of the edges $\{i,x\},\{j,x\}$ is uncut.
If the constraint is not unsatisfied, then $i,j$ belong to the same part, and so (depending on the location of $x$) either zero or two of the edges $\{i,x\},\{j,x\}$ are uncut. Since we are aiming to minimize the number of uncut edges, we can assume that zero are uncut.

In total, the number of unsatisfied constraints is the same as the number of uncut edges.


Why does garbage collection extend only to memory and not other resource types? It seems like people got tired of manual memory management, so they invented garbage collection, and life was reasonably good.  But what about every other resource types?  File descriptors, sockets, or even user created data like database connections?

This feels like a naive question but I cannot find any place where anyone has asked it.  Let's consider file descriptors.  Say a program knows that it will only be allowed to have 4000 fds available when it starts.  Whenever it performs an operation that will open a file descriptor, what if it would

Check to make sure that it isn't about to run out.
If it is, trigger the garbage collector, which will free a bunch of memory.
If some of the memory freed held references to file descriptors, close them immediately.  It knows the memory belonged to a resource because the memory tied to that resource was registered into a 'file descriptor registry', for lack of a better term, when it was first opened.
Open a new file descriptor, copy it into new memory, register that memory location into the 'file descriptor registry' and return it to the user.

So the resource would not be freed promptly, but it would be freed whenever the gc ran which includes at the very least, right before the resource was about to run out, assuming it isn't being entirely utilized.

And it seems like that would be sufficient for many user defined resource cleanup issues.  I managed to find a single comment here that references doing cleanup similar to this in C++ with a thread that contains a reference to a resource and cleans it up when only it has a single reference remaining (from the cleanup thread), but I can't find any evidence of this being a library or part of any existing language.

GC deals with a predictable and reserved resource. The VM has total control over it and has total control over what instances are created and when. The keywords here are "reserved" and "total control". Handles are allocated by the OS, and pointers are... well pointers to resources allocated outside the managed space. Because of that, handles and pointers are not restricted to be used inside managed code. They can be used - and often are - by managed and unmanaged code running on the same process.

A "Resource Collector" would be able to verify if a handle/pointer is being used within a managed space or not, but it by definition is unaware of what's happening outside it's memory space (and, to make things worse some handles can be used across process boundaries).

A practical example is the .NET CLR. One can use flavored C++ to write code which works with both managed and unmanaged memory spaces; handles, pointers and references can be passed around between managed and unmanaged code. The unmanaged code must use special constructs/types to allow the CLR to keep tracking of references being made to it's managed resources. But that's the best it can do. It cannot do the same with handles and pointers, and because of that said Resource Collector would not know if it's ok to release a particular handle or pointer.

edit: Regarding the .NET CLR, I'm not experienced with C++ development with the .NET platform. Maybe there are special mechanisms in place that allows the CLR to keep tracking of references to handles/pointers between managed and unmanaged code. If that's the case then the CLR could take care of the lifetime of those resources and release them when there all references to them are cleared (well, at least in some scenarios it could). Either way, best practices dictate that handles (especially those pointing to files) and pointers should be released as soon as they are not needed. A Resource Collector would be not-complying with that, that's another reason to not have one.

edit 2: It's relatively trivial on the CLR/JVM/VMs-in-general to write some code to free up a particular handle if it's used only inside the managed space. In .NET would be something like:

// This class offends many best practices, but it would do the job.
public class AutoReleaseFileHandle {
    // keeps track of how many instances of this class is in memory
    private static int _toBeReleased = 0;

    // the threshold when a garbage collection should be forced
    private const int MAX_FILES = 100;

    public AutoReleaseFileHandle(FileStream fileStream) {
       // Force garbage collection if max files are reached.
       if (_toBeReleased >= MAX_FILES) {
          GC.Collect();
       }
       // increment counter
       Interlocked.Increment(ref _toBeReleased);
       FileStream = fileStream;
    }

    public FileStream { get; private set; }

    private void ReleaseFileStream(FileStream fs) {
       // decrement counter
       Interlocked.Decrement(ref _toBeReleased);
       FileStream.Close();
       FileStream.Dispose();
       FileStream = null;
    }

    // Close and Dispose the Stream when this class is collected by the GC.
    ~AutoReleaseFileHandle() {
       ReleaseFileStream(FileStream);
    }

    // because it's .NET this class should also implement IDisposable
    // to allow the user to dispose the resources imperatively if s/he wants
    // to.
    private bool _disposed = false;
    public void Dispose() {
      if (_disposed) {
        return;
      }
      _disposed = true;
      // tells GC to not call the finalizer for this instance.
      GC.SupressFinalizer(this);

      ReleaseFileStream(FileStream);
    }
}

// use it
// for it to work, fs.Dispose() should not be called directly,
var fs = File.Open("path/to/file");
var autoRelease = new AutoReleaseFileHandle(fs);


web content "mining" using supervised learning tequniques We're accessing an API of a web system for obtaining product information. We require some additional information, which is not available through the API. This information is publically available for each product visually - through the source code for each item on its item page. We've written an algorithm which parses this information from the web page for each item, but that will be highly ineffective in the long run, since the algorithm will simply stop working if and when they decide to change the source code ( for example - redesign of the front end ).

I feel like there should be a supservised learning approach to this problem, however I'm unaware if there exist such solutions.

What are some good aproaches to this kind of problems ?

Regards.

In short, this is probably difficult.

Your question is not fully specified, since you did not write the details of the data you are parsing and since estimating the possible changes to it is a matter of guesswork.

Once this web site changes format, then if we assume that the products remain the same, you are essentially looking at supervised learning task: given a list of known product web pages, make an "extractor function" that outputs the desired field.

If you are lucky and all the product pages are identically structured then this problem might be quite easy. You simply need to identify the path to the node of the HTML in which the desired information lies. On the other hand, if the web pages have a varied structure, or no structure at all, then the problem may be much more difficult.

There are some academic works in these areas, but don't get your hopes up. Look for the keywords "automatic web extraction".


Looking for interesting unanswered questions within complexity theory for a project I'm looking for interesting open questions in complexity theory that someone with an undergraduate degree in math and comp/sci could theoretically tackle. I have strong interest in the polynomial hierarchy, and the study of probabilistic classes like RP, co-RP, ZPP, BPP, and also their logarithmic counterparts. I also have some interest in quantum computing complexity theory, but I'm afraid my knowledge of quantum isn't that strong. (Only the basics from my modern physics class, which included some quantum). Important: must be new research or new expansion on previous research, a question that either hasn't been asked or hasn't been answered successfully that I might be able to say something interesting about, even if I don't ultimately solve it. I'm willing to learn any necessary programming languages/programs/methods/etc to the end of answering this question (or trying to)!

Note: this is for a senior year undergraduate thesis in math / comp sci.

Thanks for any suggestions!

Edit: An example might be to analyze the complexity of a particular problem that hasn't been (formally) analyzed yet but may yield interesting results.

Do something interesting with visibly languages. They are a relatively recent topic with many useful practical applications. For example, I would find it interesting to better understand the role of synchronization here, compared to the role of synchronization for the theory of codes. Already the simplest case could be interesting, where the visibly language just distinguishes between inner symbols and separator symbols, and the considered codes are just bifix code.

David Richerby is right that this questions allows opinion biased answers. The origins of the opinions voiced in this answer can be found here.


Is this a valid DFA for (a|b)*abb? I'm trying to come up with an alternate DFA for accepting (a|b)*abb than the one present in the dragon book. Here's the one I tried:

It seems valid to me but I'm not sure. Also, is there a way to check for validity of automatons so that I don't end up bugging you guys next time?

Your DFA does not recognize $(a|b)^*abb$. For example it does not recognize $abb$.


The set of all eventually periodic words is not Buchi Recognizable? An $\omega$-word $s \in \Sigma^\omega$ is eventually periodic if it is of the form $s = uv^\omega$ for finite words $u, v \in \Sigma^*$.

I want to show that the set of all eventually periodic words is not buchi-recognizable.

I do not know how to proceed. My attempt was to find a part of the word and then pump it indefinitely to get something that is not in the language. However, pumping right away does not seem to work since that would give an eventually periodic string again.

Note that every non-empty Büchi recognizable language contains at least one eventually periodic word and that the class of all Büchi recognizable languages is closed under complement. Thus, if the language $L = \{w \in \Sigma^\omega \mid w \text{ is eventually periodic}\}$ was Büchi recognizable its complement $L^C$ is also Büchi recognizable but of course contains no eventually periodic word contradicting the first fact I stated.


Is there an existing data structure that is of fixed size, and will push the oldest/last element out if a new element is inserted? I'm looking for a data structure that will push its oldest/last element out if a new element is inserted. For example, let D represent the structure. D contains 3 elements of the type Number D's default values will be initialized to 1, 2 and 3.

$$D = [1, 2, 3]$$

If a Number that contains the value 5 is inserted into D, 3 will be pushed out, while 1 and 2 are shifted right.

$$D = [5, 1, 2]$$

The first thing that comes to mind would be an array, but the definition does not include the pushing behavior.

Fixed-size queues are often implemented using what some people call circular buffers. If you remove the protection against it being full, you get the desired behaviour.

Of course, no actual pushing will happen in the array -- that would be too expensive -- but it will look like it from the outside.


Is there a way to test if two NFAs accept the same language? Or at least generate a set of strings that one NFA accepts, so I can feed it into the other NFA.  If I do a search through every path of the NFA, will that work?  Although that will take a long time.

The decision problem is PSPACE-complete as Shaull noted.

However, it turns out that in practice it is often possible to decide NFA equivalence reasonably quickly.  Mayr and Clemente (based on experimental evidence) claim that the average-case complexity scales quadratically.  Their techniques rely on pruning the underlying labelled transition system via local approximations of trace inclusions.

Just like SAT is NP-complete in a worst-case analysis, yet often turns out surprisingly tractable for real-world instances, it therefore seems likely that NFA equivalence can be decided efficiently for many real-world instances.

Richard Mayr and Lorenzo Clemente, Advanced automata minimization, POPL 2013, doi:10.1145/2429069.2429079 (preprint)


Are there other interpretations of |G| than |V|, that is |V(G)|? This may be a basic question, but I'm hoping someone can settle this nagging doubt I'm having. I'm reading up on FPT complexity using a book by Downey and Fellows. It has some introductory examples which detail complexity in terms of $|G|$, which seems to denote $|V|$ as mentioned here.

The sections containing those examples explicitly refer to $|V(G)|$ however, so I wonder if there might be other interpretations of $|G|$ that convey some nuance in terms of complexity I'm missing, or can I safely assume that it does in fact mean $|V|$?

I don't have the book, so I looked through the pages available on Google Scholar. It seems that they use $|G|$ to denote the size of a graph description that is $|V(G)| + |E(G)|$.

For example on page 24 they say that Vertex Cover is solvable in $2^k|G|$ time using bounded search tree method. In fact this method gives $2^kk|V|$ time for graphs with at most $k(|V| - 1)$ edges (it's easy to show that otherwise graph doesn't have Vertex Cover of size $k$). According to this "reverse engineering" $|G|$ corresponds to $k|V|$ that is essentially $|V| + |E|$.


Proof that a node N balanced binary search tree has $2^i - 1$ children where $i$ is the position of the first 1-bit in N, starting from 0 I was binary indexed trees and I came across this article. One part of the justification was the following:

  Given that the (binary search tree) tree is perfectly balanced, a node N will have exactly
  $2^{i}-1$ children on each side, where $i$ is the position of the first
  1-bit in N, starting from 0, and counting from least significant to
  most significant. For example, for $N=11000$, we have $i=3$. For $N=111$, we
  have $i = 0$. This can easily be checked by recalling that the left
  children of $N$ consist of every number lower than $N$ (similarly for the
  right side). The “minus 1″ is there because we can’t count $N$ itself as
  being a child of $N$.

First off, I believe that the authors claim that

  "This can easily be checked by recalling that the left children of $N$
  consist of every number lower than $N$"

is not entirely accurate, as for example, in the following BBST:

      4
   /     \
  2       6
 / \     / \
1   3   5   7

The left children of node 6 do not contain every number lower than 6. Nevertheless, the formula $2^i - 1$ still holds true. Why does this work?

Since I'm still learning proof techniques, this is a good practice for me too. Please verify the solution yourself. We shall prove this with a series of lemma.

Lemma 1.
A perfectly balanced tree with height $h$ would have $n = 2^{h+1}-1$ nodes.

Proof.
Trivial proof by induction.

Lemma 2.
A perfectly balanced indexed binary search tree have root with value $2^h$.

Proof.
By lemma 1, there are $2^h-1$ nodes on the left subtree of the root. By constraint of binary search tree, the root element will have value $(2^h-1)+1=2^h$.

Lemma 3.
In a perfectly balanced indexed binary search tree, any node $A$ with value $k$, and its rooted subtree of height $h$, have left child with value $k-2^{h-1}$ and right child with value $k+2^{h-1}$.

Proof.
Due to the properties of the tree, the value of the left child of $A$ is the value of $A$ itself, which is $k$, subtracted by the number of nodes on the right subtree of the left child, which is $2^{h-1}-1$ from lemma 1, added by one. This is trivial upon drawing out such a tree, which I shall not include here. Hence, the value of left child is $k-(2^{h-1}-1)-1=k-2^{h-1}$. A similar proof will suffice for the value of right child.

Theorem.
In a perfectly balanced binary search tree with height $h$, any node $A$ will have exactly $2^i−1$ children on each side, where $i$ is the position of the first $1$-bit in the value of node $A$, starting from $0$, and counting from least significant to most significant.

Proof.
We shall prove by induction from root down to leaves. By lemma 2, the root value is $2^h$, which binary representation is

$$
1\overbrace{0\dots0}^h
$$

The position of the first $1$-bit will therefore be in the $h$ position. Substituting $i=h$, we have $2^h-1$ children on each side, which agree with lemma 1.

Now, we assume any node $A$ satisfy the stated theorem. By lemma 3, the left child of node $A$ with value $k$, and its rooted subtree of height $h$, have left child with value $k-2^{h-1}$. By lemma 1, we know that $i=h$, so it suffice to show that the position of the first $1$-bit in $k-2^{h-1}$ appears a bit before that in $k$. In other words, we can assume that the first $1$-bit in $k$ appears at position $h$, and we need to show that the first $1$-bit in $k-2^{h-1}$ appears at position $h-1$.

In binary, we can represent $k$ as

$$
1\dots1\overbrace{0\dots0}^{h}
$$

and we are subtracting it from $2^{h-1}$, as represented by

$$
1\overbrace{0\dots0}^{h-1}
$$

Since $k$ is all zeros in the first $h$ bits, subtracting by $2^{h-1}$ will cause bit $h$ to become $0$ and bit $h-1$ to become $1$, which retain the stated proposition. A similar prove can be done for the right child of $A$. In addition, one also need to prove the termination case to complete this prove, which I also leave out here.


What is a flow through the cut in the Ford-Fulkerson algorithm? In page 12 of the slide, it states flow across a cut $(S, T)$ is $f(S, T) = \sum_{u\in S} \sum_{v\in T} f(u,v) - \sum_{u\in S} \sum_{v\in T} f(v,u)$.

I think the first part $\sum_{u\in S} \sum_{v\in T} f(u,v)$ is the amount of flow entering the network at the source node. The second part $\sum_{u\in S} \sum_{v\in T} f(v,u)$ is the amount of flow leaving the network at the sink node. Shouldn't these two be the same? Why the flow across a cut is the difference of these two?

Consider a graph of two node $s$ and $t$ and one edge $(s,t)$ with a flow $f$, $f(s,t)=1$.

Let $S=\{s\}$ and $T=\{t\}$. Then the flow across the cut $(S, T)$ is, apparently 1. Or,
$$f(S, T) = \sum_{u\in S} \sum_{v\in T} f(u,v) - \sum_{u\in S} \sum_{v\in T} f(v,u)= f(u,v)=1.$$

$\sum_{u\in S} \sum_{v\in T} f(u,v)$ is the flow from $S$ to $T$.  $\sum_{u\in S} \sum_{v\in T}f(v,u)$ is the flow from $T$ to $S$. Their difference is the flow across $(S,T)$.

Note that all ideas above does not depend on which is source node nor which is sink node. The flow across a cut $(S,T)$ just means how much (water, current, resource, etc) is flowing from $S$ to $T$.

It happens that it is required the source node is in $S$ and the sink node is in $T$ in that part of the proof. That requirement does NOT affect the explanation above. It is just a convenience measure since in a flow network we are only interested in that kind of cut. However, it does make the situation somewhat confusing.

Now let $s$ be the source node and $t$ be sink node. So that the cut $(S,T)$ above is indeed a cut as required in the proof.

  the first part $\sum_{u\in S} \sum_{v\in T} f(u,v)$ is the amount of flow entering the network at the source node. The second part $\sum_{u\in S} \sum_{v\in T} f(v,u)$ is the amount of flow leaving the network at the sink node. Shouldn't these two be the same? Why the flow across a cut is the difference of these two?

The first part $\sum_{u\in S} \sum_{v\in T} f(u,v)=f(u,v)$ is not necessarily the amount of flow entering the network at the source node, although it happens to be in the current example.

The second part $\sum_{u\in S} \sum_{v\in T} f(v,u)=0$ is not necessarily the amount of flow leaving the network at the sink node. In fact, it is not in the current example!
The amount of flow leaving the network at the sink node is
$\sum_{u\in V}f(u,t)=1$. Now, can you read the following again?

The second part $\sum_{u\in S} \sum_{v\in T} f(v,u)$ is the flow from $T$ to $S$ while $\sum_{u\in V}f(u,\text{the sink node})$ is the flow from all nodes to the sink node.
Even if $T$ consists of the sink node only, these two sums are different. The former is for flow from the sink node and the latter is for flow to the sink node. They are not only different. They are very different! They are too different.

Here are a few easy exercises about a general flow network $G=(V,E)$ with source node $s$ and sink node $t$ and a flow $f$.

Exercise 1. The amount of flow entering the network at the source node is the flow across the cut $(\{s\}, V\setminus\{s\})$.

Exercise 2. The amount of flow leaving the network at the sink node is the flow across the cut $(V\setminus\{t\}, \{t\})$.

Exercise 3. The amount of flow across any cut is the same.


Time Complexity: Intuition for Recursive Algorithm I decide to learn more about dynamic programming, so I started reading the Dynamic Programming chapter from the CLSR book.

The first example problem presented there is Rod Cutting (15.1). Given a rod of length n and a list of prices for rods of any sizes figure out how to cut the rod so that the price of the pieces will be maximized (and one can only cut at even positions).

The first recursive algorithm presented there is the following

CutRod(p, n)
  if n == 0
    return 0
  q = -inf
  for i = 1 to n
    q = max(q, p[i] + CutRod(p, n -1))
  return q

n is the size of the rod and p an array that contains the prices.

I understand the algorithm, the problem I have is that I thought intuitively the time complexity of such an algorithm would be O(b^d) (where b is the branching factor and d the depth of the recursion tree) which would be O(n^n).

In the book the recurrence relation is presented: T(0) = 1 and T(n) = 1 + sum(j=0, n-1, T(j)) Then it is explained that the complexity following from this is O(2^n) which you can easily be seen by expand the recurrence relation.

How can I quickly see that my initial intuition was wrong? And in general when looking at a recursive algo how can I figure out weather the time complexity is O(b^d) or not.

Based on the code you show there, your intuition is right.

However, it looks like there is a typo in the code and the next-to-last line should have been

  q = max(q, p[i] + CutRod(p, n-i))

i.e., n-i rather than n-1.  Try to work through a proof of correctness, or through a few examples, to see why I say that.  The running time analysis they show is for the corrected code, rather than the code with the typo, and then once you make that correction to the code, the recurrence relation they provide is correct.


DFA that accepts decimal representations of a natural number divisible by 43 First, I have tried to build a DFA over the alphabet $\sum = \{0,\dots, 9\}$ that accepts all decimal representations of natural numbers divisible by 3, which is quite easy because of the digit sum. For this I choose the states $Q = \mathbb{Z}/3\mathbb{Z}\cup\{q_0\}$ ($q_0$ to avoid the empty word), start state $q_0$, accept states $\{[0]_3\}$ and $\delta(q, w) =\begin{cases} [w]_3 &\mbox{if } q = q_0 \\
[q + w]_3 & \mbox{else } \end{cases}$

Of course, it doesn't work that way for natural numbers divisible by 43. For 43 itself, I would end in $[7]_{43}$, which wouldn't be an accepting state. Is there any way I can add something there or do you have other suggestions on how to do this? Thanks.

If the string read has a certain decimal value, then reading the next digit changes that value: multiply by $10$ and add that digit. The DFA keeps track of that value modulo $43$. Thus, for $q\in \{0,1,\dots,42\}$ and $a\in \{0,1,\dots,9\}$ you do

$\qquad \delta(q,a) = (10\cdot q + a) \bmod 43$.

Note that the DFA does not actually perform the computation; the transition is hard-coded.


How is expected value in entropy derived? I was self learning about entropy and came across this equation.
$$
H = - \sum p(x) \log p(x)
$$
The equation for entropy in expected value,
$$
H(x) = \operatorname*{\mathbb{E}}_{X \sim P}[I(x)] = -\operatorname*{\mathbb{E}}_{X \sim P}[\log P(x)].
$$
But the expected value is written as
$$
\mathbb{E}[X] = \sum_{i=1}^k x_i p_i = x_1p_1 + x_2p_2 + \cdots + x_k p_k
$$
Using the above expected value formula, I expected the entropy equation looks something like this
$$H(x)= -\operatorname*{\mathbb{E}}_{x \sim P(x)}[\log P(x)]= - \sum xP(x)\log P(x) $$
where is the $x$ gone in the real entropy formula in summation notation?

Here is the definition of the expectation of a discrete random variable $Y$:
$$
\mathbb{E}[Y] = -\sum_y \Pr[Y = y] \cdot y.
$$
In your case, $Y = \log P(X)$, where $X \sim P$. Therefore
$$
\mathbb{E}[X] = \sum_y \Pr[\log P(X) = y] \cdot y.
$$
Notice that
$$
\Pr[-\log P(X) = y] = \sum_{x\colon \log P(x)=y} \Pr[X = x] \cdot y = \sum_{x\colon \log P(x)=y} \Pr[X = x] \cdot \log P(x).
$$
Therefore
$$
\mathbb{E}[X] = \sum_y \sum_{x\colon \log P(x) = y} \Pr[X = x] \cdot \log P(x) = \sum_x \Pr[X = x] \log P(x) = \sum_x P(x) \log P(x).
$$


Is the language { | p and n are natural numbers and there's no prime number in [p,p+n]} belongs to NP class? I was wondering if the following language belongs to NP class and if its complimentary belongs to NP class:

\begin{align}
C=\left\{\langle p,n\rangle\mid\right.&\ \left.  p \text{ and $n$ are natural numbers}\right.\\
&\left.\text{ and there's no prime number in the range}\left[p,p+n\right]\right\}
\end{align}

could you please check if my reasoning is okay to deduce NP?
(I am not sure, but here's what I think):
for each word $\langle p,n\rangle \in C$ we know that the word belongs to C because there exists a primal certificate -  an nontrivial divisor to any of the numbers between $[p,p+n]$, though I am not really sure it is in NP.

regarding the complement: I think it is in NP because the compliment compositeness can be decided by guessing a factor nondeterministically. But again I am not so sure about it and I don't know how to correctly prove and show it.

Would really appreciate your input on that as I am quite unsure and also checked textbooks and internet (and this site) about it.

Edit: for the sake of solving the problem, due to xskxzr's comment, let's assume p and n are represented by binary, as there's a difference according to his comment between p and n being represented in unary and binary(this is also quite interesting).

Note that there's always a prime between $p$ and $2p$ for any $p$ thus we can eliminate $n$ as a complexity parameter, as for any non-trivial  instance we have $n < p$.

The complement (there exists a prime in range $[p, p+n]$) is quite easy  (due to the shoulders of giants). There are various well-known polynomial size certificates of primality of $q$ you could return along with some $q \in [p, p+n]$ if that prime $q$ exists. Thus your language is in co-NP.

However the question of whether it is in NP or not seems very hard to me. Our input size is $b$ such that $2^b \approx p$. You need the existence of a $O(b^c)$ sized certificate that in the worst case asserts the compositeness of an exponentially large ($|[p, p+n]| \approx |[p, 2p]| \approx p \approx 2^b$) series of consecutive integers. From my intuition about number theory, finding such a certificate would be a major result, but disproving its existence would be as well. But perhaps someone with more number theoretic knowledge than me can pitch in if either of those turn out to be easy.


Why Turing wasn't wrong? Computer science is a science and as a science each thesis can be refutable. So, why there is no "major" counter-thesis?
After all, Einstein was a well known "genius" and has lived a long life and he has got many opponents. Why isn't it the same case for Turing?

Computer science is a science only by name. In practice, it is a blend of engineering, mathematics, and empirical science.

With that out of the way, here are a few comments about the Church–Turing thesis. First, about the thesis itself. We can think of at least three interpretations of the Church–Turing thesis. Under the first, stronger interpretation, any computation that can be done in the physical world can be modelled by (say) a Turing machine. This is a thesis which indeed can be refuted, and people have tried to refute it, though so far unsuccessfully (Scott Aaronson suggests to regard this as a "law of nature").

The second, weaker interpretation only claims that any computation done in practice (now) can be modelled by a Turing machine. This thesis is essentially correct, though to make it truly correct you need to make it mathematically precise; Nachum Dershowitz and Yuri Gurevich have done just that, though their formulation doesn't necessarily reflect the intuitive content of the thesis.

The third interpretation, very related to the second, is that any pseudocode that we can describe can be implemented on a Turing machine. We use this thesis implicitly whenever we describe and analyze algorithms, both in very theoretical areas (recursion theory, computational complexity, theoretical algorithms and data structures, approximation algorithms) and in more applied areas, in which the pseudocode is often translated to code in practice.

Second, in practice the more interesting thesis is what is sometimes called the Cook–Karp thesis. This thesis states that the class $\mathsf{P}$ embodies all decision problems that can be solved efficiently in practice. In my view, this thesis is dubious. There are three main attacks on this thesis.

The first attack is that the class $\mathsf{P}$ is defined asymptotically, whereas we are interested in problems of finite size. It could be that for practical input size, a problem which is perhaps not in $\mathsf{P}$ can be solved efficiently (for example, small cryptosystems can be broken even if they are secure). Conversely, it could be that a problem is in $\mathsf{P}$ but it cannot be solved efficiently, since the polynomial time "kicks in" only for large problems.

This is very related to the second attack, which is that polynomial time algorithms need not be efficient: they could have a large (big O) constant or a large exponent. A good example for a large constant is fast matrix multiplication algorithms, which are not practical due to the large constant. A good example for a large exponent is deterministic primality testing (the AKS algorithm), which isn't practical due to the large exponent.

A third attack, which is more speculative at this point, is that quantum computers can efficiently solve some problems which we think classical computers cannot. While quantum computers still exist only on paper, unless we believe that there is some fundamental obstacle to constructing them (as some people indeed do, for example Gil Kalai), we have to contend that in the future the class $\mathsf{P}$ would have to be enlarged to the corresponding quantum class $\mathsf{BQP}$.

A related attack states that randomized algorithms can be stronger than deterministic ones: for example randomizes primality testing is practical while the AKS algorithm isn't. However, it is believed that "randomness doesn't help", in the sense that $\mathsf{P}=\mathsf{BPP}$ (which doesn't mean that randomized algorithms can't be faster; it only means that they can only be polynomially faster).


A universal operator necessarily generates $\neg x$ for input $x,…,x$ I originally posted this on math.stackexchange, but then deleted it and moved it here since I think it would fit this site more.

I saw a claim in a slideshow from a basic computer architecture course that given some boolean operator $T(x_1,...,x_n)$, if it is universal then necessarily:
$$T(x,...,x)=\neg x$$
However, I found no explicit mention of this claim anywhere else, including here. Is it correct? And if so can one please provide a proof or a proof-idea? Because it was provided as a fact completely unrelated to the rest of the slides I have no idea how to approach it, and I am not sure I even have the right tools to do so.

I have already seen this question, for example, but there the proof is tailored towards a specific function. My problem is with proving the general case.

There are two ways to define a universal operator: when constants are allowed, and when they are not allowed. If constants are allowed, then one can define a universal operator which doesn't satisfy the claim, as follows:
$$
T(x,y,z) = \overline{x \land y} \land z.
$$
This is universal since $T(x,y,1)$ is the NAND operator, but $T(0,0,0) = 0$.

Now suppose that constants are not allowed. Since $T$ is universal, there is a $T$-circuit which computes the NOT function $x \mapsto \lnot x$. Let us now consider the possible values that $T(x,\ldots,x)$ takes:

$T(x,\ldots,x) = \lnot x$: in this case the claim holds.
$T(x,\ldots,x) = x$: in this case, induction shows that every $T$-circuit in which the only inputs are copies of $x$ necessarily computes the value of $x$; in particular, no $T$-circuit computes NOT.
$T(x,\ldots,x) = 0$: in this case, when $x = 0$, induction shows that every $T$-circuit always computes 0; in particular, it doesn't compute NOT.
$T(x,\ldots,x) = 1$: similar to the preceding case.

This shows that $T(x,\ldots,x)$ must compute $\lnot x$.


Is transfer learning applied on only similar datasets only? I am trying to make a CNN model on different brands of logos . Firstly , I wrote a CNN from scratch and trained it on which I got 70% accuracy, I have total 40 classes and each class has 100 images . I know it is too short, that is why I am now moving towards pretrained model. My question is that I read on Internet that Transfer learning applied on only similar datasets like lets say VGG model trained on Cats and Dogs , so we can use it for training the tiger images also . Can I use different dataset like I am using MobileNet on different brands of logos . Will it give good accuracy ?

Let me start by making an acknowledgement that in machine learning intuitions can be wrong and it is not possible to know beforehand what would work and what wouldn't work. That's why machine learning is very much an experiment based method.
Having made this acknowledgement let me tell you my intuition. If you transfer learning from image processing problem to a different image processing problem then it shouldn't hurt if your network is deep enough. Most likely, a convolutional network's earlier layers find simple features that are useful to describe any image. Like horizontal lines and diagonal lines. Then, the deeper layers vary according to specificity of the dataset to find more complex features.
Even if you are working on a wildly different image problem, what you can try to do is keep the earlier layers constant during the learning and just learn the deeper layers. After some learning you can allow the earlier layers to change as well to do some fine tuning.


CFG and PDA for the grammar that has perfectly nested parentheses and brackets I gotta make a CFG and PDA for the grammar that has perfectly nested parentheses and brackets.

$\qquad\begin{align}
 S &\to [S] \\
 S &\to (S) \\
 S &\to SS \\
 S &\to \varepsilon
\end{align}$

Not sure if this is correct, or how to make the PDA from it?

The language you study is a classic, the one-sided Dyck language (on two pairs of brackets). You can directly make a PDA by considering the following property of nested strings: every symbol closing bracket you read should match the last unmatched opening bracket. Keep the unmatched $[$ and $($ on the stack and you are ready to go.


Type Inference and Generalization I've been trying to understand type inference for Hindley-Milner-based languages, and I'm struggling to understand how generalization works. Let's say I have the following program in Haskell:

x :: Int
x = id 1

y :: Char
y = id 'a'

id :: a -> a
id x = x

If the type-checker traverses the program from top to bottom, then from x we can infer that the type of id must generalize Int -> Int, and from y we can infer that id must generalize Char -> Char, but I'm unclear how we can use these constraints without inferring a too-specific type for id.

If we check id first, then we can just instantiate its type in x and y, and use unification. However, if we have recursive or mutually recursive bindings, ensuring that all mentioned top-level bindings are typechecked before the binding itself would lead the type-checker into an infinite loop.

How are these issues resolved?

There are a few things to realize:

First, top level declarations are implicitly let-bound, so your code is equivalent to the following:

let
  x :: Int
  x = id 1

  y :: Char
  y = id 'a'

  id :: a -> a
  id x = x

Secondly, as was mentioned in the comments, Haskell will sort the let statements topologically, nesting them when it can, and any recursive uses are monotyped unless annotated.

Finally, the types of let-variables are generalized at their definition, but specialized at their use. So now we have (something close to):

let
  id :: a -> a
  id x = x
in let
  x :: Int
  x = id 1

  y :: Char
  y = id 'a'

Finally, we need to see that while variable types are generalized at their definition, they are specialized at their use.

So, this is roughly what inference does:

The checker infers the type $id : \alpha \to \alpha$, then generalizes this to $\forall a \ldotp a \to a$.
The checker puts $id : \forall a \ldotp a \to a$ into the environment for checking $x$ and $y$
While checking the definitions of $x$, at the use of $id$,
the type $\forall a \ldotp a \to a$ is instantiated to $\beta \to \beta$, where $\beta$ is a fresh unification variable.
While checking the definitions of $y$, at the use of $id$,
the type $\forall a \ldotp a \to a$ is instantiated to $\gamma \to \gamma$, where $\gamma$ is a different fresh unification variable.

Because the polymorphic type scheme is instantiated with unique variables at each use, the inference is able proceed without error.


Algorithm to find out the number of times a number occurs consecutively in an array in a range specified I have an array say

8 3 5 4 4 4 4 4 3 2 7 11 12 7 7 7 7 1 2

total =17 elements
now you are given a range say [2,11] both included ,now you have o find out the element that has occurred the max number of times and the number of times it has occurred

A simple traversing through the array in the range  and keeping the track of the each element is one solution but time complexity is O(N) and if we are given N queries time complexity = O(N^2). Any faster algo than this ?

Define a sub problem solution as the range of longest sub series.
If there are more than one we solution is 2 at most. The once at the tips of the range.
and there are exactly (n^2-n)/2 sub problems here.
You can solve each sub problem in o(n).

If you were to remember the results of problems you solved.
You can remember all in o(n*(n^2-n)/2) and it's fine.

But, If you consider Dynamic programming.
There is a bottom up series to solve each sub problem in o(1) time.

when trying to solve(i,j) two cases are to consider:

the range is at the tip. so consider increasing the result.
the range is at the tip. just return the longest. again up to 2 ranges.


Is there a difference between perfect, full and complete tree? Is there a difference between perfect, full and complete tree? Or are these the same words to describe the same situation?

Yes, there is a difference between the three terms and the  difference can be explained as:

Full Binary Tree: A Binary Tree is full if every node has 0 or 2 children. Following are examples of a full binary tree.

         18
       /    \
     15      20
    /  \
   40   50
  /  \
 30  50

Complete Binary Tree: A Binary Tree is complete Binary Tree if all levels are completely filled except possibly the last level and the last level has all keys as left as possible.

            18
       /         \
     15           30
    /  \         /  \
  40    50     100   40
 /  \   /
8   7  9

Perfect Binary Tree: A Binary tree is Perfect Binary Tree in which all internal nodes have two children and all leaves are at same level.

           18
       /       \
     15         30
    /  \        /  \
  40    50    100   40


Aussume P != NP, are these assertions valid? Assume $P \ne NP$, and $A$ is a problem in $P$ and $B$ is a problem which is $NP-complete$.
Are the following assertions valid?

$A \le_{P} B$
$B \le_{P} A$

My approach:

$B \le_{P} A$ isn't valid, because if $B$ is reducible in poly-time to $A$, so $B$ has to be also in $P$. But thats not possible because $P \ne NP$.
$A \le_{P} B$. Is it possible to reduce a problem in $P$ to a problem in $NP$ ? If it is, then the assertion is valid.

Question: Is my approch correct or am I missing some important point?

Regarding 1: yes, since $B$ is $\mathsf{NP}$-complete it must be $\mathsf{NP}$-hard, i.e., for ever every problem $C$ in $\mathsf{NP}$ we have $C \le_P B$. Since $A \in \mathsf{P} \subseteq \mathsf{NP}$, we can pick $C=A$.
This is true regardless of whether $\mathsf{P}=\mathsf{NP}$.
Notice, however, that we are using the fact that $B$ is $\mathsf{NP}$-complete. In general it is not possible to reduce an arbitrary problem in $\mathsf{P}$ to an arbitrary problem in $\mathsf{NP}$.
Regarding 2: no. Here your reasoning is correct, $B \le_p A$ would imply $\mathsf{P} = \mathsf{NP}$.


Is program coding part of computer science? As an amateur Bash/JavaScript scripter I was wondering if program coding ("writing source code") in general, and abstractless coding in particular (binary) is a concept of Computer Science or just an engineering implementation to ease doing the science and to automate processes.

Is program coding part of computer science?

I read a quote by Bjarne Stroustrup which said that computer science was the study of computers in the same way astronomy is the study of telescopes.

Computer science does indeed study coding in the abstract, particularly among the study of algorithms and data structures. Both of these fields are highly mathematical in nature, and seek to understand the idea of the abstract data type more fully. Of course, practical lessons can be learned and applied to various computers languages, systems, and applications, particularly answering questions like:

  Can it be done?
  What's the way to do it fastest with the least amount of memory?
  How do I compare two different ways to code the same solution to a problem?

When studying algorithms, for instance, Big-O Notation is presented as a way at looking at the computational complexity of an algorithm? Will it finish in linear time? What about polynomial time? In fact, in computational comlexity theory a tremendously important question about what can be solved abstractly with coding is the question of NP-completeness.

When studying coding abstractly, often pseudocode is used to represent instructions as opposed to an implemented language. For example:

  Procedure DoIt()
       Loop from 1 to 100
          If num is divisible by 3
              Print that its divisible by 3
          If num is divisible by 5
              Print that its divisible by 5
  End

Other ways of studying algorithms and data structures include diagrams and graphs, often using tree data structures.


Confusion about proof of undecidability of REGULAR TM in Sipser's book in the book "Introduction to the Theory of Computation" by Michael Sipser there is an example of undecidable languages in which there is a language REGULR_TM which is described as follows :

REGULAR_TM = { <M> | M is a Turing machine and L(M) is regular language }.
 Well, Sipser says that this is an undecidable language since we cannot have a decider to decide this language. Because if we could, we could create a TM that decides ATM which we know previously that is undecidable. so this could cause a contradiction.
Here is the proof from this book :

Proof. We let R be a TM that decides REGULAR_TM and construct TM S to decide ATM. Then S works in the following manner.

S = "On input <M, w>, where M is a TM and w is a string:

Construct the following TM M2.

M2 = "On input x:

  1. If x has the form 0^n 1^n, accept.

  2. If x does not have this form, run M on input w and accept if M accepts w."

Run R on input <M2>.
If R accepts, accept; if R rejects, reject."

Now my question is, is this kind of constrcuting a TM S correct?
the part that is really confusing me is the part that says "run M on input w and accept if M accepts w". this is the whole question for Atm. If we could answer that question why we need a machine M2 to feed it into the R and output the result of R. We just "run M on w".

Also for some languages that [we know] are decidable we can have the same argument and conclude that it is not decidable.

----- EDIT -----

Ok. let me explain my confusion a little bit different. consider language A_DFA :

A_DFA = { <B, w> | B is a DFA that accepts w }

We know it is decidable (Proof in the textbook). so we reduce ATM to A_DFA.

PROOF. let R be Turing machine that decides A_DFA. we construct TM S to decide ATM. then S works in the following manner :

S = "On input <M, w> where M is a TM and w is a string:

Construct the following DFA D:

DFA D has only one state q0 which is also the start state.
all arrows come back to q0 itself. if M accepts w add q0 to F. (F is the set of final states.)
Run R on <D, w>
accept if R accepts; reject if R rejects.

It is interesting that I kind of understood the problem of my own work when I was writing the proof of reduction of ATM to A_DFA. I write it so that if it is true others can learn if it is wrong others will correct it!

I think that because M2 in the first proof is a Turing machine we CAN say that if "M accepts w". (we somehow embedded the work of "if M accepts w" into M2 without actually running M on w). but in my own proof of ATM -> A_DFA the problem is that we cannot construct DFA D without actually running M on w. so we cannot construct D. That's the reason why the first proof is true and my proof is wrong.

A universal Turing machine accepts a machine $M$ and an input $x$, and simulates the run of $M$ on $x$.

If $M$ halts on $x$, the universal Turing machine will also halt, and will output the state of $M$ at the end of computation.
If $M$ doesn't halt on $x$, the universal Turing machine will also not halt.

This is what the machine $M_2$ does on step 2. It simulates $M$ on $w$, and may or may not halt. What a universal Turing machine cannot accomplish is solve the halting problem, that is, given $M$ and $x$, do some computation which always terminates, and answer whether $M$ halts on $x$ or not. Instead, it simulates $M$ on $x$, and halts iff $M$ halts on $x$.

We shouldn't be able to tell whether an arbitrary machine $M$ halts on an arbitrary $w$ or not. The reduction translates this question into the question whether $L(M_2)$ is regular. Since the former question is undecidable, so is the latter one.


Time complexity, Big-O for this function? def f(n):
    if n < 100000:
        return 0;
    for(int i = 0; i < n*n; i++){
        return f(n-1)
    }

What is the time complexity?

My answer is $O((n!)^2)$. Here's my thought process:

The for loop will be running $n^2$ the first time.
However, during the first loop (i.e., $i = 0$), it will call $f(n-1)$, hence
the next for loop will be $(n-1)^2$.
This will keep going until $n <10000$ (base case).  Assuming $n$ is very
huge, the number of calls for each function to base case is essentially $n$ times.
Now, considering all the for loops, the total number of calls is essentially $n^2 \cdot (n-1)^2 \cdot (n-2)^2 \cdots 1!$ (there will be a total of $n$ times multiplication, and each multiplication will be $n-1$ of the previous one because of $f(n-1)$ call).

It runs in time $O(n)$. Remember that a function only returns once.  In each call to f, the for loop is immediately terminated at i=0 by the return statement, so the function body is equivalent to

if n < 100000
    return 0;
else
    return f(n-1);

However, your answer of $O((n!)^2)$ is not wrong: $(n!)^2$ is a huge overestimate of the running time, but big-$O$ essentially means "at most this much."


Are these two languages regular? Let $\operatorname{value}(x)$ be the result when the symbols of $x$ are multiplied from left to right according to
 $\qquad \displaystyle\begin{array}{c|ccc}
    \times & a & b & c \\
    \hline
    a & a & a & c \\
    b & c & a & b \\
    c & b & c & a
   \end{array}$

 Is $L=\{xy \mid |x|=|y| \land \operatorname{value}(x) = \operatorname{value}(y)\}$ regular?

 Is $L=\{xy \mid \operatorname{value}(x)= \operatorname{value}(y)\}$ regular?

Hint for (1): consider a different type of value, $\mathrm{value}(s) = 1$ if $s$ ends with $z$, and $\mathrm{value}(s) = 0$ otherwise. Define the language $L$ as in your case, and consider $L \cap x^* z y^* z$.

Hint for (2): consider the language $L_\alpha = \{xy : \mathrm{value}(x) = \mathrm{value}(y) = \alpha \}$. What is the relation between $L_\alpha$ and $M_\alpha = \{ x : \mathrm{value}(x) = \alpha \}$? Is $M_\alpha$ regular?


GPR registers in computer How to ensure data integrity in General Purpose Registers (GPR registers) given their limited number (for x86 their number is 6),and on the other hand that they are used simultaneously by all processes?

Their integrity is maintained by several features working in conjunction.

For synchronous code execution, function calls, i.e. invocations, generally require some management.  This management is named the calling convention.  Both caller and callee must agree on the same convention or else things break.  (It is possible for one caller and callee to agree, then have that callee, now play caller to call someone else, using an alternate calling convention they both agree upon.  This works but might make stack unwinding more complex for the debugger, or for error handling/exceptions.)  The calling convention dictates how parameters are passed (registers & stack), how return values are passed back, and certain registers don't participate in the invocation and are particularly designated for retaining their original caller-defined values across the call — meaning that if the callee want to use those designated registers it has to save them first, and then restore them before returning.

For asynchronous code execution of threads/processes, either the hardware provides multiple CPUs or the software is time-slicing the CPUs, or both.

If the hardware provides multiple CPUs (whether by hyperthreading or full blown CPUs), it provides sufficient register sets for all the CPUs, so it provides a  copy of the necessary processor state for each provided processors.  Some of the computation units may be shared (e.g. in hyperthreading), but the register state is duplicated.

When software (e.g. operating system) does time-slicing, it uses a clock or other interrupt to suspend one thread's operation, and resume another thread (that had may have been previously suspended in a similar manner).

The interrupt mechanism itself requires cooperation between hardware and software.  Generally speaking, the hardware provides the minimal features necessary, and leave the rest up to software — although on more modern processors, some features the software could do are taken over by the hardware so that operating systems don't require as much customization for new CPUs.

The interrupt mechanism was invented around the time of the DEC PDP-1 processor, ~1959, and was then called Sequence Break System.  Before that, processors ran mostly batch jobs and did I/O synchronously.  With the introduction of the interrupt mechanism, the processor can be signaled by an external connector to take an unscheduled branch to an interrupt handler aka interrupt service routine.  At every sequence point in the processors execution where it could service an interrupt, some hardware is checking that external pin to see if an interrupt is being requested.  A clock is one device that regularly interrupts, I/O devices also interrupt.  When an interrupt handler runs the hardware must preserve, minimally, any (register) state of the thread that it destroys in switching to the interrupt service routine, for example, the PC, since starting interrupt service routine is effected by making the CPU take an (unscheduled) branch.  This could be done by having two PC registers (one main one and a shadow one for remembering the old PC at time of interrupt) or by using some prearranged memory location to store the PC of the interrupted code.  Depending on the processor architecture some other shadow registers may be provided, like an alternate stack pointer.  These things would make the interrupt handler easier to program (though the initial handler still would have to be written in assembly, not even C).  Once the handler is running, it will save any other state for the interrupted thread, so that it can do some work using the CPU in a rather normal way, and still resume the interrupted thread later — maybe much later, after first giving some other threads a time slice.

Have a look at this answer for more information on the subject of interrupts.

See also MultiThreading on Single Core, and here Interrupts vs. Exceptions


Why can't un-journaled filesystems be resized? I have yet to find an un-journaled filesystem that can be resized without data loss or intermediate conversions, and I'm wondering why that is.

Filesystems like FAT, for example, leave free space at the end of the block device; it seems pretty simple to me to just add more free space onto the end...

Edit: It seems that some filesystems, created without a journal, can still be resized. I created an EXT4 filesystem with mke2fs -t ext4 -O ^has_journal /dev/loop0p1, grew the partition, and successfully resized it. I also created an EXT2 filesystem (which to my knowledge doesn't have a journal) and successfully resized it.

My current theory is that it's just a big coincidence that most filesystems without a journal can't be safely resized and most with a journal can.

The "file allocation table" (which gives the FAT filesystem its name) is a fixed-size array "statically allocated at the time of formatting." Its size is determined by the size of the partition, because "The table contains entries for each cluster, a contiguous area of disk storage." (quoted from Wikipedia).

So if the partition is made larger, the FAT has to be made larger. But in order to do that, whatever pieces of files which happen to occupy the sectors adjacent to the FAT need to be moved elsewhere. That's not a simple procedure, and while it is being performed, the whole filesystem is in an inconsistent state.

That might seem like a suboptimal design, but since FAT was designed for single partition removable media (i.e. floppy disks) whose size was determined at the time of manufacture, there was no need to plan for resizing. The fixed-size immovable allocation table makes for faster, simpler code.

The Wikipedia article provides a lot more details, if you're curious. It's actually not too difficult a project to write a FAT driver, which might provide additional insights.


why nominal unification is a first-order unification? In my understanding, if a unification solves equations of terms that are not higher-order terms, then it is a first-order unification.

If a unification solves equations of terms that are higher-order terms, then it is a higher-order unification. Therefore a unification solves equations of $\lambda$-terms should be a higher-order Unification.

That is what I thought.

Read about unification

the paper nominal unification said that nominal unification is a first order unification, but it is solving equations of $\lambda$-terms.

Why nominal unification is a first-order unification while clearly solving equations of higher-order terms?

Also, that paper shows an example of unification

$$
\lambda a.\lambda b.(b \, M_6) =?= \lambda a.\lambda a.(a \, M_7)
$$

on the right side $\lambda a.\lambda a.(a \, M_7)$, what is that? Why two abstractions have same bound variable $a$ ?

I am confused, could anyone clearify it to me, thanks!

Most experience people have with unification (if any) is usually unification modulo syntactic equality: two terms unify if there is a substitution for unification variables that makes the terms syntactically identical.  However, you can consider other base equivalence relations that are coarser than syntactic equality.  For example, there's associative, commutative equality that let's you unify two bags (aka multisets) of terms, e.g. the term $\{\!\!\{\mathtt{x},\mathtt{y}\}\!\!\} = \{\!\!\{\mathtt{y},\mathtt{x}\}\!\!\}$ where I'm using $\{\!\!\{ \ldots \}\!\!\}$ to represent a bag.  Unification with a base equivalence like this, coarser than syntactic equality, come up, for example, in checking record types.  You can imagine you have a bag of record labels and you want to record types to be the same regardless of how you wrote down the labels.

So, in this context, higher-order unification is unification modulo $\alpha\beta\eta$-equivalence.  The base equivalence is what makes it higher-order-unification, not the terms it operates on. I can apply normal, syntactic, first-order unification to lambda terms too. Unification modulo $\alpha\beta\eta$-equivalence means being able to unify expressions like $E(3) = (3,3)$ via a substitution such as $[E \mapsto \lambda x.(x,x)]$ as these are $\beta$-equivalent. (Following Prolog, I'll use capital letters to indicate unification variables.  Also, note $[E\mapsto\lambda x.(3,3)]$ is another non-equivalent substitution which is why higher-order unification produces extra non-determinism.)  Nominal unification does not unify these terms. $(\lambda x.(x,x))(3)$ is not $\alpha$-equivalent to $(3,3)$.  An application will never be $\alpha$-equivalent to a pair constructor. (However, if the notation was implicitly in curried-style, i.e. $(3,3)$ meant $((,)(3))(3)$, these would syntactically unify.  Generally, though, multi-ary application is never $\alpha$-equivalent to unary application.)

Nominal unification is unification modulo $\alpha$-equivalence.  At a raw syntax level $\lambda x.x$ is syntactically different from $\lambda y.y$ because $x$ is different syntax than $y$.  This is undesirable as we want to treat these terms as completely identical.  We don't want the choice of variable name to matter to, e.g., type checking.  This problem is clearly solvable because we could use deBruijn notation and the only term corresponding to the two above lambda terms would be something like $\lambda\mathbf{1}$.  The power of deBruijn notation is that syntactic equality is $\alpha$-equality.  Nevertheless, it would be nice not to use deBruijn notation.

So one way to implement nominal unification would be to simply convert each term to deBruijn notation and unify.  This would be fine if all we needed to do was answer "yay" or "nay", but we also need to produce a substitution.  If we convert $\lambda x.x$ and $\lambda y.E$ to $\lambda\mathbf{1}$ and $\lambda E$ respectively, then unify them, we get $[E \mapsto \mathbf{1}]$. But obviously $\lambda x.x \neq (\lambda y.E)[E\mapsto x]$.  Basically, we need to keep track of what variable corresponds to $\mathbf{1}$ on each side of the equation.  This gives us two bijections (for any particular unification variable, i.e. locally) that maps variables to deBruijn indices, here $[x \mapsto \mathbf{1}]$ and $[y\mapsto\mathbf{1}]$.  We can compose these bijections to get a bijection (i.e. permutation) between variables on each side.  This leads to $[E \mapsto (x\ y)\bullet x]$, in their notation, which simplifies to $[E\mapsto y]$, the desired substitution.  There are some extra concerns about capturing variables that additionally complicates the picture.

Summarizing, higher-order unification means unification modulo $\alpha\beta\eta$-equivalence.  Nominal unification means unification modulo only $\alpha$-equivalence.  This can be reduced to syntactic unification of deBruijn terms, but if we want to produce substitutions on non-deBruijn terms we need to keep track of some extra information.  Doing a similar reduction for higher-order unification would involve reducing to terms in $\beta\eta$-normal form, which thus requires such normal forms to exist hence the focus on the typed case, and leads to creating terms out of nowhere which themselves require unification.


Why would this be a deterministic context free language? $L = \{a^n b^n | n>0 \}$ $\cup$ $\{ a^n b^{2n} | n < 100 \}$ so the book that I'm reading says this is a deterministic context free language
 $L = \{a^n b^n | n>0 \}$ $\cup$ $\{  a^n b^{2n} | n < 100 \}$

But i think this is wrong Because :

at the beginning of building the DPDA, we have to decide whether we should go with the first one or the second, and considering both of them start with a there is just no way we could build a DPDA right?? or am i wrong?

i also tried solving this by first building the $a^nb^n$ and then going for the second one if the stack is not empty, but still couldn't come up with anything, i tried putting 2 a's for every a input but didn't work

so how is the book saying this can be build with a DPDA?

Also i have to say I KNOW that non infinite languages are regular, but this one is not infinite!

Maybe you can create 100 states that push two $a$'s onto the stack for every $a$, and then pop these $a$'s for every $b$. In the event of getting to the 100th state, when you read the 101st $a$, pop 100 $b$s from the stack and continue as you would for the first language alone.


Hex Word Search Generator Algorithm I want to create an algorithm to build a hex matrix with given:
- max n rows
- max m collumns
- min t rown
- min q collumns

containing the specific words from a list: "example", "test", "algorithm".

For example. To build a hex matrix with:

  - max n = 5 rows
  - max m = 6 collumns
  - min t = 5 rows
  - min t = 4 collumns
  - containg words: "orange", "test"

Can anyone point me in the right direction of how to build this type of algorithm? ( C++, C#, Swift, Objective-C)

Represent the Hex as Graph;

each node has additional property; has_letter; $T,F$
add the first randomly

choose starting point on the graph, probably randomly
place the letters by DFS or BFS,
add the letter into a list $l$.

adding another word with one connection, from start

from the list find the first letter of the new string that in the middle of another.
place the remaining words by DFS or BFS in nodes with $F$ flag.

adding another word with one connection, not necessary from the beginning.

from the list find the letters of the new string.
One part may be on the upper; as corner and almond. if the connection is $o$, alm on the upper,
One part may be on the lower, and nd from the previous example.
place the upper part with DFS or BFS in nodes with $F$ flag.
place the lower part with DFS or BFS in nodes with $F$ flag.

Hope this helps;


Optimal clustering with optimal number of clusters as well as max and min cluster size constraints I need to cluster $N$ data points.
I don't know the number of clusters to be formed. It needs to be found optimally.
Also, there is maximum and minimum cluster size constraints, where $C_{\max}$ is the maximum size that one cluster can get and $C_{\min}$ is the minimum size that one cluster must get.
The coordinates of the $N$ data points are stored in a matrix $D\in\mathbb{R}^{2\times N}$, $D$ is a matrix of $N$ rows and each row has two elements defining the $x-$axis and $y-$axis coordinates. However, $D$ can be expressed in any convenient form, for example, $D\in\mathbb{R}^{N\times 2}$ or $D\in\mathbb{C}^{N\times 1}$ (where the coordinates are expressed as a complex number: $x+iy$)
How can I formulate this as a mathematical optimization problem and solve it efficiently?
Data points can be uniformly distributed over a 2D plan of any given size.

Answer 1. There are various clustering algorithms depending on different requirements. You can employ $k$-means clustering method since it is fast, simple, and popular.
Answer 2. If you do not know the number of clusters, employ Elbow method. That is, first cluster the data for $k = 1$. Then cluster the data with $k = 2$, then $k = 3$ and so on. Initially, the cost of the clustering will decrease rapidly with increase in $k$. Once the $k$-means cost starts to appear constant with increase in $k$; that value of $k$ is the desired number of clusters.
Answer 3. When there are constraints on the size of clusters, the problem is (informally) known as the balanced clustering problem or capacitated clustering problem. The Wikipedia article does contain a few links of its implementation. This is a research paper for the balanced $k$-means problem. You might have to do some more research on this topic to find the perfect answer as per your requirement.

Note: The clustering problem that minimizes the $k$-means objective is $\mathsf{NP}$-hard. Therefore, you can expect to find an optimal solution to your problem in polynomial time.


Creating a logical circuit Task:
Design a 2 bit comparator.

Input: 2x 2 bit (I take it as 2 2-bit values, let them be unsigned for simplicity)
Output: 1 if result input1>input2 is true, 0 otherwise

Develop truth table and derive circuits.

The problem: I'm completely new to this so I have not even a idea where where to look for the lighthouse.

The question: I'M NOT LOOKING FOR COMPLETE SOLUTION, instead I'm looking for a guidance through topics/materials which I should check to be able to solve it myself.

Done so far: I started with understanding logical gates and those seem to be pretty straight forward.

P.S.: Purpose of posting this question is to boost the speed with which I will get to the actual solution.

SOLUTION:
f(A,B,C,D) = !AB!C!D + A!C + ABC!D. (! - used for negation or NOR, ABC notations means A AND B AND C). I had three adjacent rectangles two of which were of unit cell size and one of 4 cells size (one cell was actually far away, but there's this toroidally connection property, not sure about terminology). A and B are MSD and LSD of the first number respectfully and B and C are same for second number. As for the circuit image: sorry folks my hand drawing requires strong mental stability.

Well, as the problem asks you to make a truth table, you should first make one (this is generally a good idea even if not asked explicitly). For your question, you can say assign two bits to input1, say $a$ and $b$, and two bits to the input2, say $x$ and $y$. Then you might say that if $a = 1$ and $b = 0$, input 1 is $2$.

Once you have the truth table (4 inputs, one output), you can get the corresponding boolean expression from the truth table in "sum-of-products" form. Basically, suppose for every entry where the output is 1, you form a "min-term" of the inputs. For example, say for 2 inputs $p$ and $q$, if output is $1$ when $p=1$ and $q = 0$, the min-term would be $p\bar{q}$. Get these min-terms for all inputs where the output is 1, and add them/OR-them together. This is because the output is 1 if and only if any one min-terms is true. You can read more here or here or here.

Now, once you have the boolean expression, you might want to minimize it - implement the logic using fewer gates. This is not asked in your question, but you might want to do it anyways. Karnaugh map technique, which you seem to already have read, is one technique. There is another called the Quine-McCluskey algorithm.

Once you have the boolean expression, you can generate the corresponding circuit mechanically. So, for each min-term, implement it using AND gates, and NOT gates. Connect all these to the input of a OR gate. For example, for something like $p\bar{q} + \bar{p}q$, $p\bar{q}$ means $p$ AND (NOT $q$). Do the same for the other min-term, and give them to the input of an OR gate. The above links also provide information and examples about this.

As for speed, you'll get faster with practice!


Find a list of actions that result in desired state I have a problem that I need to solve, and I'm looking for which area of computer science (algorithms. etc) would be appropriate to solve this problem.

In the system we have a list of actions that a user has previously taken. The possible actions are:

User creates item of type A.
User creates item of type B.
User creates item of type C.

The date and time the action was taken is also recorded.

We have a function passesRules which takes the list of all actions the user has previously taken as input, and applies a set of rules and returns a boolean. The boolean is true if any of the rules are true, and false if none of the rules are true.

There are many possible rules, but in general they take the form of:

Has user created 5 items of type A in the last 10 days?
Has user created 2 items of type B in the last 3 days?
Has user created more than 6 items of type C in last 5 days, AND
created 3 items of type A in the last 10 days?

What I want to do is to create a function predictActions which predicts the actions the user must take so that passesRules returns true.

Obviously with the rules described above there are multiple different sets of actions that could make passesRules return true. I would like predictActions to return an array where each element in the array is a list of actions the user could take to make passesRules return true.

predictActions should take the following parameters:

The list of actions the user has previously taken.
The list of rules.
The current date.

I'm not asking for a solution, but I don't know what area of computer science to investigate further to model and solve this problem. Something from graph theory, or some type of constraint solver?

Thanks!

It depends on what the rules are.  For your particular rules, this can be handled very simply by counting the number of events of each type seen in the given time window; then predictActions can easily compute the additional number of each type of action needed.