Addressing mode in 8086 I'm a beginner learning about Assembly language and I was doing questions where I have to identify different addressing mode in 8086 processor.
One such instruction is:
mov ah,09h
Here the source operand has immediate address mode and destination operand has Register address mode.
In many tutorials online they have just mentioned that the instruction has only Immediate addressing mode, I don't understand why these tutorials do not mentioned about the destination addressing mode.
Shouldn't the answer be both immediate and register addressing mode for the given instruction.
I know it is a very simple question but every other explanation on the internet is making me more confused. I would really like to know if my reasoning is correct.

Well, x86 hasn't the simplest instruction format... And similar addressing modes can be named differently for different CPUs.
In most CPUs (particularly RISCs and simple 8bits CPUs), there is only zero or one memory operation for data, so each instruction can be binned in one addressing mode or another.
For CISC CPUs it can be a bit more complex, for example x86 supports writing an immediate value to memory without going through a register.
Intel manuals don't really name the addressing mode for each instruction, because it's too complex, there are instead acronyms to describe operands such as imm8,imm16,r/m8,r/m16...
So your "MOV AH,0x09h" is probably "immediate" addressing, Intel describes it as "MOV r8,imm8" : 8bit register as destination to 8bit immediate.


Does O(1) communication complexity imply that a language is regular? Let's say that we have a function $g(i,j)$, which is an arbitrary boolean-valued function over $i,j \in \{a,b\}^*$, such that $|i| = |j| = m.$ Moreover, we can also say that $g$ has communication complexity $c(m),$ and we let $L = \{ij \mid g(i,j) = 1\}.$
Would it be accurate to say that if $c(m) = O(1),$ then $L$ is regular? I'm not entirely sure that this is the case. I've been trying to think about counterexamples to this statement, but I can't really think of any. I do know that the converse is true, namely that if $L$ is regular, then $c(m) = O(1)$. I've been racking my brain over this in the past few days. Any ideas?

No.  Let $L_0$ be a context-free language, say the language of matched parentheses, $L_1 = \Sigma^* \setminus L_0$, and
$$L = \{ij \mid b \in \{0,1\}, i \in L_b, j \in L_b, |i|=|j|\}.$$
Then $L$ is not regular, but it has communication complexity $O(1)$.


Change in Training Accuracy I am solving a problem in the Kaggle learn section : https://www.kaggle.com/c/facial-keypoints-detection

The problem involves detecting facial keypoints in a 96x96 image, some 30 features are detected. It is a supervised dataset.

I am using a convolutional neural network with max pooling, 2 convolutional layers and 2 max pooled layers, and one fully connected layer.

The problem uses the rmse metric for scoring.
So i used an ADAM optimizer to minimize the rms loss.

CASE 1:

I just simply trained the model, i got an average training rms error of 11.2, and finally when the output is generated I clamp the values which are greater than 96 (It's a 96x96 image) to 96, i get a test rms error of 9.1.

CASE 2:

I train the model itself with the clamped output values, i.e any output of greater than 96 gets clamped to 96 while training.

I thought CASE 2 would lead to faster and better convergence.
I used the same hyper-parameters for CASE 2 and found that it is converging more slowly and gives a very high rms error of around 180.

Can anyone explain what is happening?

The problem with your second approach (Case 2) is that the neural network might decide to output very large numbers for keypoints near or on the edge.  If it does, the loss function won't do anything to discourage it from doing that.

For instance, suppose the keypoint is at (30,94) for one instance in the training set.  Then outputting (30,1000) has the same penalty as (30,96).  So a network might just learn to output (30,96), and then start increasing the second coordinate (it learns (30,97), then (30,98), etc.) -- there's no penalty for that.

In particular, suppose that at some point the network is outputting (30,96) on that instance, and suppose the gradients encourage increasing the 96 a little bit.  Then in the next iterations the weights will be adjusted so it outputs (30,97).  Because the output is clamped before applying the loss function, (30,97) will receive the same penalty as (30,96).  Also it will have the same gradient.  Thus the learning process will continue adjusting the weights to cause the second coordinate to keep increasing forever.

This causes learning to fail to converge, or to converge very slowly.  And if learning fails to converge, it's plausible that overall rms error (including on other instances where this issue doesn't arise) might be very bad.


Use complementary slackness to prove the LP formulation of max-flow only need polynomial number of path constraints This is a homework problem for a class that ended 2 years ago, I'm learning it by myself.

Consider a directed graph $D=(V,A)$, $s,t\in V$. $A=\{a_1,\ldots,a_n\}$. Let $P=\{p_1,\ldots,p_m\}$ be the set of all simple paths from $s$ to $t$, There is a capacity function $c:A\to \mathbb{R}^+$. First we are asked to express max s-t flow as a linear program letting each path $p_j$ in $P$ associated with the variable $x_j$, there could be a exponential number of variables.

The formulation,
$$
\begin{align}
\text{Maximize:} & \sum_{j}x_j\\
\text{subject to:} & \sum_{a_i \in p_j}{x_j} \leq c(a_i) &\text{ for } 1 \le i \le n, \\
& x_j\geq 0 &\text{ for } 1 \leq j \leq m\\
\end{align}
$$

The dual is therefore:
$$
\begin{align}
\text{Minimize:} & \sum_{i} c(a_i) y_i\\
\text{subject to:} & \sum_{a_i\in p_j} y_i \geq 1 &\text{ for } 1 \le j \le m, \\
& y_i\geq 0 &\text{ for } 1 \leq i \leq n\\
\end{align}
$$

Assuming we have an optimal solution for the dual, the problem ask us to use complementary slackness to show there exist a formulation of the primal with only a polynomial number of paths, which also obtain an optimal solution. How is this done?

One way which comes to mind is to use the fact that if $\sum_{a_i \in p_j} y_i > 1$ for some $j \in [m]$ then $x_j = 0$ and so the path $p_j$ is irrelevant. However, consider a graph with exponentially many paths in which the source has capacity 1 and all other vertices have capacity 2. The optimal solution is 1 and it is obtained by $y_s = 1$ and $y_v = 0$ for all $v \neq s$, and so all the inequalities considered above are tight. (For a "generic" graph, however, we can expect the optimal solution to be obtained at a vertex, and so have at most $n$ tight constraints.)

Another way is to notice that if the primal has an optimal solution then it has one which is a vertex, and so has at least $m$ tight inequalities. At least $m-n$ of them are of the type $x_j \geq 0$, and so there is an optimal solution using at most $n$ paths. However this is not helpful in the context of the exercise.


Determine if there's a $P_3$ as an induced subgraph in a graph $G$ Given a graph $G$ on $n$ vertices with $m$ edges, show an algorithm that determines if there's a $P_3$ as an induced subgraph in $G$ in $O(m+n)$ time. ($P_3$ is the path on 3 vertices).

What I was thinking at first is that any vertex $v$ that has at least two neighbors could indicate a $P_3$ but it wouldn't be induced since these two neighbors might be connected. So that would mean I would have to iterate over all pairs of neighbors of every vertex to determine if they're connected and I would exceed the requested runtime. Plus, that way I would actually be able to not only tell if there's a $P_3$ but also find it, which kinda tells me this isn't what I should be doing.
Any suggestions? Or hints?

Without loss of generality, we can assume that the graph is connected and contains at least three vertices. If the graph is a clique, it doesn't contain an induced $P_3$. What happens if it is not a clique?


Question about the difference between radix trees and patricia trees I've already done some research on this topic, but it still isn't quite clear to me.

According to this post patricia trees are radix trees with $r = 2$. Every patricia tree I've seen so far is used to store alphanumeric symbols. Assuming that there are used 8 bits to represent one symbol, $r$ is the number of bits compared and the radix of a radix tree is $2^r$ shouldn't the radix of a patricia tree be $2^8 = 256$?

If you have a look at a PATRICIA Tree with the following inputs (in this order):

smile
smiled
smiles

According to the linked post a Patricia tree should then look like this:

smile - - - smiled - - - smiles

But intuitively (by the alphanumeric representation) it should look like this

       d
      /
smile
      \
       s

Quoting Wikipedia:

  PATRICIA trees are radix trees with radix equals 2, which means that each bit of the key is compared individually and each node is a two-way (i.e., left versus right) branch.

According to Wikipedia, Patricia is just a "brand name" coined by Donald R. Morrison, standing for Practical Algorithm To Retrieve Information Coded In Alphanumeric.

Patricia trees thus accept their input in the form of binary strings. If the input is a word, then it is first encoded in binary.

As for the smile/smiled/smiles example, it is explained in the linked post – each of these words is encoded as a binary string, and this is what the Patricia tree sees. It is completely unaware of the semantic interpretation of the bitstring as an alphanumeric word.


Enumerate all maximal subset of a weighted knapsack Given a knapsack $A$ composed of $(u_i, v_i)$-item where $u_i$ is the item identifier and $v_i$ is the weight of the item.

I call a maximal subset when you consider a subset $S$ of $A$ where the sum $R(S)$ over $v_i$ in this subset is less or equal than $P_{max}$ and if you try adding any item $(u_j, v_j) \in A \setminus S$ (if that's not empty) in $S$, then it'll exceed the $P_{max}$ limit, that is: $\forall (u_j, v_j) \in A \setminus S, R(S \cup \{ u_j, v_j \}) > P_{max}$.

I wrote this Python algorithm to compute such an enumeration:

def determine_available(bag, Pmax):
    return [(u, p) for (u, p) in bag if p <= Pmax]

def enumeration(bag, Pmax):
    if Pmax == 0:
        return []

    cur = []
    for v, p in determine_available(bag, Pmax):
        r = Pmax - p

        if not determine_available(bag, r):
            cur.append([v])
        else:
            for pos in enumeration(bag, r):
                cur.append([v] + pos)

    return cur

print(enumeration([(4, 20), (2, 2)], 100)) # for example.

Pseudo-code:

enumeration (bag: set of available items, Pmax)
     if Pmax = 0
     then return empty list

     current_subsets <- empty list
     for all available and usable item of identifier v, weight p
     do
          r = Pmax - p
          if enumerate(bag, r) is empty
          then add the singleton [v] as a subset in current_subsets
          else
               for all subset of enumerate(bag, r)
                  add in current_subsets: [v] + subset
     done
     return current_subsets

Unfortunately, I would like to compute only distinct solutions without removing duplicates after the enumeration. Is there any way to do this?

Bonus question: how to enumerate them in an iterative way?

There might be exponentially many such maximal subsets, so there is in general no efficient way to enumerate all of them.

It's not hard to write a recursive algorithm to enumerate all subsets.  There are only two cases:

The subset doesn't contain item 1.  It consists of a maximal subset of items 2,3,... that sum to $P_\max$ or less.
The subset does contain item 1, plus a maximal subset of items 2,3,... that sum to $P_\max-v_1$ or less.

You can enumerate all subsets of the first type with a recursive call to the procedure, and enumerate all subsets of the second type with a second recursive call.  The base case: if $P_\max \le 0$ or $A$ is empty, then the only such subset is the empty set.


Input distribution in FLP Impossibility Lemma 2 in "Impossibility of Distributed Consensus with One Faulty Process" is as follows:

  LEMMA 2. P has a bivalent initial configuration.

They prove this by showing that the opposite assumption creates a contradiction. As part of that proof, they state:

  Let us call two initial configurations adjacent if they differ only in the initial value x, of a single process p. Any two initial configurations are joined by a chain of initial configurations, each adjacent to the next. Hence, there must exist a 0-valent initial configuration C0 adjacent to a 1-valent initial configuration C1.

In other words, there exists two "adjacent" sets of inputs that differ in only in the value of one of the inputs.

But if I use the output of a totally correct consensus protocol to ensure that the inputs are always either all 0 or all 1, the resulting two sets of inputs would not be "adjacent".

So it appears they implicitly assume that every combination of inputs must be possible. Why can they make this assumption?

The authors' goal is to rule out protocols that work for every possible input. Hence, in their proof by contradiction, they can assume that the protocol works correctly on every input.

The specification of an algorithm should include all constraints on the possible inputs. For example, binary search assumes that the input array is sorted. The specification of consensus protocols doesn't specify any constraints beyond the processes' inputs being binary.


If all computations of non deterministic Turing machine on the input string are all accept then is the boolean formula of them a tautology? If M is non deterministic Turing machine and w is any string then $\Phi_{M,w}$ is satisfiable if and only if M accepts w according to Cook and Levin (1971).

By the definition of non deterministic Turing machine, M accepts w if and only if M has an accept computation on w.

But if all computations of M on w are accept then is $\Phi_{M,w}$ necessarily a tautology more than just satisfiable?

We know for sure that if M rejects w then all computations of M on w are reject and $\Phi_{M,w}$ is unsatisfiable.

The formula $\Phi_{M,w}$, which says "Turing machine $M$ accepts input $w$" is never a tautology.

If you look at how the formula is defined, the variables denote things like "At time $t$, the machine is in state $q$" and "At time $t$, the $i$th cell of the tape contains symbol $\sigma$" and the clauses say things like, "$M$ is only in one state at a time", "every tape cell contains only one character at a time" and "the tape cells don't change except where the head is."  Thus, any assignment to the variables that violates these conditions (e.g., in two states at once, two characters in the same tape cell, characters on the tape changing without being written by the head), then $\Phi_{M,w}$ is falsified.


Simplyfing a particular boolean expression I'm having a lot of trouble with two problems the first is:

1) (y*w) + y + w

 What I tried here is applying the distributive law as follows

(y*w) + (y+w)
((y+w) + y) * ((y+w) + w)
((y*w) + y) * ((y*w) + w)

then applying the absorption law and getting y*w but the answer is y + w, so I'm unsure how to get it using the laws of Boolean algebra.

2) The second problem I am having issues with is

Prove that if x*y = x then ~x*~y = ~y

What I tried was negating both sides of the first expression and plugging into the second but that isn't allowed in Boolean algebra it seems.

I will use $\land$ instead of * and $\lor$ instead of +.

a) You could  simplify it as following:

$ \ \ \ (y\land w) \lor y \lor w = (y\land w) \lor (y \land T) \lor w = y\land(w \lor T) \lor w = (y \land T) \lor w = y \lor w$

b) and prove it as following:

Since $x \land y = x$ we have $\lnot x \lor \lnot y = \lnot x$ by De Morgan's law. By substituting $\lnot x$ in the given equality we have
$$\lnot x \land \lnot y = (\lnot x \lor \lnot y) \land\lnot y = (\lnot x\land \lnot y) \lor (\lnot y \land \lnot y) = (\lnot x\land \lnot y) \lor \lnot y = $$
$$=(\lnot x \lor T)\land \lnot y = T \land \lnot y = \lnot y$$

Recall that for any boolean $x$ and $y$ the following identities always hold

$x \lor T = T$
$x \land T = x$
$x \land x = x$
$x \lor x = x$
$\lnot(x \land y) = \lnot x \lor \lnot y \text{ (De Morgan's law)}$
$\lnot(x \lor y) = \lnot x \land \lnot y \text{ (De Morgan's law)}$


How to prove that the reduction relation is not symmetric I know that the reduction relation is not symmetric. Writing formal proofs is the main core of the course I take on Theory of Computation. So I'm trying to prove that theorem. For that I need to show two languages $L_{1},L_{2}$ so $L_{1}\leq L_{2}$ and $L_{2}\not\leq L_{1}$. My textbook suggests to use $L_{1}\triangleq\Sigma^{*}$ and $L_{2}\triangleq HP$ and show that $L_{1}\leq L_{2}$ and $L_{2}\not\leq L_{1}$.
So I need to split the proof into two sections:

Prove $L_{1}\leq L_{2}$ - Stuck. Not sure how to prove it formally.
Prove $L_{2}\not\leq L_{1}$. I want to use that $HP\not \in R$. So lets assume by contradiction that $HP\leq\Sigma^{*}$. This means there such function $f\,:\,\Sigma^{*}\to\Sigma^{*}$ between $HP$ and $\Sigma^*$. How to continue?

The definition of reduction: Given two languages $L_1$ and $L_2$, we say that there is reduction from $L_1$ to $L_2$ (and mark $L_1\leq L_2$) if there is a function $f\,:\,\Sigma^{*}\to\Sigma^{*}$ so:

$f$ is full - for each $x\in \Sigma^*$ there is one $y\in \Sigma^*$ so $f(x)=y$.
$f$ can be computed - there is a Turing machine that can compute $f$.
fulfils: $x\in L_1$ iff $f(x)\in L_2$.

As formality is important, how do I fill the blank spaces up to the full proof?

In order to show that $L_1 \leq L_2$, we need to come up with a computable function $f$ such that $x \in L_1$ iff $f(x) \in L_2$. Since $L_1 = \Sigma^*$, every $x$ satisfies $x \in L$, and so we need to find a computable function $f$ such that $f(x) \in L_2$ for all $x$. The easiest way to satisfy this is to choose $f$ to be a constant function.
In order to show that $L_2 \not\leq L_1$, we need to show that $f$ is a computable function that it is not the case that $x \in L_2$ iff $f(x) \in L_1$. That is, we need to show that for every computable $f$ there exists $x$ such that it is not the case that $x \in L_2$ iff $f(x) \in L_1$. Since $L_1 = \Sigma^*$, we always have $f(x) \in L_1$, so the only way in which "$x \in L_2$ iff $f(x) \in L_1$" can fail is if $x \notin L_2$. That is, we need to show that for every computable $f$ there exists $x$ such that $x \notin L_2$. The goal doesn't involve $f$, so it suffices to show that there exists $x$ such that $x \notin L_2$.
You take it from here.


Smallest string length to contain all types of beads I read this question somewhere, and could not come up with an efficient answer.

A string of some length has beads fixed on it at some given arbitrary distances from each other. There are $k$ different types of beads and $n$ beads in total on the string, and each bead is present atleast once. We need to find one consecutive section of the string, such that:

that section contains all of the $k$ different types of beads atleast once.
the length of this section is as small as possible, provided the first condition is met.

We are given the positions of each bead on the string, or alternatively, the distances between each pair of consecutive beads.

Of course, a simple brute force method would be to start from every bead (assume that the section starts from this bead), and go on till atleast on instance of all beads are found while keeping track of the length. Repeat for every starting position, and find the minimum among them. This will give a $O(n^2)$ solution, where $n$ is the number of beads on the string. I think a dynamic programming approach would also probably be $O(n^2)$, but I may be wrong. Is there a faster algorithm? Space complexity has to be sub-quadratic. Thanks!

Edit: $k$ can be $O(n)$.

With a little care your own suggestion can be implemented to $O(kn)$, if my idea is correct.

Keep $k$ pointers, one for each colour, and a general pointer, the possible start of the segment. At each moment each of these colour pointers keeps the next position of its colour, that follows the segment pointer. One colour pointer points to the segment pointer. That colour pointer is updated when the segment pointer moves to the next position. Each colour pointer in total moves only $n$ positions. For each position the segment pointer computes the maximal distance to the colour pounters, and one takes the overal minimum of that.

Or, intuitively perhaps simpler, let the pointers look into the past, not the future. Let the colour pointers denote the distance to the respective colours last seen. In each step add the distance to the last bead to each pointer, except the one of the current colour, which is set to zero.

(edit: answer to question) If $k$ is large, in the order of $n$ as suggested, then one may keep the $k$ pointers in a max heap. An update of a pointer costs $\log k$ each of $n$ steps. We may find max (the farthest colour, hence the interval length) in constant time, each of $n$ steps. So $n \log k$ total plus initialization.

Now we also have to find the element/colour in the heap that we have to update. This is done by keeping an index of elements. Each time we swap to elements in the heap (a usual heap operation) we also swap the positions stored in the index. This is usually doen when computing Dijkstra's algorithm with a heap: when a new edge is found some distances to vertices have to be decreased, and one needs to find them.


For a logic gate to be universal, must it necessarily be able to perform duplication? It is said that a gate that can simulate AND and NOT is universal and able to recreate any classical circuit. I was looking at some of the circuits simulated by NAND, and for some of them, we need to split the output of a gate and direct each of the splits to other NAND gates (see the area circled in red):

If we make the restriction that all gates are reversible (in particular, we require fixed input/output size), does the AND/NOT criterion still hold? Is the ability to "split" outputs (i.e., a gate that can do AND, NOT, and duplicate a $0$ or $1$, e.g. $(0,0,1) \rightarrow (0,1,1)$ ) a necessary/sufficient condition for universality?

I'm not sure what you're asking, precisely, but it's certainly not true that a reversible universal gate requires the number of set bits in the output to be the same as in the input. Toffoli gates do not have that property, for example.
EDIT
Thanks for the clarification. The answer to your question is that any reversible circuit must have at least as many output lines as input lines. As an exercise, prove this. Try using the pigeonhole principle.
So what happens if you need a reversible circuit with fewer output lines than input lines? You just add output lines, the values of which are irrelevant. The circuit still computes what you need it to, it also happens to compute more stuff that you don't care about.
So what I think you're asking about duplication is can there be more output bits than input bits? The answer is "kind of", and it comes down to what model of reversibility you care about.
Such a circuit can clearly be logically reversible. But can it be physically reversible? I'm not a hardware designer, and I don't know.


What is the difference between derivative free optimization and derivative optimization in terms of advantages/disadvantages? I understand the basic operation of the algorithms however i'm unclear as to when to use one over the other and what advantages/disadvantages they offer over each other.

Also as an aside, if anyone knows any good resources that go over the topic of optimization in detail (especially gradient free optimization) that I could read or watch, i'd really appreciate it if you could point me in the right direction.

Thanks in advance guys and apologies if its a basic question, I'm quite new to the topic.

Actually, derivative methods such as random search shorten the time allocated for function evaluation if the problem is big. On the other hand, derivative-free methods take much time to complete function evaluation that leads to a dramatic increase in optimization time.


Build a regular grammar for a regular language The language considered is the infinite set of all chains that meet the following conditions.

Conditions:

1) They consist of symbols from the set {1,a,b}.
2) They always start with the subchain '1a'.
3) They always include at least one subchain 'aa'.

For example:

1aa, 1abaa, 1aaab, 1aab1a, ... etc.

One regular expression for this language seems to be like this: $1a ((1+b)^* a)^* (a (1+b)^* )^* a (1+b+a)^*$

How to find a regular grammar for this language?

I've thought of many ways but it seems to be too complex for me. I tried the following as solution, but it is not correct, I guess.

G ({1,a,b}, {A,S}, P, S)
P:
S -> 1S|bS|aA
A -> 1A|bA|1a

The expression always starts with 1a. There are two options, the third character in the string is a or not. If it is a, then you don't have the obligation of following 'it contains at least one a'. Otherwise, you need to. Thus the regular expression is:

    1aa(1+a+b)*+1a(1+a+b)*aa(1+a+b)* .

The conversion from regular expression to automata to regular grammar is standard. One possible algorithm is given here: https://math.stackexchange.com/questions/574571/build-regular-grammar-from-regular-expression

Here is an intuitive way to convert a regular expression to a right linear grammar:

Convert the regular expression to an NFA. This is standard (see page 102 of Automata Theory, language and computation, 3rd ed).
To convert the NFA to a right linear grammar, take the states to be non-terminal and the alphabets to be terminal. For a transition of the form S -> S' via a, add the production rule S -> aS'. Please note that you need to take care of the final states and epsilon transitions separately.

You can also convert the NFA to a DFA (again, standard subset construction method, see the aforementioned book) and then the method will be simpler.


Mapping a free variable of type A to a cartesian closed category In From Lambda Calculus to Cartesian Closed Categories, the author explains the interpretation of lambda calculus in cartesian closed category and at one point he explains how a term representing a free variable of type A is mapped to the cartesian closed category as follow:

 [Γ x:A :- x:A] = π2 : ([Γ ] × [A]) → [A]

 (A term which is a free
 variable of type A is an arrow from the product of Γ and the type object A to A;
 That is, an unknown value of type A is some arrow whose start point will be
 inferred by the continued interpretation of gamma, and which ends at A.
 So this is going to be an arrow from either unit or a parameter type to A -
 which is a statement that this expression evaluates to a value of type A.)

I appreciate if someone can elaborate further on what the author means, perhaps with an example, since I am a newbie to category theory.

It's not clear exactly what your confusion is, so I'll try to explain the example more clearly, and you reply in the comments if something's still not apparent.

In the interpretation of the simply-typed $\lambda$-calculus in a cartesian-closed category, contexts $\Gamma$ and types $A$ are interpreted as objects $⟦\Gamma⟧$ and $⟦A⟧$ (types being equivalent to one-variable contexts), while a term $\Gamma \vdash t : A$ is interpreted as a morphism $⟦t⟧ : ⟦\Gamma⟧ \to ⟦A⟧$.

Context extension is represented by taking the product in the cartesian-closed category, that is: $⟦\Gamma, x : A⟧ = ⟦\Gamma⟧ \times ⟦A⟧$. We want to form the projection of the variable $x : A$, which is represented by a morphism $⟦x⟧ : ⟦\Gamma, x : A⟧ \to ⟦A⟧$, which by definition is a morphism $⟦x⟧ : ⟦\Gamma⟧ \times ⟦A⟧ \to ⟦A⟧$. There's one obvious choice here: to project the second component of the product. Taking $⟦x⟧ = \pi_2$ gives us a term of the correct type and it satisfies the expected properties.

In general, contexts (represented by lists of variables in the type theory) are represented by products of types in the cartesian-closed category, and the term corresponding to the $i^\text{th}$ variable is given by the $i^\text{th}$ projection from the product, $\pi_i$.


Longest cycle in a digraph Given a directed graph $G$, we want a (simple) cycle in $G$ of maximal length. The cycle does not need to be an induced subgraph of $G$. What is known about this optimization problem?

Do we know its complexity? Is it much harder than the decision problem of detecting a Hamiltonian cycle? How well-approximable is the problem?

For the exact problem, is there a more efficient algorithm than exhaustive search using Johnson's cycle-enumeration algorithm?

Ideally, for the complexity question, I would like a description similar to here and here for related problems on undirected graphs: Longest induced cycle, Longest path, and Longest induced path. Longest cycle (for undirected graphs) is discussed in "A Structural Overview of NP Optimization Problems", although I have a harder time understanding that account.

FWIW, I'm particularly interested in (approximate) solutions for strongly connected digraphs of 100-500 vertices having average vertex degree ~10 and several induced tournaments on 5-10 vertices. I've been playing with genetic algorithms, and I'd like to know (1) whether better methods are available and (2) what level of performance I can reasonably aim for.

The problem of finding a longest simple cycle in a digraph is NP-hard, since the problem of finding a longest simple cycle in an undirected graph is a special case: you can consider an undirected graph to be a digraph with a symmetric edge relation.  (Longest simple cycle is NP-hard since it lets you solve Hamiltonian cycle.)


What are advantages / disadvantages of horizontal and vertical microprograms? Currently I know:

About vertical micro programming: The control signals are not immediately passed to the ALU components, but are rather processed first and passed as an compressed function code.

About horizontal micro programming: There is just one wire connecting all ALU components directly. The signal contains for each component a bit indicating whether the component should be activated or not.

I guess H-$\mu$Programs generally runs faster as they have not to be processed extra. However have the disadvantage that the signals are pretty long.

Are there other advantages / disadvantages to each of these two types of micro programming?

EDIT: I saw a comment regarding the question being dated. Yes, it is. Nonetheless, examiners at university want to know such things. I had a hard time finding information, which is why I asked on this StackExchange, sort of as a last resort.

This questions seems dated, about the way computers and instruction sets were designed in the 70's.

AFAIK, micro-ops in x86 CPUs have about 100 bits, and are decoded separately in each operation unit (ALU, LSU, FPU...) There is no gigantic flat microcode controlling every multiplexer.

There used to be several layers of microcode and ROM decoding tables instructions are translated into "vertical" micro-ops which are then decoded into "horizontal" signals (IIRC, the MC68000 was like that).

Pure horizontal microcode is impractical in modern chips. Long wires have parasitic capacitance and are "slower" than transistors. Using a large and wide microcode ROM outputting hundreds or thousands of signals to individual adders, multiplexers and registers would make a large and slow chip.

Additionally, nowadays processors are pipelined : A wide microcode would need hundreds of flipflops to propagate instruction decoding along the pipeline.


Sub-exponential for Subset Sum on the total bit length of the input Was crawling the internet, and found this in a paper (1)

"[...], a variant of dynamic programming called
dynamic dynamic programming has been shown to have a worst-case sub-exponential time complexity of $2^{O(\sqrt x)}$ when the total bit length $x$ of the input set is used as the complexity parameter."

As I understand this claim violates the Exponential Time Hypothesis, and there has been some answers in the forum clearly stating no such sub-exponential algorithm exists, would be interesting to know what the experts in the area think about the proposed algorithm in terms of worst case complexity.

Direct link to the paper (2) explaining the dynamic dynamic approach.

(1) Thomas E. O’Neil -An Empirical Study of Algorithms for the Subset Sum Problem

(2) Thomas E. O’Neil, Scott Kerlin - A Simple $2^{O(\sqrt x)}$ Algorithm for PARTITION and SUBSET SUM

This doesn't violate the exponential time hypothesis.  The exponential time hypothesis says that k-SAT takes exponential time, i.e., $\Omega(2^{cn})$ for some constant $c>0$.  So if you found a $O(2^{\sqrt{n}})$ time algorithm for k-SAT, that would violate the exponential time hypothesis -- but a a $O(2^{\sqrt{n}})$ time algorithm for subset sum does not violate the hypothesis.


Understanding Cache Mapping and Access (Computer Architecture) Consider a 512-KByte cache with 64-word cachelines (a cacheline is also known as a cache block, each word is 4-Bytes). This cache uses write-back scheme, and the address is 32 bits wide.

Answer the next questions for Direct Mapped cache, Fully Associative and Way Set Associative

What is the size in bits of the cacheline offset, cachline index and tag?

What I know:

Direct mapped caching allows any given main memory block to be mapped into exactly one unique cache location.

Set-associative mapped cache allows any given main memory block to be mapped into two or more cache locations.

Fully-associative mapped caching allows any given main memory block to be mapped into any cache location.

I don't know how that would make a difference in computing byte offset, index and cache

$Byte offset=log_2(\text{bytes in one cache block})$
$Index=log_2(\text{Number of cache blocks in the cache})$
tag: The rest of bits in the address

Attempt at a solution

I would do the mapped cache part by using the previous expressions. I don't want the answer, but I would like orientation.

Thanks!!

Any physical address consists of two parts : one part is the block offset and the other part is the block number.

Physical Address { Block number, Block Offset}

Block Number has further 2 parts : the index part and the tag.

The memory is assumed to be logically divided into many blocks. A block may contain more than one words in it ( which is indicated by the block size ). To reach to a specific word block offset is used.
Block offset is the number of bits required to address each word in the memory.

For instance, in a byte addressable system ( 1 word = 1 byte ) if the block size = 1 KB thenBlock Offset = 10 bits.  (Byteoffset=log2(bytes in one cache block)
The block offset remains same in each type of mapping as the number of words in each block do not change.

The implementation of block number is different in different mappings.

In case of Direct mapping the block number has two parts:

block no { tag, line number}

Since each block is mapped to one line in the cache,  the "line number" part of block number contains number of bits required to identify each line in the cache.
In this case since cache size = 512 KB and block size = (64 * 4)B = 256 B
The Number of lines in the cache = 512 KB / 256 B = 2 K = 2 ^ 11
Therefore, the number of bits in line number part will be 11.
The remaining bits are tag bits.

Fully Associative Mapping the tag number is same as the block number .
In Fully Associative Mapping any memory block can be mapped to any of the cache lines. So to check which line of the cache a particular block is mapped to every line number is "tagged".

And in Set Associative Mapping the block number is divided into two parts:

block no { tag, set number}

Here, the cache is divided into many sets, so the "set number" part consists of the number of bits required to identify each set uniquely.
Depending on the number of lines in each set ( a K-way set associative mapping will contain K lines in each set), the number of sets can be found out.

Hope this will help you.


What is the difference between Cased-based Reasoning and Rule-based reasoning? As stated here, Rule-based Reasoning systems are considered to be "old style" AI that uses rules prepared by humans - as opposed to Neural Networks where machine recognizes pattern i.e. acquires new knowledge and takes decision based upon that.

What I understand about Case-based Reasoning (CBR), it looks at the new cases in light of similar past cases, finds suitable reference cases, evaluates their application on the new case and revises it accordingly, applies it on the new case, and finally stores the case and solution as newly acquired knowledge.

Considering this, can I state that Case-based Reasoning should be considered as "new style" AI? Or is there a gap in my understanding?

I wanted to add: If anyone can offer a rough spectrum, that puts different AI approaches on different points depending on how independently they can take decision or how much prone they are to learn from experience (i.e. train their mind) instead of being 'pre-configured', that will also be welcome.

As said in the comments, there may be a part of subjectivity in the answers to this question.

Yet, I think it is fair to say that case-based reasoning mostly belongs to what is often called transductive methods, while rule-based (as well as neural networks and most statistical models) models mostly belong more to what is often called inductive approaches.

In short:

Transductive methods will not try to induce a generic model from your past observations/experiences, but will simply try to predict/find the answer of a new problem by looking at past experiences. This means you have to maintain a memory of past experience, and then select the most adequate one to answer your new problem. The most well-known representative of such approaches is probably K-NN.
Inductive approaches will try to induce a "compact" model from your past observations/experiences, and to generalise (make an induction) from those. Once this is done, you can forget your past experiences and only use your learned model to make prediction.

The parallel you can make is between looking up a table of stored input/output values (e.g., to get a p-value), which is transductive, and using a mathematical formula to compute a new prediction, which is inductive.

Lastly, it should be noted that the way you build your model when performing induction largely depends on your applications, available knowledge and needs (there are certainly ways to learn rule-based systems from data).


Does a logical system have semantics? From Wikipedia:

  A logical system or, for short, logic, is a formal system together with a form of semantics, usually in the form of model-theoretic interpretation, which assigns truth values to sentences of the formal language, that is, formulae that contain no free variables. A logic is sound if all sentences that can be derived are true in the interpretation, and complete if, conversely, all true sentences can be derived.

Does a logical system have semantics?

Does the assignment of truth values to sentences of the formal language count as the semantics of a logical system? I feel it  provide little interpretation of what the sentences of the formal languages mean.

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

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


Sorting $n^2$ numbers which consist of numbers from 1 to $n$ I wish to sort $n^2$ numbers which all come from the set $\{1,2,3,...,n\}$, i.e duplications are allowed. I know I can just use
merge sort which has complexity $\mathcal{O}(n^2\log (n))$, but I was wondering if it was possible to do better since I know all the numbers will be coming out of $\{1,2,3,...,n\}$.
If there is a special name for this type of problem please let me know. Any references or answers are greatly appreciated.

Given your contraints, I think Counting sort or Radix sort will do the job.

https://en.wikipedia.org/wiki/Counting_sort

https://en.wikipedia.org/wiki/Radix_sort


Check if a linear function or an affine function can be a pseudo random function Let $G = \{0, \cdots , p-1 \}$ be a field. Let $K = G^{m \times n}$ and $F:K \times G^n \to G^m$ be a family of functions.
For $A \in G^{m \times n}$ and $x \in G^n$ we have $F(A,x) = Ax$.
I need to check if $F$ is a secure pseudo random function.
We say that PRF $H: K \times X \to Y$ is $(T, \epsilon)$-secure if for every algorithm $B: X \to \{0,1\}$ of size $T$ it follows:
$$|P(B^{H_k()} = 1) - (B^{R()} = 1)| \le \epsilon$$
where $H_k(x) = H(k,x)$, $R:X \to Y$ is a random function, and $B^{S()}$ means $B$ has oracle access to the function $S$.
Now, back to the question, I tried to describe the following adversary B:
on input $x \in G^m$ and access to oracle $Z()$, $B$ will take $n$ base elements of $G^m$ and run $Z()$ on them.
Then, $B$ will check if $ x \in span\{Z(e_1), \cdots , Z(e_n) \}$ and return 1 if it is.
This way I get that $P(B^{H_k()} = 1) = 1$ and if $ m > n$ then $P(B^{R()} = 1) \le \frac{1}{p^{m-n}}$, which proves that $H$ is not secure.
The only problem is when $n \ge m$, since I am not sure how to get a good bound on $P(B^{R()} = 1)$ in this case.
Help would be very appreciated!
There is also the same question but with $K = G^{m \times n} \times G^m$ and $F:K \times G^n \to G^m$, $F((A,b), x) = Ax+b$.

Intuitively, pseudorandom functions are functions that look random. A linear function $f$ satisfies
$$ f(x+y) = f(x)+f(y) $$
for all $x,y$, which is highly unlikely for a random function. Similarly, an affine function $f$ satisfies
$$ f(x+y) - f(x+z) = f(y) - f(z) $$
for all $x,y,z$, which is highly unlikely for a random function.


F-measure with $\beta > 1$ Consider the F-measure $F_{\beta}$. I know that with $\beta < 1$ precision is given more importance, ending with $F_{0} = precision$. With $\beta > 1$ means recall gets the upper hand, with the other extreme at $F_{inf} = recall$.

\begin{equation}
F_{\beta}  = (1+ \beta^2) \cdot \frac{Precision \cdot Recall}{(\beta^2 \cdot Precision) + Recall}
\end{equation}

I understand why for $\beta < 1$ precision is given more importance, but I don't understand for $\beta > 1$

Define $\gamma = 1/\beta$, $P=\textrm{precision}$, and $R=\textrm{recall}$.

Then $$F_{\beta} = (1 + 1/\gamma^2)\cdot \frac{PR}{P/\gamma^2 + R} = (\gamma^2 + 1) \cdot \frac{PR}{\gamma^2R + P}$$, which is the $F_\gamma$ measure with the roles of $P$ and $R$ switched.

So the same reasoning that shows precision is preferred for $\beta < 1$ can be used to show that recall is preferred when $\gamma = 1/\beta < 1$, i.e. when $\beta > 1$.


Log space reduction from STCONN to CYCLE I read this post: Showing Cycle is NL-complete?, but I am not sure why the reduction is log space, as it requires keeping track of the new graph, which has $n^2$ nodes.

There is no need to store the new graph on the tape. We just need to be able to output it in logspace. This is straightforward, for any reasonable encoding of graphs.


Sorting algorithm for ranking hundreds of Images based on pairwise comparison I am facing the task of designing an algorithm to rank some hundred of images (around 300). The ranking is to be based on pairwise comparison judged by human (done through Amazon mechanical Turk). I have read many papers on ranking inference based on a subset of all possible pairwise comparisons (e.g. Jamieson and Nowak 2011). But I think because I don't have many images, exact ranking should be achievable with properly designed pairwise comparison sequences using some sorting algorithm.
Nonetheless this is different from the standard array sorting in the sense that, comparison result is not known with certainty prior to arranging the pair for comparison and letting the human judge decide. Thus there is a bit of adaptive selection involved. Moreover since it is based on the perception of one human judge, no parallel processing is possible to expedite the sorting. What is worse, transitivity is not guaranteed. Therefore some standard sorting algorithms may not be applicable.
Would somebody please recommend some sorting algorithm for my task?
Many thanks!

If you're actually using humans (e.g., MTurk) and there is any subjectivity at all, I expect that standard sorting algorithms may perform poorly.  Standard sorting algorithms expect that there will be zero errors or mistakes in any of the comparisons.  If a single comparison returns a faulty value, the sorting algorithm might fail badly.  However, in practice, humans make mistakes; and if the rating task is subjective, humans don't always agree on all rating decisions.  Consequently, I expect standard algorithms are likely to be a poor match.
If transitivity is not guaranteed, standard sorting algorithms are definitely not suitable.
There are better approaches that can tolerate some errors and mistakes and disagreements.  For instance, you might be interested in the Bradley-Terry-Luce model; see https://cs.stackexchange.com/a/134416/755.  It helps you infer an overall ordering, based on individual pairwise comparisons.  That model does not support nontransitivity, though.
We could also consider how to choose which pairwise comparisons to make (i.e., the experiment design question, instead of the inference question).  I don't know if there is literature on that; but Peer grading design - choosing a graph, to get accurate rankings/ratings might be of interest, and it might be worth checking Stats.SE or asking there about this aspect of the problem.


Find max flow in a network with all capcities of $\sqrt 2$ and one with 2 Given a graph $G(V, E)$ with capacities on the edges such that all edges have a capacity of $\sqrt2$ apart from one edge with a capacity of 2. need to find max flow efficiently.

I can run Dinic on this graph or FordFulkerson but I know it can be more time-efficient.

What I have tried -

transform all edges capacity to be 1, then find max flow using Dinic algorithm on 0-1 network that is more efficient than a general network.
then If the edge that had a capacity of 2 isn't saturated it won't be saturated on the original graph so we can just find the min-cut and multiply the number of edges that cross the min-cut by $\sqrt 2$ and that's the max flow.
but if it's saturated I'm stuck.

First, you can divide all capacities by $\sqrt{2}$ so that all capacities are now $1$ except for a single edge $e'$ which has capacity $\sqrt{2}$.

Call this instance $G$. Create $G_1$ which is a copy of $G$ where the capacity of $e'$ has been replaced with $1$, and find the max flow of this graph, with a value $F_1$.

Now, consider $G_2$ which is also a copy of $G$ where the capacity of $e'$ has been replaced with $2$ and has a max flow of $F_2$.

If $F_2 > F_1$, this means that starting from the flow assignment of maximum flow in $G_1$ there is an augmenting path in $G_2$ along which you can push $1$ additional unit of flow. This augmenting path necessarily corresponds to an augmenting path in $G$ where you can push $\sqrt{2}-1$ additional units of flow. Thus, the max flow for $G$ is $F=F_1 + \sqrt{2}-1$.

If $F_2 = F_1$, this means that starting from the flow assignment of maximum flow in $G_1$ there is no augmenting path in $G_2$ along which you can push any amount of flow. This also means that this holds for $F$, as the capacity increase of $e'$ between $F_1$ and $F$ is lower than between $F_1$ and $F_2$. Thus, the max flow for $G$ is $F=F_1$.

(You just need a single search of augmenting path to determine if $F_2 > F_1$ or $F_2 = F_1$ once you have computed the flow for $F_1$)

Then, to get the answer to your original problem, just scale the flow back by multiplying $F$ by $\sqrt{2}$.


Balanced Distribution Of Items I shall call this the "Curtain Hook" problem.

Please excuse my lack of formal maths notation as it has been over 20 years since I have needed it.

A standard pencil pleat curtain has L number of loops on the back (evenly spaced along the width) with which to hang the curtain.  The curtain pole will come with H number of hoops to hang the curtain upon.
The problem is how to distribute - with as uniform as possible gaps between - the hooks across the loops.

For example, if I have 15 hooks (per curtain) and each curtain has 38 loops where should I hang the 15 hooks?

By hand I came up with:
HoHooHooHooHoHooHooHoHooHooHoHooHooHoH
Which is not evenly spaced. (H being a hook, o being an unused loop)

Is there an evenly balanced solution for this combination?
Is there an algorithm that can be used to describe where to place the hooks evenly?

Ps. Not homework, just someone with a curious analytical mind who had to put up some curtains recently.  I was thinking of creating a web page to help others if a general solution/algorithm could be found.

Thanks

Craig

You haven't quite defined your problem, so let me answer a more concrete one: when can there be an evenly spaced solution. I assume that by "evenly spaced" you mean that all the spaces are the same, and that there must be hooks and the first and last positions. If the space is $s$, then we must have
$$ L = 1 + (s+1)(H-1), $$
since the string is of the form $H(o^sH)^{H-1}$. This is possible if and only if $H-1$ divides $L-1$, in which case the spacing is
$$
 s = \frac{L-1}{H-1} - 1.
$$
In your case, 14 doesn't divide 37, so an even spacing is impossible.


Complexity of ODD-SMALLER-SAT While familiarizing myself with polynomial hierarchy, I used this book which is written by Ingo Wegener. Now I'm practicing, and on page 132 I met this exercise:

Let us consider a Boolean formula $\phi$ on the variables $x_1, ...,x_n$. Each $n$ bit vector $\overline x \in \{0,1\}^n$ is a possible assignment to variables and these vectors can be naturally classified in alphabetical order. The ODD-SMALLER-SAT-DECISION  problem is to determine, being given $\phi$, if the smallest assignment $x$ which is satisfactory is such that $x_n = 1$.

How to prove that this problem is part of the complexity class $\Delta_2$?

Given $\phi$ and an assignment $\overline{y}$, the problem of deciding if there exists a satisfying assignment $\overline{x} \le \overline{y}$ (w.r.t. the lexicographical order) is in NP.
This can be seen by either designing a nondeterministic Turing machine that solves the problem in polynomial time (nondeterministically guess $\overline{x}$, then deterministically check if $\overline{x} \le \overline{y}$ and $\phi(\overline{x}) = \top$, if so accept, otherwise reject), or by noticing that $\overline{x}$ itself is a yes-certificate for the instance (that can be deterministically checked in polynomial-time).

Then your original problem is in $\Delta_2 = P^{NP}$: perform a binary search on the space of the $2^n$ possible assignments to find the smallest satisfying assignment $\overline{x}^*$ for $\phi$. This can be done by repeatedly solving the above problem, each time halving the search space. After $O(\log 2^n) = O(n)$ iterations you are left with $\overline{x}^*$. Check whether $\overline{x}^*_n = 1$ and answer accordingly.


Using backtracking to find all possible permutations in a string I came across this algorithm in a book, and have been struggling to understand the basic idea. The books says it uses backtracking to print all possible permutations of the characters in a string. In Python, the algorithm is given as:

def bitStr(n, s):
    if n == 1: return s
    return [digit + bits for digit in bitStr(1, s) for bits in bitStr(n - 1, s)]

print(bitStr(3, 'abc'))

I'm pretty weak in algorithmic thinking and am struggling for both an intuitive understanding of this, as well as tracing it. Can somebody explain what this algorithm does and how exactly is uses 'backtracking'?

Backtracking is a general algorithm "that incrementally builds candidates to the solutions, and abandons each partial candidate ("backtracks") as soon as it determines that the candidate cannot possibly be completed to a valid solution." (Wikipedia).

So, basically, what you do is build incrementally all permutations. As soon as as you build a single permutation, you backtrack and build another one, and so on until you generate all $n!$ possible permutations, say, on $n$ symbols.

Example: $n=3$, $S=\{1,2,3\}$.

You start with $1$. Then you move forward an choose $2$ (since $1$ has already been chosen), and then you choose $3$. At that point you have built the first permutation $123$. Then you backtrack and select $3$ instead of $2$, then select $2$, and you have $132$. You backtrack again, but you have already used $2$ and $3$, so you backtrack again (one level up where), and choose $2$ instead of $1$, then you select $1$, and finally $3$, so you have $213$.
The following picture should clarify the basic idea:

In other words, you simply traverse the tree, and when you reach the leaf you print the permutation. Then you backtrack one level up, and try another option. Moving one level up the tree is what we call the backtracking in this case.

As for implementation, the backtracking is usually implemented using recursive call(s) as in your example. I assume that you have necessary programming skills to implement this basic idea yourself, in particular solving problems using recursive calls.


Testing whether the language of one automaton is a subset of another Is there an algorithm to solve following problem?

Given two finite automata $A$ and $B$. Determine whether the language recognized by automaton $A$ is a subset of language recognized by automaton $B$ or otherwise.

Recall some closure properties of regular languages, namely that they are closed under complementation and intersection. Now, $L(A)\subseteq L(B)$ whenever $L(A)\cap\overline{L(B)}$ is empty. So you need to construct the automaton that accepts the intersection of $A$ and the complement of $B$ – these are standard constructions – and test whether the resulting automaton accepts the empty language. This can be checked by inspecting the automaton to see whether any accepting states are reachable from the initial state. If not, then the language accepted is empty.


If $f(n)=\Omega(g(n))$ and $h(n)=\theta (g(n))$ then does this implies $f(n).g(n)=\Omega(g(n).h(n))$? If $f(n)=\Omega(g(n))$ and $h(n)=\theta (g(n))$ then does this implies $f(n).g(n)=\Omega(g(n).h(n))$

I saw a proof where they have proved  If $f(n)=O(g(n))$ and $h(n)=\theta (g(n))$ then this implies $f(n).g(n)=O(g(n).h(n))$.

So I thought may this should also hold. I have taken some examples and the formula holds on all of them. However I can't be sure. There can be a contradicting case.

I have got the answer. It's easy.

Since $f(n)= \Omega g(n)$

$cg(n)\le f(n)$

Multiplying both sides by h(n)

$cg(n).h(n)<=f(n).h(n)$

$f(n).g(n)=\Omega(g(n).h(n))$


Starvation in longest remaining time first CPU scheduling I want to know if longest remaining time first (LRTF) CPU scheduling has starvation or not. Also give reason how it starve/does not starve a process.

I know longest job first (LJF) may starve a process if all other incoming processes have longer CPU burst.

TLDR: Starvation is possible under some assumptions.

Without loss of generality let's assume that in tie situation of longest remaining time first (LRTF) algorithm we give CPU time to process with lowest ID.

Let's also assume that incoming processes IDs are always increasing.

Now let's consider two cases.

1) At some time there will be no new processess.

This is obvious because once new processess will stop arriving then eventually all processess will be executed, so no starvation.

2) New processess will never stop arriving.

Let's say that at time 0 all max time of process is $d$.
In other words:
$d=\max_{p\in\mathcal{P}}(t_p)$. Where $\mathcal{P}$ is set of processess and $t_i$ it remaining time of $i$'th process.

So now let's consider following scenario:

Adversary knows $d$ and that at time 0 there are $n$ processess, at each time unit adversary inserts new process with time $d+1$.

At time $1$ one of processess numbered $1...n$ (the one with time $d$) will consume one time unit. Then new process will arrive with time $d+1$ it will gain one time unit from scheduler. From now no of processess $1...n$ will gain CPU time, because all adversary processess will remain $d$ time units and newly arrived process will have prority over another.

There is on problem with this analysis. It assumes that there can be infinite number of processess in the system. In real operating systems this cannot be achieved.

Now let's assume that adversary doesn't know $d$. He might choose some constant $k>2$ and insert it's processess with that time. At some point in time which is equal to $\sum^{n}_{i=1}{\max(0, k-t_i)}$ adversary processess will starve all other procesess.


What is the runtime of the following code? Can you explain to me how you get the Big O notation for the runtime of the following snippet of code?

for x = 1 to n
{
    y = 1
    while y < n
       y = y + y
}

Can you explain the steps on how you get the big O notation for it? Also why doesn't it matter if there a bunch of statements inside a for loop when calculating the big O notation? Wouldn't the number of operations increase as n gets larger if there are more O(1) statements inside the for loop? Help would greatly be appreciated.

Hint: First of all, since the code in the loop doesn't depend on $x$, the running time of the code is $\Theta(n)$ times the running time of the code inside the outer loop. Second, the running time of the code in the inner loop is $\Theta(\ell)$, where $\ell$ is the number of iterations of the while loop, which is the number of times you need to double $1$ until you reach or exceed $n$. Perhaps you can find a formula for $\ell$.


Merging two binary search tress You have two binary search trees A and B, each one is a complete binary tree containing $2^k-1$
nodes. The maximum value of the keys in the tree A is less than the minimum value of the keys
in tree B.

Propose an efficient algorithm for creating a single height-balanced binary search tree containing the key values of all the nodes in both the trees A and B.

Begin by computing the heights h1 of T1 and h2 of T2. This takes time O(h1 + h2): You simply traverse a path from the root, going to left child if the balance factor is -1, to the right child if it is positive, and to any of the children if the balance factor is 0, until you reach a leaf. Assume that h1  h2; the other case is symmetric.

Next, DELETE the smallest element x from T2, leaving T2′ of height h. This takes O(h2) time.

Find a node v on the rightmost path from the root of T1, whose height is either h or h + 1, as follows:

v ← root(T1)
h′ ← h1
  whileh′ >h+1do
  if balance factor (v) = -1 then h′ ← h′ − 2
  else h′ ← h′ − 1
  v ← rightchild(v)

This takes O(h1) time.
Let u denote the parent of v.

Form a new tree whose root contains the key x, whose left subtree is the subtree rooted at v and whose right subtree is T2′.
Note that this is a valid binary search tree, since all the keys in the subtree rooted at v are in T1 and, hence, smaller than x, and, by construction, x is smaller than or equal to all elements in T2′. The balance factor of the root of this new tree is h−h′, which is either -1 or 0, so this new tree is a valid AVL tree. The height of this new tree is h′ +1, which is 1 bigger than v’s height. Let the root of this new tree be the right child of u, in place of v. Again, since all keys in this new tree are at least as big as u, this results in a valid binary search tree. This part of the construction takes constant time.

Now, as in the INSERT algorithm, we go up the tree, starting at u, fixing balance factors and perhaps doing a rotation. This takes O(h1) time. Note that the correctness follows from the condition at u before this process is begun is a condition that can arise during the INSERT algorithm.
Since h1, h2 ∈ O(log n), the total time taken by this algorithm is in O(log n)

you can find more answer in this question :
Merging of height balanced trees

and this algorithm can help you for more details :
A Fast Merging Algorithm MARK R. BROWN


Which could be a possible time complexity? I have the following algorithmen (picture) which calculates a Vertex Cover and gets an undirected $G(V,E)$ Graph as input.

The following task is to find the possible Time complexity (estimate) while $n = |V|$, $m = |E|$,
$n \le m + 1$ and $deg(v) = |N(v)|$:
a) $O(n log n)$
b) $O(n + m)$
c) $O(2^n*m)$
d) $O(n^k*m)$
e) $|V| \choose k$ * $\sum_{v \in V} deg(v) $

Clearly a,b cannot be an estimate running time for the algorithm.
e) looks correct, but c and d?

$n=|V|$, and $\sum_{v\in V}deg(v) = 2\cdot |E| = 2m$ (each edge is counted exactly twice).
Take a look here for a proof why ${n \choose k} = \Theta(n^k)$ for a fixed $k$. Substitute everything, and get that also $O(n^k*m)$ is a valid estimate (again, only if $k$ is a fixed number!).
c) Is clearly not a tight bound, since it doesn't even depend on $k$ (although, this statement is by no means a proof).


Fast hashing algorithm for mapping/quantizing a collection of floats onto a small set of sorted floats With my application, I have

Collection X: thousands of floating-point numbers with the value range [0, 1], not sorted.
Collection Y: 11 floats ranging from [0, 1], sorted.
The size of X is known. Let it be L.

The goal is to quantize X and map it onto Y, so that we get a hash array of indices of Y for X. Eventually Y will be then quantized onto 10 discrete things pointed to it.
An example to make it a bit clearer,

Y = [0.0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0]
X = [0.678, 0.124, ..., 1.0, ., 0.013, 0.475]

I want the algorithm output to be 0-based indices like these:

H(Y[0]) = H(0.678) = 6
H(Y[1]) = H(0.124) = 1
H(Y[n-2]) = H(0.013) = 0
H(Y[n-1]) = H(0.475) = 4

Attempts
Naively, I've tried linear and binary searching for positioning each element of X in Y so that the element is found between an adjacent pair of elements in Y.
However, the performance is not good enough for my application. This quantization happens in a realtime thread that slow computation is undesirable.
Question
What is the best way of this kind of hashing/quantization? X is not sorted.
Thanks!

Take X, multiplied by say 10,000, rounded down to the nearest integer. In plain C, z = (int) (x times 10000.0).
There are 10,000 possible values of z. For most values of z, you can determine the index from z. So create a table with 10,000 entries. In the table, store an index i if you can prove that x should be mapped to i, knowing z, and store -1 if you can’t prove this.
As a result, you get the correct value probably in 9,980 of 10,000 values, and then you use whatever slow algorithm you have for the remaining 1 in 500 values.
PS. The same table size would be used for double precision numbers. Whatever the table size, there will be only few values X that cannot be mapped correctly using this method, maybe 10 or 20. If you take a table of size 10,000 then 99.8% or 99.9% are mapped correctly, and 0.1% or 0.2% need a slow algorithm. The exact same thing happens with double. You could use 1000 entries, then the 10 or 20 failing ones would be 1% or 2%.
And a nice thing is that this method will work however the Y values are distributed. Only if the number of Y values is larger, then you might want to increase the table size.


Defining a predicate on the structure of a string I have the following homework question. (For a bit of context - the study unit is Formal Languages and Automata).

  Define the predicate $\mathrm{pre}(s,t)$ over $s, t\in\Sigma^*$ by induction on the structure of $s$ such that it satisfies the following conditions:
  $$\mathrm{pre}(s,t) = \begin{cases}
\mathsf{true} & \text{if there exists $s'\in\Sigma^*$ such that $s \mathbin{+\!\!+} s' = t$} \\
\mathsf{false} & \text{otherwise}.
\end{cases}$$

Now I have considered two definitions so far. However they both assume things about the structure of $t$, and the way the question is worded implies that we can only assume things on the structure of $s$ (in a recursive way).

The definition is:
$$ \mathrm{pre}(\epsilon,t) := \mathsf{true}\\
   \mathrm{pre}(\alpha.s,\beta.t) := (\alpha = \beta) \wedge \mathrm{pre}(s,t),
$$
and the second, which avoids having $\beta.t$ in the argument:
$$ \mathrm{pre}(\epsilon,t) := \mathsf{true}\\
   \mathrm{pre}(\alpha.s,t) := (\alpha =\mathrm{head}(t)) \wedge \mathrm{pre}(s,\mathrm{tail}(t)),
$$
where I would then define $\mathrm{head}$ and $\mathrm{tail}$ in a recursive way on $\alpha.s\in\Sigma^*$ (so essentially, this does the same thing).

Is there a way this can be done without assuming anything about the structure of $t$?

No, in the recursive case you need to take the first symbol out of $t$, so you need at that point to unfold the structure of $t$.

Note that, as in functional programming, the functions $head$ and $tail$ should be used with great care since they are not total: $head(\epsilon)$ and $tail(\epsilon)$ are undefined. Hence, remember to require $t\neq\epsilon$ every time you use $head(t)$ or $tail(t)$, and to handle the $\epsilon$ case elsewhere.

I would tend to use your first solution, which needs a similar fix.

$$
\begin{array}{l}
{\sf pre}(\epsilon,t):= \sf true \\
{\sf pre}(\alpha.s,\epsilon):=\sf false \\
{\sf pre}(\alpha.s,\beta.t):=(\alpha=\beta)\land {\sf pre}(s,t)
\end{array}
$$

In this way you are not assuming that the second argument is non empty. You are still assuming that it is a word, but that's needed.


(Possibly Easy) Formal Language Question I am looking at a "practice test" for a Theory of Computation class.  It was a test in a previous year.

I am asked to prove that, given L1 and L2 are regular, the union and difference are both regular.

It seems to me that for the union, since all the members of each separate set are regular, and the union consists exactly of all those members, therefore the union is regular.

And since the difference (L1-L2) is just a subset of L1, it is also regular.

This seems awfully straightforward and skips a lot of process.

Is it correct or am I missing something?

The reasoning you give is not formal enough. For the union case, you're just restating the theorem "the union of regular sets is regular since the union of regular sets is regular"; for the difference case, your assertion "a subset of a regular language is regular" is false ($\Sigma^*$ is regular and every language is a subset of $\Sigma^*$).

Regular languages are defined in terms of finite automata. The general approach to a proof is that you look at the definitions of what is given (L1 and L2 are regular, so there are automata...) and show a logical reasoning from that to the definition of what you want to prove (there is an automaton ... therefore L3 is regular).


Proof on lower bound of search in unsorted array with information theory? I know there are proofs using an adversary technique. I've seen other proofs for search in a sorted list using information theory. But I haven't come across a proof using it to prove the lower bound for a search in an unsorted list using information theory.

Here is an informal proof, which you can try to formalize.

Suppose that we’re looking for 1 in an array of length $n$ of 0s and 1s. We consider the following distribution: each element is 1 with probability $1/n$. (You can also try your luck with the uniform distribution over all arrays with a single 1.)

Given the transcript of the algorithm, you can either recover the position of a 1, or deduce that the array consists only of 0s. Since typically there are only few 1s, the entropy of the answer should be $\Theta(\log n)$.

On the other hand, each position you query only gives you $h(1/n) = \Theta(\log n/n)$ information. Hence you need to query $\Omega(n)$ bits.


Is there a way to map a multi-variable structure onto a single range? I want to categorise variants of a structure made up of some number of variable components by mapping it to a unique range. Assume that the individual components all fall within the same base range.
I'm using color as an example for this question as its intuitive to think about but I don't want the question to be specific to that, its just a framework for understanding the problem.
Simple case:
Imagine I have a structure, called C made up of two values (r, b) (red and blue) and I want to categorise variants of C into distinct bands, things like "very red", "quite blue", "slightly blue", "quite red" etc.
In this case I could just map the values by starting at 0 and then adding anything in the r channel and subtracting anything in the b channel, then I would get a final value in a 1 dimensional range somewhere between -1 and 1 (assuming the values for r and b are clamped. Then I could use this output value to categorise it into a band: maybe anything below -0.8 is "very blue" and a value between 0.4 and 0.5 is "somewhat red".
Examples:
(0.1, 0.3) -> -0.2
(1.0, 0.0) -> 1.0
(0.2, 0.9) -> -0.7
Not so simple:
However, if I introduce a third value, so C is made up of (r, b, g), I can't see how I can easily map this to a range which I can make assertions about, like "bluey green" or "reddish blue". Trying to create a solution in code for this (naively) just ends with a complicated set of conditional statements.
One solution I thought might work would be to convert the 3D version of C into a point on a triangle expressed as a weighting of its vertices (where each vertex corresponds to one of C's components), and then convert that point in 2D coordinate space into a categorisation based on where it falls in a sub-shape - which is just a delimited area - on the triangle. So I could say, if the point falls inside this sub-shape on the triangle its "bluey green", if the point falls inside this other sub-shape, then its "reddish blue" etc. However, this does seems like a fairly intricate solution and I'm not sure if I am heading down the wrong path.
Also, I can't see how this would then generalise to putting more and more variables into C.
I don't a have strong intuition for what field of mathematics or computer science I should be looking into to solve a problem like this or how exactly mapping like this work.
If anyone knows how to solve this or what sort of things I should be looking at to solve it, I would really appreciate some advice! Thanks.

If you want to solve this for colors, there are many techniques that are appropriate in that domain.  But you say you aren't really asking about colors, so I'll treat it as an analogy and try to give an answer that is more general (but wouldn't be what I would recommend for colors):
It sounds like you want to cluster the possible values into multiple clusters.  I would suggest you read about clustering algorithms. You'll need to pick a "similarity measure" that measures how similar two structures are.  That is domain-specific and not something we can tell you; you'll have to pick it based on your knowledge of the specific application domain.


L = { | M is a TM and halts on every input after 5 steps exactly } - is L decidable? in order for M to belong to L, it must halts on all inputs after 5 steps exactly. is the problem not decidable ? how can it be proved ? I could not succeed in doing a reduction from Htm as the attempt to count M(w) steps failed.

update:
apparently the language is in R. can anyone provide a proof?

It is NOT NECESSARY to read the whole input for a Turing Machine to halt.

Imagine a Turing Machine M that receives any input such that it reads anything and moves right exactly 5 times. On fifth step it reaches the accept state and halts.

M belongs to L.

Contrary to what I was thinking before, L is indeed decidable.

Consider all Σ $^5$ configurations of the first 5 cells of the tape. For each of these configurations execute 5 steps. If TM is nondeterministic execute 5 steps for all possible paths. If TM does not halt for some configuration (or execution when TM is nondeterministic) reject. Otherwise, accept.

As  Σ $^5$ is finite, L is decidable.


Find N best subset of quotations I am faced with the following problem;

We are provided cost quotations for shipping cost per packet by various shipping companies, let's call these quotations $Q_1 ... Q_k$.
Each Quotation is a $M \times N$ matrix with weights categories of packets along one axis and size categories along the other axis.
We are provided with a list of packets as well with respective weights and sizes such that we can convert the packages to be shipped into a 2d matrix of size $M \times N$ as well based on categorization of each packet and each cell shall contain the relevant number of packets in that weight+size category. Let's call this matrix $P$.

The total shipping cost for all the packets should we chose a shipping company '$i$' is sum of ( $Q_i \times P$ ) where '$\times$' is the element-wise multiplication of the two matrices.

We are required to find a subset of size '$w$' shipping companies (or quotations) such that the overall shipping cost is minimum.

I understand that a brute force algorithm trying out all combinations is not going to work due to the explosion of the number of combinations as '$w$' starts to increase. Moreover, I have also convinced myself that I can not iteratively build out a solution by first selecting two best quotations, merging them into one and then continue to add one more till I reach '$w$'.

Can someone help me find the relevant class of problems and suggest a solution?

This problem is $\textrm{NP}$-hard by a reduction from (the decision version of) set-cover: given an integer $k$, a set of items $I = \{x_1, \dots, x_n\}$ and a collection $S = \{S_1, \dots, S_m \} \subseteq 2^I$ of subsets of $I$, decide whether there is a subset $C$ of $S$ such that $|C| \le k$ and $\bigcup_{S_j \in C} S_j = I$.

Given an instance of set-cover, we can reduce it to your problem as follows:

There are $n$ packages to be shipped. Each package has a unique combination of weight class and category. For simplicity you can think of all the packages being in same category but having different weight classes. I will denote by $W_i$ the weight class of the $i$-th package.
There are $m$ shipping companies. The $j$-th shipping company ships a package of weight class $W_i$, with $x_i \in S_j$, for a cost of $\varepsilon < \frac{1}{n}$ and a package of weight class $W_i$, $x_i \not\in S_j$, for a cost of $1$.
Pick $w = k$.

There is a set-cover of size at most $k$ iff the cost for shipping all the packages using at most $w$ companies is at most $\varepsilon n < 1$.

Indeed, given a set-cover $C = \{ S_{j_1}, \dots, S_{j_\ell} \}$ of size $\ell < k$ we know that $\bigcup_{i=1}^\ell S_{j_\ell} = I$, i.e., if we select the $j_1$-th, $j_2$-th, $\dots$, and $j_\ell$-th shipping companies, we can send each of the $n$ packages at a cost of $\varepsilon$.

On the other hand, if there is a way to send all the packages using at most $w$ shipping companies with a cost of at most $\varepsilon n < 1$ then, for each of the $n$ packages, there must be at least one selected company that ships it with a cost of $\varepsilon$. In other words the sets $S_j$ corresponding to the selected companies are a set-cover of size at most $w = k$.

Notice that any solution has either a cost of $\varepsilon n$ or a cost of at least $1$. Choosing $\varepsilon$ small enough shows that this problem is also inapproximable (in fact, if a shipping cost of $0$ is allowed, you can directly set $\varepsilon = 0$).


Languages A, B ∈ NP-complete such that A⋃B = Σ* I'm pretty new to complexity theory and it seems like I stuck with this problem. We should find language $B$ such that it accepts any words rejected by $A$ but in that case, it seems that $B$ is a complement of $A$ and therefore $B$ belongs to $coNPC$. What is my mistake? Thank you!

Hint: let $A$ be a NP-complete language and $B=\Sigma^*$.  Then $A \cup B = \Sigma^*$.  Is $B$ the complement of $A$?  Does it belong to coNPC?


unambiguous context-free languages and complementation I was considering the following two natural questions about the relationship between unambiguity and complementation for the class of context-free languages:

Is the complement of an unambiguous context-free language also a context-free language?
If a language is context-free, and its complement is context-free as well (i.e., a so-called strongly context-free language), is it the case that the language is unambiguous context-free?

The first question above is motivated by the fact that it holds for deterministic context-free languages, which are a strict subclass of the unambiguous context-free languages.

Both questions turn out to have negative answers, as shown in [this][1] article.
In particular, the authors construct

An unambiguous context-free language whose complement is not context-free.
An inherently ambiguous (i.e., non-unambiguous) context-free language whose complement is context-free.

Consequently, there is no relationship between the notion of unambiguity for context-free languages and the complementation operation.

[1] The Independence of Inherent Ambiguity From Complementedness Among Context-Free Languages" by Hibbard and Ullian, JACM, Volume 13 Issue 4, Oct. 1966, Pages 588-593
 https://dl.acm.org/citation.cfm?doid=321356.321366


Priority Queue - When Prioritizing Take Place? In a Priority Queue we first enqueue according to the priority given to the element? Or we enqueue just like a queue but dequeue high the highest priority element first?
Or both ways are acceptable?

The underlying data structure is usually a heap, and the elements are partially ordered when it's initialized. At that point, the highest priority element is at the root of the heap ready to be popped next. When a new element is added to the heap it is added at the end and partial ordering is done bottom up; and when an element is removed the last element moved to the root and the partial ordering is done top down. So when implemented using a heap, the prioritization is maintained by partial ordering when initialized and when an element is added or removed.


Are models of computation closed under composition? It's common to ask whether a particular class of languages $\mathcal{C} \subseteq \mathcal{P}(\Sigma^*)$, for some alphabet $\Sigma$, is closed under complement, or union, or intersection, or concatenation, or the Kleene star. And those questions seem natural to me, because they're essentially questions about the power of a model of computation that can decide precisely the languages in $C$. However, it seems just as natural to me - perhaps even more natural - to ask whether such a class is also closed under composition.

Here's what I mean by that. If I fix some subset $\mathcal{C} \subseteq \mathcal{P}(\Sigma^*)$ of "decidable" languages relative to some model of computation, for any (finite) $\Sigma$, then I have also fixed some subset $\mathcal{F} \subseteq B^A$ of computable functions, for any languages $A, B$ - because each function $f : A \rightarrow B$ can be viewed as a function $\bar{f} : A \times B \rightarrow \{0, 1\}$. Given that, I would expect that for any reasonable model of computation, if $f : A \rightarrow B$ and $g : B \rightarrow C$ are computable, then $g \circ f : A \rightarrow C$ should be as well. Put in terms of the corresponding languages, I'd expect that if $L_f = \{(a, b) \in A \times B : f(a) = b\}$ and $L_g = \{(b, c) \in B \times C : g(b) = c\}$ are decidable, then $L_{g \circ f} = \{(a, c) : \exists b \in B s.t. f(a) = b \wedge g(b) = c\}$ should be decidable as well.

This seems to me like a natural question to ask of any class of languages. Is it in fact a reasonable question? If not, why? If it is, is there a better way to frame it, one that would make it more clear what we're demanding?

Given that, I would expect that for any reasonable model of computation, if $f : A \rightarrow B$ and $g : B \rightarrow C$ are computable, then $g \circ f : A \rightarrow C$ should be as well.

Let's say our model is quadratic time computation. If $f$ is the function which maps a string of length $n$ to a string of $n^2$ zeroes, then $f$ is computable in our model, but $f\circ f$ is clearly not.

  I'd expect that if $L_f = \{(a, b) \in A \times B : f(a) = b\}$ and $L_g = \{(b, c) \in B \times C : g(b) = c\}$ are decidable, then $L_{g \circ f} = \{(a, c) : \exists b \in B s.t. f(a) = b \wedge g(b) = c\}$ should be decidable as well.

This is a bit of a weird definition since $L_f$ can be much easier than $f$ (e.g., let $f(a)$ be the function that outputs a prime factorization of $a$). $F_l$ is poly-time while it is not known that $f$ is. Let's make $f$ also take an additional input $i$, and then let $f(a,i)$ output the number $i$ together with a factorization of $a$. If we then make $g$ output the $i$th bit of the factorization we end up with $L_f$ and $L_g$ being poly-time computable but $L_{f\circ g}$ being as hard as factorization.


TF IDF Spark values are small after cosine similarity I am creating a software that computes the cosine similarity between 2 strings.

I am using Spark as I have to use Java. I created a Bag of words model and computed the cosine similarity successfully.

Feeding the same sentences to the software and substituting the bag of words model with a TF-IDF the similarity between sentences took a hit. Some similar sentences became not similar.

Example

"a b c"

"a a b c d"

Cosine similarity using Bag of words is 0.871

Cosine similarity using TF-IDF is 0

Is this behavior correct or am I doing something wrong?

From the
documentation:

  Since logarithm is used, if a term appears in all documents, its IDF value becomes 0.

So if you're only considering similarity between two strings, then you only have one document in your corpus, and either your TF value will be 0 (since the word doesn't appear in the document), or the IDF value will be 0 (since the word does appear in the document), thus all terms in TF-IDF will be 0.

If you just have two strings, then cosine similarity should be enough for you - IDF is attempting to weigh the relative importance of each word within the entire corpus (from an information theoretic perspective, it basically treats the word as appearing uniformly across the documents it appears in within the corpus - under that assumption, one can consider IDF to be a form of information gain; i.e., how many bits of information does having this term gain you, relative to selecting a document at random from within the whole corpus. If every document in the corpus has a term, then under that uniform model, providing that term in the query doesn't help you at all in narrowing down your selection).


Efficient bucketing of numbers Assume we have a sorted list of n numbers, I want to map those numbers to m buckets or clusters. For each bucket the average of all numbers in that bucket will be computed. The task is to find a mapping, so that the difference between those cluster averages and the original numbers is minimal.

Example:
List: [1, 2, 3, 4], desired number of buckets: 2
Optimal Solution:
Bucket 0: [1, 2], Average: 1.5, Difference: abs(2 - 1.5) + abs(1 - 1.5) = 1
Bucket 1: [3, 4], Average: 3.5, Difference: abs(4 - 3.5) + abs(3 - 3.5) = 1
Overall Difference: 2

I know how to create a mapping by brute force, but I would need a more efficient algorithm.

Polynomial time is not too difficult.

A "cluster" contains a sequence of 1 or more consecutive numbers from your list. The "badness" of a cluster is defined as the sum of absolute differences between the numbers, and the average of the numbers in the cluster. A sequence of clusters is a list of clusters, containing consecutive numbers from the list starting with the first one. And the "badness" of a sequence of clusters is the sum of badnesses of the individual clusters.

First get a reasonable upper bound for the best clustering to avoid unnecessary work: Just cluster the n numbers into m buckets of equal or almost equal size, then calculate the badness of this sequence of clusters. Call the result B. You might also calculate the badness of a sequence of clusters created by splitting where the largest gaps between consecutive numbers are.

Now for 1 ≤ m' ≤ m, and for 1 ≤ n' ≤ n - (m - m'), calculate the best sequence of m' clusters covering exactly the first n' numbers, and its badness. For m' = 1 that's trivial, because the cluster consists of the numbers 1 to n'. For m' > 1 it is more difficult: The best clustering using m' clusters to cover 1 to n' consists of the best clustering using m'-1 clusters covering 1 to n'' for some n'' < n', plus the cluster n''+1 .. n'. You calculate the badness of this for n'' = n'-1 down to m'-1. All these badnesses can be calculated in O (n), so the best badness for m' and n' can be found in O (n).

In total, you find the optimal badness for m clusters covering 1 to n in $O (n^3)$. If you take advantage of the upper bound B found earlier, and consider that any result that leads to a badness > B can be ignored, you can probably save significant amount of time.

PS. How to find the badness for different clusters each in constant time: Let's say you want to find the badness of a cluster covering the numbers from l to r, for l = r, r-1, r-2, ..., 1. Start with l = r. The sum of items in the cluster is $C = a_l$. The badness is 0. Let s = l. Then the sum of items at indices < s is $S = 0$.

Now replace l with l-1. Increase C and S by $a_l$. The average A of items in the cluster is C / (r - l + 1). As long as $a_{s-1} ≥ A$ replace s with s-1, and subtract $a_s$ from S. The badness in the cluster is C - 2S + ((2s - l - n - 1)A (unless I made some mistake).


Dividing large numbers modulo m I have numbers $a$, $b$ and $m$, and I need to get the result of $\ \dfrac{a}{b} \mod m$.

The catch is that while $m \leq 10^9$, $a$ and $b$ can get extremely large ($2^{100,000}$), so I'm keeping them as a multiset of their prime factors.

I read about modular multiplicative inverse but I haven't found a way to use it in this problem and would appreciate any help.

Also, note that $m$ is not necessarily prime;

If $a = \prod_i a_i$ and $b = \prod_j b_j$ then $$\frac{a}{b} \pmod{m} = \prod_i a_i \pmod{m} \times \prod_j b_i^{-1} \pmod{m},$$
where the products on the right are performed modulo $m$.


Understanding the reduction of REGULARTM from ATM REGULARTM is defined as below:

REGULARTM ={〈M〉| M is a TM and L(M)is a regular language}.

I am trying to understand the proof of REGULARTM being undecidable from Sipser's book "Introduction to the Theory of Computation". The book says:

We let R to be a TM that decides REGULARTM and construct TM S to decide ATM. Then S works in the following manner.
S = “On input〈M,w〉, where M is a TM and w is a string:

1.Construct the following TM M2.

    M2=“On input x:
        1.If x has the form 0^n1^n,accept.
        2.If x does not have this form, run M on input w and accept if M.”
2.Run R on input〈M2〉.
3.If R accepts,accept; if R rejects,reject.”

The problem that I am facing is in the 2nd substep of the 1st step which says:

If x does not have this form, run M on input w and accept if M.

What if M does not halt on w? Then the decider S that we are building would not halt.

Let's look just at $M_2$ for the moment. If $M$ accepts $w$, then $M$ will accept strings of the form $0^n1^n$ in step (1) and everything else in step (2). In other words

If $M$ accepts $w$, then the language $L(M_2)=\Sigma^*$, which is of course regular.

Now if $M$ doesn't accept $w$, then $M_2$ will accept all and only strings of the form $0^n1^n$, so $L(M_2) = \{0^n1^n\mid n\ge 0\}$ and this language is certainly not regular.

The important thing here is that we don't have to run $M$ on $w$ to decide its behavior: the behavior is determined solely by whether $M$ accepts $w$ or not. Since $R$ was assumed to be a decider, it doesn't have to run $M$ to determine whether the language of $M_2$ is regular or not; because $R$ is a decider it is by definition assumed to be able to tell that.


What is the correct way to define time constructible functions? Sipser defines a time constructible function as

  $f(n)$ is time constructible if there exists a turing machine which given input $1^n$ writes value of $f(n)$ in binary to the output tape in $O(f(n))$ time.

whereas Sanjeev Arora and Barak defines it as

  $f(n)$ is time constructible if there exists a turing machine which given input $1^n$ writes value of $1^{f(n)}$ in binary to the output tape in $O(f(n))$ time.

I am unable to see how are these two definitions equivalent. Isn't there a case where writing value in binary takes less time that writing it in unary ? Also what is the reason for inputs being given in unary rather than binary or some other base $k > 2 $ ?

The two definitions are probably equivalent (perhaps $f(n)$ need be not too small): given $f(n)$ in binary you can write $1^{f(n)}$ in $O(f(n))$ time, and vice versa. The ideas are as follows.

Binary to unary: Inductively construct $1^{b_m b_{m-1} \ldots b_{m-t}}$, where $b_m\ldots b_0$ is the binary representation of $1^{f(n)}$. At each step we need to roughly double the string of 1s, and in stage $t$ this takes roughly $O(f(n)/2^{m-t})$ time. Taking into account all stages, we get roughly $O(f(n))$.

Unary to binary: Construct the binary representation of $f(n)$ from LSB to MSB by repeatedly dividing $f(n)$ by two. The $t$th division by two requires time $O(f(n)/2^t)$, so overall this runs in time roughly $O(f(n))$.

As to why the input is in unary rather than in binary, this ionly affects small $f(n)$; as we have seen, converting between $1^n$ and $n$ should take time $O(n)$, and this is affordable as long as $f(n) = \Omega(n)$.


Polynomial hierarchy: inclusion between spaces Using the definition for the polynomial hierarchy:

$$ \Sigma_{i+1}^P = NP^{\Sigma_i^P} $$
$$ \Pi_{i+1}^P = coNP^{\Sigma_i^P} $$

I have been asked to to show that:

$$ P^{\Pi_k^P } \subseteq \Pi_{k+1}^P $$

I don't really have many ideas on how to go for it:

by definition $ P^{\Pi_k^P } $ is the set of languages accepted by a $PTIME$ deterministic TM with an oracle answering queries in $\Pi_k^P$, while $\Pi_{k+1}^P$ is the set of languages accepted by a universal alternating TM, with an oracle answering queries in $\Sigma_k^P$.
If I could use a universal ATM $M_A$ to simulate a DTM (and I would say I can't) then I should be able to recognize a language $L \in P^{\Pi_k^P}$ by noticing that $L$ is accepted by a DTM $M$ that uses the oracle $O$ (that answers about $\Pi_k^P$), thus taking a universal ATM $M_A$ to simulate $M$ and another universal ATM $M_O$ (accepting queries in $\Pi_{k+1}^P$) to simulate the oracle (since $\Pi_k^P \subseteq \Pi_{k+1}^P $).

But I really think this reasoning cannot be done, as actually I'm not using the oracle…how should I approach the problem?

Using the definition of Papadimitrou for polynomial hierarchy, or for that matter from wiki, the proof is really simple. $\Delta^P_{k+1} = P^{\Pi_k^P} \subseteq CoNP^{\Pi_k^P} = CoNP^{\Sigma_k^P} = \Pi^P_{k+1}$. Similarly $\Delta^P_{k+1} \subseteq \Sigma^P_{k+1}$.

But if the definition of polynomial hierarchy is done by alternating quantifiers than also we can prove it in the following way. The proof follows the book "Computational Complexity" by Arora and Barak, yet you have to flip a few $\exists$ and $\forall$, and do some negations. Assume equal fixed polynomial length certificates in the following proof.

We know that $P^{\Pi_k^P} = P^{\Pi_k^{SAT}} = P^{\Sigma_k^{SAT}}$.

Suppose that $L$ is decidable by a polynomial-time DTM $M$ with oracle
access to $\Sigma_k^{SAT}$.
Then, $x$ is in $L$ if and only if there exists a sequence of
oracle answers that makes $M$ accept $x$. That is, if $a_1 , . . . , a_m \in \{0, 1\}$ is a sequence of (correct)
answers  to oracle queries on input $x$, that is, the machine $M$
receives $a_i$ as the answer to its $i$ th query, then
(1) $M$ reaches the accepting state $q_{accept}$ and (2) all the answers are correct. $m$ is the maximum number of oracle queries.

We can modify DTM $M$ so that it will make exactly $m$ queries for the given input size $|x|=n$, i.e $m$ is not varying depending on the outcomes of the oracle. $m$ will be (less than) a polynomial in $n$. $m$ can also be made polynomial time computable by possibly taking a larger value. The proof is made further difficult because there are polynomial number of queries and each $i$-th query may be different depending on the answers of previous queries. Also we need to convert $\exists a_1, a_2,...$ to $\forall a_1,a_2,...$ is the proof by Arora and Barak.

Let $\phi_{i,a_1,a_2,...,a_{i-1}}$ denote the
$i$-th query that $M$ makes to its oracle when executing on $x$  receiving
answers $a_1 , . . . , a_{i-1}$ . $\phi_{i,a_1,a_2,...,a_{i-1}}$ can be generated by a turing machine (which is similar to $M$ in some ways) in polynomial time. Then, the condition (2) can be phrased as follows:

if $a_i = 1$ then  $ \exists u_1 \forall u_2 ... \phi_{i,a_1,a_2,...,a_{i-1}}(u_1,u_2,...,u_k ) = 1$
and if $a_i = 0$ then $ \forall v_1 \exists v_2 ... \phi_{i,a_1,a_2,...,a_{i-1}} (v_1,v_2,...,v_k ) = 0$.

Now we have the following:

$x \in L$
iff $\forall  a_1 , . . . , a_m \in \{0,1\}$
$\exists i \in [1..m]$ if $a_i = 1$ then $\forall U_i^1 \exists U_i^2, \forall U_i^3,...\phi_{i,a_1,a_2,...,a_{i-1}}(U_i^1, U_i^2,U_i^3,...,U_i^k) = 0$  OR
$\exists i \in [1..m]$ if $a_i = 0$ then $\exists V_i^1\forall V_i^2, \exists V_i^3,...\phi_{i,a_1,a_2,...,a_{i-1}} (V_i^1,V_i^2,V_i^3,...,V_i^k) = 1$
OR $M$ accepts $x$ using answers $a_1 , . . . , a_k$

This implies that $L \in \Pi_{k+1}^P$ since $\phi_{i,a_1,a_2,...,a_{i-1}} \in \Sigma_k^{SAT}$. ( You can club all quantifiers as $\forall a_1 , . . . , a_k , U^1_1 , U^1_2 . . , U^1_m \exists V^1_1 , . . . , V^1_m, U^2_1, U^2_2, ... U^2_m \forall V^2_2,..., V^2_m, U^3_1, ...U^3_m \exists ...$ , the certificates are still polynomial).

We can actually prove $NP^{\Sigma^P_k} = \Sigma^P_{k+1}$ and $CoNP^{\Pi^P_k} = \Pi^P_{k+1}$ using similar methods if I remember correctly.

The inclusion graph is given pictorially below,


Removing conflicts of LR(1) parsing tables S' -> S $

S -> I ; S
S -> return E ; S
S -> return I ; S
S -> ''

I -> id
I -> id = E
I -> id = I

E -> C && C
E -> C || C
E -> ! C
E -> C

C -> A > A
C -> A < A
C -> A >= A
C -> A <= A
C -> A == A
C -> A

A -> T A'
A'-> + T A'
A'-> - T A'
A'->''

T -> F T'
T'-> * F T'
T'-> / F T'
T'->''

F -> id
F -> const
F -> ( A )

This is supposed to be a LR(1) grammar, but its LR(1) parsing table have a conflict on the ; symbol column: it has both a shift and a reduction transition. How this conflict can be removed?

The ambiguity comes from

I -> id

because that rule means that both I ans E derive id, which in turn means that return id could be a derivation of either:

S -> return E ; S

or

S -> return I ; S

Also, id1 = id2 could be derived from:

I -> id = E

or

I -> id = I

It doesn't make sense for id to be a statement if id + 3 is not; I'd just drop the I -> id production.


Iterative merge sort I was asked to perform merge sort by iterative method. I solved it as follows: I first stored each of the elements of the array given in another array say $A$. Then I sent entries of $A$ two by two for merging(was given that the function for merging is known and it merged two arrays at a time). This function returned the merged array which I stored in another array $B$. After I was done with all the elements of $A$ I deleted $A$ and copied each of the entries of $B$ in $A$.I allocated memories for $A$ and $B$ dynamically. I repeated this for $log(n)$ times and each time I halved the size of $A$ and $B$. Is my algorithm correct??

I suggest you try to run your algorithm on a few small arrays and see if it works.
Merge sort can be implemented in-place, and the same is true in your case.
Consider the recursive version of merge sort. Apart from calling itself recursively, the only other operation is merge. See if you can make a sequential list of all calls made to merge (with their parameters).


What is the generating function for the sequence $\{kH_k\}_{k \geq 1}$ I am trying to answer exercise 3.1 from Sedgewick and Flajolet's "Introduction to the Analysis of Algorithms".  That is, I am trying to find the Ordinary Generating Function for the sequence:

$$\{kH_k\}_{k \geq 1}$$

I think that the generating function for this sequence is:

$$H_1 + 2H_2z + 3H_3z^2 + 4H_4z^3 + ...$$

which abbreviates to

$$\sum_{n \geq 0} (n+1)H_{n+1}z^n $$

By inspection, I see that this has the form of the Index Multiply operation on OGFs.  This means that our generating function can be obtained by differentiating the OGF for the sequence

$$\sum_{n \geq 0}H_n z^n$$

I know that this

$$\sum_{n \geq 1}H_n z^n$$

has a well known OGF. But that is for the range $n \geq 1$, and our sequence has range $n \geq 0$.  If I split off the first term $n = 0$, we get the sum:

$$H_0 + \sum_{n \geq 1}H_n z^n$$

And it's now that I've lost my confidence.  Is the method I've outlined above the right way to go in finding the desired OGF?  If it is OK, it seems to rest on the existence of a zeroth Harmonic number.  Is there actually a zeroth Harmonic number $H_0$?

Thanks.

We know that a generating function for the Harmonic series is:

$$
\sum_{i =1}^{\infty} H_i z^i = -\frac{\log(1-z)}{1-z}
$$

you may verify it by taking the MacLaurin expansion.

Taking the derivative with respect to $z$:

$$
\frac{d}{dz} \left ( \sum_{i =1}^{\infty} H_i z^i \right ) = \frac{d}{dz} \left ( -\frac{\log(1-z)}{1-z} \right )
$$

yields:
$$
\sum_{i = 1}^{\infty} iH_i z^{i-1} = \frac{1 -\log(1-z)}{(1-z)^2}
$$

Notice that LHS is exactly the formal series you mentioned.