Simple algorithm for IEEE-754 division on 8-bit CPU? IEEE Std 754-2008 is the modern definition of Floating-Point Arithmetic. It requires that division (among other operations) performs

  as if it first produced an intermediate result correct to infinite precision (..), and then rounded that intermediate result, if necessary, to fit in the destination’s format.

I ask for a simple algorithm performing that operation, tailored to 8-bit CPUs with 8x8->16 bit multiplier; speed is a second(ary) criteria.

For simplicity I restrict to binary32 type

Image credit: wikipedia

and positive "normal" input with exponents such that no overflow or underflow occurs (so that we can ignore any sign or exponent consideration beyond some limited final exponent adjustment according to the result of the division), and rounding to nearest even:

  the floating-point number nearest to the infinitely precise result shall be delivered; if the two nearest floating-point numbers bracketing an unrepresentable infinitely precise result are equally near, the one with an even least significant digit shall be delivered.

I ask because I strongly suspect that the AVR libc implementation of float division (typically used on the Arduino Uno) deviates from the standard beyond being locked to roundTiesToEven, and I wonder how hard it would be to fix that. The current code seems to be divsf3, which invokes divsf3x to perform the division to apparently 40-bit mantissa, then rounding with fp_round. Isn't that very sketch doomed, BTW?

When using properly-rounded higher-precision floating-point arithmetic to compute operations in lower-precision arithmetic, there is the potential issue of double rounding: The result is first rounded to the higher precision, then rounded again during conversion to the lower precision. This can lead to incorrect results, but that is not always the case.

Samuel Figueroa, "When is double rounding innocuous?", ACM SIGNUM Newsletter, Vol. 30, No. 3, July 1995, pp. 21-26

shows that in the case of floating-point division, the higher-precision format needs to have twice the precision of the lower-precision format to avoid issues due to double rounding. This conditions is satisfied were we to use IEEE-754 binary64 to perform the division, then round the result to IEEE-754 binary32. On the other hand, if the higher precision uses 40 mantissa bits, its precision is less than twice that of binary32, so some incorrect results due to double rounding would be expected.

However, from the description in the question it doesn't sound like this is the case. Rather, it seems that there is an internal computation that computes many more quotient bits than are strictly necessary, and this un-rounded result is rounded once to get the binary32 result. After normalization of dividend and divisor a correctly rounded binary32 division requires a total of 25 quotient bits (24 bits for the significand including the integer bit that is implicit in the stored format, plus a round bit), plus a sticky bit that is the OR of all other potential quotient bits.

Note that we don't have to compute the potentially infinite number of quotient bits in order to determine the value of the sticky bit. It suffices to know whether the remainder after computation of 25 quotient bits is zero or not. A zero remainder means the sticky bit is zero, a non-zero remainder means the sticky bit is one. The rounding in nearest-or-even mode requires three pieces of information: the least significant bit of the significand, the round bit, and the sticky bit. The significand needs to be increased when either (1) the round bit is set and the sticky bit is set or (2; tie case) the round bit is set, the sticky bit is clear, but the LSB of the significand is set (meaning it is odd).

Conceptually, for division in a semi-logarithmic floating-point format one needs to subtract the exponents and divide the significand. The conceptually simplest way to perform the latter operation is to perform binary long-hand division. In each step, one compares the current remainder with the divisor. If it is greater than or equal to the divisor, the next quotient bits is one and one can subtract the divisor from the remainder. Then double the remainder for the next step.

Using a small 8x8->16 bit multiply would conceptually be much more involved. One would either build a narrow division operation from this building block and perform a high-radix long-hand division (e.g. base 256), or build a much wider multiplication operation with is then used to compute the quotient with a Newton-Raphson iteration for the reciprocal, using fixed-point computation. In the latter case, the rounding is more involved as an accurate remainder does not fall naturally out of the computation. In addition, a table of starting approximations, say 8 bits, for the reciprocal is typically needed. The following research report discusses relevant trade-offs in the context of the 8-bit Kestrel processor:

Eric Rice and Richard Hughey, "Multiprecision division on small-word parallel processors: Expanded Version". University of California Santa Cruz, April 1998 (online)

I incorporated the above algorithmic sketch into the (tested) ISO-C code below. This code is written for clarity and does not incorporate various obvious optimizations, however I have tried to minimize the size of variables under the assumption that the asker's platform has support for 8-bit operations and limited support for 16-bit operations, similar to a Z80.

#include <stdint.h>

#define SIGN_MASK     (0x80000000)  /* sign bit of IEEE-754 binary32 format */
#define EXPO_MASK     (0x7f800000)  /* exponent bits of IEEE-754 binary32 */
#define MANT_MASK     (0x007fffff)  /* significand bits of IEEE-754 binary32 */
#define MANT_INTBIT   (0x00800000)  /* where integer bit would be if stored */
#define QNAN_BIT      (0x00400000)  /* distinguishes QNaN from SNaN */
#define INFTY         (0x7f800000)  /* infinity */
#define INDEFINITE    (0xffc00000)  /* special QNaN */
#define MAX_NORM_EXPO (254)         /* maximum biased exponent for normals */
#define MIN_NORM_EXPO (1)           /* minimum biased exponent for normals */
#define EXPO_BIAS     (127)         /* exponent bias IEEE-754 binary32 */
#define MANT_BITS     (24)          /* effective # of mantissa bits binary32 */
#define QUOT_BITS     (MANT_BITS+1) /* one extra bit for rounding */
#define EXPO_SHFT     (MANT_BITS-1) /* integer bit is implicit */
#define ROUND_BIT     (1)           /* mask for round bit in 25-bit quotient */
#define MANT_LSB      (2)           /* mask for significand lsb in quotient */

uint32_t fp32_div_kernel (uint32_t a, uint32_t b)
{
    uint32_t r, x, y, sign;
    uint16_t expo_x, expo_y, expo_res;
    uint8_t i, odd, rnd, sticky;

    /* extract biased exponents and sign bits */
    expo_x = (a & EXPO_MASK) >> EXPO_SHFT;
    expo_y = (b & EXPO_MASK) >> EXPO_SHFT;
    sign = (a ^ b) & SIGN_MASK;

    if ((expo_x >= MIN_NORM_EXPO) && (expo_x <= MAX_NORM_EXPO) &&
        (expo_y >= MIN_NORM_EXPO) && (expo_y <= MIN_NORM_EXPO)) { /* fast path */
divide:
        /* extract significands */
        x = (a & MANT_MASK) | MANT_INTBIT;
        y = (b & MANT_MASK) | MANT_INTBIT;
        /* compute exponent of result */
        expo_res = expo_x - expo_y + EXPO_BIAS;
        /* dividend may not be smaller than divisor: normalize */
        if (x < y) {
            x = x << 1;
            expo_res--;
        }
        /* generate quotient one bit at at time */
        r = 0;
        for (i = 0; i < QUOT_BITS; i++) {
            r = r << 1;
            if (x >= y) {
                x = x - y;
                r = r | 1;
            }
            x = x << 1;
        }
        /* OR remainder bits into sticky bit */
        sticky = (x != 0);
        if ((expo_res >= MIN_NORM_EXPO) &&
            (expo_res <= MAX_NORM_EXPO)) { /* normal, may overflow to infinity*/
            /* extract round and lsb bits */
            rnd = (r & ROUND_BIT);
            odd = (r & MANT_LSB) != 0;
            /* remove round bit from quotient and round to-nearest-even */
            r = (r >> 1) + (rnd & (sticky | odd));
            /* combine exponent and significand */
            r = ((uint32_t)expo_res << EXPO_SHFT) + (r - MANT_INTBIT);
        } else if ((int16_t)expo_res > MAX_NORM_EXPO) { // overflow: infinity
            r = INFTY;
        } else { /* underflow: result is zero, subnormal, or smallest normal */
            uint8_t shift = (uint8_t)(1 - expo_res);
            /* clamp shift count */
            if (shift > QUOT_BITS) shift = QUOT_BITS;
            /* OR shifted-off bits of significand into sticky bit */
            sticky = sticky | ((r & ~(~0 << shift)) != 0);
            /* denormalize significand */
            r = r >> shift;
            /* extract round and lsb bits */
            rnd = (r & ROUND_BIT);
            odd = (r & MANT_LSB) != 0;
            /* remove round bit from quotient and round to-nearest-even */
            r = (r >> 1) + (rnd & (sticky | odd));
        }
        /* combine sign bit with combo of exponent and significand */
        r = r | sign;
    } else { /* slow path */
        /* take absolute value of arguments */
        x = a & ~SIGN_MASK;
        y = b & ~SIGN_MASK;
        /* if dividend is a NaN, convert that NaN into a QNaN and return it */
        if (x > INFTY) return a | QNAN_BIT;
        /* if divisor is a NaN, convert that NaN into a QNaN and return it */
        if (y > INFTY) return b | QNAN_BIT;
        /* dividend and divisor are both zero or infinity: invalid operation */
        if (((x == 0) && (y == 0)) ||
            ((x == INFTY) && (y == INFTY))) return INDEFINITE;
        /* 0/y or x/INF -> 0 */
        if ((x == 0) || (y == INFTY)) return sign;
        /* x/0 or INF/y -> INF */
        if ((y == 0) || (x == INFTY)) return sign | INFTY;
        /* if dividend is a subnormal, normalize it */
        if (expo_x == 0) {
            expo_x++;
            do {
                a = a + a;
                expo_x--;
            } while (!(a & MANT_INTBIT));
        }
        /* if divisor is a subnormal, normalize it */
        if (expo_y == 0) {
            expo_y++;
            do {
                b = b + b;
                expo_y--;
            } while (!(b & MANT_INTBIT));
        }
        /* now that dividend and divisor are normalized, do the division */
        goto divide;
    }
    return r;
}


Optimise the size of union of sets We consider a set of sets $S = \{S_1, S_2, \dots, S_n\}$, and we want to find a subset $I$ of $S$ that maximises the size of the union of the set $S_i$ included with a penalty for each set included. We can represent this problem as the optimisation of the following quantity:
$I = argmax_{I} |\cup_{S_i \in I} S_i| - |I|$
What would be an efficient way to solve this optimisation problem?
We know from the inclusion-exclusion principle that the union of sets can be expressed as follows:
$|S_{i_1} \cup \dots \cup S_{i_k}| = \sum_{j=1}^{k} (-1)^{j+1} \sum_{1 \leq l_1, \dots, l_j \leq k}  |S_{l_1} \cap \dots \cap S_{l_j}|$

Your problem is NP-hard. Given an instance $T_1,\ldots,T_n$ of Maximum Coverage, let $x_1,\ldots,x_n$ be new variables, and create an instance $S_1,\ldots,S_n$ of your problem, where $S_i = T_i \cup \{x_i\}$. We have
$$
\left| \bigcup_{i \in I} S_i \right| -|I| = \left| \bigcup_{i \in I} T_i \right|.
$$
On the positive side, consider the following greedy algorithm: $I_0 = \emptyset$, and for $k = 1,\ldots,n$, $I_k$ is obtained from $I_{k-1}$ by adding the set which maximizes the total number of elements covered by sets in $I_k$. It is known that for $k \in \{0,\ldots,n\}$, the set $I_k$ found by the greedy algorithm has the following property: for all sets $J_k$ of size $k$ we have
$$
\left| \bigcup_{i \in I_k} S_i \right|  \geq
(1-1/e) \left| \bigcup_{i \in J_k} S_i \right|.
$$
In particular, if the optimal solution to your problem has size $k$ and objective value $O$, then
$$
\left| \bigcup_{i \in I_k} S_i \right| \geq (1-1/e)(O + k),
$$
and so
$$
\left| \bigcup_{i \in I_k} S_i \right| - k \geq (1-1/e) O - k/e.
$$
The minimal optimal $k$ satisfies $O \geq k$ (each set adds at least one new element), and so $(1-1/e) O - k/e \geq (1-2/e) O$. This shows that the greedy algorithm (more explicitly, finding $k$ which maximizes $|I_k|-k$) gives a $1-2/e$ approximation to your problem (this can probably be improved).


timed automata - advance only in certain states I am currently looking into timed automata for a project.
I am thinking about a timed automaton where a clock only advances when the automaton is in a certain state.
However, my little knowledge in the domain makes me wonder whether somebody already defined timed automata like that.

As an example:
I.e. I have a timed automaton with two states: L0 and L1.
My clock is c - the total time that the automaton spent in time L1.

The clock c should only advance when the automaton is in state L1.

(see upper part of drawing)

Solution with my existing knowledge (not very elegant):

I can see a way where I could use event-clock automata (1) to achieve this, by triggering an event a and on entering L1 the value of c is set to:
c := c - xa
where xa is the time since event a.
(See lower part of the drawing)

However, I'm not convinced of this solution as it is inelegant, further I'm not sure whether timed automata allow for the setting of clocks. So far I only read about reset to zero.

(1) http://pub.ist.ac.at/~tah/Publications/a_determinizable_class_of_timed_automata.pdf

So, after looking deeper into the subject I found the solution. Posting in case somebody else needs an answer and is unfamiliar with the subject.

What I was looking for is called a Stopwatch Automaton (SWA) and allows the time to stop or advance (by specifying the derivative of a clock c' = {0, 1}).
Reference: The Impressive Power of Stopwatches. Franck Cassez, Kim Larsen
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.123.669&rep=rep1&type=pdf

Further I discovered that Hourglass automata also allow time to stop, but additionally also to reverse: c' = {-1, 0, 1}.
They however require the specification of a maximum clock value after which "all the sand passed through the hourglass" and the clock does not advance further.
Reference: Hourglass Automata.
Yuki Osada, Tim French, Mark Reynolds, Harry Smallbone
https://arxiv.org/abs/1408.5965


Polymorphism restriction on lambda-bound variables in HM I'm trying to implement the Hindley-Milner type system, following Milner 1978, "A Theory of Type Polymorphism in Programming" (link). In the Hindley-Milner system, a polymorphic let-bound expression may take on a different type each time it is referenced. For example, we can have let id = (λx · x) in (id 3, id true) where id has type α → α with two instantiations, α = int and α = bool. However, the variable of a lambda expression is not permitted to be polymorphic in this way: λf · (f 3, f true) is not a well-typed expression.

To prevent this restriction from being "cheated" by something like λx · let x2 = x in ..., we must recognize some restriction on the polymorphism of let-variables as well. Milner 1978 describes it as follows:

  We decree that in instantiating the type of a variable bound by let or
  by letrec. only those type variables which do not occur in the types
  of enclosing λ-bindings (or formal parameter bindings) may be
  instantiated. We call such instantiable variables (in a generic type)
  generic type variables.

However, using what seems to me the obvious interpretation of "enclosing λ-bindings" (namely, that the let-expression should occur in the e of some λx · e), Milner's prescription does not seem to cover all of the cases where it is necessary to prevent some type variables of a let-binding from being polymorphically instantiated. Consider the following expressions:

let id = (λx · x) in (id 3, id true)
let id = (λx · x) (λx · x) in (id 3, id true)

While the first one is of course acceptable, I believe the second one should not be, as if this type of code is allowed, it becomes impossible in general for a compiler to generate statically typed code. And indeed, OCaml rejects the statement let id = (fun x -> x) (fun x -> x) in (id 3, id true).

So my questions are:

Am I interpreting the paper incorrectly?
How should I determine whether a type variable in a let-bound expression is eligible to be instantiated with multiple types?

Yes, you are restricting it too much. The second code is perfectly fine.

For the record, Haskell has no issue with your code:

> let myid = (\x->x)(\x->x) in (myid 'a', myid True)
('a',True)

and Ocaml as well works fine, after eta-expansion:

let myid y = (fun x -> x)(fun x -> x) y in (myid 'a', myid true);;
- : char * bool = ('a', true)

Eta expansion is needed in Ocaml, I think, because of the value restriction, where a binding is not generalized unless it is a function (let f x = ... instead of let f = ...). This restriction was needed to avoid some soundness issues with mutable variables -- remember Ocaml is not a "pure" language, and allows side effects everywhere.

Anyway, Hindley-Milner should generalize let f = (\x->x)(\y->y) in ... just fine. First, \y->y is given the monotype $\alpha\to\alpha$, where $\alpha$ is a fresh type variable. Then \x->x is given $\beta\to\beta$, with a fresh $\beta$. Then we type check the application, which succeeds and unifies $\beta = (\alpha\to\alpha)$. The resulting type for the application is $\alpha\to\alpha$. Since $\alpha$ is not present in the environment, it can be generalized so the we get
$f : \forall \alpha.\, \alpha\to\alpha$.

Bonus exercise: type check the following

# let myid y = (fun x -> x)(fun x -> x) y ;;
val myid : 'a -> 'a = <fun>
# myid myid myid true;;
- : bool = true


A real life system that faces and solves the dining philosophers problem I'm looking for an application of the dining philosophers problem. Is there some real life system that faces the concurrency problem of "the dining philosophers problem" and implements a solution? I've been searching for over an hour.

It would be even better if the implemented solution is Tanenbaum's solution described here.

The dining philosopher's problem is a worst case scenario used to illustrate issues in algorithms. It's a test case. You probably won't find a static one-to-one mapping between it and a real world case.

However, similar situations can occur dynamically. If at any point the graph of actors waiting for resources forms a cycle, you are stuck in a deadlock. Most of the time this happens with n = 2 actors, but sometimes you can get more complicated deadlocks.


Inserting at the head of a linked list is O(1), but this involves moving pointers, and they are not constant size I don't understand how linked list insertion is constant time.  The larger the list gets, the more bits are required to specify memory locations, and then the more bits that must be edited to account for changes in pointers.

Where is my mistake here?

We usually analyze algorithms using the RAM model, in which basic operations on machine words cost $O(1)$. On an input of length $n$ bits, the size of a machine word is $\log n$. In your case, a pointer should fit into one machine word, and so moving a pointer should take $O(1)$ time.

A different issue is how much time is required to maintain the heap. One way around this is to work in the "heap-enabled RAM model", in which heap operations are for free. Probably many papers on algorithms implicitly work in this model.

Finally, a few words on the RAM model. It extends the Turing machine model in two ways. First, it allows indexing. This matches the way actual computers work. Second, it allows constant time arithmetic on machine words, which are usually chosen as indicated above. The size of machine words is chosen so that operations on indices take $O(1)$. For example, consider the following program for summing an array $A$:

sum = 0
for i from 1 to n:
  sum = sum + A[i]
return sum

If we want this algorithm to run in $O(n)$, we need the operation $i \to i + 1$ to run in $O(1)$. Since $i$ could be $\log n$ bits long, we need machine words to be at least $\log n$ bits long. Practice shows that it is not necessary to consider larger machine words. Note that machine words of size $C\log n$ can be simulated using $O(1)$ machine words of size $\log n$ using a multiplicative overhead of $O(1)$; since we don't care about constant factors, increasing the machine word to size $C\log n$ doesn't affect the power of the model.


Is there a difference between $\lambda xy.xy$ and $\lambda x.\lambda y.xy$? I am currently learning the lambda calculus and was wondering about the following two different kinds of writing a lambda term.

$\lambda xy.xy$
$\lambda x.\lambda y.xy$

Is there any difference in meaning or the way you apply beta reduction, or are those just two ways to express the same thing?

Especially this definition of pair creation made me wonder:

  pair = $\lambda xy.\lambda p.pxy$

The first is an abbreviation for the second. It's a common syntactic convention to shorten expressions.

On the other hand, if you have tuples in the language, then there is a difference between

$\lambda x.\lambda y.xy$ and
$\lambda (x,y).xy$.

In the former case I can provide a single argument to the function, and pass the resulting function around to other functions. In the latter case, both arguments must be supplied at once. There is, of course, a function that can be applied to convert 1 into 2 and vice versa. This process is known as (un)currying.

The definition of $\text{pair}$ you mention is an encoding of the notion of pairs into the $\lambda$-calculus, rather than pairs as a primitive data type (as I hinted at above).


Isomorphisms between regular graphs of same degree Are all $n$-vertex regular graphs of degree $d$ isomorphic?

Can someone provide an example of two non-isomorphic graphs $G_1$ and $G_2$ which are both regular with degree $d$ and have the same number of vertices (i.e., $|G_1| = |G_2|$)?

Of course not.

Consider, for example, the cycle $C_6$ with six vertices and the graph obtained by the union of two copies of $C_3$. Then both are 2-regular, but they are obviously not isomorphic.

This is also the case if we restrict the question to connected graphs. Consider, for instance, the following two 3-regular graphs:

You can see they are not isomorphic because the second one contains cycles with six vertices that have chords; this is impossible in the first graph since it has precisely four six-cycles and you can see none of them have chords. (Or even easier: The second one has a five cycle, whereas the first one has only cycles with three, four, six, or more vertices.)

What you might be able to prove is that all 2-regular and connected graphs are isomorphic (see, e.g., this), but this is a big restriction compared to the original question.


How to generate uniformly random binary trees? Could someone please provide a reference giving an algorithm to generate uniformly random binary trees?

There is a article available here and survey available here

But desipte that its very easy to generate such tree, it all depends on random generator, it must be uniform.

There are two simple approaches:

Generate full tree up to some height and randomly cut edges
Start from root and make decision about each child on lower level

Both of them are guarantee to end, fist one is obvious, second one needs some induction proof which is quite simple to do.

Taking into account Juho's hint take a look at Boltzmann sampling, it is indeed a powerfull tool which you can use. And here's a working example.


Complexity Classes UP and US According to complexity zoo:
Class UP (Unambiguous Polynomial-Time) is defined as:
The class of decision problems solvable by an NP machine such that

If the answer is “yes,” exactly one computation path accepts.
If the answer is “no,” all computation paths reject.

Class US (Unique Polynomial-Time) is defined as:
The class of decision problems solvable by an NP machine such that the answer is “yes” if and only if exactly one computation path accepts.

In contrast to UP, a US machine can legally have more than one accepting path that just means that the corresponding input is not in the language.

My question is:

Is there an example of a problem which is known to be in one class,
but not in other?  We know that UP $\cup$ coNP $\subseteq$ US.
It is known that class US is a subset of $P^{NP}$. A well-known example is USAT which is known to be US-hard (and coNP hard) but not known to be coNP. US is not known to be equal to coNP. Also, I know that coNP $\subseteq$ US. Can one give an intuitive reason for this?
How can a machine have more than one accepting path, but
that input is not in the language? (Maybe I am missing something
trivial here)

Let me start with your third question. It seems that you don't quite understand the definitions of $\mathsf{UP}$ and $\mathsf{US}$, so let me repeat them here.

Definition of $\mathsf{UP}$. Property U. A non-deterministic Turing machine has property U if every input has at most one accepting path. The language accepted by such a machine consists of all inputs which do have an accepting path.
The class $\mathsf{UP}$ consists of all languages accepted by non-deterministic Turing machines having property U and running in polynomial time.
Definition of $\mathsf{US}$. U-acceptance. The language accepted by a non-deterministic Turing machine consists of all inputs which have an accepting path. In contrast, the language U-accepted by a non-deterministic Turing machine consists of all inputs having exactly one accepting path. Any input having either no accepting path or at least two accepting path does not belong to the language U-accepted by the machine.
The class $\mathsf{US}$ consists of all languages U-accepted by non-deterministic Turing machines running in polynomial time.

As for your second question, to show that $\mathsf{coNP} \subseteq \mathsf{US}$ it suffices to reduces $\mathsf{coSAT}$ to $\mathsf{US}$. Given a SAT instance $\phi = C_1 \land \cdots \land C_m$, let
$$\psi = (v \lor C_1) \land \cdots \land (v \lor C_m) \land (\lnot v \lor x_1) \land \cdots \land (\lnot v \lor x_n),$$ where $v$ is a new variable and $x_1,\ldots,x_n$ are the original variables. Then $\psi$ has a unique satisfying assignment (in which all variables are true) iff $\phi$ is unsatisfiable.
As for your first question, if $\mathsf{P} = \mathsf{NP}$ then $\mathsf{P} = \mathsf{UP} = \mathsf{US}$, so no unconditional separation is currently known. If you're interested in conditional separations, I suggest asking a new question focused just on that issue.


Implementing SUM(i,j) and CHANGE(i,j) in O(log(n)) using a datastructure with O(n) space complexity I have two operations:

$Sum(i,j)$ : Calculate $A[i]+A[i+1]+....+A[j]$

$Change(i,x)$: Set $A[i]=x$

I need to implement these operations in an appropriate data structure using $O(n)$ space ($n$ is the length of the input array $A$).

The $Sum(i,j)$ procedure needs to have a runtime complexity of $O(\log(n))$ and the $Change(i,x)$ procedure needs to have a runtime of $O(\log(n))$.

I thought about using a heap seeing as change-key in a heap is $O(\log(n))$, but I cant figure out how exactly to get the $Sum(i,j)$ procedure down to $O(\log(n))$. To me it seems you would need $O(n)$ time to do this. If anyone could nudge me in the right direction I would appreciate it.

What is a Segment Tree?

It is a data structure which is used to operate over a range of input.

  How does it work?

The original elements of the array form the leaves of the tree. Each internal node represents some merging of the sub trees. For example consider the array $A = [1,5,7,8,9,15]$.

If we were to construct a segment tree out of the array with the sum operation in mind, we would have the following tree.

  What about the run time complexity?

If we try to implement the $Sum(i,j)$ and $Change(i,x)$ operations via a segment tree, the time complexity would be the following:

 Construction of the Segment Tree: This would take $O(n)$ time.
 $Sum(i,j)$ : This would take $O(\log(n))$ time.
 $Change(i,x)$ : This would take $O(\log(n))$ time.

  What about the space complexity?

Being an almost complete binary tree, a Segment tree with $n$ leaf nodes will have $2n — 1$ total nodes. Hence the space complexity will be $O(n)$.


What is the difference between maximal flow and maximum flow? What is the difference between maximal flow and maximum flow. I am reading these terms while working on Ford Fulkerson algorithms and they are quite confusing. I tried on internet, but couldn't get a reasonable answer. I believe maximum flow is quite clear as it means maximum amount of flow that can be transferred from source to sink in a network, but what exactly is maximal flow.

Please answer in layman terms if possible.

Thanks.

As saadtaame mentions, maximum usually means global maximum, whereas maximal means local maximum. For example, a maximal independent set in a graph is one to which no vertex can be added (making it a dominating set), while a maximum independent set is one with largest cardinality among all independent set.

My guess is that a maximal flow is one in which every source-to-sink path has a saturated edge (i.e., the flow equals the capacity). Such a flow cannot be improved by pushing more flow through some source-to-sink path.

It so happens that such a flow is also maximum. To see this, consider the residual network, formed by the unsaturated edges. Let $C$ be the connected component containing the source. Since the flow is maximal, $C$ does not contain the sink, and so it forms a source-sink cut in the graph. The value of every flow in the graph is bounded by the capacity of edges crossing the cut. Yet by definition, this is also the value of the flow under consideration, completing the proof.


Is order of matrix multiplication affecting numerical accuracy of the result? I have to multiply three matrices of floats: A (100x8000), B (8000x27) and C (27x1).

Is there any difference in accuracy between A(BC) and (AB)C?
If yes - how may I determine the more accurate multiplication order?
Speed is not a factor here.

Matrices A and B contain 8000 samples of (respectively) 100 and 27 features.

Yes, there are differences in accuracy since with machine numbers the usual properties of arithmetics don't hold.

Machine numbers are defined as
$$ F(\beta,t,m,M)= \{ 0 \} \cup \{ x \in \mathbb{R} : x = sign(x)\beta^{p} \sum_{i=1}^{t}d_i\beta^{-i},\ 0 \leq d_i \lt \beta\ ,\ d_1\ne 0\ , -m \le p \le M  \} $$ and represent the subset of $\mathbb{R}$ that your machine is able to represent.

All other numbers must be approximated with a number in this subset (usually by truncating the numbers or rounding them).

Let's assume we are in $F(10,2,m,M)$ meaning we are working in base 10 with two digits.

Let $x=0.11*10^1$, $y=0.31*10^{1}$ and $z=0.25*10^{1}$.

The associative property of multiplication doesn't hold:

$(x*y)*z = 0.34*10^1 * z = 0.85*10^1$

and

$x*(y*z) = x * (0.78 * 10^1)  = 0.86*10^1$

other properties that don't hold are:

the associative property of the addition
distributive properties
$x(y/x)$ isn't always equals to $x$
if $xy=yz$ then isn't always true that $x=z$


Clarifying what it means to be Strongly NP-Complete Wikipedia defines strongly NP-Complete as:

  A problem is said to be strongly NP-complete, if it remains so even when all of its numerical parameters are bounded by a polynomial in the length of the input.

What I interpret this to mean is this:

Let's consider the 3-partition problem, with our numerical paramater being $\sum_{x \in S} x = B$. Since this problem is strongly NP-Complete, there exists a polynomial $p(N)$, such that if we restrict ourselves to only sets $S$ such that $B < p(|S|)$, this problem is still NP-Complete. (i.e. finding an algorithm with complexity polynomial in $|S|$ for this restriction would prove P=NP)

Is this the correct interpretation? If so, where could I find upper bounds of such polynomials $p$ for famous problems, such as the 3-partition problem? Also, if I'm not mistaken, this implies that the 3-partition problem is NP-complete in terms of $B$, as well as $|S|$, right?

Yes, that's correct.  You'll probably have to figure out the polynomial yourself.  The way to find the polynomial is to look at the reduction, and from that you should be able to deduce a polynomial.

In your case, I believe there is a reduction from 3D-MATCHING to 3PARTITION, so you would analyze that reduction to find the polynomial.  Given an instance of 3D-MATCHING, the reduction explicitly constructs an instance of 3PARTITION whose solution can be used to solve the 3D-MATCHING instance; so you'd analyze how large the parameter of 3PARTITION instance could possibly be, as a function of the size of the set, and that would tell you the polynomial $p$ you are looking for.


How to prove the NP-completeness of 15-Partition Problem I would like to have a proof of the NP-completeness for 15-Partition Problem.

It is analogous to the well-known 3-Partition Problem. The problem is to decide whether a given multiset of integers can be partitioned into subsets of 15 members that all have the same sum. More precisely, given a multiset S of n = 15 m positive integers, can S be partitioned into m subsets of 15 members S1, S2, …, Sm such that the sum of the numbers in each subset is equal?

It is not an excercise, it is a real problem dealing with load balancing. I did not expect someone would suspect it as a homework/excercise. I mentioned only related facts, obviously, I need to say more. I have a hardware switch with 15 ingoing ports and one outgoing port. Such switches, I have actually 6. That means, I have 15 x 6 = 90 ingoing ports. I have to connect cabels to these 90 ports and I can not affect how much data flows throught these 90 cabels. My task is to assign these 90 cabels to these 90 ports such that the output flow from each switch would be equal. I have already implemented 4 algorithms solving this problem based on dynamic programming, integer linear programming, differential evolution and reinforcement learning.

I would like to have an exact proof that the problem is not so easy to solve, i.e., I would like to prove it belongs to NPC.

Moreover, I have realized today, in case of total flow is not divisible by 6, all switches will not have the equal sum of flow on outgoing port. For example, total flow is 456 254 bytes, then Switch1 to Switch2 should have flow 76 043 bytes each and Switch3 to Switch6 should have flow 76 042 bytes. So maybe, I can not use 15-Partition Problem, not sure about it.

I think this could work.

We multyply all the numbers by fifteen and we also multiply $B$, the quantity that each "bucket" should add to, by fifteen and we add twelve to it. Then we add twelve numbers of size one for each bucket to the input.

As twelve is less than fifteen, we have to use exactly twelve of them to fill each bucket, then we have to use other three numbers to fill each bucket. As random_hacker says in the comment, if we use more than twelve numbers in a bucket, we will not be able to cover the gaps in another bucket and so that bucket won´t be able to reach the quantity it should reach.

We see that if the big numbers fill the buckets in 15-partition, they also fill the buckets in 3-partition. Also, if we put four or more big numbers in a bucket, we will have more than fifteen numbers in that bucket


Is $\Gamma \vdash x x : T$ possible in the simply typed lambda calculus? Is $\Gamma \vdash x x : T$ possible?

This problem appears on page 104 of Benjamin Pierce's "Types and Programming Languages".

My conclusion is that it is was the case then we would get $x: T_1 \to T_2$ and $x:  T_1$ and by some axiom, these types are not equal.

The problem is identifying this axiom but I fear it might be possible to have this equality...

Any hints?

You are on the right track. The argument you would use is on the lines of
size of types defined below: (I am assuming you are in the world of simply typed $\lambda$-calculus)

$size(T) = 1$

$size(T \to T') = size(T) + size(T')$

Unification will only work if the size of types is equal, and in this case
$size(T \to T') > size(T)$ hence there cannot be such a term.

However, if you add recursion/non-termination in the type system.
You can indeed have such a term.
$ \vdash (\lambda x. x x) (\lambda x. x x):\bot$

$\bot$ is the type that represents non-termination.


Time Complexity of inserting a vector to a vector of vectors in C++ I was solving a question on LeetCode, where I had to generate all possible subsets of a given set of numbers.
Although, the solution makes sense to me, I am unable to understand the derivation of time complexity for those solutions.
A solution I found there was:
class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> subs = {{}};
        for (int num : nums) {
            int n = subs.size();
            for (int i = 0; i < n; i++) {
                subs.push_back(subs[i]);  <---- LINE X
                subs.back().push_back(num); <---- LINE Y
            }
        }
        return subs;
    }
};

It is an iterative solution to solve the problem.
What I don't understand is the time complexity of the given solution and more importantly, the complexities of Line X and Line Y.
Does copying subs[i] take O(n) time and then pushing back take another O(n) time, or is it an O(1) step?

First tings first:
Line X does a copy subs[i] and creates a new vector.
In terms of vector length $n$ this step is $O(n)$.
Line Y is amortized O(1). (The vector might need to reallocate making it O(n) in the worst case; to avoid reallocation see @MSalters post.)
The runtime of the whole procedure is a bit more difficult.
At the $i$-th number subs contains every possible subset of all numbers so far.
Thus length of subs $=2^i$, but we are interested in how many numbers we need to copy. this can be calculate with the sum of all subset sizes which is $i2^{i-1}$ (meaning at step $i$ we have to copy $i2^{i-1}$ numbers and make $2^i$ push operations).
$$O\left(\sum_{i=0}^{n-1} i2^{i-1}+2^i\right) = O(n2^n)$$
The complexity on the right makes sense, all sizes of all vectors in subs will be $n2^{n-1}$ in the end.


Can I use infinite numbers in a reduction? I have to reduce $L_\text{empty}$ to $L_\text{inf}$

where

$\qquad L_\text{empty} = \{e \mid |L(P_e)| = 0 \}$ and
$\qquad L_\text{inf}= \{e \mid |L(P_e)| = \infty \}$.

where $P_e$ is the program with Gödel number $e$, and $L(P_e)$ the language it accepts.

So can I define a program $P$ like this

input n
Run Pe on 1...n for n steps
if Pe accepts any number then
  enter an infinite loop and start accepting infinite number
if Pe does not accept any number then
  accept 1

Now if I can define program P like above then asking the question whether the index of $P$ is in $L_\text{inf}$ will tell me whether the language accepted by $P_e$ is empty or not.

A language cannot contain infinite numbers, since by definitions it is a set of finite numbers. The language itself could be infinite, though: it could contain infinitely many numbers.

In your solution, in the first case, you first enter an infinite loop and then "start accepting infinite numbers", but once you've entered an infinite loop, you're not accepting anything.

Your reduction $f$ has to satisfy the following two properties:

If $e \in L_{\mathrm{empty}}$ then $f(e) \in L_{\mathrm{inf}}$.
If $e \notin L_{\mathrm{empty}}$ then $f(e) \notin L_{\mathrm{inf}}$.

In plain English:

If $L_e$ accepts no inputs then $L_{f(e)}$ should accept infinitely many inputs.
If $L_e$ accepts at least one input then $L_{f(e)}$ should accept finitely many inputs.

Try to see if you can come up with such a function $f$. The basic idea is similar to yours - on input $n$, $f(e)$ should check whether $L_e \cap \{1,\ldots,n\} \neq \emptyset$. You should just be more careful in what happens next.


What do I need to know about algorithms? Drawing from Are algorithms (and efficiency in general) getting less important?, I get that algorithms are more important than ever, but I need to know anything about them other than their complexities?

I would expect to use algorithms out of a library of some sort that has been written by people that are much much more knowledgeable than me, and have been thoroughly tested (most of the STL comes to mind here, but also boost, and probably every other library that someone would care to name).

Thus, unless I am a library maintainer/implementer of some sort, do I need to know anything about these algorithms?

If you do anything a bit complicated, you will almost certainly have to design your own algorithms. STL/boost are nice, amazing really, but it is useful to know how things work behinds the scenes and be able to reproduce it. This will help you tackle problems that the STL/boost, generic enough as they are, cannot handle; or problems that are entirely different from the ones the STL/boost can help with. Many times, algorithms and data structures that I've designed were built on top of STL/boost.

  Thus, unless I am a library maintainer/implementer of some sort, do I need to know anything about these algorithms.

Chances are, if you make any interesting programs, you are going to find it useful to design some algorithms and data structures. Sometimes, the most effective optimizations cannot beat a simple change in methodology or representation.

Unless the algorithm you require/design is useful to a wider audience, it can sometimes be difficult to package it as a useful library. Perhaps you will find that something you made can be useful, and will publish it (github is chock full of these projects). Therefore, I think that if you program long enough, you will become a "library maintainer/implementer of some sort", even if you are the only one using it, for lack of publicity.

Bottom line: I don't think libraries like STL and Boost are making knowing algorithms less important at all; rather they are making more advanced algorithms within reach. While libraries such as these can sometimes make knowledge of their algorithms unnecessary for small programs, in practice it can important to know if you intend to design anything complex.


Proving that $\mathrm{SpaceTMSat}$ is PSPACE-complete Let $\mathrm{SpaceTMSat} = \{\langle M, w, 1^n\rangle\mid\text {DTM $M$ accepts $w$ in space }n\}$.

How do I prove that this language is PSPACE-complete?
NP contains NP-complete problems and so does PSPACE. Am I supposed to prove it the same way as I would prove an NP-complete problem?

For any complexity class $X$, a language is $X$-complete if it's in $X$ and every problem in $X$ can be reduced to it. There are two main ways to prove that a language is $X$-complete: literally show that it meets the definition of $X$-completeness, or show that some other $X$-complete problem reduces to it.

In cases where the language is essentially, "Here's a machine in~$X$ and an input: does it accept?", it's usually best to go for the literal approach and show that every problem in the class can be reduced to your problem. Why? Because every problem in the class is decided by a Turing machine, and your language is about whether those Turing machines accept or not.


Complexity of Integer Factorization In Quantum Information and Quantum Computation by Nielsen and Chuang, they define the complexity class NP as follows (page 142):

A language $L$ is in NP if there is a turing machine $M$ with the following properties.

If $x\in L$ then there exists a witness string $w$ such that $M$ halts in the state $q_Y$ ("yes state") after
a time polynomial in $|x|$ when the machine is started in the state $x$-blank-$w$.
If $x \not \in L$ then for all strings $w$ which attempt to play the role of a witness, the
machine halts in state $q_N$ ("no state") after a time polynomial in $|x|$ when $M$  is started in the
state $x$-blank-$w$.

This definition is motivated by the factoring decision problem, where they identify "witness strings" $w$ with possible factors of $x$.
My confusion is, based on how NP is defined, it seems like we are able to construct a polynomial time algorithm for solving the factoring decision problem. For a given string $x$, start the factoring turing machine $M$ in the state $x$-blank-$w$ for all $w < x$, and check whether the machine ever halts in $q_Y$. Since there are $O(|x|)$ witnesses to check, and for each witness, the machine will halt in polynomial time, it follows that this algorithm will determine whether $x$ has factors in polynomial time.
Clearly this shouldn't work, but I am unsure where the flaw in my logic is.

The issue is that your proposed algorithm is polynomial with respect to the numerical value of the input, but not relative to the input's size. The binary encoding of $N$ requires at most $\lceil\log n\rceil$ bits, so an algorithm which takes the encoding of $N$ and preforms $\Omega(N)$ operations is actually exponential. Such algorithms are said to run in pseudo polynomial time.
Additionally, it seems that you are confusing factoring and primality testing. A possible decision version of factoring is given $(n,x)$ check whether $n$ has a factor $\le x$ (while your proposal refers to the case where only $n$ is given, and you loop to find a possible factor). While checking if a given number is prime is known to be in $P$, FACTORING is believed to lie outside of P.


How to get the optimized quicksort algorithm's time complexity I learned in my data structures class that QuickSort can be optimized by calling the InsertionSort method when the length of the subarray is less than a certain threshold. However, when it comes to the actual time complexity calculation of the optimized version of QuickSort, I'm having trouble finding the result. The problem is as follows.

An optimized-QuickSort function calls the InsertionSort method instead of itself when the size of the sublist is less than k. Assuming that the time complexity of QuickSort and InsertionSort is $c_1n\log n$, $c_2n^2$ respectively, what is the time complexity of optimized-QuickSort? (Calculate for the average case)

I assumed that the sublist is split into 1:1 by each step. As a result, I got $c_1nlog$($n\over k$) + $c_2nk$, but I am definitely not sure of my answer since I don't know if my assumption is correct. In the textbook, the average case of a non-optimized QuickSort was supposed to be calculated by assuming the partition could be the first element, second element, third element, ... , last element and then dividing the whole sum by n.

I would appreciate some help! Thanks.

The height of tree is not $log(\frac{k}{n})$ which is negative because $k<n$. We stop expanding the tree when we reach $k$, therefore we reduce the height of the original tree by $log(k)$. So the height is $log(n)-log(k)=log(\frac{n}{k})$ and the average running time will be: $$c_1nlog(\frac{n}{k})+c_2nk=c_1nlogn-c_1nlogk+c_2nk$$
As noted in comments, since $k$ is constant, that is equivalent to $\theta(nlogn)$.

EDIT: I just noted that the problem was about average case complexity and you assumed the partition to have 1:1 ratio, which is the assumption for best case scenario.
For average case analysis, we shouldn't consider any fixed partition ratio.

You can use the average case analysis in section 7.4.2 of CLRS book; except that here the probability of comparing the ith and jth element would be at most $\frac{1}{j-i+1}$, so the $c_1nlogn$ would be an upper bound on the Quicksort part of the average case. As for Insertion sort part, there would be at most $n/k$ leaves with size $k$, with total cost of $\frac{n}{k}c_2k^2=c_2nk$.


Is it possible to come up with a graph instance that would force Dijkstra to perform a decrease key on every single edge? From the analysis of Dijkstra there is a $O(mlogn)$ factor that assumes we do a decreasekey for every single edge of the given input graph.

However I find it hard to come up with an instance that can actually require this. All you have to do create the edges and then add the weights in a way that would induce a large number of decrease keys.

Is there any known way of doing that?

Yes!

A bit convoluted example is the following:

Suppose you have $n+1$ nodes and you run djikstra from $a_{0}$
Let $A=[a_{0},a_{1},a_{2}.....,a_{n}]$ the final result of the algorithm(i.e the nodes of the graph sorted by their distance from $a_{0}$)

We will now create a graph which will require every edge to be updated:

First of all add edge $e_{i}=(a_{i} , a_{i+1})  $   with $cost(e_{i})=0$ for every $i<n$

Let $M$ be a really Big Value.

For every $i<n$ and $j>i+1$ add the edge $e_{ij}=(a_{i},a_{j})$ with $cost(e_{ij})=M-i$

At every step $i$ of the algorithm ALL values of the nodes will be updated.

ex.  $M=100,  n+1=5$

Distance matrix for $A$

step 0: [-,0,100,100,100,100]

step 1: [-,-,0 , 99, 99 ,99]
and so on....


PDA with N-Stacks comparison with Turing Machines Is it possible to compare PDA having N-Stacks with Turning Machines. Are they equally powerful in this situation?

It's been told that PDA with 2-Stacks is equally powerful to Turning Machine. But what if we add more stacks i.e. 3, 4, 5...N to PDA; will it become more powerful or it can serve same purpose.

2 stacks is enough for a PDA to be as powerful as a Turing Machine. Basically, you can pop from one stack and push into the other to simulate moving across the tape head, writing, etc.

In fact, a 2-counter machine is as powerful as a Turing Machine, though the proof is much more involved. There's a sketch of it on Wikipedia


Are DCFLs closed under reversal? According to this chart, DCFLs are closed under reversal.

However, I am not convinced as the intuitive proof (reversing the arrows of the controlling finite state machine and switching the pushes and pops) for this seems to depend on non-determinism in choosing the null transition to take from the initial state (since the new initial state would contain a null transition to all the old final states).

This would make the "reverse PDA" of a DPDA non-deterministic whenever there is more than a single final state in the original DPDA.

What is the fallacy in my argument? Or is there another way to go about proving this?

I looked up Hopcroft and Ullman 1979 and it say on page 281 that it is not closed under reversal. But I  found no proof in my very fast look at the relevant chapter.
Searching the web does also give a negative answer, with counter example, on stackoverflow by a member of CS (notation adapted):

$(a+b+c)^*WcW^R$, where $W \in (a+b)^+$; this is non-deterministic because you don't know where the $WcW$ bit starts.
$W^RcW(a+b+c)^*$, where $W \in (a+b)^+$; this is deterministic because you can write a deterministic PDA to accept simple palindromes of the form $W^RcW$ and modify the accepting state to loop to itself on any of $a$, $b$ and $c$.
The trick here is that PDAs have to read input from left to right.


Is open adressing with prime steps bijective? Who can help me with this topic: Probing with a step width that is a prime number.

I am struggling with this question about defining a hashing function $h(k, i)$ for open addressing on a table of length m, that is, with slots numbers $0, 1, 2, \dots ,m − 1$.

We know that a function $h(k, i) = h_1(k) + i \cdot h_2(k) \mod m$ produces a permutation for every $k$ if $h_2(k)$ and $m$ are relatively prime, that is, if $\operatorname{gcd}(h_2(k),m) = 1$.

We can assume that $m, w$ be integers such that the greatest common divisor $\operatorname{gcd}(m,w) = 1$.

How can I prove that the function above

$\qquad f : \{ 0, \dots,m − 1 \} \to \{ 0, \dots,m − 1 \}\\
 \qquad f(i) = i \cdot w \mod m$

is a permutation, in other words, a bijective function?

The following proof only uses basic modular arithmetic, and the fact that the least common multiple $\mathrm{lcm}(a,b)$ is equal to $a\cdot b$, if $\gcd(a,b)=1$.

Injectivity:

Assume there are two different $a,b\in \{0,...,m-1\}$, $a>b$, such that $f(a)=f(b)$. This means that

$$
a\cdot w \mod m = b\cdot w \mod m
$$
and
$$
a\cdot w=b\cdot w+k\cdot m
$$
for some integer $k>0$. We reorder to
$$
(a-b)\cdot w=k\cdot m
$$
Both sides of the equation are a multiple of $w$ and $m$. However, since $w$ and $m$ don't share any divisor, any common multiple is larger than $w\cdot m$. The left hand side of the equation clearly contradicts this fact. Hence, there are no such choices for $a$ and $b$, and $f$ is injective.

Surjectivity

This can be argued by counting. The function $f$ is total on the set $\{0,...,m-1\}$, and since $f$ is injective as shown above, $f$ is also surjective.


Decidability of a Turing machine which always halts in at most ten steps I have an exam coming up soon and I need help with this.  Consider the problem:

  Given a Turing machine $M$, determine if $M$ halts in at most ten steps on every input.

Is this decidable?  Prove your answer.

Consider the following hint:

If $M$ is a TM, and it is given an input of length $12$ (for example), but you only allow $M$ to operate for $10$ steps,
what can it do with the input?


Can we find size of total interval in O(N) Let's say we have given $N$ intervals in the form $[x, y]$, both $x,y$ are integers , we want to find the number of integers covered by at least one interval of all $N$ intervals,  (look in the example for better understand).

The intervals may or may not intersect.

Example: Let N = 3, and the intervals: $a_1 = [1, 5], a_2 = [3, 7], a_3=[5,7]$ The count of the integers is 7, because they cover the numbers: $1,2,3,4,5,6,7$

Is it possible to get such size in $O(N)$ time complexity

I tried to come up with solution but I think that we should sort the intervals in some way and then to search them in linear time, but I cannot think how should we make the search and how to sort them.

There is a simple $O(n\log n)$ algorithm based on sorting all the endpoints of the intervals. I will describe a more sophisticated algorithm, which outputs the union of the input intervals as a union of internally disjoint intervals (they may have overlapping endpoints). Denote the input intervals by $[s_i,t_i]$.

Initialize a variable $a$ to 0. This variable counts the number of active intervals.
Let $x$ go over the sorted order of the $s_i,t_i$:

If $x = s_i$ and $a = 0$, record $s_i$ as the starting point $s$ of the current interval.

If $x = s_i$ (regardless of $a$), increase $a$ by one.

If $x = t_i$, decrease $a$ by one. If now $a = 0$, output $[s,x]$.

It is not hard to modify this algorithm to output a union of truly disjoint intervals.

This algorithm runs in $O(n\log n)$, the running time being dominated by the cost of sorting the endpoints of the intervals. If the endpoints are integers and we can only access them using comparisons, then there is a simple $\Omega(n\log n)$ lower bound obtained by reduction from element uniqueness. Given a list of integers $x_1,\ldots,x_n$, form intervals $[3x_i,3x_i+1]$; I'll let you take it from here. This might look like cheating (since we assume that the endpoints are integers, and use arithmetic operations in the reduction), but it does rule out certain kinds of algorithms from achieving $o(n\log n)$ performance.


Error handling in a size_t hashfunction For school I have a big assignment on hashtables etc. One of the functions is a size_t function where we calculate the hash value. (Keep in mind the structure of every function is given so we are not allowed to change input variables/function types). However, the hash calculator function does need to handle errors, but I am stuck on what value to return when encountering errors. In my head: all positive numbers are also possible hash values, and all negative numbers can not be returned in a size_t function.

Thanks in advance

I have never seen anyone doing error handling in the calculation of a hash function.

For a hash table to work, items must be equatable and hashable. If they are not equatable then sorry, you lost. As long as you can detect that an item is “bad” for equatability, you can just make it compare different to any item other than itself. And make it produce a hash code if constant zero or any other constant.

If you have problems calculating a hash function then you have a bigger problem that you need to solve first.


Hash table where items can fall into multiple buckets. What's the name of the data scrtucture? I have a task to search through an array of items. I want to narrow the search down to some partitions. I thought of hash tables, but the difference in my case is that the "hash-function" is not unique; in my case, it rather should be called "partition-function".

Here's a fizz-buzz example:

[-1]:1,2,4,7,8,11,13,14,16
[3]:3,6,9,12,15
[5]:5,10,15

You see, 15 fell into two buckets. It's ok with me.
Since I'm going to look up "all who's divisible by 3" I'll get 15. Same for "all who's divisible by 5".

I see the following problems for the datastructure:

Data is duplicated (more space, it's ok with me)
Inserts/Updates/Deletions are more expensive

The question is:

Is this approach to partitioning a good one?

Whether it is a good approach or not entirely depends on the time/space requirements of your particular application. All data structures have trade-offs. Your primary alternatives for storing partitions of a multiset are:

Collection of containers/dictionaries: you can store each subset in a different container or dictionary (such as an array or a hash table). This will allow fast unions and intersections between specific subsets, but slow membership queries. This is probably the data structure that you are trying to implement.
Generalized bit vector: assuming that your universal set $U$ is not too big, you can define a two-dimensinal array. The $i$th element of this array will store the identifers of the subsets that contain $i$. Membership queries will be fast; however, unions/intersections take time proportional to $U$.
Dictionary with a subset attribute: you can store each distinct element of the multiset in a dictionary (e.g., a hash table); then, associate an attribute to each element. This attribute will record the identifiers of the subsets that contain the element. Membership queries can be performed in the time it takes to search in the dictionary; however, union/intersection operations are again slow.
Union-find: in this data structure, each subset is represented as a rooted tree that is made up of parent pointers. This idea is extremely useful since it enables membership queries and union of subsets in (nearly) constant time. It does not support, however, to split previously unioned subsets.

For more information about all of these choices, you can have a look at Section 12.5 of The Algorithm Design Manual [1].

[1] Steven S Skiena: The Algorithm Design Manual, Springer-Verlag London (2008).


How can k-means be reduced to Integer Programming The k-means algorithm reduces to computing the objective function:

$
\underset{\textbf{S}}{\operatorname{argmax}}  \sum_{i=1}^k \sum_{\textbf{x}_j\in\textbf{S}_i} \lVert \textbf{x}_j - \mathbf{\mu}_i \rVert
$

for some observations $\textbf{x}_1,\ldots\textbf{x}_n$ to be partitioned into sets $\textbf{S}_i$.

How can this problem be reduced to an Integer Programming problem, which like k-means, is NP-hard.

I'm not sure if you can reduce this problem to an Integer Problem, because the centers are still continuous variables. There are ways to write equivalent Mixed-Integer Problems (i.e., both integer and continuous variables) but I struggle to formulate as a Linear one because of the Euclidean norm.

First you create a boolean variable $w_{ij}$ for assignment. $w_{ij} = 1$ means observation j belongs to cluster i (and zero means it does not belong). The following constraint ensures that one sample can only belong to one group:
$$
\sum_i{w_{ij} = 1},  \forall i \in 1..k
$$

You also create non-negative continuous variables $d_{ij} \geq 0$ for distances between every observation j to every center, but use the Big M method to turn this distance zero if the observation does not belong to the cluster:
$$
d_{ij} \geq ||x_j - \mu_i|| - M(1 - w_{ij})
$$

To select a value of M you can find the distance between the two points that are furthest from each other, or any other bigger value. If M is big enough and j doesn't belong to i, we have $d_{ij} \geq L$ where L is negative, so the constraint is trivially satisfied - which means $d_{ij}$ can assume any value greater or equal to zero. If j does belong to i, then the minimum value for $d_{ij}$ is the euclidean distance between observation and cluster center.

(Note: you could use a multiplicative factor instead of Big M, like this: $
d_{ij} = ||x_j - \mu_i||w_{ij}$ - this is matematically accurate but generally doesn't work well in practice because it adds non-linearity. But since this norm is already non-linear, who knows?)

Now, if you minimize the distances (I saw in Wikipedia that the correct formulation tries to minimize the sum of distances), optimization will try to reduce every single value of $d_{ij}$, so they will clamp to the correct distances if j belongs to i, and to zero if j doesn not belong to i:

$$
\min{\sum_{ij}{d_{ij}}}
$$

I hope that helps.


"If any problem in NP is not polynomial-time solvable, then no NP-complete problem is polynomial-time solvable." This is given vertabim in my lecture slides and it seems like I'm having difficulty proving this statement mathematically. I know that P is a subset of NP and NP-Complete is also a subset of NP. But what else do we have to prove for this statement?

Assume that the following were true:

A problem $X$ in NP is proven to not to be able to be solved in polynomial time.
A NP-complete problem $Y$ is proven to be solved in polynomial time with algorithm $Z$.

However, since $Y$ is a NP-complete problem we can transform an instance $x$ of $X$ into an equivalent instance $y$ of $Y$ in polynomial time, and then solve it with $Z$ in polynomial time. The sum of two polynomial times is polynomial, thus our assumption is violated.


Pushdown Automaton for $L = \{ w_1 w_2 : |w_1| =|w_2| , w_1 \neq w_2 \} $ So i know that $L =$ { $ {w_1 w_2 : |w_1| =|w_2| , w_1 \neq w_2} $ }

is a CFL, but i cannot make a PDA for it because it doesn't make any sense to me why this is CFL

i even know the grammar for it but i cannot draw the PDA because :

even if we determine the middle of the string, if we push every word of w1 to the stack, then how can we compare it to w2 when we can only POP??? how is that even possible?

i mean how can i compare two strings and determine if they are the same if i can only compare the last word of first string to the first word of the second??!

also it would help me a lot to understand if you could say which of these are CFL and which are not :

$L_1 = \{ w_1 w_2 : |w_1| =|w_2| , w_1 = w_2 \} $

$L_2 = \{ w_1 w_2 : |w_1| \neq  |w_2| , w_1 \neq w_2 \} $

$L_3 = \{w_1 w_2 : |w_1| \neq |w_2| , w_1 = w_2 \} $

there was a post about this but nobody answered how can we construct such a PDA?
i don't want to just convert the grammar to PDA with algorithms, i want to understand how the PDA is comparing two strings?

PDA for { xy : |x| = |y|, x ≠ y} from its grammar, and intuition behind it

The three languages you ask about are not very interesting:

$L_1$ is famously not context-free; it's usually written as $\{ ww \mid w \in \Sigma^* \}$. Note that the condition $|w_1| = |w_2|$ is obsolete. Standard entry-level proof techniques work.
$L_2 = \Sigma^+$ since every word $w$ (except $\varepsilon$) can be split into $w_1 = \varepsilon$ and $w_2 = w$; hence it's regular.
$L_3 = \emptyset$ since the two conditions are contradictory; hence it's regular.

As you see, neither gives you any inside into $L$. The languages discussed here are more helpful in this regard.

As for an NPDA for $L$, the answer you link already mentions that there are algorithms to get you from a grammar to an automaton; check a proof that NPDAs and CFGs are equally powerful.

That said, an idea for constructing an automaton from scratch is the same as for the grammar, even though it's a little messier to implement. Let $w$ be the whole input word, and rename $(w_1,w_2)$ to $(u,v)$ to avoid syntax overload. Then:

Note that if $u \neq v$ with $|u| = |v|$, there must be $i$ so that $u_i \neq v_i$. And, importantly, if there is no such $i$ if $u=v$.
Non-deterministically guess two input indices $j, l$  to compare.
Non-deterministicaly guess the middle index $k$ of the input.
Use states to verify that $w_j \neq w_l$.
Use states to verify that $|w|$ is even.
Use the stack to verify that $k = |w|/2$.
Use the stack to verify that $j = l - k$.
Reject if any of the verifications fail.

The main trick left is how to use the stack for the two checks at once; I'll leave that as an exercise.
Proving that the resulting automaton is instructive about the nature of non-determinism.


Computing a boolean function with a small formula Suppose that $x = (x_1,\ldots,x_n)$ is a binary vector and $f(x)$ is a boolean function. Furthermore suppose  $y = (y_1,\ldots,y_m)$ is a binary vector and that $F(x,y)$ is a binary formula  of size $k.$ Here by size  I mean the number of leaves in $F.$

Suppose I have vectors $S = \{s_1,\ldots,s_n\}$ such that for any $x \in \{0,1\}^n$ there is a $s \in S$ such that we have $$ F(x,s) = f(x).$$

I need to prove that in this case I can express $f(x)$ as a boolean formula of size $O(n\cdot k).$

What would be the idea about this?

Since for every input $x$ we have an $s \in S$ one could encode the specific $s$ for every one of the $2^n$ possible inputs but this would give a too large formula.

Edit. The original text  as it appears in the book "Extremal combinatorics with applications to computer science 2ed."

Something has gone wrong in the way you applied Adleman's theorem: it has led you to try to prove something that isn't actually true.

The statement the book asks you to prove is true.  There is a good deterministic algorithm for $f$.  Adleman's theorem, applied properly, immediately gives you a good deterministic algorithm for $f$.  Just make sure you pick the definition of "good point" correctly.  Hint: A good point for $a$ is a value $y$ such that $F(a,y)=f(a)$.  What can you conclude about $f(a)$, if you observe a point $y$ such that $F(a,y)=1$?  Now an application of Adleman's theorem immediately leads to a simple deterministic algorithm for computing $f$ and a small boolean formula for $f$.  In particular, we get the following boolean formula for $f$:

$$f(x) = F(x,s_1) \lor F(x,s_2) \lor \dots \lor F(x,s_n).$$

Why does this work?  Well, if $f(x)=0$, then we're guaranteed that $F(x,y)=0$ for all $y$ (this comes directly from the exercise in your book), so in particular every term of the above disjunction is 0, so this formula gives the correct answer for $f(x)$.  On the other hand, if $f(x)=1$, then Adleman's theorem guarantees that there exists at least one $s_i \in S$ that's a good point for $x$, i.e., at least one $s_i$ such that $F(x,s_i)=f(x)=1$, which means that the above disjunction is 1, so this formula gives the correct answer for $f(x)$ in this case, too.

In contrast, the claim you're trying to prove isn't true.  Here's an explicit counterexample.  Let $F(x,s)=s$ (so $m=1$), $s_0=0$, $s_1=1$ (so $S=\{0,1,\dots\}$), and let $f$ be any function with no small formula.  Then it is easy to verify that for all $x$ there exists $s \in S$ such that $F(x,s)=f(x)$: in particular, you can take  $s=f(x)$.  Notice that we didn't use anything about $f$, so we were free to choose $f$ any way we want.  It is also easy to see that $F$ has a small formula, for this choice of $F$.  Therefore, this choice of $F,S,f$ satisfies all the preconditions of your claim.  However, (by assumption) $f$ doesn't have a small formula, so this is a counterexample for your claim.

There's a crucial difference between "there exists at least one $s$ for which (blah) is true" vs "(blah) is true for a large fraction of $s$".

I don't know how you got to your claim or what went wrong in your translation from the book's exercise to your claim, but I suspect you didn't apply Adleman's theorem quite right, or the way you applied it didn't give you strong enough conclusions/assumptions about the properties that $F$ has.


Looking for a paper comparing NLP methods with Data Mining techniques I've recently attended a conference, where one of the participants mentioned a recent paper published by a Google employee, which showed that using data mining techniques in application to NLP might sometimes give better results than using the NLP methods themselves.

That was the only description he gave and on top of that, he didn't remember author's name.

Is anyone familiar with such paper?

there are probably several papers which fit this criteria and this may not be enough info/ criteria to really narrow it down. however some general bkg: google has pioneered research into the use of statistical algorithms for NLP for years and particularly (somewhat more recently) machine auto language translation. in this research one has a large database (aka "big data") of "translated sentence pairs" between language A and language B and the machine learning algorithm attempts to learn the relationship between the two, and its considered something of a relatively recent paradigm shift in the field because previously it was not considered/ thought possible, but google has achieved very good and improving results in the area, and my understanding is that some of this is now used/ incorporated in their live/ production/ public "translate" feature/ "product" built into the main search engine results.

try this nice list of papers: Natural Language Processing listing most NLP papers/research at google by date. there are 8 papers with the word "statistical" in the title. the most recent paper from 2013 may be close to what is being identified or cite the nearby area your speaker was referring to. other papers are from 2012 or older.

One Billion Word Benchmark for Measuring Progress in Statistical Language Modeling / Ciprian Chelba, Tomas Mikolov, Mike Schuster, Qi Ge, Thorsten Brants, Phillipp Koehn, Tony Robinson
ArXiv, Google (2013)


Definition of the cyclic shift of a formal language? Wikipedia says, the context-free languages are closed under

  the cyclic shift of $L$ (the language $\{vu : uv \in L \}$)

So I am looking for the definition of the cyclic shift operation on formal languages.

From the quote, what are required on $u$ and $v$? Are they in $L$, or in $alphabet(L)^*$? Thanks.

The cyclic shift of a language $L$ consists of all cyclic shifts of the words in $L$. Instead of defining the cyclic shift formally, let me give an example. The following are all cyclic shifts of the word monkey:

monkey onkeym nkeymo keymon eymonk ymonke

To see the connection with the definition, consider nkeymo. If we write monkey as mo concatenated with nkey and then switch both parts, we get nkeymo. This corresponds to setting u=mo and v=nkey in the definition above.

To answer your concrete question, $u,v \in \Sigma^*$. (The alphabet is usually denoted by $\Sigma$.)


Upper bound of algorithm with flooring Would much appreciate someone explaining how they managed to get to the upper bound of this algorithm.
$$T(n) = 2T(\lfloor \sqrt n\rfloor) + ln (n)$$
$$T(1) = 0$$
Solution is given as:
$$T(n) = O(logn*log(log(n)))$$

If a number is of the form $n = 2^{2^k}$ then you never encounter the floor as you open up the recursion, and then there is no problem. If you're interested in a general upper bound, you can prove by induction that $T(n)$ is monotone in $n$: if $n \leq m$ then $T(n) \leq T(m)$. Now given $n$, find some $m \leq n^2$ which is of the form $2^{2^k}$, and then
$$ T(n) \leq T(m) = O(\log m \log\log m) = O(\log n \log\log n). $$


Efficient search algorithm for a monotonic boolean array wherein the probability of target's location is available apriori A boolean-valued monotonic function is defined in the set of positive integers, $\mathcal Z$.

$$f(n) = \begin{cases} 0, &n_{min}\le n < n\ast\\1, &n\ast\le n\le n_{max} \end{cases} ; n \in \mathcal Z $$

The goal is to search for $n\ast$. The bounds $n_{min}$ and $n_{max}$ are known apriori.

A salient property of $n\ast$ is that it has a higher probability of lying in a region around $\hat{n}$ (known apriori). The exact probability distribution, although unknown, (probably doesn't matter) can be considered as continuous CDF having a higher weighting factor around $\hat{n}$

I have already implemented a simple binary search, but I am looking for more efficient solutions that somehow account for the given probability information (i.e. $n\ast$ is concentrated around $\hat{n}$), I am looking for an efficient algorithm to find $n\ast$.  without losing accuracy.

I know that Binary search is worst-case $\mathcal{O}(log\ n)$, but $f(n)$ is so computationally expensive that I can't afford even this.

If you knew the distribution of $n^*$, you could find an optimal binary decision tree (there are several $O(n\log n)$ algorithms) in terms of expected number of queries (you can't beat binary search if you care about worst case). There are also two simple algorithms which are nearly optimal. I will describe them as algorithms for locating $n^*$ given queries of the form "$n^* \leq x$", which you can easily implement by checking $f(x)$. We assume that the probability that $n^* = i$ is $p_i$.

Gilbert–Moore algorithm: Partition the unit interval $[0,1]$ into intervals of length $p_i$, and let $x_i$ be the midpoint of the $i$th interval. We locate $n^*$ by doing binary search on $[0,1]$. For an interval $I \subseteq [0,1]$, denote by $X(I)$ the midpoints $x_i$ which are found in $I$. We first ask whether $n^* \in X([0,1/2])$. Depending on the answer, we ask whether $n^* \in X([0,1/4])$ or whether $n^* \in X([1/2,3/4])$; and so on. Eventually we reach an interval $I$ such that $X(I)$ is a singleton, and we have found $n^*$.

Horibe's algorithm: Find $x$ that minimizes $|\Pr[n^* \leq x] - 1/2|$, and ask whether $n^* \leq x$. Denote by $I$ the values of $n^*$ conforming to the answer. Find $x$ that minimizes $|\Pr[n^* \leq x \mid n^* \in I] - 1/2|$, and ask whether $n^* \leq x$. Update $I$, and repeat until $I$ becomes a singleton.

Both algorithms find $n^*$ using at most $H(n^*)+2$ queries on average (where $H(n^*)$ is the entropy of $n^*$), compared to the trivial lower bound $H(n^*)$, so they're pretty good.

In your case, you don't know the distribution of $n^*$, but you can make a guess, use one of these algorithms, and hope for the best. If you have several distributions in mind, you can choose one of them to construct an algorithm, and then check their performance on the other distributions, comparing the expected number of queries to the trivial lower bound.

You could also want to optimize some other quantity – for example, the 99th percentile of the number of queries. In that case the algorithms described above will probably still be pretty reasonable.


Is following grammar LR(0)? I know how to verify whether grammar is LR(0) or not. But this particular case is little tricky and hence the question.

  Grammar:

  $SL \rightarrow SL ; S \space | \space \epsilon$

  $S \rightarrow s$

  (Note: $SL$ is single non-terminal.)

Now, LR(0) automaton for this grammar is as follow:

Now my question is whether to consider entry $start \rightarrow SL.$ in $State_1$ as SR conflict.

Because I previously came to know that we don't consider conflicts due to augmented production.

Thanks.

You haven't actually augmented the grammar. The augmented grammar has the production $$start\to SL\;\$$$

With that change, state 1 is not a reduction state and there is no conflict.

If you did not intend to augment the grammar, then it is not $LR(0)$, because the language does not have the prefix property. But that's not very useful, so normally we augment grammars, turning the language $L$ into $L\$$, where $\$$ is a symbol not in the the alphabet for $L$. Clearly the augmented language has the prefix property.

There's a reasonable explanation with references on Wikipedia.


How to find the maximal set of elements $S$ of an array such that every element in $S$ is greater than or equal to the cardinality of $S$? I have an algorithmic problem.

Given an array (or a set) $T$ of $n$ nonnegative integers. Find the maximal set $S$ of $T$ such that for all $a\in S$, $a\geqslant |S|$.

For example:

If $T$=[1, 3, 4, 1, 3, 6], then $S$ can be [3, 3, 6] or [3, 4, 6] or [4, 3, 6].
In $T$=[7, 5, 1, 1, 7, 4], then $S$ is [7, 5, 7, 4].

I have tried this recursive function.

function(T):
    if minimum(T) >= length(T):
        return T
    else:
        return function(T\minimum(T))

Is there any non-recursive algorithm. (I did not check my recursive algorithm, so it could has some flaw.)

Sort T. Then take elements while T[i] >= i+1.

For example sorted(T)=[6,4,3,3,1,1]. Then, T[0] = 6 > 1, T[1] = 4 > 2, T[2] = 3 <= 3 and finally, T[3] = 3 < 4 so we have S = [T[0], T[1], T[2]].


Confusion in Turings proof of the undecidability of the Entscheidungsproblem I was reading Turing's paper on computable numbers and the Entscheidungsproblem. There is this part of Section 9, Part II that I cannot quite seem to understand. He says:

It is pretty straight forward until the part where he introduces $\mathfrak{U}$. So $\mathfrak{U}$, he says, includes the Peano axioms; but what else does it include? I guess it includes the axioms for $G(x)$ as well, because only then would $\mathfrak{U}$ be able to "define" the sequence $\alpha$ that is being computed by $G(x)$. I am taking the word "define" here in its usual sense, but Turing explains what he means by "$\mathfrak{U}$ defining $\alpha$" as:

So for $\mathfrak{U}$ to define $\alpha$, $-\mathfrak{U}$ must not be provable? I am not sure why that is required? Because by restricting that $-\mathfrak{U}$ must not be provable we are saying that $\mathfrak{U}$ must not be refutable, which means that the sequence $\alpha$ cannot be all 0's (or so I think). But why would we want $\alpha$ to not be all 0's?
I am also confused about the two formulas ($A_n$ and $B_n$) he has written above. I am not sure why if has included the $F^{(n)}$ part. If $x$ satisfies the Peano axioms and the axioms of $G(x)$, then $U$ being a conjection of all these axioms is given to be TRUE, and if $x$ does not satisfy these axioms then $\mathfrak{U}$ is obviously FALSE. So, just based on $\mathfrak{U}$ we can tell whether $A_n$ is TRUE or $B_n$. So what is the point of $F^{(n)}$ here? I think the following set of implications say pretty much the same thing as what Turing has?

Sorry if I am overlooking something here.
Edit 1:
Here are the footnotes:

The transliteration of the passage into modern langauge would go as follows.
We extend the language of first-order Peano arithmetic with a unary predicate $G$ (and no axioms for $G$).
For a number $n \in \mathbb{N}$, let $\overline{n}$ be the numeral
$$\underbrace{S(S(\cdots S}_{n}(0)))$$
where $S$ is the successor symbol. For example, $\overline{3} = S(S(S(0))$.
Consider a formula $\mathfrak{U}(x)$ written in this language, whose only free variable is $x$ such that, for every $n \in \mathbb{N}$:

Peano axioms prove $\mathfrak{U}(\overline{n}) \Rightarrow G(\overline{n})$, or
Peano axioms prove $\mathfrak{U}(\overline{n}) \Rightarrow \lnot G(\overline{n})$.
Peano axioms do not prove $\lnot \mathfrak{U}(\overline{n})$.

Define $\alpha : \mathbb{N} \to \{0,1\}$ by
$$\alpha(n) =
\begin{cases}
1 & \text{if Peano axioms prove $\mathfrak{U}(\overline{n}) \Rightarrow G(\overline{n})$},\\
0 & \text{if Peano axioms prove $\mathfrak{U}(\overline{n}) \Rightarrow \lnot G(\overline{n})$.}
\end{cases}
$$
We say that $\mathfrak{U}$ defines the sequence $\alpha$.
Intuitively, we think of $G(x)$ as stating "the $x$-th digit of $\alpha$ is $1$", and of $\lnot G(x)$ as stating "the $x$-th digits of $\alpha$ is $0$".
The first and second condition on $\mathfrak{U}$ ensure that $\mathfrak{U}$ always assigns $\alpha(n)$ the value $0$ or the value $1$.
The third condition ensures that $\mathfrak{U}$ never assigns both $0$ and $1$ to $\alpha(n)$ (because it follows from the first two conditions that $\lnot \mathfrak{U}(\overline{n})$ is equiprovable with $G(\overline{n}) \land \lnot G(\overline{n})$).
Example: The formula $G(x)$ defines the sequence $1, 1, 1, 1, 1, \ldots$.
Example: The formula $G(S(x))$ does not define a sequence because $G(S(0)))$ does not imply $G(0)$ and it does not imply $\lnot G(0)$. (Remember that $G$ is a primitive symbol and that we have no axioms about it.)
Example: The formula $G(0) \land \forall x \,.\, \lnot G(S(x))$ defines the sequence $1, 0, 0, 0, 0, \ldots$
Example: The formula $x \neq 0 \land \Rightarrow G(x)$ does not define the sequence because Peano axioms prove $\lnot (0 \neq 0 \land G(0)$, thus the third condition is violated. If we tried to use this formula to define a sequence, it would assign $0$ and $1$ to $\alpha(0)$ (and it would assign $1$ to all other terms of $\alpha$).
Example: The formula $G(0) \land \lnot G(S(0)) \land \forall x . G(S(S(x)))$ defines the sequence $1, 0, 1, 1, 1, 1, \ldots$
Example: The formula
$$((\exists y . x = 2 \cdot y) \Rightarrow G(x)) \land
  ((\exists y . x = S(2 \cdot y)) \Rightarrow \lnot G(x))
$$
defines the sequence $0, 1, 0, 1, 0, 1, \ldots$


Understanding the closed form derivation on the function f(n/3) + n^2 +3 I have the function:

$$ f(n) =
\begin {cases}
4 & , n = 1 \\
f(\frac{n}{3}) + n^2 -3 & , n \ge2
\end {cases}
$$

The given solutions shows the unwinding of the function as follows:

Assuming $ n \ge 2$

$$f(n) = f\bigg(\frac{n}{3}\bigg) + n^2 - 3$$
$$ = \bigg[f\bigg(\frac{n}{3}\bigg) + \bigg(\frac{n}{3}\bigg)^2 -3\bigg] + n^2 -3$$
$$ = f\bigg(\frac{n}{3^2}\bigg) + n^2 \bigg(\frac{1}{9} + 1\bigg) -6$$
$$ = \bigg[f\bigg(\frac{n}{3^3}\bigg) + \bigg(\frac{n}{3}\bigg)^3 -3\bigg] + n^2\bigg(\frac{1}{9} + 1\bigg) -6$$
$$ = f\bigg(\frac{n}{3^3}\bigg) + n^2 \bigg(\frac{1}{81} + \frac{1}{9} + 1\bigg) -6$$

Where I get lost are the last two lines of the unwinding because I do not understand where the $(\frac{n}{3})^3$ becomes to $n^2(\frac{1}{81} + \frac{1}{9} + 1)$.

Question is taken from UofT CSC236 Tutorial 6

The real question is where $\left(\frac{n}{3}\right)^3$ comes form. If you look at the formula, you see that it really should have been $\left(\frac{n}{3^2}\right)^2$.

The morale here is that people make mistakes. Calculations you see in tutorial, in lecture notes, and even in textbooks, are not infallible. When something seems to be amiss, try to understand what calculation is being done, and then try to reproduce it on your own. The mistake may disappear, as in this case, or may persist, in which case there might be a more serious issue in the mathematical development; unfortunately, this also sometimes happens. We are only humans, after all.


Repeated point in polygon: preprocessing complexity given logarithmic query time? I am interested in the repeated point in polygon problem, where one is given a polygon in a preprocessing phase and in the online phase, one is asked whether a point is in that polygon. The polygon is not necessarily simple. I am interested in the case where a polygon has many edges.

Let $n$ be the number of vertices of the polygon. I have an algorithm that performs the online phase in $O(\log n)$ time but the preprocessing phase requires $O(n^3)$ time and space in general, $O(n^2)$ time and space for simple polygons, and $O(n)$ time for star-shaped polygons.

Can we do better? Specifically, does anyone know lower or upper bounds, constructive or not, for the preprocessing phase given $O(\log n)$ query time?

I'm working in two dimensions, and the points have floating point coordinates (i.e., not integer coordinates).

My algorithm is similar to a standard algorithm and has similar performance characteristics. I discovered it independently so it differs in some immaterial ways but it's not original. It works as follows:

Preprocessing:

Translate polygon into first quadrant. (This is to simplify later calculations but isn't strictly necessary.)
Create a ray passing from the origin through every endpoint and intersection point of an edge. In each resulting cone no edge crosses another.
For each cone, sort the edges crossing that cone by their distance from the origin.

Online:

Apply the same translation to the query point as was applied to the polygon.
Using binary search, find the cone containing the point, or if none, return false.
Using binary search, find the number of edges in the point's cone for which the point and origin are on the same side. Return whether this number is odd.

Your problem is a special case of planar point location. The algorithm/data structure you found by Snarak and Tarjan can answer point location (and thus point in polygon) queries in $O(\log n)$ time using $O(n \log n)$ preprocessing and $O(n)$ space. That is optimal. There are two other data structures that achieve this: a data structure by Kirkpatrick and a randomized incremental approach. The randomized incremental approach can be improved to $O(n \log^* n)$ expected preprocessing time in case of a simple polygon, and is fairly simple besides.


Minimum Spanning Tree over Vertices Proof This is the problem:

$d_{T}(v)$ denotes the degree of a vertex in a spanning tree $T$ and $w: V \rightarrow R^+$ is a weight function defined on vertices.

The goal is an algorithm that finds a spanning tree which minimizes the value $\sum_{v \in V}{d_{T}(v)*w(v)}$.

My idea is to define a new weight function on edges in the following way: $m(e_{ij})=w(v_i)+w(v_j)$, i.e. the weight of each edge is the weight of both of its vertices.

Then we run Kruskal on a graph with the given $m$ weight function. The problem is that I have no idea how to prove that it works.

I thought about starting with the expression $min \sum_{e \in E}{m(e)}$ which Kruskal yields, and then somehow change the summation to be over vertices. How can it be done?

Thanks!

It doesn't matter which minimum spanning tree algorithm you use. All you need to notice is that for a tree $T$,
$$
\begin{align*}
\sum_{(i,j) \in T} m(e_{ij}) &= \sum_{(i,j) \in T} w(v_i) + w(v_j) \\ &=
\sum_i \sum_{(i,j) \in T} w(v_i) + \sum_j \sum_{(i,j) \in T} w(v_j) \\ &=
2 \sum_i d_T(i) w(v_i).
\end{align*}
$$
You take it from here.


Shortest non intersecting path for a graph embedded in a euclidean plane (2D) What algorithm would you use to find the shortest path of a graph, which is embedded in an euclidean plane, such that the path should not contain any self-intersections (in the embedding)?

For example, in the graph below, you want to go from $(0,0) \rightarrow (-3,2)$. Normally, an algorithm like Dijkstra's algorithm would produce a sequence like:

$$\left[ (0,0) \stackrel {3}{\rightarrow} (0,3) \stackrel{\sqrt{2}}{\rightarrow} (1,2) \stackrel{4}{\rightarrow} (-3,2) \right] = 7+\sqrt{2}.$$

Full graph:

Shortest path:

Shortest non-intersecting path:

However, this path intersects itself on the euclidean plane, therefore I want an algorithm that would give me the shortest non-intersecting sequence, in this case:

$$\left[(0,0) \stackrel{3}{\rightarrow} (0,3) \stackrel{3}{\rightarrow} (0,6) \stackrel{5}{\rightarrow} (-3,2) \right] = 11.$$

This path is longer than the shortest path, but it is the shortest non-intersecting path.

Is there an (efficient) algorithm that can do this?

TikZ sources

Full graph.
Shortest path.
Shortest non-intersecting path.

It is NP-complete to even decide whether any path exists.

It is clearly possible to verify any given path is a valid path in the given graph. Thus the bounded-length problem is in NP, and so is its subset, the any-path problem.

Now, to prove NP-hardness of the any-path problem (and thus of the bounded-length problem), let's reduce SAT-CNF to this problem:

The global structure is a grid of wire pieces adjoined by a column of clause pieces. Logic formula is satisfiable iff there exists a non-intersecting path through the graph.

It is impossible to cross two pieces of the path, but it is neccessary to cross two logic wires. Rather, the path flow is strictly given: a wire point is given by two nodes. The sequence of the wire points through which the path passes is forced by the reduction. Logic is represented by which node is chosen. Any path can be chosen as long as it passes through all wire points.

In this diagram, the path is represented by the red curve and the logic flow is represented by the black wires:

Now let's build each component.

Wiring uses three tiles: the crossing, the branch point, and the vertical wire. Let's start with the hardest one:

The basic idea behind the crossing is to prepare a path for each pair of wire points and bend the possible paths enough so that all pairs except those that encode the same logic (compatible paths) cross each other. Of course we can't just say two parallel edges intersect, but we can introduce extra order-2 nodes to make two paths intersect.

Supposing the paths come from north to west and from south to east, we can: collect each path from north with its compatible path from east on a line (some incompatible paths will cross each other); cross each pair with each other by reversing the order of pairs; distribute the paths to their south and west endpoints. This is best explained by a diagram. Here, each pair of nodes represents a wire point. Paths with the same color code (carrying the same logic) don't intersect, paths a different color code do:

The branch point and the vertical wire work the same, but there are fewer paths to correlate:

The clause box follows the same logic: each literal exposes one of its paths to the reading wire, then converging to the south (if it's the northernmost term or the term to the north converges to the north) or to the north (if the term to the north converges to the south). The reading wire (one node at the endpoints) branches to become one path per literal. Each reading path then crosses the literal's true-path if the literal is negated, the false-path if it is not. Note that the converged path may or may not cross a clause boundary. For consistency, here's a diagram for $\neg A \vee \neg B$:

It is possible to generalise this reduction to encode an arbitrary tree of AND and OR gates by branching the reading wire in different way. In particular, SAT-CNF and SAT-DNF are both possible to reduce to the non-intersecting path problem in the way described as above.


Amortized Analysis for Addition of $n$ numbers How can we add n positive integers with binary expansion $l_1$, $l_2$,...$l_n$ bits so that the total complexity is $O (\sum l_i)$ for $i = {1,...,n}$ ? More importantly, how can show this complexity using amortized analysis (the potential method)?

I know the elementary school addition of 2 numbers of length $s$ and $r$ is $O(r+s)$ and hence, the addition of n integers is $O(\sum l_i)$. However, what potential function would you use to prove that bound? I don't seem to have any intuition on that... Maybe use a function similar to the standard binary counter example (number of 1's in the binary representation of the number)..?

You should be slightly more careful in your argument. Let the actual numbers you are adding be $x_1,\ldots,x_n > 0$, where $\ell_i = \lfloor \log_2 x_i \rfloor + 1$. The complexity of adding two numbers $x,y>0$ is $O(\log(x+y))$. In our case, assuming we are doing the addition sequentially, the numbers we are adding are $x_i$ and $x_1 + \cdots + x_{i-1}$, for $i=2,\ldots,n$. Therefore the entire complexity is
$$ O\big(\sum_{i=2}^n \log (x_1 + \cdots + x_i)\big). $$
Suppose now that we arrange the numbers in non-decreasing order $x_1 \leq x_2 \leq \cdots \leq x_n$. Then
$$
\sum_{i=2}^n \log (x_1 + \cdots + x_i) \leq \sum_{i=2}^n \log (ix_i) \leq n\log n + \ell_1 + \cdots + \ell_n.
$$
This is tight (up to constant factors) when all $\ell_i$ are equal. In particular, when adding $1$ to itself in this fashion, the complexity is $O(n\log n)$ rather than $O(n)$.

Can you think of a better way?


How to use a logistic regression classifier to estimate the confidence of a rule? The following is an excerpt from the Estimating LAT Confidence section of this paper:

  ... Since some LAT detection rules are more reliable than others, we
  would like to have a confidence value in each LAT that can be used to
  weight each LAT appropriately during answer scoring. To accomplish
  this, we trained a logistic regression classifier using a manually
  annotated gold standard. The classifier uses the focus and LAT rules
  that have fired as features, along with other features from the parse,
  NER, and the prior probability of a particular word being a LAT...

It's not clear to me what is the target variable of the logistic regression classifier. It sounds to me that it is binary variable indicating whether the fired rule was correct (1) or incorrect (0). Therefore, the prediction of the logistic regression classifier is the probability that the word is an LAT given that a certain rule has been hired (and some other features). Does this application of the logistic regression classifier make sense?

The details of the paper are as follows:

A. Lally et al., "Question analysis: How Watson reads a clue," in IBM Journal of Research and Development, vol. 56, no. 3.4, pp. 2:1-2:14, May-June 2012.
doi: 10.1147/JRD.2012.2184637

From context, I'd guess that the logistic regression classifier is used to predict the probability that a particular word is a LAT.  This looks equivalent to predicting the probability that the fired rule was correct to flag that word as a LAT.  This seems to make sense given the context.


Tree decomposition - Fastest algorithm in practise I'm looking for a fast in practice algorithm for calculating the (preferable optimized) tree decomposition of a graph.

I found the paper "A linear time algorithm for finding tree-decompositions of small treewidth" [1] by Hans L. Bodlaender which return a tree-decompsiton with the  optimized tree-width and as the name says, the algorithm runs in linear time but since there are no (translation: I have not found ) any implementations, I am not sure if it's being used in practice or not.

Is the paper by Hans L. used in practice or does the constant factor make the algorithm useless?

[1] http://dl.acm.org/citation.cfm?id=167161

[2] http://www.treewidth.com/docs/libtw.pdf

Edit:
Linked
https://math.stackexchange.com/questions/1246421/tree-decomposition-by-hand-for-understanding

The first caveat is that deciding whether the treewidth of a graph is at most $t$ is NP-complete, but it is FPT (which is what Bodlaender's paper shows). So for small $t$, we can (in principle) solve the problem exactly (and actually spit out the decomposition as well), but for graphs with large treewidth, then things can get a bit slow.

Having said that, you're right, the hidden constants in Bodlaender's algorithm are prohibitive, but there are more practical ways of getting at least a good tree decomposition. A useful place to start is with another of Bodlaender's papers, "A tourist guide to treewidth", which is now a bit old, but still has some valuable information and references to algorithms for generating tree decompositions, particularly in various restricted graph classes (sometimes the algorithms work in general, you just don't get a nice upper bound on the running time outside of the restricted class). John Fouhy's master's thesis "Computational experiments on graph width metrics" includes a number of way of obtaining tree decompositions (you can find it here under the link "John's thesis").

Probably most useful though is if you can get a copy of Downey and Fellow's new book "Fundamentals of Parameterized Complexity" (Springer, 2013), in which they devote Chapter 11 to heuristics for finding tree decompositions. This is probably the most recent survey in covering this material. They also note that the handful of attempts at implementing Bodlaender's algorithm have not been successful because it was impractically slow, so your lack of success in finding implementations is no coincidence. Bodlaender's algorithm works via recursive application of an FPT algorithm, the problem being that the recursion depth depends on the treewidth, (checking Downey & Fellows, the recursive depth is $O(t^8)$) which just becomes too prohibitively slow too quickly.


What is the earliest use of the "this" keyword in any programming language? I understand the this (or self or Me) is used to refer to the current object, and that it is a feature of object-oriented programming languages. The earliest language I could find which has such a concept was Smalltalk, which uses self but was wondering where and when (which programming language) the concept was first implemented?

Simula 67 is generally considered the first object-oriented language and predates Smalltalk by a number of years.

It also used the this keyword for the same concept, which can be seen in this book chapter extract:

  class Linker;
  begin
     ref(Linker) Next, Sex, Employment;
     text ID;

     procedure Add_to_List(LHead); name LHead; ref(Linker) LHead;
     begin
        Next :- LHead;
        LHead :- this Linker
     end..of..Add..to..List;

     procedure Onto_Lists(Gender,Occupation);
         name Gender,Occupation;
         ref(Linker) Gender,Occupation;
     begin
        Sex :- Gender;
        Employment :- Occupation;
        Gender :- Occupation :- this Linker
     end..of..Onto..Lists;

     InImage;
     ID :- Copy(SysIn.Image);
     InImage;
  end--of--Linker;


Construct context-free grammars that generate for the languages L(G) = {01(110)^n 10 (11)^n : n >= 0} I have given this question as home assignment. I tried a lot to solve it but couldn't found any solution. Please help
Thanks in Advance!

Hint, the grammar $S \to a S c \mid b$ generates the language $\{a^n b c^n : n \geq 0\}$. Can you you adapt this? Do you understand why it generates that language?


How to logarithmic interpolation? I'm trying to interpolate a logarithmic function but it always reaches a singularity due to $\log(0)$ being $-\infty$

is there a correct way to interpolate logarithmic functions? (as in correct parameters)

What i'm currently going for is

$y=a+b \log(cx)$

with initial values

$a=0$,
$b=1$,
$c=0$

The general fitting formula for pretty much any function is $F(x)=a*x+b$

so if you have a function inside a function it would be $F(G(x))=a*G(c*x+d)+b$ by virtue of substitution.

You made a tiny error. Instead of $y=a+b \log(cx)$ you probably want $y=a+b \log(cx + d)$

try to fit your function again. a multiplier should never equal to zero, because that would imply you don't have a function of $x$.