Dijkstra single-source shortest path $\Omega(n\log n)$?

Let $m$ be the number of vertices and $n$ the number of edges. The best you can get is $O(n + m \log m)$ by using a Fibonacci heap.

A Fibonacci heap allows decreasing the key of an element in amortized constant time. For each edge in the graph, Dijkstra's algorithm executes at most one decrease key operation. All these operations take time $O(n)$ in total. On top of that we have $m$ minimum extractions, which take time $O(m \log m)$ in total. Therefore the final complexity is $O(n + m \log m)$.


Why does the BFR (Bradley, Fayyad and Reina) algorithm assume clusters to be normally distributed around its centroid?

Roughly, the algorithm needs to estimate the probability to assign a point the correct cluster.
So the algorithm add P to a cluster if it is very unlikely that, after all the points have been processed, some other cluster centroid will be found to be nearer to P.
So the algorithm measure the probability that, if P belongs to a cluster, it would be found as far as it is from the centroid of that cluster. To do that, it assumes that the clusters contain normally distributed points aligned with the axes of the used space.


Why is self-information defined the way it is?

Though it is more common to discuss axiomatic derivation of the expectaion of $I(\cdot)$, that it, the entropy function (to which, several sets of axioms exist, see here), for the self information $I(\cdot)$, we usually care about the following properties (as defined by Shannon):

If the event happens with certainty, there is no information in it. Thus, if $p=1$, $I(p)=0$
Furthermore, $I(p)$ must be decreasing with $p$: the more likely the event is, the less information it gives us (or alternatively, the more surprising the event is, the more information its occurrence contains)
As you mentioned, we want that the information of two independent events will add up: $I(p_xp_y)=I(p_x)+I(p_y)$. The event of both $X$ and $Y$ occurring has probability $p_x\cdot p_y$ if independent.

These axioms lead to $I(p) =\log \frac1p$, up to a normalization (e.g., choosing the basis of the logarithm).


Using Yao's principle to find a lower bound

Suppose that there exists a Las Vegas algorithm $A^f$ asking $q(n)=o\big(2^{n/2}\big)$ queries. Let $Q_f\subseteq\{0,1\}^n$ be the random variable which denotes the set of queries raised by the algorithm with oracle $f$.

Sample $f$ from the uniform distribution over the collection of all difference preserving functions, and choose $s\in\{0,1\}^n$ uniformly at random, both independently from your algorithm's coins. Let us now ask what is the probability that there exists $g,g':\{0,1\}^n\rightarrow\{0,1\}^n$ such that $g,g'$ agrees with $f$ on $Q_f$, $g$ is $s$-difference preserving, and $g'$ is not. We denote this probability by $p_A$. Note that if $p_A>0$ then your algorithm cannot respond correctly on all inputs, since there exists $f,s$ such that $f|_{Q_f}$ has both $s$-preserving and non $s$-preserving extensions.

If $f|_{Q_f}$ does not have an $s$-preserving extension, then either there exists $x\in Q_f$ such that $x\oplus s\in Q_f$, or we have $x,y\in Q_f$ with $f(x)=f(y)$. For the first case, Note that $x\oplus s$ is uniformly distributed over $\{0,1\}^n$ and independent of $Q_f$, thus the probability that there exists such $x$ is bounded by $\sum\limits_{x\in Q_f}\frac{|Q_f|}{2^n}\le\frac{q^2(n)}{2^n}=o(1)$. A similar bound is obtained for finding a collision for a random $f$ (the preimage of any element in the range of $f$ is of size 2). Additionally, $f$ is not $s$ preserving with probability $\ge\frac{1}{2^n}$, so we can also (with high probability) find a non $s$ difference preserving extension for $f$.


$f(n) = o(n^c) \rightarrow \exists \epsilon > 0 \ s.t. f(n) = O(n^{c-\epsilon})$

This is false. Consider for example
$$ f(n) = \frac{n^c}{\log n}. $$


The running time of the knapsack problem is $O(n\cdot \min(B,V))$ and is not polynomial, why?

$n$ is not part of the input, $n$ denotes the number of objects in the input.

The input consists of the capacity of the knapsack, a list of objects, each with a value and weight. If there are $n$ objects in the instance then the size of the instance is at least $n$ since each object needs to be represented (with at least one bit). Therefore $n$ is polynomial in the size of the input.

In general, the size of the input (if all weights and values are at most $B$) will be $O(n \log B)$, since there are $n$ objects to represent and representing an object (which is two numbers at most $B$) will take around $2\log B$ bits.


Partially homomorphic encryption (on addition modulo N) not based on prime factorization

Typical ElGamal is homomorphic with respect to multiplication. You can get an additively-homomorphic variant by encrypting $g^m$ instead of $m$. When you decrypt, however, you will get back $g^m$, not $m$. Therefore, you have to solve a discrete log to get $m$ back. This is feasible if we place certain restrictions on $m$ (e.g., the space from which $m$ is drawn is small enough to brute-force the discrete log). Security of ElGamal relates to solving discrete logs.

You can get an elliptic curve variant of ElGamal by using an elliptic curve group instead of a multiplicative group of integers modulo some number. This will get you an additively homomorphic cipher without the need to solve discrete logs. Security of this cipher would relate to solving discrete logs in the elliptic curve group.

I am not aware of alternatives for XOR.


Tight upper bound for forming an $n$ element Red-Black Tree from scratch

To construct a red-black tree on $n$ elements you need to spend time $\Omega(n \log n)$, if you are only allowed to compare the elements' keys.
To see this notice that an in-order visit of any BST visits the nodes in increasing order of their keys.
If you were able to construct a red-black tree in time $t(n) = o(n \log n)$ then you'd also be able to sort $n$ elements in time $O(t(n) + n) = o(n \log n)$, contradicting the lower bound on sorting for comparison-based algorithms.
On the other hand, if the elements are already sorted then you can build a red-black-tree in time $O(n)$: just recursively build a balanced BST, if the last level is incomplete color its nodes as red, and color every other node black.
This requires linear time since the time complexity of the recursive algorithm can be described by the recurrence equation $T(n) = 2T(n/2) + O(1)$.


Turing Machine that halts iff the tape contains at least two '1's

I managed to solve it in the end.
If anyone is interested, I left a diagram of the TM here


Algorithm for deciding alpha-equivalence of terms in languages with bindings

There are several ways to do what you want. One of them is to use a different syntax representation under which $\alpha$-equivalent terms are actually equal. Such representations go under the name nameless or locally nameless syntax. A popular one uses de Bruijn indices. See my blog posts How to implement dependent type theory I, II and III for a blitz introduction to implementing this sort of thing (part III has de Bruijn indices explained).

If you insist on your representation, then we may still secretly use de Bruijn indices, as follows. As we descend inside a subterm during comparison, we keep a list of pairs of bound variables so far encountered. For example, when comparing Forall x1 e1 and Forall x2 e2, we add the pair (x1, x2) to the list and recursively compare e1 and e2. When asked to compare variables x and y, we search down the list: either they must both appear in the same spot (they were bound by the same quantifier) or neither appears and they are equal (they are both free and they are equal).

I am not well-versed with Haskell, but you'd get something like this:

newtype Var = Var Int deriving Eq

data Term = Belong Var Var
          | Bot
          | Imply Term Term
          | Forall Var Term

equalVar :: [(Var,Var)] -> Var -> Var -> Bool
equalVar [] x y = (x == y)
equalVar ((x,y):bound) z w = (x == z && y == w) || (x /= z && y /= w && equalVar bound z w)

equal' :: [(Var, Var)] -> Term -> Term -> Bool
equal' bound (Belong x1 y1) (Belong x2 y2) = (equalVar bound x1 x2 && equalVar bound y1 y2)
equal' bound Bot Bot = True
equal' bound (Imply u1 v1) (Imply u2 v2) = equal' bound u1 u2 && equal' bound v1 v2
equal' bound (Forall x u) (Forall y v) = equal' ((x,y):bound) u v
equal' _ _ _ = False

equal :: Term -> Term -> Bool
equal e1 e2 = equal' [] e1 e2


First, let me be sure u r aware of SET PACKING & SET PARTITIONING Problems

https://slideplayer.com/slide/4514539/

Then, I think ur problem is much easier avoiding the overlapping & the complete coverage constraints.

Going simple, here r some heuristics (think as u solving for max/optimal accepting 30%-40%"deviation from optimality)

1-Pick the max. length partition, then in the next 9th steps choose bet the global max of remaining partitions & the max of those starting after what u have reached so far.... I think that's O(10*5000) let's call it $ O(k n) $

2-Do something similar to $Bucket$ $Sorting$

Divide the partition to 10 smaller partitions(put an overlapping sub partition in its starting point bucket) , then select the max length one in each bucket. Still the same order complexity $ O(k*n) $

Finally, maybe a little bit complicated, but if u want a Theoretical abstraction of ur problem I've just watched this about the $maximum$ $K$ $coverage$ problem and the $Influence$ $maximization$ problem.

If u looked to the interval [0,1] as say M smaller/unit sub intervals being ur target population, and viewed each sub partition as connected to/infleuncing the sub intervals(units) it covers. Then u want to select $K$ (10 in ur case) subpartitions that gives u maximum coverage/influence

https://youtu.be/GqKbx3LCQqE


Solving the recurrence T(n) = 3T(n-2) with iterative method

Note that $3^{n/2-1/2} = \frac{1}{\sqrt{3}} 3^{n/2} = \frac 1{\sqrt{3}} \sqrt{3^n}$. So the $-\frac 12$ indeed becomes a constant factor that is absorbed by the $O()$, but $\frac n2$ in the exponent changes the base and changing the base changes the $O$-class.

The correct answer thus is $T(n) = O(3^{n/2}) = O(\sqrt{3^n})$.


How does Tarjan's pseudocode work (explained to someone familiar with C or Java)?

Table of Contents

I will divide my explanation of Tarjan's pseudocode into the following sections:

Tarjan's If-else Blocks (the -> & | operators)
Assignment and Equality Tests (:= and =)
There is else if, but no else construct
Tarjan's Conditional Assignment Operator := if
Additional Examples of Tarjan's if and := if
5.5.
Tarjan Arrays (or Lists)
Summary of Operators
Tarjan's Double-pointed Arrow Operator (⟷)
Tarjan's do-loops are like C/Java while-loops
Tarjan's Conditional-assignment operator with all false conditions

(1) Tarjan's If-else Blocks

(the operators → and | )

The if-else construct is perhaps the most fundamental control structure in Tarjan's language. In addition to C-like if-blocks, if-else behavior is very nearly built-into in Tarjan's assignments and Tarjan's while loops. Tarjan's arrow operator -> (or →) is a delimiter between the condition of a if-statement and the execution block of an if-statement.

For example, in Tarjan's language we might have:

# Example One
if a = 4 → x := 9 fi

If we partially translate the line of Tarjan code above into C or Java, we get the following:

if (a = 4)
    x := 9
fi

Instead of a right curly braces (as in C and Java) Tarjan ends an if-block with an ALGOL-like backwards spelling of the key-word: fi

If we continue translating our above example, we get:

if (a = 4) {
    x := 9
}

(2) Assignment and Equality Tests (:= and =)

Tarjan takes these operators from ALGOL (later also seen in Pascal).

Tarjan uses = for equality tests, not assignments (so it works like Java ==).

For assignment, Tarjan uses :=, which works like Java =.

Thus, if we continue translating our example, we have:

if (a == 4) {
    x = 9
}

A vertical bar (or "pipe" or |) in Tarjan's language is equivalent to the else if keyword in C or Java.
For example, in Tarjan's language we might have:

# Example Two
if a = 4 → x := 9 |  a > 4  → y := 11 fi

The Tarjan-code above translates to:

if (a == 4) {
    x = 9
}
else if (a > 4)  {
    y = 11
}

(3) else if only and no else construct

Earlier, I covered the basics of if-statements without describing the nuances. However, we will now discuss a small detail. The last clause in a Tarjan-ian if-else block must always contain an arrow (→) operator. As such, there is no else in Tarjan's language, only else if. The closest thing to an else-block in Tarjan's language is to make the rightmost test-condition true.

if a = 4 → x := 9 |  a > 4  → y := 11 | true  → z := 99  fi

In C/Java, we would have:

if (a == 4) {
    x = 9
}

else if (a > 4)  {
    y = 11
}
else { // else if (true)
    z = 99
}

Examples are easier to understand than general descriptions. However, now that we have some examples under our belt, know that the general formal of a Tarjan's if-else construct is as follows:

if condition
    → stuff to do
 | condition
    → stuff to do
 [...]
 | condition
    → stuff to do
fi

The character  | is like if else

The character → separates the test-condition from the stuff-to-do.

(4) Tarjan's Conditional Assignment Operator := if

Tarjan's if can be used two very different ways. So far, we have only described one of the uses of the Tarjanian if.  Somewhat confusingly, Tarjan still uses the notation/syntax if for the second type of if-construct. Which if is being used is based on context. Analyzing the context is actually very easy to do as the second type of Tarjan-if is always pre-fixed by an assignment operator.

For example, we might have the following Tarjan code:

# Example Three
x := if a = 4 → 9 fi

Begin Digression

After working with Tarjan code for awhile, you get used to the order of operations. If we parenthesize test condition in the example above, we obtain:

x := if (a = 4) → 9 fi

a = 4 is not an assignment operation. a = 4 is like a == 4 -- it returns true or false.

End Digression

It can help to think of := if as syntax for a single operator, distinct from := and if In fact, we will refer to the := if operator as the "conditional assignment" operator.

For if we list (condition → action). For := if we list (condition → value) where value is teh right-hand-side value we might assign to the left-hand-side lhs

# Tarjan Example Four
lhs := if (a = 4) → rhs fi

in C or Java might look like:

# Example Four
if (a == 4) {
    lhs = rhs
}

Consider the following example of "conditional assignment" in Tarjanian code:

# Tarjan Instantiation of Example Five
x := if a = 4 → 9 |  a > 4  → 11 | true  → 99  fi

In C/Java, we would have:

// C/Java Instantiation of Example Five
if (a == 4) {
    x = 9
}
else if (a > 4)  {
    x = 11
}
else if (true) { // else
    x = 99
}

(5) Summary of Operators:

So far, we have:

:= ...... Assignment operator (C/Java=)
= ...... Equality test (C/Java ==)
→ ...... Delimiter between test-condition of an if-block and the body of an if-block
| ..... C/Java else-if
if ... fi ..... if-else block
:= if... fi ..... Conditional assignment based on an if-else block

(5.5) Tarjan Lists/Arrays:

Tarjan's Language has built-in array-like containers. The syntax for Tarjan arrays is much more intuitive than the notation for Tarjan if else statements.

list1  := ['lion', 'witch', 'wardrobe'];
list2a := [1, 2, 3, 4, 5];
list2b := [1, 2];
list3  := ["a", "b", "c", "d"];
list4  := [ ]; # an empty array

Tarjan array elements are accessed with parentheses (), not square-brackets []

Indexing begins at 1. Thus,

list3  := ["a", "b", "c", "d"]
# list3(1) == "a" returns true
# list3(2) == "b" return true

Below shows how to create a new array containing the 1st and 5th elements of [1, 2, 3, 4, 5, 6, 7]

nums := [1, 2, 3, 4, 5, 6, 7]
new_arr := [nums(1), nums(5)]

The equality operator is defined for arrays. The following code prints true

x := false
if [1, 2] = [1, 2, 3, 4, 5] --> x := true
print(x)

Tarjan's way to test if an array is empty is to compare it to an empty array

arr := [1, 2]
print(arr = [ ])
# `=` is equality test, not assignment

One can create a view (not copy) of a sub-array, by providing multiple indices to operator () combined with ..

list3  := ["a", "b", "c", "d"]

beg    := list3(.. 2)
# beg == ["a", "b"]
# beg(1) == "a"

end    := list3(3..)
# end == ["c", "d"]
# end(1) == "c"

mid    := list3(2..3)
# mid == ["b", "c"]
# mid(2) == "c"

# `list3(4)` is valid, but `mid(4)` is not

(6) Additional Examples of Tarjan's if and := if

The following is another examples of an Tarjan conditional assignment (:= if):

# Tarjan Example Six
a  := (false --> a | true --> b | false --> c1 + c2 |  (2 + 3 < 99) --> d)

(true --> b) is the leftmost (cond --> action) clause having a true condition.
Thus, the original assignment Example Six has the same assignment-behavior as a := b

Below is our most complicated example of Tarjan code thus far:

# Tarjan Example -- merge two sorted lists

list function merge (list s, t);

return if s =[] --> t
        | t = [ ] --> s
        | s != [ ] and t != [] and s(l) <= t(1) -->
            [s(1)]& merge(s[2..], t)
        | s != [ ]and t != [ ] and s(1) > r(l) -->
            [t(1)] & merge (s,t(2..))
       fi
end merge;

The following is a translation of Tarjan's code for merging two sorted lists. The following is not exactly C or Java, but it is much closer to C/Java than the Tarjan version.

list merge (list s, list t) {

    if (s is empty) {
        return t;
    }
    else if (t is empty){
        return s;
    }
    else if  (s[1] <= t[1]) {
        return CONCATENATE([s[1]], merge(s[2...], t));
    else  { // else if (s[1] > t[1])
        return CONCATENATE ([t[1]], merge(s,t[2..]);
    }
}

Below is yet another example of Tarjan-code and a translation in something similar to C or Java:

heap function meld (heap h1, h2);

    return if h1 = null --> h2
            | h2 = null --> h1
            | h1 not null and h2 not null --> mesh (h1, h2)
           fi
end meld;

Below is the C/Java translation:

HeapNode meld (HeapNode h1, HeapNode h2) {

    if (h1 == null) {
       return h2;
    }
    else if (h2 == null) {
        return h1;
    } else {
        mesh(h1, h2)
    }
} // end function

(7) Tarjan's Double-pointed Arrow Operator (<-->)

Below is an example of Tarjan code:

x <--> y

What Does a Double Arrow (⟷) Operator Do in Tarjan's Language?
Well, almost all variables in Tarjan's Language are pointers.
<--> is a swap operation. The following prints true

x_old := x
y_old := y
x <--> y
print(x == y_old) # prints true
print(y == x_old) # prints true

After performing x <--> y, x points to the object which y used to point to and y points to the object which x used to point to.

Below is a Tarjan statement using the <--> operator:

x := [1, 2, 3]
y := [4, 5, 6]
x <--> y

Below is a translation from the Tarjan code above to alternative pseudocode:

Pointer X     = address of array [1, 2, 3];
Pointer Y     = address of array [4, 5, 6];
Pointer X_OLD = address of whatever X points to;
X = address of whatever Y points to;
Y = address of whatever X_OLD points to;

Alternatively, we could have:

void operator_double_arrow(Array** lhs, Array** rhs) {

    // swap lhs and rhs

    int** old_lhs = 0;
    old_lhs = lhs;
    *lhs = *rhs;
    *rhs = *old_lhs;
    return;
}

int main() {

    Array* lhs = new Array<int>(1, 2, 3);
    Array* rhs = new Array<int>(4, 5, 6);
    operator_double_arrow(&lhs, &rhs);
    delete lhs;
    delete rhs;
    return 0;
}

Below is an example of one of Tarjan's functions using the ⟷ operator:

heap function mesh (heap nodes h1, h2);
    if key(h1) > key(h2) → h1 ⟷  h2 fi;
    right (h1) := if right(h1) = null → h2
                   |right(h1) ≠ null → mesh (right(h1), h2)
                  fi;

    if rank (left (h1)) < rank (right (h1))
        → left(h1) ⟷ right(h1)
    fi;

    rank (h1) := rank(right(h1)) + 1;
    return h1;
end mesh;

Below is a translation of Tarjan's mesh function into pseudo-code which is not C, but looks more like C (relatively speaking). The purpose of this is to illustrate how Tarjan's ⟷ operator works.

node pointer function mesh(node pointers h1, h2) {

    if (h1.key) > h2.key) {

         // swap h1 and h2
            node pointer temp;
            temp = h1;
            h1 = h2;
            h2 = temp;
    }

    // Now, h2.key <= h1.key

    if (h1.right == null) {
        h1.right = h2;

    } else // h1.key != null {
        h1.right = mesh(h1.right, h2);
    }

    if (h1.left.rank < h1.right.rank ) {
        // swap h1.left and h1.right

        node pointer temp;
        temp = h1;
        h1 = h2;
        h2 = temp;
    }

    h1.rank = h1.right.rank + 1;
    return h1;
}

(8) Tarjan's do-loops are like C/Java while-loops

Tarjan's language if and for constructs are familiar for C/Java programmers. However, the Tarjan keyword for a while-loop is do. All do-loops end with the keyword od, which is the backwards spelling of do. Below is an example:

sum := 0
do  sum < 50 → sum := sum + 1

In C-style pseudocode, we have:

sum = 0;
while(sum < 50) {
    sum = sum + 1;
}

The above is actually not quite right. A Tarjan do-loop is really a C/Java while(true) with an if-else block nested inside. A more literal translation of the Tarjan code is as follows:

sum = 0;
while(true) {
    if (sum < 50) {
         sum = sum + 1;
         continue;
         // This `continue` statement is questionable
    }
    break;
}

Below, we have a more complicated Tarjan do-loop:

sum := 0
do  sum < 50 → sum := sum + 1 | sum < 99 → sum := sum + 5

C/Java-style pseudocode for the complicated Tarjan do-loop is as follows:

sum = 0;
while(true) {

    if (sum < 50) {
         sum = sum + 1;
         continue;
    }
    else if (sum < 99) {
         sum = sum + 5;
         continue;
    }
    break;
}

(9) Tarjan's Conditional-assignment operator with all false conditions

Although the lengthy explanation above covers most things, a few matters are still left unresolved.
I hope that someone else will someday write a new-improved answer based on mine which answers these quandries.

Notably, when the conditional assignment operator := if is used, and no condition is true, I am not what value is assigned to the variable.

x  := if (False --> 1| False --> 2 | (99 < 2) --> 3) fi

I am not sure, but it is possible that no assignment is made to x:

x = 0;
if (false) {
     x = 1;
}
else if (false) {
     x = 2;
}
else if (99 < 2) {
     x = 3;
}
// At this point (x == 0)

You could require that the left-hand-side variable seen in an := if statement be previously declared. In that case, even if all conditions are false, the variable will still have a value.

Alternatively, perhaps all-false conditions represents a runtime error. Another alternative is to return a special null value, and store null in the left-hand argument of the assignment.


The statement $X = O(\log n)$ gives an upper bound on $X$, which implies a lower bound on $e^{-X}$ (which is a monotone decreasing function). You can say
$$
e^{-X} = e^{-O(\log n)} = n^{-O(1)}.
$$
In other words, there exists a constant $C > 0$ such that for large $n$,
$$ e^{-X} \geq \frac{1}{n^C}. $$


Is there a guaranteed min-cut algorithm for weighted graph or weighted cyclical digraph?

Directed graphs: Use any max-flow algorithm together with the max-flow min-cut theorem.  There are any number of algorithms for max-flow in an arbitrary directed graph.  This is bog-standard stuff that should be covered in any algorithms textbook.  See also minimum cut.

Undirected graphs: Use a min-cut algorithm for undirected graphs, e.g., Karger's algorithm or this lecture.  I don't know what you mean by "it is not guaranteed to provide a solution"; the probability that it fails to find a solution is exponentially small, e.g., you can make this probability smaller than the chance that a cosmic ray hits your computer, makes it compute the wrong answer, and then you get struck by lightning and die anyway.  Tough luck about that lightning, by the way.

Next time do more research before asking.


Algorithm to find if exists a k-length acyclic path with negative weight on an weighted undirected graph

If $k$ is part of the input to the algorithm (as opposed to a constant chosen ahead of time), and if "acyclic path" means a path that does not visit any vertex more than once, then this problem is already at least as hard as Hamiltonian Path, which is NP-hard: to reduce the latter to this problem, just give every edge some negative weight (e.g., -1) and set $k=n−1$.


Numerical problem on Access time in Cache memory

Here is the algorithm for a read operation:

Check if the cell is in the first-level cache.
If not, check if it is in the second-level cache.
If not, access it from main memory.

The data you are given allow you to calculate how much time each operation takes, and what is the probability that each of the steps is being taken. Using this, you can calculate the average time of a read operation.


Can timestamp be used in synchronization of processes having Race Condition?

The short answer is yes, since what you're essentially doing with the timestamps is making all potentially conflicting processes sequential. Of course, in sequential systems there are no race conditions (a bit of a simplification, but nevertheless). In what way does timestamping processes differ from creating locks on resources, which is the current standard in parallel computation? You may want to reflect on what the real issues with race conditions are. Maybe this definition from Wikipedia might help:

  "A race condition or race hazard is the condition of an electronics, software, or other system where the system's substantive behavior is dependent on the sequence or timing of other uncontrollable events."

So the primary issue to consider is what happens when you don't have control over the process(es) that cause(s) the race condition.


In which situation do we choose randomized binary search instead of the normal binary search?

Randomized binary search makes sense if your randomness source has a good bias towards your search target. You can then use it to reduce the expected search time (even retaining the $O(\log n)$ asymptotic worst-case complexity) as described in this answer.

If your randomness source is simply a uniform distribution, then you won't get much out of it. If you use it naively (i.e., simply choosing the midpoint according to your randomness source), it will actually perform worse than standard binary search since the worst-case complexity will be $O(n)$, not $O(\log n)$ (consider the case where your interval is $[1,n]$, your target 1, and your randomness source outputs $n-1, n-2, n-3, \dots$).


For every $k$ and $\sigma$, let $A(k,\sigma)$ be the minimum of $\sum_{j=1}^m w(a_j)$ over all subsets $a_1,\ldots,a_m$ of $\{1,\ldots,k\}$ containing $k$ such that $\sum_{j=0}^m (a_{j+1} - a_j - 1) = \sigma$; note that there are $O(n)$ choices for each of $k$ and $\sigma$. You can compute $A(k,\sigma)$ for all $k,\sigma$ using dynamic programming, and use it to solve your problem in polytime.


Minimum sum of squared Euclidean distance between two arrays

for m' = 0 to m
for k' = max(0, m-m') to min(m', k)
Take the problem of the first m' items of X and the first k' items of Y. Find the value of the smallest sum, and whether X[m'] is in that sum.
The optimal subset of the first m' items of X is either the best subset of the first m'-1 items of X matching the first k' items of Y, or the best subset of the first m'-1 items of X matching the first k'-1 items of Y, with X[m'] and Y[k'] added.
Note that sets and subsets are not sorted. If you want the indexes in arbitrary order, sorting X and Y first should work.


Help with a difficult expected runtime recurrence

Yes, you'll have $B(i) = O(\sqrt{n})$ (with very high probability).

Note that $k_i$ is binomially distributed, so it is approximately Gaussian.  It has mean $0$ and standard deviation

$$\sigma_i = \sqrt{n} \times 2^{-i/2 - 1}.$$

The probability that $k_i$ is more than, say, 10 standard deviations above the mean is incredibly small.  We'll define the event $\textsf{BAD}_i$ to be true if $k_i \ge 10 \sigma_i$, and we'll define the event $\textsf{BAD}$ to hold if there exists $i$ such that $\textsf{BAD}_i$ holds, i.e.,

$$\textsf{BAD} = \textsf{BAD}_1 \lor \dots \lor \textsf{BAD}_m.$$

By a union bound, we have

$$\Pr[\textsf{BAD}] \le \sum_i \Pr[\textsf{BAD}_i],$$

which is still very small.  Moreover, if $\textsf{BAD}$ does not happen, then we have

$$B(m) \le \sum_i 10 \sigma_i = 10 \sqrt{n}/2 \sum_i {1 \over \sqrt{2}^i} \le 10 \sqrt{n}/2 \times 3.5 = O(\sqrt{n}).$$

In other words, there is a constant $c$ such that $B(m) \le c \times \sqrt{n}$ with overwhelmingly high probability.

(I've shamelessly handwaved and glossed over details all over the place to present the intuition in a clean way, but even correcting for them isn't going to change the bottom-line answer.)


State machine with knowledge of prior states?

In digital design we would call the thing you are looking for an algorithmic state machine.  In compiler design we would call it a control flow graph.  The idea in either case is that you divide the state problem into two parts, one part represents the control state, the other part represents the data path.  You label the states with how you want the data path to be modified, and the data path has some boolean outputs that you use to determine which way the control state should change.

Formally, you are describing a Moore machine where each state describes a set of control signals that will be sent to tell the data path how to modify itself, and the data-path in turn has a small set of boolean outputs that are used as the input language to the control state machine.

Your original problem would then have a control state, Q, and two variables, v1 and v2 and the graph would look something like:

       q1: v1 <- some_function(...)
                |
                v
       q2: something else happens
                |
                v
    q3: v3 <- some_other_function(...)
        test (v1==1 && v3==1)?
       /                 \
       | true             | false
       v                  v
q4: something    q5: something else
       \                  /
        \                /
         v              v
           q6: whatever


How to write the turing machine processing operations?

The state marks the position of the head (as well as the current state): for example, in $q_00011$, the head is to the left of $0011$, and in $xq_1011$, it is to the left of $011$.

The notation $\sigma \vdash \tau$ means that the configuration $\sigma$ leads, after one step of the Turing machine, to the configuration $\tau$.

As David Richerby mentions in his comment, all of this is explained in your textbook at some point.


I assume you want to know the maximum possible bits that a product of two numbers might have. Under that assumption, let the first number $a$ have $m$ bits, and the second number $b$ have $n$ bits.

Then, $$a \leq 2^{m} - 1 $$
Similarly, $$b \leq 2^{n} - 1$$

Then, the product is:
$$a \cdot b \leq 2^{m+n} - 2^m - 2^n + 1$$
Now, both $2^m$ and $2^n$ are greater than $1$ (since $n, m > 0$).
So, $$a \cdot b < 2^{m+n} - 1$$

Therefore, at most $m+n$ bits are sufficient for the product of the two numbers. Of course, lesser bits might suffice. Also, the sign bit is not included in the computation, and each of $a$, $b$, and $a \cdot b$ might have a separate sign bit.

If you really need to optimize on space, you can check $a$ and $b$ for special cases. Some cases could be:

$a$ or $b$ is $0$: You need 1 bit
$a$ or $b$ is $1$: You need as many bits as the other number
One of the numbers is a power of $2$: It will contain exactly one $1$, say at position $i$ (LSB is position 0). Then, the multiplication is equivalent to left shifting the other number by $i$ bits.

You might think up other special cases if you really need to.

Edit: As pointed out by Sam in the comments, if you impose the restriction that the most significant bit has to be 1 (unless the number itself is 0), you can get a lower bound too.
Since the MSB is 1, we have:
$$a \geq 2^{m-1}$$ and $$b \geq 2^{n-1}$$.
Thus, $$a \cdot b \geq 2^{m + n - 2} = 2^{(m+n-1) - 1}$$

To represent $2^{(m+n-1)-1}$, you require $m+n-1$ bits, and so to represent $a \cdot b$, you need at least $m+n-1$ bits. This leaves the special case when either of the numbers is $0$, and assumes there are no leading 0's in any of the numbers.

As a conclusion, if you know the number of binary digits/bits of your number (as you mention in your question), you are most likely implying that there are no leading $0$'s and the left-most bit is $1$ (exception being when the number itself is 0, where you can simply assign 1 bit for the resulting product). In such a scenario, the product will have either $m+n$ bits or $m+n-1$ bits.


How can we know if a Turing machine halts, given that it writes to finite memory?

To answer your question, if you know that a Turing machine uses only $M$ cells, then you can tell whether it halts by running it for enough steps. If the Turing machine uses only $M$ cells, then it can be in one of $N$ configurations, where $N$ depends on $M$, the number of states, and the alphabet size. If you run it for $N$ steps and it doesn't halt, then altogether it will have gone through $N+1$ configurations, two of which must be equal, hence it is in an infinite loop and won't halt.

However, your actual question is different. You want to show that the following set is undecidable:
$$
L = \{ \langle M \rangle \colon M \text{ uses a finite amount of memory} \}.
$$
We will do so by reduction from the halting problem. Given a Turing machine $M$, construct a new Turing machine $M'$ which acts as follows:

for i from 1 to infinity:
    simulate M for one step, and halt if M halts
    move the head i steps to the right
    move the head 2i steps to the left
    move the head i steps to the right
end for

If $M$ halts, then $M'$ also halts, and in particular uses a finite amount of memory. Otherwise, $M'$ will necessarily use an infinite amount of memory.


Understanding commutativity and associativity for primitive types

Consider the following code:

  a = (b + c) + d

  e = c + (b + f)

Using associativity and commutativity, we can improve it to

  t = b + c

  a = t + d

  e = t + f

This uses one less addition. Since integer addition (ignoring overflow) is guaranteed to be commutative and associative, an optimizing compiler is allowed to use this optimization. The same isn't quite true for floating point addition, which is not associative.


As the comments say, the basic trie will not help with this task. So I'll propose a special trie for this task. It is the same in every way to normal trie except the "end-of-word" (EOW) nodes (Note that these are not necessarily leaf nodes as words may overlap, e.g. "the" and "theory").

Forget the trie for a moment and imagine all words of frequency 1 in a linked list. Now imagine we have multiple linked lists for each frequency. Now we have $k$ linked lists if there are $k$ distinct frequencies. We can chain these links together, in order of frequency, to create a linked list of linked lists. You could imagine something like this:

We will try to add this same idea into the EOW nodes in the trie without messing up the trie structure. It will be similar, but we will also need every EOW node to point to the sentinel node of their respective frequency list. We will have the following properties in the EOW nodes:

head - head (or sentinel) of this frequency list.
next - next EOW node in this frequency list.
prev - previous EOW node in this frequency list.
frequency - frequency of the word that ends at this EOW node.

The sentinel node will also have a next_head and prev_head field to go to the next and previous frequency list. Similarly the empty root of our trie will act as a sentinel to the first frequency list (i.e. root.next_head is frequency_list_1.head). It will look something like this:

Now we just need to modify the insertion procedure a little bit to accommodate these changes. Specifically the changes will occur when we reach the EOW node. I had started writing the changes out in pseudocode but it became a bit cumbersome. So there are probably easier ways to do this. The idea still is the same. Insertions should only increase by $O(1)$ operations because you'll never have to move a node more than one frequency list at a time, and if you have the necessary pointers this is fine. From there it's as simple as iterating over the list of lists of EOW nodes.

Analysis:

Let the words be a set $S$ of $n$ words and $k$ unique words (apologies for reusing $k$, this is different than the first $k$ we define).

Then we have that the insertion time for all words will be $O(sum\{|S_i|\})$. Or if we say $m$ is the length of the longest word, then it is $O(m \cdot n)$. Then after insertions getting the frequencies in order is $O(k)$ and $O(n)$ for the simple traversal.


Arranging tasks with specific constraints (scheduling)

This is actually a bin packing problem, rather than a scheduling problem.  If I remember correctly (it's been a long time) bin packing is the dual of scheduling.

In the most basic kind of bin packing problems each room would be available for exactly three hours, and the goal would be to minimize the total number of three-hour sessions you would consume.  Your problem has an extra constraint that rooms come in pairs that are available for 3 and 4 hours.

Bin packing problems are usually NP-complete, but there are some heuristics that tend to work well in practice.  For the basic bin packing problem the usual heuristic would be to sort the talks from longest to shortest.  Then start placing talks into rooms in that order.  For each talk examine the rooms in the same order.  Place the talk in the first room where it will fit.  You only rent a new room if you have a talk that won't fit in any of the existing rooms.

There's a bit more on the Wikipedia Bin packing page:
http://en.wikipedia.org/wiki/Bin_packing_problem

And I found this article, which describes some of the approximation algorithm results in this area (as of 1987):
http://www.columbia.edu/~cs2035/courses/ieor6400.F07/hs.pdf


What is the lower bound of the following computation

The attempt in the edited question is almost there.  When you issue the instruction OP, you get the answer back seven cycles later. When you issue an OP instruction, you must wait two more cycles before issuing another. You need to issue $N-1$ OP instructions, so they're issued at times $0, 2, 4, \dots, 2(N-2)$, and the last one completes seven cycles after it's issued, so we get the required answer.

Having said that, the example in the question seems bad. Since OP is an instruction taking two arguments, it's unclear what X[0] OP X[1] OP X[2] even means. If it's supposed to mean S := X[0] OP X[1]; S := S OP X[2]; then there are dependencies between the instructions. The second OP needs to know the value returned by the first, so it can't be issued until the first one has finished.  If the instruction sequence is supposed to mean X[0] OP X[1]; X[1] OP X[2], then it should just be written that way, or even just OP; OP, since the arguments are irrelevant.


Simple Definition of a Simple Grammar (with confusing example)

You're right, the grammar is wrong. Everything would be fine, though, if you were able to eventually eliminate the $B$. Here's a way to do that:
$$
S\rightarrow b\mid aA\\
A\rightarrow aB\\
B\rightarrow aB\mid b
$$
The first production generates a singleton $b$ or the first $a$, the second generates the second $a$ and the third eventually generates an arbitrary number of $a$s followed by a $b$.


Does a path exist going through each color only once?

I understand from your question that you are asking for a polynomial-time algorithm for solving the problem. It is unlikely there is one for the problem.

Taking the hint of @jjohn, this is exactly the same problem as in the Kleinberg-Tardos book, Exercise 8.12. They call the problem evasive path. Here, color classes represent different zones, and you must get from $s$ to $t$ visiting each zone at most once.

There are at least two straightforward reductions. The other one is from directed Hamiltonian path, and the other one from set partitioning, i.e. exact cover. If you still care about solving the problem, you can do it in $O^*(2^k)$-time, where $k$ is the number of colors.


Finding the max XOR of two numbers in an interval: can we do better than quadratic?

We can achieve linear runtime in the length $n$ of the binary representation of $l$ and $r$:

The prefix $p$ in the binary representation of $l$ and $r$, that is the same for both values, is also the same for all values between them. So these bits will always be $0$.

Since $r>l$, the bit following this prefix will be $1$ in $r$ and $0$ in $l$. Furthermore, the numbers $p10^{n-|p|-1}$ and $p01^{n-|p|-1}$ are both in the interval.

So the max we are looking for is $0^{|p|}1^{n-|p|}$.


Give an example of a language whose Myhill-Nerode equivalence relation is such that if $x,y \in \{0,1\}^*$ with $x \neq y$, then $[x] \neq [y]$

Consider the language $L$ consisting of words $w a 0 1^n$ where $w$ is an arbitrary word, $a$ is either 0 or 1, $w$ has at least $n$ letters and the $n$-th letter of $w$ is $a$. Clearly, given a word in $L$ there exists exactly one decomposition to this form (define $n$ to be the number of trailing ones in the string).

If $w \neq u$ then without loss of generality $w_i = 0, u_i = 1$ for some $i$. But then $w 0 0 1^i \in L$ while $u 0 0 1^i \notin L$. If $w$ is a prefix of $u$, then you can take $n$ which is larger than the length of $w$ but smaller than length of $u$.

In other words $L=\{v a u a 0 1^n : |v| = n-1, |a| = 1\}$; clearly this is a CFL.

(This is a variant of my answer from Can a language have $\Sigma^{*}$ as its syntactic monoid?)


How to represent sums of piecewise quadratic functions for efficient optimisation?

I'd suggest storing this in a tree data structure.  The tree represents a piecewise quadratic function (namely, the sum), and each leaf of the tree represents the domain of one of the pieces.  Each internal node corresponds to a range of intervals (the union of the intervals associated with the leaves under it).  Store in each node the maximum of the function on that interval.  Also, you will store in each node some of the summands (each of which is a quadratic function on some limited domain).  The quadratic function associated with a leaf is the sum of all of the summands found on the path from the root to that leaf.

If you maintain the tree using a self-balancing binary tree data structure, the height of the tree will be $O(\log n)$, where $n$ is the number of pieces in the sum.

Now, suppose you want to update the tree by adding a quadratic function $f$ with a small domain.  First, split the two leaves $f$'s endpoints fall into, if necessary.  Then, you can express the domain of $f$ as a union of $O(\log n)$ intervals, each associated with one of the nodes of the tree.  So, update those $O(\log n)$ nodes by adding in $f$ as another summand.  Also, for each leaf whose interval is contained in the domain of $f$, compute the maximum value of the quadratic function that leaf represents.  Now propagate these maxima up the tree, until you have eventually updated the maximum at the root; this lets you compute the maximum of the sum.  If the domain of $f$ contains $m$ leaves, then the running time for this update will be $O(m + \log n)$.  So, it will be quite slow if the domain of $f$ is large, but it will be fast if the domain of $f$ is very small.

I could not figure out how to make this run in $O(\log n)$ time regardless of the size of the domain of the summand added.

I suspect there may be a simpler data structure that also achieves $O(m + \log n)$ time updates -- I suspect the machinery of self-balancing binary tree isn't needed.


I went ahead and looked to see if there was a good resource that I could provide, but beyond some resources that Aaronson wrote, I could not find any good additional supplements. You should check out what he says and see if that helps. However, I'll do my best to provide a very quick and potentially hand wavy interpretation.

Basic Quantum Computing: (If Needed)

Consider a quantum computer with some number of quantum bits. Before we measure quantum bits, they are in a superposition of many possible output states. When measured, they collapse to a single state that is sampled from a probability distribution of states. In other words, during measurement, some state is "chosen" randomly from all possible states, with some more likely than others to be "chosen".

A quantum computation takes these unmeasured qbits and methodically applies quantum logic gates. Doing this influences that superposition (the probability distribution of final states). When we are done applying quantum gates, we perform a measurement on the entangled qbits (final quantum state). This gives us a result we can use, but all the underlying quantum information is lost, preventing us from measuring again. The quantum computation would have to be repeated from scratch in order to perform another measurement. To account for errors, quantum computations are usually performed multiple times to build up additional confidence in the final result.

Postselection in a Computation:

When computing a decision problem, let us just designate a single quantum bit, $q_1$, as our "answer" where $\lvert1\rangle$ and $\lvert0\rangle$ correspond to accept and reject.

Postselection introduces conditional probability into the mix. We say we want to postselect a quantum bit, $q_1$,for a specified outcome of a second bit, $q_2$. To simplify matters, let us assume that this is the last thing that we do before measuring. Without postselecting, our machine would accept with  $\mathbb{P}\left[q_1=\lvert1\rangle\right]$. If we use post selection as described above, we are telling $q_1$ to only be in a superposition of states that work given that $q_2=\lvert1\rangle$. The probability that the computation accepts now becomes $\mathbb{P}\left[q_1=\lvert1\rangle\mid q_2=\lvert1\rangle \right]$. This essentially filters out all possible states that $q_1$ could have been in if $q_2 = \lvert0\rangle$.

If $q_2$ happened to be defined as an indicator of a "good" computation in our experiment, then, by using postselection, we would have thrown out all the "bad" computations.

Note: $\mathbb{P}\left[q_2=\lvert1\rangle\right]$ must be $>0$ or else the conditional probability measure is not well defined.

So in short, postselection gives us the ability to force quantum bits to think that another quantum bit is in a specific state we choose. This lets us filter out a lot of results that we consider to be useless to us when we measure our quantum state. As demonstrated in Aaronson's proof of $\text{PostBQP = PP}$, the ability to postselect provides significant computational advantage over vanilla models of quantum computation.


What is the Number of epochs with no improvement after which training will be stopped.?

The number of iterations with no improvement is a hyperparameter. Scikit-learn has a default value of 10 in the MLPClassifier but of course you can select one depending on your problem. You can also do a grid search over all your model's hyperparameters.
Another advice I would give is that you could first train the model experimentally for a lot of epochs. If you see it getting stuck for a lot of iterations and then increasing after a halt, then it's better to set a higher value. On the other hand if after a lot of time you don't see it improving you should set the max number of iterations with no improvement to a smaller value.


Is there a decidable problem which has a proof that it cannot be proved to have a particular deciding Turing machine?

Let us examine the following language:

$x\in L \iff ZFC \hspace{1mm} \text{is consistent}$.

Clearly, $L$ is decidable, and is decided by either the constant 1 or 0 machines.

Proofs from ZFC for the statements "$M_0$ decides $L$", "$M_1$ decides $L$" cannot exist  (if ZFC is consistent), since any of those would imply a proof from ZFC about its own consistency (see Godels's second incompleteness).

Note that i can however, provide a proof that the following machine $M$ decides $L$:

Given input $x$, check if there exists a proof for the consistency of ZFC, of length$\le |x|$. If such proof is found, return 0, otherwise return 1.

If ZFC is consistent, the above machine outputs 1 for all $x$. If it isn't, we also have a proof that the above machine decides $L$ (An inconsistent system can prove any statement). The problem is that i cant prove whether or not $M$ computes the constant 1 function.


Deciding if a Turing machine has made a left move

$|w|$ steps are needed to scan the input, if a left move is made during this scan accept.

Otherwise, at the end of the input, the head of the Turing machine is on the blank part of the tape (over the first blank symbol after the input). Suppose the state is $q_{i_1}$. If the Turing machine doesn't make a left step and stays on state $q_{i_1}$, then it will do it forever (it will continue moving right on the infinite blank tape on state $q_{i_1}$). But it can move right and switch to state $q_{i_2}, i_1 \neq i_2$.

If you continue with this reasoning you see that there are only two possibilities:

it moves left or
it enters a state $q_{i_{k+j}}$ for the second time and thus it will loop forever: $q_{i_k} \rightarrow q_{i_{k+1}}\rightarrow ...\rightarrow q_{i_{k+j}}=q_{i_k} \rightarrow q_{i_{k+1}}\rightarrow ...$

But there are only $N$ different states so at most $N+1$ more steps are needed to detect such loop.


Ray Tracing versus object-based rendering?

Raytracing is a very nice and intuitive algorithm, and it is a more physically realistic way of describing the illumination of a scene than rasterization, but:

Raytracing is slow, specially if you want to implement the more realistic effects that distinguish it from rasterization (e.g. refraction, reflection, motion blur, soft shadows) because this implies creating a lot more rays per pixel.
Most people can't tell the difference between real and fake effects, which I think is the key point. The goal of a practical rendering algorithm is to create a photorealistic representation of a scene in the most efficient way, and right now Rasterization, although uses a lot of hacks, accomplishes this very well.
There are many other practical limitations of Raytracing compared to a Rasterization renderer: poor anti-aliasing and displacement mapping, limited instancing, etc.

Even in non-interactive applications, such as movies, Raytracing is used very little becasue of its limitations. Pixar only started using Raytracing in Cars, and only for some specific reflection effects (Ray Tracing for the Movie ‘Cars’).

Here is an excellent article that describes in more detail the current state of Raytracing and its advantages and disadvantages: State of Ray Tracing (in games).


Let $\Sigma = \{0, 1\}$. Clearly $\Sigma^*$ is enumerable. For the word problem you can proceed as follows.

For each pair $(i,j) \in \mathbb{N}_+^2$ in dovetail fashion:

Let $w_i$ be the $i$-th word in $\Sigma^*$.
Check whether $w_i$ encodes a valid Turing machine $T$ (w.r.t. some fixed encoding). If not skip to the next iteration.
Simulate the Turing machine $T$ with input $w$ for at most $j$ steps.
If $T$ halts at the end of the $j$-th step, output $T$.

For the Halting problem you can do as follows:

For each pair $(i, j, k) \in \mathbb{N}_+^3$ in dovetail fashion:

Let $w_i$ be the $i$-th word in $\Sigma^*$.
Let $w_j$ be the $j$-th word in $\Sigma^*$.
Check whether $w_i$ encodes a valid Turing machine $T$ (w.r.t. some fixed encoding). If not skip to the next iteration.
Simulate the Turing machine $T$ with input $w_j$ for at most $k$ steps.
If $T$ halts at the end of the $k$-th step, output $\langle T, w_j \rangle$.


Give an example of a connected graph where α(G) =100 and β(G) = 200

You are on the right track, just keep going: what if you take a slightly larger complete graph? Specifically, what if you take a $K_{101}$?


Comparing random access and sequential access

The answer critically depends on the model in use, specifically whether or not the memory is cached, and how the cache is being used. In the following I'll explore the two main architectures: with and without a cache.
Throughout, we assume the file consists of $k$ parts: $f_1, \ldots, f_k$ where $f_i$ is 4 bytes (32bits).
A. The simple case: a single-layered RAM.
In this case, we assume that we have a large memory $M$, where each address contains 32 bits of data.  Accessing an address in the memory takes $t_M$ time, and fetches the 32bits stored in that address.
We can assume that the file is stored sequentially in the memory, (although it doesn't matter), that is, $M[i]=f_i$ for $i\le k$ and $M[i]=0$ otherwise.
In this case, accessing the file in any order will take the same time, namely $k \cdot t_M$.
bottom line: RAM allows random-access with the same access time as sequential access. (this is why it is called a Random-Access Memory, RAM).
B. A more realistic case: a cached memory
In the more interesting case, the memory is layered. There is a small fast cache we denote $C$ that contains small amount of addresses, say 1024. Each address contains 32bits of data.
When accessing an address $i$ in the memory, the process is the following:

if $M[i]$ exists in the cache, say $C[j]=M[i]$, then the access time is $t_c$. (this is called a cache hit)
Otherwise, the slow memory is being accessed, and the data is fetched in time $t_C+t_M$. Additionally, $M[i]$ is now stored in the cache as well. (this is called a cache miss)

It is assumed that $t_C \ll t_M$. In case of a miss, if the cache is already full, we assume that the new value brought to the cache replaces the oldest item in the cache (the one that was last accessed the earliest)
B.1 A Single Access
Assume that at the beginning the cache is empty.
If the file is being accessed only a single time, then, each address we access is a miss, and it will take us $k(t_C+t_M)$ to access the entire file, regardless of the order.
B.2 Multiple Access
Now, assume we need to access the file twice. At the first time the cache is empty and so it will take us $k(t_C+t_M)$ to fetch the file, as above.
On the second time, things are a bit different.
If $k<1024$, then in the next access, the entire file is in the cache, and it will take us $k t_C$ time to access it again, regardless of the access order.
If $k>1024$ (say $k = 2048$), then in the second access the times slightly change:

if we access the file sequentially, then we will always have a miss, since the cache will hold the 1024 parts we have most recently accessed, and will never hold the next one that we need. The time is $k(t_C+t_M)$,
if we access it in a random order (that is independent of the order in the first time we accessed the file), then the first part will be there with probability $1/2= 1024/2048$, the second with probability $1023/2047$ and so on (the last 1024 parts will always cause a miss). This gives a slightly better access time.

B.3 Blocked cache
Realistic caches don't work byte-by-byte, but rather they work in blocks.
Let's say the block size is 256 words (that is, the 1024-cells cache holds 4 blocks of 256$\times$32bits each). Now, when you access an address $i$ in the memory, the following process happens:

if $M[i]$ exists in the cache, then the access time is $t_c$.
Otherwise, the slow memory is being accessed, and the entire block that contains $M[i]$ is brought into the cache. This takes time $t_C + 256t_M$.
We assume we always work in aligned blocks of 256 words: so if you access any address between 0 and 255, the same block $M[0],\ldots, M[255]$ is fetched into the cache.

Now, if you access the file in sequential order, once you access $M[0]$ you get a miss, and the first block gets into the cache. This takes time $t_C + 256t_M$. The next 255 access will be a hit. The total time will be about $k(t_C + t_M)$.
However, if you access the file randomly, every part has a probability of about $1024/k$ to already be in the cache (this is not exactly correct, but close enough). Thus the time will be (approximately)
$k \cdot (1024/k \cdot t_c + (1-1024/k)(t_C + 256t_M))$. This may be substantially worse than in the sequential case.
bottom line: if the cache is blocked, you get advantage accessing sequentially. Otherwise, it shouldn't matter that much.
C. The (even more) realistic case
Finally, I must add that there are more parameters that affect the analysis.
First, usually the memory has several cache layers, e.g., L1--L3 cache, and a main memory. Each level has more memory but is slower than the layer beneath it.
In order to give a precise analysis, a full description of the memory and the access pattern should be given, since many parameters might have a dramatic effect on the total access time.


Contamination in Atomic Broadcast in crash stop failure model

I think you are confusing the failure model with the correctness goals of a protocol.

A failure model specifies what kinds of things can go wrong (i.e., what kinds of failures the protocol is designed to deal with and promises to be able to handle).
A correctness goal describes what properties the protocol promises to provide (i.e., what properties it needs to achieve, to qualify as correct).

We then analyze whether a particular protocol meets a particular correctness goal in a particular failure model.  For example, protocol might achieve the correctness goal in one failure model but not in another.

Example of failure models include crash-only; or Byzantine failures; or others.  See Sections 2.3 and 2.6 for examples of kinds of failures.  A failure model would specify which of those failures are in scope (and thus, implicitly, which are out of scope).

An example of a correctness goal is "Causal Broadcast" or "Atomic Broadcast" or "Causal Atomic Broadcast".  For instance, the correctness goal that we call "Causal Broadcast" is that the protocol must ensure Causal Order for all delivered messages (see Section 3.3 of the paper you mention).  There might be a protocol that achieves Causal Order in the presence of crashes but not in the presence of Byzantine failures.

With that understanding, Section 3.11 of your paper starts out with an example of a failure that can be problematic.  That's a type of failure that isn't just a crash.  Yes, it could be considered an instance of a Byzantine failure.  However, it is also a more specific type of failure; one can articulate a more specific failure model that is more constrained than arbitrary Byzantine failures, but broader than just crashes, and which includes that failure as the sort of failure that can occur.  It may be useful to think about what is achievable in that intermediate failure model.  There are more failure models in the world than just "crash stop" and "Byzantine".


How do I calculate the probability of a PCFG rule in a parser?

A probabilistic context-free grammar is a generative model, which can be used to generate random words in the language of the underlying context-free grammar. In order to do this, for each nonterminal $A$ we give a probability distribution on the set of rules of the form $A\to \alpha$. To generate a sentence, you start with the starting symbol $S$. As long as the current sentential form contains some nonterminal, say $A$, you apply a random derivation rule $A\to \alpha$ according to the probability distribution. If the probabilities are chosen correctly, then eventually a terminal word will be generated (almost surely).

On the left of your image, you can see the probability distributions. You can estimate the probabilities from a collection of parse trees, but you can also come up with them in any other way. In particular, it doesn't make too much sense to determine them from a single parse tree, like your description seems to imply.

On the right of your image, you can see the calculation that the given parse tree be generated by the PCFG on the left. This probability is the product of all derivation rules that need to be applied to obtain the parse tree (the order of application is immaterial since it doesn't affect the product).

Your underlying difficulty seems to be that you don't understand what PCFGs are for and how they are used. Hopefully, my description above helps to clarify this somewhat.


Are there difficulties differentiating between 3 levels of signal?

That's more electronic than computer science (and the issue could be different with other technology). The 2 levels signals we use are generated by putting transistors in a saturation state(*). They behave like switches and the whole technology is driven to optimize this behavior(+). Even without considering that historical skew, generating an intermediate level at a fixed value is more difficult than using saturation, will consume more power (a big part of the power is currently consumed in the transition between saturating state, you will need to stay in that mode where power leaks a lot), reduce the resistance to noise (can be reduced by increasing the supply voltage and thus the power consumption) leading to reduced fabrication yield.

(*) Historically, there has been computer working with transistor in a non saturated state. There is a speed advantage to that. Power consumption (and needs for dissipation) killed the practice.

(+) Analog circuits are made with different processes which are deemed unsuitable for large digital circuits and even small one which don't need an analog part.


Show that the set of all TMs that move only to the right and loop for some input is decidable

Your approach is on the right track. It should follow the next ideas:

If there exists such $w$, then, when $M$ reaches the first "blank" after reading $w$ it will be in a state $\tilde q$ that goes right (and then keep going right, no matter the state changes). Finding this $\tilde q$ that satisfied this property (if such exists) can easily be verified for by checking all the states in $Q$ (of the given $M$).
If such $\tilde q$ exists, we need to see if it is reachable after reading some input $w \in \Sigma^*$. The idea you already noticed is that if this happen, then $\tilde q$ will be reachable after processing the end of some word in $\Sigma^{Q+1}$ (or the like). This is simply a pigeonhole argument..

Therefore it is enough to only examine all the words in $\Sigma^{Q+1}$ and check if $M$ on any of them goes only right, and reaches $\tilde q$ when hitting the first blank. Since the number of words in $\Sigma^{Q+1}$ is finite, this is doable in a finite time.

You just need to properly formalize the above ideas as a decider $\hat M$.


Find the duplicates in a list of floating point numbers

Sorting

The simplest algorithm is to sort your floats, then compare adjacent entries.  This will let you find all pairs that are $\le \frac1N$ apart in $O(N \lg N)$ time.

Hashing

It's also possible to come up with a linear-time algorithm, i.e., to check whether there is any nearby pair of floats and if so find at least, in $O(N)$ time.

Let $M=\lfloor N/2 \rfloor$.  Build a list of integers by replacing each float $x$ with $\lfloor Mx \rfloor$, then find all duplicates in the resulting list of integers.  Finding duplicates in a list of integers can be done in expected linear time by hashing and looking for a pair with the same hash.  For each duplicate integer, check whether it corresponds to a pair of floats that differ by $\le \frac1N$.

Then, do it again: build a second list of integers by replacing each float $x$ with $\lfloor Mx + 0.5 \rfloor$, then find all duplicates in this list and check each to see whether it corresponds to a pair of floats that differ by $\le \frac1N$.

It's possible to show that if there exists a pair of floats that differ by $\le \frac1N$, then this procedure will find at least one such pair; and if there aren't any such pair, then this procedure will discover that fact.  Moreover, with suitable choice of the hash function, this can be made to run in expected linear time.  In fact, if you replace the hashing with counting sort, this runs in deterministic linear time.

In practice

In practice, my advice is to simply sort and then compare adjacent entries.  It will be easier to implement, less fiddly (you don't have to deal with corner cases), obviously correct, and probably more than fast enough in practice.


Number of possible programs in a language

When considering such questions we usually disregard limitations of real computers and think about a programming language theoretically.

A general-purpose programming language (any language used in practice falls into this category) has infinitely many programs. Furthermore, all programs can be generated systematically. Implementing a program which generates all programs may be a useful learning experience, but has little actual value. The number of all programs of length $n$ is exponential in $n$ and so is unfeasable, except for fairly small values of $n$.


So I'm not completely sure, but I think you're asking to count the number of strings of size $n$ (over the alphabet $\{a, b\}$) where the factor/substring $aa$ does not appear right?

In this case, there are a few combinatorial approaches that you can take. Both Yuval and ADG have given simpler and more intuitive arguments, so I definitely suggest checking their answers out! Here's one of my favorites, it's a little strange, but it's a very general (and kind of a fun) approach.

Let's start with a simpler language, that of words which starts and ends with $b$ (also with no substrings of $aa$). We can look at an admissible string (e.g. $bbb\textbf{a}b\textbf{a}bbbb$) as a list of sequences of $b$s separated by singular $a$s. This gives the construction:
$$
w = (b^+a)^*b^+
$$
Now, how do we count sentences that belongs to this language?

Let's imagine that we're expanding these expressions out. What does $e^*$ denote? Well, it's simply
$$
e^* = \epsilon \mid e \mid ee \mid eee \mid eeee \mid \dots
$$
Now, this will make very little sense, but let's imagine that $e$ is a variable over some numerical field. In particular, we'll treat $\epsilon \to 1$, $a \mid b \to a + b$, and $abc \to a \times b \times c$. This then says that
$$
e^* \to 1 + e + ee + eee + \dots
$$
Let's try to see the motivation behind this strange interpretation. This is almost a bijective transformation. In particular, we want to preserve the count of each $e^n$ word, which, as you can readily see, we do. However, there's one crucial difference between the string expressions and numerical expressions: the multiplication (concatenation in strings, $\times$ in numerical expressions) is now commutative! Intuitively, commutativity lets us treat all permutations of the same word as the same; that is, we don't disambiguate between the expression $bbbab$ and $bbabb$; they both represent a string with 4 $b$s and one $a$. Therefore, this transformation allows us to preserve the count of each word of a certain number of $a$s and $b$s, but it now allows us to turn a blind eye on the superfluous details that we don't care about.

If you go back to precalculus, you might recognize this series as $\frac{1}{1 - e}$. I know that it doesn't make any sense to rewrite this regular expression as a numerically-valued function, but just bare with me for a moment.

Similarly, $e^+ = ee^* \to \frac{e}{1 - e}$. Which means that we can translate $w$ into
$$
w \to \frac{1}{1 - (\frac{b}{1 - b} \times a)} \times \frac{b}{1 - b}
$$

In turn, we can simplify this down to
$$
w(a, b) = b \times \frac{1}{1 - (b + ba)}
$$

This tells us that the language $w$ is isomorphic to the language $b(b \mid ab)^*$ (whose direct translation is already $\frac{b}{1 - b - ba}$) without ever having to resort to any language-theoretic tools! This is one of the power of treating these series as closed-form functions: we can perform simplifications on them that are nearly impossible to perform otherwise, hence reducing it down to a simpler problem.

Now, if you still recall any of your calculus course, you'll recall that certain types of functions (being well-behaving enough) admits these series representations known as Taylor expansions. Don't worry, we won't really have to worry about those pesky Calc 1 problem-sets; I'm just merely pointing out that these functions can be represented as the sum
\begin{align*}
w(a, b) &= \sum_{i,j} w_{ij} a^i b^j
\end{align*}
so that $w_{ij}$ gives the number of words that satisfies $w$ such that it has exactly $i$ occurrences of $a$ and $j$ occurrences of $b$. However, we don't particularly care about whether something is an $a$ or a $b$. Rather, we just care about the total number of characters in the string. To turn a "blind eye" between $a$ and $b$, we can just (literally) treat them the same, e.g. let $z = a = b$ and get
$$
w(z) = w(z, z) = \frac{z}{1 - z - z^2} = \sum_k w_k z^k
$$

where $w_k$ counts the number of satisfiable words of length $k$.

Now, all that's left to do is to find $w_k$. The usual combinatorial approach here would be to decompose this rational function into its partial-fraction: that is, given the denominator $1 - z - z^2 = (z - \phi)(z - \psi)$, we can rewrite $\frac{z}{(z - \phi)(z - \psi)} = \frac{A}{z - \phi} + \frac{B}{z - \psi}$ (There's a bit of algebra involved here, but this is a universal property of rational (one polynomial dividing another) functions). To solve this, you can refactor
$$
\frac{A}{z - \phi} + \frac{B}{z - \psi} = \frac{z}{(z - \phi)(z - \psi)}
$$
which generates the constraints $A + B = 1, A\psi + B\phi = 0$. Irregardless of what $A$ and $B$ are, recall that $\frac{1}{1 - x} = 1 + x + x^2 + \dots$, well, we can rearrange
\begin{align*}
w(z) &= \frac{-A}{\phi - z} + \frac{-B}{\psi - z} \\
&= (-A\phi)\frac{1}{1 - \frac{z}{\phi}} + (-B\psi) \frac{1}{1 - \frac{z}{\psi}} \\
&= (-A\phi)\left(1 + \phi^{-1} z + \phi^{-2} z^2 + \dots\right) + (-B\psi)\left(1 + \psi^{-1} z + \psi^{-2} z^2 + \dots\right)
\end{align*}
therefore
$$
w_k = (-A\phi)\phi^{-k} + (-B\psi)\psi^{-k}
$$
Here, $\phi$ is the golden ratio $\frac{1 + \sqrt{5}}{2}$ and $\psi = -\phi^{-1}$ is its conjugate. We then have an easy description of the asymptotic behavior of the $w$ language: it runs in $\Theta(\phi^n)$. In fact, if you expand everything out, you'll find that
$$
w_k = \frac{\phi^{k} - \psi^{k}}{\sqrt{5}} = \left\lceil \frac{\phi^{k}}{\sqrt{5}} \right\rceil
$$
There's also an intricate connection to another common combinatorial class. This is just the Fibonacci numbers!

Now, suppose you have $w_k$, which counts the number of strings of size $k$ that starts and ends with $k$ (and also contains no $aa$ substrings), how can we build a string that can start or end with an $a$? Well, it's simple: an admissible string is either in $w$ (starts and ends with $b$), or it is $a w$ (starts with $a$), or it is $w a$ (ends with $a$), or it is $a w a$ (starts and ends with $a$). Therefore:
$$
f(n) = w_n + w_{n-2} + 2 * w_{n - 1}
$$
Recall that $w_n$ is the fibonacci sequence, so $w_{n-1} + w_{n-2} = w_n$, which means that
\begin{align*}
f(n) &= (w_n + w_{n-1}) + (w_{n-2} + w_{n-1}) \\
&= w_{n+1} + w_{n} \\
&= w_{n+2}
\end{align*}
Therefore, $f(n) = \text{fib}(n + 2) = \left\lceil \frac{\phi^{n+2}}{\sqrt{5}} \right\rceil$

Now you probably don't have to do this analysis, but just by having the insight that this sequence is a shifted Fibonacci sequence ought to give you an idea of some other combinatorial interpretations that you can try.


Duplicate elements in Queue for BFS Maze Algorithm

Yes.  There is no point having duplicates in the queue, so don't enqueue a position if (a) it has already been visited, or (b) it is already on the queue.

What happens if you skip checking whether it is already on the queue?  Depending on how the rest of your code works, this could slow down your implementation significantly (it could increase the asymptotic running time from linear to quadratic).


Worst Case for AVL Tree Balancing after Deletion

To make a lot of rebalancing, you would like to make your AVL tree as imbalanced as possible. And the worst case is a Fibonnachi-like tree:

, where $T_n$ is a tree with $T_{n-1}$ as a left child and $T_{n-2}$ as a right child ($T_1=T_2=$single-node tree).
On this example, if you remove 19, then node 18 must be rebalanced. After that, node 13 must be rebalanced. Essentially, you will have a rebalance at every level above node 20. You can build an arbitrary large such tree. I didn't check, but it should be simple to prove that removing the rightmost node always suffices for the worst case.


No, there's no standard name for a process where the transpose of the transition matrix is stochastic (at least, to my knowledge).

However, this process is the time-reversal of a Markov process.  That's a remarkable and descriptive property that just about completely characterizes this process.  In particular, it seems likely that many things we'd want to know about such a process can be derived from the fact that it's the time-reversal of a Markov process, plus known facts about Markov processes.

Anyway, if you need to describe the process, "time-reversal of a Markov process process" is probably about as good as you're going to get.


Solving number of distinct elements in $O(\frac{n\ell}{p})$ space complexity with $2p$ passes over data

Try something along the following lines. Preform $p$ iterations where each iteration consists of two passes over the stream. The $i$'th iteration first pass remembers all elements whose index $\bmod p$ equals $i$ , denote this collection by $S_i$. The second pass, for each element of the stream whose index $\bmod p$ is greater than $i$, checks if it appears in $S_i$, and if so deletes it. Denote by $S_i'$ the remaining subset after the second pass, then your algorithm returns $\sum\limits_{i=1}^p |S_i'|$.


After posting the above I realized there was a possible solution with a different model. By viewing sets as nodes in a directed graph and edges as constraints, where $x \subseteq y$ would be translated to x -> y, the final checker would simply look for a path between $a$ and $b$ in this graph. (Using DFS or BFS per this SO question).


Your understanding is mostly correct.  That is a valid loop invariant.  It's just a relatively weak one.  It is common to find a situation like this, where there are multiple possible loop invariants, some more useful than others.  You've found a relatively weak (less useful, less informative) loop invariant.

Your real question is: how do I find a loop invariant that is strong enough to let you prove your code is correct?  The answer to that is that you need to start by specifying what it means for your code to be correct.  You need to start by writing a specification for your code, that outlines what it means for it to correctly compute the log function.

The specification will typically take the form of a precondition and a postcondition on the function itself.  The loop invariant is only a tool to help you prove that the code of log meets the specification for log.

I can't tell you what the right specification is, as you haven't told us what you want log to do.  But here is one example specification:

Precondition: $x=2^k$ for some $k \in \mathbb{N}$
Postcondition: if $x=2^k$, then the return value of log is equal to $k$

When you try to crank through a Hoare-style proof that log meets this specification, you'll find that you need a loop invariant.  The following loop invariant will be sufficient:

$$i \ge 0 \land j \ge 1 \land j = x \cdot 2^i.$$

I don't expect it to necessarily be obvious that this is a valid loop invariant, nor that this is sufficient to prove the code above meets the spec I gave.  Fortunately, there is a systematic step-by-step way to verify that: you use Hoare logic.  To learn about this, I recommend that your next step be to spend some quality time with a textbook that explains preconditions, postconditions, loop invariants, and Hoarse logic.

Of course, that's not necessarily the only specification you might have in mind.  Another possible specification would be

Precondition: $x \ge 1$
Postcondition: if $2^k \le x < 2^{k+1}$, then the return value of log is equal to $k$

or even:

Precondition: $x \ge 1$
Postcondition: the return value of log is equal to $\lfloor \lg x \rfloor$

Those might require different, more elaborate loop invariants.  The point is: whether a loop invariant is strong enough depends upon what you're trying to prove, and in particular, what spec you're trying to prove the code meets.

A small correction: When you write

  "without pointing out explicitly that this is a logarithm calculator, the loop invariant is invalid",

that's not quite right: the loop invariant you gave is a valid loop invariant.  It's just a relatively weak one.

Also, when you write "satisfy the simple algorithm above", that's probably not the right way to put things.  I've never heard the word "satisfy" used in this way before.  Instead, the right question to ask is: how do I prove that this code meets a particular specification?  To ask that, you first need to know what the specification that you're trying to meet is.


Dynamic programming: speed of top down vs bottom up approaches

Top down approach would be faster in cases where the no of entries that you have to compute are significantly less than than the total number of entries. Remember, recursive approach is slow than iterative approach because there is some overhead of function call too.

Top down approach fails in some cases because it works by recursion. In recursion you require space (stack space) for storing each function call. Now, if the depth of your recursion tree is large you may run out of stack space. In that cases iterative approach (like bottom to top approach) works because you can use memory from heap and running out of stack space is not an issue there.


How to deal with $n\sqrt n$ in master theorem?

You have to remember that $\sqrt[x]{y} = y^{\frac{1}{x}}$.

Then the rest should follow easily.

Don't look at the following unless you're genuinely stuck.

   $n\sqrt{n} = n^{1}\cdot n^{\frac{1}{2}} = n ^{\frac{3}{2}}$, hence $d = \frac{3}{2}$. We also have $a = 8$ and $b = 4$, so $\log_{b}(a) = \log_{4}(8) = \frac{3}{2}$. Hence we have the second case of the Master Theorem where $f(n) \in \Theta(n^{d}\log^{0}n) = \Theta(n^{d})$ with $d = \log_{b}(a)$. Therefore $T(n) \in \Theta(n^{d}\log n) = \Theta(n^{\frac{3}{2}}\log n)$.


Why there is no constraint on "Prover" in definition of $IP$?

There's nothing canonical for what constraint one might put on it.  Requiring complete efficiency would give BPP, since the algorithm can just simulate the whole interaction.  Requiring efficient-given-a-polynomial-length-string would give MA, since the prover could just send its string to the verifier.  It turns out that PSPACE is always enough, so letting the prover be at least that powerful yields the same class as not constraining the prover.  I suppose

things from TFUP to [CH given a polynomial-length string] might give intermediate classes.


Semantics of a logic describe how to compute the truth value of an expression, possibly given some interpretation. For example, one rule would say that an expression $\varphi \land \psi$ is true iff both $\varphi$ and $\psi$ are true, and another would say that $\forall x \varphi(x)$ is true if for all $x$ in the domain of discourse $D$ (which forms part of the interpretation).

Sometimes the semantics are not obvious – for example, there are different semantics for modal logic. Sometimes we are interested in non-standard semantics, such as
the semantics of bounded arithmetic described in Forcing with random variables.


Batch sizing for convolution neural networks -- powers of 2 or powers of primes?

No.  It doesn't apply to CNNs.  CNNs are doing the same operation on each item in the batch; it's much simpler than what's happening in a FFT (which involves interaction between the elements of the array; you can't compute a FFT by just separately doing something to each element of the array in parallel).


The rules like "onions" with various layers that you describe in your question can be thought of as a build order for how you will construct a string -- eg. "first I will build this part of the string, and then I will build this other part" or "I need to build these two parts at the same time in order to ensure that they are synchronized".

A good general strategy for constructing a context free grammar is to
determine this build order and then have a production rule that
represents each stage and/or each possibility of your build order.
You should be able to point to each nonterminal and explain the "meaning"
or type of string that nonterminal is trying to construct.

For the example of $a^ib^jc^k$ with $i \ne j$, one possible build order could be:

Produce $a$'s and $b$'s in equal number (this is like $a^ib^j$ where
$i = j$. Try writing a grammar for this first.)

At some point, the number of $a$'s and $b$'s have to diverge, so pick either $a$ or $b$ and produce an unbounded number of that character (this is like $a^ib^j$ where $i \ne j$. Try taking the grammar you have from 1) and adding production rules to be able to do this.)

Now just produce an unbounded number of $c$'s at the end. (this is the desired $a^ib^jc^k$ with $i \ne j$.)

A good question to ask yourself:
Why do we have to have more than one production rule to construct $a^ib^j$ where $i \ne j$? If I want the number of $a$'s and $b$'s to be equal, it makes sense that I'd have to build them at the same time, but if I want $i \ne j$, why can't I just do something like:
$S \rightarrow aS\ |\ Sb\ |\ \varepsilon$
which says "produce some number of $a$'s and then produce some number of $b$'s"?


minimum number of nodes that traverse all the graph

Try combining Tarjan's strongly connected components algorithm with a topological sort.


Is everything in CS either a numeric method or a symbolic method?

No. You could make a decent argument that every algorithm is in some sense a symbolic manipulation, though not in the sense normally used for symbolic computation - they are not explicitly algebraic, and more naturally find expression as logic and set theory (unsurprisingly). Taking the wider view of symbolic manipulation though, even numerical analysis is just symbolic calculation, it's only at the external semantic level that we recognise it as an approximation of what we actually want to do. The computer is still just pushing bits around.

However Computer Science extends beyond algorithms, even though they are central to CS. It includes complexity, computability, plus practical subfields like networking, machine intelligence, compiler and language design &c. which involve more than just designing algorithms.

Just to pick a few illustrations of this: designing a programming language is not a computation of any sort (the compiler is of course), but it is certainly computer science; the construction of a complexity reduction is not a computation (but the reduction itself is; the choice of processor layout in parallel computing is a choice made by the designer.


Yes. These are two different words for the same thing. I've also heard it called a lexer sometimes.


Finding the shortest time to go from one stop to another stop in a train system with many train lines with connection stations

Transform your input to a graph in which each vertex represents a stop on a line. If a stop is shared by multiple lines, then add one copy of the vertex per line and a new super-vertex connected to all such copies with edges of weight 2.5 (so there is a path of length 5 between any two of these stops). Add edges between consecutive stops of the same line with weights matching the travel times.

Use Dijkstra's algorithm to find the shortest path between the starting stop and the last stop.

The time required is $O(n\log n)$ where $n$ is the overall number of (not necessarily distinct) stops across the different lines. This is because is possible to assign edges to vertices so that: 1) each edge is assigned to a "stop" vertex, and 2) each "stop" vertex has at most $2$ edges assigned (i.e., the one towards the "next" stop w.r.t. an arbitrary direction of the line the vertex belongs to, if any, and possibly the one to a super-vertex), showing that the number of edges is at most $2n$.

EDIT:

Here is the graph obtained by applying the above transformation to the example in the question.
The edges of the horizontal line are in red, those of the vertical line are in blue. All the vertices representing stops on a specific line are white, while the only super-vertex is in black. Black edges have a weight of $2.5$ each (not shown). The tree vertices in the gray circle together represent the stop at the intersection of the horizontal line and vertical line.


Reducibility of 2 boolean satisfiability problems

Problem A is reducible to Problem B in following manner:

Pick a variable in problem A and set it to
0
Now we have a formula of size n-1, if satisfiable with B then return satisfiable
Else, pick problem A again and set the variable to 1
Now we have a formula of size n-1 again, if satisfiable with B then return satisfiable else return unsatisfiable

In other words: Split problem A into two problems B using any variable. If B says unsatisfiable for both 0 and 1 then it is unsatisfiable. If it says satisfiable for at least one of the two, then it is satisfiable.


Analyzing time complexity of solution in tutorial

Let me focus on the following question:

  Is $3^nn$ a tight bound on $\binom{n}{k}n2^{n-k}$?

First, let us see that this is a valid bound. This follows from the binomial theorem:
$$
\sum_{k=0}^n \binom{n}{k} n 2^{n-k} = 3^nn.
$$

Since there are $n+1$ summands in the expression, we deduce that
$$
\max_{0 \leq k \leq n} \binom{n}{k} n 2^{n-k} \ge \frac{3^nn}{n+1}.
$$
Using Stirling's formula, we find out that
$$
\max_{0 \leq k \leq n} \binom{n}{k} n 2^{n-k} = \Theta(3^n\sqrt{n}).
$$
This is a tighter bound.


Classification of job shop scheduling problems

In searching around for an online presence for one of the classics in this field (Coffman, Denning: Operating Systems Theory, Prentice Hall, 1983) I came upon what looks like a comprehensive textbook with a Google books preview Pinedo: Scheduling: Theory, Algorithms, and Systems, Springer 2008.  The author's homepage also has pages devoted to each of his books.  It has chapters for multiprocessor scheduling, open shop scheduling, flow shop scheduling and job shop scheduling.

The flow shop problem has $n$ jobs with $m$ machines.  Each job needs to visit machines in the exact order $1,2,\ldots,m$.  There are $nm$ parameters $d_{ij}$, which is the amount of time job $i$ demands on machine $j$.  There is no constraint on the order in which machines service jobs.  (The constraint is on the order in which jobs need machines.)

The permutation flow shop problem seems to add the constraint that every machine must service the jobs in the same order.  So the goal is to permute the jobs to minimize the makespan of pipelining each job through the machines in order.

The open shop problem completely relaxes the ordering constraints.  Each job demands time on each machine, but in no particular order.  (And, of course, the amount of time demanded by job $i$ on machine $j$ can be 0.)

The flow-shop problem and open-shop problems are special cases of the more general job shop problem with precedence constraints:  We are given a set of jobs $J=\{J_1,\ldots,J_n\}$ and a set of resources $R=\{R_1,\ldots,R_m\}$.  Each job $J_i$ consists of a set of operations $O^i=\{O_1^i,\ldots,O_p^i\}$.  Each operation $O_k^i$ requires a set of resources $R_k^i \subseteq R$ for a time $t_k^i$, and for each job, $J_i$ there is a set of precedence constraints (i.e., a partial order or directed graph) on the operations, $O_k^i \xrightarrow[\mathrm{before}]{} O_l^i$, stating that operation $O_k^i$ needs to finish before $O_l^i$ starts.

Your problem is a job-shop problem with an additional generalization that there are classes of identical resources ("3 locksmiths") and the operations can use any resource in the class.  This brings in an aspect of the multiprocessor scheduling problem.

N.B., I believe that I've used the terminology that is used in the books by Coffman and Denning, and by Pinedo.  The wikipedia pages are an utter disaster.  The wikipedia page on job shop scheduling gives a definition of the open-shop problem that contradicts the wikipedia page on open shop scheduling.  The wikipedia page on the flow shop problem is incomprehensible.  And wikipedia is confused about the difference between multiprocessor scheduling, which involves $m$ interchangeable resources, and job-shop scheduling.  For example, the wikipedia page on the Coffman-Graham list scheduling algorithm calls it a solution to the job-shop scheduling problem, although Coffman and Graham use the term "multiprocessor", not job-shop in the titles of their papers.  (And note that the author of the wikipedia page on multiprocessor scheduling seems unaware of the original variant with precedence constraints.)


How much does regularization prevent overfitting?

Moritz Hardt's excellent blog outlines extensive research into the idea that stability in machine learning methods is related to the idea of generalization. Interestingly, we find that regularization implies stability.

Formally, given observations $S = (z_1, \dotsc, z_n)$ and algorithm $A$, stability is defined as the expected difference between the risk and empirical risk $$\mathbb{E}[R - R_e] = \Delta,$$ where $R_e = \ell(z, S) = \frac{1}{n} \sum_i \ell(z_i, A(S))$ is the empirical risk and $R = \mathbb{E}_{z \sim D}[\ell(z, A(S))]$ is the risk.

The post details how to obtain bounds on $\Delta$ and its implications much better than I ever can. I highly recommend reading that post along with all of his other posts.

A much more practical argument is that regularization constrains the problem space to a very specific subset of models; namely, regularization methods can be recast as constrained optimization where $\|\beta\|_p \leq  c$ for some value of $p$. This is equivalent to using prior knowledge about the problem and forcing the solution to be within some constrained space.


Is my reasoning wrong that $PSPACE$ should not equal $EXPTIME$?

I did not understand the first part of the question, but just so you know, its unknown whether $EXPTIME=EXPSPACE$ or not. What is known is that $EXPSPACE\subseteq \bigcup _cDTIME(2^{2^{n^c}})$ from the relations shown here.
The second part of the question: If $EXPTIME=EXPSPACE$ then $PSPACE\neq EXPTIME$, is absolutely correct: by the space hierarchy theorem, $PSPACE\subsetneq EXPSPACE$ and therefore $PSPACE\subsetneq EXPTIME$ as $EXPSPACE=EXPTIME$ (by our assumption).


Where were the ideas of vote, accept and commit phases originally introduced?

This dates back to the Byzantine broadcast algorithm of Bracha:

Bracha, Gabriel. "Asynchronous Byzantine agreement protocols." Information and Computation 75.2 (1987): 130-143.


What algorithm paradigm is a recursive solver of Sudoku?

Let us go over your paradigms one by one:

Local search: In this paradigm, we start with some solution and try to improve it by local changes. Local search can be applied to Sudoku in at least two ways:

Start with a non-legal solution (either not satisfying the Sudoku constraints or not conforming to the filled cells), and try to make local changes (say, one cell at a time) that make it more legal.
Same as before, only we also allow partially filled boards. In this case we might as well start with the board as given, and at each step pick a cell and fill in some legal value. When we get stuck, we can choose a cell and erase it, and so on. This is a stochastic form of local search which in some sense goes against the essence of classical local search, which is completely deterministic and strives to reach an arbitrary locally optimal solution.

Dynamic programming: In this paradigm, we reduce our instance to smaller instances in such a way that the "repertory" of smaller instances is small, and each could be reached in many different ways.  One way you could try to implement this paradigm to Sudoku is as follows. Pick an empty cell and fill it in all possible legal ways. For each such filling, check whether it leads to a solution. Each filling is a smaller problem since it has fewer empty cells. However, the number of possible smaller instances is huge, and each is reached in a unique way, so while this is the same as your recursive solution, it's not really in the spirit of dynamic programming.
Greedy: In this paradigm, you repeatedly make choices that you cannot later change. In the case of Sudoku, this corresponds to identifying unfilled cells which have only one legal filling. This is the approach used by most humans to solve Sudoku, though some puzzles require rather elaborate case analysis to find such safe fillings.
Divide and conquer: In this paradigm you divide your instance into independent instances which you solve separately, and then use their solutions to solve the original instance. One way this could be applied to Sudoku is by finding all possible solutions of 3×3 squares, and then try to combine them together. This is not only a terrible algorithm, but also the recursion is very shallow, whereas in divide and conquer we are aiming at deeper levels of recursion.
Backtracking: The standard recursive approach for Sudoku (pick a cell, enumerate all values, and recurse) is a great example of backtracking, which is the paradigm that best describes this algorithm.


No, it's not known whether $PH \subset PP$, and it's not known whether $PP \subset PH$.  Neither of those is implied by Toda'a theorem.

This blog article cites a paper by Beigel giving some weak evidence to suspect that $PH \not\subset PP$ (that $PH$ is not contained in $PP$).  Please be warned that this is very weak evidence and doesn't really prove anything.  The result says that there's a relativized world where $P^{NP}$ is not contained in $PP$.  It follows that there's a relativized world where $PH$ is not contained in $PP$.  This might suggest the conjecture that $PH \not\subset PP$.  Or, at least, it suggests that proving $PH \subset PP$ might require special proof techniques (non-relativizing proof techniques; and most, but not all, known proof techniques do relativize).


How fast we can run 128-bit LCG generator?

If you have a linear congruential random number generator X, then applying X say 8 times is another LCG whose constants are easy to find. If X calculated a series a0, A1.a2 etc. then you can calculate a0 to a7, and then apply Y to all 8 numbers in parallel, assuming this takes a lot less than eight times the effort.
I hope you know how to calculate the same LCG many times without divisions.


How to Generate Control flow graph from a Petri net model?

Since you are interested in generating test sequences automatically using colored Petri nets, note that it's not clear that you need reduction to control flow graphs (and dealing with all the related issues). Some techniques were presented, that use various different methods to generate test sequences from Petri nets. Some examples include:

H. Watanabe and T. Kudoh, "Test suite generation methods for concurrent systems based on coloured Petri nets," Software Engineering Conference, 1995. Proceedings., 1995 Asia Pacific, Brisbane, Qld., 1995, pp. 242-251.

J. Desel, A. Oberweis, T. Zimmer and G. Zimmermann, "Validation of information system models: Petri nets and test case generation," Systems, Man, and Cybernetics, 1997. Computational Cybernetics and Simulation., Orlando, FL, 1997, pp. 3401-3406 vol.4.

Xu, Dianxiang. "A tool for automated test code generation from high-level Petri nets." Applications and Theory of Petri Nets. Springer Berlin Heidelberg, 2011. 308-317.

On the other hand, since Petri nets and control flow graphs are not semantically equivalent in general (and capture different type of information), the translation between the two is usually done in some specific domain (and restrictions). (Although usually, control flow graphs can be transformed into equivalent Petri nets.). Some examples and discussions are given in:

De Jong, Gjalt G. "Data flow graphs: system specification with the most unrestricted semantics." Proceedings of the conference on European design automation. IEEE Computer Society Press, 1991.

The Design Of A General Method For Constructing Coupled Scientific Simulations, Matthew J. Sottile

Note that your question seems a bit too general. (Moreover, it also seems as an instance of XY, as noted by D.W.) Without more details, it seems hard to give a concrete and concise answer. Hopefully, given pointers can get you closer to your desired goal.


Why are there $2^{2^{n}}$ possible boolean functions of n inputs?

Hint:
let $f$ be a boolean function with $n$ inputs  i.e $f(b_{1},b_{2},b_{3}...b_{n})$
For example, when $n=3$,   $(1,0,1)$ and $(1,1,0)$ are  different inputs to $f$.
Each input maps to an answer. Also there are limited values that  $f(b_{1},b_{2},...,b_{n})$ can take.

Now consider the definition of a function: $f\colon A \to B$

Define  the size of both  sets $A$ and $B$ and you will arrive at your answer.


Identifying the Equivalence Classes of a Language with equal number of 10 and 01 strings

It's a trick question.

They try to make you think that you have to count how many 01 strings and how many 10 strings there are, but you don't have to.

Say the first letter is 0. So far, no 01 and no 10 strings. This doesn't change if there are more zeroes. But if we find a 1, we now have got a 01 string. Nothing changes until we get a zero, and we have one 01 and one 10 strings. Again, more zeroes don't change this, the next 1 means the number of 01 strings is one higher than 10, and the next 0 after that makes the number equal again.

You can see that if we start with a 0 and process more letters, every time the string ends with a 1 the 01's are one ahead of the 10's, and when the string ends with a 0 their counts are equal.

You do the same for the case that the string starts with a 1. Again the counts are equal every time the last digit is a 1 and unequal every time the last digit is 0. Counts are equal every time the first and last digits are the same.


Is a BST considered a data structure or abstract data type

A binary search tree is a data structure.  The interface it supports (the list of operations you can perform on it and their semantics) is an abstract data type.

See https://en.wikipedia.org/wiki/Abstract_data_type for explanation of the difference between an ADT and a data structure.