Why are the laws of an applicative functor defined the way they are? Let's recall the definition of an applicative functor. Throughout this question, I write $x: T$ to denote that the value $x$ has type $T$.

Definition: An applicative functor consists of a type constructor $F: * \to *$ together with two operations:

a function $\mathsf{pure}: A \to F(A)$ that transforms a base value $x: A$ into a "wrapped" value $\mathsf{pure}(x): F(A)$.
a binary operation $\circledast: F(A \to B) \to F(A) \to F(B)$ that applies a wrapped function $f: F(A \to B)$ to a wrapped value $x: F(A)$ and produces a wrapped result $f \circledast x: F(B)$.

We require these operations to satisfy the following conditions:

Wrapped identities apply as identities.
$$ \mathsf{pure}(\operatorname{id}) \circledast x = x $$

Wrapped composition applies as composition.
$$ \mathsf{pure}(\circ) \circledast f \circledast g \circledast x = f \circledast g \circledast x $$
Here, $\circ$ denotes the function composition operator.

Wrapping distributes across function application.
$$ \mathsf{pure}(f(x)) = \mathsf{pure}(f) \circledast \mathsf{pure}(x) $$

Wrapping exchanges across application.
$$ f \circledast \mathsf{pure}(x) = \mathsf{pure}(g \mapsto g(x)) \circledast f $$

Question: Why are these the "correct" laws for an applicative functor? To be more precise,

Are these laws known to be logically independent, in the sense that none of these four laws can be derived from the other three?
Assuming the answer to question 1 is "yes," what essential characteristic of applicative functors would be lost if we dropped each law, in turn, from the definition? In other words, for each law $L$, there should exist structures $(F, \mathsf{pure}, \circledast)$ satisfying all laws except $L$; why do we not want to call these applicative functors?

As described in the original idioms paper, Applicative (called Idiom there) corresponds to a strong lax monoidal functor. This can be formulated as:

class (Functor f) => MFunctor f where
    unit :: () -> f ()
    pair :: (f a, f b) -> f (a, b)

The applicative functor laws are then equivalent to the above operations being "monoidal" in the following sense (plus the functor laws):

fmap snd (pair (unit (), u)) = u
fmap fst (pair (u, unit ())) = u
fmap (\(a, (b, c)) -> ((a, b), c)) (pair (u, pair (v, w))) = pair (pair (u, v), w)

The "strength" aspect comes from the fact that these operations (and the functor ones) are "first-class". In a language without higher-order functions, the lax monoidal functor would not be strong. (The usual presentation of Applicative doesn't even make sense in a language without higher-order functions whereas the MFunctor presentation does.)

So, dropping any of the laws means you don't have a lax monoidal functor.

Yet another way of looking at it is to note that the applicative functor operations and laws give rise to a family of operations: liftN :: ((a1, ..., aN) -> b) -> (f a1, ..., f aN) -> f b with unit = lift0 id and pair = lift2 id. Using Agda, we could present this more formally as:

open import Level

data List {i : Level}(A : Set i) : Set i where
    Nil : List A
    Cons : A → List A → List A

record ⊤ : Set where
    constructor tt

record _×_ (A B : Set) : Set where
    constructor _,_
    field
        fst : A
        snd : B

All : (Set → Set) → List Set → Set
All P Nil = ⊤
All P (Cons x xs) = P x × All P xs

module _ {F : Set → Set}
    (map : {A B : Set} → (A → B) → F A → F B)
    (unit : ⊤ → F ⊤)
    (pair : {A B : Set} → F A × F B → F (A × B))
 where
    pull : {As : List Set} → All F As → F (All (λ A → A) As)
    pull {Nil} tt = unit tt
    pull {Cons A As} (x , xs) = pair (x , pull {As} xs)

    liftN : {B : Set}{As : List Set} → (All (λ A → A) As → B) → All F As → F B
    liftN f xs = map f (pull xs)

This perspective arises due to the connection between monoidal categories and multicategories. A lax monoidal functor corresponds to a map of multicategories, liftN being the action on multiarrows. If Haskell had multi-ary functions, it would be natural to model it with a multicategory. The appropriate analogue of "functor" would be a map of multicategories, i.e. an applicative functor. From the multicategory perspective, the applicative functor laws are what make the action on multicomposition coherent. Roughly speaking, if we dropped, say, the associative law for pair, this would be akin to having functions with a binary tree of parameters instead of a list of parameters. One could explore generalized multicategories for this.


Complexity to insert subset of array to minimize order inversions I'm not entirely sure what to call this, or if there are good reductions to other known problems, so references to those will help.
As input you're given an array $A$ of length $n$ of distinct elements, and another array $B$ of length $k < n$ that contains a subset of the elements in the first array, potentially in a new order. The output should be an array of length $n$ with every element in $A$ such that the relative order of every element in $B$ is preserved, and the order of elements in $A \setminus B$ should minimize the number of inversions with respect to $A$.
For example, take as input $A = 1, 2, 3, 4$ and $B = 1, 4, 2$, then the output could be either $1, 3, 4, 2$ or $1, 4, 2, 3$, as each have one inversion caused by the placement of 3, which is the smallest you can achieve without altering the order in $B$.
This can pretty trivially be done in $O(k (n - k) + n)$, where for each element in $A \setminus B$ you scan through $B$ and compute the number of inversions that would happen if inserting there, and simply put the element in the gap that minimizes it. However, this is worst case $O(n^2)$ depending on $k$, and that seems avoidable. In particular, it seems like there should be some invariants in the relative order of elements that need to be placed that should save some time.
There are small tweaks that make it better, but that don't improve the worst case complexity. For example, take two elements $c_1, c_2 \in A \setminus B$, where $c_1$ comes before $c_2$ in $A$. After finding $c_1$'s optimal position, $c_2$ must come after it in the final order.
Psuedo Code
fn min_inversions(a_order, b_order)
    # all ordered elements for constant time access
    b_set := set(b_order)
    # all elements left of element considering for rank inversions
    left_set := set()
    # where to start looking for insertions
    # equal to the last insertion found, helps time, but not worst case
    start_index := 0  # index to start scan for minimum
    # array for each gap between elements in b_order, we insert the missing elements here
    # since we process missing elements in order, we can append to preserve order
    insertions := [[] for _ in 0..len(b_order) + 1]

    for ai in a_array:
        if ai in b_set:
            # don't need to locate, but mark as left of considered element to compute inversions
            left_set += set(ai)
        else:
            # number of inversions for placement in any considered gap
            # initial value is arbitrary as we only care about relative value, but this setting is "correct"
            inversions = [size(lef_set)]
            for bi in slice(b_order, start_index):
                change = -1 if bi in left_set else 1
                inversions += [inversions[-1] + change]
            start_index = start_index + argmin(inversions)
            insertions[start_index] += [ai]
    # here insertions has everything from A\B in the optimal gap, just need to interleave with the initial B
    result := interleave(insertions, b_order)
```

Since this problem is basically about merging the element not in $B$ with element in $B$ to minimize order inversions, this answer will be focused on the following problem. The algorithm and analysis hereof can be extended to the problem in the question easily.

$A$ is a sorted array of $n$ integers. $B$ is an array of $m$ integers. $n\gt0, m\gt0$.
How can we merge them into one array efficiently without changing the order of elements in $B$ so that the result array has minimum number of inversions?

As OP indicated, the problem above can be done trivially in $O(nm)$. "For each element in $A$ you scan through $B$ and compute the number of inversions that would happen if inserting there, and simply put the element in the gap that minimizes it."  The OP also noted that in the result array, we should keep elements that come from $A$ sorted.
The observations above given by OP lead to the following recursive helper algorithm that gives the indices where elements of $A$ should be inserted into $B$. The simple idea is "binary insertion". That is, insert the middle element into $B$, then recurse.
Pythonic notations will be used.
Input: $A$ is an array with $A[sa\colon ea]$ sorted. $B$ is another array with subarray $B[sb\colon eb]$ specified. $I$ is an array of the same length as $A$.
Output: updated $I$, such that if for each element $A[i]$ in $A[sa\colon ea]$, we insert $A[i]$ right before $B[I[i]]$, keeping the original order of $A$ among themself, the inversion number of $A[sa\colon ea]$ merged with $B[sb\colon eb]$ is minimized.
Procedure:

If $sa\ge ea$, return.
Let $ma = (sa + ea)//2$
Scan through $B[sb\colon eb]$ to find the indice $mb$ in range($sb\colon eb+1$) such that if we put $A[ma]$ right before $B[mb]$, we will have minimum number of inversions that consist of $A[ma]$ and an element in $B[sb\colon eb]$.  (Or, any one of those optimal indices).
Let $I[ma] = mb$.
Call this procedure with $A[sa\colon ma-1]$, $B[sb\colon mb]$ and $I$.
Call this procedure with $A[ma+1\colon sb]$, $B[mb\colon eb]$ and $I$.

To solve the initial problem, we will do the following.

Initialize $I$, an array of $n$.
Run the algorithm above with $A[0\colon n]$, $B[0\colon m]$ and $I$
Merge $A$ with $B$ according to $I$.
Return the merged array.

If implemented properly, the algorithm above runs in $O(m\log n + n\log m)$ time. It can be proved that $O(m\log n + n\log m)$ time is optimal. It uses $O(n)$ auxiliary space.
The algorithm here is, basically, doing the same thing to find the same arrangement as in OP's pesudocode. Only more efficiently.
It is a nice exercise to prove the correctness of either algorithm.

If the given array $A$ is not sorted, then sort it at the start of the algorithm. That will add $O(n\log n)$ to its time-complexity.


Cutting yarn into integer-length pieces to maximize profit based on known prices for each length My classmates and I were working on a problem on our introduction to algorithms homework, but we are having a lot of trouble wrapping our heads around it. Below is the problem:

  We are given a string of yarn of length $n$ meters, and our goal is to cut this yarn into integer-length pieces. For every integer $1..n$ we know the selling price of a piece of yarn of that length. We call the selling price of a string of yarn of length $i$ by $p_i ≥ 0$. We must give an algorithm to compute the maximum amount of money that we could make by cutting the string into integer-length pieces. Our algorithm must run in $O(n^2)$.

So we know that this type of problem can be solved using a dynamic programming approach, but we're having trouble coming up with a recurrence relation. We think that we should start with an array $L$ such that $L[i]$ denotes the maximum amount of money given with a certain amount of cuts, but we're uncertain about how exactly we should represent this and where to go on from here.

Thanks a lot in advance!

This answer isn't really helpful for your assignment and isn't framed in terms of dynamic programming. It's just about solving the problem fast.

This problem can be solved in $O(n \lg^2 n)$ time by using iterative max-convolution on the prices.

Max-convolution takes an array $a$ and tells you $\max_j^d (a_j + a_{d-j})$ for each starting offset $d$. By being clever you can do it in $O(n \lg n)$ time instead of $O(n^2)$, kinda reminiscent of the convolution theorem.

edit: but see @Kaban-5's important caveat in the comments, about this algorithm depending on random inputs instead of random choices!

The key thing to realize is that, if the price for a piece of length $d$ is less than the price of a piece of length $d-j$ plus a piece of length $j$, then the effective price for a piece of length $d$ should increase to the sum of those two prices. And if we keep looking for these pricing inefficiencies and fixing them, we'll converge on the true optimal selling price for each length.

A single max-convolution will replace every price with the maximum you can get by splitting a piece into up to two pieces and selling all the pieces. A second max-convolution will be searching through all splits into up to 4 pieces. The third goes up to 8. And so forth until we hit up-to-$n$ after the $\lg n$'th max-convolution.

Here's the algorithm:

def bestSplitPrice(prices):
    """
    Assuming you have a piece of yarn of length len(prices)+1, find
    the best price you can get by cutting it and selling the pieces
    at the given prices-per-length.
    """
    prices = [0] + prices #A zero-length piece costs nothing
    for i in range(ceil(lg2(prices))):
        prices = max_convolve(prices, prices)[:len(prices)]
    return prices[-1]

And here's an example:

prices = {1:1$, 2:3$, 3:3$, 4:4$, 5:5$, 6:5$, 7:7$}
# array-ify, including 0-length price
prices = [0, 1, 3, 3, 4, 5, 5, 7]
# max-convolve lg2(8) = 3 times
prices = [0, 1, 3, 4, 6, 6, 7, 8]
prices = [0, 1, 3, 4, 6, 7, 9, 10]
prices = [0, 1, 3, 4, 6, 7, 9, 10]

The best piece-price for length-7 is 10$

Here's how the max-convolutions play out if only the 1$ piece is given a price:

prices = [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
prices = [0, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
prices = [0, 1, 2, 3, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3]
prices = [0, 1, 2, 3, 4, 5, 6, 7, 8, 7, 7, 7, 7, 7, 7, 7]
prices = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15]

Notes:

I suspect this can be cut to $O(n \lg n)$ by having the max-convolutions double-hitting exponentially larger and larger sections of the array.


NTIME(f) subset of DSPACE(f) As the question states, how do we prove that $\textbf{NTIME}(f(n)) \subseteq \textbf{DSPACE}(f(n))$?

Can anyone point me to a proof or outline it here? Thanks!

Here is an expanded version of Igor Shinkar's comment. The simplest way to simulate a non-deterministic machine running in time $f(n)$ and space $s(n) \leq f(n)$ uses $s(n) + 2f(n) + O(1)$ space. We enumerate over all possible coin tosses, simulating the original machine on each of them; this requires space $f(n)$ for storing the coin tosses, and $s(n)$ space for simulating the actual machine. There is a slight difficulty here: when the coin tosses are "read" by the (original) machine, we need to mark somehow where we are in the sequence of coin tosses; we can use an additional bit per coin toss. It is probably possible to optimize this even further.

If we're careful, we might be able to get something even better, since in each run of the program, the total number of coin tosses and the total space used add together to at most $f(n)$. I suspect it's possible to run the simulation in $(1+o(1))f(n)$ space. Perhaps we will need to assume something like $f(n) = \Omega(\log n)$ for that.

As Igor mentions, usually resource-bounded classes are only defined "up to big O", so that the result, which uses space $O(f(n))$, is still in $\mathrm{DSPACE}(f(n))$.


single algorithm to work on both directed and undirected graph to detect cycles? I have been trying to implement an algorithm to detect cycles (probably how many of them) in a directed and undirected graph. That is the code should apply for both directed and undirected graphs.

Using DFS or topological sort is mostly recommended in various posts. But largely, everything is addressed for undirected graph.

This link describes one approach for cycle detection. To my understanding this works for directed graphs.

This link has the code for cycle detection in undirected graphs. but I fail to understand how it ignores the back edge. That is it must ignore any cycles with two nodes, say D to C and C to D.
which means it must remember it parent as the DFS recurses. But the code does not seem take care of that.

Any suggestions welcome..

Take a look at the answers for finding all cycles in graph.

You can transform undirected graph into a directed graph quite easily: for every edge (u,v) in your original graph G, put two edges (u --> v) and (v --> u) into your new directed graph T. Apply any of the algorithms that find cycles in a directed graph on T. However, notice that any undirected edge transforms into a directed cycle (u - v - u), so if your original graph was initially undirected, you can ignore cycles of length 2 at the end.


How to write suitable three address code for switch-case statements? I want to translate a java switch-case statement to intermediate representation of the three address code form. Three address code or TAC is a form of intermediate representation where each instruction contains at most three addresses and one operator. An address is a name such as x (stored in the symbol table), compiler generated temporary such as $t_{1}$ or a constant such as 3.14 or ‘s’. A name could refer to a variable, label, etc.
If you have an arithmetic statement

(3 * w) + y

then the corresponding TAC would be

$t_{1}$ = 3 * w
$t_{2}$ = $t_{1}$ + y

Now, when it comes to switch statements, my textbook (the Dragon Book for Compilers), gives a translation of this form:

for a switch-case statement of this type:
switch E
case V1: S1
...
case Vn-1: Sn-1
default: Sn
Assuming the first translation is used, at the code generation stage (when we convert 3AC to machine code), the code generator will interpret the instructions as a sequence of conditional and unconditional jumps with intervening labeled statement blocks. It would translate them into the machine code (say x86) version of the same. When these instructions are executed by the processor, it handles each jump sequentially to determine the correct labeled block to be executed.
But, I have also read that the machine code translation of a switch-case statement includes a jump table that allows the processor to execute the entire switch statement in one go. So, then which version is used?
I wanted to post this on stackoverflow but I do not have enough reputation to post an image.

Some more things to look at:

First, mixed table/branch approach. Say you have cases 1, 2, 3, 4, 5, 6 and 999,999,999. You might check for 999,999,999 first, then use a table for the rest. And remember for the table approach that you need to check if the case is within the table. So take a table for 0-5, compare if case ≥ 6, if not you use the table, if yes, you handle the remaining case.

Second, probably most important: Binary search. Say you have cases 1-20. First you compare against 10. Branch to a second compare block if the case is >10. That alone halves the average number of comparisons needed.

Third, take advantage of one comparison usually giving multiple results. If you know that x = 1, 2 or 3, then you need only one comparison with 2 and two conditional branches.


Is (λx.FV(A)) and (λx.FV(B)) β-equivalent? Does free variables have some meaning in lambda calculus? If I follow this β-reduction
(λx.λz.y x) y
    -> (λz.y x){x/y}        (variable FV(y) captured)
    -> ((λz.y x){a/y}){x/y} (rename FV(y) -> FV(a)){
    -> (λz.a x){x/y}
    -> (λz.a y)

Here we have FV(y) captured during the β-reduction, so I rename it to FV(a) and continue the reduction. Is this result even valid?
I would rename the y argument instead
(λx.λz.y x) y
    -> (λz.y x){x/y}        (variable FV(y) captured)
    -> (λz.y x)({x/y}{y/a}) (rename argument FV(y) -> FV(a)
    -> (λz.y x){x/a}
    -> (λz.y a)

If I use De Bruijin index notation for both outputs I would get:
(λz.a y) -> (λ.1 2)
(λz.y a) -> (λ.1 2)

so they seem β-equivalent for me.
This means that FV has no meaning at all, FV(a) β= FV(b) β= FV(c) ...  is my understanding right?
I'm asking because when applying lambda calculus I would like to have some global variables that are not bound by the expression but are bound by the context, things like *, +, sqrt, etc, in this case I cant just replace free variables because they may have a meaning, what would I do so?

Thanks @lemontree for your answer, I'm implementing a lambda calcualtor so I need to take care of every single step. I write things in the math notation (λx.x) y and then translate to the expected code Appl(Lamb('x', 'x'), 'y'), M[x/y] m.replace('x', 'y'), so having a notation for every step help me a lot :).
I search but can't find any special notation for ɑ-conversion so I came up with M[BV(x)/y] to denote that x is not free in M and to make it distinct from M[x/y]. And a special function NX that returns the next available variables. Here is how I reduced your example (thank you!)
    (λx.λy.y x) y
        -> (λy.y x)[y/x]
        -> (λy.y[y/x] x[y/x])               CAPTURE ERROR on y (backtrack)
        -> (λy.y x)[BV(y)/NX(x, y)][y/x]    NX(FV ∪ BV) returns the next available variable
        -> (λy.y x)[BV(y)/z][y/x]
        -> (λz.z x)[y/x]
        -> (λz.z[y/x] x[y/x])
        -> (λz.z y)

The bits that I missed

A definition of available variables not (FV ∪ BV). I need this to implement ɑ-conversion
A formal notation for ɑ-conversion

Is there anything like this in the literature? Thanks in advance :)

Free variables have a "meaning" in the sense that two free variables (as opposed to two bound variables) are not $\alpha$-equivalent -- and that's precisely why your first reduction is not correct: We are not allowed to do "free renaming", only bound renaming!
Capture avoiding substitution is defined as

If $x \neq y$ and $y \in FV(N)$ and $x \in FV(P)$, then, where $z \not \in FV(N) \cup FV(P)$:
$(\lambda y.P)[N/x] = \lambda z.(P[z/y][N/x])$

Capture avoiding substitution happens only when a variable occurring free in $N$ is bound by lambda abstraction in the term to substitute ($y \in FV(N)$) and there are actual occurrences of $x$ in $P$ to substitute ($x \neq y$ and $x \in FV(P)$). In that case, we rename the bound variable in the term that undergoes substitution (the function body), i.e. $(\lambda y.P) \rightsquigarrow \lambda z. (P[z/y])$, then perform the actual substitution of $N$ for $x$ in $P'$. We do not rename free variables, and we do not perform renaming in the argument.
In your example, beta-reducing $(λx.λz.y x) y$ means to replace every free occurrence of $x$ in $\lambda z. yx$ by $y$ provided that $y$ is free to substitute. y will not be captured by anything: As you observe, $y$ is free in $\lambda z.yx$, and that's precisely why there is no capturing and thus no capture avoiding to perform, and the substitution can be done directly. Thus the correct reduction is

$\newcommand{\bred}{\triangleright_\beta}
\phantom{\triangleright_\beta} (\lambda x. \lambda z. yx)y\\
\bred (\lambda z.yx)[y/x]\\
= \lambda z. (yx[y/x])\\
= \lambda z. (y[y/x])(x[y/x])\\
= \lambda z. yy$

De Bruijn indexing on this term is vacuous, because there are no pairs of binding and bound variables ($\lambda z$ does not bind any occurrences of $z$, and the two occurrences of $y$ are not bound by any abstraction $\lambda y$).

A case where capture avoiding substitution would be needed is if the argument $y$ were bound in the function body, e.g. if instead of the vacuous abstraction $\lambda z$ there were $\lambda y$:

$(\lambda x. \lambda y. yx)y\\
\bred (\lambda y.yx)[y/x]\\
= \lambda z. (yx[z/y][y/x]) \quad \text{(avoiding catpure of $y$)}\\
= \lambda z. (zx[y/x])\\
= \lambda z. zy$

Re. notation and implementation:
It depends a bit on how you define it, but the way I used it above (which is the approach chosen in e.g. Hindley & Seldin (see below):
When bound renaming has to happen to avoid variable capture, then this is part of the definition of substitution, i.e. the result of $(\lambda y.P)[N/x]$ with $y$ free in $N$ syntactically identical ("$=$", rather than just $\alpha$-equivalent) to $\lambda z.P[z/y][N/x]$.
To express $\alpha$-equivalence in the sense that a pair of terms only differs in their bound variable names, you can write $\equiv_\alpha$.
Alternatively, one could define beta reduction such that substitution can only be performed if no variable conflict occurs, and if it does, one has to prepend a step of $\alpha$-renaming before $\beta$-reducing.
"not $FV(A) \cup FV(B)$" is just the set-theoretic complement relative to the set of all variables, $VAR - (FV(A) \cup FV(B))$. To implement a choice of "the first variable not in $FV(A) \cup FV(B)$" you need to presuppose an ordering of variables such as $x < y < z < x_1 < ... x_n$ and then do something like $min\{x: x \in VAR \land x \not \in FV(A) \land x \not \in FV(B)\}$. The set of free and bound variables is defined by straightforward recursion on the structure of the lambda term.
Furthermore, for a precise notation in the implementation one may want to distinguish between an atomic beta reduction/variable renaming step vs. reducibility/equivalence through a chain of reductions/renamings, as well as $\beta$-reducibility monotonously downwards from $A$ to $B$ as opposed to $\beta$-equivalence by finding a common term both reduce to.
For variables you should use $x, y, z, u, v, w, x_1, x_2, \ldots$; wheras $a, b, c, \ldots$ are more typically understood as constants.
Constants is also what objects and functions interpreted "by context" such as $*, +, sqrt$ would naturally be treated as; their meaning is "fixed from the outside" and you can combine lambda reduction with custom inference steps like $(\lambda x.+xx)(2) \bred +22 =_\mathbb{N} 4$.
You can find the notation I used and all the definitions necessary for rigorously implementing substitution etc. in (amongst others)
J. R. Hindley & J.P. Seldin (2008), Lambda calculus and combinators: an introduction.
Another classic is
H. Barendregt (1992), Lambda calculi with types.


How to recursively infer a word/string from a context-free grammar? Give the recursive inference of the word $abcddd$ from the Context-free Grammar:

  $A\rightarrow aAd\mid B$
  $B\rightarrow bBd\mid C$
  $C\rightarrow cC\mid cD$
  $D\rightarrow Dd\mid ϵ$

This is a follow up question to this one here. Much like that question I haven't found any good information on the subject. I understand the inductive proof of an inferred word belonging to a language, but I don't know how to put it to practical use. I have found an example in our course literature, "Introduction to Automata Theory, Languages, and Computation" by Hopcroft, Motwani and Ullman, but they only have a filled out table of the inference of several words without any detailed explanation on how they got there.

I tried to mimic that table for this excersice and think I have solved it, but I don't understand what I'm doing or if I'm even doing it right. What I need is someone to explain the thinking behind this algorithm or whatever it is they are using. Here is the table I have created for the word $abcddd$:

$$
   \begin{array}{ r | c | c | c | c }
   & \textit{String Inferred} & \textit{For language of} & \textit{Production used} & \textit{String(s) used} \\ \hline
   (i) & ϵ & D & D \rightarrow ϵ & - \\
   (ii) & d & D & D \rightarrow Dd & (i) \\
   (iii) & cd & C & C \rightarrow cD & (ii) \\
   (iv) & cd & B & B \rightarrow C & (iii) \\
   (v) & bcdd & B & B \rightarrow bBd & (iv) \\
   (vi) & bcdd & A & A \rightarrow B & (v) \\
   (vii) & abcddd & A & A \rightarrow aAd & (vi) \\
    \hline
  \end{array}
$$

To me this is just like deriving words, but backwards, if you know what I mean? So, I am doing this correctly? Why am I doing this, instead of just deriving words "as usual"?

You are correct to realize that this is just like deriving words, but backwards. The authors admit this when they say "However, it is often more natural to think of grammars as used in derivations, . . ."

Labeling the productions as $A\rightarrow aAd$ (1), $A\rightarrow B$ (2), $B\rightarrow bBd$ (3), $B\rightarrow C$ (4)m $C\rightarrow cC$ (5), $C\rightarrow cD$ (6), $D\rightarrow Dd$ (6), and $D\rightarrow\epsilon$ (8) we can produce this derivation
$$
A\stackrel{(1)}{\Longrightarrow}aAd\stackrel{(2)}{\Longrightarrow}aBd\stackrel{(3)}{\Longrightarrow}abBdd\stackrel{(4)}{\Longrightarrow}abCdd\stackrel{(6)}{\Longrightarrow}abcDdd\stackrel{(7)}{\Longrightarrow}abcDddd\stackrel{(8)}{\Longrightarrow}abcddd
$$
and reading this from right to left gives exactly the table you had.

Frankly, it's not a topic I cover when I'm teaching this material.


What are some of the functions in TC1? Are there any non-trivial functions in TC1? Apart from that are there functions which are known to be in NC2 but not in TC1?

According to wikipedia, topological sorting is in NC2. Note sure whether this is trustworthy, the proposed algorithm seems to require AC2:

  One method for doing this is to repeatedly square the adjacency matrix of the given graph, logarithmically many times, using min-plus matrix multiplication with maximization in place of minimization. The resulting matrix describes the longest path distances in the graph. Sorting the vertices by the lengths of their longest incoming paths produces a topological ordering (Dekel, Nassimi & Sahni 1981).

To check whether this algorithm is really in NC2 instead of just AC2, note that even so a single addition could take log log n time, all the additions of a max-plus matrix multiplication can be done in parallel. However, it is unclear how to do a single binary max operation in constant time.

It looks as if the max operations of a max-plus matrix multiplication cannot all be done in parallel. Maybe there is some trick to get the max of n numbers with log n bits in log n time, but I cannot see it at the moment. Edit: Here is the trick: Expand the numbers from binary to unary, then the maximum can be computed independent for each bit. Since conversion between unary and binary can be done in AC0 in both directions, it looks like we don't just get NC2, but even AC1. So this is even an example for the real question, i.e. a non-trivial function in TC1.

As Emil Jeřábek pointed out, there is no end to functions in TC1:

  all context-free languages, determinants over Z and over finite fields, various related problems in linear algebra (matrix powering, matrix inverse, characteristic polynomial, solvability of linear systems)

However, I have the impression that all those examples are also in AC1 or even weaker classes like SAC1. Just like my example which initially was even unclear whether it is in NC2, they don't need the power of TC1.

Coming up with examples which are in TC1 (or NC2) and really need TC1 (or NC2) will be extremely challenging.


Iterative Fibonacci algorithm correctness proof, finding loop invariants The algorithm take in an integer $n$ and outputs the $n$th number in the Fibonacci sequence ($F_n$). The sequence starts with $F_0$. I am trying to prove the correctness assuming valid input:

int Fib(int n) {
    int i = 0;
    int j = 1;
    int k = 1;
    int m = n;
    while(m >= 3){
        m = m-3;
        i = j +k;
        j = i+k;
        k = i + j;
    }
    if(m == 0 ){
        return i;
    }
    else{
        if(m == 1){
            return j;
        }
        else{
            return k;
        }
    }
}

For a reminder, a loop invariant is a claim which holds every time just before the loop condition is checked. It holds even when the loop condition is false. I've established and proven one loop invariant that $m \geq 0$. This helps me show that the algorithm terminates since when the loop exits since $m$ is either 0, 1, or 2. However, I'm stuck on finding another loop invariant that would help me show that the algorithm produces the correct Fibonacci number.

One pattern I found is that the result of returning i, j, or k is due to the result of the initial value of $m$ $\% 3$. Depending on the remainder, either i, j, or k is returned. I tried expanding this idea further but led myself to a dead end. I'm thinking I need to find some way to express $F_n = F_{n-1} + F_{n-2}$ in terms of i, j and k in order to prove that the program outputs correctly. Am I on the right track with remainders or is there something I'm missing?

It kind of depends on what formalism you want to use for this proof.. But the core-idea which holds for pretty much any such formalism is the following:

Suppose you establish some invariant $I$ you will want to be able to make the following conclusion

$$
m < 3 \land I \implies X
$$

where $X$ tells you that the values $i,j$ and $k$ have the right values.

You are on the right track with the argument $I = I' \cup \{ m = n \mod 3 \}$, however $I' = \{m \geq 0\}$  is way too weak to establish that $\texttt{Fib}(n)$ returns the $n$th Fibonacci number.

Try the following:

Find some existential (for some value, eg. $z$) claim about the relationship of $n$ and $m$ (seems like you already did so)
Now use that value $z$ to show $\{ k = F_z, i = F_{z-2}, j = F_{z-1} \}$1

I hope this will help you!

1: Depends on your claim about $m$ and $n$, could also be shifted $\{ k = F_{z+2}, i = F_z, j = F_{z+1} \}$ as in gnasher729's answer which is simpler. The core idea is the same.


Could all CPU instructions get fundamentally faster if a better multiplication method was developed I was reading the article Integer multiplication in time O(n log n) by David Harvey and Joris Van Der Hoeven, 2019.

Could this discovery increase the throughput of future CPU's? If so could we determine by how much preemptively?

I don't see the relevance.

New multiplication algorithms only offer a practical improvement for numbers with huge numbers of bits and probably don't beat existing algorithms until you're dealing with numbers with thousands or even millions of bits. For an extreme example, Fürer's algorithm, which runs in time $O(n\log n\, 2^{O(\log^*n)})$ will only become competitive with Schönhage and Strassen's $O(n\log n\log\log n)$ algorithm for $n>2^{64}$ bits and, let's be honest, whatever it is that you're multiplying, it doesn't have $2^{64}$ bits. In contrast, CPUs operate on fixed-length words with a few tens of bits.
Most of what a CPU does isn't multiplying numbers, anyway.
Also, note that Harvey and van der Hoeven "make no attempt to... exhibit a practical multiplication algorithm" (page 2 of their preprint).


Does this behavior have a formal name, and if so, what is it? This is related to the issue asked about in this other question.

For the sake of this question, let's assume that we have a variable v that can have any value from the set of values

  "a", "b", "c", ..., "z"

In this case then the programmers wants to have specific code executed when the value of v is not "x", "y", or "z".

So the following IF statement is constructed:

  if (v != "x" || v != "y" || v != "z") {//do something}

Above statement would always return true, due to that the 3 conditions using negation are checked independently of each other.

Consequently, at any given time, any single one of the 3 conditions can evaluate to TRUE, leading to the entire IF statement evaluating to TRUE.

Anyway so the question I wanted to ask is, does this behavior or situation have a formal name, and if so, what is it?

In many programming languages above statement always returns true, due to that the 3 conditions using negation are checked independently of each other.

It returns true not just due to "that the 3 conditions using negation are checked independently of each other", but because the expression (v != "x" || v != "y" || v != "z") is always necessarily true. In logic such expressions are called tautology, i.e. a formula that is true in every possible interpretation (Wikipedia).

But "this behavior or situation" does not have a special name in programming and is usually considered as a programming error.


Min-coin change problem with limited coins I have been assigned the min-coin change problem for homework. I have to calculate the least number of coins needed to make change for a certain amount of cents in 2 scenarios: we have an infinite supply of coins and also where we only have 1 of each coin. I was able to quickly implement the solution for the first scenario using a recursive formula from here but was not able to find a recursive formula for the second case and I instead came up with an iterative solution.

We can just sum every possible combination of coins, check and see if the sum is equal to the target wanted and compare the number of coins used to the current lowest number of coins. I also realized that I can use binary counting to simulate all possible combinations using the bits in the iterator as a coefficient (either 1 or 0) for each coin and then calculate the Hamming Weight to check how many coins was used in the sum.

To visualize an example with 3 coins:

C1 C2 C3 | S                        | W
 0  0  0 | 0 * C1 + 0 * C2 + 0 * C3 | 0
 0  0  1 | 0 * C1 + 0 * C2 + 1 * C3 | 1
 0  1  0 | 0 * C1 + 1 * C2 + 0 * C3 | 1
 0  1  1 | 0 * C1 + 1 * C2 + 1 * C3 | 2
 1  0  0 | 1 * C1 + 0 * C2 + 0 * C3 | 1
 1  0  1 | 1 * C1 + 0 * C2 + 1 * C3 | 2
 1  1  0 | 1 * C1 + 1 * C2 + 0 * C3 | 2
 1  1  1 | 1 * C1 + 1 * C2 + 1 * C3 | 3

Obviously we can omit the case where all the coefficients are 0, but for completeness (when target = 0) and simplicity I've kept it in the solution.

My implementation in Python is:

import math

def least_coins(coins, target):
    least = math.inf

    # loop all 2^n possible sums of coins
    for i in range(2 ** len(coins)):
        sum = 0

        # add all the coins multiplied by their coefficient in this iteration
        for j in range(len(coins)):
            # get the j-th bit in i
            coefficient = i >> j & 1
            sum += coefficient * coins[j]

        if sum == target:
            count = 0
            # calculate the Hamming Weight of i to determine the number of coins used
            while i:
                i &= i - 1
                count += 1
            least = min(least, count)

    return least

coins = [3, 1, 1, 3, 2, 4]
target = 10
print(least_coins(coins, target))
>>> 3
# 3 + 3 + 4 = 10

As you can see the coins are not necessarily unique, but can only be used once. How can I turn this into a recursive formula (if possible and for the reason of possibly being able to optimize it using dynamic programming) or even introduce coefficients other than 0 and 1 so the problem can be more general where we have a certain amount of each coin?

Let $N(t,S)$ be the least number of values from $S$ which sum to $t$. The basic recurrence is
$$
N(t, S \cup \{s\}) = \min(N(t,S),N(t-s,S)+1).
$$
I'll let you work out the details.

This recurrence leads to an efficient algorithm only if we are allowed to run in time polynomial in $t$.

If we think of $t$ encoded in binary, then this algorithm runs in exponential time.

Indeed, the very related SUBSET-SUM problem is NP-complete.


Problem on Floating Point Representation Consider the floating-point representation

31-24 : Exponent
23-0  : Mantissa

The exponent is in 2's complement representation and mantissa is in the sign magnitude representation. the range of the magnitude of the normalized numbers in this represntaion is

  $(a)\ 0\ to \ 1$

  $(b)\ 0.5\ to\ 1$

  $(c)\ 2^{-23}\ to \ 0.5$

  $(d)\ 0.5\ to \ (1-2^{-23})$

My approach:
as the normalized number in floating point representation has as implicit 1.

Hence smallest mantissa would be

  $1.0000\cdots [24\ 0's]=1$

Largest mantissa would be

  $1.1111\cdots [24\ 1's]=1+(1-2^{-24})\approx2$

So my ans coming as 1 to 2, Which is not in the option. What mistake I'm doing..

First, this is not the way standard IEEE P754 single precision floating point numbers are represented :

Exponent is not two's complement, there is instead an offset, for IEEE normalised : F=2^(Exponent - 127) * 1.Mantissa * Sign
Normalised numbers have an exponent different from 00 (being denormals) and FF (for infinites, NaN)

If this peculiar format has no implicit 1, mantissa should be between 0.10[..]0000 and 0.11[..]1111 :  Answer (D) or between 1.0000 and 1.11111, which is your proposal.

(IIRC, Intel double extended x87 80bits format does not have the implicit 1 and works as you describe. It is not striclty IEEE compliant, the 8087 being older than the standard.)


algorithm to find all values that occur more than n/10 times I took an algorhytm course on coursera and there some optional questions for student enrichment. I can't solve the following task:

  Decimal dominants. Given an array with n keys, design an algorithm to find all values that occur more than n/10 times. The expected
  running time of your algorithm should be linear.

And authors provied following hint:

  Hint: determine the (n/10)-th largest key using quickselect and check
  if it occurs more than n/10 times.

Actually it is not cleat for me how can quick select help me. quick select is algorhitm which can help to find k-th largest element in linear time. In the lecture materials written that it work approximately linear.

Let's work with example. We have 100 elements array. We found 10-th elements.
( frankly speaking according the book we found such element order that all elements with index > 90 more or equals than elems[90] and all elements with index < 90 less or equals elem[90]

How can I calculate occurences?
Imagine, that we calculated occurences and it is less than 10. What would be the next step?

P.S.

Perhaps the hint was aiming at the following approach. Suppose that the array were sorted. If a value appears $m$ times and we divide the array into intervals of length $m$, then the value must appear at the end of one of the intervals. This suggests the following algorithm for finding all values that appear $n/C$ times: compute the $i \cdot n/C$-largest elements for $1 \leq i \leq C$, and for each of them, check whether the value appears at least $n/C$ times. Each iteration takes $O(n)$ time using Quickselect, for a total of $O(Cn)$ time.


Is a file a string of zeros and ones? Is a computer file just a string of zeroes and ones? If so, can it start with zeroes?
I have not been able to find an answer, surprisingly.

Yes the File has a binary representation and it can start with a leading zero.
To verify this open any file from your computer with an hex editor and modify the leading hex to 00.
You would most likely be unable to open the file, because you damage the signature but it still can be considered a valid file.


Getting negative cycle using Bellman Ford I have to find a negative cycle in a directed weighted graph. I know how the Bellman Ford algorithm works, and that it tells me if there is a reachable negative cycle. But it does not explicitly name it.
How can I get the actual path $v1, v2, \ldots vk, v1$ of the cycle?
After applying the standard algorithm we already did $n-1$ iterations and no further improvement should be possible. If we can still lower the distance to a node, a negative cycle exists.
My idea is: Since we know the edge that can still improve the path and we know the predecessor of each node, we can trace our way back from that edge until we meet it again. Now we should have our cycle.
Sadly, I did not find any paper that tells me if this is correct. So, does it actually work like that?
Edit: This example proofs that my idea is wrong.
Given the following graph, we run Bellman-Ford from node $1$.

We process edges in the order $a, b, c, d$. After $n-1$ iterations we get node distances:
$1: -5$
$2: -30$
$3: -15$
and parent table:
$1$ has parent $3$
$2$ has parent $3$
$3$ has parent $2$
Now, doing the $n$th iteration we see that the distance of node $1$ can still be improved using edge $a$. So we know that a negative cycle exists and $a$ is part of it.
But, by tracing our way back through the parent table, we get stuck in another negative cycle $c, d$ and never meet $a$ again.
How can we solve this problem?

You are right for the most part. Just one more addition. When you go back the predecessor chain when trying to find the cycle, you stop when you either reach the starting vertex $v_1$ or any other vertex that has already been seen in the predecessor chain that you have seen so far. Basically, you stop and output vertices whenever you detect a cycle when going backwards using the predecessors.
As for papers, a simple Google search yields Xiuzhen Huang: Negative-Weight Cycle Algorithms. As a bonus, they also list another algorithm for finding negative weight cycles that are not reachable from the source vertex $s$.


How the Abstract DPLL Algorithm Works in SAT Solving I have come across many definitions of the DPLL algorithm but haven't been able to follow them. The ones that are closest to making sense to me are the ones based on state-transition systems with transition rules such as defined here:

$F$ is a CNF formula, $C$ is a clause, and $M$ is a model. A description of it is as follows:

  Here, a DPLL procedure will be modeled by a transition system: a set of states
  together with a relation, called the transition relation, over these states. States
  will be denoted by (possibly subscripted) $S$.... A state is either fail or a pair $M \parallel F$, where $F$ is a finite set of clauses and
  $M$ is a sequence of annotated literals.... We will not go into a complete formalization
  of annotated literals; it suffices to know that some literals $l$ will be annotated
  as being decision literals; this fact will be denoted here by writing $l^d$
  (roughly, decision literals are the ones that have been added to $M$ by the Decide rule given
  below). Most of the time the sequence $M$ will be simply seen as a set of literals,
  denoting an assignment, i.e., ignoring both the annotations and the fact that $M$
  is a sequence and not a set.

I understand that a literal is an atom or its negation, but I don't understand what an annotated literal is, which is a core part of understanding what a model $M$ is in $M \parallel F$. I also don't understand what the decision literals are.

Two examples are as follows.

This is as much as I can gather. This:

$$\emptyset \parallel 1 \lor \bar{3}, \bar{1} \lor \bar{4} \lor 5 \lor 2, \bar{1} \lor \bar{2}$$

Is essentially an implementation of this:

$$M \parallel F$$

Also, the commas are really $\land$, as in:

$$\emptyset \parallel (1 \lor \bar{3}) \land (\bar{1} \lor \bar{4} \lor 5 \lor 2) \land (\bar{1} \lor \bar{2})$$

So each of the blocks between the commas or $\land$ are clauses. On the left is a growing list of literals (atoms or their negation). On the right are the rules being applied (like Decide). But I don't understand (a) how the rules are being applied / why they are chosen at the time they are chosen, (b) how it results in an annotated literal for $M$ on the left, and (c) why some of them are marked in bold as the "decision" literals.

The final result, from my understanding, is the model $M$ (on the left) that satisfies the formula $F$ on the right. Essentially, it's a valuation.

Wondering if one could clarify how the first example works, how the annotated literals get added to the model $M$ on the left.

Describing DPLL as a series of state-transition rules is the worst way I've ever seen to aid understanding the algorithm.  The pseudocode provided in the WIkipedia article on DPLL is much easier to understand if you're approaching the algorithm for the first time.

;Algorithm DPLL
;Input: A set of clauses Φ.
;Output: A Truth Value.

function DPLL(Φ)

if Φ is a consistent set of literals
   then return true;
if Φ contains an empty clause
   then return false;
for every unit clause {l} in Φ
   Φ ← unit-propagate(l, Φ);
for every literal l that occurs pure in Φ
   Φ ← pure-literal-assign(l, Φ);
l ← choose-literal(Φ);
return DPLL(Φ ∧ {l}) or DPLL(Φ ∧ {not(l)});

Decision literals are the literals returned by the choose-literal function called above.  Annotated literals are just literals that are members of M that are marked in some way so the DPLL implementation can distinguish decision literals from literals added to M by unit propagation.  This marking is for the sake of the backjumping code which must unroll assignments until the one responsible for the current conflict is found and then replace it.

Note that the original DPLL algorithm did not have backjumping in it.  It simply backtracked, either reversing the current assignment or returning false if the algorithm had run out of assignments to try.  Backjumping was a later innovation.

Note also that pure literal assignment isn't usually done in modern SAT solvers that implement some form of DPLL.  It is a fairly expensive check to do in an algorithm expected to recurse and backtrack an exponential number of times and the benefits of doing the check don't outweigh the costs.


Are there some real-world optimization problems with very cheap objective functions? Many real world optimization tasks (especially black box optimization) have objective functions, which are quite expensive to evaluate. For example to find the optimal shape of an airplane wing, a computer model of the wing needs to be constructed and then a large physical simulation needs to be executed, usually taking many hours.

Are there some real-world optimization tasks that have optimization functions which are extremely cheap (on the order of milliseconds) to evaluate? The only thing that comes to my mind are some classical functions, such as the travelling salesman problem with up to a few hundred nodes. The evaluation of a solution consists just of adding a few hundred numbers, which is easily accomplished on the desired time scale. Unfortunately, I am not convinced that the TSP is a real-world problem, since it is so simple.

If you don't consider the Traveling Salesman Problem to be "real-world" enough, maybe take a look at its close cousin the Vehicle Routing Problem (VRP). In particular, consider all the variations of VRP, many of which clearly have their origins in real-world situations (e.g.: time windows, backhauls, etc...). This survey (pdf) by Eksioglu et al. details many of these variations. And, as far as I can tell, VRP objective functions are not much more difficult to evaluate than those of TSPs.


What information needs to be saved in a Lamport clock system to deduce message causality? By using Lamport timestamps, we can determine the causality of messages. It is however unclear to me how one would deduce this simply from the lamport timestamp of the message.

Take the following model situation: there is a casuality break when it comes to process 2:

Now, we add Lamport clocks (hopefully I have done that correctly)

I'm at loss when it comes to understanding how I can read out the correct casuality of received messages by process 2 from just the timestamps. Unless I haven't determined the timestamps properly.

It looks like there's some additional information needed to do that. Maybe to save the timestamp of the message itself, and the id of the sending process?

Lamport clocks are not designed to allow you to infer all causality.  No one ever claimed that knowing the Lamport timestamp is enough to read out the causality of all messages.

Rather, Lamport clocks provide a partial ordering that is consistent with causality: if event $a$ happens before event $b$ (causally), then $a$'s timestamp will be smaller than event $b$.  The converse does not necessarily hold.

See https://en.wikipedia.org/wiki/Lamport_timestamps and https://en.wikipedia.org/wiki/Lamport_timestamps#Implications.

If you want to read out the full causality, use vector clocks or other methods that are designed for that.


Turing machine that can remember Special Turing Machine is defined just like standard Turing Machine, only that each step is made according to the content of the tape starting from the left edge to the head position in tape.
(The transition function in this case belongs to Q X Γ* -> Q X Γ X {L,R})

Which of the following is true:

A. Every language L has a Turing machine that decides L if and only if there is a special Turing machine that decides L.

B. Every language L has a Turing machine that decides L in a polynomial time if and only if there is an special Turing machine that decides L in a polynomial (input length polynomial).

C. A,B answers are correct.

D. A,B answers are incorrect.

and my question is:
the correct answer is D and I can't understand why.

The answer is:
Each language can be decided by a special Turing machine in linear input length time (O(n) when n is the input length). A transition function goes to the right as long as no blank space is seen, and as soon as you see a blank space switches to receiving or rejecting according to the word written on the tape.

My question is:
How can I decide whether to reject or accept a word?
In other computational models, such as PDA, DFA, we defined the transition function similarly, and no power was added to the model.
Why does it seem that power is added to the computational model as a result of the change of the transition function when it comes to Turing machines?

Thanks.

Given any language $L$ there is a special Turing machine $T$ that decides $L$ in polynomial time.

The Turing machine has 3 states: the initial states $q_0$, the accepting state $q_A$ and the rejecting state $q_R$.
Let $\Gamma$ be the tape alphabet (including the blank symbol $\varepsilon$), and let $\alpha x$ denote the contents of the tape starting from the left edge to the head position in tape, where $\alpha \in \Gamma^*$ and $x \in \Gamma$. As usual, I am going to assume that the input is written starting from the beginning of the tape and that the head is initially positioned at the beginning of the tape.
The transition function $\delta$ is defined as follows:

$\delta(q_0, \alpha x) = (q_0, x, R)$ if $x \neq \varepsilon$
$\delta(q_0, \alpha x) = (q_A, x, R)$ if $x = \varepsilon$ and $\alpha \in L$
$\delta(q_0, \alpha x) = (q_A, x, R)$ if $x = \varepsilon$ and $\alpha \not\in L$

Since there are undecidable languages for regular Turing Machines, this immediately implies that A and B are false.

Answers D and C are unclear. They talk about "both answers" but you are given $4$ possible answers.


Hiring problem from CLRS Hiring problem is discussed in section 5.1 and 5.2 of the CLRS and I'm referring this for exercise solutions.

However, for Exercise question 5.2-2 my solution deviates from the one given in the reference and mine seems be correct. I am still not satisfied with the reasoning of my solution though. Here it goes.

The Question: In HIRE-ASSISTANT, assuming that the candidates are presented in a random order,
what is the probability that you hire exactly twice?

My solution: 1. First candidate is always going to be hired so all we have to do is to calculate the probability that only one candidate is hired from the remaining n - 1 candidates. So I divided it into n - 1 cases where like

case 1: If the second candidate is hired. (other than the first one only)

case 2: If the third candidate is hired.

and so on..

Now the probability of case 1:

1(anyone will be hired) * 1/2(the probability of this being more than the first) * 2/3(probability of this not being the highest till now) * 3/4 * 4/5 * 5/6.... * (n-1)/n = 1/n

Similarly for case 2: 1 * 1/2 * 1/3(must be highest till now) *1/4... * (n - 1)/n = 1/2n

case 3: 1/3n
and n-1 th case : 1/(n-1)*n

so my answer is

1/n * (1 + 1/2 + 1/3 + 1/4... 1/(n-1))

but the solutions pdf mentions

(2^n - n - 1)/n!

My solution seems correct for n == 3 where the answer should be 3/6. So can anyone please validate this approach and guide me if this is wrong.

In fact, your result is correct and that reference solution is wrong!

Here is where that reference solution goes wrong.

  Since we view the candidate ranking as reading an random permutation, this is equivalent to the probability that a random permutation is a decreasing sequence followed by an increase, followed by another decreasing sequence.

A permutation that leads to hiring of two candidates if and only if the first candidate is not the best candidate and is better than all others candidates that come before the best candidate. There is no requirement of sequences being decreasing or increasing.

(There is a minor typo in your case 2. You meant 3/4 instead of 1/4.)

I would not say your reasoning is fully correct yet, though you have got the correct result, since I have not found a natural way to explain rigorously your way of computing the probability of each case by a product of probabilities. I am even more far away from being certain that your reasoning is wrong. It looks like you shared my feeling as well.

There are better or more rigorous ways to produce the correct result. I will let you think about it.


Functorial type constructors in System F I have come across the claim that all basic data types in System F, such as Bool, Nat, and List(U), can be expressed in the form $\forall \alpha (((T\alpha \rightarrow \alpha) \rightarrow \alpha)$, where $T(\alpha)$ is a definable functorial type constructor.

Can someone explain why this is true or refer me to a proof? Because I have not found a proof for this claim yet.

The usual (categorical) characterization of inductive data types is as initial $F$-algebras for a functor $F$.  An $F$-algebra is a pair of a type, $A$, and a function $a : FA \to A$.  A homomorphism of $F$-algebras, $\varphi : (A,a) \to (B,b)$ is a function $\varphi : A \to B$ which satisfies $\varphi\circ a = b\circ F\varphi$.  An $F$-algebra, $(\mu F,\mathsf{in}_F)$, is initial if there exists a unique homomorphism from it to any other $F$-algebra.  This means we have a function which takes an $F$-algebra $(A,a)$ and produces a function $\mathsf{fold}_A(a):\mu F\to A$ which satisfies $$\mathsf{fold}_A(a)\circ\mathsf{in}_F=a\circ F(\mathsf{fold}_A(a))$$
The type of $\mathsf{fold}$ in System F would be $\forall \alpha.(F\alpha\to\alpha)\to\mu F\to\alpha$.  The free theorem for this (as calculated by this) specializes to
$$\forall \alpha,\beta. \forall \varphi : \alpha\to \beta.
   \forall a : F \alpha \to \alpha.
   \forall b : F \beta \to \beta.\\
    \varphi \circ a = b \circ F \varphi \implies \varphi \circ \mathsf{fold}_{\alpha}(a) = \mathsf{fold}_\beta(b)$$
which further specializes to
$$\forall \beta.
   \forall b : F \beta \to \beta.
    b\circ \mathsf{fold}_{F\beta}(Fb) = \mathsf{fold}_\beta(b)$$
and
$$\forall \beta. \forall \varphi : \mu F\to \beta.
   \forall b : F \beta \to \beta.\\
    \varphi \circ \mathsf{in}_F = b \circ F \varphi \implies \varphi \circ \mathsf{fold}_{\mu F}(\mathsf{in}_F) = \mathsf{fold}_\beta(b)$$
If we can prove $\mathsf{fold}_{\mu F}(\mathsf{in}_F) = id_{\mu F}$, then this would mean that $(\mu F,\mathsf{in}_F)$ was an initial $F$-algebra as the above equation says: "any $F$-algebra homomorphism $\varphi : (\mu F, \mathsf{in}_F)\to(B,\beta)$ is $\mathsf{fold}_\beta(b)$ and thus exists and is unique". Of course to do this we need to actually give a definition of $\mu F$, $\mathsf{fold}$, and $\mathsf{in}_F$.

By noting that $\forall \alpha.(F\alpha\to\alpha)\to\mu F\to\alpha$ is isomorphic to $\mu F \to \forall \alpha.(F\alpha\to\alpha)\to\alpha$, there's an obvious choice for both $\mathsf{fold}$ and $\mu F$: simply set $\mu F = \forall \alpha.(F\alpha\to\alpha)\to\alpha$ and $\mathsf{fold}$ to be the inverse image of $id$ with respect to that isomorphism.  Explicitly, $$\mathsf{fold} = \Lambda\alpha.\lambda a\!:\!F\alpha\to\alpha.\lambda g\!:\!\mu F.g[\alpha]a$$ All that remains is to define $\mathsf{in}_F$ and show that $\mathsf{fold}_{\mu F}(\mathsf{in}_F) = id_{\mu F}$.  The easiest way to define $\mathsf{in}_F$ is to just follow the types: $\mathsf{in}_F : F\mu F \to \forall \alpha.(F\alpha\to\alpha) \to \alpha$ so $$\mathsf{in}_F = \lambda x\!:\!F\mu F.\Lambda\alpha.\lambda a\!:\!F\alpha\to\alpha.a(F(\mathsf{fold}_{\alpha}(a))x)$$
This definition is particularly convenient as you may have noticed that while I've shown that if there's a homomorphism $\varphi : (\mu F,\mathsf{in}_F)\to(A,a)$ then it is $\mathsf{fold}_A(a)$, and I've shown that there is a function $\mathsf{fold}_A(a):\mu F\to A$, I haven't shown that $\mathsf{fold}_A(a)$ is a homomorphism. That is, I haven't shown $\mathsf{fold}_A(a)\circ\mathsf{in}_F = a\circ F(\mathsf{fold}_A(a))$, but with the above definitions of $\mathsf{fold}$ and $\mathsf{in}_F$ this is easily shown by normalizing. To finish, $$\begin{align}
\mathsf{fold}_{\mu F}(\mathsf{in}_F)
& = \mathsf{in}_F\circ\mathsf{fold}_{F\mu F}(F(\mathsf{in}_F)) \\
& = \lambda g\!:\!\mu F.\Lambda\alpha.\lambda a\!:\!F\alpha\to\alpha.(a\circ F(\mathsf{fold}_{\alpha}(a)) \circ \mathsf{fold}_{F\mu F}(F(\mathsf{in}_F)))g \\
& = \lambda g\!:\!\mu F.\Lambda\alpha.\lambda a\!:\!F\alpha\to\alpha.(\mathsf{fold}_\alpha(a)\circ \mathsf{in}_F \circ \mathsf{fold}_{F\mu F}(F(\mathsf{in}_F)))g \\
& = \lambda g\!:\!\mu F.\Lambda\alpha.\lambda a\!:\!F\alpha\to\alpha.(\mathsf{fold}_\alpha(a)\circ \mathsf{fold}_{\mu F}(\mathsf{in}_F))g \\
& = \lambda g\!:\!\mu F.\Lambda\alpha.\lambda a\!:\!F\alpha\to\alpha.\mathsf{fold}_\alpha(a)g \\
& = \lambda g\!:\!\mu F.\Lambda\alpha.\lambda a\!:\!F\alpha\to\alpha.g[\alpha]a \\
& = \lambda g\!:\!\mu F.g
\end{align}$$


How to measure processing power of a quantum computer? Is there any way to get an equivalent of computing power of quantum computers in terms of computing power of common computers? I mean, how many teraflops (or so) can a quantum computer compute? How can I calculate that equivalence? I think it depends on the architecture, like a x64 in common computer, and a 512-qubit.

this is a very difficult/subtle/controversial question at the heart of current research that even topnotch scientists are having a lot of trouble answering precisely. there are two main lines of QM computer development:

adiabatic QM computing, this is the Dwave computer that is up to 512 qubits, but it doesnt operate using "qbit transport" which is the main line of scientific research
"standard" QM computing transports qbits so their spins can interact as laid out in "quantum circuits". there is a lot of theoretical research on this topic but physics researchers are apparently still far from actually implementing (physically building/realizing) this type of computing.

unfortunately in both cases there are other further issues:

theoretically, can one get a speedup based on the mathematics/physics of quantum computing? see eg proof of speedup with [adiabatic] qm computing tcs.se
in practice, after one builds the computer, and one applies various systems, eg error correction being one of the main ones, and decoherence being one of the main challenges to overcome, how efficient will it be? will there be any speedup over conventional computing?
QM algorithms run completely differently, they are not based on binary logic! so therefore there is not yet any way to determine what the "equivalent" or "corresponding" qm algorithm is to a "classical" algorithm that is under consideration. the best we can do is try to optimize the performance of both & see what happens but that is obviously not satisfactory and somewhat dependent on human factors.

so the best answer right now is "nobody can really say right now". or, the best quantum computer in the world, Dwave, (apparently costing in \$ millions per unit, and over $100M research so far) is now shown in scientific papers to be slower than desktop computers when algorithms are optimized on those computers. or, "its an open question subject to cutting edge international research". there are many posts in Aaronsons blog on the subject. see also

Dwaves dream machine
Will Bourne, Inc magazine 1/9/2014
Dwave & the inception of the QM computing dream collection of lots of refs, papers, se questions etc


How many times do we access memory with a TLB? As I understand it, when we are on a virtual memory based system, we have to access memory 2 times (one for the Page Table and one for the physical address in RAM). But, how many times would we have to access if we had a TLB?

Many systems use more than one level of page tables, so you may need to access memory more than two times.

With a TLB and assuming you have a cache hit, then you will only need to access memory once since TLBs are usually implemented in hardware. Otherwise, you will have to access memory the same amount of times you would if you didn't have a TLB (such as if the TLB is empty).


Monoalphabetic Cipher Key I am not sure how to get the key for the following Monoalphabetic Cipher question. This is a textbook question and I know the answer, but I juts dont know how they got the key.
Question:

Decrypt the following Cipher texts, and give the key.  (Note that the correct key is the Encryption key, so if F changes to H and F is the plaintext, then the key is “C”):
(a) YRRYAIYRMLAC (b) DOBXQPZELLI

Answer: a) Text:ATTACKATONCE Key = X  b) Text: GREATSCHOOL Key = A
Can somone please explain to me how to determine the key?

You try all 26 possibilities, and check which of them results in an English-looking test. In principle you can do the latter statistically, but in this case there are only 26 possibilities, so you might as well just look at all of them manually.


Minimum number of shopping trips for a group of people to buy presents for each other We have a group of $n$ people. We are given a list of who must buy presents for whom within the group. Each person might need to buy/receive any number of presents, or possibly none at all. In a shopping trip, a subset of the people travel together to the same store, and buy presents for anyone who is not present at the store. They may not buy presents for someone else on the same shopping trip because then it wouldn't be a surprise. A person may go on multiple shopping trips. We want to minimize the total number of shopping trips required for everyone to buy all the presents they need.

As an example, consider the case where there are 5 people, and each must buy presents for every other person in the group. Let the people be numbered 1 to 5.  This can be done in 4 shopping trips, as shown:

Trip 1: 1, 2, 3 go shopping
Trip 2: 1, 4, 5 go shopping
Trip 3: 2, 4 go shopping
Trip 4: 3, 5 go shopping

How would I go about solving this problem? It is obvious that the input can be represented by a directed graph, but I don't know where to go from there. Someone brought up the biclique cover problem, but while similar, it does not answer this question.

We can think of the input as a directed graph $G$ on $n$ vertices, where the edge $(u,v)$ means that person $u$ must buy a present for person $v$.   The goal is to find a set of bicliques $(S_1,T_1),\dots,(S_k,T_k)$ such that $k$ is minimal and the edge set $E$ of the graph is a subset of $\cup_i (S_i \times T_i)$.  Also, in extending the definition of bicliques to a directed graph, a biclique $(S_i,T_i)$ only contains edges which map $S_i$ to $T_i$.  This differs from the biclique cover problem in that we don't require each biclique to be a subgraph of $G$ (we don't require $S_i \times T_i \subseteq E$ for each $i$).

Specifically, I will accept an answer that either:

Demonstrates that this problem is NP-hard or
Presents a polynomial time algorithm that answers this question exactly (no approximants or upper bounds)

For the record, I did not see this problem anywhere, I am just wondering about it for my own curiousity.

I can see how to reduce this problem to Graph Colouring, which gives you a tool for solving the problem (for small instances!), but not yet how to reduce in the other direction (which would establish NP-hardness).

The basic idea is to build a graph that contains a vertex for every purchase, and an edge between any two purchases that cannot occur on the same trip; we then look to group the purchases into the smallest possible number of groups ("trips"), such that no two purchases in the same group would conflict.  Specifically, if $G = (V, E)$ is the original directed graph in which an edge $uv$ indicates that person $u$ needs to buy person $v$ a gift, then create an undirected graph $H = (X, Y)$ in which there is a vertex $x_{uv}$ for each edge $uv$ in $G$ and an (undirected) edge $x_{uv}x_{vw}$ whenever $uv$ and $vw$ are both (directed) edges in $G$ (if $v$ buys some $w$ a gift during a trip, then no one can buy $v$ a gift during that same trip).  A vertex colouring of $H$ is a partition of the necessary purchases (vertices in $H$) into trips (colours) that don't conflict (share an edge), and a vertex colouring of minimum size takes the fewest possible trips.

It might be possible to go in the other direction (reduce Graph Colouring, or some other NP-hard problem, to your problem, and thereby establish its NP-hardness), by adapting a reduction from 3SAT to Graph Colouring (as, e.g., detailed on p. 10 of Jeff Erickson's notes), but I haven't attempted this myself.


How can I calculate the new quotient if I came to know divisor is increased by one? If I have two number consider a and b and let their division quotient is c.
I know the value of c but I don't know either value of divided(a) or divisor(b). If I came to know the value of divisor is increased by one, can I somehow calculate the new value of quotient(c)

I guess, maybe using some bit manipulation rules or tricks, I could  get the new value of quotient c

Example:
A / B = 50
IF B is increased by 1, can I somehow calculate the new value in quotient?

Knowing the ratio r = A / B and nothing else about the numbers A and B, there is very little we can say about for example A / (B + 1) or A / (B - 1). We have A = rB. If for example B = 1, then A = r, and A / (B + 1) = r / 2, half the value of A / B. On the other hand, if B = 1,000,000 and A = r*1,000,000 then A / (B + 1) = r * 1,000,000 / 1,000,001 = r - r / 1,000,001, barely different from r.

In the example A / B = 50 and r = 50, when B is replaced with B + 1, the ratio r changes from 50 to 25 if B = 1, but only from 50 to about 49.999,950 if B = 1,000,000.


Explanation of pseudocode and time complexity analysis I am trying to work my way through some computer science training and I am not able to properly understand the following pseudo code:
COUNTING-1 (n)             cost          times

1  for r=1 to n            c1               n+1

2    for c=1 to n          c2               n(n+1)

3      sum = sum+1         c3               n2

4  return sum              c4               1

T(n)=c2*n(n+1)+c3*n2 +c1*(n+1)+c4=an2+bn+c

Could someone explain why the outer loop is n+1, and not just n?
Also what are the constants c, a and b? I don't understand why they need to factor into the explanation equation as it isnt clear what their value will.
Apologies if these are really simple questions. If there are some useful things I should read I would appreciate a pointer in the right direction.
*Edit: I think looking at it again the c constant is the cost of the operation which for each is constant time, so 1. Is the cost of a single operation ALWAYS 1? If it is (which it appears to be in this RAM model) what is the point in over complicating the formula underneath with those values?
Why not just T(n)=n(n+1) + n2 + (n+1)

First question: some book, for example well known CLRS 3ed. p25-26, counts, that in for loop test in loop header is executed one times more, then loop body. Accordingly you see $n^2=n(n+1)-n$ in 3-d line.
Second question: simplify $T(n)$ and write it as polynomial from $n$. Then you obtain representations for $a,b,c$: $$T(n)=c_2n(n+1)+c_3n^2 +c_1(n+1)+c_4=\\=(c_2+c_3)n^2+(c_2+c_1)n+(c_1+c_4)=\\=an^2+bn+c$$
So $a=(c_2+c_3)$, $b=c_2+c_1$ and $c=c_1+c_4$. If we speak about asymptotic estimation, then $T(n)=O(n^2)$.


Help with a difficult expected runtime recurrence I developed an algorithm and have a recurrence for its runtime; I want to show the expected runtime is $O(\sqrt{n})$.
At each iteration $i$, I have a random variable $k_i$ that is equal to the number of heads after flipping $\frac{n}{2^i}$ coins minus $\frac{n}{2^{i+1}}$ (i.e. a binomial distribution centered at 0 with width $\frac{n}{2^i}$). The runtime of my algorithm is then given by the following recurrence:
$$B(0) = 0$$
$$B(i) = \max\{B(i-1)+k_i, 0\}$$
When $B(i)$ is large, the negative and positive $k_i$ can cancel each other out, so intuitively one should be able to come up with a pretty good bound on $\mathbb{E}[B(n)]$, but I have no idea where to start.

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.)


Suggest a data-structure that supports the following operations with time complexity of $ O(log(n)) $ Iv'e been struggling a lot with this one.
I am looking for a data-structure (could be a modification of an existing type of data-structure, or a combination of more than one data-structure), which supports the following methods, all with time complexity (at worst-case) of $O(log(n))$:

Insert(v) - insert v to the structure
search(v) - search for v
delete(v) - delete node with value v
updateKeys(x,v) - for each node with a value greater then x, add v to it's value, where v is a positive number.

For example, if I had the following set of elements: ${1,2,5,8,10,15,20}$
, using updateKeys the following way: $ updateKeys(10,5) $ would change the set to : $ {1,2,5,8,15,20,25} $.

Well, I had a lot in my mind.
Basically, my assignment is on the following data-structures:

Hash tables - which sounded good at first, but I couldn't think of a way to find all elements larger than or equal to x.
AVL tree - it does support the basic methods with this complexity, but in order to find which elements are larger, I need to search through all tree which can cost more than $ log(n) $. Further more, I can mess the tree up if I for instance make a left son be larger than it's parent.
A combination of the two above - looked promising at first, but again, I couldn't find a way to find those elements.
Heap - for some reason it sounds like a good direction since I have some sort of order, but update the values with log(n) time? seems impossible.
Skip list - here I thought about using skip list since the most bottom layer is sorted in increasing order, so I thought about finding the minimum value larger than x, and then update all of it's followers from the right. Sounds good, but it is definitely not within $ O(log(n)) $, since for the following set ${1,2,3,4...10}$, and for $ x=1 $, I need to iterate 10 numbers, which is $ O(n) $

We also studied B-trees, ADT structures...

Then, almost hopeless, I started reading about data structures that weren't even taught in our course, such as range trees, BIT trees and so on.For some reason, some of them seemed suitable for this purpose, but since it's not in our syllabus, I don't think we are even allowed to use them.

Thanks in advance.

AVL tree - it does support the basic methods with this complexity, but in order to find which elements are larger, I need to search through all tree which can cost more than log(n).

Not quite. In order to change all those entries, yes; but by searching for $x$ you can identify all nodes that have greater values: all nodes you visit and have key $> x$, namely those where you go left, and their right subtrees.

  Further more, I can mess the tree up if I for instance make a left son be larger than it's parent.

No, and that may be the key insight. If we increase all keys $>x$ by some constant we maintain the search-tree property! In particular, you never increase a left son and not its parent!

These two observations lead us to the idea: use AVL-trees (or any balanced search tree, I daresay) and execute key increments lazily. For that, add to every node an integer inc that is initially $0$.

Now, a call updateKeys(x,v) proceeds as follows.

Search for x using usual BST search.
Whenever you go left at some node y,

increase y.key by v and
increase y.right.inc by v.

This adds at most constant overhead per visited node, so it has the same $\Theta$-running-time as search.

We execute the updates whenever we traverse the tree anyway. That is, augment all four operations so that when they access some y.key they execute this first (if y.inc > 0):

y.left.inc  += y.inc
y.right.inc += y.inc
y.key       += y.inc
y.inc        = 0

This adds at most a constant amount of effort per visited node for all the operations, so it does not change their $\Theta$-bounds on time. We do need a linear amount of extra memory, but that seems to be allowed.

Detailed pseudocode and proofs of correctness are good exercises.


How much time (in hours) will it take to check if the number with 20 binary digits is the prime number? How much time (in hours) will it take to check if the number with 20 binary digits is the prime number, in problem it's mentioned that for number with 10 digits it took 1 hour it's also said that the number has been checked using AKS pirmality test and it's also given that log(n) is the lenght of the number to be verified.

Primality testing is very fast with the Miller–Rabin algorithm [1]. You can use the deterministic variant with witnesses 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, and 37 to test any 64 bit number in $O(\log^3 n)$ time. This should take less than one second with any reasonable implementation.

[1] https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test


Comparison of constructive and local-search heuristics for TSP In my high school class, we are currently looking at evaluating heuristic methods for intractable problems - especially TSP.

My question is what is the advantages or disadvantages of using a constructive heuristic (like Nearest-Neighbour) compared to local search (something like 2-opt from some research?)

Thank you

So first of all lets consider the techniques. Nearest neighbour is a heuristic that directs the search. That means that it informs how the search should proceed. It can be seen as preemptive.

The 2-opt is not a search heuristic but is a technique used to attempt to improve a solution(partial solution). You can think of it as massaging the solution into a more desirable solution.

As for advantages/disadvantages... well the nearest neighbour heuristic directs the search, but it may make silly mistakes. This in effect allows the search tree to be led "Down a rabbit hole".

The 2-opt solution is computationally more complex. It requires you to consider all quadruples (all pairs of edges if your data structure allows it) and then decide if the cross has occurred. In situations that you are looking for good enough and need an answer quickly, this type of search may be too computationally intensive. Although to the best of my knowledge, in any situation where 2-opt is a reasonable idea, the fitness of your solution should only improve/stay the same... Although I would not be surprised if I were wrong about that.


Given snapshot and boolean circuit how to compute coNP formula? Theorem 6.20: If $\mathsf{EXP\text{}} \subseteq \mathsf{P_{poly}\text{}}$ then $\mathsf{EXP\text{}} = \Sigma_2 ^{p}$.

My attempt  : Let $L \in \mathsf{EXP\text{}}$. Then $L$ is computable by an $2^{p(n)}$-time Turing machine $M$, where $p$ is some polynomial. Let $x \in \{0,1\}^n $ be some input string. For every $i \in [2^{p(n)}] $, we denote by $z_i$ the encoding of the $i$th snapshot (the machine's state and symbols read by all heads) of $M'$s execution on input $x$. If $M$ has $k$ tapes, then $x\in L \iff $ for every $k+1$ indices $i,i_1,i_2,\cdots,i_k$, the snapshots $z_i,z_{i_{1}},\cdots,z_{i_{k}}$ satisfy some checkable criteria.

As $\mathsf{EXP\text{}} \subseteq \mathsf{P_{poly}\text{}}$, then there is a $q(n)$-sized circuit $C$ (for some polynomial $q$) that computes $z_i$ from $i$. Now the main point is that the correctness of the transcript implicitly computed by the circuit can be expressed as a $\mathsf{coNP\text{}}$ predicate (namely, one that checks that the transcript satisfies all local criteria).
Hence, $x\in L$ iff the following condition is true

$$ \exists C \in \{0,1\}^{q(n)}  \forall i,i_1,i_2,\cdots,i_k \in \{0,1\}^{p(n)} T(x,C(i),C(i_1),\cdots,C(i_k)) = 1$$

  Question : I am not able to understand, how transcript implicitly computed by the circuit can be expressed as a $\mathsf{coNP\text{}}$ predicate ?

Reference : http://theory.cs.princeton.edu/complexity/circuitschap.pdf

You want to know how, given a circuit $C$, one can express the statement "given $i$, $C$ correctly computes $z_i$, the i'th snapshot in the computation of $M$ on some fixed input $x$", by a coNP predicate. Note that if this can be done, say using the predicate $\varphi (C,x)$, then
$$\psi(x)=\exists C: \varphi(C,x)\land C\left(2^{|x|^c}\right) \text{ is accepting}$$

is exactly the $\Sigma_2$ formula you're looking for. To see why, note that $x\in L$ iff the last snapshot is accepting, or equivalently if $C\left(2^{|x|^c}\right)$ is accepting, and $C(i)$ correctly computes $z_i$. So if $\varphi(C,x)$ indeed expresses "C correctly computes $M$'s snapshots on input $x$", then $x\in L \iff \psi(x)$. If you have a guarantee that polynomial circuits for $L$ exist, then you can bound the existential quantifier, and only look for poly-size circuits.

So how do we write $\varphi(C,x)$ as a coNP predicate? Using locality, you know that the $i'th$ snapshot depends on some $k$ previous ones (where $k$ is a constant depending on the number of tapes). $C$ correctly computes the snapshots if for all $i,i_1,...,i_k$ (this gives you the universal quantifier) it holds that
$T\left(x, C(i), C(i_1),...,C(i_k)\right)$, where $T$ depends on $M$'s transition function. Intuitively, $T$ checks whether $i_1,...,i_k$ are the previous indicies of snapshots who determine $z_i$, and if so verifies that the transition was indeed according to $M$'s rules.


How is CPU different from GPU? A central processing unit offers to handle various operations like calculating, watching movies, making presentation etc. While a graphics processing unit is majorly used for the purpose of video rendering or playing of high-quality graphical games.
I found the above statement on a website listing the differences between CPU and GPU.
What I am not able to understand is how making PPTs,listening to songs from graphics in terms of mathematical operations that the brain of computer applies!
All these operations handled in terms of bits,so why treat them differently?
Also why cant we have a PC completely based on GPUs if they so good at executing parallel instructions and handling large amount of bits for graphics?Though i have heard about GPGPUs but why cant traditional GPUs be used?

GPUs are highly specialized: they are very good at a very small number of things, but they are extremely bad at everything else.
CPUs are general: they are mediocre at everything.
GPUs are good at applying the same operation out of a small number of potential operations, and in particular, the same very simple operation to a lot of identical things. E.g. when you want to brighten up a picture, you need to apply the same extremely simple multiplication to all 3 colors of all 10million pixels of a 4K screen.
A CPU is almost exactly the opposite: the number of potential different operations is not small, it is almost endless. (Word processing, spreadsheet crunching, compiling, web browsing, emailing, controlling a robot, driving a car, …) The operations aren't simple, they are extremely complex. And you don't apply the same operation to a huge number of identical things, you apply a different operation to a number of different things.
GPGPU (General-purpose GPU) is a misnomer, really. They are not "general purpose" in the same sense that a general purpose CPU is. What is meant by that, really, is that they can be used for purposes other than creating pictures that still have the same characteristics as graphics. For example, modern graphics cards can do particle simulations for generating realistic rain or explosions. What "GPGPU" means is that you can use those same particle simulation features without generating a picture from it, and instead, say, generate velocity predictions for the fragments of an exploding asteroid.
But, reading your mail is a very different thing than simulating a billion particles.


Cover k edges to minimize the length of the longest uncovered path in a tree You are given a tree $G\langle V, E\rangle$ and an integer $k$. The goal is to cover $k$ edges of the graph, to minimize the length of the longest uncovered path in the tree (and to return this path's length)
Constrains: $O(n\log n)$ time and $O(n)$ space.

Now, the scheme of the algorithm is kinda obvious (from the given constrains). We need to priorities the edges and pick the highest $k$-edges (technically, we throw all edges to a priority queue and pick the first $k$)
So, I think, the keys should tell us how centric the edge is.
My first attempt was BFSing the graph from some node and BFSing again from the most distant node of the first scan.
Each node will get two values: distance from the first starting node and distance from the second starting node.
Though, I'm not sure how well this method grasp the notion of centric.
I'd be glad to hear your thoughts about the current idea or your own ideas.

(This answer expands on Albert Hendriks' approach from the comments.)

First idea: let us turn the problem around.
As stated, we fix the number of covered edges, $k$, and minimize the maximum length of an uncovered path $d(k)$.
Instead, let us fix the maximum length of an uncovered path, $d$, and minimize the number of covered edges $k(d)$.

Suppose now we can calculate $k(d)$ in $O(n)$.
Then the original problem can be solved in $O(n \log n)$.
Indeed, note that both $d(k)$ and $k(d)$ are non-increasing functions.
To answer the question "what is $d(k_0)$?", we can find the minimum $d_0$ such that $k(d_0) \le k_0$.
And that can be done in $log (n)$ calculations of $k(d)$ by doing a binary search for the right $d$ with the obvious bounds of $[0, n-1]$.

What's left is to, given a fixed value $d$, calculate $k(d)$ in $O(n)$.

Second idea: we can select an arbitrary vertex as the root, run a depth-first search from the root, and make decisions about covering edges in depth-first search order.

Let us visit a vertex $v$ in our depth-first search.
We recursively visit all its children in any order.
After visiting child $u$, we assume that we have dealt with all uncovered paths longer than $d$ in $u$'s subtree.
We also know the length $\mathrm{dfs}(u) \le d$ of the longest uncovered path from $u$ to the vertices of its subtree.
The longest uncovered path from $v$ to the vertices of $u$'s subtree has an extra edge $v - u$, so its length is $r = \mathrm{dfs}(u) + 1$.

(I) Obviously, if $r > d$ (it can only be $d + 1$), we have to cover some edge on the long path we found.
Since the whole subtree of $u$ is already dealt with, it makes sense to cover an edge which is the closest to the complement of the subtree of $u$ in the whole tree, which is the edge $v - u$.

(II) But there's more to consider.
A path can go from the subtree of one of our children, via our vertex $v$, to the subtree of another child.
And if such path has length greater than $d$, we have to cover an edge on it.

To find such paths, for our vertex $v$, we store the maximum length of an uncovered path into a child's subtree we have so far.
Let this stored length be $s$, initially zero.
After each child $u$ we visit, check whether $r + s > d$.
If so, let us cover the edge to the longest of $r$ and $s$, so the new maximum length of an uncovered path becomes $s_{\textit{new}} = \min (s_{\textit{old}}, r)$.
If $r + s \le d$, we don't yet have to cover anything, and the new maximum length is $s_{\textit{new}} = \max (s_{\textit{old}}, r)$.

Note now that, with such implementation, case (I) is covered by case (II).
In particular, if we don't yet store a path in a child's subtree, the stored value just adds a length of $0$.

When we finish visiting all children of $v$, the stored value $s$ is the length of the longest remaining uncovered path from $v$ to the vertices of its subtree.
In particular, if $v$ is a leaf, the value $s$ remained zero.
We can now return this value as $\mathrm{dfs}(v)$.

The remaining question is, if we don't cover an edge using the algorithm above, could it have helped us later if we had in fact covered it?
The answer is no: such a cover could safely be moved at least one step closer to the root of the tree, without altering other covers.

In pseudocode, with a bit more low-level details than the explanation above.
Assume the vertices are numbered 0, 1, ..., n-1.
We select vertex 0 as the root (recall that the root can be arbitrary), and just call dfs (0, -1).

dfs (v, p):                            // v is current vertex, p is its parent
    {s, w} := {0, -1}                  // maximum path of length s into child w's subtree
    for u in adjacent[v]:              // all neighbors of v...
        if u != p:                     // ...except its parent, if it has one
            r := dfs (u, v) + 1
            if r + s > d:              // we have to cover the longest...
                if r > s:
                    cover (v, u)
                else:
                    cover (v, w)
                    {s, w} := {r, u}   // ...and possibly update to shortest
            else:
                if r > s:
                    {s, w} := {r, u}   // here, update to longest
    return s                           // length of the longest remaining path

As we can see, dfs (v, p) returns the length of the longest uncovered path from $v$ to the vertices of its subtree.

So, we set the value d (to the pseudocode, it acts as a global variable), run dfs, and track the number of covered edges as the total number of calls to the cover function.
The cover function may actually record the covered edges if need be, but at the very least, it increases the counter k by 1.
If the edges themselves are not needed, we can drop the variable w too, and leave only s from the tuple {s, w}.

For the original problem, do the above in a binary search over the possible values of d to get the full solution.


Heuristics for space-efficient storing of Unordered Finite Sets in a DFA I've got an algorithm I'm working on that generates, stores, and iterates through a large number of finite sets. I'm finding that memory is a bottleneck long before time is.

The finite sets are subsets of the vertices $V$ in my graph, so each finite set is small, there's just a lot of them.

In an effort to save space, I've started representing the finite sets as binary words of length $|V|$, with a 0 indicating the element is not in the set, a 1 indicating that it is. I'm storing the collection of these words as an acyclic deterministic automaton (also known as DAWG, directed acyclic word graph).

However, this requires a fixed ordering of the potential elements, which is fine, but arbitrary. If a different ordering were more likely to produce a smaller output set, I'd be happy to use it.

I'm wondering:

Is there a known, efficient algorithm for finding the permutation which gives the smallest DFA representing a set of finite sets?
If not, has any research been done on heuristics for orderings which have been shown to often produce smaller DFAs?

It sounds like you are describing a binary decision diagram, also known as a BDD.  BDD's have been studied extensively in the literature, so you might take a look at the literature.

In particular, the question of finding the best permutation is known  as the "variable ordering" problem for BDDs.  Finding the optimal variable ordering is NP-hard.  There are some heuristics, but they don't always work.  See https://en.wikipedia.org/wiki/Binary_decision_diagram#Variable_ordering.  Probably the easiest approach is to use an existing BDD library (the standard ones will typically incorporate some variable ordering heuristics).

You might also be interested in ZDDs.


How to prove the correctness of the MinDistance algorithm? My question is about how to prove the correctness of this algorithm, I know it is not a good algorithm, it is not efficient and can be improved. How could I prove it still returns the desired value? What are the loop invariant and variant? How to insert assertions between lines?

The algorithm goes like following,

Algorithm MinDistance (A [0…n-1])

//Input: Array A [0...n-1] of numbers

//Output: Minimum distance between two of its elements

dmin←∞

for i←0 to n-1 do

    for j←0 to n-1 do

        if i≠j and |A[i]-A[j]|<dmin

        dmin←|A[i]-A[j]|

return dmin

Define an order of pairs of indices $(i,j)$ according to the order in which they are accessed in your code. At the end of the $(i,j)$th iteration, $dmin$ holds the minimum of $|A(k)-A(\ell)|$ among all pairs $(k,\ell) \preceq (i,j)$ such that $k \neq \ell$. This loop invariant is easy to prove, and implies the correctness of the entire algorithm.


Is there a problem which can be solved in $O(f_k(n))$ time for any $k$ where $\lim_{k \to \infty} f_k(n) = 0$ but no constant time solution is known? So Fibonacci heaps can perform insertions in amortized constant time, and I came up with a sequence of heap data structures $H_k$ such that insertions can be performed in amortized $O((\log n)^{1/k})$ time where $n$ is the size of the heap. If we didn't know insertions could be performed in constant time, then my result would suggest it, since we can get arbitrarily close to constant running time asymptotics with my solution.

This led to me to wonder, is there an example of a family of algorithms or data structure operations, that are all functionally equivalent, and can be performed in $O(f_k(n))$ time, where $f_k$ is a sequence of functions such that $\lim_{k \to \infty} f_k(n) = 0$ for all $n$, but no constant time alogorithm/data structure operation can be found? Or at least where no constant time solution is currently known? I suspect the answer is yes but probably hard to prove. It would be very surprising if the existence of such family of algorithms with $O(f_k(n))$ running time would imply a constant time algorithm exists.

You can sort numbers in $O(\frac{n\log n}{k})$ for all fixed $k$, and $\lim_{k\to\infty} \frac{n\log n}{k} = 0$ for all fixed $n$.


How balanced is a binary tree in the average case? For algorithms involving binary trees, time or space complexity is often O(logn) in the best case of a completely balanced tree, and O(n) in the worst case of a completely unbalanced tree. Sure, it's a generalization, but it's also a reasonable one.
But in real algorithms, we're typically not interested in the rare worst case performance, much less the best case performance. Rather, we're interested in how the algorithm performs in typical use. This begs an interesting (and useful) question: How balanced is a binary tree on average? Is there a reasonable way to approach that problem, or is it so dependent on use case that there's no better answer than "take a look at the binary trees you're using in your algorithm"?

Is there a reasonable way to approach that problem, or is it so dependent on use case that there's no better answer than "take a look at the binary trees you're using in your algorithm"?

To be a bit stereotypical: yes. There are reasonable ways to approach the problem, but it's so dependent on use case that you will need to take a look at how your particular algorithm builds binary trees to get information about your algorithm.
More specifically: you ask about the 'average' balance of a binary tree, but you can't have an average without a probability distribution on the set of binary trees. There are (infinitely) many different probability distributions, and different algorithms for generating trees will lead to different distributions on the set of trees generated.
For example, since the number of binary trees on $n$ nodes is finite, we can talk about the uniform distribution where we consider every binary tree equally probable, and ask what the average balance is there. For concreteness, I'm going to use height as a measure of the balance of a tree, because it's easy and well-studied, but note that there are plenty of other metrics you could measure by: maximal ratio between subtree sizes, for instance, would be another reasonable one. Looked at over the uniform distribution of $n$-node binary trees, the average height is proportional to $\sqrt{n}$, (almost) 'right between' the two extremes.
But very few algorithms would lead to a uniform distribution on binary trees. As an example of a more reasonable distribution, we could choose a permutation uniformly at random from the $n!$ permutations on $\{1\ldots n\}$ and then build a binary tree by inserting nodes labeled $1$ through $n$ into a tree in the given order. It can be shown that this process yields a tree with average height proportional to $\log n$, so trees generated in natural fashion from random data are generally 'pretty good'.