Amortized analysis for disjoint sets' find-set(x) function (from CLRS) I start off by apologizing for the fact that I don't really know how to use latex/markdown. My question, however, is directly from the Introduction To Algorithms book by Cormen et al. The topic discusses about the time analysis for disjoint set operations using forests with union-by-rank and path-compression heuristics. In particular, I am stuck at Lemma 21.13 (580) for which the "find-set(x)" subroutine is claimed to run at O(alpha(n)) time where alpha(n) is the inverse Ackermann function. I cannot arrive to the conclusion that there is at most alpha(n)+2 nodes in the find path that satisfy some specific conditions. This node count comes from the maximum number of nodes where the level(x) is constant across the find path if my interpretation is correct. I assume it is an obvious outcome of previously proven lemmas. Unfortunately, I am not so bright to validate this result.

Of course, without the details about the potential function, this question cannot be answered. There is a big problem, besides that I cannot elegantly type it out in latex. There is a ton of lemmas that logically weave this proof. So, I assume that you have the text with you. Just in case if all of this is obvious to you, here are the fundamentals.

A really really big function:
1st arg -> subscript (denotes the "level" (the notation also seems to be native within the book))
2nd arg -> superscript (denotes the number iterations of the same function)
3rd arg -> the actual input

$A(0,1, j) = j+1$
$A(k,1, j) = A(k-1,j+1,j) \mid k \ge 1$

its inverse for j = 1:
$alpha(n) = \min\{k : A(k,1,1) \ge n\}$

two auxiliary functions needed to define potential function:
//note that x is the node and x.p is its parent node, x.rank is its rank (the thing that increments monotonically traversing up)

level(x) = max {k: x.p.rank >= A(k,1,x.rank)}
iter(x) = max {i: x.p.rank >= A(level(x), i, x.rank)}

The potential function is then defined as:
//n is node count, q is the qth operation in the system, x is the node

phi(q,x) = alpha(n) * x.rank ; if x is not a root or x.rank = 0
phi(q,x) = (alpha(n) - level(x)) * x.rank - iter(x) ; if x is not a root and x.rank >= 1

Again, I emphasize that this question is really specific about the literature because it is not so obvious as to how all this and the $alpha(n)+2$ path length is necessary to prove the bound. But, I am open to other proofs where the find-set(x) subroutine (the one which compresses the path in after finding the root) is a superconstant.

The idea is actually quite simple. Just like in the book, let us assume that the find path consists of $s$ nodes. We disregard the root (because its potential doesn't change at all after the operation) and the node we upon which find_set is called (because it may have rank 0, which means its potential might not change). This leaves us with $s-2$ nodes.
Now, consider any node $z$ among the remaining $s-2$ nodes. As explained on pages 576-577 (I am using the 3rd edition), we have $0 \le \operatorname{level}(z) < \alpha(n)$. In other words, the level of $z$ must be between 0 and $\alpha(n) - 1$, inclusive. Indeed, it is the fact that we have
a finite number of options for the levels of the aforementioned $s-2$ nodes that will help us prove the assertion presented by the authors.
They say one example is worth a thousand words, so let's do one. Suppose we have 8 nodes between the root and the one upon which find_set was called. Suppose also that $\alpha(n)$ turns out to be $4$. Here's one possibility for the levels of the nodes, given in the order they appear in the find path:
$$ 2, 0, 1, 3, 2, 3, 1, 0 $$
The book claims that there are at most $\alpha(n)$ (4 in our case) nodes $x$ for which there doesn't exist a node y later in the path such that $\operatorname{level}(x) = \operatorname{level}(y)$. Take a good look at the sequence; you'll see that the claim holds for our example.
Now, the million dollar question. Why? Think about the last $\alpha(n)$ nodes. We could assign different levels to each one (as I have done for this example) so that none of them have a complementary node higher up the find path with the same level. However, that is the most we can have; every other node will now have some ancestor with the same level. Long story short, no matter how hard we try, we cannot have more than $\alpha(n)$ nodes without an ancestor of equal level; such a scenario would require more options for the level of a node than are available.
Put it all together, and it is evident that there exists another node with the same level down the line for at least $s - \alpha(n) - 2$ of the $s$ nodes, just like the book claims.
As for why the authors have found it unnecessary to provide an explanation for their claim, you are asking the wrong guy.


What are the advantages of cuckoo hashing over dynamic perfect hashing? Dynamic perfect hash tables and cuckoo hash tables are two different data structures that support worst-case O(1) lookups and expected O(1)-time insertions and deletions. Both require O(n) auxiliary space and access to families of hash functions for their operations.

I think that both of these data structures are beautiful and brilliant in their own right, but I'm not sure I see how and when one of these would be preferable over the other.

Are there specific contexts in which one of these data structures has a clear advantage over the other? Or are they mostly interchangeable?

Dynamic perfect hashing in the sense of Dietzfelbinger et al. only needs 2-independent hashing. While there are some results on simple hashing for cuckoo hash tables, such as twisted tabulation hashing and "Explicit and Efficient Hash Families Suffice for Cuckoo Hashing with a Stash", the original dynamic perfect hashing is more robust in some sense.


Find two disjoint set Given an universum $U$ and two sets $A$ and $B$ of sets of elements from $U$. I want to find (if such a pair exists) $a \in A$ and $b \in B$: $a \cap b \equiv \emptyset$. Currently I can do it only in $O(|A| \cdot |B| \cdot |U|)$, is there way to improve this?
Say, $|U| \leq 32$. Is there a way to speed algorithm up?
If it matters, one can assume, that all elements in $A \cup B$ are unique. Another variation of the problem is $A \equiv B$ and there is a need to search $a$ and $b$ from the single set.

Set $A = B$ and $|U| = \Theta(\log |A|)$, and you run up against the Orthogonal Vectors Conjecture trying to do better than $|A|^{2-o(1)}$.


Detailed explanation about Damerau Levenshtein Distance algorithm? I'm a fresh year Computer Science student. Our teacher gave us damerau levenshtein distance algorithm pseudo code (which he got from Wikipedia apparently) and asked us to explain how the algorithm works step by step. I've been looking around the net to find an article about that but nothing that explain how the algorithm works step by step. I tried to understand it myself but still have no idea how that works. Below is the pseudo code that he gave us :

algorithm DL-distance is
    input: strings a[1..length(a)], b[1..length(b)]
    output: distance, integer
    da := new array of |Σ| integers
    for i := 1 to |Σ| inclusive do
        da[i] := 0
    let d[−1..length(a), −1..length(b)] be a 2-d array of integers, dimensions length(a)+2, length(b)+2
    maxdist := length(a) + length(b)
    d[−1, −1] := maxdist
    for i := 0 to length(a) inclusive do
        d[i, −1] := maxdist
        d[i, 0] := i
    for j := 0 to length(b) inclusive do
        d[−1, j] := maxdist
        d[0, j] := j
    for i := 1 to length(a) inclusive do
        db := 0
        for j := 1 to length(b) inclusive do
            k := da[b[j]]
            ℓ := db
            if a[i] = b[j] then
                cost := 0
                db := j
            else
                cost := 1
            d[i, j] := minimum(d[i−1, j−1] + cost,  //substitution
                               d[i,   j−1] + 1,     //insertion
                               d[i−1, j  ] + 1,     //deletion
                               d[k−1, ℓ−1] + (i−k−1) + 1 + (j-ℓ−1)) //transposition
        da[a[i]] := i
    return d[length(a), length(b)]

I'm still trying to get the idea how it works step by step but if someone can help me I'll be very thankful.

The algorithm is based on dynamic programming. It computes a table $d[i,j]$ which stores the edit distance between $a_1\ldots a_i$ and $b_1\ldots b_j$. Although you only really need $i$ to range from $0$ to $\mathrm{length}(a)$ and $j$ to range from $0$ to $\mathrm{length}(b)$, some corner cases are handled by allowing $i=-1$ or $j=-1$ and letting the corresponding cells in the table have infinite cost (a large enough number is used instead of infinity).

The formula used to compute $d[i,j]$ given earlier parts of the table is explicitly found in the code, so I'll let you figure it out on your own.


Closure properties between 2 languages of different types Whenever said - The intersection between a Context Free Language and a Regular Language is always Context Free, what is the best logical way to confirm the statement?
I have this Chomsky hierarchy in mind that I refer whenever closure properties between Type-m and Type-n languages are asked but sometimes I come up with a wrong result.
How do you people logically solve it? What is the best simplest way?

You have to prove that the intersection of a context-free language and a regular language is always context-free. The simplest proof might go through push-down automata. Given a push-down automaton for a context-free language $L_1$, it is not too hard to augment it so that the state of a DFA for the regular language $L_2$ is maintained, and given this, you can construct a push-down automaton for $L_1\cap L_2$. Other proofs are also possible.

Each such question should be considered on its own. There are no general tricks. You can't just rely on the diagram. The problem with relying on the diagram in this case is that the intersection of two context-free languages need not be context-free; so the fact that regular languages are context-free isn't enough to show that the intersection of a context-free language and a regular language is again context-free.


Clarification for a class of Turing machine problems So say I have a task like this:

  Construct a Turing machine transforming the word u to the word v byt
  removing all the sequences of form "ba" from the word u. Input
  alphabet = {a,b,c}.

  Example: for IN cabbaacba, OUT cac.

And my problem always is: can I leave blank characters in place of "ba" sequences in tasks like this so that in the end, I have something like $ca \Phi \Phi \Phi \Phi c \Phi \Phi$ on the tape or do I have to work on the tape in such a way that I end up with, for example "cac", written consecutively, without blanks?

The question does not mention replacing "ba" by spaces.     It does not say that you can have spaces between the symbols in the output word. Is the blank character even in the output language?


Mathematically calculating time complexity This is a thread about mathematically calculating time complexity of nonlinear functions. I know that those questions were asked a lot, but it didn't make me understand fully the subject.

Also I understand that it's impossible to calculate every function, but usually we can (otherwise we have not been asked to do so on the exam).

I know how to mathematically  calculate the time complexity of the following function:

for(i = 0; i <= n-1; i++) {
    for(j = i + 1; j <= n - 1; j++) {
        // loop body - const O(1)
    }
}

I would calculate it as following: (hope without mistakes)

$$\begin{align*}
    \sum_{i=0}^{n-1}\sum_{j=i+1}^{n-1}1 & \overset{(1)}{=}\sum_{i=0}^{n-1}((n-1)-(i+1)+1)\\
 &=\sum_{i=0}^{n-1}(n-i-1)\\
 &=n\cdot\sum_{i=0}^{n-1}1-\sum_{i=0}^{n-1}i-\sum_{i=0}^{n-1}1\\
 &\overset{(2)}{=}n\cdot\sum_{i=0}^{n-1}1-\sum_{i=1}^{n-1}i-\sum_{i=0}^{n-1}1\\
 &\overset{(1)}{=}n\cdot((n-1)-0+1))-\sum_{i=1}^{n-1}i-((n-1)-0+1)\\
 &=n^{2}-n-\sum_{i=1}^{n-1}i\\
 &\overset{(2)}{=}n^{2}-n-\frac{(n-1)\cdot n}{2}\\
 &=\frac{2n^{2}-2n-n^{2}+n}{2}\\
 &=\frac{n^{2}-n}{2}\\
 &=O(n^{2})
\end{align*}$$

when I use the following equations:

$$\sum_{i=m}^{n}1=n-m+1 \,\,\,(1)$$
$$\sum_{i=0}^{n}i=\sum_{i=1}^{n}i=\frac{n(n+1)}{2} \,\,\,(2)$$

But when I get across with much harder function, as following:

example 1:

int x = 2;
while (n < x) {
    x *= x;
}

example 2;

int i = 1;
while(i < n) {
    if((n – i) % 2)
        i *= 3;
    else
        i *= 2;
 }

I get lost. I really don't know where to start calculating. I always can start inserting different values for n, and guessing the time complexity, but it does not feels right (and also it can be misleading).

Is it even possible to mathematically calculate the time complexity of those examples? how should I approached those questions? Maybe is there somewhere a list of possible tricks?

If we ignore effects of overflow and assume we can square x as often as we like in constant time, then the first example clearly either stops immediately if n ≥ 2, or runs forever if n < 2.

In the second example, at each iteration i is multiplied either by 2 or by 3. Therefore after k iterations, $2^k ≤ i ≤ 3^k$. The number of iterations until i ≥ n is between $log_2 (n)$ and $log_3(n)$ which is in each case $O (log(n))$.

On the other hand, I'm currently working on an algorithm where I don't have the slightest idea how to calculate the runtime, although measurements show that it takes experimentally about $600 n^{1/2}$ nanoseconds for values from $10^{12}$ to $10^{19}$ - with huge variations. A proof for $O(n^{1/2})$ is mathematically beyond me.

In the end, this question is like asking "how can I prove mathematical theorems". Some are easy, some are hard, most get easier with practice. There is no "list of possible tricks". The most helpful thing is that when you are concerned with big-O notation you don't need precise results. A constant factor makes no difference.


Need Help Understanding MST Cutset Formulation I just started learning about linear programming in my class, and I'm having some trouble understanding the MST Formulation Integer Linear Programming (Cutset Formulation).
This is the definition:

An integer linear program that solves the minimum spanning tree problem is as follows:
$$
\begin{align*}
\text{Minimize} & \sum_{\{u,v\} \in E} w_{u,v}x_{u,v} \\
\text{subject to} & \sum_{\substack{\{u,v\} \in E\colon \\ u \in S, v \notin S}} x_{u,v} \geq 1 & \text{for all $S \subseteq V$ with $0 < |S| < |V|$} \\
& \sum_{\{u,v\} \in E} x_{u,v} \leq |V|-1 \\
& x_{u,v} \in \{0,1\} & \text{for all $\{u,v\} \in E$}
\end{align*}
$$

$x_{ij}$ is defined to be $1$ if the edge $ij$ is in $T$.
What exactly does the optimum value represent here? Is it the number of edges that are used in our MST? If so, how does knowing the number of edges help us in forming the MST?
How does this ILP "work" to solve the MST problem?

The first constraint makes sure the induced subgraph remains connected : there must be an edge between every pair of subsets of $V$ ; or in terms of graph theory,  for every cut, at least one edge must cross the cut. For example, if $S=\{a\}$, the constraint is
$$
\sum_{(u,a)|u\neq a} x_{ua} \ge 1
$$
and this imposes that $a$ does not end up alone.

The second constraint makes sure you end up with $n-1$ edges, which is a characteristic of a tree.


Max no. of keys of B-Tree of height h I am reading about B-Tree through CLRS. One of the exercise problem is to express maximum number of keys in a BTree of height $h$ and minimum degree $t$.

Properties of BTree of $t$:

$t\ge 2$
Min. no of keys in a node is $t-1$ and max. number of keys in a node is $2t-1$
Max number of children a node can have is $2t$

To solve it the formula I came up with is $$\sum_0^h (2t)^h(2t-1) $$

Does it have any convergence?


Internal tangent intersection of two point sets in linear time I need to find the intersection of the internal tangents of two point sets $V_a, V_b$ in $\mathbb{R}^2$, defined via their convex hulls. We can assume that the sets are disjoint and linearly separable, so I think the internal tangents are uniquely defined as the two lines which are tangent to each of the convex hulls of the sets, such that each set is on a different side. This is the point marked green here:

This paper ("Computing Plurality Points and Condorcet Points in Euclidean Space") I'm currently reading (paywalled, unfortunately...) says in a sort of side note that this problem can be solved using linear programming, in linear time in the number of points, but doesn't describe how.

For constructing a linear program, I thought about describing lines by $F(x, y) = ax + by + c= 0$, and optimizing a function of $a, b, c$. Then the obvious constraints would be $\forall v \in V_a: av_x + bv_y + c \geq 0$ and the according thing for $V_b$, to force the lines to go between the two sets.

But now I am stuck. For one, we need to constrain the space of lines somewhat; $\lVert (a, b) \rVert = 1$ would be natural to require, but that's not linear.  Also, I'm not sure about the cost function; I thought about using

$$\min_{a,b,c} \sum_{v\in V_a} F(v_x, v_y) - \sum_{v\in V_b} F(v_x, v_y),$$

since $F$ is somehow a distance from the line (although not in the strict sense, I guess). But that is just guessing and also doesn't work -- I tried some things like I described in JuMP, but it always returned "infeasible".

How can this be formluated as a linear program? Alternatively, I can accept an algorithmic solution with linear time. Or a disproof, of course.

I found a way to solve the problem in my case -- maybe that only applies to the special conditions found in the paper. There, the two point sets can be assumed to be non-collinear and always separable by a line parallel to one of the coordinate axes, and we always know that $A$ is "left of" (or "above") $B$.

In this case, we can represent a line simply by $y = kx + d$, and get one internal tangent by minimizing the function $F(k, d) = k$ subject to
$$
\forall v \in A: v_y \leq k  v_x + d\\
\forall v \in B: v_y \geq k  v_x + d.
$$
The other one can  be found by swapping $A$ and $B$ (or the relations) and maximizing.


Is there a graph theory textbook that covers treewidth thoroughly? Can someone recommend a graph theory textbook that covers treewidth thoroughly?
Something that focuses on the graph-theoretic structure of bounded treewidth graphs rather than solving problems on them.  Don't need the strongest/newest results but would prefer something that
Preferably something that covers sublinear treewidth of planar and minor free graphs.

I don't know if the thing you are looking for exists, but here are at least some pointers:
Parameterized Algorithms by Cygan et al (free PDF version) has a chapter dedicated on the topic.  This is slightly algorithms oriented, but contains structural stuff too.
Graph Theory by Diestel has one chapter, (12.  Minors, Trees and WQO) on the subject, about 40 pages.  homepage
Bodlaender has a chapter Treewidth of Graphs in the Encyclopedia of Algorithms.  homepage
Heggernes has a short compendium used for her advanced algorithms class Treewidth, partial $k$-trees, and chordal graphs.
You also have Ton Kloks' book, Treewidth springer, but it's getting rather old.  I have not read this one, so I don't know much about it.


Order preserving encoding of strings to numbers I want to encode strings as real numbers while preserving order. The order of the strings is the lexicographic order (as used in phone books); the order of the numbers is the standard order.

Is there an general (i.e. no additional conditions such as e.g. known max string size) encoding with this property?

(I assume that by lexicographic order, you mean lexicographic order. Phone books may have all kinds of oddities due to ordering proper names, such as sorting McDonald near MacDonald.)

Suppose your strings only contained the characters 1, 2, 3, 4, 5, 6, 7, 8 and 9. The mapping from the string $s$ to the decimal number 0.$\!\!s$ is monotonic.

If you have $n$ characters in your alphabet, use base $n+1$.

This encoding accommodates infinite strings too, but you need to use base $n+2$ and skip the largest digit as well as the smallest digit (the largest string beginning with 1 is 1888… $\mapsto 0.1888\ldots$ which is smaller than 2 $\mapsto 0.2 = 0.1999\ldots$).


Prim's algorithm: difference between brute force and PQ approaches I'm trying to figure out the different way we obtain an MST with a brute force Prim's algorithm compared to the optimized version based on priority queues.

Given a graph $G=(V,E)$, the former can be stated as in Dasgupta et al.:

X = {}
while(|X| < |V-1|)
  pick a subset S of V for which X has no edges between S and V-S
  let 'e' be the minimum weight edge in E between S and V-S
  X = X union {e}

It uses blue rule and builds the tree edge by edge: at the end you have the MST of the whole graph, until then $X$ is just incomplete. If we use a brute force approach, running time is $O(|V|\cdot |E|)$.

As we know, better running time is obtained mantaining a priority queue that we use to find the cheaper edge incident to the tree that we build on a step by step basis. Anyway i think that this more than just optimization, since solution with this last approach is built incrementally.

Infact, if with brute force you have a tree built edge by edge considering from the beginning the whole graph, with priority queues you instead discover nodes incrementally: at each step you have a valid MST of a subproblem. As long as the algorithm proceeds, every node is discovered and priority queue becomes empty. At this point the MST has grown to be the solution of the whole graph. I can summarize with the following simple example:

You start from node $A$, and edges to $B$ and $C$ are immediately discovered. They become part of the tree. Anyway tree changes as long as new nodes are discovered (see UPDATE label in the picture). With brute force you don't have anything similar.

Please, let me know if i'm mistaken or if my reasoning is not complete.

First, the psuedo-code given is not intended for brute force Prim's algorithm. It is a meta-algorithm for MST. Quoted from the beginning of Section 5.1.5 of "Algorithms":

  What the cut property tells us in most general terms is that any algorithm conforming to the following greedy schema is guaranteed to work.

Both Kruskal's algorithm based on disjoint sets and Prim's algorithm based on priority queues are instances of the meta-algorithm.

As for your other questions:

  "If we use a brute force approach, running time is O(|V|⋅|E|)."

It does not make much sense to discuss about the time complexity of a meta-algorithm.

  "Anyway I think that this more than just optimization, since solution with this last approach is built incrementally."

The greedy meta-algorithm for MST is incremental. And both Kruskal's algorithm and Prim's algorithm are incremental.


Algorithm for 3-object matching I believe that in the general case stable matching for 3 members rather than 2 is NP-Complete, but I wonder if in my case there's something that I am missing that could have reasonable time complexity.

The specific purpose of the program I am trying to write is to take an arbitrary number of objects and split them into groups of 3. Hypothetically, each object has a color (let's say right now there's 10 possible colors).

The part of this group creation that allows something of a "preference list" of other members is both having group members of different colors and having been grouped with them in the past as little times as possible.

Everything I have come up with either has horrendous time complexity or has the chance of failing (missing possible groupings). If anyone has done anything like this before I would appreciate any suggestions.

It sounds like you're looking for a polynomial-time approximation algorithm for the 3-dimensional matching problem (which is, as you noted, NP-complete - the decision problem is one of Karp's 21 NP-complete problems).

In 2014, Ostrovsky and Rosenbaum proved that 3D matching is APX-complete. This implies the existence of an efficient algorithm that produces a result within a "fixed multiplicative factor of the optimal answer" - in their case, $4/9$.


Is There a Complete Problem for the Class of Turing Decidable Problems? Languages such as $\text{HALT}_{TM}$ are $\textsf{RE-complete}$ under many-one reductions. It is  trivial to see that $\text{co-RE}$ has complete problems, too. S. Schmitz [1] considers some classes inbetween $\text{ELEM}$ and $\text{REC}$. They present complete problems for these classes under specifically crafted reductions.

Are there complete problems for $\textsf{R} = \textsf{RE} \cap \textsf{co-RE}$ (aka $\textsf{REC}$) relative to weaker reductions? Turing reductions are inappropriate because they are capable of doing all the work. Should we expect such reductions to be contrived or not so (e.g. many-one reductions that are restricted to primitive recursion)?

[1] Sylvain Schmitz Complexity Hierarchies Beyond Elementary 2013 http://arxiv.org/abs/1312.5686

Generally a class having a complete problem under a nice class of reductions
implies that the class can be enumerated.
$\mathsf{R}$ is not computably enumerable, therefore it does not have a complete problem with respect a nice class of reductions.

Here is the argument:

Assume that there is a complete problem $A$ for $\mathsf{R}$.
Therefore for any problem in $\mathsf{R}$ can be obtained from
a reduction (let's say polynomial time many-one reductions) combined with $A$.
We can computably enumerate the reductions,
therefore we can computably enumerate $\mathsf{R}$.
But $\mathsf{R}$ is not computably enumerable
(otherwise we could diagonalize).

In the literature look for the set of total recursive/computable functions.


How to find longest possible identical sequence in Array A and B? You have to arrays of single digit numbers. (0 - 9).

A = [....1 billion elements....];
B = [3,5,8,1,2,5,8,3,4,9,1,0,2];

I want to find combo of as few as possible subsets that of array B in A.

So whole Array B could be in Array A by coincidence since it's very large and that would be the largest match as whole sequence is there. Or you could have subset of array B, [8,3,4,9], at index ex: i = 3800443...

Now my goal is to convert Array B to references based on Array A.

So If I give you object like this:

{
  block1: {i: 48938, len: 388},
  block2: {i: 2828, len: 3},
  ...
}

you'd be able to reconstruct array B if you had array A.

One mistake would be to go and find biggest subset only. Then the solution would have biggest subset, but not minimum amount of subsets possible.

Example:

a = [1,3,4,4,3,0,8,3,5,5,2,8,3,1,0,9];
    |^||^||^||^||^||      ^     ||^|

Although this has longest subset, but It ended up with 6 blocks. Whereas,

b = [1,3,4,4,3,0,8,3,5,5,2,8,3,1,0,9];
    |    ^    ||     ^    ||    ^   |

here each subset might not be the longest but there are fewer subsets to cover whole array.

Assuming all characters of $B$ are wholly contained in $A$, then this method should give you an optimal results.

Algorithm

Compute the longest substring $P_i$ in $A$ that is a prefix of the suffix of $B$ from $B_{i \ldots n}$. This is essentially equivalent to finding the longest common substrings between $A$ and $B$ starting at index $i$ of $B$. There are many methods of doing this, some listed below:

Compute a suffix tree $T$ for the array $B$. Making sure to leave in the suffix links (these are important for back tracking and essentially make the tree like an Aho-Corasick state machine). Traverse $A$ using $T$ as a state machine. Keep track of deepest non-root node reached in $T$ for each path from root to leaf. This will take $\Theta(|B|) + \Theta(|B| + |A|) = \Theta(|B| + |A|)$.
Solve this by inserting both strings $A$ and $B$ into a generalized suffix tree. Keep track of deepest common ancestor between a suffix leaf of $B$ with any other suffix leaf in $A$. This will take $\Theta(|B| + |A|)$.
Least optimal, use dynamic programming, but reverse the formula so you compute longest prefix for a suffix, rather than longest suffix for a given prefix. This will take $\Theta(|B|\cdot |A|)$. (Would not recommend)

Sort $P$ by the index of the starting character of the prefix (i.e. in the original suffix order).
Let $i = 0$
While $i < |B|$:

Let $j$ be the last index of substring $P_i$.
Add substring $P_i$ to a set $S$.
Let $i = j+1$

Return $S$ as it is the set of sequences in $A$ that minimally but completely cover $B$.

Running Time

Let $n = |B|$ and $m = |A|$:

Will take $O(n + m)$ because branching factor is constant (only 10 values) and if you keep it compressed and refer to indices instead of values.
Will take $O(n \log n)$ or $O(1)$ depending on how you structure $T$.
Will take $O(n)$.

Total time will be $O(m + n)$ which will be $O(m)$ for $m \gg n$.

Example

Let $$B = [0, 1, 3, 1, 2, 0]$$
$$A = [2, 1, 3, 0, 5, 1, 2, 4, 0, 1, 3, 0, 3, 1]$$

Step 1 would compute the following tree:

Step 2 should generate the following longest prefixes $P$ for suffix $S$:

$$\begin{array}{|c||r|r|}
\hline B \text{ indices} & S & P \\
\hline [0\ldots 5] & 0,1,3,1,2,0 & 0,1,3 \\
\hline [1\ldots 5] & 1,3,1,2,0 & 1,3 \\
\hline [2\ldots 5] & 3,1,2,0 & 3,1 \\
\hline [3\ldots 5] & 1,2,0 & 1,2 \\
\hline [4\ldots 5] & 2,0 & 2 \\
\hline [5\ldots 5] & 0 & 0 \\
\hline
\end{array}$$

We then follow steps 5, 6, and 7 to get that our set to be returned is contained of:
$$P_0 = [0, 1, 3], P_3 = [1, 2], \text{ and } P_5 = [0]$$

It's also easy to think of this as the maximum number of disjoint subsequences of $B$ contained in $A$. The maximum here is 3 because there are at most 3 subsequences that have no overlapping pieces:

Maybe this visualization will help. Then we should keep track of indices along the way in $A$ (this is relatively trivial with proper manipulation), but we see $B$ can be represented by:

$$A[6 \ldots 8] \; A[4 \ldots 5] \; A[3 \ldots 3]$$
$$0,1,3 : 1,2 : 0$$


What kinds of problems are modeled by a recursive definition of a set of strings? Given this definition:

  The set $\Sigma^*$ of strings over the alphabet $\Sigma$ is defined recursively by:
  BASIS STEP: $\lambda \in \Sigma^*$ (where $\lambda$ is the empty string)
  RECURSIVE STEP: If $w \in \Sigma^*$ and $x \in \Sigma$ then $wx \in \Sigma^*$

My understanding of this is that the subset $\Sigma^*$ will expand with each iteration by what appears to be $|\Sigma|^n$ elements where $n$ is the number of iterations. So for example, given $\Sigma = \{a,b,c\}$ we have:

Base Case: $\Sigma^* = \{\lambda\}$
Iteration 1: $\Sigma^* = \{\lambda,\lambda a, \lambda b, \lambda c\}$
Iteration 2: $\Sigma^* = \{\lambda,\lambda a, \lambda b, \lambda c, \lambda aa, \lambda ab, \lambda ac, \lambda ba, \lambda bb, \lambda bc, \lambda ca, \lambda cb, \lambda cc \}$

Etc.

If this is the correct interpretation of the data structure described by this recursion, what types of problems are structures like this used to study/prove in CS?

The definition you quote is a formal definition of strings which is particularly conducive to induction. There are many other ways to define strings, for example as sequences of letters, or more exactly as mappings $f\colon \{1,\ldots,n\} \to \Sigma$ for some $n \in \mathbb{N}$.

There are several different ways of understanding your definition, which is stated rather informally. The usual interpretation is as a least fixed point: $\Sigma^*$ is the least set which contains $\lambda$, and for each $w \in \Sigma^*$ and $\sigma \in \Sigma$, also $w\sigma \in \Sigma^*$; here you should think of concatenation as some formal operation, which is perhaps more appropriate to write as (say) $(w.\sigma)$.

What is a least fixed point? In this case, it is the intersection of all sets satisfying the two conditions stated above. One can prove that in general, such sets can be constructed just in the way that you describe: start with the empty set, and repeatedly a closure operation $C$, which in this case is
$$ S \to S \cup \{\lambda\} \cup \{w\sigma : w \in S, \sigma \in \Sigma\}. $$
Form a sequence $S_0 = \emptyset$, $S_1 = C(S_0)$, $S_2 = C(S_1)$, and so on, and take ${\cal S} = \bigcup_{n=0}^\infty S_n$. It is not too hard to show that ${\cal S} = C({\cal S})$, and moreover ${\cal S}$ is the least fixed point.

Another way of thinking of these rules is as a proof system for demonstrating that a certain expression is in $\Sigma^*$. We have an axiom $\begin{array}{c}\\\hline \lambda\end{array}$ and an inference rule $\begin{array}{c} w \\\hline w\sigma \end{array}$ valid for all $\sigma \in \Sigma$.

A third way is through induction: a property $P$ holds for all $\Sigma^*$ if $P(\lambda)$ and for all $\sigma \in \Sigma$, $P(w) \longrightarrow P(w\sigma)$. This is how we usually use this definition.

Given this definition, it is possible to define operations on strings and to prove theorems on strings. For example, length is defined by $|\lambda| = 0$ and $|w\sigma| = |w| + 1$, and concatenation by $x::\lambda = x$ and $x::(w\sigma) = (x::w)\sigma$; it is straightforward to prove by induction (on $y$) that $|x::y| = |x| + |y|$.

This sort of definition is common in the more formal parts of computer science. Other parts will prefer the informal definition "$\Sigma^*$ is the set of all words over $\Sigma$", or more explicitly, "$\Sigma^*$ is the set of all finite sequences of elements of $\Sigma$".


Finding a good loop invariant for a powering procedure Consider the following algorithm for computing integer powers:

Procedure power(integer x, integer n)
    power := 1
    for i := 1 to n
        power := power * x
    return power

Can we say that the loop invariant is $power \leq x^n$ ?
Before the loop $power$ is initialized to $1$ so its equal to $1 \leq x^n$.

How do we prove maintenance of the invariant?

No, you can't say that $power \leq x^n$ is a loop invariant, since it is not maintained by the loop. For example, if $x > 1$ and at the current iteration $power = x^n$, then the invariant is satisfied at the beginning of the loop but not at the end of the loop.

Also, this loop invariant doesn't help you prove that at the end $power = x^n$, which is presumably your end goal.

Try to think of an invariant which describes the value of $power$ in terms of $x$ and $i$.


Is it 100% OK to say "All software doesn't need to know the system lower than the architecture level"? Most of you know this diagram. If this diagram is true, all software is free to not know the levels lower than ISA. But it's not true. Softwares like performance-critical programs or system softwares like OS and compilers, are often forced to understand not only ISA but also microarchitecture.

If so, what about the levels lower than microarchitecture? Is it 100% sure to say the levels lower than uArch aren't require to be understand by softwares or programmers?

Nothing is 100% sure in life.

Abstractions are rarely perfect; they can be leaky.  Nonetheless, just because developers at higher levels sometimes need to know about lower layers doesn't mean they always do, or usually do; and it doesn't mean the abstraction is useless.

Yes, there are cases where it is helpful to know about even lower levels of the architecture.  For instance, cold boot attacks and the row hammer attack are made possible by a property of the physics of DRAM cells, so if you want to analyze the security of a system against that specific threat model, you might need to know about things at the level of devices and physics.  These cases are the exception rather than the norm, but they do exist and are occasionally relevant.


Does P = NP in Cellular Automata of Hyperbolic Spaces? I read a few years ago in this book that NP problems are tractable in the space of cellular automata in the hyperbolic plane. What does this mean? Does P = NP according to these books/papers?
Some excerpts from the paper:

It is well known that if we have binary trees at our disposal “for free”, it is possible to solve NP-problems in polynomial time, see [14, 5]. However, it is not immediate to implement binary tree algorithms in the pentagrid, and the goal of this section is to indicate how one can proceed.

From my understanding, the P = NP problem is looking for polynomial-time algorithms to solve complicated problems. From my cursory glance through the books and papers, it seems to suggest that he has solved the problem. What am I missing?
Here is another paper, titled In Some Curved Spaces, We Can Solve NP-Hard Problems in Polynomial Time: Towards Matiyasevich's Dream.

The P vs. NP problem is a question about Turing machines $T$, because the complexity classes P and NP are defined in terms of these theoretical machines. Let's call these classes $P_T$ and $NP_T$ from now on. The paper introduces a new theoretical computation machine   $H$ that has associated classes $P_H$ (runs in polynomial time on the hyperbolic cellular automaton) and $NP_H$ (runs in non-deterministic polynomial time on the hyperbolic cellular automaton).
The first step in this paper is a proof that the 3SAT problem, a well known $NP_T$-complete problem, can be solved in polynomial time on this machine, i.e. this problem lies in $P_H$. Next, they show any polynomial time reduction on a Turing machine can be performed in polynomial time on their hyperbolic automaton. Since 3SAT is $NP_T$-complete, any $NP_T$ instance can be reduced to a 3SAT instance in polynomial time (on $T$ by definition, so also on $H$ by their lemma) and then be solved by solving 3SAT in poly-time, both on the hyperbolic automaton. In other words, the main result of this paper (Theorem 1) can be written as $NP_T \subseteq P_H$ in our notation. This does not give a solution to the P vs. NP problem, because that would need to relate the classes $NP_T$ and $P_T$.
Note that the authors include some remarks on the P vs. NP problem in section 4.2, where they claim their result is evidence for P$\neq$NP (!):

A third direction consists of the new light shed on the P=NP question in the
ordinary settings. As the hyperbolic space has properties which are very different from the properties of the euclidean space, in particular, it has many more directions, would not that be a hint favorable to prove that P$\neq$NP in euclidean conditions? It seems that
for the last ten years the works in the field of complexity incline people to believe
more in P$\neq$NP. Apparently, the present result also belongs to that trend.


How to come up with a language that is recognizable but not co-recognizable? Forming a language that is recognizable but not co-recognizable. I'm having trouble coming up with a language with these properties. A recognizable language is a language $A \subseteq \Sigma^*$ iff $A = L(M)$ for some Turing machine $M$.

Co-recognizable is the exact same except the complement of $A$ has to be recognizable.

My question is how do I come up with a language that I know will be recognizable but not co-recognizable?

Remember that there are three things a Turing machine can do, given an input. It can:

Accept
Reject
Diverge (infinite-loop)

"Recognizable" means "we can accept on strings in our language, and reject-or-diverge on anything else". "Co-recognizable" means "we can reject-or-diverge on strings in our language, and accept on anything else". Or, equivalently, "we can accept-or-diverge on strings in our language, and reject on anything else".

So the key is, intuitively, to find a language so that a TM always diverges on (some) strings not in the language.

A classic example is the Halting Problem. (To be more specific, the set of encoded Turing machines that halt on empty input, for a given encoding.) You can recognize this language by simulating the machine, then accepting. But you can't recognize its opposite.

(Formally, you have to do a bit more work. You have to prove that the language is undecidable: that no Turing machine can always say "no" correctly, even if it can always say "yes" correctly. Usually this means reduction to the Halting Problem or Rice's Theorem.)


Find the lightest weight of a path between $u$ to $v$ that contains no more then $k$ edges (If there's one) Given a directed and strongly connected graph $G=(V,E)$, weight function $w: E \to \mathbb{R}$ and two distinct vertices $u,v \in V$. We know that there aren't negative cycles.
I need to find algorithm, efficient as possible,such that for every value of $k$, $2 \leq k \leq |V|-1$, it will find the lightest weight of a path between $u$ to $v$ that contains no more then $k$ edges (If there's one).

I don't know what to do. I want to use Bellman Ford somehow, I just don't sure how.

Thanks a lot.

Consider the dynamic programming formulation of Bellman-Ford:

$\qquad \displaystyle \mathrm{bf}(i,j) = \begin{cases}
                             0         &, i = 0 \land j = s \\
                             \infty    &, i = 0 \land j \neq s \\
                             \min\limits_{k \in V}\, \big(\, \mathrm{bf}(i-1,k) + c(k,j)\,\big) &, \text{else}
                          \end{cases}$

What meaning does $\mathrm{bf}(i,j)$ have, that is what does DP-matrix entry $\mathrm{bf}[i,j]$ contain?

   If you unfold the definition (i.e. proof by induction) you see that $\mathrm{bf}(i,j)$ is the weight of the shortest path from starting node $s$ to $j$ with at most $i$ edges -- exactly what you are looking for.


Proving that the language $\{ w^n\mid w \in \{0,1\}^∗, \, n \ge 2 \}$ is not regular I'm trying to prove that the following language is not regular:
$$\{ w^n\mid w \in \{0,1\}^∗, \, n  \ge 2 \}$$
I'm trying to prove this with the pumping lemma, but I'm kind of confused because $w$ is a language, not an expression like $a^n b^n$, and I don't know how can I partition that into three parts.

Suppose towards a contradiction that your language $L$ was regular and let $p$ be its pumping length.
Consider the word $w = 0^p 10^p1 \in L$. By the pumping lemma, $w$ can be written as $w=xyz$ with $x=0^{h}$, $y=0^k$, and $z=0^{p-h-k}10^p 1$ (here $h+k \le p$ and $k \ge 1$) such that, for every non-negative integer $i$, $xy^iz \in L$.
Substituting and simplifying, the above means that, for every $i \ge 0$,  we have $0^{p-k} 0^{ki} 1 0^p 1 \in L$. In particular, the above must hold for $i=0$, implying that $0^{p-k}1 0^p 1 \in L$.
Since $0^{p-k}1 0^p 1 \not\in L$ (recall that $k \ge 1$), this is provides the sought contradiction and concludes the proof.


Why do Amdahl's law and Gustafson's law give us different speedups, when applied on the same task? I am given a task, where exactly 50% of the work is parallelizable. When applying Amdahl's law to calculate speedup when using 2 processing units instead of one, I get a different result than the one I get when calculating the same speedup using Gustafson's law. I don't understand why is that.

The reason is that Amdahl's law and Gustafson's law refer to two very different situations.

In particular, Amdahl's law applies to those cases in which the problem size is fixed, e.g. you need to process a static dataset or an image of given dimensions. The law treats the problem size as being a constant (size constrained model), and clearly shows how the execution time decreases as the number of processors increases. This law can be applied to any system, not just to parallel systems; it is a very general statement about any improvement  in a system, i.e., no matter how much one improves one part of a  system, the improvement in the overall performance is bounded by  $1/f$, where $f$ is the fraction of the original time spent in parts of the system one does not improve. This model, fixing the amount of data per processor, usually provides the highest efficiency possible (this is commonly referred to as strong scaling).

On the other hand, rather than assuming that the problem size is fixed, it is just as valid to assume that the parallel execution time is fixed. This is exactly what the Gustafson's law does: as the parallel system size is increased (i.e. the number of processors $p$ is increased), the problem size is increased to maintain constant parallel execution time (weak scaling). Therefore, this is a time constrained model. So, the important difference is that the scaled speedup of Gustafson starts with a big problem on a big ($p$ processors) machine and looks back toward the one-processor case and asks how  long it would have taken to execute, whilst Amdahl's law starts with a problem on the one-processor machine, and asks how long it might take on a many-processor parallel machine. Gustafson simply noted that there were lots of problems that seemed  to run well on lots of processors: they computed for a great deal of time $(1-s)$ using all the processors, and not all that long $(s)$ in a serial fashion. So he derived the scaled speedup formula to help explain that.

Does this contradict Amdahl's law? No, of course.
Amdahl works when you are given a fixed size input and you want to understand how fast you can process in parallel that input. Gustafson works when you can increase the problem size and you want to solve larger problems in the same amount of time. For instance scientist are actually interested to solving larger instances of problems, or want to increase the complexity of a model to gain better accuracy.


Determine smallest possible parameter set for FPT I am reading a book about complexity analysis and cannot find a way to solve a problem in that book.
The problem is, that I do not understand how to determine the smallest possible parameters, given the runtime of an algorithm. Do I just need to insert some numbers and see if the parameters exceed n at some point? Perhaps someone can explain that to me.

Consider the following exercise:

  The following O(.) expressions represent worst-case runtimes of different algorithms, where n is a measure of the input size and p, q and r are parameters (where p, q, r <= n). Which of the following running times are FPT running times?
  Give the smallest possible parameter set for which the running times are FPT (if one exists) and explain.

  a) $O(p^q * n^2)$

Now I know that by the definition of FPT, this runtime is FPT (because we have a function of the parameters times n^constant). However, what are the smallest $p$ and $q$ in that case?

There are some more, but I just want to understand how to solve it and then I'll try the rest myself again.

Taken from:

  Rooij, I. V., Blokpoel, M., Kwisthout, J., & Wareham, T. (2019). Fixed-Parameter Tractable Time. In Cognition and Intractability: A Guide to Classical and Parameterized Complexity Analysis (p. 125). Cambridge, England: Cambridge University Press.

Recall that the runtime must be of the form $f(k) \cdot n^c$ for some constant $c$. So I believe that the exercise is asking, given that all three are at most $n$, which do you have to take as formal parameters in your analysis to achieve an FPT runtime.

So if only $p$ is a parameter, is that FPT? What if only $q$? Clearly, if both are fixed, you have FPT runtime.


Would it be possible to use the cloud for RAM? I'm not sure if this is the right place to ask but I had this idea. Since the cloud can be used for storing memory, would it be possible to use it for RAM too?

Network latency is orders of magnitude too high for a remote server to usefully share its RAM directly, even if you could cobble together a virtualization layer to make it work.  However, today's network speeds are high enough that remote RAM based key/value stores like memcached can compete favorably with hammering a local database due to insufficient local memory for caching.

Since this question has the virtual-memory tag, I'll also point out that network servers (which is what "cloud computing" is the latest name for) have been used for virtual memory (also known as "swap") since the diskless workstations of the late 1980's.  These machines are called "thin clients" today.


Decreasing a digraph's edge-weights while keeping net weights of edges at each vertex constant Given a directed weighted graph, is there an algorithm that does the following:

Removes as many edges possible.
Reduces as many weights as possible.

Given the constraint that the net weight of all edges connected to the vertex (sum of incoming edge weights minus sum of outgoing edge weights) remains the same and every edge weight remains non-negative.

Examples:

The graph "A -10-> B -10-> C" could be reduced to "A-10->C" since vertex B has net zero weights (10 incoming and 10 outgoing)

The graph "A -10-> B -3-> A" could be reduced to "A-7->B".

Thanks.

The second objective is just a simple circulation problem http://en.wikipedia.org/wiki/Circulation_problem
as the maximum circulation gives the highest reduction in weight. This problem is basically equivalent to max flow for which efficient algorithms are well known.

Not so sure about trading of the first and second objective. You might achieve something like this by modelling it as a min concave-cost network flow problem with capacities, e.g. by some cost function that is nearly flat at arc saturation, such that it favours saturating arcs once they are close, but this is NP-hard:
http://link.springer.com/article/10.1007/BF02283688

Maybe there is a more efficient way depending on what you are trying to achieve,  but the constraint that net edge weights remain the same indicate that you are looking for some network flow type algorithm.

Do you have an application for this in mind?


Why do the sequent calculus NOT left and NOT right rules work? The rules I am considering are $\frac{\neg A, \ \Gamma \implies \Delta}{\Gamma \implies \Delta, \ A} (\neg L)$ and $\frac{\Gamma \implies \Delta, \ \neg A}{A, \ \Gamma \implies \Delta} (\neg R)$

I am trying to get my head around some of the sequent calculus rules, and while I think I understand most of them, I am struggling to apply any intuition to the negation rules shown above.

The intuition of looking at the left as a conjunction of literals and the right as a disjunction of literals seems to break down, and I am unclear how to explain these rules to myself.

What is a sensible way to view such rules and put some understanding on them?

You could start by considering simplified versions of the rules and build intuition by considering those cases. For instance,

$$\frac{\neg A, \ B \implies C}{B \implies C, \ A} (\neg L)$$

can be interpreted as stating that $(\neg A\wedge B)\Rightarrow C$ implies
$B\Rightarrow (C\vee A)$.

So if it is the case that $\neg A$ and $B$ are true implies $C$ is true, then if only $B$ is true, either $C$ is true (independently of $\neg A$) or $A$ is true, for otherwise $\neg A$ would be true, which combined with $B$ being true would make $C$ true.

A similar game can be played with the other case.


For complexity classes A and B, what does $A^B$ mean? What does $A^B$ mean where A and B are complexity classes?

The "Polynomial Hierarchy" page says:

$A^B$ is the set of decision problems solvable by a Turing machine in class A augmented by an oracle for some complete problem in class B

In that case what is a Turing machine in class A?

(besides just a machine of some sort that can solve problems in A, because that doesn't give any insight as to what it means to augment such a machine with an oracle)

The motivation for this question was: What is a Turing Machine in class coNP.

An oracle is a way for a Turing Machine to ask a question and get it answered immediately, "magically". The way we usually model it is that the Turing Machine can write down the question on a special, extra tape, and then (say) the tape is erased and the answer immediately written on it.

More specifically, we usually suppose that the oracle is for a particular language, so we write a string on the tape, followed by some special "end-of-string" symbol; then, the formula disappears and is replaced by either "YES" or "NO".

For a concrete example, suppose our Turing Machine has an oracle for SAT. Then it can write a formula on the string and immediately find out if it's satisfiable or not.

Notice that, since SAT is NP-Complete, a TM with a SAT oracle can decide any language in NP in polynomial time: Just reduce the input to a SAT formula, and then ask the oracle about this SAT formula.

So we might write $P^{NP}$ for the set of languages that can be decided in polynomial time by a TM with an oracle for SAT.


Approximating a series for asymptotic upper bound So I stumbled upon a question here to find an asymptotic bound for the recurrence
$$
T(n) = 4T(n/4) + \left( \frac {n} {\log n} \right)^2 $$

The solution shows a solution using master method to prove the answer as $O(n)$
However, I tried to solve it using substitution as:

$$T(\frac {n} {4^i}) = 4^{i+1} T(\frac {n} {4^{i+1}} ) + \sum_{j=0}^{i} \frac {n^2} {4^j {(\log \frac{n}{4^j})^2} }$$

I then get
$$
T(n) = 4^{x+1}(Base Constant) + \sum_{j=0}^{logn -1} \frac {n^2} {4^j {(log \frac{n}{4^j})^2} }$$
$x=\log n$

Now for the summation:
$$n^2\sum_{j=0}^{\log n -1} \frac {1} {4^j {(log(n) - j\log (4))^2} }$$

All logarithms to be taken base 4:
$n^2\sum_{j=0}^{\log n -1} \frac {1} {4^j {(\log (n) - j)^2} }$

Now, the first substitution I made was $t = \log n -j $

$n^2\sum_{j=1}^{\log n -1} \frac {4^t} {4^{\log n} {t^2} }$

= $n^2\sum_{j=1}^{\log n -1} \frac {4^t} {n {t^2} }$
= $n\sum_{j=1}^{\log n -1} \frac {4^t} { {t^2} }$

Using wolfram and wkipedia, the sum comes out to $Li2(4) -n Lerch Function(4,2,\log (n)-1)$

I could simple assume this is constant and that would prove my bound to be $O(n)$ as the master theore suggests, but I ahve no proof to bound the Lerch and dilogarithmic function.

Another substitution I tried was

$$ t=4^j (\log n -j)^2 $$
which gives me
$$n^2 H(n) - H((\log n)^2) $$ where $H(n)$ is the nth harmonic number
I again could not reach a bound for this, besides $\log (n) - \log (\log n) $
which is quite different from my first substitution.

If someone could help me with what error I'm making, or why the substitutions yield different results that would be great.

To make things a bit simpler, let us assume that we use base 4 logarithm. Following your steps, for $n = 4^k$ and $T(1) = 0$ we get
$$
\begin{align*}
T(n) &= \frac{n^2}{(\log_4 n)^2} + 4\frac{(n/4)^2}{(\log_4 n-1)^2} + 16\frac{(n/16)^2}{(\log_4 n - 2)^2} + \cdots \\ &=
\frac{n^2}{(\log_4 n)^2} \left[ 1 + \frac{1}{4(1-1/\log_4 n)^2} + \frac{1}{16(1-2/\log_4 n)^2} + \cdots \right].
\end{align*}
$$
Let us now use the series expansion
$$
\frac{1}{(1-x)^2} = 1 + 2x + 3x^2 + 4x^3 + \cdots.
$$
Substituting this in the expression above, we get
$$
\begin{align*}
\frac{T(n)}{n^2/\log^2_4n} &= 1 + \frac{1}{4} + \frac{1}{16} + \cdots \\ &+
2\left[ \frac{1}{4\log_4 n} + \frac{2}{16\log_4 n} + \cdots \right] \\ &+
3 \left[ \frac{1}{4\log_4^2n} + \frac{2^2}{16\log_4^2n} + \cdots \right] + \cdots \\ &\approx \frac{4}{3} + \frac{8/9}{\log_4 n} + \frac{20/9}{\log_4^2 n} + \cdots
\end{align*}
$$
The error in the approximation is polynomially small: for example
$$
\sum_{k=0}^{\log_4 n-1} \frac{1}{4^k} = \frac{4}{3} - \frac{4/3}{4^{\log_4 n}} = \frac{4}{3} - \frac{4/3}{n}.
$$
The error is somewhat larger for the other summands, but still polynomially small. Taylor's theorem (or direct calculation) shows that if we truncate the series for $1/(1-x)^2$ after the term $(d+1)x^d$ then we get an error of $O(x^{d+1})$. Altogether, this shows that the following asymptotic statements hold:
$$
\begin{align*}
T(n) &= \frac{4}{3} \frac{n^2}{\log_4^2 n} + O\left(\frac{n^2}{\log_4^3 n}\right), \\
T(n) &= \frac{4}{3} \frac{n^2}{\log_4^2 n} + \frac{8}{9} \frac{n^2}{\log_4^3 n} + O\left(\frac{n^2}{\log_4^4 n}\right), \\
T(n) &= \frac{4}{3} \frac{n^2}{\log_4^2 n} + \frac{8}{9} \frac{n^2}{\log_4^3 n} + \frac{20}{9} \frac{n^2}{\log_4^4 n} + O\left(\frac{n^2}{\log_4^5 n}\right), \ldots \\
\end{align*}
$$


Question about the definition of complexity class oracles If $B$ is a complexity class, then the class $P^B$ (for example) is defined as the set of problems that can be run in polynomial time, given an oracle to every problem in $B$.  That's what they told me in my Theory of Computation class, anyways.

Per this definition, it seems to me that $P^P$ captures every decidable language.  Here's why I think that:

Let $M$ be a TM that always halts.  On input $x$, construct a new machine $M'$ that: (1) checks to see if the input is equal to $x$, (2) if its input is $x$ then it simulates $M$ on $x$, (3) if its input is not $x$ then it instantly rejects.

This new machine $M'$ runs in $O(n)$ time, so in the class $P^P$, we have an oracle to it.  We can now consult this oracle to find out if $M'$ accepts $x$, and we learn in only $O(n)$ time whether or not $M$ accepts $x$.  So we have an algorithm that decides $M$ and runs in $TIME(O(n))$, given an oracle to some countable set of problems in $TIME(O(n))$ (e.g. every $M'$, constructed with respect to every possible finite bitstring $x$).

What am I misunderstanding?

Here is an attempt to clarify my confusion.

This is the model that I think we are using:

There are three tapes usable by the Oracle Turing Machine: a standard worktape, an "oracle input tape," and an "oracle machine tape."  The OTM can enter a special state where it takes the machine description written on the oracle machine tape, performs a magical 1-step simulation of that machine on input equal to the contents of the oracle input tape, and then writes down a $1$ or a $0$ on the worktape according to the results of the simulation.

Define: A language $L$ is in $P^P$ if there is an OTM that decides L and always halts in $p(n)$ steps on length $n$ input (for some polynomial $p$), and also for every Turing machine description $M$ used by the OTM, there exists a polynomial $q$ such that $M$ halts in $q(n)$ steps on input $M$.

Then my argument is valid, I think: every machine that we write down runs in linear time overall (even though the constant associated with that machine will grow very quickly for increasingly-long inputs).

This wouldn't be a problem if we flipped the quantifiers (i.e. "there exists a polynomial $q(n)$ such that every machine description $M$ used by the OTM halts in $q(n)$ steps).  But I'm not sure that still describes $P^P$...

Either you're misunderstanding what they said, or you're not misunderstanding anything.

If $B$ is a complexity class, then the class $P^B$ is defined as $\bigcup_{L \in  B} P^{L}$. (That applies even when $B$ does not have a complete problem.)

If $B$ is a complexity class and $K$ is complete for $B$ under polynomial-time Turing reductions, then $P^B = P^K$.

Proof: If those hypotheses hold then for all languages $L$ in $B$, by using the reduction to simulate oracle queries to $L$, one has $P^L \subseteq P^K$.

Thus, if those hypotheses hold then $P^K \subseteq \bigcup_{L \in B} P^{L} = P^B  = \bigcup_{L \in B} P^{L} \subseteq \bigcup_{L \in B} P^{K} = P^K$.

Therefore, if those hypotheses hold then $P^B = P^K$.


Proof that pseudorandom generators implies one-way function I'm reading proof on Wikipedia that the existence of pseudorandom generators implies the existence of one-way functions.
My understanding is that pseudorandom generators are defined as

A function $G_l:\{0,1\}^l\to\{0,1\}^m$ is a pseudorandom generator if all of the following hold:
a. $l<m$
b. $G_l\in\mathbf P$
c. For any polynomially-sized circuit $C$,
$$ \left|\Pr_{x\sim\text{Unif}\{0,1\}^l}[C(x)=1]-\Pr_{x\sim\text{Unif}(D)}[C(x)=1]\right|<\text{poly}(n),
 $$
where $D$ is the image of $G_l$.

and that one-way functions are defined as:

A function $f:\{0,1\}^n\to\{0,1\}^n$ is a one-way function if all of the following hold:

$f$ is invertible
$f\in\mathbf P$
For any polynomially-sized circuit $C$,

$$
 \Pr[f(C(f(x))=f(x)]<\text{poly}(n).
 $$

Question 1: Looking at definitions for one-way functions above, I assume that the notation $f:\{0,1\}^n\to\{0,1\}^n$ refers to a family of functions $\mathcal F=\{f_n\}_{n\in\mathbf N}$, where each $f_n$ is an invertible function $\{0,1\}^n\to\{0,1\}^n$. (And analogously for the defintion of pseudorandom generators.) Is this assumption correct?
The proof that pseudorandom generators implies one-way functions given on the Wikipedia page starts off with:

Consider a pseudorandom generator $G_l:\{0,1\}^l\to\{0,1\}^{2l}$. Let's create the following one-way function $f:\{0,1\}^n\to\{0,1\}^n$ that uses the first half of the output of $G_l$ as its output. Formally,
$$
f(x,y)\to G_l(x)
$$

Question 2: What exactly is this saying? It looks like $|x|+|y|=n$, so I'll assume for now that $|x|=l=n/2$, in which case $G_l(x)$ outputs a string of length $2l=n$.  But if $G$ ignores $y$, how can $f$ be injective?
Thanks!

One-way functions need not be invertible. A one-way function which is invertible is known as a one-way permutation.
Here is the definition of one-way function from Goldreich's primer:

A function $f\colon \{0,1\}^* \to \{0,1\}^*$ is one-way if it can be computed in polynomial time, and is hard to invert: for every polynomial time algorithm $A$, $$ \Pr_{x \in \{0,1\}^n}[f(A(f(x),1^n))) = x] \text{ is negligible}. $$

(A function $\epsilon(n)$ is negligible if $\epsilon(n) = O(1/n^k)$ for all $k$.)
As you can see, there is no promise that $|f(x)| = |x|$; it could be that $f(x)$ is longer than $x$, or even shorter than $x$ (which is why we feed $A$ the auxiliary input $1^n$, an arbitrary string of length $n$).


Algorithm to find the first person in front of $A$ that is shorter than $A$ We have an array of $n$  positive integers $a_0,a_1\dots a_{n-1}$ and let $a_n=0$.

I need to build an array $b_0,b_1\dots b_{n-1}$ such that $b_i$ is the first integer larger than $i$ with $a_{b_i}\leq a_i$.  (Note that there is no requirement that the $b_i$ be distinct.)

Does anybody know if this can be done in reasonable time? (say $\mathcal O(n\log n)$ for example)

There is an $O(n)$ solution for building such array using stack.

Starting with a brute force algorithm, you can traverse the array from right to left and for each element in the array, try all elements to the right of it until finding a smaller number. That would be $O(n^2)$.

To get an $O(n)$ solution, instead of each element having to look at all the elements to the right of it. We would just maintain a list of special elements by noticing that whenever a number at position $x$ sees a larger number to the right of it (at position $y$ where $y$ > $x$), the larger number is of no use anymore.

To prove that, we can assume for contradiction that element at position y was the $b_i$ of some future number. That means that $a_y < a_i$ but since $a_x < a_y < a_i$ and $x$ is between $i$ and $y$, then element $x$ would have been $b_i$ instead. Hence, a contradiction.

The algorithm to get $b_i$ would be to do the same as the brute force, but instead of just searching for a smaller element to the right, we will delete the larger elements that we meet on our way and break as soon as we find a smaller number. Simulating this efficiently can be done using a stack, where each $i$ keeps popping elements while the top of the stack is larger than $a_i$. The top of the stack after the pops will be $b_i$. $a_i$ is then pushed to the stack so that it will be seen by the next elements.

Complexity

The algorithm may still look as an $O(n^2)$ algorithm, but looking at the number of times that an array element is checked, we will find that each element is looked at for a constant number of times, since it is either pushed (once), popped (also once) or selected as $b_i$ (total of n for all a $b_i$). So the sum of operations is $O(n)$ for the algorithm.


Turing Machine that triples a unary format number? I managed to figure out how to double a unary format number however I have had no such success in tripling it. An input tape would be of the following format Λ111Λ and the output would be like Λ111Λ111111111Λ with the tripled number coming directly after the initial input tape. Any help would be greatly appreciated.

Copy the number once (as you have done already). Mark the spot between the original and the copy with a new letter. Now run again the copy, but stop copying once you see the letter $\land$.
That is, copy $\land 111\land$ into $\land 111 \#  111 \land $. Now copy again, while thinking of $\#$ as the new beginning of the tape. You will get $\land 111 \# 111 \# 111 \land$. After that, replace all $\#$ with $\land$ to get: $\land 111\land 111\land 111\land$
Notice that this process can be done any number of times, meaning that you can clone the input any number of times you would like!

Also, as a general "trick" for such problems, try introducing either a new letter to the alphabet (it usually helps create edge cases that you need to solve), or to meddle with an existing machine's states (such as adding an index into their states, etc')


Consequences of a language that hides his lower level rappresentations I know it's a silly scenario but I wolud like to know if it's relevant and maybe there are some sort of theory/studies on it or it's merely a non-sense situation.

Immagine a language much close to a Turing machine that is compiled in an higher language (let's say C). This language can accept an integer as input, but using his syntax i don't have any access to his internal rappresentation of this integer, that is the integer wolud be located in one single cell and the only operation I can do on a cell are:

 +1, -1, copy/paste from a register, set to 0, chek if it's non-zero.

Now if I want to output the sign of the integer I would create a copy of it so that in one cell the value gets incremented and in the other gets decremented. Until I reach 0 and then I would stop and correctly tell the sign.

The interesting part is that under the hood, this program would surely use the information of the sign of the integer to execute +1 and -1 correctlty...

So I'm using operations that would use information x to obtain information x... Normally I would have access to the rappresentation of the integers and to check the sign consists in looking at one particular bit. But in this case some information is hidden from me.

It reminds me of solving the limit sin(x)/x as x goes to 0 by de l'Hopital rule... It's a logical fallacy because that limit is required in order to differentiate sin(x)

Could there be situations when this is not generated explicitly by us and it's inevitable? Has it more profound consequences?

There's plenty of precedent for this in real programming languages. One obvious example is pointers/references, which are internally just an address (probably). The language/runtime must know this, but in managed languages you don't have access to that.

One of my favourite examples of "useful information that must be there but is hidden" is in C++. You can allocate an array of objects using the new[] operator and deallocate them with delete[]:

Object* objs = new Object[25];
// do stuff to objs
delete[] objs;

C++ does not provide a way to obtain the number of elements in array. However, the delete[] operator must have access to this information, because it needs to execute the destructors of those elements.


When does an extendible 1:1 p.c. function have a 1:1 computable extension? A partial computable function $\varphi_e$, defined on a c.e. set $W_e$, is called extendible if there exists some computable function $f$ which extends $\varphi_e$, i.e. $\varphi_e(W_e) = f(W_e)$.
My question is what are the conditions for a p.c. function $\varphi_e$ to have an injective extension.

So far I have found some necessary conditions:

Obviously, $\varphi_e$ itself should be injective.
$|\overline{W_e}| \leq |\overline{\varphi_e(W_e)}|$. Because $f(\overline{W_e})$ should have no intersection with $f(W_e) = \varphi_e(W_e)$, so $f(\overline{W_e}) \subseteq \overline{\varphi_e(W_e)}$.
This rules out $\varphi_e(x) = x/2$, defined on even numbers. And also any other surjective partial function.

I couldn't manage to find a sufficient condition yet.

Here is an example of an extendible, non-injectively-extendible p.c. function $\psi$ which nonetheless satisfies your conditions (and I think indicates in general that any sufficient condition will be quite complicated):

Let $\langle\cdot,\cdot\rangle$ be your favorite computable bijection $\mathbb{N}^2\rightarrow\mathbb{N}$. We define $\psi$ as follows (with the role of "$2^k$" being  merely to control the range of $\psi$, and consequently show that just demanding that the range be "small" won't yield a sufficient condition):

Suppose $k$ is even. Let $a_k, b_k$ be the unique natural numbers such that $k=2\langle a_k,b_k\rangle$. We define $\psi(k)$ to be $2^k$ if $\varphi_{a_k}(a_k)$ halts strictly before $\varphi_{b_k}(b_k)$ does, and we let $\psi(k)$ be undefined otherwise.
Suppose $k$ is odd. Let $a_k, b_k$ be the unique natural numbers such that $k=2\langle a_k,b_k\rangle$+1. We define $\psi(k)$ to be $2^{k-1}$ if $\varphi_{b_k}(b_k)$ halts strictly before $\varphi_{a_k}(a_k)$ does, and we let $\psi(k)$ be undefined otherwise.

$\psi$ is clearly 1-1, p.c., of co-infinite range (indeed, the range is "computably coinfinite" in the sense that the complement of the range contains an infinite computable set; in jargon, the range of $\psi$ is non-simple), and extendible: it is extended by the function $x\mapsto 2^{2floor({x\over 2})}$. However, it's easy to show that it's not extendible to a 1-1 total computable function, essentially since such an extension would have to always guess correctly whether one program halts before another does.


Bayes net: algorithm to calculate joint distribution? I recently started studying bayesian networks and I am now implementing an exact inference algorithm: enumeration. I am aware of the complexity and inefficiency of this method but I want to fully understand it.

As far as I know there are three basic 'steps':

Use Bayes Rule on query / evidence variables.
Use summation for hidden variables.
Calculate joint distribution.

I've tried a recursive approach as suggested in most documentation of the topic, here's the algorithm I'm using (with python):

'''
bayesnet is an instance of a class that hold a bayes net
queryVars is a list of tuples (varname, boolean) to describe the state of a variable, eg. ('B', True)
evidenceVars is a list of tuples (varname, boolean)
'''
def enumerate_method(bayesnet, queryVars, evidenceVars = []):
    #Check evidence vars to apply bayes rule
    if len(evidenceVars):
        return enumerate_method(queryVars + evidenceVars) / enumerate_method(evidenceVars)
    #Check if there are hidden variables left given the query variables
    if len(bayesnet.hiddenVariables(queryVars)):
        #For every hidden variable
        for hiddenvar in bayesnet.hiddenVariables(queryVars):
            return enumerate_method(bayesnet, queryVars + [(hiddenvar, True)]) + enumerate_method(bayesnet, queryVars + [(hiddenvar, False)])

    #Calculate joint distribution of queryVars?

    return bayesnet.joint(queryVars)

I am still unsure of how to implement the joint distribution calculation. My BayesNet class stores, for each variable, a name, a list of parents and a list of tuples with the probability given its parents. The bayes network is fully described.

I guess I have to use the chain rule, but I have trouble with that as it brings new expressions with evidence variables that I do not have.

Am I moving on the right direction? If so, could you provide a suggestion on how to calculate the joint distribution.

You already have the result of the chain rule - this is your networks topology basically. Now you need to compute the joint. I would start from "root nodes", i.e. nodes with no parents, and proceed forward (I'm sure you can go the other way too, just more pain):

Each of the "root nodes" has its "own" joint already. I.e. if your network was just one root node, you're done - just output the CDF.
Now suppose your network is two "root nodes". What's the joint? Suppose you have two boolean variables A,B with values a,~a,b,~b. The joint is:

(a,b, P = a*b)

(a,~b, P = a*~b)

(~a, b, P = ~a*b)

(~a,~b, P = ~a*~b)
This looks like a cartesian product. I.e. you have a cartesian product in the variables, and the value is the product of terms. This is the simple version of a "factor product" - where factor is some unnormalized discrete distribution.
In general the product of two factors will encounter variables that are common to the factors. Do the cartesian product and throw out all tuples that match on the common variables - this is the join in databases. Compute the probability as before.
Now you have the factor product. Just use on your graph to compute the joint. Be careful with paths that separate and then join back in the graph.


Where can I find information on Data Structures used in common software? As part of a course I am teaching on Data Structures, I want students to research and present the use of Data Structures in popular software/services. However, basic googling shows me that this information is not so readily available.

Can someone point me to the right resources that I may share with the students as a starting point for their research?

EDIT

Judging from the received replies, the original question is not sufficiently clear so I am adding more details.

I am looking for resources of the type that state, for example, that service-x uses data-structure-a in order to perform functionality-y because of property-b. This is the ideal case. Other resources that provide similar information are also welcome.

Off the top of my head:

Every modern operating system uses balanced binary search trees to implement the virtual memory map of a process. Windows uses splay trees, Linux and OS X use red-black trees, and Solaris uses AVL trees. They do this because the operating system needs to store the virtual memory map in order (by virtual address), to allow for fast insertion and removal, and to look for unused regions where it could allocate space.

Many modern 3D games (e.g. anything which uses a recent version of Unreal Engine) use octrees to determine what objects are visible to the camera. They do this because it's quite efficient to calculate what nodes overlap with a camera's view frustum.

Many (if not most) routers use radix trees to implement routing tables. They do this because it is often the prefix of a network address (i.e. the most significant bits) which is important, not the whole key. Moreover, lookup takes time which only depends on the size of the address, not the number of routing table entries, which makes predicting timing easier.

Hash tables are, of course, used everywhere. Antivirus software uses it to perform lookups in its database of known malware, word processors use it to perform spelling checks, etc.

Graph data structures are used by spreadsheets to implement evaluation. Think of each occupied cell as a node, and draw an arc between to cells if the value of one directly depends on the value of the other. When an entry changes in a cell, the graph is traversed to determine which cells need updating based on that change.


Proving preservation under substitution System F Omega I am going over the proofs for the simply typed lambda calculus in the book "Types and Programming languages" by Benjamin Pierce. I am trying to find inspiration for the similar proofs for System F Omega. When I was going over the preservation under substitution proof for the simply typed lambda calculus  I was a bit puzzled.

The hypothesis of the proof is:

  If  $\Gamma ,x:S \vdash t:T $ and $\Gamma \vdash s:S$ then $\Gamma \vdash [x \mapsto s]t : T$

So far I understand the proof quite well, but for the case $T-Abs$ I'm a bit lost. The rule is shown below.

$$
  \dfrac{\Gamma ,x:T_1  \vdash t_2 : T_2}
        {\Gamma \vdash \lambda x:T_1 . t_2 : T_1 \rightarrow T_2}
$$

To prove the hypothesis for this case we use the previously proven lemmas weakening and permutation.

We assume that in this proof  $x \neq y$ and $y \notin FV(s)$.

First we list the givens:

$t = \lambda y:T_2 . t_1$
$ T = T_1 \rightarrow T_2$
The first subderivation: $\Gamma ,x:S,y:T_2 \vdash t_1 : T_2$
The second subderivation: $\Gamma \vdash s:S$ by hypothesis.

Step 1 The first step we take is using permutation on the first sub-derivation, yielding: $\Gamma ,y:T_2,x:S \vdash t_1 : T_2$. The reason why this happens is a bit unclear to me. I am assuming that the actual order of the extensions of $\Gamma$ matter for the third step.

Step 2 The second step, which is the one that is unclear to me, is applying weakening to the second sub-derivation: changing $\Gamma \vdash s:S$ into $\Gamma ,y:T_2\vdash s:S$. The reason that I find this odd is that this new form of the sub-derivation is not used anywhere in the proof.

Step 3: By the induction of our hypothesis we know that $\Gamma ,x:S,y:T_2 \vdash t_1 : T_2$ implies $\Gamma ,y:T_2 \vdash [x \mapsto s]t_1 : T_2$. And since we know that, we can apply the $T-Abs$ rule. Since that is what it basically says.  We wrap the given sub-derivation in a lambda and we have to remove the $y:T_2$ from the context because it is now introduced by the abstraction we constructed:

$$\Gamma \vdash \lambda y:T_2 . [x \mapsto s]t_1 : T_1 \rightarrow T_2$$

And finally we can move the substitution outside because we assumed that $x \neq y$ and $y \notin FV(s)$.

$$\Gamma \vdash [x \mapsto s]\lambda y:T_2 . t_1 : T_1 \rightarrow T_2$$

And this is exactly what we had to prove.

The problem I have with the second sub-derivation is that we nowhere in the prove actually used it. We never relied on that fact. Any input would be highly appreciated.

Throughout $y$ should have type $T_1$ instead of $T_2$.

Let us be more careful about step 3. We are going to apply the following induction hypothesis:

  If $\Gamma, y : T_1, x : S \vdash t_1 : T_2$ and $\Gamma, y : T_1 \vdash s : S$ then $\Gamma, y : T_1 \vdash [x \mapsto s] t_1 : T_2$.

After that we will use abstraction to get $\Gamma \vdash (\lambda y : T_1 . [x \mapsto s] t_1) : T_2$, and finish the proof by observing that $(\lambda y : T_1 . [x \mapsto s] t_1) = [x \mapsto s](\lambda y : T_1 . t_1)$.

So let us make sure that the induction hypothesis is applicable:

First we need $\Gamma, y : T_1, x : S \vdash t_1 : T_2$: because $\Gamma, x : S \vdash (\lambda y : T_1 . t_1) : T_1 \to T_2$ by inversion we obtain $\Gamma, x : S, y : T_1 \vdash t_1 : T_2$ and then we use exchange to get $\Gamma, y : T_1, x : S \vdash t_1 : T_2$. This is your step 1. (The exchange is valid because types are non-dependent in this argument.)
Second, we need $\Gamma, y : T_1 \vdash s : S$: we already have $\Gamma \vdash s : S$. By weakening we obtain $\Gamma, y : T_1 \vdash s : S$, this is your step 2.

Supplemental: It seems unclear how induction works. To perform a proof by induction we need to specify what the induction is on. In this case the induction is on the derivation of $\Gamma, x : S \vdash t  : T$. Thus, we have to look at all the possible cases of deriving $\Gamma, x : S \vdash t  : T$. Each inference rule gives us one case, and we've just discussed the case of $\lambda$-abstraction. Each case has its own induction hypotheses, one for each premise of the rule.

Let me give you a simpler example. Suppose we only had the following typing rules:

Variables: $$\frac{(x : T) \in \Gamma}{\Gamma \vdash x : T}$$
Pairs: $$\frac{\Gamma \vdash e_1 : T_1 \qquad \Gamma \vdash e_2 : T_2}{\Gamma \vdash (e_1, e_2) : T_1 \times T_2}$$
First projection: $$\frac{\Gamma \vdash e : T_1 \times T_2}{\Gamma \vdash \mathsf{fst}\,e : T_1}$$

A derivation is a finite tree built from these rules (if you are not clear about that, you should first understand what a derivation is). Suppose we want to show that every derivable judgement has some given property $\phi$. To prove this by induction on the derivation, we need to show three things:

Variable case: if $(x : T) \in \Gamma$ then $\Gamma \vdash x : T$ has property $\phi$.
Pair case: if $\Gamma \vdash e_1 : T_1$ has property $\phi$ and $\Gamma \vdash e_2 : T_2$ has property $\phi$ then $\Gamma \vdash (e_1, e_2) : T_1 \times T_2$ has property $\phi$.
First projection case: if $\Gamma \vdash e : T_1 \times T_2$ has property $\phi$ then $\Gamma \vdash \mathsf{fst}\, e : T_1$ has property $\phi$.

The first case has no induction hypothesis, it is a base case. This is so because the corresponding inference rule has no premises (only the side condition $(x : T) \in \Gamma$). The second case has two induction hypotheses, namely that $\Gamma \vdash e_1 : T_1$ has property $\phi$ and that $\Gamma \vdash e_2 : T_2$ has property $\phi$. This is so because the corresponding inference rules has these two premises. The third case has one induction hypothesis, and you should be able to see why that is if you understood what I am saying.


Find Big O using Iteration I am trying to find Big O of this formula: $T(n)=T(n-1)+2n$ by using iteration however I am stuck on a step.

$T(n)=T(n-1)+2n$ I then plugged $T(n-1)$ into the equation so $T(n-1)=T(n-1-1)+2(n-1)$ which then I got $T(n)=T(n-2)+2(n-1)+2n$. $T(n-2)$ gives $T(n-3)+2(n-3)$ which plugging it back in gives $T(n)=T(n-3)+2(n-3)+2(n-1)+2n$. I substituted the following $2(n-3)+2(n-1)+2n$ into a summation that gave me $\sum_{i=0}^k 2(n-i)$$=-(k+1)(k-2n)$. I am not too sure how I should continue.

You're almost there. You correctly have
$$\begin{align}
T(n) &= T(n-1)+2n\\
     &= [T(n-2)+2(n-1)] + 2n = T(n-2)+2(n-1)+2n\\
     &= T(n-3)+2(n-2)+2(n-1)+2n\\
     &= T(n-4)+2(n-3)+2(n-2)+2(n-1)+2n
\end{align}$$
and in general,
$$
T(n)=T(n-j)+2(n-j+1)+2(n-j+2)+2(n-j+3)+\dotsm+2n
$$
Now all you need is the base value for the recurrence. Let's suppose that it was $T(0)=0$ (for the big-O estimate it really wouldn't matter if we had had, say $T(1)=3$ as our base).

To get to the base case, $T(0)$, we'd then need $n-j=0$. In that case, we'd have
$$
T(n)=T(0)+2(1)+2(2)+2(3)+\dotsm+2n= \sum_{k=1}^n2k=2\cdot\frac{n(n+1)}{2} = O(n^2)
$$


Whether the 2 minimum spanning tree of same graph contains the lowest edges in common? If two minimum spanning trees on the same graph only have 2 edges in common, then those two edges must be the lowest costs edges in the graph.

True/false? and why?

Because according to me if there is a only edge which connects 2 subgraphs then that will be included in the MST whatever might be the value. So according to me the answer is False but the solution says the answer to be true. Please explain.

To prove that it's false you just need a counter-example.

The two MST can be

Noticed that the only two common edge is not the lowest cost edge. Hence the statement is FALSE.

However, if all the edges have unique weights, the answer is TRUE.

  Any MST of a size larger than 1 contains the smallest and the second
  smallest edge.

The smallest edge must be in any MST. Suppose not, we can always include it and form a cycle, and remove the largest edge in the cycle to form a smaller tree.

The second smallest edge must also be in any MST (of the size larger than 1). Suppose not; we can include it and form a cycle. Noticed that a cycle must have at least 3 edges. Hence, the largest edge that is removed must be larger than the second smallest edge. Hence we also form a smaller tree.

Since any MST must contain the 2 smallest edge, when they only have 2 edges in common, it must be both of them, which are also the lowest costs edge in the graph.


Generate a dataset for binarization of text in images I want to generate a dataset of binarized masks of scene-text images to use them to train a model. I have no previous experience in dataset synthesization especially related to font-rendering.

Can anyone provide me some links to articles/blogs/related-github-projects?

Start with the following paper, and use it to seed a literature search using the usual methods.

Detecting Text in Natural Scenes with Stroke Width Transform.    Boris Epshtein, Eyal Ofek, Yonatan Wexler.  CVPR 2010.


Is "flops" a reliable measure of deciding computational capacity? Is "flops" a reliable measure of deciding computational capacity? If we do matrix multiplication and matrix addition of the same size of matrix, do the flops remain the same?

Referring to question https://stackoverflow.com/questions/329174/what-is-flop-s-and-is-it-a-good-measure-of-performance

I am curious to know if I do a 100x100 matrix multiplication and matrix addition, will the FLOPS remain the same? Can I say time required by the processor (and hence FLOPS) remain same regardless of operation?

Can someone also comment on how theoretical maximum FLOPS of a processor are determined. And if FLOPS is taken as standard measure of performance, then can someone use an algorithm that will always be highly efficient but not useful in scientific computing?

Much computing is shuffling data around, from memory to CPU(s) and viceversa, from disk to memory, and so on. Performance could well be determined by non-processing needs. If there are several CPUs involved (many supercomputers really do the computing on graphics cards, which are massively parallel SIMD computers), jobs that can't be sped up by processing separate data streams with the same instructions will go much slower than extensively studied and paralellized to death computations like massive matrix operations.

So the answer is no, raw FLOPS aren't a good measure of performance. Again, the only reliable performance measure for your specific problem is the performance on it. "Performance" isn't a number, it is a vector with multiple independent aspects, and the requirements of your problem are also a vector, in the same dimensions. How well they match over a wide range of possible problems to a particular machine can't be reduced to a single number.


Machine Learning - Support Vector Machines I'm looking for good resources regarding Support Vector Machines, or suggestions where to start learning SVM.

Already used references:

Stanford ML course by Andrew Ng is great place to star
A Tutorial on Support Vector Machines for Pattern Recognition, Burges, 1998
SVM tutorials
Neural Networks and Learning Machines, Third Edition  Learning with Kernels - SVM, A. Smola

There are tons of tutorials for various backgrounds. What is your background?
Here is one list of tutorials: http://www.kernel-machines.org/tutorials


Artificial intelligence - bridge and torch problem I am doing a artificial intelligence course as part of my computer science degree.

I am stuck on a question about searching. The question is a version of the Bridge and torch problem.

Five people need to walk from this side to the other side of a bridge at night. The bridge is not in a very good condition and will hold at most 3 people at a time. They discover that they only have one torch. This means that after one,two,or three people have crossed the bridge, somebody (one, two, or three people) will have to come back with the torch so that the next persons can cross
safely. Each of the five people (Anna, Brett, Charles, David, and Ernest) take a different time to cross the bridge. Whenever 3 people cross they can only go as fast as the slowest person in the group. Since the torch has limited battery life they need to figure out which is the fastest way to get all 5 of them across the bridge. The times each take to get across are:

1. Anna: 5 Minutes
2. Barry: 7 Minutes
3. Charles: 1 minute
4. David: 2 minutes
5. Ernest: 9 minutes

I am asked how big the search space is of the problem. This is where I am getting stuck. There are 5 people, and two sides of the bridge where they can be. There is also a variable amount of people that can cross at a time (1-3 people).

My state representation is $\{ A, B, C, D, E \}$ representing the first letter of each person, with this being the set of people on the left side of the bridge. Hence, my goal state is $\{ \}$ - all people on the right side of the bridge.

I've also worked out the sequence of moves that leads to the optimal solution - my issue is just the size of the search space.

How do I go about calculating the size of the search space?

Before you can calculate the size of the [thing], you need to decide exactly what the [thing] is.

In this case, you've decided that the state space is the set of people on the left side of the bridge. The people on the left can be any subset of the people, so any subset of $\{A, B, C, D, E\}$. The number of subsets of an $n$-element set is a well-known fact you should recall from your discrete mathematics classes.

Note that people moving across the bridge is not part of the state: it's a transition from one state to another (also known as an action). If you included that information in the state, you'd just make the search take longer.  For example, instead of having the state "$A$, $B$, and $E$ are on the left" transitioning to "$A$ and $E$ are on the left", you'd have it transition to "$A$ and $E$ are on the left and $B$ is on the bridge", which would then have no choice but to transition to "$A$ and $E$ are on the left" (and nobody is on the bridge). Adding a bunch of states that have only one successor is only going to slow down your search.


What is alternative parenthesizations? I'm a person using english as the second language and reading CLRS book at a slow pace due to my poor english. I have a problem with understanding the meaning of the word 'alternative'. In page 303 on CLRS, says:

  we should convince ourselves that exhaustively checking all possible parenthesizations does not yield an efficient algorithm.Denote the number of alternative parenthesizations of a sequence of n
  matrices by P(n). Since we can split a sequence of n matrices between
  the kth and (k+1)st matrices for any k = 1,2,...,n-1 and then
  parenthesize the two resulting subsequences independently, we obtain
  the recurrence ...(omitted)

What is the word 'alternative parenthesizations'? is this word equivalent to the 'all possible parenthesizations' in the above block quote? searching dictionary for the word 'alternative' is not helpful to me.
Thank you in advance.

Depending on the context, "all alternative parenthesizations" means either "all possible parenthesizations" or "all possible parenthesizations apart from the one we were just talking about."

The sense of the word "alternative" being used here is "one of two or more available possibilities."


Best case "skew height" of an arbitrary tree Given an arbitrary binary tree on $n$ nodes, choose an assignment $A$ from each parent to one of its children (the "favored child" as it were). We define the skew height of the tree as $H_A(\mathsf{nil})=0$ and $H_A(\mathsf{node}\;a\;b)=\max(H_A(a), H_A(b)+1)$ if $A(\mathsf{node}\;a\;b)=a$ is the favored child and symmetrically $\max(H_A(a)+1, H_A(b))$ if $b$ is favored.
The question is: For a fixed tree $T$, what is the minimum skew height over all assignments? I would like to get an asymptotic bound on $f(n)=\max_{|T|=n}\min_AH_A(T)$.
Other variations on this problem I am interested in are when the trees are not binary (but there is still one favored child and all others add one to the height), and when there is sharing (i.e. it is a dag), which doesn't affect the height computation but allows for much wider "trees" while staying under the $n$ node bound.
The obvious bounds are $f(n)=\Omega(\log n)$ and $f(n)=O(n)$. My guess is that $f(n)=\Theta(\log n)$ for binary trees, and $f(n)=\Theta(\sqrt n)$ for dags (with some kind of grid graph as counterexample).

For a binary tree, let $H(T)=\min_AH_A(T)$, where $A$ ranges over all favored-child assignments of $T$. Call $H(T)$ the skew height of $T$.
Here is a simple observation. The skew height of a perfect binary tree of (ordinary) height $n$ is $n$, too.

For a binary tree $T$, an edge is called a passing edge if one of the endpoints has exactly one child. We call a binary tree $M$ a b-minor of $T$ if $M$ can be obtained by removing a subtree or contracting a passing edge repeatedly.
For a binary tree $T$, what is its skew height? Here is a visual characterization.
The skew height of $T$ is the maximum (ordinary) height of all perfect binary trees that are also b-minors of $T$. Intuitively speaking, a binary tree is of skew height $s$ $\iff$ it "contains" a perfect binary tree of ordinary height $s$.
Proof. Since both removing a subtree and contracting a passing edge do not increase the skew height, $$H(T)\ge \max_{M\text{ is a b-minor of T}}\mathsf{height}(M),$$ where $\mathsf{height}(\cdot)$ is the (ordinary) height of a tree. On the other hand, by induction on the number of nodes of $T$, we can show that a binary tree of skew height $s$ must contain a b-minor that is a perfect binary tree of ordinary height $s$. $\quad\checkmark$.

Recall that $n$ is the number of nodes in $T$. We have,
$$H(T) \le \lceil \log_2(n+1)\rceil - 1.$$
Proof. Induction on $n$. The base case, $n = 1$ is easy to verify.
Suppose it is true if the number of nodes in $T$ is smaller than $n$. Consider a binary tree $T$ of $n$ nodes with root node $r$.

If $r$ has only one child, say, $a$, then $$H(T)=H(\text{the subtree rooted at } a)\le \lceil \log_2((n-1)+1)\rceil - 1\le \lceil \log_2(n+1)\rceil - 1.$$
If $r$ has two children, say, $a$ and $b$. Since the number of nodes in the subtree rooted at $a$ and the subtree rooted at $b$ is $n-1$, one of the subtrees has at most $\lfloor (n-1)/2\rfloor$ nodes. WLOG, suppose it is the subtree rooted at $b$. Then
$$H(T)=\max(H(\text{the subtree rooted at }a ) + 1, H(\text{the subtree rooted at } b)) \\
\le \max(\lceil \log_2(\lfloor(n-1)/2\rfloor+1)\rceil,\lceil \log_2((n-2)+1)\rceil -1) $$
Since $$ \lceil \log_2(\lfloor(n-1)/2\rfloor+1)\rceil=\lceil \log_2(\lfloor(n+1)/2\rfloor)\rceil=\lceil \log_2(n+1)\rceil-1,$$
we have $H(T)\le \lceil \log_2(n+1)\rceil-1.$ $\quad\checkmark$

Recall that $f(n)=\max_{T\text{ is a binary tree and }|T|=n}H(T)$. The above section has proved $f(n)\le \lceil\log_2(n+1)\rceil-1$.
On the other hand, the skew weight of the perfect binary tree with $2^m-1$ node is $m-1$. Hence,
$$f(n)=\lceil\log_2(n+1)\rceil-1.$$


How to find all the contiguous subsequence of an array is less than O(N^2) time complexity? I am unable to find product of every contiguous subsequence of an array in less than O(N^2) time complexity.

What actually i want to do is find the number of contagious subsequence whose product of elements is either odd or multiple of 4. The problem here is time i want an algorithm which can make it happen in O(N).

public class PrintAllSubArrays {

    public void printSubArrays(int [] arrA){

        int arrSize = arrA.length;
        //start point
        for (int startPoint = 0; startPoint <arrSize ; startPoint++) {
            //group sizes
            for (int grps = startPoint; grps <=arrSize ; grps++) {
                //if start point = 1 then
                //grp size = 1 , print 1
                //grp size = 2, print 1 2
                //grp size = 3, print 1 2 3 ans so on
                for (int j = startPoint ; j < grps ; j++) {
                    System.out.print(arrA[j] + " ");
                }
                System.out.println();
            }
        }
    }

    public static void main(String[] args) {
        int [] arrA = {1,2,3, 4};
        new PrintAllSubArrays().printSubArrays(arrA);
    }

}

This question is part of a problem from a finished programming contest: "Squared Subsequences" (April 2020)

A contiguous subsequence satisfies your conditions if either it consists only of odd elements, or it contains one number which is a multiple or 4, or it contains two numbers which are multiples of 2. This suggests computing the following quantities:

$X$: Number of contiguous subsequences consisting only of odd elements.
$Y$: Number of contiguous subsequences containing an even element.
$Z$: Number of contiguous subsequences containing no element which is a multiple of 4, and exactly one even element which is not a multiple of 4.

You are interested in $X+Y-Z$.

To determine $X,Y$, it suffices to partition the elements into odd (O) and even (E). If your sequence is of the form
$$
O^{\ell_1} E O^{\ell_2} E \cdots O^{\ell_r} E O^{\ell_{r+1}},
$$
then
$$
X = \sum_{i=1}^{r+1} \binom{\ell_i+1}{2}, \\
Y = \sum_{1 \leq i < j \leq r+1} (\ell_i+1) (\ell_j+1).
$$
In order to compute $Y$ quickly, note that
$$
2Y = \left(\sum_{i=1}^{r+1} (\ell_i+1)\right)^2 - \sum_{i=1}^{r+1} (\ell_i+1)^2.
$$

In order to compute $Z$, we first separate our sequence by breaking at every element which is a multiple of 4. If $Z_j$ is the number of $Z$-type contiguous subsequences in the $j$th subsequence, then $Z = Z_j$. We can write the $j$th subsequence as
$$
O^{\ell_1} E O^{\ell_2} E \cdots O^{\ell_r} E O^{\ell_{r+1}},
$$
just as before. We then have
$$
Z_j = \sum_{i=1}^r (\ell_i+1) (\ell_{i+1}+1).
$$
In total, the algorithm runs in linear time.

Disclaimer: Verify that the formulas work – they might be slightly off, but the general idea should work.


4-digit 5's complement of a negative number Let $n = -13, \ k = -24$

How do I find the 4-digit 5's complement of each number? What would be the result of $n + k$ in complement representation?

I understand how to calculate $n$-digit, 2's complement. I convert it to base 2, invert and add one.

Also, with positive numbers, let's say $n = 13,  \ k = 24$, the 4-digit 5's complement would be $(5542)_{10}$ and $(5531)_{10}$. Correct? What would their addition be?

Let me demystify $b$'s complement.

Let $b \geq 2$ be an integer. Given a $d$-digit integer $x$ is base $b$, we want to find a $d$-digit integer $y$ such that $y \equiv -x \pmod{b^d}$. Why is this useful? Suppose that $z$ is also a $d$-digit integer, and assume that $z-x \geq 0$. Then $z-x \equiv z+y \pmod{b^d}$, and so if we add $z$ and $y$ and ignore the carry, we will get $z-x$ to achieve subtraction.

How do we find $y$, the $b$'s complement of $x$? We take $y =k\times b^d-x= b^d-x = (b^d-1-x)+1$ (with $k\in \mathbb{Z}$, let $k = 1$). Now the representation of $b^d-1$ in base $b$ consists of $d$ digits of $b-1$, so $b^d-1-x$ is obtained by inverting all the digits of $x$ (subtracting them from $b-1$). This is $b$'s complement: the $b$'s complement $y$ of $x$ is obtained by inverting all digits and adding 1.