Multi-level cache for which inclusion holds

Correct Answer: 1) and 4) only . For inclusion property to hold, every changes in L1 should be made in L2 also. therefore , L1 should be write-through. It is not necessary fr L2 to be write -back. And 4) is mandatory for the same reason i.e L2 would need to hold the contents as same as L1 and as much as ,or may be greater than L1.


Machine Learning: how to correctly calculate gradient descent for simple linear problem

First off, your gradient is error*x1 with respect to w1, but not to w0. The gradient for w0 is just error.

Second, you're computing error with the wrong sign. It should be predicted - actual, not the other way around. What you're doing is essentially adding the gradient at every step.


Finding minimal strongly connected graph

We can solve the problem in $\mathcal{O}(E \log V)$ by binary search.

We can identify the strongly connected components in a graph in linear ($\mathcal{O}(V + E)$) time. Thus we can check if the graph is strongly connected in linear time.

If $G(t_{0}) = (V, E(t_{0}))$ is strongly connected, so is $G(t) = (V, E(t))$ for $t \geq t_{0}$. Further, if $G(t_{0})$ is strongly connected, so is $G(t)$ where $t$ is the maximum edge weight that is at most $t_{0}$. Thus we can binary search for $t$ over all edge weights.

The algorithm is:

Sort edges by weight. Let $w_{i}$ be the $i$th smallest edge weight (1-indexed). Set $w_{0} = -1$.
Initialise binary search: set $l = 1$ and $h = |E| + 1$
While $l \neq h$:

set $m = \lfloor\frac{l + h}{2}\rfloor$. Then, If $G(w_{m})$ is connected, set $h = m$. Otherwise set $l = m + 1$.

If $l = |E| + 1$, no $t$ works. Otherwise, answer $t = w_{l}$

In the binary search, we maintain the invariant that $G(w_{h})$ is strongly connected (or $h = |E| + 1$), while $G(w_{l - 1})$ is not (assuming $|V| \geq 2$). We exit the loop when $l = h$, thus either $l = |E| + 1$ and the graph is not strongly connected for any $t$, or $G(w_{l})$ is strongly connected, but $G(w_{l-1})$ is not, thus $G(t)$ is not strongly connected for $t < w_{l}$. Thus the algorithm is correct.

The first step takes $\mathcal{O}(E \log E)$ time. The third step takes linear time and is executed at most $\log E$ times. Thus, the complexity is $\mathcal{O}((V + E) \log E) = \mathcal{O}(E \log V)$.


Stable marriage problem with only one side having preferences

The answer to your first question is: yes, there is a simple augmentation.  It is described in the standard literature on the stable marriage problem.  See the Wikipedia article for references in the literature where this is described.  It is also described here: The stable marriage algorithm with asymmetric arrays.  See also https://cs.stackexchange.com/a/28528/755.

Your second question is an instance of the assignment problem.  We form a bipartite graph, with an edge between a doctor $d$ and a school $s$ if the school $s$ is among $d$'s top 3 choices.  Then we want to know whether there is a perfect matching in this graph.  (If a school has multiple slots, then make multiple copies, one copy per slot.)  There are polynomial-time algorithms to determine whether a bipartite graph has a perfect matching.  See also Existence of bipartite perfect matching.

So, the answer to your second question is: yes, it is possible.


Product of all nodes except for one in Binary Tree

One simple approach: for an internal node $x$, let $P(x)$ denote the product of the integers on the path from the root to $x$, and let $Q(x)$ denote the set of integers obtainable as the product of all but one of the integers on the path from the root to $x$.  Now, descend the tree from the root down to the leaves, computing $P(x)$ and $Q(x)$ for each node $x$ as you go.  Note that you can compute $P(x),Q(x)$ from $P(w),Q(w)$, where $w$ is the parent of $x$.

The asymptotic worst-case running time will be $O(n^2)$.  No algorithm has better worst-case asymptotic running time, as there can be $\Theta(n^2)$ different products that you need to output, so any correct algorithm will need to have worst-case running time at least $\Theta(N^2)$.


In what case would bi-directional BFS have a worse asymptotic run time than regular BFS?

When attempting to find a path from a source vertex $s$ to a target vertex $t$, with both BFS and bi-directional BFS, if you assume a fairly steady branching factor $b$, the number of possibilities checked (and hence the running time) is dependent on the depth. For BFS the depth is the distance from the source to the target, giving $b^{k}$ vertices visited, for bi-directional BFS the two searches meet in the middle, so it's two lots of half-distance searches - $2\cdot b^{k/2} = 2\cdot\sqrt{b^{k}}$, which is clearly better.

So to get a worse time, you need a route from $s$ to $t$ that traverses very few vertices, but the route from $t$ to $s$ would visit many vertices. Essentially you want an asymmetric branching factor.

The family of star graphs would be sufficient for this. A star graph has a single central vertex, and all other vertices are connected directly to it, and no other vertices. So if you have $s$ as one of the pendent vertices, and $t$ as the central vertex, normal BFS would take constant time, and bi-directional BFS would take linear time. You can also invent more complicated examples that share this property of a low branching factor going one way, but a high one coming the other (up to a point).


Red-black tree amortized cost of the rebalancing

If you look at the rules for what happens in a red/black tree insertion, you can see that the fixup rules for maintaining the red/black invariants only propagate upward if the newly-inserted node becomes the child of a red node with a red sibling.

Let's call a "fissionable" group in the red/black tree a black node with two red children. If you do an insertion into a fissionable group, the fissionable group will be recolored and rotated in a way that ends up eliminating that fissionable group, but which propagates the insertion fixup to a higher level in the tree. If you set the potential function of a red/black tree to be the number of fissionable groups in the tree, then the true cost of doing an insertion is 1 + r, where r is the number of groups destroyed, and the number of new fissionable groups created is at most one (you should check this), so the amortized cost of a fixup is O(1) because the potential drop is r.

It's a lot easier to think about this by looking at the isometry between red/black trees and 2-3-4 trees. A fissionable group in a red/black tree corresponds to a 4-node in a 2-3-4 tree, and if you understand 2-3-4 tree insertions it's pretty easy to see why the amortized cost of an insertion into a red/black tree is O(1).


Linear program for min-length pair of edge-disjoint paths problem

I think this can be solved in polynomial time by finding a minimum-cost maximum flow in the graph, where you set the capacity of each edge to $1$ and the cost of each edge $e$ to $-l(e)$, and add a source node $s_0$ with an edge $s_0 \to s$ of capacity 2 and cost 0.  (You might need to add a "demand" that the edge $s_0 \to s$ has exactly 2 units of flow along it.)
If you must formulate it as an ILP, introduce a zero-or-one variable $x_e$ for each edge, with the intended semantics that $x_e=1$ means that edge $e$ is in the first path.  Add a constraint that, for each vertex $v$ other than the source/sink, $\sum_w x_{(v,w)}$ is 0 or 2; for the source and sink, it must be 1.  This captures the requirement that you have a path from $s$ to $t$.  Add another zero-or-one variable $y_e$ for each edge, with similar constraints to ensure it represents a path from $s$ to $t$.  Finally, enforce the disjointness requirement: $x_e + y_e \le 1$.  The objective function to maximize is $\sum_e l(e) x_e + l(e) y_e$.
You can enforce a constraint that a variable $z$ is 0 or 2 by requiring $z=2t$ where $0\le t \le 1$ is a fresh zero-or-one integer variable.


Why must a Turing Machine that Repeats the Same Configuration Twice be in an Infinite Loop?

This is because the transition function $\delta$ of a TM is deterministic. If the configuration is the same, then the arguments of $\delta$ are also the same, resulting in an infinite loop. Formally, this can be proved like @gnasher729 does.

Let's consider your example. If your $TM$ moves like the following,

$$
  (q_1, \dots00[0]111\dots) \xrightarrow{q_1, \text{right}} (q_1, \dots000[1]11\dots) \xrightarrow{q_1, \text{left}} (q_1, \dots00[0]111\dots)
$$

then the last step equals the first one, which means an infinite loop.


Minimum cost to match $n$ people with $m$ shops

Your problem is an instance of minimum bipartite perfect matching. This is known as the assignment problem, and there are known efficient algorithms.

As a first step, you should compute the weights of all edges, using the formula your are given (L1 distance between the point corresponding to the person and the point corresponding to the shop).


One way, if you want to prove that $n2^n \in 2^{\mathcal{O}(n)}$, is to show that there exists a $c \in \mathbb{R}$ such that $n2^n \le 2^{cn}$ for all $n$ greater than some $n_0 \in \mathbb{N}$.

Correspondingly, if you want to show the contrary, then you have to show that such a $c$ does not exist. However, we will see that the statement is true.

Choose $c = 2$, i.e., we ask whether $n2^n \le^? 2^{2n} = 4^n$ for all $n > n_0$. We know that $n \le 2^n$ for all $n \in \mathbb{N}$. Therefore, it also holds that $n2^n \le 2^n\cdot 2^n = 2^{2n}$. Hence, we have an upper bound for the function $n2^n$ by choosing $c = 2$. In this case, we can set $n_0 = 1$, for instance.


I suspect you should be able to solve this with a sweepline algorithm, probably in $O(n \log n)$ time or something like that.
In particular, I suggest you build a data structure so that for any $x$, you can find the range of $y$-values that are in the intersection of all the circles.  You should be able to build such a data structure by mimicking the Bentley-Ottmann algorithm.  Decompose each circle into four quarter-circles (arcs that cover one-fourth of the perimeter of the circle).  Each quarter-circle takes the place of a line segment.  Each intersection between two quarter-circles is an "event".  Then it is easy to answer your original question; each interval of $x$ values between two consecutive events corresponds to a single leaf in the tree, and you can quickly compute the lowest $y$ value in the intersection for that range of $x$ values, then do that for each such interval.  I haven't tried to work through all the details, so I suggest you check the specifics to see if this works out or if there is some challenge I've overlooked.


Assuming all the quantities are positive, just use $\log(Y-iy)\leq \log Y$, expand the brackets and use the standard identities for $\sum_i i$ and $\sum_i i^2$.  The $\log$ term disappears anyway since, asymptotically, it's dominated by the terms polynomial in $i$.


To find median of k sorted arrays of n elements each in less than O(n*k*log(k))

Let us denote the arrays by $A_1,\ldots,A_k$, their sizes by $|A_1|,\ldots,|A_k|$, their medians by $m_1,\ldots,m_k$, and their union by $\mathbf{A}$. We will try to solve the following more general problem: given $t$, determine the $t$'th smallest element in $\mathbf{A}$.
Let $m_r = \min(m_1,\ldots,m_k)$ and $m_s = \max(m_1,\ldots,m_k)$. Define
$$
N = \sum_{i=1}^k \lceil |A_i|/2 \rceil.
$$
There are at least $N$ many elements in $\mathbf{A}$ whose value is at least $m_r$, and at least $N$ many elements in $\mathbf{A}$ whose value is at most $m_s$.
If $N \geq t$ then elements larger than $m_s$ cannot be the $t$'th smallest element. In particular, we can throw out the upper half of $A_s$. Similarly, if $N \geq n+1-t$ then elements smaller than $m_r$ cannot be the $t$'th smallest element, and so we can throw out the lower half of $A_r$ (and update $t$ accordingly, by subtracting $\lfloor |A_r|/2 \rfloor$). Note that $\min(t,n+1-t) \leq \lceil n/2 \rceil \leq N$, and so at least one of these cases must happen.
How many rounds does it take this algorithm to complete? Each round results in reducing the size of one of the $k$ arrays roughly by half (the reduction is $\ell \mapsto \lceil \ell/2 \rceil$). One can check that it takes $\lceil \log \ell \rceil$ steps to reduce each array to a singleton. Therefore the number of rounds it takes the algorithm to narrow down all arrays to a single element is
$$
\sum_{i=1}^k \lceil \log |A_i| \rceil \leq k + \sum_{i=1}^k \log |A_i| \leq k + k \log \sqrt[k]{|A_1| \cdots |A_k|} \leq k + k \log \frac{|\mathbf{A}|}{k}.
$$
After an initial round which takes $O(k\log k)$ time, each subsequent round can be implemented in $O(\log k)$, if we store the medians in an appropriate data structure such as a heap. Following this phase, we are left with $k$ elements, and we can run a linear time selection algorithm to find the $t$'th smallest element in $O(k)$. In total, this algorithm runs in time
$$
O\bigl(k\log k + k \log \tfrac{|\mathbf{A}|}{k}\bigr) = O(k\log |\mathbf{A}|).
$$
When $|A_i|=n$ for all $i$, this is $O(k\log (kn))$.


What does $ \forall \alpha_1, \dots , \alpha_n . \tau $ mean formally as a type?

The notation is explained in your course material, e.g. here starting on slide 47.
In the notation $$T = \forall \alpha_1, \dots, \alpha_n.\tau$$ $\alpha_i$ are type variables, the $\tau$ is a monomorphic type, and $T$ is a universally quantified, polymorphic type. While free type variables may occur in $\tau$, the quantified variables $\alpha_i$ do not occur free in $\tau$.

  Why is there a dot separating the quantifier and the type

This is a just a syntactic convention used in type theory. The dot separates the quantifier part from the type it applies to.

  How does this relate to normal FOL? e.g. if I had $ \forall x \phi(x) $ that would mean that for all values x can take in the universe at hand, the proposition $\phi(x)$ is true

There's a strong relationship between logical formulas and types in programming languages, called Curry-Howard isomorphism.

  Is $\tau$ a function of the (meta?) variables $ \forall \alpha_1, \dots , \alpha_n $?

$\tau$ is not a function, it's a monomorphic type. You can think of the quantification as adding more context to this monomorphic type thus making it polymorphic. The quantification basically "hides" the variables from the context the whole expression appears in.

  What do $ \forall \alpha_1, \dots , \alpha_n $ stand for?
  Are $ \forall \alpha_1, \dots , \alpha_n $ meta-variables? What is their domain?

$\alpha_i$ are type variables that (typically) occur free in $\tau$, but are bound by the quantification and do not occur free in $\forall\alpha_i.\tau$ anymore. Like variables in a mathematical expression represent placeholders for concrete values, type variables represent placeholders for more concrete types.

  Could I have a couple of concrete examples of what they are

The most common example of a polymorphic type is the list type $\forall \alpha . \alpha\;\mathsf{list}$ (this is the notation for Ocaml, in Haskell the notation would be $\forall \alpha.[\alpha]$). In your real code this polymorphic type might be used as a monomorphic type when $\alpha$ is replaced by a concrete type like $\mathsf{int\;list}$, $\mathsf{bool\;list}$ or even $\mathsf{(int\;list)\;list}$.

Sometimes you may still deal with polymorphic types, for example the empty list literal $[\,]$ has the polymorphic type $\forall\alpha.\alpha\;\mathsf{list}$. Note that this is different from when you use $[\,]$ in your real code when it usually will be specialized to $\mathsf{int\;list}$ (or whatever concrete lists you are dealing with) when type inference happens. So $[\,]$ may have one polymorphic type or one of many monomorphic types, where the latter are all very different.

The above linked PDF gives more examples on slide 55.


Relationship between inductive families and type-returning functions

As mentioned by Andrej, this is an instance of transporting along an equivalence of families and display maps. In this specific case, we have an equivalence of graphs and relations.
open import Function
open import Data.Product
open import Relation.Binary.PropositionalEquality
open import Level renaming (zero to lzero; suc to lsuc)

-- type of relations on a set
Rel : ∀{i j} → Set i → Set (i ⊔ lsuc j)
Rel {i}{j} V = V → V → Set j

-- type of graphs with set of vertices V
record Graph {i j}(V : Set i) : Set (i ⊔ lsuc j) where
  field
    E   : Set j   -- edges
    src : E → V   -- source vertex
    tgt : E → V   -- target vertex
open Graph

Rel→Graph : ∀ {i j V} → Rel {i}{j} V → Graph {i}{i ⊔ j} V
Rel→Graph R = record {
  E   = ∃₂ λ s t → R s t ;
  src = proj₁ ;
  tgt = proj₁ ∘ proj₂ }

Graph→Rel : ∀ {i j V} → Graph {i}{j} V → Rel {i}{i ⊔ j} V
Graph→Rel {V} G s t = ∃ λ e → (G .src e ≡ s) × (G .tgt e ≡ t)

Note that we can only define the round-tripping functions if i ≤ j, since then the output i ⊔ j level becomes j, and the trip is well-typed. Your Link definition does not fit into this, but it's possible to just redefine it as Link : Set → Set → Set₁ without loss of generality (as the two definitions are equivalent).
If the levels check out, we can show that round-tripping in both directions yields equivalent relations and graphs respectively. We don't need to know anything about the internals of the relations and graphs involved; this equivalence always holds.
Your transformation makes use of the fact that the set of edges for the graph is equivalent to a small set, since the relation only has two possible edges.
open import Data.Unit
open import Data.Bool
open import Data.Integer
open import Data.Nat

data Link : Set → Set → Set where
  link-a : Link ⊤ Bool
  link-b : Link ℕ ℤ

-- the graph of Link
Link' : Graph Set
Link' = Rel→Graph Link

-- an equivalent graph with smaller edges
Link'' : Graph Set
Link'' = record {
  E   = Bool ;
  src = λ {false → ⊤; true → ℕ} ;
  tgt = λ {false → Bool; true → ℤ} }

Now, anything which depends on an edge only needs do depend on a Bool. In particular, Tie' Link'' : Set.
record Tie {j} (R : Rel {_}{j} Set) : Set (lsuc j) where
  field
    E   : ∃₂ λ A B → R A B
    fun : proj₁ E → proj₁ (proj₂ E)

record Tie' {j} (G : Graph {_}{j} Set) : Set j where
  field
    E   : G .E
    fun : G .src E → G .tgt E

The equivalence of graphs and relations generalizes to relations of any arity, and also to multiple relations of arbitrary arities, where relations can be indexed over other relations. In general, the equivalence says that for each telescope of dependent n-ary relations, there is a direct category $C$ such that the telescope is equivalent to the set of functors from $C$ to $\textbf{Set}$.
In the case of graphs, $C$ has two objects and two arrows between them, going in the same direction, so a functor $F : [C,\textbf{Set}]$ consists of two sets $V,E$ and two functions $src, tgt : E \rightarrow V$, so we can see that every $F$ is a graph.

Are Tie and Tie′ meaningfully distinct, in the sense that Tie allows
doing things that Tie′ does not?

They are equivalent, we get one from the other by transporting the parameter along the graph-relation equivalence.

Seeing as the transformation is entirely mechanical, intuitively it
seems we ought to be able to somehow achieve Tie Link : Set while
retaining Link as an indexed type, but it isn’t clear to me that this
is actually possible.

If we're working in cubical Agda, the graph-relation equivalence can be proven using univalence. Then, every possible construction which depends on relation can be transported to another which depends on a graph. Additionally, everything which depends on Link can be transported to depend on Rel→Graph Link. So at least this part works completely automatically.
However, the resizing part is not automatic, i.e. we have to prove that Rel→Graph Link is equivalent to Link'' with the small set of edges. It is not true in general that the set of edges for a relation is smaller than the set of vertices. Probably it's possible to have a conservative algorithm which tries to find such resizings, I don't think it has been researched.

... in a similar sense to that described in Inductive families need
not store their indices. Is this reasoning flawed, or is this simply
an implementation infelicity?

The technique in "Inductive types need not store their indices" is related but not exactly the same thing. In that paper, the transformation is a bit more restricted & specific thing, as there the point is to convert an inductive type family to a purely recursive one. The family-display map translation can be also used to get rid of indices, but that works in a "non-algorithmic" and different way. A classic example is vectors.
Let's have Vec A : ℕ → Set. We have an equivalence between ℕ → Set and Σ Set λ A → (A → ℕ) (as another case of the family-display map equivalence).
open import Data.Vec
-- Vec : Set → ℕ → Set

Vec' : Set → Σ Set λ A → (A → ℕ)
Vec' A = ∃ (Vec A) , proj₁

But now we can notice that ∃ (Vec A), the so-called "total" type (analogous to the type of edges previously) is equivalent to List A.
open import Data.List

Vec'' : Set → (∃ λ A → A → ℕ)
Vec'' A = List A , Data.List.length

Now, we can convert back to the family version with the generic equivalence:
Vec''' : Set → ℕ → Set
Vec''' A n = ∃ λ (l : List A) → Data.List.length l ≡ n

Which is a definition of vectors which does not store indices. But this is more like a hint, and this de-indexing does not work in a mechanical way, unlike the "need not store indices" technique.

Has the relationship between these two constructions been treated
explicitly in any existing literature?

I don't know of any reference which is exclusively about this equivalence, but it's commonly featured in category theory and type theory (or math in general). The two definitions of graphs is a classic example. There's also the equivalence of indexed categories (family version) and fibrations (display map).


Does every undecidable problem contain a decidable subset?

Yes. The empty language is decidable and subset of every other language.
You can also say that every undecidable language has a superset which is decidable ($\Sigma^\ast$ for example).


Expected number of maximal cliques in $G(n,p)$

Since $\mu$ is the sum of $n$ terms, we can estimate it up to a factor of $n$ by the maximal term:
$$ \max_{d=1}^n \binom{n}{d} p^{\binom{d}{2}} (1-p^d)^{n-d} \leq \sum_{d=1}^n \binom{n}{d} p^{\binom{d}{2}} (1-p^d)^{n-d} \leq n\max_{d=1}^n \binom{n}{d} p^{\binom{d}{2}} (1-p^d)^{n-d}. $$
In order to find out which term is the largest, we can use the estimate
$$ \log_2 \binom{n}{d} p^{\binom{d}{2}} (1-p^d)^{n-d} \approx nh(d/n) + \binom{d}{2} \log_2 p - (n-d)p^d, $$
which is true up to polynomial factors for $d = \omega(1)$. We can estimate the magnitude of the largest term by differentiating this quantity with respect to $d$. If you follow this path, you should obtain an estimate for $\mu$ which is tight up to polynomial factors in $n$.


What does 'Describe the language of this automaton' mean?

The language of an automaton is the language accepted by the automaton, that is, the set of words accepted by the automaton.
Now, certainly, one way of describing the language is as the language accepted by this particular automaton. But the question is asking you to find a simpler description. Here is the set of words accepted by your automaton:
$$
01, \\
001, 101, \\
0001, 0101, 1001, 1101, \\
00001, 00101, 01001, 01101, 10001, 10101, 11001, 11101, \\
\ldots
$$
Can you spot a pattern?


The answer to your question is formally "yes". This is because one possible Turing machine that halts iff P=NP is either (i) a Turning machine that always halts or (ii) a Turing machine that never halts (regardless of its input).
However, the following argument might be closer in spirit to what you are asking:
Assume that $P=NP$ is not independent from the axioms you are (implicitly) using.
Since proofs are enumerable you could build a Turing machine $T$ that iterates over all "candidate proofs" that P=NP.
When a candidate proof $\pi$ is considered, $T$ checks whether $\pi$ is an anctual proof. If it is, $T$ halts immediately. If it isn't, $T$ continues with the next candidate proof.
It follows that $T$ halts iff $P=NP$.


Why are primitive types stored in a stack in systems level software?

You've probably encountered the simplest definition of a stack, which is a data structure with two operations push and pop, and some basic properties:

If you call push on a value and then pop, the value you get from the pop is the value passed to push, and the stack is returned to its original state.
pop is invalid on a stack where there has never been a push (empty stack).
These properties also apply if the stack is modified in the middle, as long as these modifications return the stack to its state before the modifications.

There are many equivalent formulations of these axioms. The point here is that with this definition, push and pop are the only things you're allowed to do on a stack.

With the metaphor of a stack as being like a stack of plates, you can't “peek” at a value that isn't at the top of the stack (the most recently pushed value). (Note that I'm describing a stack that grows upwards. Unfortunately there's no standard for that: some stacks are described as growing down. But even with downward-growing stacks, the word “top” usually means the most recently pushed value.) But when a stack is a data structure, it's often possible to access values anywhere in the stack.

The same word “stack” can mean any variant of the basic data structure, supporting other operations apart from push and pop. There's no completely universal limit for what can be called “stack”, but generally, if a data structure is called a “stack”, it means that it's a collection of values where the only way to add an item is push and the only way to remove an item is pop. Other operations may be supported, such as:

Reading the stack size.
Peeking, i.e. reading any of the values on the stack (not just the top one).
Modifying a value on the stack.

Let's look at programming languages now. Almost every programming language has a concept of function (or procedure, subroutine, method, etc. — the distinction is not relevant here). Function calls have certain properties:

If the code in function f calls a function g and then g returns, you're back to f, in the same context as before (“context” here means the values of local variables).
You can't return from the top level of the program that's not inside a function. (Depending on the programming language, this may not even be a thing: the program may start directly by calling a certain function, so that there's no way to have code outside of any function. Or a ”return“ statement outside of any function may exit the program instead.)
These properties also apply if there are additional sequences of function calls involved that return back to the original function.

Looks familiar? Yep, the function calls form a stack. (Many programming languages have ways to break the stack structure, such as exceptions which can pop many values from the function call stack in a single statement, or even more complex things that I won't go into.)

The way the function call stack is implemented on a processor is usually through a stack of return addresses. Each function call does a push of the current value of the instruction pointer before jumping to the code of the called function, and returning from a function is a pop in that stack and a jump to the popped address.

Each time a function is called, its local variables come into existence. So the variables, in turn, form a stack. Calling a function pushes a new entry on the variable stack for this function's variables, and returning from a function pops an entry from the variable stack. (You can model this either with a single entry for all of a function's variables and a single push/pop per call/return, or with one entry per variable and as many push/pop per call/return as the function has variables.)

Note that variables are associated with a function call, not just with a function. When a function is called recursively, or more generally as part of a chain of calls of mutually recursive functions, each function call has its own variables, even if they happen to be calls to the same function. Conversely, local variables of a function don't “exist” while the function isn't being called. (Some of the very first programming languages had one storage area per routine, which existed all the time. These languages did not permit recursive calls. No modern programming language works that way, but some hardware description languages do.)

In a language with dynamic scoping, if a function f calls a function g, the code of g can access the variables of f by name. This is an example of a stack with extra operations: the code of g can read and modify the variables of f. The code of g can't create new variables of f or destroy variables of f, so this is still a stack. In a language with [lexical scoping]9https://en.wikipedia.org/wiki/Scope_(computer_science)#Lexical_scoping), the code of g can't access the variables of f by name, but it may nonetheless be able to access and modify their value if it can see a pointer or reference to a variable of f.

So far I've described how almost every programming language works. The specifics of what “the variables of a function call” means depends on the programming language. There's the association between the variable name and its value, and there's the value itself. Most programming languages have three classes of storage: global (exists for the whole lifetime of the program), stack (lasts as long as a function call), and heap (can be created and destroyed arbitrarily). But how apparent this is depends heavily on the language. In most higher-level languages, these classes of storage are a detail of how the compiler or runtime environment works, because storage allocation and destruction is automatic. Variables have a scope (the parts of the program where a certain name refers to that variable). Storage usually doesn't have an explicit scope in higher-level languages, but it does in lower-level languages.

In Rust, the scope of storage is explicit. A variable's storage lives as long as the variable lives, i.e. until the function returns. It lives longer if the value is returned from the function. Heap storage requires explicitly boxed values.

Now that I've described what a stack is as an abstract data structure, and how it arises when describing the theory of programming languages, I'm finally read to discuss how it works in the implementation of a programming language. Here, I'm going to describe how most implementations of most programming languages work when compiled to native code. (Languages compiled to byte code are typically fairly similar, but may be a bit further from this simplified description.) It's possible to do things differently, but unusual. I'm also going to keep things simple and not go into details that aren't important to understand the basic concept, such as registers, function parameters, return values, block scope, etc.

The typical way to implement a function call stack is to store the return addresses and the local (unboxed) storage for its variables in a single memory area. This specific method of implementing the stack abstract data structure is also called a “stack”. The stack of memory management for function calls works this way:

There's an array of memory which is reserved for the stack.
Pushing means copying a value to the top of the stack and incrementing the stack pointer, which is an index into the array of memory.
Popping means reading the value at the top of the stack, then decrementing the stack pointer.
To call a function, push the current value of the instruction pointer, then push enough storage for the function's local variables. The set of things pushed at this stage constitute a stack frame.
To return from a function, pop the stack frame and jump to the return address.

As long as a function call is in progress, its variables are in its stack frame. To access them, you need to know their address. To access a variable of the current function, all you need to know is its position in the stack frame. And the address of the stack frame of the current function is the top of the stack minus the frame size. So for example, let's imagine a simple (unoptimized) compiler for a simple programming language and the following program fragment in a function:

variable a = 22;
variable b = 33;
variable c = 2 * a;

This is compiled as:
* Allocate a frame with room for three variables.
* Write 22 to the address sp - 3 where sp is the stack pointer. (For simplicity, in this example, I assume that all variables have the size 1. Having differently-sized variables just requires keeping track of their sizes and doing additions at compile time.)
* Write 33 to the address sp - 2.
* Read a value from the address sp - 3, multiply the value by 2, and write the result to the address sp - 1.

As you can see, accessing a variable doesn't require popping to it. This is because computer memory itself is not a stack, but random-access memory. The stack that contains the local variables is a stack only because it grows and shrinks according to a stack pattern, not because it's impossible to access elements that are not at the top.

Accessing a variable of a function which isn't the current one doesn't require popping to it either. It does require knowing the address of that variable. If a variable has access to another function's variable, this can be either because the variable was passed as a parameter, or because the current function has access to a reference (pointer) to that variable. In either case, what happens under the hood is that the address of the variable is stored somewhere where the called function can access it.


What will be the time complexity of this function (C++) and why?

How to solve the polynomial: Clearly it's less than n * n * log (n) = O (n^2 log n). And clearly it is more than (n/2) * (n/2) * log (n/2) = O (n^2 log n). So it's n^2 log n.

However, your assumption that the sort is O (n log n) is not justified. Each time except the first you are sorting an array that is already sorted with the exception of the first array element. Many sort implementations will sort that kind of array in O (n), so the total time may be just O (n^2).


Generating uniformly distributed random numbers using a coin

What you're looking for is based on Rejection sampling or the accept-reject method (note that the Wiki page is a bit technical).

This method is useful in these kinds of situations: you want to pick some random object from a set (a random integer in the set $[a,b]$ in your case), but you don't know how to do that, but you can pick some random object from a larger set containing the first set (in your case, $[a, 2^k + a]$ for some $k$ such that $2^k + a \ge b$; this corresponds to $k$ coin flips).

In such a scenario, you just keep picking elements from the bigger set until you randomly pick an element in the smaller set. If your smaller set is big enough compared to your larger set (in your case, $[a, 2^k + a]$ contains at most twice as many integers as $[a,b]$, which is good enough), this is efficient.

An alternative example: suppose you want to pick a random point inside a circle with radius 1. Now, it isn't really easy to come up with a direct method for this. We turn to the accept-reject method: we sample points in a 1x1 square encompassing the circle, and test if the number we draw lies inside the circle.


The flow defined by you, satisfies both the constraints: a) conservation of flow at each vertex -- by the definition of balanced network and b) the capacity constraint because $f_{e} = c_{e}$ for every $e \in E$. Therefore, it is a valid flow.

It is a max-flow because it is sending the flow of value which is equal to the capacity of the cut $C$ defined as: $\{s\}$ and $V \setminus \{s\}$, i.e. max-flow = $\sum_{(s,u) \in E} c(u,v)$ since there is no incoming edge to $s$. Note that any flow can not exceed the capacity of this cut. This fact follows from the min-cut max-flow theorem. i.e., max-flow $=$ min capacity of an $s$-$t$ cut $\leq$ capacity of cut $C$. Therefore, what we have is a max-flow.


If you have a smallest grammar approximation, do you immediately have a CFG inference algorithm?

This is extremely optimistic.

The first problem you face is that an approximate smallest grammar will at best help you find strings which occur frequently. It won't distinguish keywords from names, and it won't isolate words. (Note for reference that Lempel-Ziv has a good approximation ratio. Charikar, Lehman, Liu, Panigrahy, Prabhakaran, Sahai, & Shelat (2005) The smallest grammar problem, Information Theory, IEEE Transactions on, 51(7), 2554-2576).

The second, related, problem you face is tokenisation. Programming language grammars deal in tokens, not in characters. Just the issue of tabs vs spaces in the samples is likely to mess things up. This might be finessed by making assumptions about tokenisation and then finding approximate smallest grammars over the language of tokens, but be prepared for nasty surprises. E.g. string literals in C# are definitely non-trivial, and you might not have many instances of @-strings from which to infer.

The third problem is that some languages (particularly those designed for code-golf) have unusual tokenisation and so little grammar that the tokenisation is where the real difficulty lies. E.g. identifying the tokenisation of CJam operators is going to be hard. You might do slightly better if instead of working from a grammar per sample you concatenate the samples, separated by a token which doesn't occur in any sample, and then find an approximate shortest grammar for that super-sample. At least that way you might have sufficiently many occurrences of the more common multi-character tokens to pick them out as symbols.


Efficient algorithm to decide if a location is reachable

The problem you're trying to solve is exactly graph connectivity. You don't necessarily need to construct the graph explicitly but this is a graph problem.

By "you don't necessarily need to construct the graph explicitly", I mean that you don't necessarily need to create any new data structures.  Every time your graph algorithm says "vertex", you can think "co-ordinates" and every time it says "neighbour" or "adjacent" or "edge", you can think of the squares above, below, to the left and to the right that contain 0.


Determining set of states that satisfy a CTL formulae

The semantics of the "Until" operator allows for the eventuality to be satisfied immediately. That is, $pUq$ holds both in the computation $ppppq$, but also in $q$.

Thus, in your formula, the eventuality is satisfied immediately in states $s_1,s_3$, and satisfied within 1 step in $s_2$. But all of them satisfy it.


NFA accepting $L=\{wbbav \;|\; w \in \{a,b\}^*, v \in \{a,b\}^+, v\; has\; suffix\; a\}$

I will address your second question, namely, whether there is an NFA with fewer states. The appropriate technique here is fooling set:

  Let $L$ be a language, and let $x_1,\ldots,x_n,y_1,\ldots,y_n$ be words such that $x_iy_i \in L$ but for every $i \neq j$, either $x_iy_j \notin L$ or $x_jy_i \notin L$. Then every NFA for $L$ contains at least $n$ states.

(The proof is a simple exercise.)

In our case, we take
$$
\begin{array}{c|cc}
i & x_i & y_i \\\hline
1 & bbaa & \epsilon \\
2 & bba & a \\
3 & bb & aa \\
4 & b & aaa \\
5 & \epsilon & bbaa
\end{array}
$$
For all $i$ we have $x_iy_i = bbaa \in L$. Conversely, if $i < j$ then $|x_jy_i| < 4$ and so $x_jy_i \notin L$.

In fact, we have proven the following more general result:

  If the minimal length of a word in $L$ is $\ell$, then every NFA for $L$ contains at least $\ell+1$ states.


If $m \leq a \log m + b$, why does $m = O(\max\{a \log a, b\})$?

$m \leq a \log m + b$ has no asymptotic behavior. This is because regardless of constants $a, b$, the left hand side grows faster than the right side, leaving only a finite range where $m$ is valid.

It is likely what was meant is $m \leq a \log a + b$. In this case we have that $m$ is bounded by something, so $m = O(a \log a + b)$. If you have that $O(x + y) = O(\max(x, y))$, then the question is solved.

But why is $O(x + y) = O(\max(x, y))$ true? With big-$O$ notation we are interested in the asymptotically fastest growing part. We ignore constant factors. Now check three cases (in the limit):

$$x < y \rightarrow O(x + y) = O(y)$$
$$x > y \rightarrow O(x + y) = O(x)$$
$$x = y \rightarrow O(x + y) = O(x + x) = O(2x) = O(x)$$

Since our choice for $x = y$ doesn't matter, we can see that choosing the minimum gives us the right asymptotic behavior.


Is the number of NP-complete problems finite?

As in the comment, consider the collection of problems $N$-SAT (Is $\phi$, a logical formula in $N$-CNF, satisfiable?). Or $N$-coloring of graphs, for $N \ge 3$ (Can the graph be colored with $N$ colors?). Many NP-complete problems have some parameter (Is there a clique of size $k$ in the graph? Has the digraph a feedback vertex set of size $k$?).


If someone was designing a computer language, why would they require static members to be defined outside the class?

Such language design solution makes sense, because class body is basically a declaration, which normally has to be in the header file. All definitions has to appear in cpp files, where class instances are actually used. If you allow static members to be defined inside class body, then you mix declarations with definitions. So I would require this to make separation between declarations and definitions clear.

In terms of this separation it is fine to initialise static const class members inside class body. Basically, you are defining some constant and it could be equivalently done with some #define directive.

It doesn't seem that this restriction is due to the limits of the language or a compiler. Java doesn't have this restriction and allows definitions inside the body of a class for any static data member (not const only).

Update: C++11 relaxes the restriction and supports non-static member in-class initialisation. Static members still have to be defined outside.


What Exactly is "Improvement" in Seed AI?

Improves itself by recursively rewriting its own source code without human intervention.

A machine learning technique that has some of the properties of a Seed AI is Meta Genetic Programming.

With Genetic Programming (GP) the system automatically writes code to solve a predefined task. GP evolves computer programs according to a natural evolution paradigm, using various operators and parameters.

Meta-GP allows simultaneous evolution of operators and parameters along with the population of programs.

Of course one can imagine multiple meta-levels in an evolutionary computation system: more levels of populations acting on each other and/or populations that act upon themselves.

It's worth noting that there can be a Free Lunch for Meta-GP / Hyper-Heuristics, but these techniques:

introduce extra computational cost, which have to be weighed against potential advantages;
seem very sensitive to biases in the syntax from which the operators are generated and thus less robust.

Anyway it's an open research field.

  How do you define "improve"?

Usually GP has an objective function (fitness function) to translate a desired behaviour.

Writing these fitness functions is a formidable task and it happens than your GP system optimizes for something other than it was intended for (may it happen for a Seed-AI-system?)

It's not clear if there is a way of doing without defining an objective function.

You can try to mimic Nature using a local, distributed, asynchronous form of competition or, according to the idea that "to achieve your highest goals, you must be willing to abandon them", applying Novelty Search,

but often fitness is still there (although behind the scene).


How can I quantify the number of swaps required for insertion sort?

It is a classic exercise to relate the running time of insertion sort to the number of inversions in the input. An inversion is a pair of indices $i < j$ such that $A[i] > A[j]$. The number of comparisons made by insertion sort when there are $I$ inversions is always between $I$ and $I+n-1$.


Prove that at least as many edges as vertices implies a cycle

Graph has a cycle on $k$ vertices implies that those vertices are connected with $k$ edges. Also, the graph is connected so $p-k$ vertices which left should be connected to the cycle, that means extra $p-k$ edges (distinct end points). Totally the graph has more($\geq$) than $p$ edges.


We say that a bound $f(n) = O(g(n))$ is tight if in fact $f(n) = \Theta(g(n))$, that is, if also $g(n) = O(f(n))$. So $2n^2 = O(n^2)$ is tight since $n^2 = O(2n^2)$, whereas $2n = O(n^2)$ is not tight since $n^2 \neq O(2n)$.

As you mention in your question, if $f(n) = o(g(n))$ then the bound $f(n) = O(g(n))$ is not asymptotically tight. However, there is a third option: it could be that $f(n) = O(g(n))$, $f(n) \neq o(g(n))$, and yet the bound $f(n) = O(g(n))$ is not asymptotically tight. An example is $f(n) = n|\sin n|$ and $g(n) = n$.

One could also define $f(n) = O(g(n))$ to be tight if $f(n) \neq o(g(n))$. In that case the "third option" is that $f(n) = O(g(n))$ is asymptotically tight although $f(n) \neq \Theta(g(n))$.


I don't think closure property implies decidability. Consider r.e. languages and intersection. R.e. languages are closed under intersection, e.g., if $L_1$ and $L_2$ are r.e. languages then $L_1 \cap L_2$ is also r.e. but may be undecidable.

On the other hands, CFLs are not closed under intersection. However, a language which is intersection of two CFLs is not CF but may be decidable. For example $L_1=\{a^ib^ia^j |i,j \geq 1 \}$, $L_2=\{a^ib^ja^j |i,j \geq 1 \}$ are both CF, however $L_1 \cap L_2 = \{ a^ib^ic^i | i,j \geq 1\}$ is not CF, but it is still decidable.


Is this book's definition of phrase correct?

To be a phrase is to be reducible to a single non-terminal. What you call a definition of phrase is actually the definition of what it is to be a phrase of a sentential form.

$\beta$ is a phrase of $\alpha_{1}A\alpha_{2}$, because it will be reduced to $A$. There are (obviously) phrases in sentential forms consisting entirely of terminals, i.e., sequences of symbols that will be reduced to a single non-terminal. They are not phrases of that sentential form, though.

A handle is the simple phrase of the sentential form that will be the result of the reduction to be made immediately, at some point. $\beta$ exists as a phrase, because it will be reduced to $A$. A bottom-up parser will usually reduce first its leftmost simple phrase, which will then be the handle of the resulting sentential form.

Definitions are not arbitrary, they serve a purpose.


Can Java be accurately described as statically and dynamically typed?

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


So I have to find a manipulation of $p$ such that I only have even numbers as solution.

Not so. You have to find a manipulation of $p$ such that if you can find a solution / all the solutions of the manipulated $p'$ in even numbers, then you can find a solution / all the solutions of $p$. That's a very different problem.


What would be the appropriate learning path given these circumstances?

A project I would recommend is the NandToTetris Project. It takes you from understanding the basic logic gates through VonNeumann architecture to how Operating Systems work.


"Applicative order" and "Normal order" in lambda-calculus

The term you are reducing is $(K_y \Omega)$ where $K_y$ is the constant function $\lambda x. y$ (it always returns $y$, ignoring its argument) and $\Omega = (\lambda x. (x \, x) \: \lambda x. (x \, x))$ is a non-terminating term. In some sense $\Omega$ is the ultimate non-terminating term: it beta-reduces to itself, i.e. $\Omega \to \Omega$. (Make sure to work it out on paper at least once in your life.)

Applicative order reduction must reduce the argument of the function to a normal form, before it can evaluate the top-level redex. Since the argument $\Omega$ has no normal form, applicative order reduction loops infinitely. More generally, for any term $M$, $M \Omega \to M \Omega$, and this is the reduction chosen by the applicative order strategy.

Normal order reduction starts by reducing the top-level redex (because the function $K_y$ is already in normal form). Since $K_y$ ignores its argument, $(K_y \Omega) \to y$ in one step. More generally, $K_y N \to y$ for any term $N$, and this is the reduction chosen by the normal order strategy.

This case illustrates a more general phenomenon: applicative order reduction only ever finds a normal form if the term is strongly normalizing, whereas normal order reduction always finds the normal form if there is one. This happens because applicative order always evaluates fully arguments first, and so misses the opportunity for an argument to turn out to be unused; whereas normal order evaluates arguments as late as possible, and so always wins if the argument turns out to be unused.

(The flip side is that applicative order tends to be faster in practice, because it's relatively rare for an argument to be unused; whereas it's common for an argument to be used multiple times, and under applicative order the argument is only evaluated once. Normal order evaluates the argument as often as it's used, be it 0, 1 or many times.)


What kind of recurrence relations has p < 0?

As Rick Decker mentions, in this context $\log^p n = (\log n)^p$, and so $p$ can be an arbitrary real number. If you wanted to denote composition, you would use $\log^{(p)} n$ (which in other contexts signifies the $p$th derivative!). In that case, when $p$ is a negative integer, you just need to use the inverse of $\log$, namely $\exp$:
$$
\begin{align*}
\log^{(2)} x &= \log\log x \\
\log^{(1)} x &= \log x \\
\log^{(0)} x &= x \\
\log^{(-1)} x &= e^x \\
\log^{(-2)} x &= e^{e^x}
\end{align*}
$$
This definition ensures that $\log^{(a)} \log^{(b)} x = \log^{(a+b)} x$ for all integers $a,b$. The natural domain of this definition is integer $p$, though it can probably be extended for fractional $p$ in such a way that the equation above still holds.


What data structure to use for large scale DHCP server

A good data structure for IPv4 translation is a 256-way trie, this means any lookup always requires exactly 4 memory accesses, and shared prefixes will be hot in cache.
You can do the same for IPv6 but implementing a unique suffix check (instead of always expanding trie nodes) is probably worth it.


Language of all strings that has exactly 1 triple b

It seems you are almost there.  You just need to care substrings with $abb$. One possible way is
$R.E = (a^{*} (ba)^*(bba)^*)^*bbb(a^*(ab)^*(abb)^*)^*$

Note that I came upon this regular expression from the $FM$ of language you described. So, another way to find $R.E$ is from $FM$ directly.


foresightful acceleration and decelerations

I think an approach that will work is to "work backwards" through the path, keeping track of the maximum velocity that can be used at that point (subject to the restrictions on acceleration), then "work forwards" along the path, assigning a velocity at each point (subject to the restrictions on acceleration).
Represent the path as a sequence of evenly spaced points $P_1,\dots,P_n$, i.e., $P_1$ is the start of the path, $P_n$ is the end of the path, and $\|P_{i+1}-P_i\|_2$ is the same for all $i$.  At each point $P_i$, you know the direction $D_i$ the car will be heading: $D_i$ is a unit-length vector that is tangent to the path at that point, so we can approximate $D_i = (P_{i+1}-P_{i-1})/\|P_{i+1}-P_{i-1}\|_2$, using vector arithmetic.  I'll describe an algorithm to compute speeds $s_1,\dots,s_n$ so that $s_i$ represents the speed of the car at point $P_i$, and so that the acceleration constraints are satisfied.  Then the car's velocity vector at point $V_i$ will be $V_i = s_i D_i$.
What constraints do the acceleration constraints impose on the $s_i$?  Well, I'll assume your goal is to impose an upper bound on the maximum acceleration allowed: in particular, I'll assume we have a constant threshold $c$ and we require that the acceleration vector $A_i$ satisfies $\|A_i\|_2 \le c$ at every point.  Notice $$A_i = {V_{i+1} - V_i \over \|V_i\|_2/\|P_{i+1}-P_i\|},$$ so the constraint $\|A_i\|_2 \le c$ becomes
$$\|s_{i+1} D_{i+1} - s_i D_i\|_2 \le c s_i / \|P_{i+1}-P_i\|.$$
Given $s_{i+1},D_i,D_{i+1}$, we can obtain an upper bound on the maximum allowable $s_i$ that is consistent with this constraint, as the constraint is equivalent to
$$\|s_{i+1} D_{i+1} - s_i D_i\|_2^2 - c' s_i^2 \le 0,$$
where $c' = c \|P_{i+1}-P_i\|$ is a known constant. The left-hand side of that is a quadratic function in $s_i$, so you can efficiently compute an upper bound on $s_i$ by solving a quadratic equation.  Moreover, given an upper bound on $s_{i+1}$, we can obtain an upper bound on $s_i$ by replacing $s_{i+1}$ in the equation above with the upper bound and solving for the upper bound on $s_i$.
So, our strategy during the backwards pass will be: at each point $P_i$, we will compute an upper bound $u_i$ on the maximum speed $_i$ that the car can be permitted to have at that point.  In particular, we'll choose $u_i$ so we're assured that if the car has speed $u_i$ or less at $P_i$, then there is a way to complete the path so that from $P_i \ldots P_n$ the car satisfies all the constraints.  We've already described how to do this: given $u_{i+1}$ (an upper bound on $s_{i+1}$), we described above how to compute $u_i$ (the upper bound on $s_i$).  Thus, during the backwards pass, we will iterate through $i:=n,n-1,\dots,1$, setting at each step $u_i$ based on $u_{i+1}$.  At the end of the backwards pass, we have computed all of the $u_1,\dots,u_n$.
Next, we will do the forwards pass, to assign a speed at each point.  Iterate through the points in the order $i:=1,2,\dots,n$.  At each step, we'll compute $s_i$ based on $s_{i-1}$ and $u_i$.  In particular, the acceleration constraints impose a constraint on $s_i$: $\|s_{i} D_{i} - s_{i-1} D_{i-1}\|_2^2 \le c' s_i$.  We also have the constraint $s_i \le u_i$.  You can solve this to find the maximum possible value of $s_i$ (it involves solving a quadratic equation), and assigning $s_i$ this value.  Continue forward along the path, until you have assigned speeds $s_1,\dots,s_n$ for the entire path.
The result will be a valid plan for how to traverse the path.  In particular, at point $P_i$, the car will be travelling at speed $s_i$.  While at point $P_i$, you will accelerate or decelerate the car so that by point $P_{i+1}$ it is travelling at speed $s_{i+1}$.  This can be done by using the gas pedal or brake pedal to accelerate by $A_i \cdot D_i$, where $A_i = s_{i+1} D_{i+1} - s_i D_i$ (this will ensure acceleration in the $D_i$ direction of the acceleration vector $A_i$), using the steering to stay on the road (this will ensure acceleration in the direction perpendicular to $D_i$ to stay on the road).
This solution assigns the maximum possible speed at each point, and thereby traverses through the path in the fastest way possible, while respecting the limits on acceleration at every point along the path.


Forget about strings meaning anything. For any symbol $a$ and natural number $n$, $a^n$ is the string made from $n$ copies of $a$. So $a^1=a$, $a^2=aa$, $a^5=aaaaa$ and $a^0$ is the empty string, usually written as $\varepsilon$ or $\lambda$.

The set $\{1^n\mid n\in\mathbb{Z}\}$ isn't well-defined (did Sipser really write that?), since $-1\in\mathbb{Z}$ but $1^{-1}$ doesn't make sense: what would $-1$ copies of the symbol $1$ look like?

However, the set $\{1^n\mid n\in\mathbb{N}\}$ is just $\{1^0, 1^1, 1^2, 1^3, \dots\}$, i.e., $\{\varepsilon, 1, 11, 111, \dots\}$ (I'm considering zero to be a natural number; delete $\varepsilon$ if you think that one is the first natural number). Now, strings such as $111$ can be interpreted as numbers written out in some base (unary, binary, decimal, whatever). But the definition is just giving you a set of strings.


Dijkstra's algorithm to compute shortest paths using k edges?

If the graph has no negative edges, the problem can be solved in $O(k \cdot (|V|+|E|) \lg |E|)$ time using Dijkstra's algorithm combined with a product construction.  We construct a new graph $G'=(V',E')$ with vertex set $V' = V \times \{0,1,2,\dots,k\}$ and edge set

$$E' = \{((v,i), (w,i+1)) : (v, w) \in E\}.$$

In other words, for each edge $v \to w$ in $G$, we have edge $(v,i) \to (w,i+1)$ for all $i$ in $G'$.

Now use Dijkstra's algorithm to find the shortest path in $G'$ from $(s,0)$ to a vertex of the form $(t,i)$ where $i \le k$.  This will be the shortest path in $G$ that uses at most $k$ edges.


Language of TMs such that one state is visited most often

After a deleted (wrong) answer I thought  about the following to prove that $L$ is RE for single tape Turing machines.

As you said in the question, the problem is "recognizing" $M \in L$ that doesn't halt.

Note that a non-halting TM $M \in L$ not necessarily must expand the tape; for example:

q,[ -> q,[,R
q,a -> q,b,R
q,] -> q,],L
q,b -> q,a,L
causes an endless ping-pong in the same state q
...[aaaaa]....
   ^head

Also note that a non-halting TM $M \in L$ can expand the tape without changing its state; for example:

q,[ -> q,[,R
q,a -> q,b,R
q,B -> q,b,L
q,b -> q,a,L
causes an endless expanding loop:
...[aaaaaBB...

But for both expanding and non-expanding cases, we must have that the Turing machine $M$ must continue forever in the same state otherwise it doesn't belong to $L$ (cardinality constraint).

But the halting problem for one-state one-tape Turing machine, on a blank tape except for a finite number of cells, is decidable. See for example Gabor T. Herman: The uniform halting problem for generalized one-state turing machines. Information and Control; Volume 15, Issue 4, October 1969, Pages 353-367):

-----
Introduction: The uniform halting problem (UH) can be stated as follows: Give a decision procedure which for any given TM will decide whether or not it has an immortal instantaneous description (ID). An ID is called immortal if it has no terminal successor.
... we assume that in an ID the tape must be blank except for some finite number of squares ...
In this paper we show the solvability of the UH for one-state TM's ...
-----

So, to enumerate the $M_i \in L$ start a dovetailed simulation of $M_1,M_2,M_3,....$.

if $M_i$ halts at steps $n$  then just count the states visited and outputs $M_i$ if there is a most visited state;
otherwise, if $M_i$ doesn't halt at step $n$, and it is in state $q$; decide if the corresponding one-state TM halts or not. If it doesn't halt then $M$ belongs to $L$;...
... otherwise continue the dovetailed simulation (if it halts it will be detected at a later step)


How are useless states created NFA to DFA

Below a nondeterministic automaton for the language of all strings where the one-but-last letter is an $a$. If we make it determinsitic using the standard construction half of the states will be unreachable.
You ask, why does this happen? Look at the initial state $0$ of the original automaton. It has a loop for both $a$ and $b$. That means that in the powerset construction all next states will always contain state $0$ because the deterministic automaton collects the states of all paths from the original automaton. As a consequence all states without $0$ are uneachable.

It is possible "by hand" to avoid those unreachable states, by a step by step construction. Only consider staes that are reached and continue form those to the next possible states. A kind of depth-first construction will work.


In a relational model, CC would be redundant, it's like saying that 1 = 1 * 1.
Using a real example, if A = person ID, B = person fingerprint, C = person name,
then you would say that "given a person ID and fingerprint, the name of a person is Bob, Bob is the name of the person".
Thus, I would argue that AB -> CC and AB -> C are equivalent, and the composition AB -> CC is not necessary.

given both A -> C and B -> C, then If you know did a search for "Bob" in the database, you would get both results for person ID's and person fingerprints. If fingerprints are stored together with person ID's, this means that your search result has one redundant entry for every result. Therefore it is much better design to only have the relation A -> C or B -> C to reduce the number of lookups. If A and B are in seperate entities, however, you might want both relations.

If you only specify AB -> C, you would not be able to use A -> C or B -> C, which are both true. Therefore you should not put this statement alone. However, if A -> B and B -> A, it might be valid, but usually inefficient. Now, to find AB given C (searching for all relations that match "Bob"), you need to lookup both person ID and person fingerprint, and match these two together (checking if A -> B or B -> A). It is faster to just check one attribute (look for only A or B, not both).


It turns out the definition is straightforward as seen in [1]. And as an example, exponentiation is not definable in simply-type $\lambda$-calculus.

  The class of extended polynomials is the smallest class of func- tions
  over N which contains:

  the constant functions: 0 and 1,
  projections,
  addition,
  multiplication,
  the function ifzero(n, m, p) = if n = 0 then m else p

Definable functions in the simply typed lambda-calculus by M. Zakrzewski (2007)


The most frequent integer value from set of intervals

It seems to me that the answer to your question will have a technique similar to this - https://stackoverflow.com/a/9676296/477522


Does a reduction from sorting imply an $\Omega(n \log n)$ time bound?

It's not a valid argument.   What it does prove is that any comparison-based algorithm for Problem X must use at least $\Omega(n \log n)$ comparisons.  (There is a known algorithm for integer sorting whose running time is $O(n \sqrt{\log \log n})$, in some models of computation, but it is not a purely comparison-based algorithm; see here.)


How do we define a tree in a directed graph?

Sometime there isn't a completely agreed upon meaning of terms, it is more useful to look at the context to see which definition is appropriate.

In this case, instead of searching for definition of general directed tree, it is better to look for directed steiner tree.

A quick search pulled up this paper which has this diagram showing an example of directed steiner tree:

While not explicitly defined, it coincides with my intuition of what a default directed tree should look like --- A directed graph with exactly one directed path from a distinguished root vertex to any other vertex in the graph (tree).


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

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


Why does restricting size of input for NP complete problem imply a runtime of O(1)?

If the input size is limited, then you can calculate the solutions to all problems. This will take a very, very, very long time. But once these solutions have been calculated, you can just lookup the solution of any problem in your list of solutions.

Even worse: Look at the definition of Big-O. The claim is that there is a constant $c > 0$, and an integer $N_0 > 0$ such that for every problem with a size $N > N_0$, the problem can be solved in less than $c * 1$ steps. If you restrict SAT to $N ≤ 1000$, then this is trivially true with $c = 1$ and $N_0 = 1001$. There are no problems with a size > 1000, therefore all the (nonexisting) problems with a size ≥ 1001 can be solved in one step.


Longest common substring many strings to one

Let's assume you have already built suffix tree for string $S$. Then for any string $T$ you can find $\mathtt{LCS}(S, T)$ in $\mathcal{O}(|T|)$ time, $\mathcal{O}(1)$ space, and read-only access to the suffix tree.

Here's pseudocode that finds $M$ - location in the suffix tree (edge plus position on that edge) that corresponds to $\mathtt{LCS}(S, T)$:

M := C := ST.root

for i := 1..|T| do
  while C.canNotExtendWith(T[i]) do
    C := C.contract()

  C := C.extendWith(T[i])

  if C.length > M.length then
    M := C

Here:

ST.root is the suffix tree root
C.canNotExtendWith(x) returns true if you can't follow given letter $x$ from location $C$
If $C$ is a location of string $U$ in the tree, then C.extendWith(x) returns location of string $Ux$
If $C$ is a location of string $xU$, then C.contract() returns location of $U$ (i.e. follows the suffix link)
If $C$ is a location of string $U$, then C.length is $|U|$

Both correctness and $\mathcal{O}(|T|)$ time complexity follow from the Ukkonen's algorithm.

Hand-wavy explanation of the algorithm correctness:

If you can't extend the substring with single letter, there's no point in trying to extend it further
If you've already found a good candidate substring, there's no point in contracting it


Sorting a set of $n$ elements containing only $\log n$ unique elements

Your solution is almost complete. Try replacing the hash table with a comparable data structure, such as a balanced binary search tree. Since the tree will only contain at most $\log n$ elements, all the operations on the tree will take time $O(\log\log n)$, and the resulting algorithm will take time $O(n\log\log n)$.

Any comparison-based algorithm for your problem takes time $\Omega(n\log\log n)$. To see that, notice that there are roughly $(\log n)^n$ different possible relative orderings for your set (the actual number is a bit smaller, but not by much). Any comparison-based decision tree must therefore have depth $\Omega(\log [(\log n)^n]) = \Omega(n\log\log n)$.

If you allow more general algorithms, then you can improve the complexity to randomized $O(n)$ using a hash table, along the lines that you mentioned. Since you can afford a hash table of size $O(n)$ although the occupancy is only $\log n$, the probability that your algorithm exceeds its expected running time significantly will be very, very small.

It is also possible that under a suitable computation model, you can sort you list in deterministic $O(n)$ time. Some people consider this kind of algorithm cheating, though.


For the set of coins (2,3,11). $\frac{3}{2}<\frac{11}{3}$ so by your assumption we can be greedy here. Consider the value of 23. The greedy strategy would involve first taking 2 11 cent coins to give us 22 cents. Then there is nowhere left to go, we cant possibly get to 23 from here. We do have a solution though with $(0,4,1)$


Here is a simple grammar:
$$
\begin{align*}
& S \to aSb|U|V \\
& U \to aUa|T \\
& V \to bVb|T \\
& T \to bTa|\epsilon
\end{align*}
$$


How to find the Branch factor of 8 Puzzle

The relevance of the blank space is that a move is encoded by the transition of the blank space.  So for example, if the blank space is in the center we have 4 possible moves:

This is what the author is talking about when he says

  "2 from each corner for a total of 8 corner moves."

The blank space is what's in the corner. Here's one of the 4 possible corner positions:

As you can see, when the blank space is in the corner there are two possible transitions.

Continuing,

  "3 from center of each side for a total of 12"

There are 4 centers of a side and each has 3 possible transitions.

I hope this combined with Jeffrey's weighted average explanation answers the question.


Demonstration that EXP is closed under union complementation and concatenation

By definition $EXP = \bigcup_{k\in N}{DTIME\big(2^{n^k}\big)}$.

Let $L_1, L_2 \in EXP$. Then $L_1 \in DTIME\big(2^{n^m}\big)$ and $L_2 \in DTIME\big(2^{n^k}\big)$ for some $k,m \in N$.

So for a string $w$ checking $w \in L_1 \cup L_2$ takes $2^{n^m} + 2^{n^k}$ time which is $O(2^{n^l})$ where $l = max(m,k)$. So $L_1 \cup L_2 \in DTIME\big(2^{n^l}\big)$ and hence in $EXP$.

Let $w$ be a string of length $t$. Then checking $w \in L_1L_2$ takes $t(2^{n^m} + 2^{n^k})$ since for strings $u$ and $v$ such that $w=uv$ we check $w \in L_1$ and $v \in L_2$ $t+1$ times since there are $t$ different prefixes and suffixes of $w$. Assuming $l = max(m,k)$ we have $t2^{n^l}$ running time which is less than $2^t2^{n^l} = 2^{t + n^l}$ which belongs to $EXP$.

Finally, checking $w \in L_1$ takes $O(2^{n^m})$ times so the Turing machine halts with "no" if $w \in L_1$, with "yes" otherwise. Thus $\overline{L}_1^{} \in EXP$.


Why don't integer multiplication algorithms use lookup tables?

If you want to use lookup tables, and you have 4GB of memory, you'll only be able to use a lookup table with about $2^{32}$ entries or fewer, so you'll only be able to handle multiplication of numbers that are at most 16 bits long.  If you want to multiply larger numbers, you won't be able to use lookup tables for multiplication.  Typically we want to multiply numbers that are larger than that.  And when we do want to multiply small numbers, using the CPU's built-in multiply instruction is usually faster than using a lookup table.

So there is no size (that I'm aware of) where a lookup table is a good solution for multiplying two numbers.

Now you're thinking that maybe the numbers that are generated by FFT should be multiplied with lookup tables.  But those are just numbers, and as I said above, there is pretty much no situation where the fastest way to multiply two numbers is with a lookup table.  It doesn't matter how those numbers were generated -- whether by FFT or by any other process.

So I'd say the reason it doesn't have more attention is because it doesn't deserve attention; it seems unlikely to be faster or better than existing schemes.

Lookup tables are occasionally used in cryptographic code, where constant-time access is needed.  This is not because they are faster -- they're not; they're slower -- but because they have other properties that are beneficial.  I don't know of any specific examples, but it wouldn't surprise me to discover that someone had used a lookup table for multiplication in some constant-time cryptographic code.


Use subset of training data as prediction data

The most important thing is to avoid "testing on the training set".  If you trained a model on a set of 500 users and then evaluate how well it performs by testing it on some of those same users, you're committing the "testing on the training set" sin.  The consequences of doing that is that your evaluation results will be misleading: they will over-estimate the effectiveness of your model.

There are various standard methods to avoid this problem.  One method is to use a holdout set: you set aside, say, 67% of your data for training and the other 33% for testing.  You train a model on the first 70% (the training set), and then evaluate how well your model performs on the other 30% (the testing set).  This will then give you a reasonable, unbiased estimate of the performance of your machine learning model.  In practice, a test+train division is often not enough; for various reasons, you'll often want three sets, a training set, a validation set, and a testing set.  You can read more about that in standard resources.

Another reasonable method is to use cross-validation to estimate the effectiveness of your scheme.  Basically, this involves repeatedly dividing up the data, learning a model on one portion of the data and evaluating on another portion, and then averaging the results.  This is a reasonable alternative to dividing the data into train+validate+test sets, when you don't have a lot of labelled data -- as in your case.

These comments are all about how to build the model, select parameters for your model, and evaluate the model's performance (predict how effective it will be in practice).  Once you've done all that and settled on a model, then you can simply apply the model to new customers to predict their likelihood of cancelling their subscription.

Finally, one last comment: your approach assumes uniformity over time: i.e., that the factors that influence behavior in the past will continue to hold in the same way in the future.  This may or may not be realistic.  For instance, maybe today some people are more likely to cancel cable subscriptions because of the availability of Netflix/Hulu/etc. whereas ten years ago that wasn't as much of a factor.  In many areas, things can change over time.  Read about concept drift to learn more about that particular challenge.

If this didn't answer your question, edit the question to clarify in more detail what you are asking about.


Sum rule for Big-O with equal complexity-functions?

It depends on if some variables on dependent on another, or if they are given as parameters in the problem. For example, in many graph-related problems, $n$ can be the number of vertices, and $m$ can be the number of edges. In this case, $m$ can be as large as $O(n^2)$. So in the general case, say if we have an algorithm whose first phase runs in $O(n)$ and second phase runs in $O(m)$, we just add the two terms together and do not attempt to simplify --- the final runtime is $O(n+m)$.
In terms of several variables given as parameters that aren't necessarily related: eaving multiple variables inside the final equation is standard, e.g. I can say that multiplying an $m\times n$ matrix and an $n\times p$ matrix takes $O(mnp)$-time using schoolbook multiplication, or solving the knapsack problem takes $O(nt)$-time where $n$ is the number of items and $t$ is the target sum.
In special cases like planar graphs and other sparse graphs, we know that $m=O(n)$, so we can safely substitute $n$ in place of $m$ in the final running time for simplification.
As a digression, this illustrates why on sparse graphs (where $m=O(n)$) one would prefer to use Dijktra's in a loop for all-pairs shortest path (in contrast to a transitive-closure based algorithm like Floyd-Warshall); since now Dijkstra runs in $O(m \log n) = O(n \log n)$, the overall complexity for using Dijkstra's in a loop becomes $O(n^2 \log n)$, which is better than Floyd-Warshall. By contrast, note that Dijkstra's runs in $m \log n$ for the general case, which means on dense graphs where $m=O(n^2)$, it becomes less efficient than Floyd-Warshall in terms of worst-case running time.
In other cases, there can be variables aren't even polynomially bounded by a given parameter --- take the knapsack example above, where $t$ can be exponential in $n$.


Complexity of an algorithm with multiple inputs

[If I have time, I'll answer the rest of the question later.]

  I've also seen phrases such as 'cubic in $k$ and $n$'; what does this mean exactly?

It's vague, unfortunately, and you should avoid writing anything like this, ever.  It means at the very least, that the complexity depends somehow on $k^3$ and $n^3$ but I'm sure you'd already figured that out.  Beyond that, it's impossible to say much. It's unclear whether it's some function of $k^3+n^3$ or some function of $k^3n^3$ or something else.  It's also unclear whether they're talking about an upper bound or a lower bound: if I told you that a recipe needs a kilo of potatoes, you'd assume that was an upper bound, but if I told you that a restaurant needs kilos of potatoes, you'd assume a lower bound.


Where are file-information like "created" or "last edited" actually stored?

Information like "creation time" is called metadata.  The filesystem stores both the contents of the file and its associated metadata on the hard drive.  It has to -- if you reboot the computer, we need that information to persist, so it has to be stored somewhere that will survive reboots.  That place is the hard drive.

See https://en.wikipedia.org/wiki/File_system, How do Hard Drives Send and Recieve Data?, Reconstructing files from binary, Typical file structure, and a good operating system textbook to learn more about how filesystems work.


Knapsack problem, partition problem, or in general dynamic algorithm with negative numbers allowed

In the two examples you mention, the dynamic programming algorithms work just as well. Let's take partition as an example. The dynamic programming approach computes, for every $m$, the sums of all subsets of $\{w_1,\ldots,w_m\}$. This works just as well if negative numbers are allowed. The range of the table has to be modified accordingly, to account fo the largest possible positive and negative amounts. With knapsack it's similar, and I'll let you work out the details.


L = { , M is a DFA accepting all strings except finitely many

It is indeed decidable, but your solution is not quite correct.

To restate the problem, we're given an encoding $\langle M\rangle$ of a DFA $M$, and we want to decide whether accepts every possible string except a very small (finite) number of them. So for each DFA encoding in this language $L$, there's an associated $x_{M} \in \mathbb{N}$ (which we don't know) and $M$ only rejects $x_{M}$ strings.

So for example, a DFA $A$ that accepts everything (i.e. $\Sigma^{\ast}$) would be in $L$, because $x_{A} = 0$, which is definitely a finite number. Similarly if we have a DFA $B$ which rejects the string $a$, but accepts everything else, this would be in $L$ as $x_{B} = 1$, which is also finite.

Right, now to showing that this decidable for every DFA $M$. To do this we need to make a key observation, similar to what you were proposing, but sort of reversed; if a DFA rejects only finitely many strings, they must all have length smaller than $k-1$, where $k$ is the number of states. Why is this true? Suppose that it rejects a string with length greater than $k-1$, then to process this string the DFA must go around a cycle (either a loop or a longer path, or some combination thereof), but if it can go around the cycle once, it can do it twice, or three times, or any number of times. So if there's at least one long rejected string, there must be an infinite number of rejected strings.

Using this, we can see that if it rejects a string of length somewhere between $k$ and $2k$ (a single go around the cycle can use each state at most twice), then it must reject an infinite number of strings.

Finally we can get to our decider:

On input $\langle M \rangle$ where $M$ is a DFA:

One by one, enumerate all strings of length $k$ to $2k$.

Simulate $M$ on each string.
If $M$ rejects any tested string, reject.

If $M$ rejects no strings of length between $k$ and $2k$, accept.


Understanding Dijkstra's notation $f.x.y$

I think this would read as follows in modern notation (although  field-local variations are possible):

$$\forall x y. x < y \Rightarrow f(x,y) < f(y,x).$$

Read aloud: for all x and y, x is less than y implies that f of x and y
is less than f of y and x.

If you read the first sentence of the linked document, it says that square brackets represent universal quantification over $x$ and $y$. The second states that $f$ is a function. => is ASCII art for $\Rightarrow$ (logical implication).

The main problem here is missing context (and detective skills). This article refers to EWD878. Perhaps looking there would have helped. Indeed, looking at that article, you see notation slightly closer to what is used today (at least, by Haskell programmers: f.x.y becomes f\ x\ y).


Tree traversal with conditional summing values from nodes

This algorithm is simple conceptually, but the implementation is a bit much so I'll try to present it in a couple steps. First, an example.

Linked List Example

Consider the following linked list where rank and value are equivalent: $A = [1, 3, 5, 6, 4, 2, 0]$

We will create auxiliary array $S$ where $S[i]$ is the sum of the subtree (sub-linked list) rooted at node $i$. This will basically be a suffix sum array for our purposes. This takes $O(n)$ time to create and it would be: $S = [21, 20, 17, 12, 6, 2, 0]$.

We will now process the nodes in order, adding them to a stack $T$. We have one rule before adding a node, if the node value on the top of the stack is greater than the node we're adding, then we must pop it from the top of the stack. This will ensure that when we pop a node off the stack, the current node we're at will be the first node lesser than it. Let's say we're popping node $i$ and we're currently at node $j$, then we have the function we're interested in is simply $f(i) = S[i] - S[j]$. Let's run through this with our example:

Let A = [ 1,  3,  5,  6, 4, 2, 0]
Let S = [21, 20, 17, 12, 6, 2, 0] be the suffix sum array of A
Let T be the increasing order stack, initially empty.

1) T = []
2) T = [1]
3) T = [1, 3]
4) T = [1, 3, 5]
5) T = [1, 3, 5, 6]
6) T = [1, 3, 4] and set f(6) = 12 - 6 = 6, set f(5) = 17 - 6 = 11
7) T = [1, 2]    and set f(4) =  6 - 2 = 4, set f(3) = 20 - 2 = 18
8) T = [0]       and set f(2) =  2 - 0 = 2, set f(1) = 21 - 0 = 21
9) T = []        and set f(0) = 0

We can take $f$ to be our final answer array where $f = [21, 18, 11, 6, 4, 2, 0]$.

Problem with applying this to a Tree

You may notice a problem with applying this to a tree. We are destroying the information of $T$ when we finally get to a leaf node. So to remedy this, we will have to rebuild it in a way as we come back up the recursion stack. For this we will need to keep track of a few more things. First, we will need to know the depth at which a node resides. This is easy to calculate in a single traversal of the tree. Next, we will need to know the depth at which a node was removed from $T$. This is also easy to keep track of during the recursion. So let's move to the next section of the algorithm itself.

The Algorithm Approach

Let's define some things we need. I'll simply add them as pointers on the node itself and assume that our stack $T$ holds a reference to the nodes. For a node $V$ let the node have the following properties:

v.rank - rank of node $v$. (given)
v.value - value of node $v$. (given)
v.sum - the sum of the values of nodes in the subtree rooted at $v$ (precomputed).
v.depth - the depth of node $v$ where the root is at depth 0. (precomputed)
v.removal - the depth we are at when we remove node $v$ from $T$. This may be overwritten multiple times throughout the algorithm if $v$ has multiple children.
v.f - the function we're interested in computing (based on the definition in the question). Initially set v.f = v.sum, and we will subtract away subtrees where necessary.

For the sake of dealing with base cases, I will assume w.l.o.g. that leaf nodes will have a dummy node attached to them as a child with value 0 and rank less than that of all nodes in the tree.

So we have our stack $T$, we will also have another stack $R$ which will keep track of the order of the nodes we've removed from $T$. This will be necessary to rebuild $T$ on our way back up from recursion. Assume $T$ and $R$ are global variables.

def visit(v, d):
  // Where v is the node we're visiting, and d is the depth we're at.

  // Before recursion
  while top(T).rank > v.rank:
    u = pop(T)
    u.removal = d     // set depth of removal
    u.f = u.f - v.sum // remove sum of subtree rooted at v because it's lesser
    push(R, u)        // push it onto our removal stack R

  if v is not a dummy node:
    push(T, v)
    for each child u of v:
      visit(u, d + 1)

  // Build back up T, we use d - 1 because we're building it back up
  //   so that it is fixed for the level above (when recursion returns)
  while top(T).depth > d - 1:
    u = pop(T)        // we must remove nodes that are depth below our current

  while top(R).depth <= d - 1 and top(R).removal > d - 1:
    u = pop(R)
    push(T, u)

Example

Consider this tree (assume rank = value):

Let's work through the first few steps of this example explicitly:

d = 0 | v = 2 | T = [2]          | R = [] recurse on 4
d = 1 | v = 4 | T = [2, 4]       | R = [] recurse on 5
d = 2 | v = 5 | T = [2, 4, 5]    | R = [] recurse on 8
d = 3 | v = 8 | T = [2, 4, 5, 8] | R = [] recurse on 7
d = 4 | v = 7 | T = [2, 4, 5, 7] | R = [8] recurse on 0

set 8.f = 15 - 7 =  8 and 8.removal = 4

d = 5 | v = 0 | T = []           | R = [8, 7, 5, 4, 2]

set 7.f =  7 - 0 =  7 and 7.removal = 5
set 5.f = 24 - 0 = 24 and 5.removal = 5
set 4.f = 53 - 0 = 53 and 4.removal = 5
set 2.f = 55 - 0 = 55 and 2.removal = 5
build T back up and return

d = 4 | v = 7 | T = [2, 4, 5, 7] | R = [8]

build T back up and return

d = 3 | v = 8 | T = [2, 4, 5, 8] | R = []

build T back up and return

d = 2 | v = 5 | T = [2, 4, 5]    | R = [] recurse on 3
d = 3 | v = 3 | T = [2, 3]       | R = [5, 4] recurse on 1

set 5.f = 24 - 4 = 20 and 5.removal = 3
set 4.f = 53 - 4 = 49 and 4.removal = 3

d = 4 | v = 1 | T = [1]          | R = [5, 4, 3, 2] recurse on 0

set 5.f = 24 - 4 = 20 and 5.removal = 3
set 4.f = 53 - 4 = 49 and 4.removal = 3

...

I will not continue the rest cause it will take a while, but you can see at this point all nodes in the subtree rooted at 5 have been completely evaluated.

Analysis

This is where I'm having a bit of trouble. It is technically one traversal of the tree, but I am not sure if this is $O(n + m)$. There would need to be some argument about how many times a node can be pushed and popped onto $T$ and $R$.

Consider a path $p$ from root to leaf. Every node on this path will be popped and pushed from $T$ and $R$ a constant number of times (similar argument as the linked list). Every time a node $v$ forks into $k$ children, this will increase the number of times nodes on the path from root to $v$ will be pushed and popped by a factor of $k$. When we reach the leaf node, $T$ will be empty and $R$ will be full.

You can upper bound this by the following formula. Let $k$ be the total number of leaf nodes, let $d$ be the maximum depth of the tree. Then the runtime is $O(kd)$.

To put this into perspective, for a binary tree of depth $\log n$ and $n/2$ leaf nodes, this runs in $O(n \log n)$.


Well, kind of, but not really. A defining characteristic of a Turing machine is its current head position, where the head is reading and writing from the tape. These two tapes appear to be identical, but the tape head isn't in the same place. It depends on how you define "the same thing": the tapes themselves are the same, but the Turing machines' states are not.


Is it true that PAC is a subset of agnostic PAC?

The trivial implication is:

$\mathcal{C}\subseteq 2^\mathcal{X}$ is agnostic PAC learnable $\Rightarrow$ $\mathcal{C}$ is PAC learnable

Intuitively, being agnostic PAC learnable is a stronger condition, since you can, for all distributions on $\mathcal{X}\times\{-1,1\}$, get close to the optimal error (in particular, you can do so when the labels are forced to be consistent with some $c\in\mathcal{C}$).

To see this formally, suppose a concept class $\mathcal{H}\subseteq 2^{\mathcal{X}}$ is agnostic PAC learnable. This means that there exists an algorithm $A$, such that for all $\epsilon,\delta>0$ there exists $m\in\mathbb{N}$ such that for all distributions $\mathcal{D}$ over $\mathcal{X}\times\{-1,1\}$, and a set of labeled samples $(x_i,y_i)_{i=1}^{n\ge m}$ drawn from $\mathcal{D}$, $A$ outputs $h\in\mathcal{H}$ such that:

$err(h)\le err^*(\mathcal{D})+\epsilon$, with probability $\ge 1-\delta$, where $err^*(\mathcal{D})$ is the error rate of the optimal hypothesis relative to $\mathcal{D}$.

To show that $\mathcal{H}$ is PAC learnable, let $h\in\mathcal{H}$ be some target concept, and let $\mathcal{D}$ be any distribution over $\mathcal{X}$. Examine the distribution $\mathcal{D}'$ on $\mathcal{X}\times\{-1,1\}$ obtained by drawing $x\in\mathcal{X}$ according to $\mathcal{D}$, and taking the pair $\left(x,h(x)\right)$. Note that $err^*\left(\mathcal{D}'\right)=0$, which means there exists an algorithm $A$ which produces a hypothesis in $\mathcal{H}$ with small generalization error (you can complete the details yourself, this shows you that all you need to do is unfold the definitions).

The opposite implication (agnostic PAC learnability follows from PAC learnability) is also true, since they are both equivalent to $\mathcal{C}$ having a finite VC dimension, but this is much harder to show.


books on algorithms for beginners in Ruby or Python or C. Not too math heavy

To be honest, it doesn't really matter what languages you use to learn an algorithm (it's only the syntax that changes, the logic is the same).

However, if you want a Python specific one check out:

Python Algorithms: Mastering Basic Algorithms in the Python Language

A more generic one is by the O'Reilly series (they make wonderful books!):

Algorithms in a Nutshell

There are also a number of youtube tutorials, so check out this, although it is in Java, it is very good!


Complete proof of PAC learning of axis-aligned rectangles

Let $R_S, R_T$ denote the sample rectangle (smallest consistent rectangle) and the target rectangle correspondingly. Since $R_S\subseteq R_T$, $R(R_S)\le \mu\left(R_T\setminus R_S\right)$. The intuition behind taking strips of mass $\epsilon$ around the edges of $R_T$ is that you want to satisfy two conditions:

The strips, $r_1,...,r_4$ should have large enough mass so that with high probability $m(\epsilon)$ samples do not miss them (this would follow from a simple bound for a geometric random variable).

The strips should have small enough mass, so that if all were seen by the samples, then $R_T\setminus R_S\subseteq \bigcup\limits_i r_i$, where the latter union has small probability thus bounding $R(R_S)$.

Your question is settled by the geometric argument in the second point. If all strips were seen by the samples, then we can only err on points in the strips.


Best algorithm (Time Complexity) to find Minimum spanning tree of an complete, positive weighted, undirected, graph

Since it is a complete undirected graph, the number of edges are $\Theta(n^{2})$, where $n = |V|$. In order to find the MST, you must find the edge of minimum weight among all the given edges since it is always a part of the Minimum Spanning Tree. Since, the lower bound of finding the minimum among $N$ elements is $\Omega(N)$. Therefore, you can not do better than $\Omega(n^{2})$ if the graph is complete.


Is it axiomatic that the Time Hierarchy Theorem holds true in all relativized worlds?

The proof of the time hierarchy theorem relativizes. This means that all the steps remain true if all Turing machines are given access to the same oracle $O$ (for arbitrary $O$). This implies that the theorem itself remains true if all Turing machines are given access to the oracle $O$.

So yes, it is possible to prove that no oracles exist with respect to which the time hierarchy theorem fails.


Are there problems with complexity between $O(n^c/\log^b n)$ and $O(n^{c - \varepsilon})$?

The question is about upper bound (which is $O(n^{2013} / (\log n)^{2012})$) and lower bound (which is $O(n^{2012.9})$) – do they correspond to each other?

According to definitions of Big-O and Ω we have to find constants $c_1$, $c_2$, and $n_0$ such that for $n\geq n_0$ two following inequalities are true:

$$c_1 n^{2012.9} \leq T(n) \leq c_2 n^{2013} / (\log n)^{2012}.$$

If such constants exist, then the lower bound must be less than upper bound for sufficiently large $n$:

$$c_1 n^{2012.9} \leq c_2 n^{2013} / (\log n)^{2012}.$$

Let's simplify this a little:

$$c_1 (\log n)^{2012} \leq c_2 n^{0.1}.$$

Can we find $n_0$ such that this inequality is true when $n \geq n_0$? Yes, sure – the power function eventually wins over the logarithm function, so the answer is TRUE.


The one literal rule, usually known as the unit clause rule, state that if you have a unit clause (a clause containing only one literal) then you should set that literal to the value which satisfies the clause.

The pure literal rule states that if some variable appears only positively or only negatively in all clauses, then you can set that variable accordingly (true if it appears positively, false if it appears negatively).

You can apply the unit clause rule but not the pure literal rule in the formula $p \land (q \lor \lnot p)$. The result would be setting $p$ to true and simplifying the formula to $q$. Another application of the unit clause rule will set $q$ to true and will satisfy the formula.

You can apply the pure literal rule but not the unit clause rule in the formula $(p \lor q) \land (p \lor r)$. The result would be setting $p$ to true, and satisfying the formula.


Faster algorithm to search in a set of strings

You only need to read the strings in set $A$ and the characters in pattern $p$ once. You can store each character of $p$ in a hash table* for (expected) constant time lookup, and, then, perform a linear scan in $A$ to obtain the desired result. The running time of this solution is $O(n+m)$, where $n$ is the length (i.e., the total number of characters) of $A$ and $m$ is the length of $p$.

* A solution that is more space-efficient than the hash table (and guarantees constant time lookup) is to use a bit array $P$ to store pattern $p$. This array will be indexed by the ASCII values of all possible characters that you want to consider in your application; for instance, $P$ will have 26 index positions in the case of the English alphabet: one per distinct character. The $i$-th bit of $P$ will be set to $1$ if the $i$-th character appears in $p$, and to $0$ otherwise. Thus, you can scan $A$ in linear time and discard every string that contains at least one character $c$ such that $P[v_c]=0$, where $v_c$ is the ASCII value of $c$.


Is the Jacobian matrix calculation process correctly on this energy function?

That is not an equation to be solved; it is an objective function to be minimized.  They apparently describe how they optimize it in Section 3.3.3 of the paper.  I suggest trying to understand that section.


It works because the three cases you mention will remove every non-pure variable after some number of steps, but it is crucial that you also consider the recursive step, namely $\mbox{dpll}(\phi \land l) \lor \mbox{dpll}(\phi \land \neg l)$.

After a recursive step, you are guaranteed to have at least one unit clause, so the unit clause will be set to its value and hence all the variable will in the end be assigned a value.

I think your misunderstanding must arise from the recursive calls.  Observe that if you have any formula $\phi = ((a \lor b \lor c) \land \cdots)$, then $\mbox{choose-literal}(\phi)$ will return some unassigned variable, say $a$.  The recursive call will then be with $\phi \land a$ which will be $(a \lor b \lor c) \land \cdots) \land (a)$.  And then $\mbox{unit-literal}(\phi)$ will return $a$ and set it to true.  The other recursive call is equivalent, but with $\phi \land (\neg a)$ so $\mbox{unit-literal}(\phi)$ will still return $a$ and set $a$ to false.


For which level of PH is $\operatorname{VALID}$ complete

Just like SAT is NP-complete, $\overline{SAT}$ is coNP-complete. More generally, if $L$ is $\Sigma_k$-complete then $\overline{L}$ is $\Pi_k$-complete (and vice versa). You can prove this using the definitions.


Why we cannot prove that a computable function is total?

You misunderstand soundness and completeness of logic. You think that it says:

  A statement is true if, and only if, it is provable.

But it really says:

  A statement is true in every model if, and only if, it is provable.

It can happen that there is a model in which a statement is true but not provable. What if you live in such a model? Then it could happen that in the model in which you live there is a total function $f$, but there is no proof that $f$ is total.

Here is a precise mathematical reason why your thinking does not work. I am going to show that, whatever formal system you are using (so long as it is a reasonable one), there is a total function which your formal system does not prove to be total.

You do proofs in some formal system $T$ (for instance, $T$ could be first-order logic and Zermelo-Fraenkel set theory) whose axioms are computably enumerable (or else you're a mystic guru). Let us also assume that $T$ contains arithmetic, and that $T$ is consistent (or else you're mad).

Define the following function f

def f(n):
    if n encodes a proof of 0 = 1 in formal system T:
        while True: pass
    else:
        return 0

Observe that f is total if, and only if, $T$ is consistent:

if $T$ is consistent then it does not prove $0 = 1$, hence f never enters the infinite while loop.
if f is total, then it never enters the infinite while loop, therefore no $n$ encodes a proof of $0 = 1$ in $T$, therefore there is no proof of $0 = 1$ in $T$, which means that $T$ is consistent.

Because $T$ is consistent, f is total.

But $T$ does not prove that f is total: if it did, then it would prove that, for every $n$, $n$ does not encode a proof of $0 = 1$, but this would imply that $T$ proves its own consistency, which it cannot by Gödel's incompleteness theorem.


Why are states called locations in Timed Automata?

It is mainly a matter of avoiding ambiguity.

At any moment in a Timed Automaton (TA), available transitions depend on the current location and the current clock valuation.
Thus, the current state is the combination of the current control state (or location) and the current clock valuation.

If you see a Finite State Automaton as a TA with $0$ clocks, only one clock valuation is possible, and it is the same for every states.
The clock valuation is thus irrelevant, and the current state is entirely determined by the current location.
To simplify the vocabulary, we identify both terms.

The word "location" is often used because it is hard to mistake it for "state".
But it is not uncommon to see "discrete state" instead of "location", and "extended state" instead of "state".


Proving a language is not context free using the Pumping Lemma

You can try to take a different value for $i$ in that case. It is not necessary to fix one $i$, but the $i$ chosen may depend on the chosen partition $xyuvz$. Will $7p+ib$ always divide $21p+ia$?


how to find upper bound and lower bound of quadratic equation

Since $n \geq 1$ (since $n$ is the input length), we have
$$
20n^2 \leq 20n^2 + 11n + 1 \leq (20+11+1)n^2 = 32n^2.
$$
Put differently, for all $n \geq 1$, the function $f(n) = 20n^2 + 11n + 1$ is bounded from below by $20n^2$ and from above by $32n^2$. This shows that $f(n) = \Theta(n^2)$.

Note also that when $n$ is large, $f(n)$ gets very close to $20n^2$. Indeed,
$$
1 \leq \frac{f(n)}{20n^2} \leq 1 + O\left(\frac{1}{n}\right).
$$