Can the algorithm be optimized? I am new to backtracking and recursion. I have seen numerous explanations on how on to find the minimum number of coins needed to make a particular amount. This involves a top down dynamic approach with mermoization and a bottom up using dynamic programming. Even the brute force apporach always starts using a top down approach breaking the problem down into smaller sub problems and then caching.

However, I have written the following algorithm that is not optimized to do the same but cannot figure out how to apply memoization. Is it even possible?

My basic algorithm is I start from sum = 0 and keep count of how many coins I have used by adding coin values and then returning the minimum count.

//function is called with sum = 0, coins = 0 and minCoins = Integer.MAX_VALUE
//coins[] contains the different coin denominations and target is the desired amount
// count is the number of coins that have been used

public static int makeChangeBacktracking(int sum, int[] coins, int target, int count, int minCoins) {

        if(sum == target) {
            return count;
        }

        for(int coin : coins) {
            //choose
            sum+= coin;
            //explore
            if(sum <= target) { //if it is greater than the target then why recurse???
                int c = makeChangeBacktracking(sum, coins, target, count + 1, minCoins);
                if(minCoins > c) {
                    minCoins = c;
                }
                //undo
                sum-= coin;
            }
        }
        return minCoins;
    }

I would like to apply any technique to improve the run time of the above algorithm. A clear explanation of whether or not memoization or other optimization techniques can be applied to this to speed up would be helpful.

A simple and efficient algorithm would be (correct me if I'm wrong):

1) Find the biggest valued coin just below that particular amount
2) Do the same thing with amount - coin_chosen
3) Repeat until convergence

Does this solve your problem?

e.g   Available coins: 1p,2p,5p,10p,20p,50p,£1 ...
47p -> -20p -> 27p -> -20p -> 17p -> -10p -> 7p -> -5p -> 2p -> -2p -> 0p

There are other less efficient ways to do this like maybe using genetic algorithms but I guess this would be the quickest ...


Proving complexity by reduction using strongly NP-hard problem I have a decision problem $X$ of which I think I can show its complexity by using a reduction from a problem $Y$ that has been shown to be strongly NP-hard.

I tried to follow the same procedure as for proving NP-completeness which I try to summarize here:

Show that problem $X$ is in NP (polynomial time verifiable)
Make the Karp reduction from a known NP-complete problem by finding a poly-time algorithm that transforms the instances $y$ of $Y$ to instances $x$ of $X$
Show correctness of algorithm: Show that for every yes/no answer to an instance of $Y$, the algorithm also returns yes/no

The problem I'm currently facing concern point 1 and 2:

I'm sure that $X$ is in NP, but $Y$ is not necessarily, right? Is it a problem when I try to reduce an NP-hard problem to an NP-complete one?
The strongly NP-hard problem $Y$ is not necessarily NP-complete, right? Can I still use $Y$ here?

Another open question regards the fact that $Y$ is strongly NP-hard:

Assuming that I can do the reduction as outlined above, is then $X$ also strongly NP-complete?

I will assume that your definition is the one on Wikipedia.

We wish to prove that $X$ is strongly NP-Complete. Here's how you do that. First, show that $X$ is strongly NP$^1$. Next, find a strongly NP-Complete problem $Y$ and reduce $Y$ to $X$. That is, provide an algorithm which takes an instance $y$ of $Y$ and produces $f(y)$ such that if $y\in Y$ then $f(y)\in X$ and otherwise, if $y\not\in Y$ then $f(y)\not\in X$.

I remember in which way to reduce a problem (was it $X$ to $Y$ or $Y$ to $X$?) by framing it as a conversation which I've laid out here in this other answer(link): someone challenges me by saying $X$ is easy. Then I say, nonsense, if $X$ were easy, then I could solve very hard problem $Y$. And then I show how to do that: I take an instance of $Y$, rewrite it into an instance of $X$, and then you're done. You've shown that $X$ is at least as hard as $Y$, so we write $Y\leq X$.

$^1$ best I can figure, strongly NP means it has logarithmically-sized certificates


When directed graph is linear, return the nodes in order. Otherwise fail The Problem

I have a set of edges (a, b), where a and b are nodes in a directed, acyclic graph (DAG).

The number of edges is guaranteed to be the number of nodes - 1.

I am looking for an algorithm that finds a sequence of nodes [n_1, ... n_n] so that the sequence contains all nodes in the graph, and that all edges (n_i, n_i+1) for 0 < i < n exist in edges.
If that sequence is not possible because the given set of edges is not equal to the set of edges required, then I need an error to be thrown.

Edit: the graph may have an arbitrary number of disconnected components. I obviously don't consider a graph with multiple disconnected components as linear.

Ideas so far

Note that I am checking that the number of edges is exactly the number of edges required for such a sequence to exist. As a result, the algorithm can fail when there are two edges that share a source or a destination. However, I still need to get that sequence.

I realize that topological sort returns a linear order of a directed graph, which satisfies my requirements. However, I still want to fail when the graph is not exactly linear like that, instead of getting a linear order anyways.

Maybe I can validate, then do a topological sort. But that sounds inefficient. I am also not sure about the formal names of things in this problem, so it's hard to simply look up an algorithm. I feel like I am missing some simple connection or trick here.

Could you provide me with an algorithm that accomplishes this? I'll take pseudocode or any language of your choice.

Here is a quite non-optimal algorithm, to get you started.

Go over all edges $(a,b)$. For each edge, go again over all edges, and check how many times $a$ appears. Stop once you discover $a$ that appears only once (if this never happens, reject). We will take $n_1 = a$.

Go over all edges again, looking for the unique edge $(n_1,b)$ in which $n_1$ appears. Take $n_2 = b$.

Go over all edges again, looking for an edge $(n_2,c)$ in which $n_2$ appears on the left (if there is no such edge, reject). Take $n_3 = c$.

Continue in this way, finding $n_4,\ldots,n_n$.

This algorithm runs in $O(n^2)$. Using hashing, you should be able to improve it to $O(n)$.


Are there techniques to know how many times loops like these will run? How do you evaluate how many times some loops will run, when you start to complicate the boundaries conditions? For example, take this function:

def f(n):
    s = 0
    for i in range(n):
        for j in range(i, (n + i**2) // (n - i) + 1):
            s += 1
    return s

for i in range(10):
    print(i, "->", f(i))

Output:

0 -> 0
1 -> 2
2 -> 5
3 -> 10
4 -> 17
5 -> 28
6 -> 42
7 -> 60
8 -> 83
9 -> 109
```

If you approximate this as an integral of the second for loop you get, substituting $k=(n-i)$:

$$I_n = \int_1^n \frac{n+(n-k)^2-(n-k)+1}{k} dk = \int_1^n 1+\frac{(n-k)^2+1}{k} dk$$

according to WA, the corresponding antiderivative is of the indefinite integral is:

$$(n^2+1)log(k) + \frac{1}{2}k(k-4n+2) +C$$

Thus, evaluating at $k=1$ and $n$ we get:

$$I_n = (n^2+1)log(n)+\frac{-3+6n-3n^2}{2}$$

So, the discrete sum should approximately reflex that. I graphed it out on desmos, and it seems to show that the exact error grows infinitely, they are asymptotically equal.


Constructing a PDA for the language $\{a^mb^n | m > n\}$ i saw in a book how to construct a PDA for a case with m is equal to n . It's pretty simple, just push a symbol for every a and pop this symbol for every b that the PDA reads. But, i don't found a way to construct a PDA for this particular case. Every help is welcome.

You can think about the scheme you proposed (push a symbol for every a, pop for every b) as using the stack as a counter. When you see an a, you increment the counter (push a symbol onto the stack) and when you see a b, you decrement the counter (pop from the stack). In the case where $m=n$, the stack should be empty after processing the whole string, or in other words the value of the counter should be 0. Following the same scheme, how would we know from the count that $m > n$? What would the stack have to look like in that case?


Sort complexity expressed via distinct number of elements I am reading Probabilistic counting algorithms for database applications. In the introduction an algorithm for finding an intersection is specified:

Sort A, search each element of B in A and retain it if it appears in A.

It is claimed that if a, b are number of elements in A and B, and $\alpha, \beta$ are the number of distinct elements in A, B then the complexity of this algorithm is $O(a\log\alpha + b\log\alpha)$. My question is, why the sorting of A is only dependent on the number of distinct elements? Is there some kind of algorithm I am not aware of? If so, why the same algorithm could not be used for the second strategy? The second strategy is:

Sort A and B, use merge-like operation to discard duplicates.

For this algorithm the complexity is $O(a\log a + b\log b + a + b)$ which makes sense to me.

You can use a balanced binary search tree to sort $A$ in time $O(a\log\alpha)$ by going over the elements of $A$, for each element searching whether it already appears in the tree, inserting it if it isn't already there. You can then perform the second stage in $O(\log \alpha)$ per element of $B$, for a total of $O(b\log\alpha)$.

If you are allowed to use hashing on the elements of $A$ and $B$, then you can use a dynamic hash table to compute the intersection in expected $O(a+b)$ time by using a similar strategy.


$\mathsf{PSPACE}$ membership in exponentially many steps? I am trying to argue that a certain problem is in $\mathsf{PSPACE}$ and my question is, essentially, whether it is ok to have an algorithm that takes an exponential number of steps as long as, overall, the whole thing stays in polynomial space.

The context for this is that I have a naive algorithm which, it seems to me, shows $\mathsf{PSPACE}$ membership, but I am not entirely certain of the logic behind it.

I can be more concrete. Say we have a set $M$ and a transitive binary relation $>$ on $M$. $M$ is exponentially large (think all possible assignments), and $>$ can be partial and have cycles. If $a>b$, for $a,b\in M$, then we say that $a$ dominates $b$. If $a$ dominates every element in $M$ (including itself), we say that $a$ is dominating.

I know that, given $>$ and some $a\in M$, determining whether $a$ is dominating in $>$ is $\mathsf{PSPACE}$-complete. Call this the $\mathsf{DOMINATING}$ problem, and we can take it as a given that it is $\mathsf{PSPACE}$ complete.

The problem I am faced with is now is what we could call the $\exists\mathsf{DOMINATING}$ problem:
given $>$, determine whether there exists a dominating element in $>$.

My naive algorithm for $\exists\mathsf{DOMINATING}$ is as follows: take every element in $M$, ask whether it is dominating in $>$, and stop if one is found.
This, it seems to me, is in $\mathsf{PSPACE}$: even though we might have to go through an exponential number of $\mathsf{PSPACE}$ queries, we stay in polynomial space throughout.

whether it is ok to have an algorithm that takes an exponential number of steps as long as, overall, the whole thing stays in polynomial space.

Yes, of course. Polynomial space means exactly what it says.

The only reason you should worry is if you think that your algorithm takes more time than $2^{n^c}$ for all $c$.  In that case, it must either use more than polynomial space or loop forever since, there are only $|\Sigma|^{n^k}$ configurations of a tape of length $n^c$ using alphabet $\Sigma$, only $n^k$ possible head positions and only a constant number of possible states. That means there are only $|Q|n^k|\Sigma|^{n^k} \leq 2^{n^c}$ (for large enough $c$) possible configurations for a polynomial space Turing machine so if it runs for more than that many steps, it must have seen the same configuration twice so it must be in an infinite loop.


Hill Climbing Search - 8 queens In that picture, I am having trouble counting why there are 17 pairs of queens. I can only count 14. I counted 10 diagonal pairs and 5 horizontal pairs. Can someone please elaborate on this?
I am not exactly sure how it was numbered, but I believe the numbers on the board represent the new number of pairs that are attacking each other if a queen in that column were to move to that square.

5 - Horizontal attacks
9 - Diagonal attacks of slope -1
3 - Diagonal attacks of slope +1
-
Total 17 pairs of queens attacking each other.

And yes, the numbers in each square correspond to number of attacking pairs of the queen if the queen in the corresponding column is moves to that location.


Does a recursive call reset to the beginning of the method if the call is in the middle? Or does it finish the method? Sorry for noob question.

A recursive call is no different than any other call. Here is what happens when you call procedure X:

The current address is pushed into the stack.
Jump to the beginning of X.
When X concludes, pop the return address from the stack, and jump there.

It doesn't matter whether X is the current procedure or a different one.


Do the Turing machines involved in Chruch-Turing thesis have to halt on all the inputs? The following is Church-Turing Thesis from two books.

Is it correct that

The first book seems to say that the Turing machines involved in the thesis may or may not halt on a given input,
the second book says that the Turing machines involved in the thesis must halt on all the inputs?

Do the two books contradict each other? Why?

Thanks.

From Ullman and Hopcroft's Introduction to Automata Theory, Language, and Computation 1ed 1979

  Note that one TM may compute a function of one argument, a different
  function of two arguments, and so on. Also note that if TM M computes
  function f of k arguments, then f need not have a value for all
  different k-tuples of integers. ...

  In a sense,

  the partial recursive functions are analogous to the r.e. languages, since they are computed by Turing machines that may or may not halt on
  a given input.
  The total recursive functions correspond to the recursive languages, since they are computed by TM's that always halt.

  ...

  The assumption that the intuitive notion of "computable function"
  can be identified with the class of partial recursive functions is
  known as Church's hypothesis or the Church-Turing thesis.

From Lewis and Paradimitriou's Elements of The Theory of Computation

  However, we have also seen in the last chapter that not all Turing
  ma machines deserve to be called "algorithms:" We argued that Turing
  machines that semidecide languages, and thus reject by never halting,
  are not useful computational devices, whereas Turing machines that
  decide languages and compute functions (and therefore halt at all
  inputs) are. Our notion of an algorithm must exclude Turing machines
  that may not halt on some inputs.

  We therefore propose to adopt the Turing machine that halts on all inputs as the precise formal notion corresponding to the intuitive
  notion of an  "algorithm".  Nothing will be considered an algorithm
  if it cannot be rendered as a Turing machine that is guaranteed to
  halt on all inputs, and all such machines will be rightfully called
  algorithms. This principle is known as the Church-Turing thesis.

The Church-Turing thesis is an informal notion so it is not strange to see different authors taking slightly different positions.

To me, the second definition makes a bit more sense: CT tries to characterize "functions that are calculable in all cases", and for instance, we don't consider lets say, second order unification computable. The halting problem also falls in that category so I really wonder what do the authors mean.

Some interesting recent discussion about CT can be found in this thread: http://www.cs.nyu.edu/pipermail/fom/2016-August/020027.html


What is the definition of a property? I have seen 2 answers in stackoverflow:

A "trivial" property is one that holds either for all languages or for none.
The property is trivial if it contains every TM, or if it is empty.

My problem is: Saying that a property is trivial if it contains every TM is not the same as saying that a property is trivial if it contain all the languages (including non RE languages).

Same as for: Saying that a property is trivial if it is does not contain any TM languages is not the same as saying that a property is trivial if it is empty.

We call a set of languages, $P\subseteq 2^{\Sigma^*}$, a property. If you think of this subset as the set of languages who satisfy some property, then we can simply say that a language $L$ satisfies the property iff $L\in P$.

Rice theorem tells you that you can't, given a Turing machine $M$, check if $L(M)$ satisfies some non trivial property $P$, i.e. $P\neq \emptyset$, $P\nsupseteq RE$. Note that Shaull makes a distinction between semantic and syntactic properties in the comments. To the best of my knowledge, the standard definition of a property in the context of Rice's theorem is a set of languages.


Minimum pumping length of regular language I know the method to the find the minimum pumping length of regular language by constructing minimal DFA and finding the number of states but I am not able to quite understand why is it working.

For example, $L = (10)^*$.
Here minimum pumping length is 1 by constructing DFA.
But by pumping lemma, how can there be a string of length 1 belonging to $L$? As pumping lemma says the string $S$ should be such that $|S| \le p$ and $S$ should belong to $L$, where $p$ is the pumping length, and here there is no string of length 1 belonging to $L$.

Your example in fact demonstrates that the pumping length can be smaller than the number of states in the minimal DFA. In your case the minimal DFA contains 3 states, but the pumping length is 2.

The pumping length of a language $L$ is the minimal $p$ such that every word $w \in L$ of length at least $p$ can be written as $w = xyz$, where $|xy| \leq p$, $y \neq \epsilon$, and $xy^iz \in L$ for all $i \geq 0$.

If $L$ contains no words of length $p$ that's not problematic at all. For example, the pumping length of $\{ w \}$ is $|w|+1$. In that case the pumping property holds vacuously.


Is $\bigcup_{c \ge 1} \mathsf{DTime}(2^{cn})$ closed under polynomial reduction? It's well known $EXP$ is closed under polynomial reduction. It means
$\bigcup_{c \ge 1} \mathsf{DTime}(2^{c^{n}})$ is closed under polynomial reduction. But what about $\bigcup_{c \ge 1} \mathsf{DTime}(2^{cn})$? Is it also closed under
polynomial reduction?

No, this would contradict the time hierarchy theorem. Note that any language in $\mathsf{EXP}$ is polynomial time reducible to some language in $\mathsf{E}$ by padding. Suppose $L\in \mathsf{DTIME\big(2^{n^c}\big)}$, then consider $L'=\big\{x0^{|x|^c}\big|x \in L\big\}$. Obviously $L'\in \mathsf{E}$ and $L\le_p L'$, thus if $\mathsf{E}$ is closed under polynomial time reductions we have $L\in\mathsf{E}$ and consequently $\mathsf{E=EXP}$.


How can I improve this RL algorithm? This is the task: I have a unitary target matrix $T$, to decompose using matrices from a fixed (finite) universal set $\{M_i\}$, e.g. $T = M_6M_3M_9M_0$. The set is universal in the sense that one can reach any unitary with by combining its elements appropriately.

I wrote an RL algorithm with a policy network that I feed with the target $T$ and with the current "state" (i.e. the current product of the matrices that the policy chose), which returns the index of which matrix to pick next. In pseudocode, this is what I wrote:

reward = 0
 state = Identity_matrix
 chosen_indices = []
 for(i=0,max_episode_length,i++):
    prob_dist = policy(state,T)
    k = random_int(prob_dist)
    state = state * M[k]
    reward -= 1
    if ||T-state|| == 0:
        reward += 100
        end_episode()
loss = discounted_rewards * cross_entropy([prob_dist],[one_hot(k)])
minimize(loss)

I repeat this loop for several random examples of $T$ of which I know the decomposition. But, even if I limit $T$ to be a single matrix from the set, the policy learns a couple of them and then it stops learning, i.e. when I pick a new $T$, the average episode reward remains around zero.

I tried fiddling with the learning rate, the discount factor, the width of the policy network, nothing seems to make things work. What am I doing wrong?

There's no reason to think that reinforcement learning would be effective here.  Indeed, the surprise would be if it did work!  Machine learning isn't a magic silver bullet.  I wouldn't expect it to be of any assistance here; the problem relates to deep questions about the structure of the general linear group, which might be quite challenging for your policy network to learn.

Your problem is known as the membership problem for the general linear group, which might be hard (i.e., no efficient algorithm is known), depending on which field you are working over.  See https://cstheory.stackexchange.com/q/38000/5038.  If we take $T=0$ and are working with $n \times n$ matrices, this is called the matrix mortality problem; it is undecidable for $n \ge 3$.  See also https://en.wikipedia.org/wiki/List_of_undecidable_problems#Problems_about_matrices.  So, in the general case, your problem is undecidable.

Obviously, you shouldn't expect your approach to successfully solve an undecidable problem.


Maximize pairings subject to distance constraint I have a list of people's locations on a world map and want to pair nearby people up such that the number of pairs is maximized.

For example, subject to the constraint that paired people are within d=10 miles of each other, I might find 742 pairs from a list of n=3000 people's locations.

Possible considerations:

alright to assume the world is a 2D Euclidean plane
alright to assume n < 100000
the distance constraint can be relaxed, for example to a cost function with a high value after 10
as in real life, people cluster in cities, so there might be many people "0 miles apart" in New York City while people in Wyoming are few and far apart.
any leads on the same problem above but for triplets would be great. That is, the same problem, but instead of two you take three people and group them together, preferably with the constraint still being that the three are contained in a d-diameter disc, though other similar constraints are fine.

A simple approach

calculate all-pairs distances.

in the process create an array of pairs sorted from closest to farthest
in the process, for each person, store a list of people within d miles

greedily pair together the closest unpaired people
repeat the following until no progress has been made for a certain number of loops

find an unpaired person p_1 with closest person p_2 <= d miles of them. person p_2 is currently paired to person p_3.
unpair p_2 and p_3 and pair p_1 and p_2. If any exist, pair p_3 to a closest person p_4 that is unpaired and within d miles.

I'm sure there are many interesting approaches to this problem, and would any love input on what research/search terms I could look into to learn more about it, any ideas for algorithms to solve this, and possibly bounds on how well the above algorithm would work on the problem.

Thank you

You can formulate this as a maximum matching problem in an undirected graph, and then apply standard algorithms for this problem, such as Edmonds' algorithm.  These algorithms are reasonably efficient and should be fast for your parameters, and they are guaranteed to find the optimal collection of pairings.

In particular, the graph is as follows.  You have a vertex for each person.  Draw an edge between two people if they are within 10 miles of each other.  Now, you want a maximum matching in this undirected graph: i.e., a collection of edges (pairs of people) such that no two edges have a vertex in common (each person is paired up with at most one other person), and that is as large as possible.

There's lots written on the maximum matching problem; a search should turn up plenty of additional information.


A question on decidability I have a homework question that is as follows:
L(P) is a language of ASCII input strings for which a given program, P, returns "yes". Is the set of all input strings P decidable, such that P is a decision program and L(P) is decidable?
My intuition leads me to believe that the set is, in fact, decidable but I am having a tough time proving my answer.
Would appreciate any help on this. Thanks

Let $L=\{\langle M \rangle \mid M \text{ is a TM such }L(M)\in R\}$, where $\langle M\rangle$ is the encoding of a TM $M$, and $R$ is the set of all decidable languages. This is the language in question.
Notice that $R\neq \emptyset$ and also since there are languages not in $R$ (like the halting problem), then $R\neq RE$. Simply put, $R$ is not trivial (obviously).
Apply Rice's theorem on the property $"R"$, to directly get that $L$ is not decidable.


How to understand out of bound in the following theoretical context? Consider the following initialization step of loop invariant for merge procedure

Initialization: Prior to the first iteration of the loop, we have
$k=p$, so that the subarray $A[p .. k - 1]$ is empty. This empty subarray contains the k- p= 0 smallest elements of $L$ and $R$, and since
$i = j = 1$, both $L[i]$ and $R[j]$ are the smallest elements of their arrays that have not been copied back into  $A$.

I have doubt in the above statement that if $k=p$, then array $A[p..p-1]$ is impossible and hence the further argument cannot proceed, which didn't happen. Where am I going wrong?

It is often useful to allow arrays of zero length. These are just empty arrays. The length of the subarray $A[i\ldots j]$ is $j-i+1$, so when $j=i-1$, we just get an array of length 0.

Why is this useful? Here are some examples:

An array $A[1\ldots n]$ can always be partitioned into two arrays $A[1\ldots i]$ and $A[i+1 \ldots n]$ of lengths $i,n-i$. This works even for $i \in \{0,n\}$.
We can construct an array $A[1\ldots n]$ inductively using the formula $A[1\ldots i] = A[1\ldots (i-1)] \cdot A[i]$. The base case is the empty array $A[1\ldots 0]$.

Having arrays of negative length makes less sense, and could lead to confusion and errors, since there is no semantics under which the formula $|A[i\ldots j]| = j-i+1$ would hold for them, since array lengths are non-negative.


What is the difference between RAM and TM? In algorithm analysis, we assume a generic one processor Random Access Machine (RAM). As far as I know, the RAM machine is no more efficient than the Turing machine. All algorithms can be implemented in the Turing machine. So my questions are:

If the Turing machine is as efficient as the RAM machine, then why are we not assuming Turing machine for algorithm analysis?
What is the difference between RAM and TM?

Turing machines are not as efficient as RAM machines. A RAM machine can access an arbitrary tape location in $O(1)$. A Turing machine can't. A RAM machine can do arithmetic in $O(1)$ (under certain restrictions). A Turing machine can't.

Turing machines polynomially simulate RAM machines, that is, for some constant $c$, any RAM machine running in time $O(n^k)$ can be simulated by a Turing machine running in time $O(n^{ck})$. (The constant is pretty reasonable, about $2$, depending on the Turing machine model.)


Network flow - minimum flow through edge In my max flow network, I would like to have an edge with upper bound of the flow (a.k.a. edge capacity) $c_{max}$. However, I would also like to add a lower bound for the flow through the edge, $c_{min}$.

I need to be sure that the minimum flow satisfies not only all the upper bounds (capacities), but also all the lower bounds.

Is it even possible? And if yes, which changes do I need to make to my flow network so that the max flow algorithm takes these lower bounds into account?

Yes, it is possible to solve such problems efficiently.  The minimum-cost circulation problem is a generalization of the standard network flow problem, which allows you to set both lower bounds and upper bounds on the flow through each edge.  (You can set all costs equal to 1.)  There are polynomial-time algorithms to solve instances of the minimum-cost circulation problem.

I don't know if there's a simple way to do with a standard algorithm for network flow.


Why is it that every k-tape Turing machine has a 1-tape TM that runs in $O(t^2(n))$? Apparently, for every k-tape Turing machine that runs in time $O(t(n))$, there exists a 1-tape Turing machine that runs in $O(t^2(n))$.

I can see how any multi-tape machine $M$ can be simulated by a 1-tape machine $S$. Just have the tape of $S$ contain all of $M$'s tapes separated by some symbol such as #.

However, why is the running time of $S$ $O(t^2(n))$ if the running time of $M$ is $O(t(n))$? I think it would be $O(t^k(n))$ since there exist $k$ tapes, and we have to traverse through all of them.

In your suggestion you write the tapes next to one another. That has another disadvantage, if one of the tapes runs out of space one has to move the information to extend that space.

The solution is to write different tapes on "tracks", above each another, technically this is done by extending the alphabet to a cartesian product of alphabets. If the original tapes all have alphabet $\Sigma$ (for $i=1,\dots,k)$ and blank $B\in \Sigma$, the single tape simulator has alphabet $\Sigma^k\cup\{B\}$. Additionally one needs to mark the positions of the heads, leading to extra symbols on the tracks.

(edited to include answer to question in comment)


Are all vertices within a strongly connected component with 2 or more vertices part of a cycle? Within a directed simple graph, are all vertices within a strongly connected component with 2 or more vertices part of a cycle?

Suppose it's not the case, it means that there is a node $v$ that is either isolated (contradicts $n \geq 2$) or has an arrow that is incident to it. Let this arrow be from $v$ to $v'$, with no loss of generality. Since we have supposed that $v$ is not part of a cycle, it's impossible to go from $v'$ to $v$, which contradicts strong connectivity.


runtime to a BFS flood-fill with multiple centres? If we have a flood fill algorithm which, given a number of centres reprenting pixels on an image, runs a BFS flood-fill on them, checking the pixels 4 neighbours, changing their colours and adding them onto the queue to have their own neighbours processed if they have not been. What is the runtime, It seems it would be O(n) where n is the number of pixels but some sources have said it should be O(4^n). And how would this runtime change if the number of centres were changed, such that it was a multiple or fraction of n.

Suppose there are n pixels on the screen.

We add the neighbours onto the queue only if they haven't yet been processed.

This way a pixel is added onto the colouring queue only if it hasn't been coloured yet.

Thus a pixel can be added onto the queue for a maximum of 1 time.

So if there are n pixels, then at most n additions would be done to the queue and thus n operations would be needed to colour the entire display.

It doesn't matter if number of centres are increased or decreased since each pixel would need to be added onto the queue at most once.

Thus the complexity would remain O(n) in both the cases.

Sources that claim the complexity to be O(4^n) are considering a brute force approach where we don't remember the pixels we have already coloured and end up colouring it over and over again.


NP-hardness of an optimization problem with real value I have an optimization problem, whose answer is a real value, not an integer such as vertex cover and set cover. Therefore, the decision version of my problem is given an input and a real value $r$.

I have been able to reduce an NP-complete problem to my own problem in polynomial time. I also showed that my problem is NP.

Since the input to the decision problem is a real value, is this reduction valid and can I categorize my problem as NP-complete?

Edit: What if the precision of this real number is limited to $\frac{1}{polynomial(n)}$, which means that the solution is a real number with a polynomial precision.

No, you can not say that your problem is NP-complete.

The reason is that it is not in NP: there is no Turing machine at all (let alone a poly-time (non-deterministic) one) that can solve it because TMs can not handle real numbers.

The reduction may still go through and show that the problem is NP-hard; a subset of the reals should certainly suffice to model the naturals in Vertex Cover or whatever NP-complete problem you use. So it is, in principle, possible to define a computable, poly-time reduction function that does the job. It will output naturals (or integers, rationals, ...), of course, but as long as you are willing to accept these as real numbers you are fine.

This reduction is likely to carry over to restricted versions of your problem (e.g. finite precision) which can be classified in the framework of computabilty/complexity theory.


Given a maze, check if set of points is forming some-type of closed shape Let's say we have given 2-dimensional maze in form of matrix, conisting only of the letters  x and .. For example the following maze:

xxxxx 11111    .....
x...x 1...1    .xxx.
x.x.x 1.2.1    .x.x.
x...x 1...1    .x.x.
xxxxx 11111    .....

Let's group those elements, we will group x's only, such that two elements will be in one group if they share at least one of the 8 sides (4 regular and 4 diagonal). Up here is one way how to group them, now for each of those groups we want to check if they are forming closed figure (in the first maze there is closed figure and in the second there isn't because the area of x's isn't closed).

What I think for the solution

I was thinking that we should find 4 points first that are important for each figure, those are: the top right, top left, bottom left and bottom right nodes, and now check if there is path from the top right to top left and bottom right,
from the top left to bottom left and from the bottom left to the bottom right. But, it turns out that this is not working always.

Label open space in same way you label the x's, if a set of x's touches more than one label it contains a closed space.


Algorithm to get maximal selection set of a collection of sets with a binary relation I have a finite collection of finite sets $\{A_i\}_{i \in I}$. There is a relation $R$ defined on the elements  of those sets (which is not transitive, it is irreflexive, and it is symetric). Suppose we define a related partial choice as a set $\{a_j\}_{j\in J}$ such that:

$J\subseteq I$
$a_j \in A_j, \forall j \in J$
$a_j R a_{j'} \forall j,j' \in J$

That is, it consists of choosing one element for each of some of the original sets, such that all elements are related to each other.

What I need is an algorithm that a computes a related partial choice with maximum cardinality.

An equivalet way  of seeing the problem would be as follows. Given the set $\{A_i\}_{i \in I}$, call a related selection partial function ($RSPF$, for short) any partial function $f : I \rightarrow \cup_{i\in I} A_i$ such that:

$f(i)\in A_i$ for all $i \in I$ where $f$ is defined.
$f(i)Rf(i')$ for all $i,i' \in I$ where f is defined.

If we define $N := max(\{ \#Dom(f) : f \in RSPF\})$. I need an algorithm to efficiently compute an $f$ such that $\#Dom(f) = N$.

In the algorithm, the $\{A_i\}_{i \in I}$ sets can be arrays or sets.

Any Ideas?

Your problem generalizes MAX-CLIQUE, and as such its decision version is NP-complete. To see this, given a graph $G=(V,E)$, take $I=V$, $A_i=V$, and $R=E$.


Constrained Smallest Enclosing Ball Problem Let $X = \{x_1, x_2, ..., x_n\} \subset \mathbb{R}^m$ be a finite set of points. Smallest enclosing ball is a well-known problem that asks for the $m$-ball that covers all $x_i \in X$, while having the smallest radius possible.

I am interested in solving a related, more constrained problem. Namely, in my version, the enclosing $m$-ball's center can not be chosen freely, but is constrained to be one of the points in $X$. In other words, I would like to find the point $x_j \in X$ such that the maximum distance (i.e. the enclosing radius)

$$\max_{x \text{ } \in \text{ } X} \; \lVert x - x_j \rVert$$

is minimized.

Obviously, one can simply compute all distances in $O(m n^2)$ time, and find the desired point. A less naive way to tackle the problem would be to generate a space-subdividing acceleration structure, say a kd-tree. We can do this in $O(m n \log n)$. Then, per-node maximum distances can be computed in $O(f(m, n))$ time, and we can pick the node having the minimum-maximum distance. This method would have a complexity of $O(n (f(m, n) + m \log n))$. Here, $f(m, n)$ is a function that stands for the query complexity of the kd-tree. Therefore, $f(m, n)$ "looks like" $m \log n$ for small $m$, but $m n$ for large $m$.

All in all, we would still be making many repeated (and unnecessary) distance computations. Also, because of how $f(m, n)$ behaves, the latter method degrades to the former for big $m$. Therefore, even the latter solution is not very satisfactory.

Can we do better? What is the best (in terms of time complexity and practical performance) known algorithm to tackle this problem?

I guess one simple approach would be to use any known Smallest Ball algorithm to determine the center of the optimal ball. Then you use kNN-queries to find the closest neighbour, which is likely the required point.
However, you would need to show that the closest neighbour really is necessarily the best point. Maybe you need to actually check a number of candidates within a to-be-determined distance of the virtual center point.

Also, for a practical solution, I wouldn't use a kd-tree. R-Tree (or R*tree/R+tree/X-tree) behave better, so does the PH-Tree (a kind of quadtree).


Using 4-SUM to improve Subset Sum $O(2^{n/2})$ runtime I read k-Sum $k \geq 3$ can be solved in $\approx O(n^{k/2})$

If this is right, why do not have a subset sum solver with a time complexity $O(2^{n/4})$ or better?

That is, enumerating all the subsets from 4 splits, then apply 4-sum to find if some of the four partial lists add up to the target value?

Work through the math; you are off by a factor of two.  Also, you might be confusing yourself by using the same letter $n$ for two different things.

Suppose we have a list of $N$ numbers.  You are proposing to split that into four chunks, where each chunk has $N/4$ numbers.  Enumerating all of the subsets of a single chunk takes $O(2^{N/4})$ time.  Now, you have a 4-sum problem where you are working 4 lists each containing $M=2^{N/4}$ items.  This 4-sum problem can be solved in $O(M^{k/2}) = O(M^{4/2}) = O(M^2)$, and $M^2 = 2^{N/2}$, so your proposed algorithm runs in $O(2^{N/2})$ time.

There is an algorithm for subset-sum that runs in time $O(2^{N/2})$ and space $O(2^{N/4})$.  The algorithm is due to Schroeppel and Shamir.  However, it's running time is still $O(2^{N/2})$, not $O(2^{N/4})$.

I don't think there is any known subset-sum algorithm whose running time is non-trivially better than $O(2^{N/2})$.  Blum, Kalai, and Wasserman have solved a related problem in subexponential time, but it's a different problem.


Entropy and Information Gain for multi attributes Is there any way that for specific dataset I can measure entropy and information gain for two or more attributes together? Let's say we have the following dataset:

$\begin{array}{cccccc|c}
x1 & x2 & x3 & x4 & x5 & x6 & y \\
\hline
0 & 0 & 0 & 0 & 0 & 0 & 0\\
0 & 0 & 1 & 0 & 1 & 1 & 1\\
0 & 1 & 0 & 1 & 1 & 1 & 1\\
0 & 1 & 1 & 0 & 0 & 1 & 0\\
0 & 1 & 1 & 1 & 0 & 0 & 1\\
1 & 0 & 0 & 1 & 1 & 0 & 0\\
1 & 0 & 1 & 1 & 0 & 1 & 1\\
1 & 1 & 1 & 0 & 0 & 0 & 1\\
1 & 1 & 1 & 1 & 1 & 1 & 1\\
\end{array}$

How can I calculate the information gain for $x1,x2$ or $x1,x2,x3$ or $x1,x2,x3,x4$

You can group attributes together, but (assuming you're building some kind of decision tree) your decision tree will no longer be a binary tree, and you probably won't be any better off than just splitting by one attribute. Say for example you group $x_1$ and $x_2$ together, then there are 4 possible values for this new meta-attribute. You can use the same entropy calculation for this meta-attribute, and split on these four values.

But ask yourself this: why would you want to split on multiple attributes at once? Sure, it's true that $y=1$ whenever $x_1$, $x_2$, and $x_3$ are 1, but once you split on this you can't split on any subset of these three (for example, observe that $y=0$ whenever $x_2$ and $x_3$ are zero. If we split on all three variables we'd need two identical subtrees, one for $x_1=1, x_2=0, x_3=0$ and one for when they're all zero.)


Understanding why the polynomial $p(n) = \sum_{i=0}^{k} a_in^i$ is in $\Theta(n^k)$ Hi I've read this lemma in my book:

  Lemma 2.1. Let $p(n) = \sum_{i=0}^{k} a_in^i$ denote any polynomial and assume $a_k > 0$. Then $p(n) \in \Theta(n^k)$

  Proof. It suffices to show that $p(n) \in O(n^k)$  and $p(n) \in \Omega(n^k)$. First observe that for $n > 0$,
  $$p(n) \leq \sum_{i=0}^{k} |a_i|n^i \leq n^k \sum_{i=0}^{k}|a_i|,$$
  and hence $p(n) \leq (\sum_{i=0}^{k}|a_i|)n^k$ for all positive $n$. Thus $p(n) \in O(n^k)$.

  Let $A = \sum_{i=0}^{k-1}|a_i|$. For positive $n$ we have
  $$p(n) \geq a_kn^k -An^{k-1} = \frac{a_k}{2}n^k + n^{k-1}(\frac{a_k}{2}n - A)$$
  and hence $p(n) \geq (a_k/2)n^k$ for $n > \frac{2A}{a^k}$. We choose $c=a_k/2$ and $n_0 = 2A/a^k$ in the definition of $\Omega(n^k)$, and obtain $p(n) \in \Omega(n^k)$.

Can anyone explain me the part $p(n)\in \Omega(n^k)$ of the proof? Why should we divide $a_k\cdot n^k$ by 2? Why can't we take $a_kn^k$ as coefficient of $n^k$? And how do we obtain that $n>2A/a_k$?

The starting point is the inequality $p(n) \geq a_kn^k - An^{k-1}$. We want to deduce from this inequality that for large enough $n$, $p(n) \geq bn^k$ for some $b > 0$. So take any $b > 0$ satisfying $b < a_k$. Since $$p(n) \geq a_k n^k - An^{k-1} = \left(a_k - \frac{A}{n}\right) n^k,$$ we have $p(n) \geq bn^k$ as long as $a_k - A/n \geq b$. As $n \to \infty$, $A/n \to 0$, and so it is clear that the inequality $a_k - A/n \geq b$ holds for large enough $n$. If we want an explicit lower bound on $n$, we can do some algebra to obtain the equivalent inequality $n \geq A/(a_k - b)$.


Undecidability and Countability This question is prompted by Undecidable unary languages (also known as Tally languages)

How does the countability of a language imply (un)decidability?

Countability doesn't imply (un)decidability: the set of even numbers and the set of codings of Turing machines that halt on input zero are both countable but the first is decidable and the second isn't.

Conversely, for any finite alphabet $\Sigma$, the set $\Sigma^*$ of all finite strings over $\Sigma$ is countable, since each string can be seen as a natural number written in base $|\Sigma|$. Therefore, any language (i.e., any subset of $\Sigma^*$) is also countable.

The only place that uncountability comes in is that there are uncountably many different languages over any finite $\Sigma$. This gives an immediate proof of the existence of undecidable languages: there are uncountably many languages but only countably many Turing machines.


Not able to prove non regularity using pumping lemma $L$ = $0^p1^q0^p$. Where $p, q \geq 0$

Here for any string $w \in L$ , I can have $u$=$0^p$, $x$ = $1^q$ and $v$= $0^p$ and $x^i$ will belong to L for all $i \geq 0$

So how do I prove it to be non regular using pumping lemma as there doesn't exist a string $w \in L$ which cannot be decomposed into the form $ux^iv$ for all $i \geq 0$.

Don't forget that the pumping lemma guarantees that $|ux| \leq n$, where $n$ is the pumping length (which is also a lower bound on the length of $w$). You can use this condition to forbid the situation you describe.


Sliding window protocol when number of packets is equivalent to the window size I am currently taking a course in computer networking and I am curious about the following situation:

Given $n$ packets and a window size of $n$ (i.e., the number of packets is equivalent to the window size), what would happen in the following scenario?:

Packet 1 is sent by Host A and the corresponding ACK is received. Do the window boundaries need to be updated to $[2:n + 1]$ or would it remain as $[1:n]$ (as there would be $n - 1$ remaining packets (strictly less than the window size, $n$)?

Definitely, the window boundaries will be updated, in other words, the window will be shifted regardless of the fact remaining packets are strictly less than window size.

But the main point is after shifting,window will not be fully      occupied.The window in sliding window protocol is a buffer, which stores only those packets whose acknowledgement is not received. But because the packet 1's ack is received, it would no longer remain in the window.


Rollback and Timestamp Ordering in Database If we use the Timestamp Ordering for concurrency control in the following scheduling:

My TA says $T_2,T_3,T_5$ is Run and $T_4,T_5$ is Rollback. I think it's false. Is there any expert who could help us?

Timestamp Ordering ensures serializability by serializing transactions in order of their timestamps.

The transaction that starts earlier is assigned smaller timestamp than a transaction started later. Assuming the given schedule shows each transaction's start. $T_{5}$ will have smallest timestamp.

So to ensure serializability the given schedule must be conflict serializable. In other words it must be conflict equivalent to a serial schedule(It is a schedule in which transactions are aligned in such a way that one transaction is executed first. When the first transaction completes its cycle, then the next transaction is executed) whose first transaction is $T_{5}$ because of smallest timestamp.

Because $Write(y)$ of $T_{5}$ conflicts with $Write(y)$ of $T_{3}$,  $T_{5}$ is rolled back. Now considering $T_{1}$ , $T_{2}$, $T_{3}$ , $T_{4}$, their execution is already serial with respect to each other , the order being $T_{2}$ followed by $T_{1}$, followed by $T_{3}$, followed by $T_{4}$.

Hence only transaction $T_{5}$ is rolled back.


Weighted closest-pair-of-points problem I want to solve the following optimisation problem (an approximation or heuristic would be helpful as well).

I have two sets of points in the plane:
 $P=\left\{ p_{1},p_{2},\dots,p_{N}\right\} $ and $Q=\left\{ q_{1},q_{2},\dots,q_{M}\right\} $.

Each point has a value/weight, i.e there is a function $v:P\cup Q\rightarrow\mathbb{R}$ which assigns a weight/value to each point.

I want to find a pair of points, one in $P$ and one in $Q$, which maximizes the function $f:P\times Q\rightarrow \mathbb{R} $,$
f\left(p,q\right)=v\left(p\right)+v\left(q\right)-\alpha\cdot d\left(p,q\right)
$

where $d$ is the Manhattan distance between the points.
So on one hand I want points with a high value, on the other hand I want them to be close together. $\alpha$ is just a constant which I will determine according to the specific application and it assigns a "relative importance" of the distance relative to the weights.

The choice for Manhattan distance is because I want to use this with actual geographical points which are connected by actual road networks.

Does anyone have a suggestion how to solve this without an exhaustive search over all pairs? even an approximation or heuristic suggestion would be helpful.

Thank you!

Suggested solution: use a k-d tree

I recommend you use a k-d tree to store the points of $Q$, with $k=3$ (3 dimensions).  The three dimensions of each point are the $x$-coordinate, the $y$-coordinate, and the $v$-value (the value/weight of the point).

Store all of the points of $Q$ in a k-d tree.  Then given a point $p$, you can use the structure of the $k$-d tree to find the point $q \in Q$ that maximizes $f(p,q)$ in a relatively efficient way -- more efficient than naively testing each possible point $q \in Q$.  Then, you can iterate through the points of $P$, and for each point $p \in P$, use this procedure to find the point $q \in Q$ that maximizes $f(p,q)$.  Keep track of the best pair you've seen, and this will solve your problem.

I guess I'd better describe how to use the k-d tree.  Recall that each node in the k-d tree splits by a binary condition of the form $x \le c$ or $y \le c$ or $v \le c$, where $c$ is some constant (all points that satisfy the condition are stored in the left subtree of that node and all points that don't satisfy the condition are stored in the right subtree).  Each point $q \in Q$ is stored somewhere in the tree.  So, any node $s$ in the k-d tree corresponds to a subset $S_s \subseteq Q$ of points from $Q$, namely, the points that appear somewhere in the subtree rooted at $s$.  Due to the splitting criteria, each set $S_s$ has the form $Q \cap R$ where $R$ is some axis-aligned 3-dimensional rectangle.  For a particular node $s$, define

$$\begin{align*}
s.x_\text{max} &= \max\{q.x : q \in S_s\}\\
s.x_\text{min} &= \min\{q.x : q \in S_s\}\\
s.y_\text{max} &= \max\{q.y : q \in S_s\}\\
s.y_\text{min} &= \min\{q.y : q \in S_s\}\\
s.v_\text{max} &= \max\{v(q) : q \in S_s\}\\
s.v_\text{min} &= \min\{v(q) : q \in S_s\}
\end{align*}$$

As you form the k-d tree, precalculate the above 6 values for every node and store them in that node of the k-d tree, so they're available for ready lookup.

Define $R_s = [s.x_\text{min},s.x_\text{max}] \times [s.y_\text{min},s.y_\text{max}] \times [s.v_\text{min},s.v_\text{max}]$.  We can see that $S_s = Q \cap R_s$.  It will be helpful to define

$$d(p,R_s) = \min \{d(p,r) : r \in R_s\}.$$

Note that you can efficiently calculate $d(p,R_s)$, given the point $p$ and the 6 values associated with $s$.  (Basically, this involves a case analysis through 27 cases, depending upon where $p$ is relative to $R_s$.  The running time to compute $d(p,R_S)$ is $O(1)$.)

Let's fix a point $p$.  I'm going to describe an algorithm to find the point $q \in Q$ that maximizes $f(p,q)$, by recursively searching the k-d tree for $Q$ in a suitable way.  The idea is that we'll recursively visit the nodes of the k-d tree, but pruning the traversal when we reach a node that cannot possibly hold any point $q \in Q$ that will be better than the best seen so far.

To help us prune the traversal, notice that we can bound the maximum possible value of $f(p,q)$ over all $q \in S_s$, as follows:

$$f(p,q) \le v(p) + s.v_\text{max} - \alpha \cdot d(p,R_s) \text{ for all } q \in S_s.$$

Thus, whenever our recursive traversal reaches a node $s$ of the k-d tree, we'll use the above bound to figure out whether there is any possibility that exploring the subtree rooted at $s$ could possibly yield some improvement over the best result seen so far.  If not, we'll prune the traversal and won't visit any of the children or descendants of $s$.

Thus, the algorithm looks something like the following:

def findbestpoint(p):
    bestsofar := -infinity
    visit(p, root of k-d tree for Q)
    return bestsofar

def visit(p, s):
    if v(p) + s.v_max - alpha * d(p,R_s) <= bestsofar:
        return
    update bestsofar based upon the point q stored in node s (if any)
    if s is a leaf:
        return
    visit(p, s.rightchild)
    visit(p, s.leftchild)

Given a k-d tree for $Q$ and a point $p \in P$, this algorithm computes $\max \{f(p,q) : q \in Q\}$.  It will visit some of the nodes of the k-d tree but not all of them.  So, iterate through the points $p \in P$ and call findbestpoint() on each one.

The above is correct but not necessarily optimal in performance.  As an optimization, I suggest that at nodes that split on the $x$-coordinate or $y$-coordinate, you should choose the order of the recursive traversal to prefer the subtree that contains $p$; and for nodes that split on $v$-value, always prefer the subtree with the larger $v$-value.  In other words, I suggest you replace the last two lines of visit(p, s) with

    if the condition associated with s is a split on the v-value:
        visit(p, s.rightchild)
        visit(p, s.leftchild)
    else if p satisfies the condition associated with s (i.e., p is contained within the subtree rooted at s.leftchild):
        visit(p, s.leftchild)
        visit(p, s.rightchild)
    else:
        visit(p, s.rightchild)
        visit(p, s.leftchild)

This will choose a traversal ordering that is more likely to help you prune many unpromising nodes.

As another optimization, rather than resetting bestsofar to $-\infty$ on each call to findbestpoint, I suggest you initialize it to $-\infty$ once and then don't reset it again.  This will enable you to prune more effectively, and since you only want to find one pair $p,q$ that maximizes $f(p,q)$, this optimization is valid.

As yet another optimization, you can choose the order in which you iterate through the points of $P$ based on some heuristic.  For instance, you could try sorting $P$ by value and iterating through $P$ in order of decreasing value; or you could use value minus $\alpha$ times the distance to the centroid of $Q$, or something like that.  Basically, you want to first try values of $P$ that are more likely to yield you a large $f(\cdot,\cdot)$ value, as that will make the pruning more effective.

I have no theoretical guarantees on the asymptotic running time of this algorithm.  However, when the set $Q$ is large, I expect this will give significant improvements.  Once you understand how k-d trees, it should be relatively easy to code this up and give it a try.

Note that you can always choose whether to store $Q$ in the k-d tree and iterate through $P$ (as outlined above) or whether to store $P$ in the k-d tree and iterate through $Q$.  I suggest you store the larger set in the k-d tree and iterate through the smaller set.

A better algorithm using k-d trees

The idea above can be generalized further, to obtain an algorithm that might be even more efficient, at the cost of making the algorithm more complicated and more tedious to implement.

The algorithm above explores pairs $p,s$ where $p$ is a point and $s$ is a node in the tree (summarizing some subset of points from $Q$).  In the refinement, we'll explore pairs $s,t$ where $s$ is a node in the k-d tree for $P$ and $t$ is a node in the k-d tree for $Q$ (so $s$ summarizes some subset of $P$ and $t$ summarizes some subset of $Q$).  This will expose further opportunities for pruning.

Assume we have built a k-d tree for $P$ and a k-d tree for $Q$, augmented with the information listed above.  For simplicity of exposition, assume we're using one of the variants of the k-d tree data structure where the points of $P,Q$ are stored in the leaves of the tree; the internal nodes don't store points.  (You can generalize the ideas here to the case where each internal node also stores a point from $P$ or $Q$; the extension is messy but not conceptually difficult.)

Also, if $s$ is a node in the k-d tree for $P$ and $t$ is a node in the k-d tree for $Q$, define

$$d(R_s,R_t) = \min \{d(r_1,r_2) : r_1 \in R_s, r_2 \in R_t\}$$

to be the distance between the two rectangles $R_s,R_t$.  This is the distance between the "closest point of approach" between the two rectangles.  For example, if the two rectangles $R_s,R_t$ overlap, $d(R_s,R_t)=0$.  This distance is a property solely of the rectangles $R_s,R_t$ and doesn't have anything to do with the points $p,q$ that are contained within them.  Given the descriptions of $R_s,R_t$ (i.e., the 6 values stored in the nodes $s,t$), you can compute $d(R_s,R_t)$ in $O(1)$ time via an ugly but straightforward case analysis.

Now notice that

$$f(p,q) \le s.v_\text{max} + t.v_\text{max} - \alpha d(R_r,R_s)$$

for all $p \in R_s, q \in R_t$.  This gives us an upper bound on the value of $f(p,q)$ over all class of possible pairs $p,q$ of points.  Conceptually, the node $s$ summarizes a bunch of points $p$ (the set $S_s \subseteq P$), and the node $t$ summarizes a bunch of points $q$ (the set $S_t \subseteq Q$); the above bound lets us upper-bound the best possible $f(\cdot,cdot)$ value, among all pairs of points $p,q$ in these sets.

Based on this insight, we can get a recursive algorithm to find the best pair of points:

def findbestpair():
    bestsofar := -infinity
    visitpair(root of k-d tree for P, root of k-d tree for Q)
    return bestsofar

def visitpair(s, t):
    if s.v_max + t.v_max - alpha * d(R_s,R_t) <= bestsofar:
        return
    if s is a leaf and t is a leaf:
        let p := the point contained within s
        let q := the point contained within t
        if f(p,q) > bestsofar:
            bestsofar := f(p,q)
    else if s is a leaf:
        visit(s, t.rightchild)
        visit(s, t.leftchild)
    else if t is a leaf:
        visit(s.rightchild, t)
        visit(s.leftchild, t)
    else:
        visit(s.rightchild, t.rightchild)
        visit(s.leftchild, t.leftchild)
        visit(s.leftchild, t.rightchild)
        visit(s.leftchild, t.leftchild)

We can see that this explores pairs $s,t$ (corresponding to a set $S_s \times S_t$ of points), pruning when we can prove that none of the pairs $(p,q) \in S_s \times S_t$ will have a larger value of $f(p,q)$ than the best we've seen so far.

You can apply similar optimizations to those mentioned above (e.g., when $s$ is a leaf that splits on $x$-coordinate or $y$-coordinate, first try the child of t that $s$ is contained in; when $s$ is a leaf that splits on $v$-value, first try the child with the larger $v$-value; and symmetrically when $t$ is a leaf).

I would conjecture that if the size of the both sets is large enough, this might perform better than the solution mentioned above. However, I have no proof, and the only way to know for sure is to implement it and give it a try on your data set.

A connection to computational geometry

I also noticed that your problem is related to the following classical problem:

Given a set of discs in the 2-D plane, determine whether any pair of discs overlap.

and the following version of the problem:

Given a set of discs in the 2-D plane, determine the pairs of discs that are closest (where the distance between two discs is given by the closest point of approach, i.e., the minimum distance between any point in the first disc and any point in the second disc).

These are classic problems in computational geometry which I think have sub-quadratic time algorithms (by sweepline methods or something, if I recall correctly).  Unfortunately your problem seems harder those questions about discs, so I don't know whether those methods will transfer over.

Here is the connection.  Define $w:P \cup Q \to \mathbb{R}$ by $w(p) = v(p)/\alpha$ and $w(q) = v(q)/\alpha$.  Define $g:P \times Q \to \mathbb{R}$ by

$$g(p,q) = d(p,q) - w(p) - w(q).$$

Your problem is equivalent to asking for the pair of points $p \in P,q \in Q$ that minimizes $g(p,q)$, as $f(p,q) = - \alpha \cdot g(p,q)$.

Next, treat each point $p$ as being associated with a disc centered at $p$ and having radius $w(p)$; and similarly for each point $q$.  In this way if all of the $w(\cdot)$ values are positive, we obtain a collection of discs in the two-dimensional plane.  Notice that if two discs $p,q$ don't overlap, then $g(p,q)$ denotes exactly the distance between those two discs.  This condition is equivalent to requiring that $g(p,q)$ be positive for all $p,q$.

In summary, if we were promised that $v(p)$ was positive for all $p,q$ and that the maximum value of $f(p,q)$ was negative, then your problem would be equivalent to finding the closest pair of discs in the 2-D plane.

Of course, in your problem, we're not promised any of those things.  Therefore, your problem is harder.  However, if you were really eager on trying to find the best possible algorithm, you could explore the literature to find algorithms for finding the closest pair of discs and see if any of them can be generalized to your setting.


How to store $n$ numbers with space $O(n)$ bits and access time $O(1)$? I want to store a subset of $\{1,2,\dots,n\}$ in a data structure such that the total space used is $O(n)$ bits and accessing a particular element can be done in $O(1)$ time. I have tried binary search tree and array data structures but they are too slow.

In short I need a data structure with $O\big(\frac {n } { \log \log n}\big)$ many cells and size of each cell should be $O(\log \log n)$ bits.

Model of computation: Input memory and a write only output memory. The computation proper takes place in a working memory of limited size. When stating a problem can be solved with in a certain bits, what we mean is that the working memory comprises that many bits. The input and working memories are divided into words of $w$ bits for a fixed parameter $w$, arithmetic and logical operations on $w$-bit words take constant time, and random access to the input and working memories is provided. In the context of inputs of $n$ words,$w= \theta(\log n)$.

Operations: Insert($i$), access($i$), where $i \in [n]$.  The access operation must run in $O(1)$ time.

Motivation: I'd like to store the stack in DFS using this data structure.

I am looking for an deterministic approach, but to me it does not seems working, so probabilistic approach is also fine.

A simple solution is to use a $n$-bit bitvector.  This is basically an array with $n$ entries, where each entry is either 0 or 1.  If the $i$th entry is 1, that means that $i$ was stored in the data structure; 0 means that $i$ was not stored in the data structure.  This takes $O(n)$ bits of space.  The insert and access operations can be done in $O(1)$ time.

The crucial requirement that makes this solution possible is that there will be no duplicates; each number is present at most once.  If you allowed duplicates, the problem would not be solvable within the space requirements you list: storing $n$ numbers from $1$ to $n$ requires at least $\Theta(n \log n)$ bits, based on information-theoretic concerns.


Can't figure out how to make a grammar LL(1) Let's say I start with:

$A \rightarrow Ba$

$B \rightarrow dab | cBb | Acb$

Now I want to make this grammar LL(1), so I need to get rid of the left recursion. I'll work with $B \rightarrow Acb$.

I'll replace where $A$ occurs with its production:

$B \rightarrow dab|cBb|Bacb$

And that gives me a direct left recursion, which I rewrite as:

$B \rightarrow dabB' | cBbB'$

$B' \rightarrow acbB' | \epsilon$

At this point this seems like this should be LL(1), so I'm checking:
$FIRST$ sets: For $A: \{d,c\}$, $B: \{d,c\}$ and $B': \{\epsilon, a\}$.

$FOLLOW$ sets: $A: \{eof\}$, $B: \{a,b\}$ and $B': \{a,b\}$.

Now I'd like to check $FIRST^+$, but if I do $FIRST^+(B' \rightarrow acbB') = \{a\}$ and then $FIRST^+(B' \rightarrow \epsilon) = \{\epsilon, a, b\}$ which does NOT have a non-empty intersection.

Does it make sense to look at $FIRST^+$ in terms of each production that has the same left hand side? Or, have I made a mistake in calculating $FIRST$ or $FOLLOW$ sets to begin with? Is there an issue with the rule $B \rightarrow cBb$ (not left recursive exactly but does have the $B$ nestled inside).

For context-free grammar to be LL(1), these two requirements have to be met for its every rule $ A \rightarrow \alpha |  \beta$:

$  FIRST(\alpha)  \cap FIRST(\beta) = \emptyset$
$ \epsilon \in FIRST(\alpha) \implies FOLLOW(A) \cap FIRST(\beta) = \emptyset$

  Does it make sense to look at FIRST+ in terms of each production that has the same left hand side?

No, as you can see, to decide if grammar fits those rules above, we have to calculate $FIRST$ function for the right-hand sides of the grammar's rules, not for the left sides.

For your grammar, we get these results:

$A: FIRST(Ba) = \{c,d\},\space FOLLOW(A) = \{\epsilon\}$

$B: FIRST(dabB') = \{d\},\space FIRST(cBbB') = \{c\}, \space FOLLOW(B)=\{a,b\}$

$B': FIRST(acbB') = \{a\},\space FIRST(\epsilon) = \{\epsilon\},\space FOLLOW(B')=\{a\}$

As you can see, there is a $FIRST/FOLOW$ conflict (violated second requirement from above) in $B'$. You can read here about how to solve this.


Obtaining Max-Weight Matching from Max-Weight-Max-Cardinality Matching? I have a graph with integer-valued edge weights (possibly negative) on which I would like to obtain a maximum-weight matching.

However, I am using python-graph-tool, which only has max-cardinality max-weight matching, which from what I understand, only finds the max-weight matching of the max-cardinality matchings. However, it may be the case that a truly max-weight matching will not always be a max-cardinality matching (this is especially true on graphs that can have negative edge weights).

Are there any tricks I could use to still get what I need? For example, could I transform my graph $G \to G'$ so that by obtaining a max-card-max-weight matching on $G'$ I could obtain a max-weight matching on $G$? Or will I have to find another algorithm? Are there any good algorithms suited to the task?

Suppose that the original graph is $G = (V,E)$. Let $V’$ be a copy of $V$, and create a new graph $G’$ with vertex set $V \cup V’$ and the following edges:

The original edges of $G$.
For every edge $(a,b) \in E$, we add a zero-weight edge $(a’,b’)$, where $a’,b’$ are the counterparts of $a,b$ in $V’$.
A matching connecting $V$ to $V’$ (i.e., each vertex in $V$ is connected to its counterpart in $V’$) with zero-weight edges.

Every matching of $G$ can be extended to a perfect matching of $G’$ with the same weight.

A useful feature of this reduction is that it preserves sparsity — that is, denoting by $n,m$ the number of vertices and edges in $G$, and by $n’,m’$ the same parameters for $G’$, we have $n’+m’ = O(n+m)$.


Correctness proof of greedy algorithm for 0-1 knapsack problem We have a 0-1 knapsack in which the increasing order of items by weight is the same as the decreasing order of items by value. Design a greedy algorithm and prove that the greedy choice guarantees an optimal solution.

Given the two orders I imagined that we could just choose the first k elements from either sequence and use them to fill knapsack until it was full. This would be similar to choosing the items with the greatest ratio of value to weight. But I don't think that is an optimal solution.

So what I need help with is whether or not this solution is optimal. And how would I prove the correctness of a greedy algorithm.

Hint: Let $x$ be the item of smallest weight (and so of highest value). Take any solution which doesn't contain $x$. If there is room for $x$, add it to the solution. Otherwise, remove some element and add $x$ (why is that possible? does it necessarily improve the solution?). Conclude that the optimal solution always contains $x$. Apply this reasoning recursively to come up with a greedy algorithm.


When do structural hazards occur in pipelined architectures? I'm looking for some relatively simple examples of when structural hazards occur in a pipelined architecture.

The only scenario I can think of is when memory needs to be accessed during different stages of the pipeline (ie, the initial instruction fetch stage and the later memory read/write stage).

I'm thinking that there are many more structural hazards in more complex architectures, such as superscalar. Does it class as a structural hazard when an instruction is dispatched to an execution unit but is queued because the unit is in use?

If this is highly architecture-specific, then just assume MIPS or something similar.

In a scalar implementation, a structural hazard can exist if specific execution hardware is not fully pipelined.  For some operations (e.g., multiplication and especially division) the cost of implementing full pipelining may not be considered worthwhile for the expected frequency of the operation.

In a superscalar implementation, a structural hazard may exist because not every execution unit can perform every operation.  E.g., supporting initiating execution of four memory operations or four multiplications every cycle would be relatively expensive when limited to four-wide issue given that a different type of operation is likely to be available.

Register file read and write port limits can also introduce structural hazards.  Although it is possible to provide enough read and write ports to support the worst case, the costs of register file ports to satisfy the worst case (even with the benefit in design complexity of not having to specially handle exceptional cases) can be considered not worth the benefits when the bad cases are sufficiently rare or non-critical.  E.g., some out-of-order implementations use operand capture (grabbing operands that become available between the time the operation enters the scheduler and the time it is scheduled for execution) and provide fewer register read ports than required for full width operation (whether operands available earlier are read when the operation enters the scheduler or when the operation is scheduled for execution).

(Even for an in-order implementation, result-forwarding and the use of operations with a single register source operand could make supporting four register read ports for two-way issue less necessary.)

Similarly, banking is often used for caches (and has been proposed for register files).  E.g., in the common case, two accesses are unlikely to map to the same bank out of 16 banks.
Banking storage is substantially less expensive than adding access ports.  The potential for bank conflicts represents a structural hazard.


Overlap between theory and systems fields in CS I have finally had some serious graduate-level exposure to CS Theory and loved it. I really enjoyed complexity theory (time and space complexity, the different classes, reductions to prove NP-Completeness), and algorithm analysis. I am still very interested in Operating Systems, software engineering, and network/information security.

My question is: What would some starting places to look into if I want to find direct overlaps between CS Theory (algorithm design and analysis, complexity theory, information theory, etc) and, OS, or software engineering? I guess I am looking for areas that might have project possibilities that will test and expand my knowledge in both theory and either OS or SE.

For Security the best one I could think of is theory of cryptography, but I am kind of at a loss when it comes to the other two.

I can see a lot of overlap in the field of Cloud Computing or Distributed Computing
- being that it relies heavily on process scheduling and parallel processing on the operating systems side and optimization algorithms to both traverse data across multiple nodes (servers) and optimize hardware resources on the network grid. Graph theory and NP issues come up often when trying to reconcile issues concerning "Big Data" within the distributed computing space.

The software engineering CS component arises when developing designs for new operating system based applications like system monitors that help stabilize and secure distributed computing systems.

From this example, one can see much of the overlapping of said disciplines that go into Cloud Computing.


Finding Models for a sequent I am trying to generate models for the following sequent.

$$\exists x \exists y \forall z (z = x \lor z = y)$$

What I have come up with is this.

$$A= \{0,1\}$$

So in this model, for all the values of $z$ there exists $x$ such that $z = x$ or there exists $y$ such that $z = y$. Is this model correct? What other models are there that satisfy this?

You should be careful with order of quantifiers. You are given a predicate
$$\exists x \exists y \forall z (z = x ∨ z = y)$$
which is read as
$$\text{ there is } x \text { such that there is } y \text { for all } z \dots $$
while you read it as
$$ \text { for all the values of }  z \text{ there exists } x \dots$$
which would correspond to
$$\forall z  \exists x \dots$$
When you change the order of quantifiers the meaning (and hence the truth value) of the sentence changes. For example consider the set of natural numbers excluding 0. Then
$$\forall x \exists y (x \text { divides } y)$$ is a true sentence since for any $x$ take $y=x$. But the sentence
$$\exists x \forall y (x \text { divides } y)$$
is false since $x$ does not divide $x+1$.

Now as for your question, yes $A=\{0, 1\}$ models this sentence. In fact you could also take a set consisting of a single element, for instance $\{0\}$ or $\{1\}$ (there is no condition such as $x\neq y$).


Numerical example of theoretical diff file size using Kullback Leibler? I understand that the theoretical size of a diff patch between two similar files can be calculated using Kullback Leibler (KL) as described @ Wikipedia.  Can anyone point me to a numerical example of this calculation?  I can only find general theory and formulae. I'd like to check my work.  So this is what I have so far...

This is a graph of the individual divergences for each byte probability between two files, say P and Q.  They are calculated according to the standard log formula for divergence.  The byte values (0-255) are along the bottom.  You can see that the divergences are both positive and negative.

I am unsure as to what the units of the y axis are, but following on from Shannon entropy, they must be bits per byte.  And they're small values.  The sum of all the divergences, keeping sign, is 0.019 bits /byte.  Both file sizes are approximately 20KByte, so can I say that the theoretical patch size going from P to Q is 20,000 * 0.019 = 380 bits or 48 bytes?

This feels wrong.  If the graph represents the patch size somehow, then I cannot see how the information contained in this complex shaped graph can be encoded in just 48 bytes.  There are no examples anywhere on the Interweb that I can find.

One further thing.  The above is for two similar files.  If P or Q should be totally random (from a random number generator), the KL divergence calculation = approx. 0.5.  This at least makes some semblance of sense if you think about all of the bits from P to Q being on average 50% different due to the randomness.  Perhaps 48 bytes is correct.  Err, um...

I understand that the theoretical size of a diff patch between two similar files can be calculated using Kullback Leibler (KL)

That's not quite right.  I suspect you've taken an imprecise, non-technical, handwavy statement from Wikipedia and interpreted too much into it.  They're trying to summarize some underlying theory in an informal way, but such summaries are inevitably incomplete.  Instead, you'd be better off reading and understanding the underlying theory.

There is a sense in which that statement is correct if we make certain assumptions -- e.g., that the source is memoryless (each character is independent of all past ones, with no history), and that we interpret it in an asymptotic, average-case kind of way -- but for many real-world sources of  data, those assumptions don't apply.


Why is Church-Rosser so important for basing programming languages on lamdba-calculus? So, I know Church-Rosser has 2 thesis:

CR1: If $ E_1 \leftrightarrow E_2 $, then there exists an Expression E so $ E_1  \rightarrow E $ and $ E_2 \rightarrow E $

CR2: If $ E \rightarrow N $ (with N in normalform), then there exists a reduction row in normalorder (first reduce the left most ouuter most index) from E to N

from CR1 we learn that no expression can be converted to 2 different normalforms, so there is only one result for each function

from CR2 we learn that reduction in normalorder always finds the result (if their is one (no loop))

But i don't understand why these two are so important for basing a programming language on lambda-calculus. So my question is why are they?

Think of it as a sanity check. CR cones from the days when we were just figuring out what programming languages were. The Lambda calculus was new, and its basic properties were unknown.

CR says that Lambda Calculus behaves like you would expect: every expression can be evaluated to a unique value, or runs forever. We didn't know if the calculus was well behaved. We had to prove it.

Imagine that CR didn't hold, and that the order you evaluated an expression mattered. We would throw Lambda calculus away. It would be like saying $2+2$ could have more than one value.

CR also justifies the existence of lazy languages, showing that they behave at least as well as eager languages, sometimes better. Haskell certainly owes its existence in part to CR.


Determine Epsilon for identification I have a project in which I need to compare different distances in a database with a distance in input in order to identify a person. For that I use this expression: DistanceDB - DistanceInput < epsilon, if this is true then the distance and information in the Database row are related to the person standing before the kinect. How can I choose epsilon because if it's too small, no one will be identifier, and if it's too big the application will return the first row of the database. Thank you for your answers.

Your best bet is probably to start with a value that seems reasonable and improve it by trial and error.


Machine code and punched cards I have been looking into the history of programming, and everybody and their grandmothers begin the subject with a claim more or less similar to the following:

  At first, programmers used machine code. Later, there were assemblers. Then, pseudo code, and finally Fortran came.

With some Google-fu I can very easily find examples of punch cards containing Fortran statements, COBOL statements, and some Assembly statements. Wikipedia has some punch card examples for short code.

But I am yet to find a reliable source explaining how programmers entered machine code into computers using punch cards. Or pseudo code using punch cards.

Were there really punch cards for machine code? Or when stored programs appeared they were already programmable with Assembly?

You normally started by entering a little loader program one word at a time by setting the bits with a line of toggle switches on the front panel, like this:

Wikipedia has a bit of explanation of the process. (Yes, it was tedious.) The little program would then read a larger program off of some convenient input device, which could be a card reader, although the machines I used in those days used paper tape.

It could even be magnetic tape or some other magnetic storage device.

The larger program was the equivalent to the boot loader which is on sector zero of the persistent storage of whatever computer you used to ask this question, so the process is not that different.

A useful innovation was storing the initial boot loader loader in hardwired persistent memory (aka BIOS).

The use of symbolic codes to replace individual binary toggle switches (or equivalent) grew over time, and the distinction between assemblers and "higher level" languages is not a clear line. Fortran was certainly not the first higher level language, but it was extremely important.

(Some of the images come from David Gesswein's wonderfully nostalgic PDP-8 site.)


Three-address code versus JSON, XML, etc I'm working on a compiler. The textbooks I have say to output a 3-address intermediate code. This can be translated into the target language of choice.

I don't have a problem with the bulk of the source being translated to 3-addr code. But for the data-rich symbol table, this is awkward.

Is the exclusive use of 3-addr code old, obsolete advice? My compiler is multi-pass compiler. I'm working pretty hard to build a symbol table in my first pass, and I'm pretty much having to reconstruct it in 3-address code for the next pass. This seems like make-work to me when I could create from my symbol table XML or JSON.  I could write that to the intermediate file instead.

How should I represent my symbol table in the intermediate code?

XML and JSON are formats for representing data. The actual kind of data depends upon how you use them. For instance, they could be used to represent 3-address intermediate code or an abstract syntax tree, or even a symbol table.

3-address intermediate code is best generated only at the very end, as input to the code generator. For all other passes, keep as much information around as possible. This could include a decorated abstract syntax tree (decorated with types and other information) and a symbol table.

In fact, I'd only use the 3-address format if you are generating assembly. For a higher level target language, use a higher-level intermediate format.


Understanding the Reasoning Behind These Typing Rules So the expression $\Gamma \ \vdash \ e:\sigma$ states that under assumptions $\Gamma$, the expression $e$ has type $\sigma$. Then we have the following rules:

\begin{array}{cl}\displaystyle {\frac {x:\sigma \in \Gamma }{\Gamma \vdash _{D}x:\sigma }}&[{\mathtt {Var}}]\\\\\displaystyle {\frac {\Gamma \vdash _{D}e_{0}:\tau \rightarrow \tau '\quad \quad \Gamma \vdash _{D}e_{1}:\tau }{\Gamma \vdash _{D}e_{0}\ e_{1}:\tau '}}&[{\mathtt {App}}]\\\\\displaystyle {\frac {\Gamma \vdash _{D}e_{0}:\sigma \quad \quad \Gamma ,\,x:\sigma \vdash _{D}e_{1}:\tau }{\Gamma \vdash _{D}{\mathtt {let}}\ x=e_{0}\ {\mathtt {in}}\ e_{1}:\tau }}&[{\mathtt {Let}}]\end{array}

where

$\mathtt {Var}$ is variable access.
$\mathtt {App}$ is function call with one parameter (function application).
$\mathtt {Let}$ is variable declaration.

I would like to understand how these rules work. This is my understanding so far...

[$\mathtt {Var}$] "if $x$ is of type $\sigma$ from environment $\Gamma$, then under the assumption of $\Gamma$, $x$ is of type $\sigma$." Two things are confusing me so far. First is the $D$ in $\vdash_D$. The second is that the premise and conclusion seem to say the same things: "if x is of type y, then x is of type y". Wondering what this is actually saying so that I can see why it's necessary.

[$\mathtt {App}$] "if under the assumption of $\Gamma$, $e_0$ is of type $\tau \to \tau'$ $\land$ under the assumption of $\Gamma$, $e_1$ is of type $\tau$, then under the assumption of $\Gamma$, $e_0\ e_1$ is of type $\tau$." So that last part is introducing some new syntax $e_0\ e_1$, which means function application. So that makes sense. What I get confused about is the "if, then" part in this definition. Wondering if it is saying, "if the function and the parameter are present, then we can do function application", or "if the function and parameter are present, then function application occurs." I keep on interpreting it as the latter for some reason.

[$\mathtt {Let}$] "if under the assumption of $\Gamma$, $e_0$ is of type $\sigma$, and under the assumption of $\Gamma$ and $x$ of type $\sigma$, $e_1$ is of type $\tau$, then under the assumption of $\Gamma$ we can do $\mathtt {let}\ x=e_{0}\ {\mathtt {in}}\ e_{1}$ of type $\tau$." That "we can do" part is my understanding that this is saying, because of these premises, we can declare a variable. Also I'm not sure about the $\Gamma ,\,x:\sigma\vdash _{D}$, wondering if that is just saying that $x:\sigma$ is in the environment $\Gamma$, or if it's a separate thing. So basically it is just highlighting the fact that we are in the environment and we have this particular type of interest in the environment.

So to summarize, the questions are:

The meaning of $D$ in $\vdash_D$.
In $\mathtt {Var}$, wondering what the definition is actually saying and why it is necessary.
If my understanding of $\mathtt {App}$ and $\mathtt {Let}$ are correct.

For question 1, I don't think that the $D$ carries any particular meaning, it is just part of the notation, and might refer to the name given to the corresponding calculus.

For 2, what you need to understand is that $\Gamma$ really is a set of assumptions. So if $\Gamma = x_1 : \sigma_1, \dots, x_n : \sigma_n$ then $\Gamma$ is a typing context that tells us that we will assume that $x_1$ has type $\sigma_1$, that $x_2$ has type $\sigma_2$ and so on.

Now, what might be confusing to you is that there are several different levels of implications in the syntax of typing rules.

First, the typing rules themselves are implications of the form "if the premises hold, then the conclusion hold" (the premises being the hypotheses given above the line, and the conclusion being the typing judgment below the line.
Second, a typing judgments $\Gamma \vdash e : \sigma$ is also a form of implication, meaning "if the assumptions on the types of variables given in $\Gamma$ are correct, then $e$ has type $\sigma$".
And finally, there is also the arrow type $\sigma_1 \to \sigma_2$, which is also a form of implication.

So in the end, what the [Var] rule says, is that we may assume that $x$ has type $\sigma$, provided that this is part of our assumptions. Or in other words, it is always true that $x$ has type $\sigma$ under the assumption that $x$ has type $\sigma$. Or, reformulating again: when you made an assumption, you have the right to use it.

For 3, the main thing that you need to understand is that typing rules are implications (as explained above). For example, [App] says that if we can show that $e_1$ has an arrow type and that $e_2$ has the same type as the domain of the arrow (i.e., $e_1$ and $e_2$ have compatible types), then we can perform an application.


What happens at the decode phase of the instruction cycle? I am reading about the various phases of the Instruction Execution, I found out that we have three phases like below.

Fectch
Decode
Execute

Now if the part I don't understand is why do we need a decode phase ? The instruction will already be stored in a binary format at some memory location, why not just fetch and execute it.

The name "decoding" is actually a bit misleading because more things take place in this stage. You can view it as a translation from the external, programmer-visible representation of the instruction, to the CPU's internal interpretation.

All CPU architecture have an encoding of instructions, usually involving the specification of a number of op-codes specifying the "action" of the instruction (as opposed to the arguments, which might be registers, memory locations etc.). Note that the op-code is just a number, often just a byte. For instance, the addition instruction might have byte value 0x01, the subtraction might be 0x02 and so on. However, note that the numbering is somewhat arbitrary. It doesn't in itself say what the instruction does - this is something you would have to look up in the instruction manual.

What the decoding stage does is to map these numbers to the actual action of the instruction. This often involves looking up the OP-code in a data-structure, for instance a ROM. You could compare the decode stage to you looking up the op-code in a manual, to see what the instruction actually is. Now, your instruction manual is written in a human-readable language. What is the computer's manual written in? One method used in many implementations is that the ROM maps the op-code to a value which specifies the control signals that must be sent further into the execution pipeline to cause the action that is to be executed. For instance, if the instruction involves looking up the values of registers, adding them, and storing the result in another register, the ROM will contain values for the control signals that commands the register banks into read mode and the ALU into addition mode. The details of what the control signals are, are of course implementation dependent, depending on how the CPU internally functions and what control signals its various internal units accepts. However, the point is that the decode stage maps the representation of the instruction (in the form of op-code) to the actual action, in the form of these control signals. Note that on many architectures, one instruction might actually be decoded into several such "micro-instructions" with each micro-instruction essentially being a long word of all these control signals. This allows the architecture to provide the application programmer with complex instructions with short encoding. This generating and sequencing of micro-instructions might also take place in the decode stage.

Now you could ask, why not just let the instruction op-code contain all these control signals? In that case, the decode stage might not be necessary. Only problem is, that execution of an instruction often involves a lot of control signals, meaning instructions would be very long, just got the op-code. Also, it would expose the internal workings of the CPU since the external representation of instructions would now be deeply tied to the internal workings.

By the way, some architecture have very complicated encoding scheme so here the decoding involves a lot more work than just a lookup in a ROM, but in fact rather complicated logic just to determine the length and the prefixes etc. of the instruction. Also, various tricks might be necessary to keep the ROM at an acceptable size and also to allow fast look-up. On superscalar instructions, it is even possible to do this for several instructions in parallel even for encodings with variable length instructions! So as you can see, decoders can be pretty busy!


What is the equivalent of the integers symbol Z for n bit only integers? We refer to the set of all integers as $\mathbb{Z}$.  Now suppose we have a set of integers that can be held within a computer variable of $n$ bits width. Clearly they can only be of  $2^{n}$ range, signed or not. How would we symbolise that? Is there something that is done to the zed, or does it remain simply $\mathbb{Z}$?

For bounded sets, the usual convention is to use interval notation.

Specifically, $[a,b]$ means "real numbers between $a$ and $b$, inclusive", while $[a\mathinner{\ldotp \ldotp}b]$ means "integers between $a$ and $b$, inclusive". Changing any of the square brackets to curved means that endpoint is not included: $a \not\in (a,b]$, for example.

In this case, you'd want the interval $[0\mathinner{\ldotp \ldotp}2^n)$. Or, if you think the delimiters look mismatched and weird, you can use $[0\mathinner{\ldotp \ldotp}2^n-1]$.

P.S. LaTeX doesn't have a builtin for "two dots", so I used \mathinner{\ldotp \ldotp} from this answer.


What is the time complexity of sorting n words length wise and then alphabetically? Should we consider the length of the strings in the complexity? Let's assume I have a list of some words found in the English dictionary:
["hat", "assume", "prepare", "cat", "ball", "brave", "help" .... ]
I want to sort these words (which are n in number) in a way, such that they are ordered based on their length, but if 2 words have the same length, they are ordered alphabetically.
What is the time complexity of this sorting operation?
Would it be fair to say that the complexity is just O(nlogn) and not take into consideration the length of the strings? If the largest length is S, can the complexity also involve a factor of S?

This algorithm requires at most $O(n \log n)$ string comparisons, assuming you use a suitable sorting algorithm.
If strings are at most $S$ characters long, each string comparison can take up to $S$ operations.  So, the worst-case running time could be as large as $O(S n \log n)$.
If the size of the character set is constant, then it is possible to solve your problem in $O(n(S+\log n))$ time with a slightly different algorithm: compute the length of each string ($O(nS)$ time), sort the strings by length ($O(n \log n)$ time), then for each length, use radix sort on the strings of that length ($O(nS)$ time).


Algorithm for distributing members over activites (with individual preferences) So in my school we have a day where everybody participates in different activities. Each projects can have like 10 members. The whole day is divided in 2 or 3 different blocks, in which the pupils assigned to the activity change. (So in block 1 pupil x takes part in activity a and in the second block in activity d).

Before this day starts, we give make lists in which each pupil can tell us his 3 (or 4) favorite activities (he only takes part in two of them, these again are ordered from most "favorite" to least) in which he wants to take part. Now our job is to assign these pupils in a way that we have the best overall satisfaction among the pupils (so everybody did more or less did get his/her chosen activities).

What would be a good algorithm to solve this? Is there any way to do this, apart from calculating such a "satisfaction" value for each possible solution?

An optional feature would be that if someone can't get in to his/her project, they would get into a similar one according to some predefined distance.

Here is partly a solution, partly an approximation:

Let $T$ denote set of time blocks.
Let $C$ denote set of children.
Let $A$ denote set of activities.

Let $T_i$, $C_i$, $A_i$ denote $i$-the time block, child, activity.
Let $S_{ij}$ denote the satisfaction for child $i$ from activity $j$.
Let $M_j$ denote maximum number of pupils that can participate in $j$-th activity.

Create a bipartite graph where pupils are on the left side and activities are on the right.
For each pupil $C_i$ and activity $A_j$ create an edge with capacity equal to 1 and cost equal to $-S_{ij}$.
Create a source and connect it to all $C_i$, capacity equal to $|T|$.
Create a sink and connect all $A_j$ to sink, with capacity equal to $M_j * |T|$.
Find minimum cost maximum flow on this graph.
Now for each pupil you have assigned number of activities equal to the number of time blocks. If there exists a valid assignment of activities to pupils, the algorithm above will surely find some (not necessarily valid) assignment.

Let $P_j$ denote number of pupils that were assigned to $j$-th activity after the algorithm above.

Now, for the approximation part:

Let's create a grid of $|T|$ rows and $|A|$ columns, $i$-th row denoting all activities that will happen during $i$-th time interval.
Let's fill in our table. We will loop through it's columns, and for a column, we will loop from top to the bottom of the row. In parallel let's loop through all activities in some order. For activity $j$ let's put into the next cell of the table $j$ activity and move to the next cell, total of $P_j$ times for $j$ activity.
Since $P_j \le M_j * |T|$, in each row of the table there will be at most $M_j$ entries of $j$-th activity, satisfying the condition that during one time interval only $M_j$ persons can participate in $j-th$ activity.
Each row should have some permutation of pupils. Let's for each for find maximum matching between pupils and and activities in some row. Two problematic situations might occur:

Pupil is assigned to the same activities in different time blocks. We can overcome this in two possible ways:

a. Once pupil was assigned to some activity in one row, don't connect the appropriate pupil vertex to the appropriate activity vertex in the following rows.

b. Who ever said that satisfaction decreases if you participate in your favorite activity again? ;)
For some rows, we may not find perfect matching. Well, this is why it is an approximation, not a solution. since it is maximum matching, we will still find for many pupils their preferred activities from first part. For others, we can match them with other activities in a row.

Possible heuristics:

Match pupils in a row not using bipartite matching, but using Hungarian algorithm (for perfect maximum weighted matching, with weights equal to $S_{ij}$, where $j$ is activity in the appropriate cell in a row.

Try different orderings when creating a grid. For example, we may try to use simulated annealing based on the permutation of order, in which we put activities to the grid, and transition between steps that results in a swap of neighboring / any two elements in this permutation.


Compression of a text that contains only the 5 first letters of the alphabet? So the question is: "Imagine the compression of a text written only with the first 5 characters of the alphabet (a, b, c, d, e). Knowing that their apparition's frequency is 1)e, 2)a, 3)c, 4)d, 5)b, code the letters on the minimum bits possible."

so here's how I did start:

We have 5 characters, so 3bits will be enough for the characters (2^3 =8). We can put: e=001, a=010, c=100, d=011, b=110 But I don't see how to use their frequency (we don't have the value of it, they just gave a "scale" of their frequency)

If you look at the algorithm for creating Huffman trees/codes, you will see that while it uses frequencies, any weight works. You can always rescale (by dividing by the sum of all weights), if you wish.

If your problem does not contain any weights but only a relative order, you can not build a Huffman tree; you don't know where in the order the inner nodes you create go. Ask your teacher.


Synchronization in Distributed Systems If there is no global clock in Distributed systems  , then what is the solution for synchronization in DS ? Also , no global clock in DS is a direct consequence of the fact that the only communication is by sending messages through a network. Can someone please explain how the communication via message passing has resulted in no global clock ?

It is the other way around. We first model the system in a certain way, for instance we assume that there is a (or is no) global clock, or we assume that messages arrive or may fail, etc. Once we fix our assumptions, we can ask questions about the system we have characterized: does it allow computations of certain types or not?
For instance, if we assume all the nodes are identical and ask whether we can break symmetry, then the answer is no (in certain cases). If we assume there is no global clock, and ask whether the parties can synchronize, then probably the answer is no (it depends on what you mean by "synchronize"). However, can the system solve tasks without a global clock? Sure! there are plenty asynchronous algorithms that perform a large variety of tasks, like broadcasting, finding a leader, or computing a spanning tree.
So, communication via message-passing does not imply no global clock. These two are independent assumptions that characterize the system. Under these assumptions certain tasks are possible/fast and other might be impossible/slow.