Combinatory interpretation of lambda calculus

The equivalence is just equivalence in the equational $\lambda$-theory under discussion. In this case, it's the theory outlined in Table 1. Note that this theory does not include $\eta$: doing so would make the theory extensional, and the point is eventually that $\xi$ respects $\lambda$'s intensionality, while it would make CL partially extensional. I am not sure why the other answer mentions $\eta$.

Note that in $\lambda$:

$$(M =_\beta N) \Longrightarrow (\lambda x.M =_\beta \lambda x.N) \tag{1}$$

This should be intuitively obvious: if $M$ is $\beta$-convertible to $N$ when it stands by itself, then it is also $\beta$-convertible to $N$ when it is a subterm of $\lambda x.M$.

The $\xi$-rule, defined as
\begin{align}
M &\;= N \\
\hline
(\lambda x.M) &\;= (\lambda x.N)
\tag{$\xi_\lambda$}
\end{align}
makes this inference directly possible when it is part of a $\lambda$-theory. Its CL analogue would be:
\begin{align}
M &\;= N \\
\hline
(\lambda^* x.M) &\;= (\lambda^* x.N)
\tag{$\xi_{CL}$}
\end{align}

Now, the point is that in CL, the following does not hold:

$$(M =_w N) \Longrightarrow (\lambda^* x.M =_w \lambda^*x.N) \tag{2}$$

In other words, if two terms are weakly equal, then this is not necessarily true for their pseudo-abstracted versions.

Consequently, if we add $\xi_{CL}$ to a CL theory, then we start equating terms which have different normal forms.

Note. Here, $M =_w N$ denotes weak equality. It means that $M$ can be converted into $N$ (and vice versa) by a series of $\mathsf{S}$ and $\mathsf{K}$ contractions (possibly also $\mathsf{I}$, if it is part of the theory). As you probably know, $=_w$ is the CL analogue of $=_\beta$.

$\lambda^*$ is the pseudo-abstractor as defined on page 5 of your document. It has the following property:

$$(\lambda^*x.M)N \rhd_w [N/x]M \tag{3}$$

This property makes it easy to find a CL analogue for any $\lambda$-term: just change $\lambda$ to $\lambda^*$ and apply the translations according to the definition of $\lambda^*$.

To be clear, the 'counter-example' in this answer is not a counter-example to (2). Because if we have:

$$M = x \tag{4}$$
$$N = (\lambda^*z.z)x \tag{5}$$

Then $N$ really denotes (applying the translations of page 5, and the fact that $\mathsf{I}$ is defined as $\mathsf{SKK}$ at the end of page 4):

$$N = (\lambda^*z.z)x = \mathsf{I}x = \mathsf{SKK}x \tag{6}$$

Since $\mathsf{SKK}x \rhd_w \mathsf{K}x(\mathsf{K}x) \rhd_w x$, we indeed have that $M =_w N$. However, if it is a counter-example, we should then have that $(\lambda^* y. M) \not=_w (\lambda^* y. N)$. But if we translate, we actually get:

$$(\lambda^* y. M) = (\lambda^* y. x) = \mathsf{K}x \tag{7}$$
$$(\lambda^* y. N) = (\lambda^* y. \mathsf{SKK}x) = \mathsf{K}(\mathsf{SKK}x)\tag{8}$$

And is easy to verify that (7) and (8) are still weakly equal, for:

$$\mathsf{K}(\mathsf{SKK}x) \rhd_w \mathsf{K}(\mathsf{K}x(\mathsf{K}x)) \rhd_w \mathsf{K}x \tag{9}$$

Now, a proper counter-example to (2) would be:

$$M = \mathsf{K}xy$$
$$N = x$$

Since $\mathsf{K}xy \rhd_w x$, we definitely have that $M =_w N$. However, if you translate carefully for the abstracted versions, then you will see that both are distinct normal forms - and these cannot be convertible according to the Church-Rosser theorem.

First we check $M'$:

\begin{align}
M' &= \lambda^* x.\mathsf{K}xy \\
&= \mathsf{S}(\lambda^* x.\mathsf{K}x)(\lambda^* x.y)\\
&= \mathsf{S}(\lambda^* x.\mathsf{K}x)(\mathsf{K}y) \\
&= \mathsf{S}(\mathsf{S}(\lambda^* x.\mathsf{K})(\lambda^* x.x))(\mathsf{K}y) \\
&= \mathsf{S}(\mathsf{S}(\lambda^* x.\mathsf{K})(\mathsf{I}))(\mathsf{K}y) \\
&= \mathsf{S}(\mathsf{S}(\lambda^* x.\mathsf{K})(\mathsf{SKK}))(\mathsf{K}y) \\
&= \mathsf{S}(\mathsf{S}(\mathsf{KK})(\mathsf{SKK}))(\mathsf{K}y)
\end{align}
Here you can verify that $M'$ is a normal form. Here you can check that $(\lambda^* x.Kxy)P \rhd_w P$, as you should expect if $\lambda^*$ is supposed to behave like an abstractor for CL. (Click the blue links to perform weak contractions.)

Now we check $N'$:
\begin{align}
N' &= \lambda^*x.x \\
&= \mathsf{I} \\
&= \mathsf{SKK}
\end{align}

Which is obviously a normal form different from $M'$, so $M' \not=_w N'$ by the Church-Rosser theorem. Note also that $N'P \rhd_w P$, i.e. $M'$ and $N'$ 'produce the same output' for arbitrary inputs $P$.

We have now proven that (2) does not hold in CL, and that a CL theory incorporating $\xi$ would therefore equate terms that are not weakly equal. But why do we care?

Well, first of all, it makes the combinatory interpretation of $\lambda$ imperfect: apparently not all metatheoretic properties carry over.

In addition, and perhaps more importantly, while there exist extensional theories of $\lambda$ and CL, they are originally and commonly kept intensional. Intensionality is a nice property because $\lambda$ and CL model computation as process, and from this perspective two different programs (specifically, terms that have a different normal form) that always produce the same results (given equal inputs) are not to be equated. $\xi$ respects this principle in $\lambda$, and if we want to make $\lambda$ extensional, we could just add e.g. $\eta$. But the introduction of $\xi$ in CL would no longer make it completely intensional (in fact, only partially so). And this is the reason for $\xi$'s 'notoriety', as the article puts it.


Are there any garbage collectors that take into account paging?

As I recall, copy collectors are supposed to be paging friendly, as
the tracing by copying tends to improve the locality of pointer
references. This has a positive effect on the program (mutator) that
will cause less page faults when following links, and will also
improve the next collection cycle as tracing will also cause less page
faults. The tracing agenda (which pointers should be processed first) can have an impact on the effectiveness for improving data locality. This may be improved by mesuring statistics on the number of access to different pointers in different types of cells.

Now, if you consider a tracing collector in general, you must usually
maintain a structure that keeps track of the pointers that have not
been traced yet. It may be possible to organize this structure so that
all waiting pointers pointing in the same page will be kept together
(though that may take more space, in some cases, depending on the
available techniques to keep the list of such pointers).  A possible
policy is then to always trace first the largest set of waiting
pointers pointing to the same page, when there is no waiting pointer left to the pages in memory.

Regarding the question in the third paragraph, that was added after I answered, copy
collection is again an answer. The OS may reduce the number of
allocated physical pages at collection time, since the pages are completely
freed. With a mark and sweep collector, the event of a full page
beeing free is probably much rarer, thus not worth a specific
machanism to be taken into account.

This kind of ideas is natural, and is probably described in some of the
papers. But I do not recall it off hand. I think the early papers on Lisp GC contain some of these ideas (such as: should car or cdr be followed first?).

The good news in this role of copy-collection is also that paging is
friendly to copy collection since it increases the available storage
space. Recall that the copy collector requires in principle twice as
much space as used for actual data storage. Now, the effect of paging depends also on the address
space of the machine, and the physical memory available. In older
computer, physical memory was much less than available address space,
so that paging was really a space bonus, allowing policies such as
copy GC. Even when physical space is as big as the address space,
one might want to share it, so that the process using a GC would have
less address space without paging (see paging). These remarks are somewhat superseeded by the use of generational collectors. They generally use copy collection for the young generation precisely because of these qualities, and because the young generation is mostly short lived.

Then you have all the interactions of generational GC with the cache
system, that has been discussed in a previous question: Are generational garbage collectors inherently cache-friendly?

For more information on these issue, I would search the web with, for example, the keywords garbage collection and locality.


There are many data structures you could use for this purpose.

One possibility is a relational database (just like you've shown).

Another possibility is any data structure for storing equivalence relations; for instance, the standard Union-Find data structure would do.  Here you'd be storing that (System 1, level1-1) is equivalent to (System 2, level1-2), and so on.  That would work, too.

[ General advice for asking in the future: Don't worry too much about "names" for something.  Names matter a lot less than finding a reasonable solution.  Instead, think of the task you're trying to accomplish, what your requirements are, what you're trying to optimize, and then ask how to do that. You might get back an answer that says "read up on this standard thing"; or you might get back an answer that just directly describes a solution to your problem.  Either way, you win! ]


Proof of sparsification lemma: What exactly does the $\pi$ operator do?

From the definition you gave, the supersets have to be removed, as you want to keep only those sets for which there is no proper subset in $\mathcal{F}$.

For example:

In blue are the sets of $\mathcal{F}$ which don't have proper subsets in $\mathcal{F}$, in red are the ones who do. You want to keep the blue ones, by definition of $\pi$.


What is the difference between Abstract Data Types and objects?

Google brought up a similar question with an answer that I think is very good. I've quoted it below.

  There's another distinction lurking here that is explained in the Cook
  essay I linked.

  Objects are not the only way to implement abstraction. Not everything
  is an object. Objects implement something which some people call
  procedural data abstraction. Abstract data types implement a different
  form of abstraction.

  A key difference appears when you consider binary methods/functions.
  With procedural data abstraction (objects), you might write something
  like this for an Int set interface:

interface IntSet {
  void unionWith(IntSet s);
  ...
}

  Now consider two implementations of IntSet, say one that's backed by
  lists and one that's backed by a more efficient binary tree structure:

class ListIntSet implements IntSet {
  void unionWith(IntSet s){ ... }
}
class BSTIntSet implements IntSet {
  void unionWith(IntSet s){ ... }
}

  Notice that unionWith must take an IntSet argument. Not the more
  specific type like ListIntSet or BSTIntSet. This means that the
  BSTIntSet implementation cannot assume that its input is a BSTIntSet
  and use that fact to give an efficient implementation. (It could use
  some run time type information to check it and use a more efficient
  algorithm if it is, but it still could be passed a ListIntSet and have
  to fall back to a less efficient algorithm).

  Compare this to ADTs, where you may write something more like the
  following in a signature or header file:

typedef struct IntSetStruct *IntSetType;
void union(IntSetType s1, IntSetType s2);

  We program against this interface. Notably, the type is left abstract.
  You don't get to know what it is. Then we have a BST implementation
  then provides a concrete type and operations:

struct IntSetStruct {
 int value;
 struct IntSetStruct* left;
 struct IntSetStruct* right;
}

void union(IntSetType s1, IntSetType s2){ ... }

  Now union actually knows the concrete representations of both s1 and
  s2, so it can exploit this for an efficient implementation. We can
  also write a list backed implementation and choose to link with that
  instead.

  I've written C(ish) syntax, but you should look at e.g. Standard ML
  for abstract data types done properly (where you can e.g. actually use
  more than one implementation of an ADT in the same program roughly by
  qualifying the types: BSTImpl.IntSetStruct and ListImpl.IntSetStruct,
  say)

  The converse of this is that procedural data abstraction (objects)
  allow you to easily introduce new implementations that work with your
  old ones. e.g. you can write your own custom LoggingIntSet
  implementation, and union it with a BSTIntSet. But this is a
  trade-off: you lose informative types for binary methods! Often you
  end up having to expose more functionality and implementation details
  in your interface than you would with an ADT implementation. Now I
  feel like I'm just retyping the Cook essay, so really, read it!

I would like to add an example to this.

Cook suggests that an example of an abstract data type is a module in C. Indeed, modules in C involve information hiding, since there are public functions that are exported through a header file, and static (private) functions that don't. Additionally, often there are constructors (e.g. list_new()) and observers (e.g. list_getListHead()).

A key point of what makes, say, a list module called LIST_MODULE_SINGLY_LINKED an ADT is that the functions of the module (e.g. list_getListHead()) assume that the data being input has been created by the constructor of LIST_MODULE_SINGLY_LINKED, as opposed to any "equivalent" implementation of a list (e.g LIST_MODULE_DYNAMIC_ARRAY). This means that the functions of LIST_MODULE_SINGLY_LINKED can assume, in their implementation, a particular representation (e.g. a singly linked list).

LIST_MODULE_SINGLY_LINKED cannot inter-operate with LIST_MODULE_DYNAMIC_ARRAY because we can't feed data created, say with the constructor of LIST_MODULE_DYNAMIC_ARRAY, to the observer of LIST_MODULE_SINGLY_LINKED because LIST_MODULE_SINGLY_LINKED assumes a representation for a list (as opposed to an object, which only assumes a behaviour).

This is analogous to a way that two different groups from abstract algebra cannot interoperate (that is, you can't take the product of an element of one group with an element of another group). This is because groups assume the closure property of group (the product of elements in a group must be in the group). However, if we can prove that two different groups are in fact subgroups of another group G, then we can use the product of G to add two elements, one from each of the two groups.

Comparing the ADTs and objects

Cook ties the difference between ADTs and objects partially to the expression problem. Roughly speaking, ADTs are coupled with generic functions that are often implemented in functional programming languages, while objects are coupled with Java "objects" accessed through interfaces.
For the purposes of this text, a generic function is a function that takes in some arguments ARGS and a type TYPE (pre-condition); based on TYPE it selects the appropriate function, and evaluates it with ARGS (post-condition). Both generic functions and objects implement polymorphism, but with generic functions, the programmer KNOWS which function will be executed by the generic function without looking at the code of the generic function.
With objects on the other hand, the programmer does not know how the object will handle the arguments, unless the programmers looks at the code of the object.
Usually the expression problem is thought of in terms of "do I have lots of representations?" vs. "do I have lots of functions with few representation". In the first case one should organize  code by representation (as is most common, especially in Java). In the second case one should organize code by functions (i.e. having a single generic function handle multiple representations).
If you organize your code by representation, then, if you want to add extra functionality, you are forced to add the functionality to every representation of the object; in this sense adding functionality is not "additive". If you organize your code by functionality, then, if you want to add an extra representation - you are forced to add the representation to every object; in this sense adding representations in not "additive".

Advantage of ADTs over objects

Adding functionality is additive
Possible to leverage knowledge of the representation of an ADT for performance, or to prove that the ADT will guarantee some postcondition given a precondition. This means that programming with ADTs is about doing the right things in the right order (chaining together pre-conditions and post-conditions towards a "goal" post condition).

Advantages of objects over ADTs

Adding representations in additive
Objects can inter-operate
It's possible to specify pre/post conditions for an object, and chain these together as is the case with ADTs. In this case, the advantages of objects are that  (1) it's easy to change representations without changing the interface and (2) objects can inter-operate. However, this defeats the purpose of OOP in the sense of smalltalk. (see section "Alan Kay's version of OOP)

Dynamic dispatch is key to OOP

It should be apparent now that dynamic dispatch (i.e. late binding) is essential for object oriented programming. This is so that it's possible to define procedures in a generic way, that doesn't assume a particular representation. To be concrete - object oriented programming is easy in python, because it's possible to program methods of an object in a way that doesn't assume a particular representation. This is why python doesn't need interfaces like Java.

In Java, classes are ADTs. however, a class accessed through the interface it implements is an object.

Addendum: Alan Kay's version of OOP

Alan Kay explicitly referred to objects as "families of algebras", and Cook suggests that an ADT is an algebra. Hence Kay likely meant that an object is a family of ADTs. That is, an object is the collection of all classes that satisfy a Java interface.

However, the picture of objects painted by Cook is far more restrictive than Alan Kay's vision. He wanted objects to behave as computers in a network, or as biological cells. The idea was to apply the principle of least commitment to programming - so that it's easy to change low level layers of an ADT once the high level layers have been built using them. With this picture in mind, Java interfaces are too restrictive because they don't allow an object to interpret the meaning of a message, or even ignore it completely.

In summary, the key idea of objects, for Kay - is not that they are a family of algebras (as is emphasized by Cook). Rather, the key idea of Kay was to apply a model that worked in the large (computers in a network) to the small (objects in a program).

edit: Another clarification on Kay's version of OOP: The purpose of objects is to move closer to a declarative ideal. We should tell the object what to do - not tell it how by micromanaging is state, as is customary with procedural programming and ADTs. More info can be found here, here, here, and here.

edit: I found a very, very good exposition of Alan Kay's definition of OOP here.


Problem in understanding big-O notation and similiar

$O(n)$ is the set of all functions $f(n)$ such that, for sufficiently large $n$ and a positive constant $c$, $f(n) \le cn$.
$1+\Theta(\frac{1}{n})$ is an abuse of notation that denotes the set of all functions $h(n) = 1+g(n)$ such that, for sufficiently large $n$ and a two positive constants $c_1$, $c_2$, $\frac{c_1}{n} \le g(n) \le \frac{c_2}{n}$.
Then the claim is clearly false since, e.g., the function $h(n)=n$ belongs to $O(n)$ but it does not belong to $1+\Theta\left(\frac{1}{n}\right)$.


Help me identify the type of Knapack Problem I am dealing with

There's no special "name" for this problem that I'm aware of. Don't assume that problem specifications this specific will necessarily have a "name" or "type".

Instead, it's simply one of many problems that can be solved straightforwardly with dynamic programming.  You fill in an array $A[1..n]$, defined as follows: $A[i]$ is the minimum number of power supplies needed to provide power to sections $1,2,3,\dots,i$.  Then there is a simple recurrence for $A[i]$ that allows you to fill in the entire array in $O(n)$ time, namely,

$$A[i] = 1 + \min \{ A[j] : 10-i  \le j < i \text{ and } P(j,i-1)\}$$

where $P(j,i-1)$ is true if a single power supply can power sections $j,j+1,\dots,i-1$ simultaneously.

This allows you to compute the minimal number of power supplies needed.

Then, once you know this number, you can know optimize things to find the most equal distribution of power.  Let $k$ denote the number of power supplies, and $\mu$ denote the average power per supply when using $k$ supplies.  Given a constant threshold $t$, you can determine whether there exists a way to power all sections using $k$ power supplies such that every power supply's power consumption falls in the range $\mu-t \dots \mu+t$, using similar methods.  Now use binary search on $t$ to find the minimal $t$ such that this is possible.  This will give you the solution to your problem.

In general, computer science provides many techniques that can be combined in creative ways to solve problems.  When you have a new problem with multiple specific requirements, you might have to look for how to apply those techniques in a way specific to your particular situation; there's no guarantee that it will fall cleanly into some existing "category" or "type".


When is epsilon a part of the result of computing the right quotient?

In words, your definition says "The right quotient, written $L_1 / L_2$, is defined to be the set of all strings $x$ such that $xy$ is a string in $L_1$ for some string $y$ in $L_2$." According to this definition, the empty string is a member of the right quotient if and only if there is a common string in the two languages. In symbols, $\epsilon \in L_1 / L_2 \iff L_1 \cap L_2 \neq \emptyset$. In particular, this is not the case in your example, hence, the empty string is not in your right quotient.


Applying the context-free pumping lemma to a language with crossed nestings

Pumping lemma lets you construct new strings belonging to the context-free language.

To prove that the language is not context-free you can take some string $s$ from L, use pumping lemma to construct a new string $s1$ which must belong to $L$ (because you used pumping lemma to construct it!). Then you show that $s1$ does not belong to L => contradiction.

Choice of original $s$ is yours. So yes, you can use $z = a^pb^pc^pd^p$ in your proof.


How to use Hoare Logic to Prove this Assertion

Its a question of chaining/glueing the axioms between them.

Let's start from the end:

$$\mathbf{\{s == p * (p + 1) / 2\}}$$

Use the strengthening rule to change the postcondition to

$$\mathbf{\{s == p * (p + 1) / 2 \wedge p == n \wedge p >= 0\}} $$

which is equivalent to

$$\mathbf{\{s == n * (n + 1) / 2 \wedge p == n \wedge p >= 0\}}$$

By the Loop rule in order for the triple:

$$ \mathbf{\{s == n * (n + 1) / 2 \}} \mathtt{while}\ (n <= p)\ \{s = s + n ;
 n = n + 1\} \mathbf{\{s == n * (n + 1) / 2 \wedge p == n \}}
$$

we need to prove that the triple

$$\mathbf{\{s == n * (n + 1) / 2 \}} \{s = s + n ;
 n = n + 1\} \mathbf{\{s == n * (n + 1) / 2\}}$$

is valid.

Let then use the composition to reduce this to proving that the two following triples are valid:

$$\mathbf{\{s == n * (n + 1) / 2 \}}
\{s = s + n\}
 \mathbf{\{s == (n+1) * (n + 2) / 2\}}$$

and

$$\mathbf{\{s == (n+1) * (n + 2) / 2 \}}
\{ n = n + 1\}
 \mathbf{\{s == n * (n + 1) / 2\}}$$

The latter one is just an application of the Assignment rule (just replace the occurrences of $n$ by $n+1$ in the postcond to get the precondition).

To prove the first one, we need to apply Strengthening to reduce it to the triple
$$\mathbf{\{s == n * (n + 1) / 2 \}}
\{s = s + n\}
 \mathbf{\{s == (n) * (n +1) / 2 + n\}}$$
and then use the Assignment rule trivially.

Okay so now we only need (by Sequence rule) to prove that the triple

$$\mathbf{\{p>=0 \}} s:=0; n:= 1 \mathbf{\{s == n * (n + 1) / 2 \wedge p >= 0\}}$$
which can be done in the same way by splitting with sequence.


The best exposition on how to count the number of minimum spanning trees is, as far as I have seen, a stackoverflow answer by j_random_hacker.

In the course to answer a different question, that answer explains very well an algorithm that counts the number of MSTs.

It establishes that Kruskal's algorithm can find every MST.
It breaks up the Kruskal's algorithm into a series of blocks, each of which consists of a sequence of adding the edges of the same weight into a component multigraph that has been built in the previous block of operation.
It proves that the number of MSTs is the product of the number of spanning forests in the multigraph for each block-defining weight.
Finally, the number of spanning forests for a multigraph can be computed by Kirchhoff's theorem.


Is it possible to reduce a SAT problem to it's simplest form with no assumed variables in P time?

No, this is not possible, unless $P=NP$.

Why? The formula $x \wedge\lnot x$, which is always false, is technically in CNF. But, this is unsatisfiable.

Suppose we could do this in polynomial time? Then to check of a problem is satisfiable, we just minimize it. If it minimizes to our false formula, then it's not satisfiable. If it minimizes to anything else, it must be satisfiable! So we've solved SAT in polynomial time.

In terms of gates, we have the same problem: if a formula is UNSAT, then always outputting LOW is the minimal gate circuit that's equivalent.


NP-hardness of covering with rectangular pieces (Google Hash Code 2015 Test Round)

This is a sketch of a reduction from MONOTONE CUBIC PLANAR 1-3 SAT :

Definition [1-3 SAT problem]:
Input: A 3-CNF formula $\varphi = C_1 \land C_2 \land ... \land C_m$, in which every clause $C_j$ contains exactly three literals: $C_j = (\ell_{j,1} \lor \ell_{j,2} \lor \ell_{j,3})$.
Question: Does there exist a satisfying assignment for $\varphi$ such that each clause $C_j$ contains exactly one true literal.

The problem remains NP-complete even if all literals in the clauses are positive (MONOTONE),  if the graph built connecting clauses with variables is planar (PLANAR) and every variable is contained in exactly 3 clauses (CUBIC) (C. Moore and J. M. Robson, Hard tiling problems with simple tiles, Discrete Comput. Geom. 26 (2001), 573-590.).

We use $T=3, A=6$, and in the figures  ham is represented with blue boxes (transgenic ham?), pizza with orange boxes.

The idea is to use tracks of ham that carry positive or negative signals; the track is made with an alternation of 1 and 2 pieces of hams placed far enough so that they can be covered exactly by one slice of pizza of area $A$; the segments of the track are marked alternately with $+$ or $-$, the track will carry a positive signal if slices are cut on the positive segments:

Each variable $x_i$, which is connected to exactly 3 SAT clauses, is represented by three adjacent endpoints of three ham tracks (positive segment), in such a way that there are 2 distinct ways to cut it, one will "generate" a positive signal on all 3 tracks (it reppresent the $x_i = TRUE$ assignment) the other a negative signal ($x_i = FALSE$). Notice that we can also generate mixed positive and negative signals, but in that case at least one ham remains uncovered.

Each clause $C_j$ of the 1-3 SAT formula with 3 literals $L_{i,1}, L_{i,2}, L_{i,3}$ is simply represented by a single ham with three incoming positive segments of three distinct ham tracks; by construction only one of the three tracks carrying a positive signal can "cover" the ham-clause.

Finally we can build shift and turn gadgets to carry the signals according to the underlying planar graph and adjust the endpoints:

Suppose that the resulting graph contains $H$ hams. By construction every slice of pizza must contain exactly 3 hams, and in all cases every slice can be enlarged up to area $A$.

If the original 1-3 SAT formula is satisfiable then by construction we can cut $H /3$ pieces of pizza (with total area of $A H / 3$) and no ham remains uncovered.

On the oppposite direction, if we can cut $H /3$ pieces of pizza (with total area $A H / 3$) then no ham remains uncovered, and the signals on the variables gadgets and on the clauses are consistent: the ham on the clause is covered by exactly one positive slice coming from a positive variable, and every variable generates 3 positive signals or 3 negative signals (no mixed signals); so the cuts induce a valid 1-3 SAT assignment.


Heuristic for Finding Multiple Goals in Graph - e.g. using Kruskals Algorithm

MST is actually a tree, not a path (generally). Therefore, it is not a solution to TSP. (Although, MST can help you to find a solution that is not more than twice as long as the optimal solution, if you solve this in a metric space on a complete graph. That's unrelated story.)

Now, I must admit that I do not see a way spanning trees can help you if the maze contains loops. And in the case that the maze does not contain loops, it is somehow weird to talk about MST, because the graph of the maze is a tree.

However, maybe you can start to think about this: in a tree, for any two nodes, there is exactly one path that connects them. That's a trivial, but quite a nice property, isn't it? Length of this unique path is an easy lower bound that is more precise than Manhattan distance.

If you build MST over a graph with loops, this would probably not make an admissible heuristic, because the path using only MST edges can be longer than some path over edges you haven't choose to the spanning tree.

"Minimality" of MST is somehow a local property -- it's not like all the shortest paths are preserved. This is why I would never think about solving your problem with MST.


A question about domains in Karp reductions

Here is an example. Consider the problem of vertex cover. An instance of vertex cover consists of a graph $G$ and an integer $k$. This is the domain $D$. You can easily come up with a one-to-one encoding $e\colon D \to \Sigma^*$ such that (i) you can recognize whether a string is in the range of $e$ in polynomial time, (ii) given such a string, you can recover $G$ and $k$ in polynomial time. The language $L$ consists of all encodings $e(G,k)$ of graphs $G$ containing a vertex cover of size $k$. If a string is not in the range of $e$, it is not in $L$.
Now suppose that you have a reduction $f$ from the domain $D$ of vertex cover to the domain $D'$ of SAT, and let $e\colon D \to \Sigma^*$ and $e'\colon D' \to \Sigma^*$ be encodings of these domains. We can construct a reduction $g$ from the language $L \subseteq \Sigma^*$ of vertex cover to the language $L' \subseteq \Sigma^*$ of SAT as follows. Given a string $w \in \Sigma^*$, we first check whether it is in the range of $e$. If not, we output some fixed string not in $L$' If it is, we output $e'(f(e^{-1}(w)))$; that is, we decode $w$, apply $f$, and then encode the result.
Most of the time, such encoding details can be ignored. This is the case since we're working in a computation model which is strong enough to be oblivious to such matters. This is why we usually don't bother with these issues too much.


Can every program be turned into a quine?

You are looking for the recursion theorem. Let $F(e)$ be the function that on input $0x$ returns $P(x)$ and on input $1x$ returns $e$. A fixed point $\varphi_e = \varphi_{F(e)}$ is what you're looking for.

If you're interested in how this quine is constructed, take a look at the proof, for example here.


The algorithm works, but to understand why, you need to know basic probability theory. The idea is to prove by induction that at step $t$, the currently selected algorithm is uniform among the first $t$ elements. This is clearly the case when $t=1$. Assume now the induction hypothesis for time $t$, and consider what happens at time $t+1$. With probability $1/(t+1)$, the element at position $t+1$ is selected. With probability $t/(t+1)$, the previously selected element is retained. By assumption, this is a uniformly random element among the first $t$ ones, and so the probability that any given element out of the first $t$ is selected is $t/(t+1) \cdot 1/t = 1/(t+1)$. In total, we see that each of the first $t+1$ elements is selected with the uniform probability $1/(t+1)$.

If you don't like induction, you can also do it all at once. For item $i$ to be selected as the output of the algorithm, it needs to have been selected at time $i$, and to not have been dropped at any further time. If there's a total of $n$ elements then this happens with probability
$$ \frac{1}{i} \cdot \frac{i}{i+1} \cdot \frac{i+1}{i+2} \cdots \frac{n-2}{n-1} \cdot \frac{n-1}{n} = \frac{1}{n}. $$


Compression Bounds - Determine and Visualize for hypothesis vs VC dimension

Generally, every class of finite VC dimension admits to a (exponential size in the dimension) compression scheme. This was an open question resolved a few years ago by Shay and Amir in this paper. However, this is an overkill for your question, since $H_k$ obviously has a $k$-comprresion scheme (only keep the samples labeled $1$, of which there are at most $k$, and the reconstruction is zero everywhere else).
$H_{desct}$ can be compressed to two samples, given $\left((a_i,b_i),y_i\right)_{i=1}^n$, we know that either there exists $j$ such $\forall i\in[n]: y_i=\mathbb{1}_{a_i\le a_j}$ or there exists $j$ such that $\forall i\in[n] : y_i=\mathbb{1}_{b_i\le b_j}$. The compression keeps $(a_j,b_j)$ and one more sample $(a_{j'},b_{j'})$ to indicate the correct coordinate of the threshold, e.g. if the former condition holds and $\forall i\in[n]: y_i=\mathbb{1}_{a_i\le a_j}$ then pick $j'$ such that $y_{j'}\neq y_j$ (so $y_{j'}=0)$ and $b_{j'}<b_j$ (this allows us to reconstruct the function $\mathbb{1}_{x_1\le a_j}$ from the two samples). If no such $j'$ exists then $\mathbb{1}_{x_2\le b_j}$ is also a consistent hypothesis, and our compression can keep only one sample.


Algorithm for assigning items to one of two sets (2-CNF?)

There's a simpler approach, without using 2CNF.  Instead, build an undirected graph with edges between pairs of items that must be together, then find connected components (e.g., using DFS).  Now you can freely choose, for each component, which set it is associated with, and add all of its elements to that set; the result will be valid regardless of how you make those free choices.


Closed-form expression for the sums of the rows of the Trinomial triangle

Intuitively, each integer on the $i$-th row participates exactly three times in the sum of the integers on the $(i+1)$-th row. This means that the sum $S_{i+1}$ of the integers in the $(i+1)$-th row must be exactly $3$ times as large as the sum $S_i$ of the integers in the $i$-th row, i.e., $S_{i+1}=3S_i$ (and $S_1=1)$.  A formal argument is as follows:
Let $x^{(i)}_j$ be the $j$-th integer on the $i$-th row and define $S_i = \sum_{j=1}^{2i-1} x^{(i)}_j$. For simplicity define $x^{(i)}_j = 0$ whenever $j \le 0$ or $j \ge 2i$. You can show by induction on $i$ that $S_i = 3^{i-1}$.
The base case $i=1$ is trivially true since $S_1 = x^{(1)}_1 = 1 = 3^0 = 3^{1-1}$.
Suppose now that the claim holds for $i\ge 1$. Then, the claim must also hold for $i+1$. Indeed:
$$
\begin{align*}
S_{i+1} &= \sum_{j=1}^{2i+1} x^{(i+1)}_j = \sum_{j=1}^{2i+1} \left( x^{(i)}_{j-2} +  x^{(i)}_{j-1} + x^{(i)}_{j}\right)
= \sum_{j=1}^{2i+1}  x^{(i)}_{j-2} +  \sum_{j=1}^{2i+1}  x^{(i)}_{j-1} + \sum_{j=1}^{2i+1}  x^{(i)}_{j} \\
&= 3 \sum_{j=1}^{2i-1} x^{(i)}_{j} = 3S_i = 3 \cdot3^{i-1} = 3^i.
\end{align*}
$$


One one hand this is impossible, because a quine is supposed to output its own code, and the pure lambda calculus has no means for performing output.

On the other hand, if you assume that the resulting term is the output, then every normal form is a quine.

For example, lambda term $(\lambda x. x)$ is already a normal form, then assuming that its output is the resulting normal form, the output is $(\lambda x. x)$. Thus $(\lambda x. x)$ is a quine.


baz_num_elts exercise from Software Foundations

I agree with you. There's a bijection between baz and False.

Definition injective : forall {t1 t2}, (t1 -> t2) -> Prop := fun t1 t2 f1 => forall x1 x2, f1 x1 = f1 x2 -> x1 = x2.

Definition surjective : forall {t1 t2}, (t1 -> t2) -> Prop := fun t1 t2 f1 => forall x1, exists x2, f1 x2 = x1.

Definition bijective : forall {t1 t2}, (t1 -> t2) -> Prop := fun t1 t2 f1 => injective f1 /\ surjective f1.

Inductive baz : Type :=
   | x : baz -> baz
   | y : baz -> bool -> baz.

Theorem baz_False : baz -> False. Proof. induction 1; firstorder. Qed.

Goal exists f1 : baz -> False, bijective f1.
Proof.
exists baz_False. unfold bijective, injective, surjective. firstorder.
assert (H2 := baz_False x1). firstorder.
assert (H2 := x1). firstorder.
Qed.


What is a range of an attribute in data mining?

The range of the attribute is the interval where the values of the attribute varies. For Real numbers, is the closed interval [min,max].

For example, for an attribute $A$ with values $\{0.1, 0.5 , 1 , 10 , 100\}$ the range is the interval $[0.1,100]$

The concept is also valid for Integers, however there are no widely know notation to describe that. Ways of describing it would be:

$i = 1,...,10$

or

$(i \in \mathbb{Z}) \wedge (i \in [0,10])$


Is the set of Turing machines which stops in at most 50 steps on all inputs, decidable?

Let's consider the more general problem of machines which stop after at most $N$ steps, for some $N \geqslant 1$. (The following is a substantial simplifcation of a previous version of this answer, but is effectively equivalent.)

As swegi remarks in an earlier response, if the machine stops after at most $N$ steps, then only the cells $0,1,\ldots,N-1$ on the tape are significant.
Then it suffices to simulate the machine $M$ on all input strings of the form $x \in \Sigma^N$, of which there are a finite number.

If any of these simulations fail to enter a halting state by the $N^{\text{th}}\:\!$ transition, this indicates that any input string starting with $x$ is one for which the machine does not stop within the first $N$ steps.
If all of these simulations halt by the $N^{\text{th}}\:\!$ transition, then $M$ halts within $N$ steps on all inputs of any length (of which the substring of length $N$ is all that it ever acts on).


Efficient formulation for binary integer linear programming

Integer linear programming

Let me suggest another way of formulating this with ILP that might be worth trying.  Define combination to mean a list of all of the balls in a single box.  For instance, the combination might be (7,15) meaning that the box contains ball 7 and ball 15.  Of course, we can enumerate all legal values for the combination, i.e., for the contents of a single box.  There will be at most $1+N_S+N_B+N_S(N_S-1)/2+N_B(N_B-1)/2+N_B N_S(N_S-1)/2$ different combinations (fewer in practice due to the constraints on the difference of weights and the total weight of a box).

Now introduce a binary variable $x_{ij}$ that is 1 if the $i$th box contains combination $j$.  Here $j$ is an index that ranges over all possible legal choices for the combination, i.e., for the contents of a single box.  (Don't include any illegal combinations.)

We get some linear inequalities from this:

For each box, we must select one combination for it to contain: $\sum_j x_{ij} \le 1$.
Each ball must be used exactly once: $\sum_i \sum_{j \in B_k} x_{ij}=1$, where $B_k$ is the set of legal combinations that include ball $k$.

Now you can test feasibility, i.e., test whether it is possible to pack all of the balls into some given number of boxes.

For example, suppose we have 5 big balls and 10 little balls and 10 boxes.  Then there will be at most about 300 legal combinations (probably fewer), so there will be about 3000 binary variables.  I don't know whether PuLP will be effective, but you could give it a try.

Exact cover

Even better yet, one can note that your problem is an instance of the exact cover problem.  The universe is the set of balls; each combination is a subset of the universe; and we want to find a way to cover the universe by a disjoint union of the combinations.

There are dedicated algorithms for the exact cover problem that might be faster than expressing this as an integer linear program and applying an ILP solver.


Normalizing the mantissa in floating point representation

The correct binary representation of $0.145$ is $0.00100101000111...$

Normalized: $1.00101000111...$

The 8 bit mantissa is $00101000 = 0\mbox{x}28$


Finding hash of a substring $[i, j]$ in $O(1)$ using $O(|S|)$ pre computation

Yes, you can solve your problem, roughly speaking, by precomputing prefix sums.

In particular, if you are willing to do $O(n)$ precomputation and to use $O(n)$ space, we can solve your problem, for most standard rolling hashes.  We just need the rolling hash to have one extra property, the inverse property.  Most rolling hashes do have this property, including the well-known Rabin-Karp rolling hash.

Let me explain the details, below.

Some notation: let $S[i..j]$ denote the substring of $S$ from index $i$ to $j-1$ (note: it doesn't include index $j$; it is a substring of length $j-i$).  Let $H(S[i..j])$ denote the rolling hash of that substring.

The intuition

Imagine that we used a very simple hash, which is just the sum of the bytes modulo 256:

$$H(S[i..j]) = S[i] + S[i+1] + S[i+2] + \dots + S[j-1] \bmod 256.$$

This is a crummy hash function (it has lots of collisions), but let's go with it, since the purpose is just to get some intuition.  This is a rolling hash; given the hash of a prefix of the string, it is easy to extend it by one more byte (just add that byte to the hash value you've got so far).

Now with this hash function, we could easily solve your problem.  During the precomputation, we'd fill in an array $A[]$ so that $A[j] = S[0] + S[1] + \dots + S[j-1] \bmod 256$ for each $j$; this can be done in $O(n)$ time.  Now, we can compute $H(S[i..j])$ via the simple relation

$$H(S[i..j]) = A[j] - A[i] \bmod 256.$$

This can be computed in $O(1)$ time, given the precomputed array $A$.

Of course, you'd never use this in practice, because it's such a crummy hash function.  But the same idea can be generalized to work with many other rolling hash functions, which you would want to use. (Intuitively, that's because they are based upon a binary operation that is associative and has an inverse, which is all you need for this trick to work.)  I'll describe the details next.

The inverse property

All rolling hashes have the following property:

The accumulation property: Given $H(S[i..j])$ and $S[j]$, we can compute $H(S[i..j+1])$.

We need one additional property from the rolling hash:

The inverse property: Given $H(S[i..j])$ and $H(S[i..k])$, where $j < k$, it should be possible to derive $H(S[j+1..k])$.

Many standard rolling hashes do have this inverse property.  For instance, the Rabin-Karp rolling hash has the inverse property.  The same is true for hashing with cyclic polynomials (Buzhash).

How to use the inverse property for your problem

Create an array $A[]$ of $n$ elements.  During precomputation, we will fill in the elements of $A$ so that $A[j] = H(S[0..j])$.  This precomputation can be done in $O(n)$.

Now, at some later point, you would like to compute the rolling hash of $S[i..j]$, i.e., to compute $H(S[i..j])$.  How do you do that?  It turns out it is easy.  First, look up $H(S[0..i])$ and $H(S[0..j])$ using the array; this involves reading the value of $A[i]$  and $A[j]$.  Next, use the inverse property to compute $H(S[i..j])$ from these two values.  Done!  That's all there is to it.


It was probably a rather unfortunate abbreviation of 8-N-1 serial transmission which is what MIDI uses. The 8 bits are sent serially, one at time, still.


The algorithm is full and correct. If you look back to definition 6.80 in the same book, you will see that the until operator is part of path formulae, which in the CTL* MC algorithm are checked via a standard LTL model checker as written in the last switch case ($\exists \varphi$). The $\varphi$ stands for any path formula.

The algorithm also states that you take the negation of $\varphi$. So then you need to take the complement of the satisfaction set.


OK, here's a big hint.

Take any $G,A,S$ that satisfy the premises of the question.  Now add a new vertex $v'$ to the graph, and draw an edge from $v'$ to one of the vertices of $A$ with a weight of your choice.  (This means that $v'$ will be connected to the rest of the graph only by this one new edge; there are no other edges out of $v'$.)

What can you say about this new edge?  Does it cross the cut?  Is it a light edge?  Is it a safe edge?  Does this suggest any method for choosing the weight on that edge, to make things fortuitous to you?  Hint: if you think about it (or try some examples), I bet you'll see how you can arrange things to get a violation of the conjecture.

People learn best by finding the solution for themselves (rather than reading someone else's solution), so I'm not going to post more than a hint.  This hint ought to be enough to understand what's going on here....


Standard sorting algorithms assume a total ordering: given any two elements, the first is either greater than, equal to, or less than the second. (And this relationship has a few other useful properties, like transitivity.)

However, what you have here is only a partial ordering. Given two boxes, the first might fit into the second, or the second might fit into the first, or they might be the same size…or, neither might fit inside the other. (10, 1) and (2, 5) fall into this last category.

Standard sorting algorithms will choke on this. But topological sorting only needs a partial ordering, and is also more efficient (running in linear time instead of linearithmic). So it's the right tool for the job here.


Avoiding overflows while computing $e^x$ by Taylor series

Of course there are better numerical ways to compute exponential, but if you want to use Taylor expansion only, the better approach is to reformulate the expansion to avoid computing large nominators and denominators. This leads to an $O(n)$ algorithm, where $n$ is the number of iterations. Yours is $O(n^2)$ if you compute factorial and power literally (probably the python library is computing factorial with a gamma function and power with exp).

Here is a javascript program. print() is a function to write strings to console.

function myexp(x, max_itr)
{
    var y = 1.0, t = 1.0;
    for (var i = 1; i < max_itr; ++i) {
        t *= x / i;
        y += t;
    }
    return y;
}

var x = 1.2;
print("Math.exp: " + Math.exp(x));
print("10 iterations: " + myexp(x, 10));
print("99 iterations: " + myexp(x, 99));

The output is:

Math.exp: 3.3201169227365472
10 iterations: 3.3201150098285708
99 iterations: 3.3201169227365472

EDIT:

Alternatively, you can reformulate Taylor expansion as:

$$ e^x = 1 + \frac{x}{1}\left(1+\frac{x}{2}\left(1+\frac{x}{3}\left(1+\cdots\right)\right)\right)$$

An implementation in javascript:

function myexp2(x, max_itr)
{
    var y = 0.0;
    for (var i = max_itr; i >= 1; --i)
        y = 1.0 + x / i * y;
    return y;
}


Formal construction of PDA intersecting a DFA

The idea of the intersection is to construct a PDA that keeps track of the original PDA's state in the first component of the state (in the $Q_P$ component) together with the stack, and keep track of the DFA's state in the $Q_D$ component. If both accept by final state, you just need to accept if both automata end up in a final state.


Count the number of integers satisfying two conditions using DP

Hint: The table consists of cells $T(S,d,\ell)$, which count numbers of length $\ell$ in which the last digit is $d$ and the set of digits is $S$. Unfortunately this solution is exponential in $n$.


What is the name of the word problem for free groups under straight line program encoding?

The blog post you link to already gives a deterministic polynomial-time (in fact, linear-time) algorithm for the word problem over a free group with 2 letters.

In contrast, no deterministic polynomial-time algorithm for identity testing for polynomials is currently known (this is a famous open problem).

Therefore, it's not likely to be easy to prove that the word problem over the free group is equivalent in complexity to identity testing of polynomials.

The "straight-line encoding" doesn't seem to change the complexity of the word problem in any interesting way.  It seems equivalent to simply specifying the input as an expression (i.e., a sequence of symbols, where each symbol is either $x_i$ or $x_i^{-1}$).


How to make an unambigous grammar of a programming language

Grammars of real programming languages are often more restricted than CFG in order to enable efficient parsing. You may have heard of LL(k) and LR(k) grammars, for instance. All these grammars are, by definition, unambiguous; the corresponding language classes are (strict) subsets of DCFL.

You would realize a grammar is ambiguous (or otherwise not in the grammar class at hand) when the algorithm constructing a parser from it fails. Speaking in computability terms, membership for these grammar classes is decidable.


Application of floors and ceilings to the time complexity of loop with constant index increment

You are technically right, and if you want an exact value of the number of loop iterations, you can't forget the floor.
However, when doing asymptotical time complexity analysis, you can often toss terms that are negligible in front of other terms. In this case, $\frac{m}{a} - \left\lfloor\frac{m-1}{a}\right\rfloor \leq 1+\frac{1}{a}$ which is negligible in front of $\frac{m}{a}$ (for $m$ big enough).
See here for more details.


The usual approach is to identify a randomized self-reduction.  In other words, given a problem instance $x$, you generate a randomized version of $x$, say $x'$, and show how the solution to $x'$ gives you the solution to $x$.

How does this help?  Given a problem instance $x$, you can generate many randomized versions, say $x'_1,x'_2,\dots,x'_m$ (each one using independent randomness).  Now, try to solve each of the $x'_1,x'_2,\dots,x'_m$.  By the conditions of your problem, you know that you'll have a way to solve them, so that a $1/2 + \epsilon$ fraction of the answers are correct: i.e., so that $m/2 + \epsilon m$ of the $m$ answers are correct.

Now, you take it from here.  How could you use that to form a reasonable guess at the solution to $x$?


Can a computable program have an infinite output?

Our general rule is one question per post.  I'll answer the first question.

A program can certainly produce infinite output.  It can enter an infinite loop producing output.  Consider everyone's first program in Basic:

10 PRINT "Hello World!"
20 GOTO 10

It makes no sense to talk about a program being computable.  There's no need to you write a program to output a program.  Instead, you can just write the program you want in the first place.  Instead of talking about computable programs, computability is about languages.  We talk about languages being computable.  Check the definition of computability.


clarification about Algorithm of page replacement LRU with reference bits

Is my doing correct?

If I don't misunderstand your notation, when you manipulate the frame for first time (filling it with page 1, then page 2) and then page 1 is called again, you shouldn't send to disk page 2, there is no need because page 1 it is already in frame.


How to determine how many dots are in a resource in a resource allocation graph?

The dots represent the number of clients a resource can serve simultaneously. So, in the example in the question, resources $R_1$ and $R_3$ can only serve one client at a time, $R_2$ can serve two and $R_4$ can serve up to three clients at the same time.


Checking the existence of a pattern in a given prefix

Recall that in a suffix tree for $T$, each leaf corresponds to a suffix of $T$, and is labeled by its position. Furthermore, each internal vertex corresponds to a common prefix of some suffixes of $T$. We label each internal vertex with the minimal position of a suffix covered by it.
Construct a suffix tree for $T$, and augment it by labeling the internal vertices as described above. Given a pattern $P$, traverse the suffix tree to find the vertex corresponding to $P$ (it might correspond to some extension of $P$), and check whether the minimal position written there implies that $P$ occurs before position $k$.


Does any algorithm exist for computing the state of a non-trivial cellular automaton after an arbitrary number of time steps?

Two answers...

There is a trivial algorithm to do it: "Just" run the automaton for the required steps.
No, there is no general way to compress the computation. If you can prove that the automaton enters a periodic configuration, you certainly can. You can also precompute the result of a certain number of steps, and use that to skip ahead (doing several steps in one round). That is one of the ideas used to speed up finding Busy Beavers. But in general, as cellular automata are Turing-complete, to find out if you are in one of the cases where it stops or repeats is easily seen to be undecidable.


Let's consider $n!<e\left( \frac{n}{2} \right)^n=e^{n\ln n+1-n\ln2}$. On other hand $a^{n^b}=e^{n^b \ln a}$. Now we should compare $(n\ln n+1-n\ln2)$ to $n^b \ln a$, where right member wins, when $a,b>1$:
$$\frac{n\ln n+1-n\ln2}{n^b \ln a}\to 0$$


I need to present a regular expression for the following languages:

Your point 2, is obviously correct.

As for the point 1, we construct the automaton: let's remember how much more 0's we've read than 1's. Then we have transitions:

S0  by 0 to S1
S0  by 1 to S-1
S1  by 0 to S2
S1  by 1 to S0
S-1 by 0 to S0
S-1 by 1 to S-2
S2  by 1 to S1
S-2 by 0 to S-1

S0 is initial, only S0 is final. This way we are sure, that in whatever state we are, the number of $0$'s and $1$'s that were read so far differs by at most $2$ and in the final state the number are the same.

Then the language is
$$ \Bigl(0(01)^*1+1(10)^*0\Bigr)^*$$

The large parenthesis corresponds to all paths from S0 to S0, and we can repeat it as many times as needed.


Can anyone help me understand the matches to this regular expression?

Well let's walk through it. You need one or more vowels, followed by any number of numbers (including none), followed by (optionally) a letter.

ae matches your vowels, 12 matches the numbers, then a counts as your optional letter. The engine starts again and looks for the next vowel. It skips bc r2d2 since there are no vowels there.

Then it finds a for your vowels, 1 for your numbers, and s as the optional letter. Then the engine starts again and looks for the next vowel.

It finds ea for your vowels. There are no numbers, so it grabs k as the optional letter. Then it starts again looking for vowels...


Time to construct a GNBA for LTL formula

In general, logical formulae can be thought of as trees; inner nodes are operators and leaves are atomic propositions. Therefore, every formula consists of as many direct subformulae (that is on the first level) as its top-most operator's arity. For example,

$\qquad \varphi \land \psi$

has two direct subformulae $\varphi$ and $\psi$. This can be continued recursively and we see that

$\qquad \displaystyle |\operatorname{subf}(\varphi)| \leq \sum_{\circ \in \operatorname{op}(\varphi)} \operatorname{arity}(\circ)$,

where $\operatorname{op}(\varphi)$ is the multi-set of operators occurring in $\varphi$. Informally speaking, every operator contributes its operands to the set of subformulae. Note that we have $\leq$ and not $=$ because a subformula might occur multiple times.

In LTL, all operators have at most arity two, so $|\operatorname{subf}(\varphi)| \leq 2|\varphi|$ provided that $|.|$ counts (at least) operator occurrences.


W[1]-hardness of Steiner tree w.r.t. number of non-terminal vertices

When parameterized by number of non-terminal vertices in the input graph, Steiner Tree is FPT by brute force.  -  Find a minimum-size subset of non-terminal vertices such that [the subgraph induced by the union of [the set of terminal vertices] with [the chosen set of non-terminal vertices]] is connected, and then output any spanning tree of that subgraph.

(If that's not your interpretation of the problem, then clarify your last paragraph.)


Algorithm to Assign Values Based on Constraints

The problem you are describing amounts to constraint programming and the specific constraint you are talking about is the alldifferent constraint. I'm not offering a purely algorithmic solution, but reading a bit on constraint programming could give you some ideas on how to construct a search tree where you make a decision (i.e., assign a value to a variable) at each node, and how to backtrack to a feasible node when you reach an infeasible node.


Why do you reason about the minimum number of nodes of an AVL tree of height h to argue the height is $\log n$ of an AVL tree?

First of all AVL trees are binary trees so you can't argue as many nodes as we can fit in a tree of height h because the maximum nodes you can fit in a AVL tree with h is 2h+2h-1+...+20. Also the minimum number of nodes on an AVL tree with h is 1+2h-1+2h-2+..+20.

be careful for the first 1 at minimum number rather than 2h. If that plus one node would not exists, the AVL tree would be simply of height h-1, and we don't want that.

So you have to define n as be the minimum number of nodes of an AVL tree of height h. Because your algorithm has at least that much of nodes to traverse , and you do the analyze with that assumption


Assembly writer vs compiler in VLIW architecture

The "assembly writer" in that book is a human software developer who writes code in assembler language.


If you want to resolve C1 with C2, then the only option is for Loves(jack, x) (in C2) to match ¬Loves(x, F(x)) (in C1), and so as you state, you should substitute x=jack in C1 and x=F(jack) in C2. Upon making these substitutions, C1 and C2 become:

C1[x/jack] = ¬Loves(jack, F(jack)) or Loves(G(jack), jack)
C2[x/F(jack)] = ¬Animal(F(jack)) or Loves(jack, F(jack))

Resolving the two, we get:

¬Animal(F(jack)) or Loves(G(jack), jack)


Linear-time algorithm to find an odd-length cycle in a directed graph

Let $G$ be strongly connected. Run BFS (!) from an arbitrary vertex $s$. BFS creates a leveled tree where level of a vertex $v$ is it's directed distance from $s$. If while running BFS you have never seen an edge $(u,v)$ that goes between levels of the same parity then $G$ is bipartite. The parity of the level of $u$ defines the partition that $u$ belongs to. Note that since every vertex is reachable from $s$, BFS will explore all the edges, so all of the edges would be going between the two blocks of the partition. Otherwise, you find an edge $(u,v)$ that goes between levels of the same parity. Suppose level of $u$ is even and level of $v$ is even. Then run DFS (or BFS) from $v$ to get a path to $s$. If this path is of even length then you get an odd directed cycle $s \rightsquigarrow u \rightarrow v \rightsquigarrow s$. If this path is of odd length then you get an odd directed cycle $s \rightsquigarrow v \rightsquigarrow s$. Analogous thing holds when level of $u$ is odd and level of $v$ is odd. Since this algorithm simply does 2 runs of BFS/DFS, it runs in linear time.


Bottom-Up Parser With Leftmost Derivation

"Linearizing" here is equivalent to superimposing a total ordering on what is a partial order. If your grammar is context-free, this partial order can always be conveniently represented by a tree. Other types of grammars will be able to produce derivations orders that are not tree-like, and that is why we generally avoid them.

This total order is meant to allow for sequential algorithms to be written, because the input will be read sequentially. That's all, no magic here.

What happens is that different criteria for linearization will serve different algorithms: if you are going to reduce the input, you will go "from the bottom up", metaphorically, so the linear order that suits you (if you are reading the input left-to-right - because your language has an indo-european flavor), is postfix. If not, prefix.


For the sake of argument we will assume ATM is decidable. Now we are going to show a way to decide HaltTM using ATM decider, and thus reach a contradiction, since we know HaltTM is undecidable.
Details:
Since ATM is decidable then ATM(Complement) is also decidable, We take TM R that decides ATM and another S that decides ATM(Complement), we use those to build X,
given input < M, w > a turing machine description and it's input w, Run R on given input if accepts accept, if rejects then run S on input, if accepts accept, if rejects reject. This way we have insured that X will reject only machines that do not halt,and accepts all others. So we have used ATM decider to decide HALT but HaltTM is undecidable so we conclude that ATM wasn't from the start decidable.


What do we gain by having "dependent types"?

Expanding my comment: Dependent types can type more programs. "More" simply means that the set of programs typable with dependent types is a proper superset of the programs typable in the simply-typed $\lambda$-calculus (STLC). An example would be $List_{2*3+4}(\alpha)$, the lists  of length $10$, carrying elements of type $\alpha$. The expression $2*3+4$ is at the same time a program and part of a type. You cannot do this in the STLC.

The key rule that distinguishes dependent from non-dependent types is application:

$$
\newcommand{\TYPES}[3]{#1 \vdash #2 : #3}
\newcommand{\SUBST}[2]{\{#1/#2\}}
\frac{
   \TYPES{\Gamma}{\color{red}{M}}{A \rightarrow B}
      \qquad
   \TYPES{\Gamma}{\color{red}{N}}{A}  }{
 \TYPES{\Gamma}{\color{red}{MN}}{B}   }
      \qquad
\frac{
   \TYPES{\Gamma}{{\color{red}M}}{\Pi x^A. B}
      \qquad
   \TYPES{\Gamma}{\color{red}{N}}{A}  }{
 \TYPES{\Gamma}{{\color{red}{MN}}}{B\SUBST{{\color{red}N}}{x}}   }
$$

On the left you have the STLC, where programs in the premises 'flow' only  into the program of the conclusion. In contrast, in the dependent application rule on the right, the program $N$ from the right premise 'flows' into the type in the conclusion$^1$.

In order to be able to parameterise types by programs, the syntax of dependent types must be richer, and to ensure that types are well-formed we use a second 'typing system' called kinds that constrains the types. This kinding system is essentially the STLC, but "one level up".

There are many explanations of dependent types. Some examples.

Dependent Types at Work, by Bove and Dybjer.
Dependent Types, by Aspinall and Hofmann.
Dependently Typed Programming in Agda, by Norell and Chapman.
Lambda Calculi with Types, by Barendregt.

$^1$  In terms of colours: with non-dependent types, black expressions in the conclusion are constructed from black expressions in the premises while
red   expressions in the conclusion are constructed from red expressions in the premises. With dependent types the colours can be mixed by having black parts of the conclusion being constructed from red and black parts of the premise.


Constructing solution to 3SAT formulas using oracle queries

You have the right idea. Suppose you have a SAT oracle and an instance $I$ of 3SAT (or whatever SAT-ish class you like) containing $n$ variables, $x_1, x_2, \dotsc x_n$. You could then do this:

send I to the oracle
if the oracle answers "not satisfiable"
   quit
else
   j = 1
   I_0 = I
   repeat
      transform I_{j-1} to I_j by substituting x_j = 1
      send I_j to the oracle
      if the answer is "satisfiable"
         save x_j = 1
      else
         save x_j = 0
         transform I_{j-1} to I_j by substituting x_j = 0
      j = j + 1
  until j = n

When the algorithm terminates, you'll have saved a satisfying collection of values for all the variables. This will be linear in $n$ (times the steps necessary to do the substitutions, which will be polynomial in the length of $I$).


What are the current known implications of the complexity of Integer Factorization?

Before answering your questions a distinction has to be made, when talking about $NP$ completeness we are talking about the decision problem not the function problem, which is given an integer N and an integer M with 1 ≤ M ≤ N, does N have a factor d with 1 < d < M.

So answering your questions in order, Since integer factorization is not known to be NP complete, $P \neq NP$ would not cause it to automatically not be in $P$ since quite often things that were thought to be in $NP$ are moved to $P$, only an $NP$ complete problem would be excluded from being in $P$. For the second one, again since it is not $NP$ complete a polynomial time solution to it will not effect the hierarchy for the same reason as before.

As an extra note, the actual location of factorization in the hierarchy is unknown, we know is is $BQP$, $NP$, $co-NP$, $FNP$ and $UP$. It may end up being $NP$-Intermediate, but no one knows for sure.


Minimization of amount in the change coins problem using the dynamic programing approach

Your formula is wrong (I would like to see where exactly this formula appears in the course, it is not in the gif you linked).

The correct formula is the following:
Let $n$ be your amount. Let minCoins be an array of $n+1$ elements indexed from $0$ to $n$, where minCoins$[i]$ is the minimum amount of coins needed to give change for the amount $i$. Let $c_1, \dots, c_k$ be the denominations of coins you have available.

Then minCoins$[0]=0$ and, for $i>0$:
$
\text{minCoins}[i] = \min_{\substack{j=1,\dots,k\\c_j \le i}} \{1 + \text{minCoins}[i-c_j] \}.
$

In your specific example:

$$
\begin{align*}
\text{minCoins}[9] &= \min \{\text{minCoins}[9-6]+1 , \text{minCoins}[9-5]+1, \text{minCoins}[9-1] +1\} \\
&= \min \{\text{minCoins}[3]+1 , \text{minCoins}[4]+1, \text{minCoins}[8] +1\} \\
&= \min\{ 3+1, 4+1, 3+1\} \\
&=  \min\{ 4, 5, 4\} = 4.
\end{align*}
$$


$f(x) = \sqrt{x^{2}+1}-1$ (Loss of Significance)

Assume that due to rounding errors, when you try to calculate the square root of $x^2 + 1$ you actually get the square root plus $\epsilon$ for some small $\epsilon$. Assume that $\epsilon = 10^{-10}$ and $x = 10^{-6}$. Perform the calculations and write down the results.


Blum's speedup theorem implies that for any computable function $f(n,T)$ there is a computable predicate $\Pi$ such that for every program $P_1$ for $\Pi$ there is another program $P_2$ for $\Pi$ whose running time satisfies $f(n,T(P_2)) \leq T(P_1)$. In particular, there exists a computable predicate $\Pi$ such that for every program $P_1$ computing it there is another program $P_2$ computing it and running in time $T(P_2) = o(T(P_1))$.

But the theorem is much stronger: for example, for some other predicate $\Pi$, the guarantee is $T(P_2) = O(\log T(P_1))$; and for another predicate $\Pi$, the guarantee is $T(P_2) = O(T(P_1)/n)$; and so on.


Is there any mechanism where the kernel portion of an OS in memory may also be swapped?

Indeed, it wouldn't make sense to swap out an I/O buffer. The point of that buffer is that it's in RAM. The code to perform the I/O and the code to manage swap must not be swapped out either.

Other kernel code can be swapped out, in principle. However this can be problematic for several reasons. Hardware drivers that aren't involved in swap could be swapped out, but this means the kernel had to be very careful about the whole data party to swap (which may involve a disk over some external communication bus or even the network, as well as filesystem code when swapping to a file). Furthermore a lot of driver vice is very performance-sensitive: the kernel had to read it send data when the hardware is ready and may not be able to afford the time to bring vice and data back out of swap. In addition, RAM is usually assumed to be reliable (it's acceptable for the system to crash if the RAM fails), but swap (on disks or over the network) isn't, and it's difficult to design a kernel that can recover if part of it becomes unavailable. Most kernels take the simple approach and never swap out kernel code and data.


PDA for the language of words $uv$ such that $|u| \geq |v|$ and $v$ contains 1

A pushdown automaton accepting this language proceeds as follows:

Push a marker $S$ to the top of the stack.
Push $A$ to the stack for each input symbol read.
At some point, nondeterministically transition to the second phase.
Pop $A$ from the stack for each input symbol read, marking whether you ever read $1$.
Fail if you encounter $S$.
Succeed if you successfully read the entire input, and encountered $1$ during the second phase.

It is also easy to give a context-free grammar for this language, using $\Sigma$ as a shortcut for the alphabet:
\begin{align}
&S \to \Sigma S \mid \Sigma S \Sigma \mid \Sigma T 1 \\
&T \to \Sigma T \Sigma \mid \epsilon
\end{align}


Let us assume/understand that "memory access latency" means the "memory access latency" to access the cache when there is a hit. (It appears reasonable to just say "memory access latency" since the latency to access the cache might be (almost) the same whether there is  hit or miss.) Otherwise, there is no solution to this problem or we have to introduce other less straightforward assumptions.

Once we have made that assumption/understanding, the miss penalty is easy to solve.

Miss Penalty = (AMAT - Hit time) / Miss Rate
             = (AMAT - hit-rate * memory-access-latency) / Miss Rate
             = (80 - (1 - 0.4) * 60 ) / 0.4
             = 110

However, it is rather unnatural to interpret "memory access latency" as referring to accessing the cache since by default, "memory" refers to the main memory while the cache memory, L1 memory and L2 memory are referred as cache.

Another plausible situation is the last given condition is, for example, memory access latency = 160 instead of memory access latency = 60. Then we can understand "memory access latency" as, very naturally, the latency to access the main memory when there is a cache miss. I put an emphasis because it is reasonable to assume there is no way to skip the cache (in this kind of exercises). Note that this natural interpretation cannot make much sense originally when the value is 60, which is less than the given "AVG Memory Access Time", 80. I will leave the question as an exercise for you if the last condition is indeed changed to memory access latency when there is miss = 160.

(Yet another way to resolve the situation is to change AVG Memory Access Time = 80 to, for example, AVG Memory Access Time = 30.)

You may check my answer for related information.


Initializing non-deterministic variables in QBF

It looks to me like there is some confusion here about what QBF is and when it is needed.  You don't need QBF for this problem; SAT is fine.

Here's how to solve this using a SAT solver. Notice that the condition counter > 0 is true at the end if and only if there was at least one loop iteration where f output 1.  In other words, the assertion will be true if and only if

$$\exists \mathtt{loop\_aux\_0},\dots,\mathtt{loop\_aux\_n} . \mathtt{f}(\mathtt{loop\_aux\_0},\dots,\mathtt{loop\_aux\_n})=1.$$

That can be expressed as a SAT instance.  There are no nested/alternating quantifiers; the formula has the form $\exists x. \varphi(x)$, so it can be solved by SAT.  Simply express the condition f(loop_aux_0, ..., loop_aux_n)=1 in CNF form, and then use a SAT solver to check whether that condition can ever be true (for any value of the loop variables).

QBF is useful when you have nested quantifiers, e.g., $\exists x . \forall y . \exists z . \varphi(x,y,z)$.  The result will be either true or false.

It's also worth knowing about #SAT.  #SAT is useful when you want to count the number of satisfying assignments to some formula $\varphi(x)$.  In other words, instead of checking whether $\exists x . \varphi(x)$ is true, suppose we want to know the number of values $x$ such that $\varphi(x)$ is true; then this is an instance of #SAT.

QBF and #SAT are not the same thing.  They're different problems.  And QBF isn't some kind of magic wand that lets you compress any SAT instance by some enormous factor; QBF is for a specific type of logical formula.


Is there a contradiction between "set-theoretic" and "formal" definition of "Big-O"?

The first statement you made is not correct. $O(n)$ is the set of all functions $f(n)$ that are bounded above by some constant multiple of $n$ for sufficiently large $n$. The functions you have listed all belong to the set $\Omega(n)$ which is almost like $O(n)$ but instead of being bounded above by $k\cdot n$, this is the set of functions that are bounded below by $k\cdot n$ for sufficiently large $n$.

So, there is no contradiction. But you do need to look at your definitions a bit more carefully.


Beta-reduction is only allowed when the argument does not contain any free variable that is bound in the function. So before you can beta-reduce $(\lambda x. \lambda y.x) y$, you must rename the bound variable $y$ using alpha-conversion.

Formally speaking, beta-reduction and equivalence are defined not over lambda terms, but over lambda terms modulo alpha-conversion. So by performing alpha-conversion, you are not changing the term.

$$
  (\lambda x. \lambda y.x) y =_\alpha (\lambda x. \lambda z.x) y
  \to_\beta \lambda z.y
$$

An alternative approach is to treat terms syntactically, and allow the beta-reduction, but perform the alpha-conversion as part of the substitution. The two approaches can be shown formally to be equivalent (for almost all uses of the lambda calculus, this is an unimportant presentation detail).

$$
  (\lambda x. \lambda y.x) y \to_\beta (\lambda y.x)[x\leftarrow y]
  =_\alpha (\lambda z.x)[x\leftarrow y] = (\lambda x.y)
$$


Reducing from NPC to Co-NPC => NP = Co-NP?

In short
yes
Proof
Let's assume $X$ is NP-complete and $X$ is in co-NP.
We show that $NP \subseteq coNP$ and viceversa.
[$NP\subseteq coNP$]
Because $X$ is NP-complete
$=>$ for each $L\in NP$ we can found a polytime function $f$ that $s\in L$ iff $f(s)\in X$.
But $X$ is in coNP
$=>$ for the polityme reduction closure of coNP, $L\in coNP$ too
$=>$ $NP\subseteq coNP$
[ $coNP \subseteq NP$ ]
let $B\in coNP$
$=>$ $B^c \in NP$
$=>$ $s\in B^c$iff $f(s)\in X$
$=>$ $s\in B$ iff $f(s) \notin X$
$=>$ $s\in B$ iff $f(s) \in X^c$
but because $X \in coNP$
$=> X^c \in NP$ and for polityme reduction closure of $NP$
$=> B \in NP$
$=>coNP\subseteq NP$
So $NP=coNP$ under this assumptions.


M-trees appear in this survey of image retrieval techniques (emphasis added):

  In Berretti et al. [2000], curves are represented by a set of
  segments, or tokens, whose feature representations (curvature and
  orientation) are arranged into a metric tree [Ciaccia et al. 1997] for
  efficient shape matching and shape-based image retrieval.


What is implied probability, in the context of universal codes?

The idea is the following:

the following tree $T$

$
\\
\emptyset
\\
|   \ \setminus \\
|   \ \ \ \setminus \\
0 \ \ \ \ \   1
\\
|   \ \setminus \\
|   \ \ \ \setminus \\
00 \ \ \ \ \   01\\
\\
\ \ \ \ \ \ \ \ \ \ |   \ \setminus \\
\ \ \ \ \ \ \ \ \ \ |   \ \ \ \setminus \\
\ \ \ \ \ \ \ \ \ \ 010 \ \ \ \ \   011
$

of depth 3 is constructed by

Taking an object labeled as $\emptyset$ that has probability 1 and splitting it in half into two pieces which we label as $0,1$; who each acquire equal probabilities 1/2 individually.
Taking the object labeled as $0$ that has probability 1/2 and splitting it in half into two pieces which we label as $00,01$; who acquire equal probabilities 1/4 individually.
Taking the object labeled as $01$ that has probability 1/2 and splitting it in half into two pieces which we label as $010,011$; who each acquire equal probabilities 1/8 individually.

This is essentially the "unwrapping the Huffman algorithm in reverse." You are asking the wrong question, you should be asking "Why label it this way?"

The idea behind the Huffman coding scheme is that

$0,1$ each cost 1 unit of "communication complexity" or "space complexity" depending on your interests
$00,01$ each cost 2 units of "communication complexity"
$010,011$ each cost 3 units of "communication complexity"

You should read chapter 5 of Cover and Thomas

and this Wikipedia article on the kraft inequality is probably helpful too. however, if you want a proof of the infinite kraft inequality you need chapter 5 of Cover and Thomas.

The idea is to continue this (type of) procedure unto infinity so that we get a something the following tree $T_\infty$

$
\\
\emptyset
\\
|   \ \setminus \\
|   \ \ \ \setminus \\
0 \ \ \ \ \   1
\\
|   \ \setminus \\
|   \ \ \ \setminus \\
00 \ \ \ \ \   01\\
\\
\ \ \ \ \ \ \ \ \ \ |   \ \setminus \\
\ \ \ \ \ \ \ \ \ \ |   \ \ \ \setminus \\
\ \ \ \ \ \ \ \ \ \ 010 \ \ \ \ \   011 \\
\ \ \ \ \ \ \ \ \ \ |   \ \setminus \\
\ \ \ \ \ \ \ \ \ \ |   \ \ \ \setminus \\
\ \ \ \ \ \ \ \ \ \ \vdots \ \ \ \ \   0101
$

which has infinite depth.  Each time you "split" a string, you maintain a "partition of unity" i.e., you maintain a probability distribution. The kraft inequality states that if your code was constructed in this manner, i.e.,
$$
\sum_{i : \text{leaf of }T_\infty} 2^{-l(i)} = 1
$$
then the code is optimal.

  In other words if you have a set of binary strings $\mathcal{S}$ and the function
  $$p(s) = 2^{-l(s)}$$
  turns out to actually satisfy the kraft inequality, i.e.,
  $$
\sum_{s \in \mathcal{S}} 2^{-l(i)} = 1,
$$ then it is an optimal code. Therefore forming a probability distribution and being an optimal code are equivalent.

One can further prove that all such codes have a tree that witnesses their optimality.


Finding all (weighted) cycles through a given vertex

Enumerating all cycles might take exponential time

There cannot be any efficient algorithm for enumerating all cycles that contain $v$.  There could be exponentially many algorithms that go through $v$.  Therefore, any algorithm for enumerating all cycles could potentially take exponential time.

If the graph is very small and efficiency is not important, you could enumerate all cycles that go through $v$ using depth-first search or breadth-first search starting from $v$.  Or, you could use Johnson's algorithm: see Find the Simple Cycles in a Directed Graph.

You can't compute the cycle-sums you want efficiently

Now for some more bad news.  You want to compute the sum over all simple cycles, of the sum of edge-weights in the cycle.  Unfortunately, this cannot be done efficiently, either.  This problem is #P-hard, which means there is no hope for a polynomial-time algorithm for it.

Here's a proof of #P-hardness, by reduction from the problem of counting the number of simple paths from $s$ to $t$ (which is a #P-complete problem).  Let $G$ be a graph, and vertices $s$ and $t$ be specified.  Add new vertices $u,v$ and edges $(t,u)$, $(u,v)$, and $(v,s)$.  Label each edge with the weight 0, except that the edge $(u,v)$ will be labelled with weight 1.  Now suppose you had an efficient algorithm to compute the sum over all simple cycles, of the edge-weights in that cycle, for the resulting graph.  Then its output would be exactly the number of simple cycles in this graph, or equivalently, exactly the number of simple paths from $s$ to $t$ in $G$.  Thus, any polynomial-time algorithm for your problem would immediately imply a polynomial-time algorithm for counting the number of simple paths from $s$ to $t$; since the latter is #P-hard, your problem must be #P-hard, too.

For more details on #P-hardness of counting simple paths, see, e.g., https://cstheory.stackexchange.com/q/20246/5038, https://stackoverflow.com/a/5570751/781723, How hard is counting the number of simple paths between two nodes in a directed graph?.

So, the bad news is: there is no efficient algorithm for your problem, and I can prove it.

Time to look for some alternative: e.g., find some way to avoid solving your problem, or hope that your graph will be extremely small (so that exponential-time algorithms are acceptable), or look for an approximation algorithm, or something.  But you're not going to find an algorithm to solve your problem that is efficient on general graphs.

Other miscellaneous comments

It's important to phrase your question so you ask for what you really want.  It sounds like what you really want to know is whether it's possible to compute the sum of the edge weights over all cycles that go through $v$.  If that's what you really want, don't ask whether it's possible to enumerate all cycles through $v$; ask whether there's an algorithm to do what you really want.  There might be a better way to do what you really want, without enumerating all cycles.

(Incidentally, if you are summing over all cycles of any length, it is important to restrict your sum to simple cycles.  If you don't restrict to simple cycles, then there are infinitely many cycles and the sum is going to be either $+\infty$ or $-\infty$.)

For instance, it is possible to efficiently compute the sum of the cycle weights over all cycles of length $k$ (not necessarily simple) that go through $v$, where the weight of a cycle is the product of the edges in $v$.  Here's how.

Here's the key idea.  Let the matrix $M$ represent the adjacency matrix for the graph, i.e., $M_{i,j}$ holds the weight on the edge $(i,j)$, or $0$ if there is no such edge.  Let $e_i$ denote the vector that is $1$ in its $i$th component and $0$ in all other positions.  Let $x = M^k e_v$.  Then $x_j$ is a sum, over all paths from $v$ to $j$ of length $k$, of the products of the weights along each such path.  Thus, $x_v$ is a sum of the weights of all of the cycles of length $k$ that go through $v$.  The running time is polynomial.

Unfortunately, this is not restricted to simple cycles, so it is not what you  want.  Also, this approach ends up multiplying the edge weights along a single cycle, rather than adding them, so it is also not what you want for that reason.  Nonetheless, it shows how some problems of this form can potentially be solved in polynomial time without enumerating all cycles.


Theoretical speed gain of quad core vs. single core

There is no absolute value of how much faster a quad-core would be compared to a single-core. As the comments have said, it very much depends on exactly what you are doing whether it will be faster or slower. Even live performance testing may not give a fair answer since it won't model exact runtime behaviour.

In any case, if you are looking for a theoretical model it certainly is possible, though, as you can quickly see, not practically possible.

First you need to understand the architecure of the chips of the involved. When you move from single-core to quad-core not all resources are actually quadrupled. In particular the memory is still a shared resource. This memory is then split between a series of caches, some of which are shared, and some of which are not shared. Each cache is connected to the other caches either by a dedicated bus, or a shared data bus. Each of these caches, and buses, has a real bandwidth and latency number. This is not likely published, but with some very focused tests can be obtained.

Second you need to understand how the application will be using memory. How this memory is shared and the order in which it is accessed. For a single thread you could, in theory, calculate the amount of time it spends loading data from the various cache levels. For a multi-core case a key value is how often you attempt to write to the same memory. In this case you will invoke the chips cache-coherency algorithm. This algorithm is usually documented (to some degree) and the time to synchronize can be reasonably well measured.

Combine these together and you'll see that with perfect knowledge of how the program behaves and how the processor behaves you would be able to calculate the theoretical gains of increasing the number of cores. In pratice this simply won't be possible for all but the simplest of programs (but even then the way the chips manage memory is complex enough to make the problem too difficult).

What you should get from this description is primarily that processor speed alone is not the only problem. Memory is often the key bottleneck. When svick says perfectly parallelized he means they don't share memory. In this case your threads will approach the maximum 4x speed gain as the memory contention is low. However, they still share some memory cache for reading (L3 and main memory on Intel) and thus could still be limited by the total memory bandwidth.

If you wish to look at a degenerate example lookup "false sharing". In such cases the total speed goes down as more processors are added.


Which research languages have a stronger typesystem than Haskell and why?

The question is somewhat problematic, since it relies on a subjective definition of "better."
Dependently-typed languages such as Agda, Idris, and Coq have a stronger type system than Haskell. This means, you can use the types in these languages to prove strictly more properties about your code than in Haskell. That is, there are more incorrect programs that will be caught.
However, this comes at a price: type inference, and testing whether any values of a given type exist, are no longer possible. This means for these languages, you need to explicitly annotate your code with types. Essentially this boils down to writing your own correctness proofs for your code.
So are these languages "better" than Haskell? They can check advanced proofs of correctness for your code, but they can't automatically prove properties about your code the way Haskell can.
Another research language that is "better" than Haskell is LiquidHaskell. This is basically Haskell with refinement types bolted on top, parsed from special comments.
Refinement types allow you you refine types with properties. For example, instead of having an Int, you can specify {i : Int | i > 0}, giving the type of all positive integers. Type inference is decidable with refinement types, but you can't prove nearly as many correctness properties with them as you can with dependent types.
There are other refinement type systems out there, but I'm not terribly familiar with any of them.


Time-complexity of recursive defined code

The time complexity depends only on $n$ but not on $x$. You can assume $T(n)$ denote the time complexity. For $n\leq 1$, $T(n)=O(1)$ apparently. For $n>1$, the first for-loop takes $O(n)$ time and the second for-loop takes $3T(n/3)$ time since it calls $b(n/3,\cdot)$ three times.


Finding k'th smallest element from a given sequence only with O(k) memory O(n) time

Create a buffer of size $2k$. Read in $2k$ elements from the array. Use  a linear-time selection algorithm to partition the buffer so that the $k$ smallest elements are first; this takes $O(k)$ time. Now read in another $k$ items from your array into the buffer, replacing the $k$ largest items in the buffer, partition the buffer as before, and repeat.

This takes $O(k * n/k) = O(n)$ time and $O(k)$ space.


I interpret it as meaning "algorithmic technique".  It's a general framework that can be used to solve a number of problems.

Don't worry too much about the meaning of that phrase.  It's not something with an accepted definition, and you don't need to understand it to gain the value from that survey paper; it's just a passing phrase.  Instead, focus on understanding the ideas and technical results in the survey paper.


Can a RE language be reduced to a non-RE language?

First, note that if $p$ and $q$ are any two statements, the implication $p\implies q$ is logically equivalent to $(\lnot q)\implies(\lnot p)$. This equivalence is known as "taking the contrapositive".

Because of this, your statements $(I)$ and $(II)$ are equivalent. That is, the first two properties you mention are equivalent (and they follow from $L \leq_m L'$). The second two properties are also equivalent. Your question then becomes:

$(I)$ If $L \leq_m L'$ and $L \in RE$, can we conclude $L' \not\in RE$ ?

In general, no, we can not conclude that.

For instance, take $L=\{0\}$. This is a decidable language (we can test the input string against $0$, and accept iff they are equal), so it is also a $RE$ language.

Now, note that we can many-one reduce $L$ to absolutely any set $L'$ except the empty set and the full set ($\Sigma^*$). This includes non-$RE$ sets like the complement of the halting problem.

Indeed, to find a reduction, take any word $w\in L'$ and any other word $x\notin L'$. Then, the reduction function behaves as follows: it tests its input, if it is equal to $0$, then it returns $w$, otherwise it return $x$.

By construction, this is a reduction, so $L \leq_m L'$, even if $L\in RE$ and $L'\notin RE$.


Depth of a pipeline in a CPU's architecture

I think that depth is a measure of the overlapping of instructions while number of stages is a hardware constant. When you increase the number of stages, you usually make the CPU faster but it is with dimishing margin. See Almdahl's law about this and the book "Computer Organization and Design" by Pattersson and Hennesay.

The more stages, the larger the depth but it is stated that there can be optimal number of stages or optimal depth:

According to (M.S. Hrishikeshi et. al. the 29th International Symposium on Computer Architecture)

  The difference between pipeline depth and pipeline stages; is the
  Optimal Logic Depth Per Pipeline Stage which about is 6 to 8 FO4
  Inverter Delays. In that, by decreasing the amount of logic per
  pipeline stage increases pipeline depth, which in turn reduces IPC due
  to increased branch misprediction penalties and functional unit
  latencies. In addition, reducing the amount of logic per pipeline
  stage reduces the amount of useful work per cycle while not affecting
  overheads associated with latches, clock skew and jitter. Therefore,
  shorter pipeline stages cause the overhead to become a greater
  fraction of the clock period, which reduces the effective frequency
  gains.


Why cannot we enumerate all Turing machines that have no fixed point?

Because we cannot find, given a NTM $N$ and an input $x$, whether $N$ fulfills the condition $N(x)\not= x$ in any given finite amount of time. More precisely, we cannot enumerate all pairs $(N,x)$ such that $N(x)\not= x$, although we can enumerate all pairs $(N,x)$ such that $N$ halts on $x$ and $N(x)\not= x$.

Think for a moment. When can you consider $(N,x)$ fulfills the requirement $N(x)\not=x$?

We run $N$ with input $x$ for some time and it stops. If it does not output $x$, great, we have found one.
We run $N$ with input $x$. However $N$ does not stop yet. It seems $N$ just won't stop. We want very much to say $(N,x)$ does not fulfill that requirement; however, there is no moment we can be sure of that. $N$ is just running at all times. If we conclude $(N,x)$ does fulfill the requirement at some moment, it can happen $N$ will stop at the next moment, outputting $x$. Because of this possibility, we will never add $(N,x)$ when $N$ never stops on input $x$, even though $(N,x)$ does satisfy the requirement.

Note this is vastly different from the other case. When can we consider $(N,x)$ fulfils the requirement $N(x)=x$?

We run $N$ with input $x$ for some time and it stops. If it does output $x$, great, we have found one.
We run $N$ with input $x$. However $N$ does not stop yet. Fine, we just do not consider $(N,x)$ fulfils the requirement yet. Continue running $N$.

You might argue that NTM $N$ can guess $x$ such that $N(x)$ will halt and output $y\not=x$. So we will find one such $N$.
There is no problem in that.

However, consider the case when $N$ never stops on every input. Now, imagine the exact moment you consider that $N$ fulfills the condition that $N(x)\not= x$ for some $x$, using any  algorithm. What is known to you at that moment? All you know is that $N$ has not stopped yet on any input. That, however, does not exclude the possibility that $N$ might stop later on for all inputs along all paths, always outputting the input. We can never exclude that possibility, forever. (More precisely, we can exclude that possibility for some $N$ for some inputs. However, there is no algorithm can determine that possibility for all $N$.)

  If I chose a DTM in place of an NTM to run $M_w(x)$ for all possible inputs, it would be game over if $M_w(x)$ didn't halt because that would prevent subsequent runs of $M_w(x)$ with different $x$es.

It would also be game over if $M_w(x)$ will not halt for all $x$. Your $NTM$ will be running forever without ever outputting anything. That $(M,x)$ is in $L_2$ but your algorithm cannot claim it is in $L_2$ since there is no moment when the algorithm is able to claim that.

The explanation above is meant to be a way to understand the situation. A rigorous proof is still needed to confirm the conclusion mathematically (or "compute sciencely"). Since you have known a rigorous proof, I will not provide one here.


A regular expression for an automaton which accepts strings with no more than 3 consecutive zeros

Hint: A string with no more than 3 consecutive zeroes has the general form
$$0^{p_1} 1 0^{p_2} 1 0^{p_3} 1 \ldots,$$
where $p_i \leq 3$. Try expressing that structure as a regular expression.


What is the branching factor for nondeterministic games?

The branching factor depends on exactly how you model the game.  A standard way to model games that have some randomness is to imagine adding another player (the "dealer") whose only purpose is to make a random choice.

So if your game involves only one player Alice, we'll add another player Declan (the dealer).  Alice and Declan alternate turns.  During her turn, Alice can either play one of her cards or choose to draw from the pile.  Thus, if Alice has $n$ cards, she has $n+1$ actions she can choose from.  During Declan's turn, if Alice previously chose to draw, Declan selects one of the remaining cards and adds it to Alice's hand; otherwise he does nothing.  Thus, if there are $m$ cards remaining in the pile, Declan has either $m$ actions he can choose from, or only one.

With this model, the maximum branching factor is 53 (assuming Alice can have up to 52 cards in her hand).


What is the difference between exactness and optimality of an algorithm?

Every NP-complete problem can be solved in exponential time. Assuming that P differs from NP, it cannot be solved in polynomial time. It follows that the branch-and-bound algorithm probably doesn't run in polynomial time (in the worst case).

To give a concrete example, consider the problem of MAX-CLIQUE: given a graph, the task is to find a clique of maximum size. The decision version of this problem (given a graph and a number $k$, decide whether the maximum clique has size at least $k$) is NP-complete. This means that (unless P equals NP), no polynomial time algorithm can solve MAX-CLIQUE exactly on all inputs. However, there is a simple exponential time algorithm that does solve MAX-CLIQUE exactly: it just tries all potential cliques and checks which of them are present in the graph.

Finally, you mention that if a problem is NP-complete then the reason might be that there is no optimal solution. This is just wrong, and I suggest ignoring the source which led you to believe this statement.


Which type of computer programs could be called intelligent agents?

This is (obviously) up for debate. If you speak about agents, one common definition of agents is:

autonomy: agents operate without the direct intervention of humans or others, and have some kind of control over their actions and internal state;
social ability: agents interact with other agents (and possibly humans) via some kind of agent-communication language [Genesereth and Ketchpel, 1994];
reactivity: agents perceive their environment, (which may be the physical world, a user via a graphical user interface, a collection of other agents, the INTERNET, or perhaps all of these combined), and respond in a timely fashion to changes that occur in it;
pro-activeness: agents do not simply act in response to their environment, they are able to exhibit goal-directed behaviour by taking the initiative.

There is also the BDI model using the concepts belief, desire and intention for intelligent agents.

If you go further away from "agents" (this term has a specific meaning in computer science as it's also part of a software engineering paradigm) to "what makes a piece of code intelligent?" You'll see that every research area will give you a different answer. Artificial intelligence distinguishes between hard and soft AI. Neuroinformatics takes its answers from cognitive science, importing the definitions that biopsychology and neuro science give about cognition and what makes a being "intelligent". A philosopher will also have a different definition.

These definitions all have some common ground but in the end there is no ultimate definition everybody can agree on.


Find the computational complexity of a concatenated system

To summarize what you're saying:

You have an algorithm that runs in $O(n)$.
You're running it on $L$ different blocks, sequentially (no parallelism).
Every block has size $N$.

In this case, the total running time is indeed $O(LN)$.


Are context-free languages in $a^*b^*$ closed under complement?

This characterization of bounded context-free languages is due to Ginsburg ("The Mathematical Theory of Context-Free Languages"), and appears as Corollary 5.3.1 in his book. For general $k$ there are some restrictions on the semilinear sets, but for $k \leq 2$ these restrictions are always satisfied, and so it is straightforward to deduce that the complement of such a language (within $w_1^* w_2^*$) is context-free.

Ginsburg mentions these implications in his book.

Corollary 5.6.1 If $M_1 \subseteq w_1^*w_2^*$ and $M_2$ are [context-free] languages, $w_1$ and $w_2$ words, then $M_1\cap M_2$ is a [context-free] language.

Corollary 5.6.2 If $M_1 \subseteq w_1^*w_2^*$ and $M_2$ are [context-free] languages, $w_1$ and $w_2$ words, then $M_1 - M_2$ and $M_2-M_1$ are [context-free] languages.


How to find the shortest path from some vertex in set $S$ to set $S'$

If all edge lengths are non-negative, then this can be solved in $O(|E| \lg |V|)$ time using a single invocation of Dijkstra's algorithm.

We're going to modify the graph slightly by adding a new vertex $s$.  Also, add an edge of length 0 from $s$ to each vertex in $S$.

Next, run Dijkstra's algorithm, starting from the source vertex $s$.  Dijkstra's algorithm will compute for you the distance from $s$ to every other vertex $v$, i.e., it will compute $d(s,v)$ for all $v \in V$.  Note that $d(s,v)$ will be exactly the length of the shortest path from some vertex in $S$ to the vertex $v$.

Finally, compute $\min \{ d(s,v) : v \in S' \}$.  This will be the length of the shortest path from some vertex in $S$ to some vertex in $S'$.  That's your answer.

There's no need to run Floyd-Warshall.

If you can have negative edges, then it can be done in $O(|V| \cdot |E|)$ time.  Simply replace Dijkstra's algorithm with the Bellman-Ford algorithm.