Operation on binary tree I would like to confirm below understanding,

  A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child.

  Insertion:

  In binary trees, a new node before insert has to specify 1) whose child it is going to be 2) mention whether new node goes as left/right child. For example(below image),

  To add a new node to leaf node, a new node should also mention whether new node goes as left/right child.

  Deletion:

  For deletion, only certain nodes in a binary tree can be removed unambiguously.

  Suppose that the node to delete is node A. If A has no children, deletion is accomplished by setting the child of A's parent to null. If A has one child, set the parent of A's child to A's parent and set the child of A's parent to A's child.

  In a binary tree, a node with two children cannot be deleted unambiguously.

Is this understanding correct ?

Its hard to say without the knowledge of why a node goes to the left or right of another, and if this carries as a property throughout the tree. If by ambiguously you mean there is more then one valid way of replacing the node and the tree has an ordering structure (such as a binary search tree) then your understanding is correct. The deleted verticie can be replaced with either its in order predecessor, or its in order successor. Both of these will be valid with the ordering property.


How to initialize the first h in an RNN? Take a Vanilla RNN represented by the function $h_t = f(h_{t-1}, x_t)$, how do you determine $h_0$?

Edit: This answer over on the stats page has helped.

There are a few different ways. One way is to always give it a zero vector, or some other constant that means "new sequence". Another way is to train the initial state vector just like you train any other weight: initialize it randomly, then apply gradient descent during training. The former is easier and faster, but the latter can sometimes make the RNN more effective.


Transitive reduction of rectangle containment hierarchy DAG I am looking for a $O(|V| + |E|)$ algorithm for finding transitive reduction of a rectangle containment hierarchy DAG, i.e. a directed edge exists from one rectangle to another if the first rectangle contains the second.

That is, remove as many edges as possible so that if you could reach v from u, for arbitrary v and u, you can still reach it after removal of edges.

Assume that rectangles are unique, so we are dealing with a DAG.

This is useful, for example, with quantitative association rule mining from Srikant/Agrawal 1996. There, we are interested in close ancestors for hyperrectangles s.t. ancestors contain us. Determining close ancestor is similar to determining close descendant, which is related to transitive reduction with rectangle containment. This kind of rule mining is related to APRIORI algorithm for standard (i.e. "Boolean") association rule mining from Agrawal/Srikant 1994.

A similar problem is transitive reduction of standard DAG, which is here:
Transitive reduction of DAG

References

Agrawal, Srikant - Fast algorithms for mining association rules (1994)
Srikant, Agrawal - Mining quantitative association rules in large relational tables (1996)

Dec. 14, 2018

Standard approach and a heuristic alternative

Standard approach -- use graph and distance product

We note that transitive reduction is reduceable to transitive closure and vice versa both in additional time in $O(n ^ 2)$. Then, we know that if we can solve transitive closure in $O(n ^ 2 \cdot \textrm{polylog}(n))$ time, then we can also solve lax Boolean matrix multiplication (MM) in similar time by reducing it to transitive closure (or transitive reduction), according to Fischer/Meyer 1971. Lax Boolean MM is where input values are in $\{0, 1\}$ and we have semi-ring of $(\textrm{OR}, \textrm{AND})$. We can solve lax Boolean MM by reducing to standard (plus, times) MM. This means that significantly-subcubic-time approach is currently unlikely for transitive reduction. We can reduce node-based DAG transitive reduction to rectangle-containment-based DAG transitive reduction via topological ordering and shapes that have size inversely related to distance from source. For rectangle application, we should of course not have cycles, which happen when the rectangles are identical, in which case we should remove duplicates. A more direct algorithm is for computing reduction assuming sparse graph, which takes $O(n ^ 3)$ time. These times are also ignoring that to come up with initial DAG we ought to perform $n ^ 2$ containment tests, each of which takes time in $O(d) = O(2) = O(1)$.

Heuristic alternative -- use R-tree

Alternatively, assuming we have dimension $d$ moderately low and fixed and not bound tightly by $O(n)$, we can arrive at times that appear to be subcubic in $n$. We have two options -- both use an R-tree variant with bulk-loading e.g. via sort-tile-recursive (STR) approach via Leutenegger 1997 and that is balanced and that is dynamic via bkd-tree-like occasional rebuilding (see Procopiuc 2003) to support inserts and deletes in $O(\log^2(n))$ time. See Guttman 1984 for details on standard R-tree. The main idea is that we find close descendants for each of $n$ provided rectangles via a total of $n$ close-descendant queries. We consider both options to involve heuristics because we may have many intermediate hunches for close-descendant that do not ultimately survive, even though subqueries have good guaranteed time for option one.

If we have pair-wise rectangles that do not frequently involve enclosure/containment and overlap is highly correlated with enclosure/containment, then it is conceivable that we can get better performance using R-tree via either of the two options for our approach. We note that a rectangle enclosure query asks for given a query rectangle rectangles that contain it and a rectangle containment query asks for given a query rectangle rectangles that fit in it. Close-descendant query roughly works via a heuristic approach. We find primitive rectangles contained by query rectangle and use auxiliary queries to see if returned rectangles have parents that are contained by original query rectangle. The candidate close descendants we store in a "conflict" secondary R-tree for purpose of speeding up checks in form of enclosure subquery with early-stopping that determine whether a candidate parent encloses (and disqualifies) a candidate close descendant; we maintain this conflict tree via inserts and deletes. We note that when we encounter rectangles of same shape, we may choose to keep one of them arbitrarily. We use a best-first priority queue to guide bounding box consideration order; we prefer contained bounding boxes and we tie-break by preferring larger bounding box area (because it is harder to be a middle-man for a larger contained box).

Option #1 -- use look-ahead

The first option is to use look-ahead for subqueries such as rectangle enclosure and rectangle containment in conjunction with corner transformation. Close-descendant query would then not directly use look-ahead; its subqueries do. Then, we have a coefficient of $d$ for look-ahead-using queries for edge checks. We won't go into much detail about look-ahead except that it requires roughly disjoint bounding boxes for siblings (though shared edge is allowed) and that it is related to knowing that one child out of two subtrees definitely has a match (which is made more straightforward to notice assuming we also use corner transformation) via $d$ edge checks at each node. It should be noted that without look-ahead enclosure and containment already take at least $d$ time for each node for an R-tree. We modify enclosure subquery to use early-stopping, which leads time for such a query to be $O(\log(n))$ instead of $O(\log^2(n))$. Time for each close-descendant query is in $O(k \cdot \log^2(n))$, where $k$ is number of hunch close-descendants s.t. $k$ is in $O(n)$. This means for $n$ close-descendant queries overall we take time in $O(k \cdot n \cdot \log^2(n))$ = $O(n ^ 2 \cdot \log^2(n))$. Since this is less than cubic in $n$ (though we omit a factor of $d$ assuming it is moderately low and fixed), this approach may be used to get better performance in practice. We have left out detail that for look-ahead-using enclosure/containment subqueries we may take non-constant time even if there are zero matches.

Option #2 -- do not use look-ahead

The second option is to not use look-ahead and all we can say (without further simplifying assumptions) is that for each close-descendant query we have worst case of $n$ hunches, each of which would then take $O(\log(n))$ time to find (because we don't go down a branch more than once). We note that we assume that we do not use corner transformation. As a result, we have an exceedingly loose and pessimistic time bound of $O(n \cdot \log(n))$ for attempt to disqualify a hunch close descendant via enclosure subquery with early-stopping. Time for a close-descendant query then is bounded by $O(k' \cdot n \cdot \log(n))$, where $k'$ is worst-case number of hunches (i.e. $n$). Time for $n$ close-descendant queries then is bounded by $O(k' \cdot n ^ 2 \cdot \log(n))$ = $O(n ^ 3 \cdot \log(n))$. This figure is more than cubic in $n$ (again noting that we omit a factor of $d$ as it is moderately low and fixed), but the times for the approach are considerably pessimistic and we believe there is still a chance that it can perform well in practice w.r.t. brute-force. We show that this is plausible by now making a few assumptions, which we discuss below. While the first option does not take advantage of possibility that number of hunches can be significantly lower than $n$ either, it has lower theoretical bounds because they take advantage of possibility that enclosure subquery with early-stopping for disqualifying a hunch close descendant can be guaranteed to be fast.

Option #2 -- three assumptions

Assumption "zero-overlap" says that (i) bounding boxes do not overlap with query rectangle unless we enclose query rectangle for enclosure query or we are contained by query rectangle for containment query; and (ii) bounding boxes for siblings s.t. neither sibling is contained in the other do not overlap except at a boundary. We note that part one of that assumption can only mostly be true e.g. because a real rectangle collection has a largest rectangle that cannot be enclosed and a smallest rectangle that cannot contain. We introduce $b$, which describes average false-positive-to-actual-positive ratio for believing that a child for a node is associated with a guaranteed match during disqualify attempt subquery s.t. $b$ is in $[0, 1]$. Time for second option close-descendant query is broken into two parts. The first part describes getting the hunches. The second part describes attempts to disqualify each hunch. The third part is to handle updates to conflict tree. Assume number of hunches is $k''$. The time for the first part is $O(k'' \cdot \log(n))$. The time for the second part is $O(k'' \cdot (b + 1)^{\log(n)} \cdot \log(n))$. The time for the third part is $O(k'' \cdot \log^2(n))$. The total time is loosely (assuming $b$ is one) in $O(k'' \cdot n \cdot \log^2(n))$. The time for $n$ close-descendant queries is $O(k'' \cdot n ^ 2 \cdot \log^2(n))$ = $O(n ^ 3 \cdot \log^2(n))$ if $k''$ is in $O(n)$. This does not appear to be better than brute-force. If we make "zero-overlap" assumption, $b$ is zero, which gives $n$ close-descendant query time of $O(k'' \cdot n \cdot \log^2(n))$ = $O(n ^ 2 \cdot \log^2(n))$ if $k''$ is in $O(n)$. The factor of $\log^2(n)$ (instead of $\log(n)$) comes from insert/delete for conflict tree of hunch close descendants. This assumption can be true for rectangles for a hierarchy that is highly coherent -- i.e. one with many realized enclosure/containment relationships and good separation between rectangles that are not related via enclosure/containment.

We have two other assumptions -- "uniform sparsity" and "no pruning", each of which have secondary purposes that are related to our application of quantitative association rule mining. They allow us to tune to reduce work drastically given that the second option for close-descendant query can be very time-costly. Specifically, say average number of partitions for a quantitative attribute (treating categorical attribute as possibly multiple two-partition quantitative attributes) is $p$; then, number of solid regions considered for each quantitative attribute is $p ^ 2$ -- all of which survive if we have "no pruning" assumption. As we reduce $p$, the space of all possible multi-dimensional rectangles shrinks and via "uniform sparsity" assumption for fixed $n$ we have more collisions (i.e. possibly more enclosure/contain relationships) but number of rectangles (that are made of combinations of solid regions for different attributes) shrinks faster -- this means that w.r.t. close-descendant query the amount of time required we can drastically shrink by reducing average number of partitions $p$ slightly.

Miscellaneous shared details

The only reason we believe one might wish to not use option one is slightly more implementation difficulty. We don't often see a proposed algorithm that performs reporting and that has for each match a coefficient for time that is not one. Still, the coefficient that we have of $\log(n)$ or $\log^2(n)$ is fine; $\log^q(n)$ for low $q$ is often acceptable wherever we see $O(1)$, as opposed to when we have e.g. $n$ where we see $O(1)$. In general, an R-tree is better than multi-layer segment tree for rectangle enclosure/containment/intersection queries or point domination query if $d$ is less than $\log^{max(d - 1, 1)}(n)$ for $d \geq 1$ given that for an R-tree we do not clone stored rectangles. Option one and option two with assumptions imply that we appear to be better than brute-force given that it is appropriate to omit $d$.

References

Pratyaksh - Transitive reduction of DAG - Answer (2014)
https://cs.stackexchange.com/q/29133
Wikipedia - Transitive reduction - Computing the reduction in sparse graphs
https://en.wikipedia.org/wiki/Transitive_reduction
Fischer, Meyer - Boolean matrix multiplication and transitive closure (1971)
Leutenegger et al. - STR: A simple and efficient algorithm for R-tree packing (1997)
Procopiuc et al. - Bkd-tree: A dynamic scalable kd-tree (2003)
Guttman - R-trees: A dynamic index structure for spatial searching (1984)


Is multiprocessing possible on a turing machine? I recently created a parallel implementation of the Merge Sort, in which the sorting of several groups was accomplished by different processes, and was wondering if this was theoretically possible on Turing Machine?

You can consider two variants of this question.

Can a Turing machine simulate parallelism?
Can a Turing machine simulate parallelism efficiently?

The answer for the first question is a resounding affirmative. Just like your own OS simulates threads on a single-core CPU, so a Turing machine can simulate parallelism.

Regarding the more refined second question, it depends on your definition of efficiency. You can probably simulate parallelism with at most a polynomial blow-up in resources (mainly time).

Turing machines are not a good model if you care about concrete efficiency. The more appropriate model is the RAM machine. RAM machines can probably simulate parallelism pretty efficiently, though you should not accept a running time any less that the combined running times of the individual threads in your parallel solution.


Proving a certain primitive recursive function exists Assume $f\colon ω × ω → ω$ is a computable function. How can we prove that there is a primitive recursive function $g\colon ω × ω → ω$ where the following holds:

$∀n [∃s(f(n, s) = 1) ↔ ∃k(g(n, k) = 1)]$

So for every $n$, there is an $s$ such that $f(n, s) = 1$ if and only if there is a $k$ such that $g(n, k) = 1$.

Been working on this problem for a while now, if anyone could please help?

The function $g$ interprets $k$ as two inputs $k_1,k_2$. It runs $f(n,k_1)$ for $k_2$ steps, returns whatever $f$ does if $f$ halts, and returns $0$ otherwise.


What's an upper bound for this recurrence so I can take advantage of the Master Theorem? Let

$$T(N) = \begin{cases}1 & \text{if } N = 1\\
T(\varphi(N)) + 2T(\sqrt{N}) + \lg(\varphi(N))^3 & \text{otherwise}
\end{cases}$$

where $\varphi(N)$ is Euler's totient function.  My objective is to find an upper bound so that I can apply the Master Theorem and find a closed-form formula.

In order to make this answer self-contained, I will repeat the first part of my answer to your other similar question.

First, show that for $N>2$, $\phi(\phi(N)) < N/2$. This can be done as such:

Let $N = \prod_{i=1}^rp_i^{k_i}$ be the prime factorisation of $N$ ($p_i$ prime, $k_i>0$)

Suppose $N$ is even. Then $\phi(N) = N\prod_{i=1}^r(1-\frac{1}{p_i}) \leq N(1-\frac{1}{2}) \leq N/2.$ Thus $\phi(\phi(N)) < N/2$.
Suppose $N$ is odd and $N > 1$. Then $\phi(N) = \prod_{i=1}^r (p_i-1)p_i^{k_i-1}$ is even and smaller than $N$. By the previous result $\phi(\phi(N)) < N/2$.

So we get the desired result.

Now, let $k>2$ be some fixed integer, and suppose $N\geq k^2$. You can write:
$$T(N) = T(\phi(N)) + 2T(\sqrt{N})+\lg(\phi(N))^3 $$
$$T(N) = T(\phi(\phi(N))) + 2T(\sqrt{\phi(N)})+\lg(\phi(\phi(N)))^3 + 2T(\sqrt{N})+\lg(\phi(N))^3$$
$$T(N) \leq T(N/2) +4T(N/k)  + 2\lg(n)^3.$$
Where we used that $N\geq k^2 \implies T(\sqrt{\phi(N)}) \leq T(\sqrt{N}) \leq T(N/k)$ in the last step.

(Note that I am implicitly assuming $T(n)$ is a monotonically increasing function. One could get rid of that assumption by working on $S(n) = max(T(n),S(n-1))$, at the cost of making the argument more tedious and harder to follow)

Now we can apply the Akra-Bazzi method (a generalisation of the master theorem) with:

$k = 2$
$a_1 = 1$, $b_1 = \frac12$, $a_2 = 4$, $b_2 = \frac1k$
$g(x) = 2\lg(x)^3$

First we need to find $p$ such that $a_1b_1^p + a_2b_2^p = 1$, that is: $$(\frac12)^p+4(\frac1k)^p = 1 \;\;\; (*)$$
Let's call $p_0$ the solution to $(*)$.

Then, we need to plug $p = p_0$ into the equation:
$$T(N) \in O(N^p(1+\int_1^N\frac{g(u)}{u^p+1}du))$$
To get:

$$T(N) \in O(N^{p_0}(1+\frac{6(N^{p_0}-1)}{p_0^4N^{p_0}\ln(2)^3})) \in O(N^{p_0})$$
(I just trusted WolframAlpha and did some simplifications for the integral, I'm too clumsy/lazy to attempt it myself if I don't have to)

Notice that in $(*)$ we can make $p_0$ arbitrarily close to $0$ by picking a big enough $k$. In other words, for any $\epsilon > 0$ there exists some $k>0$ such that $p_0 < \epsilon$. So let's pick any $\epsilon > 0$ and set $k$ such that $p_0 < \epsilon$. Plugging that into the last result we get:

$$T(N) \in O(N^\epsilon)$$

And this is true for any $\epsilon>0$.

In other words, $T(N)$ grows slower than any polynomial function in $N$.

I suspect it is asymptotically not much bigger than $\lg(\phi(N))^4$, as the square root term will vanish pretty fast, but I can't prove anything better than what I showed.

Also note that you could use the master theorem by setting $k=2$ and working on the upper bound $T(N) \leq 5T(N/2) + 2\lg(N)^3$, but this would of course lead to a much weaker result.


Minimize sum of $w_i(y_i-y)$ given $|y_i-y| \leq 4w_i$ Given numbers $y_1,\ldots,y_n$ and $w_1,\ldots,w_n > 0$, find $y_c$ which minimizes $$ L = \sum_{i=1}^n w_i (y_i - y) $$
under the constraint $|y_i - y| \leq 4w_i$.

How to proceed?

Write
$$ L = \sum_{i=1}^n w_i y_i - \sum_{i=1}^n w_i y. $$
Thus $L$ is linear in $y$, and moreover, it is a decreasing function. Thus we want to choose the largest $y$ which satisfies the constraints $|y_i - y| \leq 4w_i$, if any. I'll let you figure out how to find this $y$.


New special data-structure I want such data-structure, which can:

add element at the end of the array in $O(log (n))$.
find out the minimum value in the sub-segment in $O(1)$

You can use a Sparse-Table for these type of queries.

Most implementations/tutorials on Sparse-Tables don't actually cover/support the usecase of adding new values (actually I've never seen one before), however it shouldn't be too hard to modify a typical implementation. You basically only need to invert what each entry stores.

Normally a sparse table stores the following things for each element at position $i$. It stores the minimum of the range $[i, i+1)$, the minimum of the interval $[i, i+2)$, the minimum of of the range $[i, i+4)$, the minimum of the interval $[i, i+8)$, and so forth.

This is a problem when you want to append a new value, because it will affect at least one range for each element, so adding a new element is $O(n)$.

However if you point the ranges in the opposite direction, you do better. So for each element at position $i$, you store the minimum of the ranges $(i-1, i]$, $(i-2, i]$, $(i-4, i]$, and so forth. You can still do the answer minimum queries in $O(1)$, but now if you add a new element at the end, you only need to recompute $O(\log n)$ ranges, namely the new ones for the new element. You don't need to modify the other entries.

One thing that you additionally should take into care. Whenever your array gets gets bigger than a power of 2, you need to compute a new range for each element (in $O(n)$ time). But that's still amortized $O(\log n)$.

edit: Actually, now that I think about it more, this $O(n)$ recomputation can be avoided. Notice, that a those new ranges $(i-2^{\log n + 1}, i]$ will contain exactly the same values as the previous ranges $(i-2^{\log n}, i]$. Therefore you can always just lookup the largest range $(i-2^j, i]$ if you want to want to know the range $(i-2^k, i]$ with $k \ge j$. Then adding a new element works in true $O(\log n)$ time, and not just in amortized time.


Iterative lengthening search: iterative version of Uniform Cost Search or DFS? Actually my question has two parts:

1) I wanted to know that whether Iterative Lengthening Search is used in combination with DFS or Uniform Cost Search? Actually, in Russell and Norvig book (on page 90), it is described as follow:

  It would seem worthwhile to develop an iterative analog to uniform-cost search, inheriting the latter algorithm's optimality guarantees while avoiding its memory requirements. The idea is to use increasing path cost limits instead of increasing depth limits. This resulting algorithm is called iterative lengthening search... It turns out, unfortunately, that iterative lengthening incurs substantial overhead compared to uniform-cost search.

It seems that by using "avoiding its memory requirements", they mean that we use it in combination with DFS.

But, here in this link, which is the solution of final exam problems of artificial intelligence course at CMU, on page 4, it is described as follow:

  Iterative lengthening search is an iterative version of uniform cost search. The main idea of this algorithm is that we use increasing limits on path cost.

  We start searching as though we were performing uniform cost search.

  and so on...

And also here in this link, question 4, part 1:

  Iterative lengthening is uniform-cost search which is run multiple times with an increasing bound on the maximum cost from the start to reach before quitting. Iterative lengthening search doesn't have advantages in the same way iterative deepening depth-first search does.Iterative lengthening will simply search the same nodes each time adding more at the end since the first closest node, second closest node, etc. is invariant. All that iterative lengthening does is require the algorithm to restart repeatedly before finding a solution.

It seems that they mean we use it in combination with Uniform-Cost search.

Actually, I implemented it using uniform cost search, but to me there is no point in running uniform cost search over and over from beginning while increasing path cost limit (I mean using DFS seems more reasonable).

So which one is correct? (Is it the case that I misinterpreted them?)

2) Would you clarify why iterative lengthening search occurs substantial overhead?(Actually in case of using Uniform-cost search it is obvious, but I wanted to know this in case of using DFS.)

Clarification:

In order to resolve any ambiguity, here is pseudocodes for ILS in both cases(using DFS or UCS):

ILS using DFS:

0. Set limit to zero.
1. Perform DFS on initial node while discarding any generated node with path cost greater than limit.
2. If DFS ended with Failure or Success, return that as a result.
3. Otherwise set limit to minimum path cost of generated nodes that were discarded in previous run of DFS.
4. Go to line 1.

ILS using UCS:

0. Set limit to zero.
1. Perform UCS on initial node while discarding any generated node with path cost greater than limit.
2. If UCS ended with Failure or Success, return that as a result.
3. Otherwise set limit to minimum path cost of generated nodes that were discarded in previous run of UCS.
4. Go to line 1.

I was thinking about this for the past week. I think that ILS in combination with UCS has no advantages to UCS itself. While ILS in combination with DFS, at least is much better than UCS in terms of memory usage. And I think overhead occurs because in both of them, in each iteration only one more node(or a few if we have several nodes with same minimum path cost) is added to nodes that we explore in next iteration. However I'm not sure about these.

Typically iterative deepening searches are used with DFS to improve the memory usage.

Consider BFS and IDDFS, both are optimal and complete but IDDFS in a tree search will use only $O(bm)$ space, where $b$ is thebranching factor and $m$ is the maximum height of the goal.

Now extending this to Uniform Cost Search using DFS, if we increase the max depth step by step, we are doing too many iterations over already visited nodes, whereas this was not true in case of IDDFS because of one step increase at a time (look for the overhead factor). So though using iterative search with DFS can save huge space ($O(bm)$), it gets worse with time complexity.

Secondly, there is no point in using Iterative Search with UCS as it is never a better upgrade over simple UCS in terms of space and time complexities.


Are NP proofs limited to polynomial length? In computational complexity theory, NP (nondeterministic polynomial time) is a complexity class used to classify decision problems. NP is the set of decision problems for which the problem instances, where the answer is "yes", have proofs verifiable in polynomial time by a deterministic Turing machine.

The proofs for an NP decision problem are verified in polynomial time.

Does this imply the proofs are at most polynomial length?

"Well you have to read the whole input. If the input is longer than polynomial, then the time is greater than polynomial."

The decision problem "Is the first bit of the input a 0?" can be solved in constant time and space - without reading the whole input.

Therefore, perhaps some NP problem has candidate proofs that are longer than polynomial length but checked in polynomial time.

The decision problem "Is the first bit of the input a 0?" can be solved in constant time and space - without reading the whole input.

Given that a Turing machine head moves right one step at a time, a Turing machine head can only read a polynomial amount of the proof in polynomial time.

While you could define proofs to exceed a polynomial length, only a polynomial prefix of the proof could be read in polynomial time, assuming the head starts at cell 0 and can move at max one cell to the right in one time unit.


How to calculate a direct mapped chace capacity with tag and valid bits? I've seen some very useful posts about this, but none took into consideration both the tag and valid bits. This is a question I took from a notebook in my computer engineering course.

  Consider a machine with a direct mapped cache, with 1 Byte blocks and 7 bits for
  the tag. This machine has a RAM with 2 KB capacity. Calculate the cache's total capcity, counting the tag bits and valid bits.

Breaking a cache into parts, I have the tag bits, set index and block offset.

I already know I have 7 tag bits, but then I'm really not sure how to calculate the rest, because in this type of question we are usually given the words per block. I think the offset is 3, because 2^3 (8 bit blocks).

I feel like the question itself doesn't give enough, shouldn't it be stated how the system address is (byte/word addressable)? Also, is the RAM capacity relevant to the question at hand?

Unless specified otherwise, addresses are always byte adresses (and with a cache with 1B/block, any other choice would not make sense)

Ram size is relevant as it indicates addresse width.

Cache blocs are 1 byte -> offset=0b (offset indicates byte position in block and only 1 possible position).

RAM is 2kB (2^11) -> address is 11 bits

Adress width=Tag with+Index width+Offset width

Tag=7b, Address=11b, Offset=0b -> index=4b

Cache is direct Mapped -> Cache size for data=number of blocks * block size = 2^(index size)*(Block size)

-> Cache Size (data) = 2^4*1B=16B

Block associated with Tag(7b) + 1 valid bit -> 1 extra B for control per block

Total cache size = 16 block each with 1B data and 1B control -> 32B


Why does the operating system switch an active process to different cores? When running a single-threaded application that is 'always busy', on a multi-core computer, modern operating systems will typically switch the process from one core to another from time to time. Even when the other cores are always idle.

Typically you can see 1 of 4 cores on a quad core processor at 100% load while the other cores are 0-1%. Once in a while, the active process will 'jump' to another core, now leaving the original core idle and utilizing 100% of another core.

Why does this happen?

Is it because the process was context-switched (even though other cores were idling)? Or is it because of thermal or power-related reasons? Something else?

Multitasking works like this: allow user process to execute for a little, then switch back to OS scheduler to be able to execute something else.

In multicore architectures, every core has equal opportuninty to acquire the process.

If you want to force your process execution on the selected core, this selection must be stored somewhere. There’s usually no reason to do that.


What do f(x) and g(x) represent in Big O notation? I have been reading about Big O notation. People writing about Big O often use the terms $f(x)$ and $g(x)$. For instance, I often see people write things like $f(x) = O(g(x))$ or $f(x) \in O(g(x))$.
Obviously $f(x)$ is the running time of the given algorithm we are comparing against infinity, but what does $g(x)$ represent?

Summary: $f$ and $g$ are typically functions, and $f$ is typically the runtime and $g$ is typically the asymptotic complexity of $f$. But if any of this is unclear from the description, I think it is best to either find another explanation, or to forget about application domains and intuitions for a second and go back to the definitions.

They're both functions. The fact that they are named "f" and "g" is probably due to the usual naming convention of functions, just like "x", "y" and "z" are usual names given to variables.

In this context, $f(x)$ is often the runtime of the algorithm under question, while $g(x)$ is used to denote the asymptotic complexity of $f(x)$; so $f(x) \in O(g(n))$ (or, $f(x) = O(g(n))$). But, convention or not, what $f$ and $g$ are, and they're relation to each other (if any), should be clear and unambiguous from the explanation. Not something that the reader has to guess based on what it usually means. (And the reader should have the mathematical maturity that is necessary to understand the concept.)

Personally, when I am confused about terms and names that are being used, I like to try to forget everything that the terms and names are ultimately used to represent. In computer programming, big-o is often used to describe algorithms. But big-o notation itself abstracts such things away; it is only about functions and their relation to each other. Forget about "runtime", "complexity" or anything else that has to do with the intended application of the notation.

Here is an example:

  Let $f$ and $g$ be two functions defined on some subset of the real numbers. One writes

  $f(x) = O(g(x))$ as $x \to \infty$,

  if and only if there is a positive constant $M$ such that for all sufficiently large values of $x$, $f(x)$ is at most $M$ multiplied by the absolute value of $g(x)$. That is, $f(x) = O(g(x))$ if and only if there exists a positive real number $M$ and a real number $x_0$ such that

  $|f(x)| \leq M \cdot |g(x)|$ for all $x \geq x_0$.

We see that $f$ and $g$ are functions. Together with all the variables used, and the relations between them, what $f(x) = O(g(x))$ means is as clear as you might reasonably expect from a Wikipedia article on a mathematical topic. We don't have to consider what this notation is supposed to be used for, and neither what those functions are even supposed to represent/model. Now, going back to the application domain of algorithm analysis; can we use this notation to describe algorithms? Yes, since runtimes of algorithms are just functions on real numbers. Then what does it mean when $f(x) = O(g(x))$, in the context of algorithm analysis? If $f(x)$ is the runtime of the algorithm, then this notation means that $f(x)$ (a runtime) does not grow more quickly than a multiple of $g(x)$, for sufficiently large $x$. That's all from reading from the definition, and interpreting $f(x)$ as a runtime.

Pitfalls of convention

Sometimes, conventions can be misleading. In fact, we've seen a "violation" of a usual mathematical convention in this post.

$f(x) = O(g(n))$

Here, the $=$ sign is used. At least for us non-mathematicians, we are used to this sign denoting a sort of equality between two things. This usually means that the two things are of the same type, e.g. they are both real numbers, and that they are equal in some sense. In particular, $=$ is often an equivalence relation. But this is not the case of this particular use of the $=$ sign. First of all, $f(x) = O(g(n))$ does not mean that $f(x)$ and $g(x)$ are equal: the closest "normal" relation to this is "$f(x)$ is less than or equal to $g(x)$", which obviously has nothing to do with equality (except as a special case). Secondly, $f(x)$ and $O(g(x))$ are not even of the same type: $f(x)$ is a function, while $O(g(x))$ is a class of functions. (An alternative notation to $f(x) = O(g(x))$ is $f(x) \in O(g(x))$, which I used in the beginning. It is arguably more "honest".)


Is this a new compression approach? I've come up with an idea on how to compress data. But I'm not sure if the approach already exists. I would like to know if it does already, and if so, what its name is.

The approach is to:

Convert the message to a number
Find the smallest equation to represent the number

The result of this is an equation. Which will be much shorter in length than the original message, or its corresponding numerical value.

The process can be reversed by evaluating the equation, and then converting the number back into the message.

Step 1. is similar to base conversion but has the following numerical sequence...

Given an alphabet of "abc"...

Message, Value
a,       0
b,       1
c,       2
aa,      3
ab,      4
ab,      5
ba,      6
...

Value "aa" shows the difference between base conversation. In normal base conversion the value of "aa" would be 0 because "a" is the first letter of the alphabet and has a value of 0, so two of them would also be zero.

The value is really the permutation sequence number for when the alphabet is iterated over (or "bruteforced"). (Aside: Useful when distributing "bruteforce" problems.)

For step 2. I plan on using state space search to generate the equation. The goal state will be the smallest equation. The search will be performed by applying and accepting a single math operation on the "remaining" value. Initially, the "remaining" value will the original number. By the end of the search it will be reduced to zero.

Non-answer feedback is welcome as comments on the question.

"The result of this is an equation. Which will be much shorter in length than the original message, or its corresponding numerical value." If that were true, your scheme would be able to compress every input by at least one bit. This is provably impossible by a simple counting argument (there are $2^n$ $n$-bit strings but only $2^n-1$ strings of length less than $n$), so your claim cannot be true.


How to Study Space Complexity I am working through Sipser, and I am trying to understand some of the algorithms described in Space Complexity, but I am having a hard time understanding the presentation of the material (especially Savitch's theorem). I have a very strong intuition for time complexity, but I don't understand how space complexity fits into a heirarchy of time complexity, and I think it has to do with the fact that it is all discussed in terms of Turing machines. It is hard to see how space and time are related when I'm wasting time untangling convoluted algorithms described in terms of Turing machines.

Does anyone have any advice on how to think about Turing machines vis-a-vis contemporary computation in general? It is unintuitive to think about algorithms in terms of input strings, tapes, and machines simulating machines. I don't feel like I am leveraging my existing knowledge of computers and programming to more deeply understand the proofs and algorithms being presented.

I think I just need help understanding how space varies based on the data structure of the input. For some input of size $n$, are the bits required to represent each entity of the input negligible? Say our language is a set of objects that are all of a certain type, and each object is massive. How does space usage vary vs. a similar language with very small objects?

Edit: I understand now that space complexity fits in with time complexity because they are both resources used to determine whether some string is a member of a language; Or in other words, whether some element belongs to a particular problem (see here).

Space Complexity measures the amount of space it takes to carry out a specific task (as a function of the input size). It is very similar to time-complexity, that measures the amount of time it would take to complete the task. In both cases, the complexity highly depends on the specific model of machine (RAM machine is faster than a double-tape Turing Machine, which is in turn faster than a single-tape Turing Machine).

Let's now focus on a specific simple model: Single-tape TM.

Example: Sorting

Consider a simple task: say, sorting. The input is a list of numbers $x=\{a1, a2, ...\}$ and the machine should write them in order. The size of the input is $|x|=n$.

One way to perform this task on a single-tape Turing machine, is to perform a Merge Sort: we look at the first number $a1$, split the list into two list, one for numbers that are larger than $a1$ and the second list with the other numbers (and then we repeat it recursively).

But how do we implement "spitting the list into two" on a single-tape TM?
A possible solution will mark the end of the input, then go over the list $n$ times, and every time it finds a number that should be on the second list, it will move it to the end of tape.
So, if we started with $n$ numbers, now we have a list of $2n$ places (some of which will be empty, since we "moved" the numbers to somewhere else). If we continue with this naive approach, we will keep increasing the space in use more and more, and will get a very large space complexity (say $n^2$ if we stupidly double the space at each phase of the recursion).

But there is a more efficient way to do it: after creating two lists, we can "close the empty gaps" that occurred when we moved elements. Since we never add or remove elements, the same amount of space we started with is always big enough to keep the intermediate lists.
For this approach we might need to maintain some counters that will tell us where each list begins and ends. Using smart methods, this can be done very efficiently, so that we will never use more than $\approx 2n$ cells of the tape. That is, the space complexity is $O(n)$ in this case.
 (see also In-place merge sort, which is not exactly what I was talking about, but might give you more intuition)

Now you can also see that Space and Time are related. If we perform the space-efficient variant, the TM needs to do some extra-work of "closing gaps", marking start and end points, keep track of counters, etc. This extra work takes time.
It is very common that there is a tradeoff between space and time:
if the algorithm is very fast, it takes a lot of memory, and if it is very space-efficient then it takes more time. For the task of sorting, see a table comparing the time and space complexity of various sorting algorithms. (Note that in that table they count the space complexity excluding the input).

Space complexity and its relation to Time complexity

So now we can define the space complexity of "sorting" as the minimal space it takes to sort. That is, take the most-efficient (memory-wise) sorting algorithm. How much space does it take to sort $n$ elements? This is the space complexity of sorting.

More generally, we can define classes of tasks that take the same space complexity. For instance $DSPACE(n)$ contains all the tasks that can be solved using $O(n)$ memory. Said differently, it contains all the tasks whose space-complexity is at most $O(n)$

There is a strict hierarchy here: If we know that a task needs $O(n)$ space, it clearly cannot be in $DSPACE(1)$. More accurately, for any function $f(n)$,
$$ DSPACE( o(f(n)) \subsetneq DSPACE( f(n)).$$

Finally, we can relate time and space:
$$DTIME (f(n)) \subseteq DSPACE(f(n)),$$
since in $x$ time we can access at most $x$ cells of the tape. More interestingly, we know that
$$DSPACE(f(n)) \subseteq DTIME(2^{O(f(n))}).$$
That is, whatever task that we can solve using $x$ bits of memory, we can also solve using in at most $2^{O(x)}$ time-steps. This follows since a machine with $x$ memory has  maximal number of $2^{O(x)}$ different configurations, so if it doesn't go into an infinite loop it must end in less than $2^{O(x)}$ time.


Stuck in converting finite automata to its corresponding regular expression I'm trying to convert the following finite automata (DFA) to its corresponding regular expression using state elimination algorithm.

For this I'm following this link. The answer of that question has following example.

But in this sample automata, there is no state between the two looping transitions. For example there is no state between transition q to r and back r to q. But in my question, there is three such cases as mentioned in the above 1st diagram. For example there is a state IV between the transition III to V and back V to III, via a. For another example, there is three intermediate states between transition I to V and back V to I via b.

I've tried to search such case on INTERNET, but can't found such issue. I've tried to attempt this question and could eliminated the II state, as following:

I'm stuck in eliminating state I, III and IV. Suppose I remove state III, than where should the transition from V to III via a can be placed? If I eliminate state IV, what will happen to transition IV to I?

Is there any general method for this type of cases? Any help will be appreciated.

Thank you very much in advance!

Let's merge IV.

We have three edge transitions to consider:

IV to I, consuming a b (1)
IV to V, consuming an a (2)
III to IV, consuming a b (3)

The only way I can enter state IV is via III (3). Hence, any state that can be reached from IV can also be reached from III.

Let's now look at the path III -> IV -> I, which is the concatenation of (3) and (1). Let's forget about states for a second and simply look at paths and the consumed symbols. There exists a path ((3),(1)) that allows us to get from III to I by consuming a bb.

Due to this fact, we can just add an edge III to I consuming a bb without changing the accepted language of the automaton. It's just a shortcut for the existing path. Once we added the edge, the original path is redundant. If I'm sitting at III, instead of walking the path (3),(1), I can just take the shortcut.

Once I have made all the paths redundant that pass through a state, the state itself becomes redundant and I can remove it along with all its edges.

We can apply the same logic to III -> IV -> V. This introduces a shortcut edge III to V consuming a ba.

With those two in place, we have covered all paths that pass through IV. You can easily enumerate all paths by taking the Cartesian product of incident and outgoing edges: I have a certain number of ways of reaching the state, and for each of those I have to consider all the possible ways of exiting the state again.

Now it's just rinse and repeat. Pick a state, enumerate all paths through it, insert shortcut edges that make all paths redundant and then remove the state along with all its edges.

The only thing to watch out for are loops. The answer you linked in your question should give you a good idea how to deal with those.


Greyscale image to binary image conversion using operations on pixel Previously, I tried convert a color image into a greyscale image by using pixel values of an image from a simple formula :-

Grey = 0.3*Red + 0.58*Green + 0.11*Blue

After that, I wanted to convert the greyscale image into a binary image & I used two different techniques :

NOTE : Red, Green & Blue are variables storing Greyscale intensity of the Pixel.

1. Algorithm 1:

if Red <= 127:
   Red = 0
   Green = 0
   Blue = 0
else:
   Red = 1
   Green = 1
   Blue = 1

2. Algorithm 2:

if Red <= AvgIntensity:
   Red = 0
   Green = 0
   Blue = 0
else:
   Red = 1
   Green = 1
   Blue = 1

where, AvgIntensity represents the average intensity of all the pixels of the image.

(Obviously,) the algorithms turned out to be wrong, producing incorrect output. So, I wanted to know about the correct way for greyscale to binary image conversion.

You are looking for a thresholding algorithm.  There is no correct or incorrect algorithm.  Some methods tend to work better than others on specific types of images; which method is best may depend on what kind of images you usually work with. I suggest studying standard thresholding methods and picking one.


Which measure of sortedness explains the phase transition in Quicksort's runtime? I'm currently creating a program to analyse the pathological cases of Quicksort. Namely, the transition of complexity from $O(n^2)$ to $O(n \log n)$ as a data set gets less ordered. Since Quicksort is a value-based algorithm, the choice of pivot determines its efficiency. We usually (Quicksort 3, and choosing a random element aside) select the first or last element as the pivot in an array. Therefore, since a good pivot is one that splits the array in half symmetrically, a more disordered array will make selecting a good pivot easier; or at least reduce the likely hood of running into the pathological case.

My program gradually randomises this array by swapping some elements each time. When I started to plot the graph of this using gnuplot I notice the trend I expected; a exponential distribution, branching off to a uniform distribution.

My question is, how do I quantify a level of disorder in a array? Is their a better way to gradually make an array of values more disordered?

Inversions are one way to measure "disorder" in a list:

  Let $A[1..n]$ be an array of $n$ distinct numbers.  If $i < j$ and $A[i] < A[j]$ then the pair $(i,j)$ is an inversion of $A$.

However, it's not the only such measure. In general, this concept is formalized in the notion of presortedness - roughly:

  An integer function on a permutation $\sigma$ of a totally ordered set that reflects how much $\sigma$ differs from the total order.

The survey papers by Mannila [1] and Estivill-Castro & Wood [2] might be good places to start.

The question How to measure "sortedness" is related.

[1] Heikki Mannila. "Measures of Presortedness and Optimal Sorting Algorithms." IEEE Transactions on Computers 34.4 (1985): 318-325.

[2] Estivill-Castro, Vladmir, and Derick Wood. "A survey of adaptive sorting algorithms." ACM Computing Surveys (CSUR) 24.4 (1992): 441-476.


Maximize the number of edges in subgraph We are given a graph $G=(V,E)$ and we want an algorithm to find a set of vertices $U$ to maximize the following quantity : $\frac{|E(U)|}{|U|}$ where $E(U)$ denotes the number of edges in the subgraph made with vertex set $U$.

Your problem is known as densest subgraph. According to Wikipedia, there is a polynomial time algorithm based on flow networks, due to Goldberg. See Goldberg's technical report Finding a maximum density subgraph.


What is the formalism to prove statements about uniqueness of functions with certain signatures Suppose I want a function like

f: ((A, B) -> C) -> A -> B -> C

A statement I've often seen made is that f has just one implementation, namely the 'curry function', i.e. g => a => b => g(a, b)

Taken at face value this doesn't seem to actually be true, I can always define f as acting differently from this in special cases, e.g. I can say it is g => a => b => g(a, b) except when A = B and then I define it as g => a => b => g(b, a).

Nonetheless, it's intuitively clear enough what is meant by 'has just one implementation'.

I would like to know the correct formalism in which statements like the above can be proven.

At a guess I would suspect it is category theory? The above feels a bit like the notion of a natural transformation, but I don't really see the details.

I'm sure there is a connection to category theory, but you can actually do it with (what I consider to be ) a simpler tool: parametricity.

They basic idea is that, when a language has the property that polymorphic types do the exact same thing for each type they're instantiated to (i.e. there's no typecase construct), we can prove very powerful properties about the language, in the form of a logical relation.

This prevents exactly the "special case" implementation that you describe in your question. It's also worth mentioning that these implementations are all extensionally equal: they might look different but produce equal results for equal inputs. e.g. you can replace any term $t$ with $(\lambda x \ldotp x) t $ and get an equivalent function.

The statements about functions only from their type are generally called free theorem, named after the paper that introduced the idea: Theorems for Free by Phil Wadler. If you're interested in this area, I highly recommend the paper, since it's a good introduction to the subject.

The idea behind this actually goes much further back than that paper, to John Reynolds work with System F and the "abstraction theorem" but it took a while before the idea became popular.

You can actually generate free theorems at http://free-theorems.nomeata.de/, although it might take a bit of massaging to get useful information from the theorems they give there.

If you're interested in parametricity used to prove things other than free theorems, like type safe, then Amal Ahmed's thesis is the best introduction I've seen. She really does a good job of describing semantic types: the type of a program is actually a property of how it runs and what it produces, and what we call "types" are a syntactic approximation of these more general semantic types.


Can a Turing Machine have fewer states? I am currently learning about Turing Machines, I am curious if a Turing Machine can have fewer states ?  Can it be done like a Transition Graph where you can have multiple states at once ?

I got this TM off of a youtube video sorry for bad hand writing, but could I just merge some of the states like you would do in Transition Graph, so instead of having 5 states it would have 4 states ? TM are more advanced so I don't know if you are even able to do this...thanks!

how could I make this into 4 states TM instead of 5 states ? in TG if would take 5 seconds do it...

It is undecidable to check whether a turing maching has a smaller encoding than a given one.  Hence there cannot be any such concept as a transition graph.

If you simply want a smaller turing maching for your example, I would guess no, from a quick glance of it.


CFL not closed under intersection while Turing Decidable are It makes me wonder that despite of (CFL) being a subset of Turing Decidable languages, Turing Decidable is closed under intersection while CFL is not.

Does not Turing Decidable engulf all CFLs?

Yes, all CFLs are Turing-decidable but a subset of an intersection-closed class of languages is not necessarily intersection-closed. CFLs and Turing-decidable languages are just one example of this.  In fact, this is not an unusual situation:

Theorem. Let $\mathcal{L}$ be an intersection-closed class of languages containing languages $L_1$ and $L_2$ such that $L_1\cap L_2\neq L_1$ and $L_1\cap L_2\neq L_2$.  There is a class $\mathcal{L}'\subset\mathcal{L}$ that is not intersection-closed.

Proof. Just take $\mathcal{L}' = \mathcal{L}\setminus \{L_1\cap L_2\}$.  $\mathcal{L}'$ contains $L_1$ and $L_2$ but does not contain their intersection, by construction. $\quad\Box$

The simplest possible example is the class of languages $C = \big\{\emptyset, \{a\}, \{b\}\big\}$.  This is closed under intersection but the subclass $C' = \big\{\{a\}, \{b\}\big\}$ is not, since $\{a\}\cap\{b\}=\emptyset\notin C'$.

Conversely, a superset of an intersection-closed class of languages is not necessarily intersection-closed.  Here's an example. Let $\mathcal{R}$ be the class of all Turing-decidable languages. Fix some coding of Turing machines and let $H$ be the language of codings of all Turing machines that halt when given empty input. It is well known that $H$ is undecidable, so $H\notin\mathcal{R}$.  I claim that $\mathcal{R}' = \mathcal{R}\cup\{H\}$ is not closed under intersections. To see this, let $h$ be any string in $H$ (for example, $h$ could be the coding of some program that just loops for all input). The language $L = \{w\mid w\neq h\}$ is clearly in $\mathcal{R}$.  $L\cap H\neq H$, since $h\in H$ but $h\notin L\cap H$. And $L\cap H\notin\mathcal{R}$ since the language of all Turing machines except for $h$ that halt when given empty input is also undecidable. Therefore, $\mathcal{R}'$ is not closed under intersections, since $L\in\mathcal{R}'$, $H\in\mathcal{R}'$ but $L\cap H\notin\mathcal{R}'$.


What factors must one consider choosing an NN structure? Suppose we have a classification problem and we wish to solve the problem by Neural Network. What factors must one consider choosing an NN structure? e.g Feed Forward, Recurrent and other available structures.

Here is a list of parameters you should take into consideration (to name some):

The learning algorithm (gradient descent is the most explained of them)
The number of layers (3,4 layers is usually enough - input, 1 or 2 hidden, output). The output layer depends on your output (e.g., if you want to classify yes/no then your output layer consists of two nodes). The same applies for input layer. However, you may consider the case of using only a subset of the input for the learning. For instance, you may think that your problem is affected by $k$ variable. However, if you take $k'$ of them then you may get better results.
Number of nodes in the hidden layers (you select that by trial and error)
Number of training iterations (not too much to avoid over-fitting)
Size of training/testing data (there are some known rules like the 80:20 for example)
The type of the function used at the nodes (neurons) (e.g. $f(x) = 1/(1+e^x)$ or $f(x) = tanh(x)$), usually the first is sufficient.
An important issue is the pre-processing and post-processing of data (this is common in all pattern recognition techniques). You may for instance convert your data by applying a certain function $f$ and then run your experiments.

Note: given the many parameters you need to deal with, it is a good approach to use a search algorithm to select the best parameters for you. It is better be a heuristic search algorithm (e.g. genetic algorithm) if you had very large number of parameters set you will deal with (which is usually the case).

Note: use the Matlab NN library or Weka (open source). They would have all these parameters for you.  In fact, Weka has many other learning algorithms.

Note: Perhaps, you may want to use other algorithms then. If this is case, try support vector machines. There was a historical battle between these two algorithms (in the 1990's). SVM won it ! (I am not being very scientific here).


Data link layer Sliding Window utilization formula query In the data link layer, the Sliding Window is used for flow control.

There are two link utilization formula that can be use. They are :

U = 1, for N > 2a + 1

OR

U = N/(1+2a), for N < 2a + 1

In both formula, N denotes the window size and a = Propagation time / transmission time

I am not really understanding which formula to use in what situation although the condition is specified. What does 2a+1 actually mean? Can anyone help me to understand it in  simple term. Thanks!

If it is about how we got to the formula, link utilization is the ratio of the time that the link is active to the total time.

total time being the sum of transmission time and propagation time.
link active time = time taken to transmit N packets = N * TransmissionDelay

Hence, the formula to calculate link utilization(or efficiency) is

N/(1+2a)

However, in practice, the link utilization cannot exceed 1 (ie link cannot be active for more than 100% of the time).
Hence, whenever N>(1+2a), we restrict the value to 1 only.


How important is initial state for local search optimisation? I have been enjoying Pascal van Hentenryck's Discrete Optimisation course and we're in Week 4 on the wonders of Local Search algorithms for combinatorial optimisation.
I'm wondering how important the initial configuration is to the quality of solution achievable in a fixed time or, somewhat equivalently, how quickly a solution of a given quality can be reached.
So if I have a good heuristic or intuition for how to arrange things in the first place, is it helpful to devote some processing time to setting that up or is it all dominated by the effect of the local search process?
For example, in the Cartesian Travelling Salesman Problem (where we're working in a 2D plane and the cost of a journy is simply the straight-line distance) I might "feel" that a good route could roughly follow a clockwise sweep from the centre of the space.  So I could use this to set my initial tour (i.e. order the nodes by their angle from the mean of all points).  This intuition might be rubbish for certain instances and great for others, I was hoping to see a study where (let's say random TSP) instances had been solved by following a heuristic first state as opposed to a completely random (but legal) first state.

A good initial state can often be helpful.  I would guess that there is a significant chance that spending extra time to find a good initial state will be useful.
All we can say in general is that "it depends".  It depends on the specific problem and the shape of the fitness landscape.  If the problem has few or no local minima, the search might not be very sensitive to the initial state.  If it has many local minima, the search might be very sensitive to the start state, and a good start state might help again.  There are no universal answers that can be supplied.
Usually the only way to answer these questions is to try it and see.  With heuristics, there aren't any provable guarantees and it's often hard to make many predictions based on theory or analysis.


Computer science fields that deal with peer-to-peer systems I'm an undergraduate and am looking forward to becoming an academic; do the whole PhD stuff and start doing research. I'm interested in a variety of computer science related things but lately P2P technologies have really caught my interest. I have the impression that I need to choose one of the computer science fields to perform my PhD studies in, so now I'm wondering how to do  that, given my interest in P2P technologies. Would P2P fall under the area of distributed systems and such?  Which fields of computer science are most relevant to P2P systems?

Distributed systems, algorithms and even graph theory are fields that are likely to be relevant.

But, in a sense, "fields" aren't particularly relevant. You don't get a PhD "in a field" but, rather, by finding an advisor who wants to do a research project with you. That person would probably be in one of the fields I've suggested but being in a field isn't a formal status.


Clarifying statements involving asymptotic notations in soln of $T(n) = 3T(\lfloor n/4 \rfloor) + \Theta(n^2)$ using recursion tree and substitution Below is a problem worked out in the Introduction to Algorithms by Cormen et. al.
(I am not having problem with the proof but only I want to clarify the meaning conveyed by few statements in the text while solving the recurrence and the statements are given as ordered list at the end. Simply because I want to master the text.)

$$T(n) = 3T(\lfloor n/4 \rfloor) + \Theta(n^2)$$

Now the authors attempt to first find a good guess of the recurrence relation using the recursion tree method and for that they allow sloppiness and assumes $T(n)=3T(n/4) + cn^2$.

Though the above recursion tree is not quite required for my question but I felt like including it to make the background a bit clearer.
The guessed candidate is $T(n)=O(n^2)$. Then the authors proof the same using the substitution method.

In fact, if $O(n^2)$ is indeed an upper bound for the recurrence (as we shall verify in a moment), then it must be a tight bound. Why? The ﬁrst recursive call contributes a cost of $\Theta(n^2)$ , and so $\Omega(n^2)$ must be a lower bound for the recurrence. Now we can use the substitution method to verify that our guess was correct, that is, $T(n)=O(n^2)$ is an upper bound for the recurrence $T(n) = 3T(\lfloor n/4 \rfloor) + cn^2$ We want to show that $T(n)\leq d n^2$ for some constant $d > 0$.

Now there are a few things which I want to get clarified...
(1) if $O(n^2)$ is indeed an upper bound for the recurrence. Here the sentence means (probably) $\exists$ a function $f(n) \in O(n^2)$ such that $T(n)\in O(f(n))$
(2) $\Omega(n^2)$ must be a lower bound for the recurrence Here the sentence means probably $\exists$ a function $f(n) \in \Omega(n^2)$ such that $T(n)\in \Omega(f(n))$
(3) $T(n)=O(n^2)$ is an upper bound for the recurrence $T(n) = 3T(\lfloor n/4 \rfloor) + cn^2$ This sentence can be interpreted as follows assume that $T'(n) = 3T'(\lfloor n/4 \rfloor) + cn^2$ and $\exists$ a function $T(n) \in O(n^2)$ such that $T'(n)\in O(T(n))$
(4) $T(n)\leq d n^2$ for some constant $d > 0$ We are using induction to verify to the definition of Big Oh...
I feel that the author could simply have written the $T(n)$ is Upper Bounded by $n^2$ and Lower Bounded by $n^2$ or the author could have simply written $T(n) = O(n^2)$ and $T(n)=\Omega(n^2)$, did the author just use the above style of statements as pointed out in $(1),(2),(3)$ just for more clearer explanation or there are some extra meaning conveyed which I am missing out.

"$O(n^2)$ is indeed an upper bound for the recurrence" means $T(n) \in O(n^2)$.
That is, $\exists n_0 \ge 1, c>0, \forall n \ge n_0, T(n) \le c n^2$.

"$\Omega(n^2)$ must be a lower bound for the recurrence" means $T(n) \in \Omega(n^2)$. That is $\exists n_0 \ge 1, c>0, \forall n \ge n_0, T(n) \ge c n^2$.

This is exactly the same as 1).

Yes. In this step you use induction to show that $T(n) \le d n^2$ for some choice of a constant $d > 0$.


Decision Tree and rank? Consider all strictly decreasing functions from {1,2,3,4} to {1,2,3,4,5,6}, or in other words, all functions defined on {1,2,3,4} such that f(1)>f(2)>f(3)>f(4). Draw a decision tree so that the leaves are in lexicographical order when read from left to right. Then answer the following questions:

(a) What is the rank of 5431?

(b) What function has rank 0?

I have been looking all over the internet but I could not find a good resource for decision tree. I would be very appreciate it if anyone could show me how to approach this problem. Thanks

The decision tree implements the following algorithm for finding $f$:

What is $f(1)$?
What is $f(2)$?
What is $f(3)$?
What is $f(4)$?

There are six possible answers to the first question, but only three of them lead to a valid function. You split according to these answers in the correct order (you want the result to be in lexicographic order), and then continue to the second question. And so on. If you did everything correct, you'll find $\binom{6}{2} = 15$ different leaves, the last of which is $6543$.


What complexity class does is this set of grammars? NL-complete? The unrestricted grammars characterize the recursively enumerable languages. This is the same as saying that for every unrestricted grammar G there exists some Turing machine capable of recognizing L(G) and vice versa.

Context: Grammars are Turing-complete. Therefore complexity classes like NL have equivalences in grammars.

  One important NL-complete problem is ST-connectivity (or "Reachability") (Papadimitriou 1994 Thrm. 16.2), the problem of determining whether, given a directed graph G and two nodes s and t on that graph, there is a path from s to t. ST-connectivity can be seen to be in NL, because we start at the node s and nondeterministically walk to every other reachable node. ST-connectivity can be seen to be NL-hard by considering the computation state graph of any other NL algorithm, and considering that the other algorithm will accept if and only if there is a (nondetermistic) path from the starting state to an accepting state.

Given a directed graph, deciding if a->b is a directed path is NL-complete.

We will reduce the directed graph to a grammar rules with one symbol on each side:

For each directed edge in the graph, add a grammar rule. The directed edge a->b becomes the grammar rule a|b.

The NL-complete query becomes, "If I set a to the start symbol, can I derive symbol b using the grammar rules?"

Each grammar rule has one symbol on each side (i.e. a|b).

Therefore grammar rules with one symbol on each side is NL-complete.

Are grammars consisting only of rules with one symbol on each side NL-complete?

Related questions:

What complexity class does is this set of grammars? L-complete?

What complexity class does is this set of grammars? P-hard?

What complexity class does this correspond to?

Yes, you can build a reduction to show that the following problem is NL-complete:

  Given a grammar where every rule has the form $X \to Y$ or $X \to a$ where $X,Y$ range over nonterminals and $a$ ranges over terminals, and given a nonterminal $S$ and a terminal $a$, determine whether $S$ can derive $a$.

This problem is equivalent to testing whether $a$ is reachable from $S$ in the corresponding directed graph, which is exactly the ST-connectivity problem.

I didn't understand what you meant by a|b.


Tight bound on the number of intersections between a line and a triangulation I'm interested in the maximum number of intersections that a line and a triangulation on $n$ points could have. More specifically, given $n$, we are interested in the worst-case (maximum) number of intersections that any line could have with any triangulation on any point set.

There is an upper bound of $2n-5$ on the number of triangles for Delaunay triangulations, this implies an upper bound on the number of triangles for any triangulation, since any triangulation can be turned into a Delaunay triangulation using flips which don't change the number of triangles.

The first obvious upper bound is $3\cdot(2n-5)$ since there are at most $3$ edges per triangle. The next better obvious one is $2\cdot(2n-5)$ since a line can intersect at most $2$ edges of a triangle.

My current best lower bound (and I suspect that this is tight) on the number of intersections is $(n-2)\cdot2$ based on the following example (ignore the arrows, for every point added to the bottom we obtain 2 additional intersections by connecting it to the two top ones):

How to prove (or disprove) that the upper bound is $(n-2)\cdot2$?

Place $T$ triangles next to each other such that the line $l$ intersects them all. Observe how the number of intersections is $T+1$. Now substitute $T$ with the upper bound on the number of triangles for any triangulation that you mentioned, and we obtain $2n-5+1=2n-4$ as an upper bound on the number of intersections. The example provided in the question shows that the bound is tight.


Growth rate of roots vs logarithms I'm trying to prove that the tenth root of n grows slower than the logarithms but I have no clue.
Also, how can I find which of two functions grows faster? It it related to derivatives?
Thanks a lot.


Where should we place action symbols in a grammar? In the following grammar that is used for math expressions(and other grammars) how do I know where should I place action symbols(@add, @mul, @pushID)? Is there a algorithm for it?

E -> TE`
E'-> +T @add E'|ϵ
T -> FT`
T'-> xF @mul T'|ϵ
F -> (E)|@pushID id

For example why @add is between +T and E' and not after E'?
I searched for it's algorithm but didn't find anything useful.

Generally, there isn't an algorithm for placing the action symbols. You always need logic in there.

In your case, you want to take the action @add right after you read the second operand of +. The derivations are leftmost, which means that the leftmost rules are going to be expanded and evaluated before the right rules. That said if you have an input of id1 + id2 * id3, the @add action symbol will be useful after id2 because up to then you have the two operands that you want to add. Exactly the same with the @mul, which is useful after id3.

Another issue is the precedence rules of the operations. We want multiplications execute before additions. The above example should be executed as id1 + (id2 * id3). Your grammar takes that into account :) . Let's see the syntax tree and I'm sure that will explain everything to you:

Now you can see the actual sequence of the rules, the precedence of Multiplication and why the position of action symbols isn't something fixed.

In another grammar, somebody would first read the id and after that have an action symbol to take it into the symbol table (usually in programming languages like Fortran).

Don't hesitate to comment me if I did not cover you.


Can Chomsky Normal Form have more than one terminal? In formal language theory, a context-free grammar G is said to be in Chomsky normal form  if
$$ S → A B$$
$$ A → a $$
$$S → ε $$

My question is that if $B$ in the the form of
$$ B → abcd $$

where $abcd$ are terminal symbol, is this still in Chomsky Normal Form? ?

The above given CFG cannot be in Chomsky Normal Form since the production
B→abcd has multiple terminals on left hand side of the production.
In order to convert the given CFG to Chomsky Normal Form, will need to replace the terminals on lhs of production B→abcd as follows -
B->abcd
B->FG
F->AE
G->CD
E->b
C->c
D->d.


Inductive approach on Kleene star proof I'm having trouble proving the following: If $L_1$ and $L_2$ are languages then: $$(L_1^*L_2^*)^* = (L_1\cup L_2)^*$$
I could be on the wrong track here, but I figured an inductive approach is a good way?

My approach was this: If I use my notation $L^{(n)} = \lambda+L+L^2+...+L^n$ so that I have a kind of 'partial' Kleene star I start the induction:

1.) Base case $n=0$:

$(L_1^*L_2^*)^{(0)} = \lambda = (L_1\cup L_2)^{(0)}$ and so this works

2.) Assume true for some $n=k\geq0$ such that $(L_1^*L_2^*)^{(k)} = (L_1\cup L_2)^{(k)}$

3.) Now I want to see how $(L_1^*L_2^*)^{(k+1)}$ evaluates to:

$(L_1^*L_2^*)^{(k+1)} = (L_1\cup L_2)^{(k)}+(L_1^*L_2^*)^{k+1}$ where I used the inductive hypothesis. I know I should try to see if this RHS can give me the union with a (k+1) but I don't know how to manipulate this anymore. Am I on the wrong track or am I just not seeing the algebra properly?

It looks like you are on the wrong track.

While it is trivially true that $(L_1^*L_2^*)^{(0)} = \lambda = (L_1\cup L_2)^{(0)}$ where $\lambda$ is the language consisting of the empty word,    it is more often than not that $(L_1^*L_2^*)^{(1)}\neq (L_1\cup L_2)^{(1)}$. For example, if either $L_1$ or $L_2$ has a non-empty words, the left side $(L_1^*L_2^*)^{(1)}=(L_1^*L_2^*)^{(1)}\supseteq (L_1^*\cup L_2^*)$ has infinitely many word. However, if furthermore we let both $L_1$ and $L_2$ be finite languages, the right side $(L_1\cup L_2)^{(1)}$ is a finite language as well. A concrete counterexample can be given by $L_1=\{a\}$ and $L_2=\lambda$.

Here is an approach to move forward. Can you prove that for any language $L$, $(L^*)^*=L^*$? The use of that equality is that you can deduce that $(L_1\cup L_2)^{*}=\left((L_1\cup L_2)^{*}\right)^*$.

Here is another approach that I like. Intuitively, it is easy to "see" the equality $(L_1^*L_2^*)^* = (L_1\cup L_2)^*$. Note that A word in $L_1^*L_2^*$ is some number of words in $L_1$ followed by some number of words in $L_2$.

A word in $(L_1^*L_2^*)^*$ is some number of words in $L_1$ followed by some number of words in $L_2$, possibly followed by some number of words in $L_1$ followed by some number of words in $L_2$, ..., possibly followed by some number of words in $L_1$ followed by some number of words in $L_2$. Here "some number of" means zero or more.
A non-empty word in $(L_1\cup L_2)^*$ is a word in $L_1$ or $L_2$, possibly followed by a word in $L_1$ or $L_2$, ..., possibly followed by a word in $L_1$ or $L_2$.

Can you see how a word in the former language must be a word in the latter language? Can you see how a word in the latter language must be a word in the former language? If you can, try expressing those "how" in rigorous terms. That would be a proof.

Here is a related exercise.

  Let $L_1$ and $L_2$ be languages such that $L_1\subset L_2^*$ and $L_2\subset L_1^*$. Prove that $L_1^*=L_2^*$.


What does the term "Finite" stands for in Finite State Machines? Do we consider Pushdown Automata, Turing Machines in Finite State Machines?
If we don't, then what does the term "Finite" stands for in Finite state machines, as PDAs & TMs are also defined to have Finite Number of States?

The number of states is finite in finite state machines (aka regular laguages).

In contrast, in a push-down machine (PDA) the number of states is potentialy infinite (more correctly unbounded, leaving out stack size limitations), but the machine itself does not bound the number of states (that is why a stack is used) (aka context-free languages)

To put it in another way, a finite state machine can store all its needed state (in the general sense, including transition rules, current symbol etc..) only in fixed finite storage, unlike push-down machine (or other automaton) which cannot do that.

A PDA, for example, by its design and definition, does not determine a fixed size needed for all its state (it is unbounded, aka infinite in this respect)

And to clear up the confusion, PDAs (and other automata) may have finite number of transition rules but not finite number of (potential) states (also refered as configurations) (see above).

update

note that a PDA does not necesarily need infinite storage, for example any given PDA can at any given time only need finite storage and even during its whole operation its storage size does not exceed an upper limit. However this is not fixed before-hand by the machine itself (like for FSMs) and thus is formaly unbounded. In fact for PDAs the storage size is determined by the input size itself and is a linear function of the length of the input (which are part of automata refered as LBAs, linear-bounded-automata, in which one end is always fixed, the bottom of the stack)


Why are special instructions used to implement system calls? Why not use normal subroutine calling instructions? The transfer of control is often completed through some type of software interrupt instruction. These special instructions result in the CPU to save the current state of the machine and transfer control to a function in the operating system. They are like a cross between an ordinary subroutine call instruction and a hardware interrupt. My question is that Why are special instructions used to implement system calls? Why not use normal subroutine calling instructions?

System calls could be done, and have been done, with normal (normal enough) call instructions. However, the operation wouldn't be a normal call: the privilege level changes, and it is unsafe to allow calling arbitrary offsets (which might not be the entrypoint of a subroutine) with a lot of privileges. So there should be some mechanism that both limits the possible destinations and changes the privilege level. That mechanism is similar in function to how a dedicates system call instruction would work, but it could be triggered by a normal subroutine call instead.
Call gates on x86 are an example of that, a mechanism that allows system calls to some locations that have been set up in advance, by using relatively normal far calls. 32bit code does not normally use far calls though, so it's not really the same thing as a completely standard subroutine call. Far calls were more usual in the 16bit era, and the 80286 which introduced call gates was still a 16bit processor, but it seems that call gates did not see much use on the 80286. Similar mechanisms existed on some other old processors.


Minimum sub-tree of a graph that covers each color at least once I have a connected graph $G$ with $k$ different colors assigned to $n$ nodes where $k<n$. All edges have unit weight.

I want to figure out an algorithm to find a minimum sub-tree of $G$ that covers all $k$ colors (i.e., such that for each color, there is at least one node of this sub-tree with that color; and minimizing the number of nodes in this sub-tree).

I have tried a lot about solving this problem. For $k=2$, the problem will have just one edge, and for $k=3$, it becomes tricky. For $k = n$, the problem becomes as simple as reporting any spanning tree of the graph. For any other $k$, I am not able to think of a definite solution.

Is the problem NP-hard? If so, I will be very grateful if someone can explain or a hint as to which NP-hard problem can be reduced to this problem.

The OP has noticed that "for k=3, it becomes tricky". Indeed, the problem with variable $k$ with respect to $|V|$ is NP-complete and, hence, NP-hard.

Let us formalize the problem so as to able to prove it rigorously. This colored nodes covering problem, called for brevity CNC, is defined in decisional form as follows:

Instance:

a connected graph $G = (V, E)$;
a positive integer $k\le|V|$ and a map $C:V\to\{1, 2, \cdots, k\} $, called coloring map with $|C(V)|=k$;
a positive integer $m$

Question: Is there a subtree $T=(V', E')$ of $G$ that $|E'|\le m$ and $|C(V')|= k$?

Claim: Colored nodes covering problem (CNC) is NP-complete with respect to $|V|$.

Proof of the Claim.

It is easy to see that CNC is in NP. Let us reduce the Steiner tree problem, called for brevity ST, one of the NP-complete problems in Karp's original paper to CNC.

Let us recall ST can be defined in decisional form as follows:

Instance:

a connected graph $G = (V, E)$;
a subset of the nodes $R\subseteq V$ , called terminal nodes;
a positive integer $m$.

Question: is there a subtree of $G$ that includes all the nodes of $R$ and that contains at most $m$ edges?

Let us show a polynomial-time reduction from ST to CNC by building an instance of CNC starting from a generic instance of ST. Given a generic instance $s$ of ST, defined by a graph $g=(V,E)$, the set of terminals $R=\{v_1, v_2, \cdots, v_k\}\subseteq V$, and the
upper-bound $m$, define an instance $c$ of CNC as the following.

the same graph $G=(V,E)$.
the coloring $C: V\to\{1,\,2,\,\cdots,k,\,k+1\}$, $C(v_i)=i$ for $1\le i\le k$ and $C(v)=k+1$ otherwise.
the same upper bound $m$.

If the induced graph $G[R]$ is connected, then both $s$ and $c$ can be determined in polynomial time in $|V|$ (in fact, constant time), since the spanning tree of $G[R]$ is a tree with the minimal number, $k-1$ of edges that can include all vertices of $R$.

Otherwise let us assume $G[R]$ is not connected. Then any subtree of $G$ that contains all nodes of $R$ must contain at least one node that is not in $R$, which must be colored $k+1$. For any subtree $H$ of $G$, $H$ includes all the nodes of $R$ and contains at most $m$ edges if and only if $H$ includes nodes of every possible color under $C$ and contains at most $m$ edges. That is, $s$ has a yes answer if and only if $c$ has a yes answer.

It is easy to see that the transformation from $s$ to $c$ can be done in polynomial time (in fact, constant time). So we have reduced ST to CNC by a polynomial-time reduction.

Bonus exercise: is the colored nodes covering problem with fixed $k$ NP-hard? This is not an easy exercise. Here is a hint.

   No. My first step toward demonstrating the existence of a polynomial algorithm is noticing that there will be at most $|V|^k$ choices of the nodes in the subtree that will be mapped to all colors. ($|V|^k$  can be lowered to $(|V|/k + 1)^k$, which does not affect the logic though). It will take some time to reach a full proof.


Comparing the sizes of two search spaces by comparing their numbers of possibilities I am trying to solve an optimisation problem and come up with two Integer Linear Programming models. For each model, I am able to find a function that calculate the number of possibilities based on different variables, e.g. problem sizes.

I cannot directly conclude that one model has a smaller search space than the other. Instead, I develop an application that compares the actual numbers of possibilities between 2 models based on different values of the variables.

My application tries millions of different variables and shows that the number of possibilities of one model is less than the other 99% of the time. Is it enough to conclude that it is likely for one model to have the smaller search space, and to be solved faster than the other?

There is no easy way to predict which ILP model will be faster to solve.  Counting the number of variables is not a reliable predictor.  Estimating the size of the "search space" (the number of feasible solutions) is not a reliable predictor.  There is, in general, no fully reliable way to tell which model will be faster -- short of actually trying both.

Instead, my recommendation is that you try experiments.  Try solving both models, and see which takes longer to solve.  If your problem is parameterized in size, you can try solving for smaller sizes and see if a pattern emerges.


Which is the best data structure for searching under these conditions I have a system with some factors, say A, B, C, and D.
There can be different values of all these factors.
Let us consider few values to have a better understanding.

Let's say A has 4 different values, A1, A2, A3, A4.
B may have 3 or 5(anything, no order or logic here), similarly C and D may also have many different values.

What I have to do is keep count of is how many times a given combination occurs.

For e.g., one combination is A1, B1, C1, D1. Another may be A1, B1, C2, D1 and so on.

I need to read the count of occurrences of these combination once from a text file, and search for it when queried, and give the corresponding count. There is one more condition. There is a threshold for the count. For example, let's say the threshold is 10. If the count for (A1, B1, C1, D1) is less than 10, then I need to find the count of (A1, B1, C1, Dany), if this is less than 10, then just (A1, B1, Cany, Dany) or (A1, B1).

A trie might have been an option, but searching will take more time than hashmaps there.

Which would be the best data structure to do so in Java?

Of course, the simplest and most obvious solution is to use hashmaps. But the factors(A,B,C,D) may be ten or twenty, and may take thousands of values. Though the file where I am reading values from is updated only once a day, so updating the hashmap is not a problem, but I am not sure if storing this amount of data at once in a DS is possible or not. Also loading it into hashmaps is going to take a lot of space I guess, as we are going to store all the possible permutations in the hashmaps.

Thank you in advance for all your suggestions and efforts, much appreciated.

Edit: Seems like my proposed structure is not more efficient than a HashMap with additional entries like (A3,B1,Cany,Dany).

Typical values

There are F=20 factors (A, B, ..., T)
Each factor has V=1000 values (A1, A2, ..., A1000).
A lot of combinations (A524,...,T123) do no appear at all. The data structure should be sparse.

Suggestion: Use the following tree structure

Non-root Nodes represent a factor-value (for instance A1).
There can be multiple nodes per factor-value.
Per Node Xx we store

The number of (...Xx, Yany, Zany, ...) in the structure
A HashMap from Y1,...,YV to the corresponding nodes.

Example

We have the factor-values
A1–A3, B1–B2, and C1–C4.
In our text, the following combinations appeared:
2 times (A1, B1, C1),
1 time (A1, B1, C4),
4 times (A1, B2, C4)

Then our tree looks like the one in the picture below.

The counter per node is green, the hashmap is red.

Operations and costs

Insertion is O(F). Query (using "any" or not, and using threshold or not) is O(F).
In case the number of factors F is constant, operations are O(1).

Insertion

We found x new occurrences of combination (Aa, Bb, ..., Nn) and want to update the structure.

curNode := rootNode
for nextFactorValue in (A_a, B_b, ..., N_n)
    nextNode := curNode.hashMap[nextFactorValue]
    if (nextNode == null)
        nextNode := new Node(nextFactorValue)
        curNode.hashMap[nextFactorValue] := nextNode
    endif
    curNode.count := curNode.count + x   // update the "any" counts
    curNode := nextNode
endfor
curNode.count := curNode.count + x     // update the concrete count

Should you want to decrement the stored counts, you may want to remove nodes once their counter hits 0.

Query

Retrieve $count(a,b,...,i)$ = number of found (Aa, Bb, ..., Ii, jany, ..., Nany)

curNode := rootNode
for nextFactorValue in (A_a, B_b, ..., I_i)
    nextNode := curNode.hashMap[nextFactorValue]
    if (nextNode == null)
        return 0
    endif
    curNode := nextNode
endfor
return curNode.count

Query with threshold

Compute $
count_t(a,b,...,m,n) =
\begin{cases}
count_t(a,b,...,m),& \text{if } count(a,b,...,m,n)<t\\
count(a,b,...,m,n),& \text{otherwise}
\end{cases}
$

curNode := rootNode
for nextFactorValue in (A_a, B_b, ..., N_n)
    nextNode := curNode.hashMap[nextFactorValue]
    if (nextNode == null || nextNode.count < t)
        return curNode.count
    endif
    curNode := nextNode
endfor
return curNode.count


What is the complete version of the paper: "How to Generate and Exchange Secrets (extended abstract)" by Andrew Yao? I've found numerous places that claim that the paper "How to Generate and Exchange Secrets" by Andrew Yao introduces garbled circuits as a solution to the secure multiparty computation problem. However, I can only seem to locate the extended abstract which lacks proofs and does not seem to mention garbled circuits. It only appears to define useful properties for solving the problem and state several theorems without proof. A complete version of the paper is mentioned at the end of this extended abstract, but I cannot locate it. Is the complete version under a different name?

I have already found expositions that explain garbled circuits. At this point I am interested in finding the complete paper, if possible.

Garbled circuits were only implied by the extended abstract. They were only explicitly introduced in the talk given by Andrew Yao at the conference.

This is clear from a footnote on the Turing Award Page:

  The first of these two papers introduces secure function evaluation, and gives a > protocol for the famous Millionaires’ Problem. In talks related to these papers > Yao introduced a technique for secure computation known as garbled circuits.

which may be found here: http://amturing.acm.org/bib/yao_1611524.cfm#bib_6

Credit is due to Wandering Logic for giving this very helpful answer in the comments above.


Grid Based DP: How do we tweak the Travelling Salesman Problem to work with Grids The question is:

  There is a n x n grid (Maze) which has either 0, 1 or 2. 0 means a path
  exists, 1 means the cell is blocked and 2 means there exists gold in
  that cell.  Task is to start from 0, 0 and cover the grid such that
  all the gold is collected and then returned to a specific cell (x, y)
  in the grid. This task has to be done in the minimum number of steps.

  Example:
  Input: Maze = {0, 2, 0}, {0, 0, 1}, {1, 1, 1} and
  x = 1, y = 1
  (return to this cell)

  Output: 1 as there is only 1 gold (in 1,1) and we are to return also in
  (1,1) so 1 move is what we need.

Reading the question, I can speculate that this is perhaps a variant of the traveling salesman problem but I cannot think of how I should be applying it here. Also, since in Travelling Salesman we return back to the source node and here we do not, I am having second thoughts if this has TSP like implementation.
Any ideas?

Travelling Sales Man is NP-complete. This problem isn't, it has an easy polynomial time solution. Don't go there.


Use minimum number of swaps so each bin contains balls of the same color There are $n$ bins, the $i$th bin contain $a_i$ balls. The balls has $n$ colors, there are $a_i$ balls of color $i$. Let $m=\sum_{i=1}^n a_i$.

A swap is take a ball from one bin and swap with a ball from another bin. We want minimum number of swaps such that each bin only contain balls with the same color.

I know a easy special cases $a_i\leq 2$ for all $i$. (If $a_i=2$ for all $i$, then you can even do it by swapping each ball at most once.)

Edit: This is wrong because finding $c(D)$ is NP-hard.

If we know which color goes to which bin, the problem is easy.

Consider a multi-digraph $D=(V,A)$, $V=\{v_1,\ldots,v_n\}$. If we know color $i$ goes to bin $b(i)$, then there are $k$ parallel arcs $(j,b(i))$ in $A$ iff bin $j$ contains $k$ balls of color $i$. Each component of the graph is Eulerian.
The minimum number of swaps required is $m-c(D)$, where $c(D)$ is the number of arc disjoint cycles that covers $A$.
We can swap by "following" a Eulerian circuit. (a swap using an arc of a minimal cycle can change it to a smaller minimal cycle and a self loop). Once the entire graph is set of self loops, we have made all the necessary swaps.

How hard is this problem in general?

Maximal decomposition of an Eulerian directed graph into edge disjoint cycles is NP-Hard, at least according to this book: Algorithms and Applications:
Essays Dedicated to Esko Ukkonen on the Occasion of His 60th Birthday.

btw, here is an article which is relevant to the problem you seem to be trying to solve: Asymptotically optimal algorithm for the Dutch National flag algorithm.

For $n \le 6$, the paper gives a simple algorithm.


Can Dynamic programming be applied to solve problems if and only if the subproblem form a DAG? I assume Dynamic Programming can be used only when the corresponding subproblems form a Directed Acyclic Graph, otherwise you're stuck in a loop.

Is this reasoning correct or is there more to it?

Let $V_P(n)$ represent the value of the optimal solution to a problem $P$ with size $n$. According to Bellman equations, this value is computed from the value of the optimal solutions of its subproblems $P'$: $V_P(n) = \oplus \{v_{P'} + V_{P'}(n')\}$ where $\oplus$ is an  operator such as $\max$, $\min$, +, ... $v_{P'}$ is an operator which steps from $P$ to $P'$, and $P'$ are the subproblems of $P$ with size $n'$ which is always strictly less than $n$, the size of the original problem.

From here, it seems affordable to create a graph $G(V,E)$ where $V$ are the values of the optimal solutions of different problems, and there is an edge between two vertices $u$ and $v$ if and only if $v$ represents a problem $P'$ which is acknowledged as a subproblem of task $P$ represented by vertex $u$. For example, when using Dynamic Programming for computing the Fibonacci numbers, if $u$ represents $Fib(n)$, then there are two edges from it to other vertices representing $Fib(n-1)$ and $Fib(n-2)$.

If this is the graph you meant in your question then, clearly, the resulting graph is a Directed Acyclic Graph because:

Each vertex is directed in only one direction: from $u$ to $v$ as only one problem ($P'$) can be a subproblem of another, $P$.
It is impossible to form a loop as $n'<n$.

All this said, however, I do not think that this characterization is too useful as it also applies to other techniques such as Divide and Conquer and plain recursion. As you are asking whethere there is more about it or not, let me highlight that an important issue to consider when deciding whether to use Dynamic Programming or not, is if the problem $P$ shows suboptimal structure, see this definition in the second paragraph.

Hope this helps,


stages of compilation gcc is a collection of compilers, based on the file extension it compiles a source file. But compilers are only supposed to convert a preprocessed code into assembly code. And after that assembling and linking is done and an executable is generated.
But several definitions says that compilers are the ones who convert source code into executable code..
i am confused. what actually a compiler is? what is gcc?
Can anyone please give me a clear definition? And i have seen in man pages of gcc mentioning the term "compiler proper" what exactly is this?

I'm not sure there is a well accepted definition of compiler. To some extent this is an informal concept, so you can't expect a mathematical definition like that of a derivative.

Judging from GCC documentation, the compiler proper converts (preprocessed) source code into object code. Several object codes are then linked together to an executable by the linker, but that doesn't form part of the compiler proper. The C/C++ preprocessor also doesn't form part of the compiler proper.

The compiler proper is further composed of two parts: a front end and a back end. The front end converts source code into intermediate code, and is language specific. The back end converts intermediate code into machine code, and is machine specific. GCC comes with several front ends and back ends, and this is why it is called a compiler collection.


Expressing the language of squares as a concatenation of two languages Can the language $L = \{ vv : v \in \Sigma^* \}$ be expressed as the concatenation of two nontrivial languages? (A language is nontrivial if it differs from $\{\epsilon\}$.)

The answer depends on $|\Sigma|$. If $\Sigma$ contains a single letter then $L = (\Sigma\Sigma)^*(\Sigma\Sigma)^*$ can be written as a concatenation of two nontrivial languages.

Conversely, suppose that $|\Sigma| > 1$, say $a,b \in \Sigma$. Since $\epsilon \in L$, necessarily $\epsilon \in L_1,L_2$. This implies that all words in $L_1,L_2$ are squares, and in particular $a \notin L_1,L_2$. Since $aa \in L$, we must have $aa \in L_1$ or $aa \in L_2$. Without loss of generality, assume that $aa \in L_1$. We similarly get that $bb \in L_1$ or $bb \in L_2$. Since $aabb \notin L$, we must have $bb \in L_1$. Since $L_2 \neq \{\epsilon\}$, it must contain some non-empty word $w$. Hence both $aaw$ and $bbw$ are squares. However, this is impossible (why?), and we reach a contradiction.


What are the difference and relation between type checking and type reconstruction? In Types and Programming Languages by Pierce,

  ML-style let-polymorphism was ﬁrst described by Milner (1978). A num-
  ber of type reconstruction algorithms have been proposed, notably the clas-
  sic Algorithm W (Damas and Milner) of Damas and Milner (1982; also see
  Lee and Yi, 1998). The main diﬀerence between Algorithm W and the pre-
  sentation in this chapter is that the former is specialized for “pure type
  reconstruction”—assigning principal types to completely untyped lambda-
  terms—while we have mixed type checking and type reconstruction, permit-
  ting terms to include explicit type annotations that may, but need not, contain
  variables. This makes our technical presentation a bit more involved (espe-
  cially the proof of completeness, Theorem 22.3.7, where we must be careful
  to keep the programmer’s type variables separate from the ones introduced
  by the constraint generation rules), but it meshes better with the style of the
  other chapters.

What are the difference and relation between  type checking and type reconstruction?

Does type checking apply only to terms with explicit type annotations which don't contain type variables?

Does type reconstruction apply only to terms either without explicit type annotations, or with explicit type annotations containing type variables?

Thanks.

What are the difference and relation between type checking and type
  reconstruction?

Type reconstruction is a class of problem that involves coming up with a type for a term. For example given a term $\lambda x. x$ can you find the type for this term. Or in general answering the question:

Does a $T$ exist such that the judgement $\Gamma \vdash M : T$ is derivable, where
$M$ is the term and $\Gamma$ is the type environment.

Type checking on the other hand is a process where the question is:

Given a $T$ and an $M$ can $\Gamma \vdash M : T$ be a valid judgement.

  Does type checking apply only to terms with explicit type annotations which don't contain type variables?

No. You can have a type checking problem that asks whether $\lambda x. x$ has a type $\tau \to \tau$ where $\tau$ is a type variable.

  Does type reconstruction apply only to terms either without explicit type annotations, or with explicit type annotations containing type variables?

As type reconstruction problem is about computing the correct type for a term, if you have an explicit type annotation for a term, you would classify it as a type checking problem.