How to prove greedy algorithm is correct I have a greedy algorithm that I suspect might be correct, but I'm not sure.  How do I check whether it is correct?  What are the techniques to use for proving a greedy algorithm correct?  Are there common patterns or techniques?

I'm hoping this will become a reference question that can be used to point beginners to; hence its broader-than-usual scope. Please take care to give general, didactically presented answers that are illustrated by at least one example but nonetheless cover many situations. Thanks!

Ultimately, you'll need a mathematical proof of correctness.  I'll get to some proof techniques for that below, but first, before diving into that, let me save you some time: before you look for a proof, try random testing.
Random testing
As a first step, I recommend you use random testing to test your algorithm.  It's amazing how effective this is: in my experience, for greedy algorithms, random testing seems to be unreasonably effective.  Spend 5 minutes coding up your algorithm, and you might save yourself an hour or two trying to come up with a proof.
The basic idea is simple: implement your algorithm.  Also, implement a reference algorithm that you know to be correct (e.g., one that exhaustively tries all possibilities and takes the best).  It's fine if your reference algorithm is asymptotically inefficient, as you'll only run this on small problem instances.  Then, randomly generate one million small problem instances, run both algorithms on each, and check whether your candidate algorithm gives the correct answer in every case.
Empirically, if your candidate greedy algorithm is incorrect, typically you'll often discover this during random testing.  If it seems to be correct on all test cases, then you should move on to the next step: coming up with a mathematical proof of correctness.
Mathematical proofs of correctness
OK, so we need to prove our greedy algorithm is correct: that it outputs the optimal solution (or, if there are multiple optimal solutions that are equally good, that it outputs one of them).
The basic principle is an intuitive one:
Principle: If you never make a bad choice, you'll do OK.
Greedy algorithms usually involve a sequence of choices.  The basic proof strategy is that we're going to try to prove that the algorithm never makes a bad choice.  Greedy algorithms can't backtrack -- once they make a choice, they're committed and will never undo that choice -- so it's critical that they never make a bad choice.
What would count as a good choice?  If there's a single optimal solution, it's easy to see what is a good choice: any choice that's identical to the one made by the optimal solution.  In other words, we'll try to prove that, at any stage in the execution of the greedy algorithms, the sequence of choices made by the algorithm so far exactly matches some prefix of the optimal solution.  If there are multiple equally-good optimal solutions, a good choice is one that is consistent with at least one of the optima.  In other words, if the algorithm's sequence of choices so far matches a prefix of one of the optimal solutions, everything's fine so far (nothing has gone wrong yet).
To simplify life and eliminate distractions, let's focus on the case where there are no ties: there's a single, unique optimal solution.  All the machinery will carry over to the case where there can be multiple equally-good optima without any fundamental changes, but you have to be a bit more careful about the technical details.  Start by ignoring those details and focusing on the case where the optimal solution is unique; that'll help you focus on what is essential.
There's a very common proof pattern that we use.  We'll work hard to prove the following property of the algorithm:
Claim: Let $S$ be the solution output by the algorithm and $O$ be the optimum solution.  If $S$ is different from $O$, then we can tweak $O$ to get another solution $O^*$ that is different from $O$ and strictly better than $O$.
Notice why this is useful.  If the claim is true, it follows that the algorithm is correct.  This is basically a proof by contradiction.  Either $S$ is the same as $O$ or it is different.  If it is different, then we can find another solution $O^*$ that's strictly better than $O$ -- but that's a contradiction, as we defined $O$ to be the optimal solution and there can't be any solution that's better than that.  So we're forced to conclude that $S$ can't be different from $O$; $S$ must always equal $O$, i.e., the greedy algorithm always outputs the correct solution.  If we can prove the claim above, then we've proven our algorithm correct.
Fine.  So how do we prove the claim?  We think of a solution $S$ as a vector $(S_1,\dots,S_n)$ which corresponds to the sequence of $n$ choices made by the algorithm, and similarly, we think of the optimal solution $O$ as a vector $(O_1,\dots,O_n)$ corresponding to the sequence of choices that would lead to $O$.  If $S$ is different from $O$, there must exist some index $i$ where $S_i \ne O_i$; we'll focus on the smallest such $i$.  Then, we'll tweak $O$ by changing $O$ a little bit in the $i$th position to match $S_i$, i.e., we'll tweak the optimal solution $O$ by changing the $i$th choice to the one chosen by the greedy algorithm, and then we'll show that this leads to an even better solution.  In particular, we'll define $O^*$ to be something like
$$O^* = (O_1,O_2,\dots,O_{i-1},S_i,O_{i+1},O_{i+2},\dots,O_n),$$
except that often we'll have to modify the $O_{i+1},O_{i+2},\dots,O_n$ part slightly to maintain global consistency.  Part of the proof strategy involves some cleverness in defining $O^*$ appropriately.  Then, the meat of the proof will be in somehow using facts about the algorithm and the problem to show that $O^*$ is strictly better than $O$; that's where you'll need some problem-specific insights.  At some point, you'll need to dive into the details of your specific problem.  But this gives you a sense of the structure of a typical proof of correctness for a greedy algorithm.
A simple example: Subset with maximal sum
This might be easier to understand by working through a simple example in detail.  Let's consider the following problem:
Input: A set $U$ of integers, an integer $k$
Output: A set $X \subseteq U$ of size $k$ whose sum is as large as possible
There's a natural greedy algorithm for this problem:

Set $X := \emptyset$.
For $i := 1,2,\dots,k$:

Let $x_i$ be the largest number in $U$ that hasn't been picked yet (i.e., the $i$th largest number in $U$).  Add $x_i$ to $X$.

Random testing suggests this always gives the optimal solution, so let's formally prove that this algorithm is correct.  Note that the optimal solution is unique, so we won't have to worry about ties.  Let's prove the claim outlined above:
Claim: Let $S$ be the solution output by this algorithm on input $U,k$, and $O$ the optimal solution.  If $S \ne O$, then we can construct another solution $O^*$ whose sum is even larger than $O$.
Proof. Assume $S \ne O$, and let $i$ be the index of the first iteration where $x_i \notin O$. (Such an index $i$ must exist, since we've assumed $S \ne O$ and by the definition of the algorithm we have $S=\{x_1,\dots,x_k\}$.)  Since (by assumption) $i$ is minimal, we must have $x_1,\dots,x_{i-1} \in O$, and in particular, $O$ has the form $O=\{x_1,x_2,\dots,x_{i-1},x'_i,x'_{i+1},\dots,x'_n\}$, where the numbers $x_1,\dots,x_{i-1},x'_i,\dots,x'_n$ are listed in descending order.  Looking at how the algorithm chooses $x_1,\dots,x_i$, we see that we must have $x_i > x'_j$ for all $j\ge i$.  In particular, $x_i > x'_i$.  So, define $O^* = O \cup \{x_i\} \setminus \{x'_i\}$, i.e., we obtain $O^*$ by deleting the $i$th number in $O$ and adding $x_i$.  Now the sum of elements of $O^*$ is the sum of elements of $O$ plus $x_i-x'_i$, and $x_i-x'_i>0$, so $O^*$'s sum is strictly larger than $O$'s sum.  This proves the claim. $\blacksquare$
The intuition here is that if the greedy algorithm ever makes a choice that is inconsistent with $O$, then we can prove $O$ could be even better if it was modified to include the element chosen by the greedy algorithm at that stage.  Since $O$ is optimal, there can't possibly be any way to make it even better (that would be a contradiction), so the only remaining possibility is that our assumption was wrong: in other words, the greedy algorithm will never make a choice that is inconsistent with $O$.
This argument is often called an exchange argument or exchange lemma.  We found the first place where the optimal solution differs from the greedy solution and we imagined exchanging that element of $O$ for the corresponding greedy choice (exchanged $x'_i$ for $x_i$).  Some analysis showed that this exchange only can only improve the optimal solution -- but by definition, the optimal solution can't be improved.  So the only conclusion is that there must not be any place where the optimal solution differs from the greedy solution.  If you have a different problem, look for opportunities to apply this exchange principle in your specific situation.


Selection type generated by nested loops where initial value is current value of parent loop Consider the generator of the selections:

for (i1 = 0;  i1 < 10; i1++)
    for (i2 = i1; i2 < 10; i2++)
        for (i3 = i2; i3 < 10; i3++)
            for (i4 = i3; i4 < 10; i4++)
                printf("%d%d%d%d", i1, i2, i3, i4);

Result:

0000
0001
0002
...
0009
0011 <-- 0010 is skipped
0012
...
0019
0022 <-- 0020 and 0021 are skipped
0023
...
8999
9999

Generated selections have the following property: the order in the selection does not mater, i.e. 0011 0101 1001 1010 1100 are the same.

Basically it is 4-combination of the set { 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, ..., 9, 9, 9, 9}

What do you say to name this type of the selection?

I always get stuck when I say:

4-xxxxxxxx of the set {0, 1, 2, ..., 9}

where xxxxxxxx is the name of this selection.

The sequences your program generates are non-decreasing sequences.


N 3d integer points in box with maximum average distance given a 3d cube with a size of m x m x m, is there an efficient algorithm to find N integer points with the average Euclidean distance between each pair maximized? If not, is there any evolutionary approach I can take to this, so in each step the solution will be improved?

Thanks!

Note that maximizing the average distance between every pair of points is the same as maximizing the total distance between every pair of points.

Let's look at an m x m square first. When N = 4, it is clear that the optimal solution is placing a point in each corner.

For N = 5, the next picture explores two alternatives of placing the 5th point when the other 4 are in the corners. It appears it is optimal to place the 5th point also in a corner. Note that in the right picture, which is already sub-optimal, the total solution does not improve when moving any of the other four points (which are in the corners).

This solution does not work for all N, but it generalizes to cubes when N is a multiple of 8. Then all points are in the eight corners in an optimal solution.


Finding paths with minimum intersections Given a graph and a set of origin-destination $\langle o_i,d_i\rangle$ pairs. The goal is computing a set of paths such that every pair has a path and number of common vertices between paths is minimized.

If you have any relevant references to share I'd like to read them.

Let there be $n$ such pairs, and $k$ vertices. Then you can translate this problem into a minimum-cost integer multi-commodity flow problem.

The core trick is to encode the minimum intersections by turning each vertex of your original problem into a triplet of vertices in the minimum-cost flow problem, an input node, and output node, and $n$ edges connecting the input node to the output node. Each edge has capacity $1$, but the costs are respectively $1$, $k$, $k^2$, $k^3$, etc. This ensures that no vertex is visited twice unless there is no more efficient solution, and similarly thrice, etc.

Then connect the output nodes to the input nodes in the flow network as in the original graph. If the original graph was an undirected graph make sure to connect the input and outputs of the pair both ways for each edge.

Finally add a source node of commodity $i$ with demand $1$ and connect it to the input node of each $o_i$, and a sink node for that commodity connected to the output node of each $d_i$.

You can tweak the cost scaling for each shared vertex, that is up to you to decide. Is one triple shared vertex equally bad to two doubly shared vertices? Then use costs $0, 1, 1, \dots$.

Unfortunately minimum-cost integer multi-commodity flow is NP-complete in general, so this does not guarantee any polynomial runtime. But it's a well-studied problem so you might be able to find fast approximations and/or good libraries. Maybe someone else has a better solution, but this problem seems difficult to me to find globally optimal solutions.


Proving the loop invariant for a simple program in Hoare logic I was studying loop invariant and came across Tomas Petricek's example. Here's the equivalent(I believe) program after I revised it a bit for proof in Hoare logic:

j = 9;
i = 0;
while (i < 10)
{
    i = i + 1;
    j = j - 1;
}

The loop invariant given by Petricek is i + j == 9, which makes sense to me. And the pre-condition and post-condition, seems to me, is (|T|) and (|i = 10 and j = -1|), respectively. Here's my attempt:

(| T |)
(| eta[j/9][i/0] |) Implied
  i = 0;
(| eta[j/9] |) Assignment
  j = 9;
(| eta |) Assignment
  while (i < 10)
  {
    (| eta and i < 10|)
    (| eta[j/j-1][i/i+1] |) Implied
      i = i + 1;
    (| eta[j/j-1] |) Assignment
      j = j - 1;
    (| eta |) Assignment
  }
(| eta and not i < 10 |) While
(| i = 10 and j = -1 |) Implied

For the three Implied rule, with eta being i + j = 9, the first two are straightforward to me:

|- T => 0 + 9 = 9
|- i + j = 9 and i < 10 => i+1 + j-1 = 9

But I can't see how do I get from i + j = 9 and not i < 10 to i = 10 and j = -1. Am I setting the wrong post-condition? I could get j <= -1 trivially, but I don't think that's how it should work, right?

I thought that, without setting j to 9 and i to 0 in first two line, what this while loop does is to set i to 10 and j to j-(10-i). In that case, if we set the initially value of i to 0 and j to 9, j would be set to 9-(10-0) = -1, which is what I intended. I'm not sure what went wrong in my reasoning. May I have a hint? Thanks!

Your invariant, together with the negation of the loop condition, is not strong enough to imply your postcondition. Try adding an additional conjunct to the invariant which, together with $\neg\ i<10$, implies $i=10$ (the $j=-1$ part then follows from $i+j=9$).


Finding shortest path involving additional restrictions Question: If you were on an island(Vertex) which are connected to multiple other islands, and to get from island A to B it takes time T and does damage D to your boat. What is the fastest route from A to B such that the total damage is strictly less than a given value H.

I tried using Dijkstra's algorithm to build a sub-tree however the shortest route may not be acceptable since the total damage could be greater than H.
Any suggestions? Please keep the answer simple since I am a high school student.

We can create a new graph consisting of $N\cdot (H + 1)$ nodes and apply the Dijkstra algorithm on that graph. We will denote the new nodes as $(u, h):$ which means that the boat is at island $u$ and has been damaged by $h$ units, where $h$ is between $0$ and $H$. For each edge $(u, v, d, t)$ that goes from island $u$ to island $v$ while taking $d$ damage and $t$ time, we will create multiple edges in the new graph $((u, h), (v, h+d), t)$ (for $0 \leq h \leq H-d$). Your starting node will be $(A, 0)$ and to find the shortest path to $B$ you need to apply the Dijkstra algorithm and take the minimum time to $(B, h)$ for some $h$ between $0$ and $H$.


Dijkstra algorithm step in Introduction to Algorithms In the introduction to algorithms proof of Dijkstra, I don't understand why the statement "both y and u were in V-S when u was chosen". We add x before y, and so we relax d[y] with the the edge $$\omega(<x,y>) + \delta(s,x)$$, d[u] can't be smaller than delta[u], so shouldn't y be in S when we add x to S? thanks.

$u$ is supposed to be the first node to be insert in $V$ such that $d(s, u) \neq \delta(s, u)$. Before the insertion, $u$ is in $S-V$, it's clear. In addition, $y$ is supposed to be the first node in a choosen optimal path $s -> u$ to belong to $S - V$ when picking $u$ from $S - V$. So before we insert $u$ in $V$, $u$ and $y$ are both in $S - V$. Note that $y$ can be equal to $u$.


Proving that recursively enumerable languages are closed against taking prefixes Define $\mathrm{Prefix}  (L) = \{x\mid \exists y .xy \in L \}$. I'd love your help with proving that $\mathsf{RE}$ languages are closed under $\mathrm{Prefix}$.

I know that recursively enumerable languages are formal languages for which there exists a Turing machine  that will halt and accept when presented with any string in the language as input, but may either halt and reject or loop forever when presented with a string not in the language.

Any help for how should I approach to this kind of a proof?

Below is a hint for working with the Turing Machine (TM) formalism for RE languages. But finishing that approach from the hint depends on how you've been working with TMs.
You have a TM, say $T_L$ to accept L and you want to construct a new TM $T_L^'$ for $\text{Prefix}(L)$.  You can start $T_L^'$ on a string $x$ and then do something to finish up with the hypothetical $y$ that completes $xy\in L$. How you do that depends somewhat on the methods you have been using to work with TMs. But that's a hint so far.


Imagine a red-black tree. Is there always a sequence of insertions and deletions that creates it? Let's assume the following definition of a red-black tree:

It is a binary search tree.
Each node is colored either red or black. The root is black.
Two nodes connected by an edge cannot be red at the same time.
Here should be a good definition of a NIL leaf, like on wiki. The NIL leaf is colored black.
A path from the root to any NIL leaf contains the same number of black nodes.

Question

Suppose that you have implemented the insert and delete operations for the red-black tree. Now, if you are given a valid red-black tree, is there always a sequence of insert and delete operations that constructs it?

Motivation

This question is motivated by this question and by the discussion from this question.

Personally, I do believe that if you imagine a valid red-black tree consisting only of black nodes (which implies that you are imagining a perfectly balanced tree), there is a sequence of insert and delete operations that constructs it. However,

I do not know how to accurately prove that
I am also interested in the more general case

The insert and delete operations in a red-black tree include the balancing needed to maintain the red-black properties.

The problem with non(left- or right-) leaning red black trees is that there are multiple ways to restore the red-blackness after the basic delete or insert.
It is not the insert or the delete that transforms the tree, but the rebalancing and rotation that happens afterwards to preserve/restore the red blackness of the tree.

The basic description of the red-black tree does not prescribe which of the possible routes to take.
It may not be possible to figure out how to exactly reconstruct a given red black tree, because the rebalancing need not be deterministic.

This has been 'solved' with left-leaning red black trees.
There is only one way the balancing is done. So any given leaning red black tree can be reconstructed using inserts and deletes, because the rebalancing/rotations are done in a specific deterministic way.

This does not mean that left-leaning RB-trees are better or more efficient, what they gain on one hand by using deterministic balancing rules, they lose on the other by more complex balancing code.

As per @Anton's comment:
There is an algorithm which uses the operation insert and delete to construct a valid red-black tree consisting only of black nodes. It uses $(h+2)⋅2^{h}−1$ insertions/deletions to create a tree of height $h$. First, we can create a perfectly balanced red-black tree in breadth-first manner using $2^{h+1}−1$ insertions, then using $h∗2^{h-1}$ insertions and the same amount of deletions repaint it into a completely black tree. The trick here is to move up $h$ times the lowest red layer up the tree until it reaches the root.

I think a complete balancing algorithm like Day-Stout-Warren would be more efficient though.


Use of -1 to express edge cases in computer programs and data structures Often I will encounter the use of - or even use myself - the value -1 as an edge case in otherwise integer data structures. For instance, as the value for "irreplaceable" in a Replacement Cost field.

This is especially useful where null is either unrecognised; semantically overburdened; or converted into empty when migrating data across formats.

What is the formal computer science view on the use of negative integers for non-numeral meanings in data fields which are still used normally for positive integers?

Most PL folks would probably suggest that an option type is better suited.

For instance, in Haskell you'd use a Maybe T type: you use Nothing instead of -1, and Just x instead of x.  In SML, you'd use a T option type, and use None instead of -1 and SOME x instead of x.

The benefit of this is to better document the meaning of the sentinel value, and also to force the programmer to consider both cases everywhere it is relevant.  This helps avoid certain kinds of programming mistakes, where a -1 value is inadvertently used as if it were a real value.  It also ensures that the domain of the type T is separate from the sentinel value.

In a language without an option type, you can also use tagged unions or other methods of encoding this into the type system or class hierarchy.

That said, this is a pretty subjective question.  Opinions will vary.  You should not expect everyone in a field to share the same opinion about a subjective matter like this.


Chomsky Classification of Languages Given is a language $A = \{ a^n\:b\:c^{2n}\:b^m |\; n ∈ N^{+} ;\; m ∈ N \}$ ; where $N^{+}$ are the natural numbers excluding 0.

I have found a type-1 grammar to describe it:

$S \to A_1A_2$

$A_1 \to aA_1cc \;| \; abcc$

$A2 \to bA_2 \; |\; \epsilon$

However, this doesn't tell me much about the language's Chomsky type. How can I know if there exists a more restricted grammar and how can I find it?

The language $A = \{ a^n\:b\:c^{2n}\:b^m |\; n ∈ N^{+} ;\; m ∈ N \}$ is not obviously regular since finite automata do not have memory and hence it is not possible for them to determine the relation between $a$ and $c$.

Let us try to construct a Type-2 grammar for this language. Note that Type-2 grammars are of the form  $V\to(V \cup T)^{*}$ where $V$ represents non-terminals and $T$ represents terminals. So our example would lead to something like this:

$S \to a\:A_1\:cc\:A_2 $

$A_1 \to a\:A_1\:cc\;|\;b$

$A_2 \to b\:A_2\;|\;\epsilon$

Hence we see that this is a Type-2 grammar according to the Chomsky hierarchy.


Is this problem a variant of TSP problem? if not, what is it called? A jet which can fly no more than R kilometers without refilling, is at location 0 and needs to fly to point N+1. There are some petrol stations on the way, some of which are ready to use, others are under construction and will be available soon.
We get an array C of length N, where the value of C[i] describes the petrol station at location i in the following way:

If C[i] = -1 there is no station.
If C[i] = 0 there is a station at    location i
If C[i] = x there is a station at location i which will be
available at in x days.

Assume that flying from point a to point b takes no time. But if jet runs out of petrol on a point x of array, it should wait x days to refill and then continue its way. If x=-1, jet is stuck.
The task is to find the minimal number of days the jet can get from point 0 to N+1, refilling on the way when necessary.

Is it a TSP variant with an extra condition? I am new to these.

P.S.The task is the same as "compute the maximum value of minimum values for each range of length R".

UPD. I looked at all types of dynamic programming questions, it is not close to them. I was given this problem in the university, as one in the miscellaneous set of problems.

TSP assumes you go through a hamiltonian path.

This problem looks more like a simple a path search with some added restrictions and it's solvable with A*.


Is the powerset of a regular set also a regular set? If so, where can I find a proof of it? If not, is there a counterexample?

By powerset of a regular language I mean the set of all subsets of a regular language.

Thank you, Marcus.

No.  In computer science, a language is normally defined to be a subset of $\{0,1\}^*$.  If $L$ is a language, then the powerset $2^L$ is not a subset of $\{0,1\}^*$, so it is not a language.

(See e.g., https://en.wikipedia.org/wiki/Formal_language#Definition.)

If $L$ is finite, then the powerset $2^L$ is finite, so as Emil Jeřábek points out, there is a way you can encode it so its encoding is a regular language, since all finite languages are regular.

If $L$ is infinite, then as Yuval Filmus points out, the powerset $2^L$ is not countable, so there is no way to encode it as a language.  Thus, when $L$ is an infinite regular language, then the answer to your question is "no, not even if you're allowed to choose a reasonable encoding".


How to pick Hamming distance Wikipedia's article Cyclic redundancy check states that for the same n (bits) there are multiple CRCs possible with different polynomial. Then it lists this Best CRC Polynomials article that gives some variations with different polynomials. I am looking to implement a simple CRC-8. What should be my criteria for picking one polynomial over another?

I assume that it boils down to selecting the Hamming distance, but how is that related to my problem at hand? How do I pick the correct/best Hamming distance for best detecting possible errors in my case (and in what terms should I describe my case)? For example, will the choice depend on the media for storing/transmitting data or other physical factors or something else?

The author of the list that you mention has written a thorough report on the problem of selecting a CRC polynomial, which probably contains the answers to all your questions. See page C-19:

Important to select CRC polynomial based on:

Data Word length
Desired HD
Desired CRC size

Safety-critical applications commonly select HD=6 at max message length

For example, HD-6 detects between 1-6 error bits in the Data Word, so the bigger the HD the better (for the given Data Word length).


print the nodes of an immutable single-linked list in reverse order Assume you have a single-linked list of length n. The list is immutable. A node node has a method next and  node.next() returns a reference to the successor of node. node.print() prints the value of node node or does some other stuff, such etails don't matter.

Is it possible to print the nodes of the list in reverse order in linear time using only a constant amount of space?

Details:

For the last element of a list next points to a special node named NIL that represents the end of a list. For NIL next() and print() are not defined.

The following simple pseudocode program prints the nodes in the order of the list. FIRST_NODE points to the first node of the list. Variable names that store references to nodes are prefixed by 'node_'.

node_current=FIRST_NODE
while node_current!=NIL
    node_current.print()
node_nurrent=node_current.next()

This algorithm calls of the medthod next n-times and there is one variable that can hold a reference to a node.

To print the k-th node of the list one can traverse the list from the start node to the k-th node in k steps. So to print the list in reverse order the following algorithm works

node_first=FIRST_NODE
node_last=NIL
while node_last!=node_first
    node_current=node_first
    while node_current!=node_last:
        node_previous=node_current
        node_current=node_current.next()
    node_previous.print()
    node_last=node_previous

It needs about $\frac{n^2}{2}$ calls of method next and needs 4 variables that can hold a reference to a node: node_first (the first node of the list), node_last (the last node that was printed), node_current (the node that is currently investigated) , node_previous (the predecessor of node_current)

It can be shown that there are algorithms that need about $O(n^{\frac{1}{k}})$ space and $O(n)$ time for an arbitrary choosen k from {2,3,4,...} to print a single-linked list in reversed order. It is also possible to do this in $O(\log n)$ space  and $O(n \log n)$ time.
 This can be found here

Can one do this better?

My question: Is there an algorithm with $O(1)$ space complexity and $O(n)$ time complexity  that prints such a list in reverse order?

Please note that the definition of the problem excludes an algorithm that prints a list in reversed order in linear time with $O(1)$ space for node references while changing the references of the list:

The list is traversed form start to end and the references are reversed during this traversal: the reference from a node to its successor is overwritten by a reverence to its predecessot. If on arrives at the and of the list is straersed form the former end (which is now the start) to the former start (which is now the end) and the nodes are printed.

No, there is no such algorithm. This is proved in Theorem 2 of "Almost Optimal Hash Sequence Traversal" by Coppersmith and Jakobsson.


In algorithm analysis what does it mean for bounds to be "tight" For example we could say alg(x) runs big omega(n) but this bound is not "tight".

What is meant by "tight"? Is it that the bound isn't at its maximum?

So maybe a tighter bound could be big omega (1)??

Generally speaking, a bound is tight if there is no "better" bound.

Take, for instance, $f(n) = \sin(n)$. Then, $-1.5 \leq f(n) \leq 2n$ are valid bounds on $f$ but they are not tight -- there are better bounds, e.g. $-1.2 \leq f(n) \leq 1.5n$.

Now, $-1 \leq f(n) \leq 1$ are tight bounds -- there are no tighter ones.

You will note that the range of $n$ is relevant here. I implicitly let $n \in \mathbb{N}$ (or $\mathbb{R}$ if you want) here; if we consider $n \in \{ \pi i \mid i \in \mathbb{N} \}$ there are better bounds.

Now, using Landau symbols the terminology is used similarly: $f \in \Omega(n)$ is a tight bound if there is no "better" $\Omega$-bound, i.e. one with a faster-growing parameter function. If we also know that $f \in O(n)$, then both bounds are tight and we have $f \in \Theta(n)$. It is, however, very possible that you have, say, $f \in \Omega(n)$ and $f \in O(n^2)$ and both bounds are tight.

Here, and in particular in the context of algorithm analysis, the range of (the implicit) parameters is relevant as well: are you talking about all inputs? Worst-case inputs? The average case? For instance, $\Omega(n)$ is a tight (lower) bound on the asymptotic running time of (improved) Bubblesort if you consider the best case, but not for average or worst case.

Note that "tight" can be relative to your goals. If you want to prove asymptotics of the form $f \sim g$, you wouldn't call a $\Theta$-bound "tight".


Absorbing Markov Chains: An efficient algorithmic approach Following this procedure I have successfully written a program to calculate the probability of ending in a given absorbing state given the initial state.  The procedure is as follows:

Given the transition matrix (P), row and column swap until the identity matrix is in the bottom right corner.

$$
P = \begin{bmatrix}
Q & R \\
0 & I
\end{bmatrix}
$$

Calculate the matrix N, and multiply by R to give the final probability matrix (B).

$$N = (I-Q)^{-1}$$
$$B = N*R$$

Where the values in B represent the probability of moving from an initial non-absorbing state (rows) to a final absorbing state.

My question is if there is a more efficient method for solving this problem if I know what my initial state is.  It seems wasteful to calculate the entire B matrix, given that I will only ever use one row in it.

I am writing a program to do this, so the matrix inversion step is particularly inefficient.  Can I avoid this altogether?

There are several possible techniques.

Let $P^t$ denote the matrix $P$ raised to the $t$th power.  Then $(P^t)_{i,j}$ (the $i,j$-th entry of that matrix) represents the probability that if you start in state $i$, you'll end in state $j$ after $t$ steps.  If $t$ is sufficiently large, this is a good approximation to the limiting value as $t \to \infty$.

So, one possible technique is to choose a sufficiently large value of $t$, compute $P^t$, and then evaluate $(P^t)_{i,j}$.  Notice that you can compute $P^t$ using $O(\lg t)$ matrix multiplications using the square-and-multiply algorithm, so it is possible to choose a very large value of $t$.  Unfortunately, if $P$ is a $n\times n$ matrix, this will be slow: it will take $O(n^3 \log t)$ time, which is significant if $n$ is very large.

Another option is to use the power iteration method as used in the PageRank algorithm.  Basically, you set the vector $x^0$ to be a vector that $1$ in its $i$th element and all zeros elsewhere.  Then, you iteratively compute

$$x^{k+1} = P \cdot x^k.$$

After $t$ steps, you have computed $x^t$; now you read off the $j$th element in that, i.e., $(x^t)_j$, and that is the probability after $t$ steps.  If $P$ is dense, each iteration takes $O(n^2)$ time, for a total of $O(n^2 t)$ time.  That might be better than the previous method, but still not too encouraging if $n$ is very large.  However, in many real applications, $P$ is sparse, and thus each iteration can be computed in $O(n)$ time; in this case, the method takes $O(nt)$ time, which can be quite efficient.

How large does $t$ need to be?  In practice, often $t$ doesn't need to be very large.  You can analyze how large $t$ needs to be, as a function of the gap between the first largest and second largest eigenvalue of $P$.  In particular, if $\lambda_1$ denotes its first largest eigenvalue and $\lambda_2$ its second largest eigenvalue, for a Markov process we have $\lambda_1 = 1$ and $\lambda_2 \le 1$.  Now effectively we need $t$ to be large enough that $\lambda_2^t$ is much smaller than $1$ (negligible compared to $1$).  If $\lambda_2$ is not too close to $1$, then $t$ won't need to be very large.  In particular, $t = O(\log(1/(1-\lambda_2)))$ iterations suffices.

As a result, the power iteration method can often be very effective and very efficient.


Can PRNGs be used to magically compress stuff? This idea occurred to me as a kid learning to program and
on first encountering PRNG's. I still don't know how realistic
it is, but now there's stack exchange.

Here's a 14 year-old's scheme for an amazing compression algorithm:

Take a PRNG and seed it with seed s to get a long sequence
of pseudo-random bytes. To transmit that sequence to another party,
you need  only communicate a description of the PRNG, the appropriate seed
and the length of the message. For a long enough sequence, that
description would be much shorter then the sequence itself.

Now suppose I could invert the process. Given enough time and
computational resources, I could do a brute-force search and find
a seed (and PRNG, or in other words: a program) that produces my
desired sequence (Let's say an amusing photo of cats being mischievous).

PRNGs repeat after a large enough number of bits have been generated,
but compared to "typical" cycles my message is quite short so this
dosn't seem like much of a problem.

Voila, an effective (if rube-Goldbergian) way to compress data.

So, assuming:

The sequence I wish to compress is finite and known in advance.
I'm not short on cash or time (Just as long as a finite amount
of both is required)

I'd like to know:

Is there a fundamental flaw in the reasoning behind the scheme?
What's the standard way to analyse these sorts of thought experiments?

Summary

It's often the case that good answers make clear not only the answer,
but what it is that I was really asking. Thanks for everyone's patience
and detailed answers.

Here's my nth attempt at a summary of the answers:

The PRNG/seed angle doesn't contribute anything, it's no more
than a program that produces the desired sequence as output.
The pigeonhole principle: There are many more messages of
length > k than there are (message generating) programs of
length <= k. So some sequences simply cannot be the output of a
program shorter than the message.
It's worth mentioning that the interpreter of the program
(message) is necessarily fixed in advance. And it's design
determines the (small) subset of messages which can be generated
when a message of length k is received.

At this point the original PRNG idea is already dead, but there's
at least one last question to settle:

Q: Could I get lucky and find that my long (but finite) message just
happens to be the output of a program of length < k bits?

Strictly speaking, it's not a matter of chance since the
meaning of every possible message (program) must be known
in advance. Either it is the meaning of some message
of < k bits or it isn't.

If I choose a random message of >= k bits randomly (why would I?),
I would in any case have a vanishing probability of being able to send it
using less than k bits, and an almost certainty of not being able
to send it at all using less than k bits.

OTOH, if I choose a specific message of >= k bits from those which
are the output of a program of less than k bits (assuming there is
such a message), then in effect I'm taking advantage of bits already
transmitted to the receiver (the design of the interpreter), which
counts as part of the message transferred.

Finally:

Q: What's all this entropy/kolmogorov complexity business?

Ultimately, both tell us the same thing as the (simpler) pigeonhole
principle tells us about how much we can compress: perhaps
not at all, perhaps some, but certainly not as much as we fancy
(unless we cheat).

You've got a brilliant new compression scheme, eh? Alrighty, then...

♫ Let's all play, the entropy game ♫

Just to be simple, I will assume you want to compress messages of exactly $n$ bits, for some fixed $n$. However, you want to be able to use it for longer messages, so you need some way of differentiating your first message from the second (it cannot be ambiguous what you have compressed).

So, your scheme is to determine some family of PRNG/seeds such that if you want to compress, say, $01000111001$, then you just write some number $k$, which identifies some precomputed (and shared) seed/PRNG combo that generates those bits after $n$ queries. Alright. How many different bit-strings of length $n$ are there? $2^n$ (you have n choices between two items; $0$ and $1$). That means you will have to compute $2^n$ of these combos. No problem. However, you need to write out $k$ in binary for me to read it. How big can $k$ get? Well, it can be as big as $2^n$. How many bits do I need to write out $2^n$? $\log{2^n} = n$.

Oops! Your compression scheme needs messages as long as what you're compressing!

"Haha!", you say, "but that's in the worst case! One of my messages will be mapped to $0$, which needs only $1$ bit to represent! Victory!"

Yes, but your messages have to be unambiguous! How can I tell apart $1$ followed by $0$ from $10$? Since some of your keys are length $n$, all of them must be, or else I can't tell where you've started and stopped.

"Haha!", you say, "but I can just put the length of the string in binary first! That only needs to count to $n$, which can be represented by $\log{n}$ bits! So my $0$ now comes prefixed with only $\log{n}$ bits, I still win!"

Yes, but now those really big numbers are prefixed with $\log{n}$ bits. Your compression scheme has made some of your messages even longer! And half of all of your numbers start with $1$, so half of your messages are that much longer!

You then proceed to throw out more ideas like a terminating character, gzipping the number, and compressing the length itself, but all of those run into cases where the resultant message is just longer. In fact, for every bit you save on some message, another message will get longer in response. In general, you're just going to be shifting around the "cost" of your messages. Making some shorter will just make others longer. You really can't fit $2^n$ different messages in less space than writing out $2^n$ binary strings of length $n$.

"Haha!", you say, "but I can choose some messages as 'stupid' and make them illegal! Then I don't need to count all the way to $2^n$, because I don't support that many messages!"

You're right, but you haven't really won. You've just shrunk the set of messages you support. If you only supported $a=0000000011010$ and $b=111111110101000$ as the messages you send, then you can definitely just have the code $a\rightarrow 0$, $b\rightarrow 1$, which matches exactly what I've said. Here, $n=1$. The actual length of the messages isn't important, it's how many there are.

"Haha!", you say, "but I can simply determine that those stupid messages are rare! I'll make the rare ones big, and the common ones small! Then I win on average!"

Yep! Congratulations, you've just discovered entropy! If you have $n$ messages, where the $i$th message has probability $p_i$ of being sent, then you can get your expected message length down to the entropy $H = \sum_{i=1}^np_i\log(1/p_i)$ of this set of messages. That's a kind of weird expression, but all you really need to know is that's it's biggest when all messages are equally likely, and smaller when some are more common than others. In the extreme, if you know basically every message is going to be $a=000111010101$. Then you can use this super efficient code: $a\rightarrow0$, $x\rightarrow1x$ otherwise. Then your expected message length is basically $1$, which is awesome, and that's going to be really close to the entropy $H$. However, $H$ is a lower bound, and you really can't beat it, no matter how hard you try.

Anything that claims to beat entropy is probably not giving enough information to unambiguously retrieve the compressed message, or is just wrong. Entropy is such a powerful concept that we can lower-bound (and sometimes even upper-bound) the running time of some algorithms with it, because if they run really fast (or really slow), then they must be doing something that violates entropy.


Show that TQBF $\notin$ SPACE$((\log{n})^4)$? How do I show that TQBF $\notin$ SPACE$((\log{n})^4)$?  I know that TQBF is PSPACE complete, but is this the right approach?

Hint: TQBF is PSPACE-complete, so it "requires" polynomial space. If there were an algorithm to solve TQBF using space $O(\log^4 n)$, you could use it to solve all problems in PSPACE using surprisingly small space. So surprising, in fact, that the space hierarchy theorem says it can't be.


Modifying the genetic algorithm I have a multi-objective optimization problem (NP-complete). To solve it, I've decided to use the genetic algorithm.

I have 3 "areas" of optimization, say parameters a, b and c, so cost function for my problem is C(F) = a + b + c -> min.

I want to somewhat modify the genetic algorithm. In the classic workflow, the initial population is created randomly. For my problem, I want to create a "smart" initial population. Since I have 3 parameters to be optimized, I wanna create 1/3 of the initial population optimized for parameter a, 1/3 optimized for parameter b, and 1/3 optimized for parameter c. Then, in the while loop just "mix" these good individuals. Is this a good way to go? Is this still considered the genetic algorithm? Is this a good modification?

P.S. I'm doing research for my master's project so I need to provide some novelty in my solution. Would this modification be considered fine for that?

Thanks in advance.

Yes, this is absolutely still considered a genetic algorithm. In fact, it is quite common to experiment with various strategies of obtaining an initial population. As you say, it is reasonable to start with a completely random population unless you have a reason to try something else.

Whether this is a good way to go is anybody's guess, really. It depends heavily on your problem and problem instances. Give it a try and see how it compares to a random initial population. Further, whether this is a modification that is considered fine, trust your advisor more than random people on the internet.


NP-complete problem with a polynomial number of yes-instances? I have the impression that for every NP-complete problem, for infinitely many input sizes $n$, the number of yes-instances over all possible inputs of size $n$, is (at least) exponential in $n$.

Is this true? Can it be proven (probably only under the assumption that $P\neq NP$)? Or can we, maybe artificially, find a problem where for all (large enough) $n$, the number of yes-instances is at most polynomial in $n$?

My reasoning is basically that given a yes-instance for 3-SAT, we can identify the literal in each clause that makes it true and replace another variable in the clause with yet another variable, without changing that it's satisfiable. Since we could do that with each clause, it leads to an exponential number of yes-instances. The same holds for many other problems such as hamiltonian path: we can freely change edges that are not on the path. I then vagely reason that since reducibility is involved where in some way solutions must be kept, it must hold for all NP-complete problems.

It seems also to hold for the maybe NP-intermediate problem of graph isomorphism (where we can freely apply the same changes to both graphs if we know the mapping). I wonder if it also holds for integer factorization.

A language with only polynomially many yes-instances is called sparse.  Mahaney's theorem states that if any NP-complete language is sparse, then P = NP.  Since most people expect that P $\ne$ NP, it seems unlikely that there exists a NP-complete language with only polynomially many yes-instances.

It's a separate question whether the number of yes-instances is exponential.  (One could imagine that the number of yes-instances might be more than polynomial but less exponential.)  The Berman-Hartmanis conjecture is relevant here; it implies that all NP-complete problems have exponentially many yes-instances.  The conjecture remains an open problem.


AVL tree balance property states for the two subtrees of a node, their height can differ at most one. Why can't it be zero? I was thinking that if they were equal, say they are required to be zero this would be enforce the balance property more effectively. Can anyone explain why 1 is a satisfactory rather than just them being 0?

What matters is that the height  of the tree is limited by $O(\log n)$. As long as you maintain that property your searches will remain efficient.

Forcing the height difference to be zero we get the above property. However we also get the property if we allow the difference to be 1. The crux is that the latter requires a lot less rebalancing to achieve. The average height of a node will very slightly increase due to our more relaxed tree structure but this downside is greatly overshadowed by the reduction in rebalancing operations.


What's a general rule for this little lambda calculus identity? I've been fiddling around with a project that does some normalization of lambda calculus(-like) expressions and I stumbled upon that

(λ λ ... λ n (n-1) ... 2 1)

(De Brujin notation) is just the identity. I've generalized this a little to realize I can do stuff like

(λ λ λ λ 4 2 1) = (λ λ 2)

So basically if you can identify some character in your expression which is just the variable index n, and all variable indices to the left of that point are greater than n, and to the right is just descending down the variable indices one at a time to index 1 then you can eliminate all the indices to the right of that character (including that character) and then eliminate the _λ_s from the head of the expression and decrease the remaining indices appropriately.

This feels too haphazard to be the simplest form of this identity though. There must be a cleaner way to express this, and possibly a more general rule.


Program transformations for numeric stability There's tons of research on program transformations for optimization.  Is there any research on transformations that improve numeric stability?  Examples of such transformations might include:

Transform $\log(\exp(a)+\exp(b))$ into $\max(a,b)+\log(\exp(a-\max(a,b))+\exp(b-\max(a,b)))$
Convert multiplication of an inverse matrix times a vector into the solution to a linear system solver.
Automatically perform multiplications of small numbers in the log domain.

All the tricks I'm aware of for better numeric stability like this are pretty standard and something that every "good" numeric programmer always does.  Since the tricks are so standard and always applied, it makes sense that the compiler might be able to do them for us.

There actually is some research on improving the numerical stability of floating point expressions, the Herbie project. Herbie is a tool to automatically improve the accuracy of floating point expressions. It's not quite comprehensive, but it will find a lot of accuracy improving transformations automatically.

Cheers,

Alex Sanchez-Stern


Heavy hitters problem linear scan and auxiliary space I'm looking at Lecture #2 from this Stanford course http://web.stanford.edu/class/cs168/index.html, let me introduce the HH problem:

We have an array of $n$ elements and we want to know which elements appear at least $\frac{n}{k}$ times, for a given $k$. You can think of $n$ as being pretty large and $k$ small.

Proposition There's no algorithm that solves the Heavy Hitters problem in one pass while using a sublinear amount of space.

An intuition for why this holds is given in the notes:

for $k=\frac{n}{2}$ we're looking at elements that appear at least twice in the array.
suppose the array is of the form $x_1, x_2, \ldots , x_{n-1}, y$ , say $S=\{x_i \mid 1\leq i\leq n\}$, then basically the HH problem reduces to a membership problem, is $y\in S$?
we can solve this problem by saving $S$ as a hash table, and the idea is that we can't solve all the memebership problems (for say $n/2$ elements) using sublinear space.

They suggest using the PHP but I don't see how that applies in this context, any idea?

I can see why the statement is true but I'm looking for a formal proof of it.

Here is the idea, taking as an example the case $k = n/2$ which you mention. Also, let's assume that a word is $\log n$ bits, and that each element consists of $C$ words. In total there are $n^C$ possible elements, forming the universe $U$.

Suppose that an algorithm uses $m$ words of space. For each subset $S$ of $U$ of size $n-1$, let $T(S)$ denote the contents of memory after the algorithm has read the first the elements of $S$ in order. We claim that $T(S_1) \neq T(S_2)$ if $S_1 \neq S_2$. Indeed, suppose without loss of generality that $S_1$ isn't a subset of $S_2$, and let $x \in S_1 \setminus S_2$. If the last element that the algorithm reads is $x$ then it should output $x$ if it had read the elements in $S_1$, and it should output nothing if it has read the elements in $S_2$.

Since there are $\binom{|U|}{n-1} = \binom{n^C}{n-1}$ different sets $S$ and $n^m$ different memory settings, we conclude that $\binom{n^C}{n-1} \leq n^m$. Since $\binom{a}{b} \geq (a/b)^b$, we conclude that $(n^{C-1})^n \lesssim n^m$, and so $(C-1)n \leq m$ or $m = \Omega(n)$ (for $C > 1$).


Can an exponential algorithm for an NPC problem be transformed into an algorithm for other NP problems in polynomial time? After looking at other questions and my textbook, I seem to get some confusion.

I do get that when there is a polynomial algorithm of NPC, there is a polynomial algorithm for a NP problem.

But the statement describing reduction seems obscure to me at least in the beginning of my studies in computational complexity.

So, can we transform an exponential algorithm for NPC (which we have) into an exponential algorithm for another non-NPC NP problem in polynomial time?

If you have an algorithm running in time $f(n)$ that solves an $\mathsf{NP\text{-}complete}$ problem, you can use it to solve any $\mathsf{NP}$ problem and the running time will be $g(n)=f(n^k) + p(n)$ ($k$ is a constant which depends on the reduction between the problems, $p(n)$ is a polynomial essentially giving the running time of the reduction function).

I am not sure what you mean exactly by exponential time, but the result above is general and will work for any $f$, e.g.:

If $f$ is a polynomial, then $g(n)$ is also a polynomial,
If $f(n) = 2^{\epsilon n}$, then $g(n) = 2^{\epsilon n^k}+p(n)$,
If $f(n)= 2^{n^\epsilon}$ then $g(n) = 2^{n^{k\epsilon}}+p(n)$.

I am not sure what you exactly mean by transforming an algorithm, but

what is essentially needed is that we are given a reduction algorithm from $Q'$ to $Q$. If we have that, it is easy to compose it with any algorithm $A$ for $Q$ to obtain an algorithm for $Q'$.
If this is given as an input to the transformation, it can transform an algorithm $A$ for $Q$ to an algorithm for $Q'$ very easily (in polynomial time): it will output the code resulting from composing the code for the reduction from $Q'$ to $Q$ with the code for the algorithm $A$. In fact, this can be done in linear time.

If the reduction is not given as an input then the algorithm has to find it. It can be done under some conditions but essentially we have to provide the transformation with enough information so that the transformation can find the needed reduction algorithm. If we don't provide enough information to find the reduction then this cannot be done. At least not uniformly in $A$. Here is an argument:

The transformation has to return an algorithm that is essentially the composition of a reduction function from $Q'$ to $Q$ with $A$. However the transformation cannot check what a given algorithm $A$ for $Q$ is really doing (because of Rice's theorem). So we can give an identity algorithm as $A$ and the transformation will not notice this and will return an algorithm which is essentially the composition of a reduction from $Q'$ to $Q$ with the identity function. But that is equal to the reduction function from $Q'$ to $Q$. So the output will be a reduction algorithm from $Q'$ to $Q$.


"Print 'em all game" for Turing machines Suppose that we have a tape restricted to $n$ cells on binaryalphabet $\Sigma = \{0,1\}$ and initially filled with zeroes.

We want to build a Turing machine $M_n$ (or better a Linear Bounded Automata) that "prints" all the $2^n$ numbers on the tape, i.e. for all $x \in [0..2^{n-1}]$ there is a time $t_x$ during the computation in which the tape content is exactly $x$. Note that we can build an "optimized" Turing machine for every $n$.

At every step the head must move left or right.

  What is the minimum number of steps $T(n)$ required?

We can easily see that $2^n-1 \leq T(n) \leq n 2^n$.

But how much can we "optimize" it?

For example for $n=3$ there is an optimal $2^n-1$ sequence:

t0:  >0 0 0
t1:   1>0 0
t2:   1 1>0
t3:   1>1 1
t4:  >1 0 1
t5:   0>0 1
t6:   0 1>1
t7:   0>1 0

If you use a Gray code then you can get $O(2^n)$. The Gray code described in the Wikipedia article modifies at time $t$ the position $p_t$ which is the index of the right-most 1 bit in $t$. The resulting position sequence is
$$ 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, \ldots $$
You are interested in $\sum_t |p_{t+1}-p_t|$:
$$ 1,1,2,2,1,1,3,3,1,1,2,2,1,1,4,4,\ldots. $$
We can see that half the time this is $1$, a quarter of the time it's $2$, one eighth of the time it's $3$, and so on. The total average value is roughly
$$ \sum_{n = 1}^\infty \frac{n}{2^n} = 2. $$
So the head moves roughly $2^{n+1}$ times compared to your lower bound of roughly $2^n$.


Greedy algorithms tutorial Could anyone point me to simple tutorial on greedy algorithm  for Minimum Spanning tree - Kruskal's and Prims' Method

I am looking for a tutorial which

does not include all the mathematical notation
explains algorithm along with the analysis of the running time.

Here is a simple definition for greedy algorithm.

There are many greedy algorithms for different problems and in order to understand them you must also know well the subject of the problem. This question on stackoverflow gives some examples of greedy algorithms usage.

EDIT :  After you made your question more clear I will try to sketch the algorithms by using "minimum mathematical notation".
Both the Kruskal's and Prim's algorithms build MST in connected graph.

Let we have graph G with vertices V and edges E.

Prim's algorithm

Select some vertex r from V and add it to the tree. r will be the root of the tree
Until all vertexes V are in the tree :

Find the shortest edge from E that has one end in the already constructed tree and the other in some of the vertices of the graph that are not in the tree and add the edge and the new vertex to the tree
When the condition in step 2. is not correct you will have the MST constructed

Kruskal's algorithm

Construct forest of trees where each tree is a single vertex from V
Until all trees are connected into single one :

Find the shortest edge from E that connects two unconnected trees and connect them with it. That step constructs from two trees a new one.
When the condition in step 2. is not correct all the trees will be connected into single one that is the MST

Note: After each iteration we have a tree/trees because there is no way to add a edge that forms a cycle

Note: The tree consists of vertexes and edges (it is kind of graph). When adding a vertex to the tree we add it to the set of vertices and when adding edge - to the set of edges.

Running Time

This part really needs mathematical notation and depends on specifics in the implementation of the algorithms, so I will leave it only with some answers and links to Wikipedia,where there are some general explanations.

Prim's Algorithm = O(E.log E) = O(E. log V)

Kruskal's Algorithm = O(E.log E) = O(E. log V)

Please read the explanations and ask only the things that are unclear to you(maybe in different question if they are related to the asymptotic notations)

"Greedy Part"

The greedy part in both of the algorithms is choosing to add the shortest edge to the tree. The shortest edge is the logically optimal choice when constructing Minimal Spanning Trees.


Is it possible for a network to have a negative cycle that is not found by the Bellman–Ford algorithm? I'm struggling to think of such a network. According to the definition I'm working with:

Given a network $(V, A, w)$.
For all arcs $(u, v) \in A$ :
$\quad$ If $d[u, |V| - 1] + w(u, v) < d[v, |V| - 1]$:
$\quad\quad$ Print “Negative cycle!” and stop immediately

To me this implies the only way a negative cycle isn't detected is if all arcs from any $u$ to my $v$ must have a positive weight. How, then, could there be a negative cycle?

No, it is not possible. If there is a negative cycle in a network, it will be found by the step 3 of Bellman–Ford algorithm as described by Wikipedia.

Here is the reason given by Wikipedia.

  Simply put, the algorithm initializes the distance to the source to 0 and all other nodes to infinity. Then for all edges, if the distance to the destination can be shortened by taking the edge, the distance is updated to the new lower value. At each iteration $i$ that the edges are scanned, the algorithm finds all shortest paths of at most length $i$ edges (and possibly some paths longer than $i$ edges). Since the longest possible path without a cycle can be $|V|-1$ edges, the edges must be scanned $|V|-1$ times to ensure the shortest path has been found for all nodes. A final scan of all the edges is performed and if any distance is updated, then a path of length $|V|$ edges has been found which can only occur if at least one negative cycle exists in the graph.

For more detailed understanding, please read the proof of the correctness of Bellman-Ford as well as finding negative cycles by Bellman-Ford.

Here is one easy related exercise.

Exercise. Let $e_0, e_1, e_2, \cdots, e_{m-1}, e_m=e_0$ be a negative cycle whose number of vertices, $m$ is the smallest among all negative cycles. Show that it is a chordless cycle.


Simple Bayesian classification with Laplace smoothing question I'm having a hard time getting my head around smoothing, so I've got a very simple question about Laplace/Add-one smoothing based on a toy problem I've been working with.

The problem is a simple Bayesian classifier for periods ending sentences vs. periods not ending sentences, based on the word immediately before the period. I'm collecting the following counts in training: number of periods, number of sentence-ending periods (for the prior), words and counts for words before sentence-ending periods, and words and counts for words before not-sentence-ending periods.

With add-one smoothing, I understand that

$$P(w|\text{ending}) = \frac{\text{count}(w,\text{ending}) + 1}{\text{count}(w) + N},$$

where $P(w|\text{ending})$ is the conditional probability for word $w$ appearing before a sentence-ending period, $\text{count}(w,\text{ending})$ is the number of times $w$ appeared in the training text before a sentence-ending period, $\text{count}(w)$ is the number of times $w$ appeared in the training text (or should that be the number of times it appeared in the context of any period?), and $N$ is the "vocabulary size".

The question is, what is $N$?

Is it the number of different words in the training text? Is it the number of different words that appeared in the context of any period? Or just in the context of a sentence-ending period?

The correct formula is

$$P(w|\text{ending}) = \frac{\text{count}(w,\text{ending}) + 1}{\text{count}(w) + N},$$

where $N$ is the number of possible values of $w$.  Here $w$ ranges over the set of all words that you'll ever want to estimate $P(w|\text{ending})$ for: this includes all the words in the training text, as well as any other words you might want to compute a probability for.  For instance, if you limit yourself to only computing probabilities for English words in a particular dictionary, $N$ might be the number of words in that dictionary.

The intuition/idea behind add-one smoothing is: in addition to every occurrence of a word in the training set, we imagine that we see one artificial "occurrence" of each possible word too -- i.e., we augment the training set by adding these artificial occurrences (exactly one per possible word), and then compute probabilities using the ordinary unsmoothed formula on this augmented training set.  That's why we get $+1$ in the numerator and $+N$ in the denominator; $N$ is the number of artificial occurrences we've added, i.e., the number of possible words.


Complex search algorithm - Points on a sphere - Best approach I have a very complex search problem which I can't wrap my head around:

  While reading please remember I'm not asking for a specific solution! Only a general approach how such a problem can be solved and what kinds of algorithms to use (more below)

I have a sphere with around 120 000 weighted and named points mapped on its surface.

Now I take a section out of the sphere with somewhat around 10 of the highest weights (not guaranteed the 10 hightest weights!)

The Problem: I want to find the spot where the section was taken out, so that i could assign each point the "name" it would have had on the sphere

Characteristics of the points on the sphere.:

120 000
The coordinates are exact
The points are weighted

Characteristics of the points in the sector:

The points are also weighted. The proportions are roughly the same as on the sphere, unfortunately I don't know a single inital weight. So my only chance is to compare the proportions.
Not every point which is on the sphere is also visible in the section (sometimes only 5-10%). However the weigths matter:

The hightest weighted points do always appear.
The first non-visible points have guaranteed less weight than most of the visible points.

The section could be rotated
All points are a bit offset (not by much), but they aren't exactly on the spot where they were on the sphere
Other errors could be possible too (like counting 2 points only once)

Additional info which might make the problem simpler:

The sector is only around 1°x1° to 5°x5°. So maybe i could use a flat map instead of a sphere. (Just like Google Maps if you zoom out enougth
The first non-visible points have guaranteed less weight than most of the visible points.

What I'm asking for:

  What is the general approach to solve this problem? Are there any algorithms you might now on which I can orientate myself?

  Anything between pure brute-force and AI is welcome!

Example image of a sector region which is detected by my algorithm:
(A larger red rectangle = higher weight)

If you think this is a good question please consider upvoting to draw attention.

Let me start by suggesting a brute-force method, then suggest some ways to speed it up:

Pick a pair of (high-weight) points $P_0,P_1$ in the sector.  For each pair of points $Q_0,Q_1$ on the sphere, guess that maybe $P_0=Q_0$ and $P_1=Q_1$: align the sector (rotate & translate it) so that $P_0$ is on top of $Q_0$ and $P_1$ is on top of $Q_1$.  There is a unique way to do this.  Then check your candidate placement of the sector, by mapping the sector onto the globe and looking at all the other points in the sector to see how well they match the points on the sphere.  If you enumerate all pairs of points $Q_0,Q_1$ on the sphere, you're guaranteed to find the correct placement of the sector for at least one of them.  So, this algorithm works, at the cost of being slow: it takes $O(n^2)$ time, where $n$ is the number of points on the sphere.

You can dramatically speed this up in several ways.

First, you can filter by the distance $d(P_0,P_1)$ between the two points.  Instead of enumerating all points $Q_0,Q_1$, only enumerate pairs $Q_0,Q_1$ such that $d(Q_0,Q_1) \approx d(P_0,P_1)$.  How do you do that?  You enumerate all possibilities for $Q_0$, and for each such $Q_0$, enumerate all points $Q_1$ that are at distance approximately $d(P_0,P_1)$ from $Q_0$.  The latter can be done using a data structure for nearest neighbor search.  If you choose two points $P_0,P_1$ that are close to each other, probably there will be only a small number of points $Q_1$ at that distance from $Q_0$.  So, heuristically, the running time might become much closer to $O(n)$.

Second, you might be able to filter using the weights.  You could pick a pair of high-weight points $P_0,P_1$ in the sector, and only consider points $Q_0,Q_1$ whose weights are above some threshold.  You'd have to experiment how to choose that threshold.  Or, you could enumerate the points $Q_0$ in sorted order of the weight, highest weight first.

You can increase robustness to small errors in the location of the points in the sector by repeating the above multiple times for multiple different choices of $P_0,P_1$.


The Clique vs. Independent Set Problem Suppose you have an undirected graph $G = (V, E)$, known to both Alice and Bob, Alice gets an independent set of $G$. Bob gets a Clique $B ⊆ V$.

Is there any algorithm in $O(\log^2 n)$ bits that finds whether
$ A ∩ B = Ø $?

This is a well known communication complexity problem called CIS problem that was described by Yannakakis.

Lecture notes; the claim is Theorem 3
Link to Nisan & Kushilevitz's textbook

I'm not sure why and how does this work exactly. and which part of the $n/2$ vertices are reduced by both players.

P.S. I came to a conclusion that an independent and a clique can intersect in at most one vertex.

The two players construct a sequence $V_0 \supset V_1 \supset \cdots \supset V_m$ of sets of vertices such that:

$V_0$ consists of all vertices in the graph.
$|V_{i+1}| \leq (|V_i|+1)/2$.
$V_i \supseteq C \cap I$.

The players stop once $|V_m| \leq 1$. At this point they can answer the question using $O(1)$ communication.

At round $i$, the players know $V_{i-1}$, and wish to construct $V_i$. They act as follows:

If $C \cap V_{i-1}$ contains a vertex $v$ with fewer than $|V_{i-1}|/2$ neighbors in $V_{i-1}$, then Alice sends Bob one such vertex $v$, and both players set $V_i$ to be this set of neighbors, together with $v$ (this is valid since $C \cap I \subseteq C \subseteq V_i$). Otherwise, she sends $\bot$.
If Alice sent $\bot$ and $I \cap V_{i-1}$ contains a vertex $v$ with fewer than $|V_{i-1}|/2$ non-neighbors in $V_{i-1}$, then Bob sends Alice one such vertex $v$, and both players set $V_i$ to be this set of non-neighbors, together with $v$ (this is valid since $C \cap I \subseteq I \subseteq V_i$). Otherwise, he sends Alice $\bot$.
If both players sent $\bot$, then $C \cap I = \emptyset$. Indeed, if $v \in C \cap I$, then $v$ has at least $|V_{i-1}|/2$ neighbors and at least $|V_{i-1}|/2$ non-neighbors inside $|V_{i-1}|$, whereas the number of potential neighbors and non-neighbors is just $|V_{i-1}|-1$. Therefore the players can abort and conclude that $C \cap I = \emptyset$.

Each round takes $O(\log n)$ bits of communication, and there are $O(\log n)$ rounds, for a total of $O(\log^2 n)$ bits of communication.


Eliminating cycles from a grammar I have the following grammar:

S -> Xb | Y

Y -> X | a

X -> S | c

Here the lowercase letters are terminals.

I have an algorithm to find the cycle in this grammar. It is S->Y->X->S and in fact there is a smaller cycle buried in there, namely S->X->S.

I've tried to devise an algorithm to remove these cycles, without too much thought, but I've come up with nothing.

Any help would be appreciated.

An algorithm to specifically remove cycles can be adapted from the more general algorithm to reduce a grammar to its Chomsky normal form. Specifically, it is the elimination of unit productions, usually abbreviated as UNIT, which is responsible for breaking cycles. Really what follows is a explanation (in fact two, the second being more refined) of how UNIT works, as far as I understand it. The best thing to do is probably to work through the example I gave in the question.

For the S production I have:

S -> Xb | Y

   = Xb | X | a   [replace Y with X | a]

   = Xb | a | c   [replace X with c]

Note that X is replaced with just c and not its full right hand side S | c, presumably to avoid introducing the cyclic unit production S->S. Note also that the X is effectively moved to the end during the process of eliminating it (I am unable to work out why this should be the case and would love it if someone could tell me).

For the Y production I have:

Y -> X | a

   = a | S | c   [replace X with S | c]

   = a | c | Xb  [replace S with Xb]

Note again that the unit productions are effectively moved to the end during the process of elimination. And again note that S is replaced with Xb and not Xb | Y, presumably for the aforementioned reason of not introducing the cyclic unit production Y->Y.

For the X production I have:

X -> S | c

   = c | Xb   [replace S with Xb]

Note here that S is replaced with Xb rather than Xb | Y. The reason for this is that the production S->Y has already been used up, so to speak, and therefore should not be introduced again.

This last step, although it now seems to make sense, confused me at first. In what follows the same algorithm is refined further in order to highlight these kinds of steps. It is also closer to a real implementation. I'll work on a different grammar, this one:

S -> Xb | Y

Y -> X | a

X -> Z | d

Z -> Y | c

I start by dividing up the grammar into non-unit and unit productions:

*******
S -> Xb
Y -> a
X -> d
Z -> c
*******

S -> Y
Y -> X
X -> Z
Z -> Y

I keep the list of non-unit productions fixed, and work on the stack of unit productions. As I create new unit productions, I add them to the top of the stack, effectively replacing the old ones. However, I keep the old ones, they remain above the dashed line (ideally I wish I could cross them out), so I have a record of unit productions that I must not re-introduce. At the same time, as I create new non-unit productions, I put them to one side in a new list and do not pollute the original list. I'll write the stack and list next to each other.

So, I eliminate S->Y, adding a new non-unit production S->a and a new unit production S->X, which I get from applying the unit production Y->X that can be found lower down in the stack to the right hand side of S->Y:

1

  S -> Y    S -> a   [from Y->a in the list of non-unit productions]
  ------
  S -> X             [from applying Y->X from further down the stack]
  Y -> X
  X -> Z
  Z -> Y

I'll continue with the process only adding qualifications occasionally when new points crop up...

2

  S -> Y    S -> a
  S -> X    S -> d
  ------
  S -> Z
  Y -> X
  X -> Z
  Z -> Y

3

  S -> Y    S -> a
  S -> X    S -> d
  S -> Z    S -> c   [no more to do, S->Y has been eliminated already]
  ------
  Y -> X
  X -> Z
  Z -> Y

4

  S -> Y    S -> a
  S -> X    S -> d
  S -> Z    S -> c
  Y -> X    Y -> d
  ------
  Y -> Z
  X -> Z
  Z -> Y

5

  S -> Y    S -> a
  S -> X    S -> d
  S -> Z    S -> c
  Y -> X    Y -> d
  Y -> Z    Y -> c
  ------
  X -> Z
  Z -> Y

6

  S -> Y    S -> a
  S -> X    S -> d
  S -> Z    S -> c
  Y -> X    Y -> d
  Y -> Z    Y -> c
  X -> Z    X -> c
  ------
  X -> Y
  Z -> Y

7

  S -> Y    S -> a
  S -> X    S -> d
  S -> Z    S -> c
  Y -> X    Y -> d
  Y -> Z    Y -> c
  X -> Z    X -> c
  X -> Y    X -> a
  ------
  Z -> Y

7

  S -> Y    S -> a
  S -> X    S -> d
  S -> Z    S -> c
  Y -> X    Y -> d
  Y -> Z    Y -> c
  X -> Z    X -> c
  X -> Y    X -> a
  Z -> Y    Z -> a
  ------

I hope these steps are clear. Finally, collating we get:

S -> Xb | a | d | c

Y -> a | d | c

X -> d | c | a

Z -> c | a

The astute may notice that the cycle is in fact X->Z->Y->X, S plays no part. It is possible to detect cycles, or more correctly strongly connected components, as a preliminary step, and then apply UNIT only to these components, which would no doubt make for a more efficient algorithm.


What is the average-case complexity of trial division? The trial division algorithm for checking if a number $N$ is prime works by trying to divide $N$ by all integers in the range 2, 3, ..., $\lfloor \sqrt{n} \rfloor$. If any of them cleanly divide $N$, then we say that $N$ is composite; otherwise we say that $N$ is prime.

In the worst case, this requires $O(\sqrt{N})$ divisions to be made. However, this only happens in the case where $N$ is prime. If $N$ is a composite number, then we might stop much earlier than this.

I'm curious about the average-case complexity of this algorithm, assuming that the input is a natural number chosen uniformly at random. Since there's no way to choose an natural number uniformly at random, I'm curious about the asymptotic growth rate of

$$\mathbb{E}[T(X_n)]$$

where $X_n$ is a random variable that takes on a value from $\{2, 3, 4, 5, ..., n\}$ uniformly at random and $T(N)$ denotes the number of divisions made by the trial division algorithm when run on the number $N$. Since the number of divisions made is equal to the smallest prime factor of the number in question, and since the number is chosen uniformly at random, this expression is equivalent to

$$\frac{\sum_{i=2}^n \xi(i)}{n-1}$$

where $\xi(i)$ denotes the smallest prime factor of $i$.

I have some thoughts about what this might look like, but I'm not sure how to formalize them. First, there's the observation that about half the integers in $\{2, 3, 4, 5, ..., n\}$ are divisible by two, about a third are divisible by three, etc., so for many numbers very few divisions are required. Second, there's the prime number theorem that gives a good asymptotic estimate for the density of the prime numbers. However, I'm having trouble seeing how to combine all this information together.

Does anyone know how to determine the asymptotic growth rate of this expression?

By the prime number theorem, about a $1/\log(n)$ fraction of numbers in the range $[n/2,n]$ are prime.  We know that the algorithm will take $\Theta(\sqrt{n})$ time for each of them (since for all $x \in [n/2,n]$, we have $x = \Theta(\sqrt{n})$).  Therefore,

$$\mathbb{E}[T(X_n)] = \Omega\left({\sqrt{n} \over \log n}\right).$$

This is enough to establish that trial division is inefficient.  Also, since we have the upper bound

$$\mathbb{E}[T(X_n)] = O(\sqrt{n}),$$

we get a pair of upper and lower bounds that are almost matching.

It turns out one can show that the correct running time is

$$\mathbb{E}[T(X_n)] = \Theta\left({\sqrt{n} \over \log n}\right).$$

I'll show the argument below.  It's a bit detailed, so brace yourself.

There's an error in your post.  You claim that

$$\mathbb{E}[T(X_n)] = {\sum_{i=2}^n \xi(i) \over n-1},$$

but that is not correct.  The running time on input $i$ is not $\xi(i)$; the running time is $\min(\xi(i),\sqrt{i})$, since trial division aborts early as soon as it has tried all divisors $\le \sqrt{i}$.  Therefore, your expression for the running time is not correct.

Yuval Filmus found that your expression was analyzed on Math.SE, and apparently

$${\sum_{i=2}^n \xi(i) \over n-1} \sim {n \over 2 \log n},$$

but unfortunately this doesn't really tell us much about the running time of your trial division, due to the error I mentioned.

If we correct the error, we find

$$\mathbb{E}[T(X_n)] = {\sum_{t<n} \xi(t) \over n-1} + \Theta\left(\sqrt{n} \over \log n\right),$$

where $t$ ranges over all composites less than $n$.  Now we can upper-bound the first term as follows:

$$\begin{align*}
\sum_{t < n} \xi(t)
&\le \sum_{p < \sqrt{n}} \left\lfloor {n \over p} \right\rfloor \times p\\
&\le \sum_{p < \sqrt{n}} n\\
&= n \times \#\{p : p < \sqrt{n}, p \text{ prime}\}\\
&= n \times O\left({\sqrt{n} \over \log n}\right).
\end{align*}$$

where the sum is over all primes $p$ that are at most $\sqrt{n}$, and using the prime number theorem in the last step to note that there are $O(\sqrt{n}/\log(\sqrt{n})) = O(\sqrt{n}/\log(n))$ many such primes $p$.

It follows that

$$\mathbb{E}[T(X_n)] = O\left(\sqrt{n} \over \log n\right),$$

so the simple bound given at the start of the answer was tight.


Threads and Operating System In a computer, the processor executes different threads and changes between them, the operating system is a program at the end that it´s being executed by the processor, there exists the posibility that the processor is not executing the code of the operating system, if there is, shouldn´t this cause problems with the programs being executed on the computer?

For full detail, you should consult a textbook on operating systems.

The brief answer is that the operating system doesn't need to be executing all the time. It suffices for it to periodically regain control of the machine, and this happens through so-called "interrupts".  Interrupts can happen for a number of reasons:

a process that wants the operating system to do something for it (e.g., to perform I/O) can raise an interrupt (known as a "system call");
a hardware device that needs attention (e.g., because some I/O that was requested has now completed) alerts the OS by raising an interrupt;
the system clock will raise interrupts at some frequency (typically multiple times per second).


Balancing subproblems in resilience testing You’re doing some stress-testing on various models of glass jars to determine the height from which they can be dropped and still not break. The setup for this experiment, on a particular type of jar, is as follows. You have a ladder with $n$ rungs, and you want to find the highest rung from which you can drop a copy of the jar and not have it break. We call this the highest safe rung.
It might be natural to try binary search: drop a jar from the middle rung, see if it breaks, and then recursively try from rung $n/4$ or $3n/4$ depending on the outcome. But this has the drawback that you could break a lot of jars in finding the answer.

If your primary goal were to conserve jars, on the other hand, you could try the following strategy. Start by dropping a jar from the first rung, then the second rung, and so forth, climbing one higher each time until the jar breaks. In this way, you only need a single jar—at the moment it breaks, you have the correct answer—but you may have to drop it $n$ times (rather than $\log n$ as in the binary search solution).

So here is the trade-off: it seems you can perform fewer drops if you’re willing to break more jars. To understand better how this trade- off works at a quantitative level, let’s consider how to run this experiment given a fixed “budget” of $k \ge 1$ jars. In other words, you have to determine the correct answer—the highest safe rung—and can use at most $k$ jars in doing so.

Suppose you are given a budget of $k = 2$ jars. Describe a strategy for finding the highest safe rung that requires you to drop a jar at most $f (n)$ times, for some function $f (n)$ that grows slower than linearly. (In other words, it should be the case that $\lim_{n\to\infty} f (n)/n = 0$.)

Anyone any insights how to solve this problem?

I know that the answer is $h = \sqrt n$. I know  that it solves the problem. But I want to know how you got that answer, there must be a general way to do it?

Drop the first jar at the $\sqrt{n}$th rung, $2\sqrt{n}$th rung, and so on until it breaks at the $m\sqrt{n}$th rung. (This takes at most $\sqrt{n}$ steps). Then drop the second jar at every rung between the $(m-1)\sqrt{n}$th rung and the $m\sqrt{n}$th rung until you find the precise breakpoint.


How to determine maximum stack size of LL(1) parser? I am generating an LL(1) parser generator for LL(1) grammars that have a maximum stack size when executed in the table-driven parser. Specifically, I'm parsing HTTP headers using a parser generated by the LL(1) parser generator.

In case somebody asks, yes, it's possible to parse plaintext HTTP using LL(1) parser, if the parser works together with the lexer, so that the parser automatically turns on and off tokens in the lexer. So, only those tokens that are valid in the context are matched in the deterministic finite automaton (DFA).

The particular grammar I'm using for my tests is this (yes, I know it's possible to fold the first header line incorrectly using the grammar, I'll fix this later):

headerField -> foldstart httpfield
headerField -> httptoken colon optspace httpfield
httpVersion -> httpname slash digit period digit
requestLine -> httptoken onespace uri onespace httpVersion crlf
requestHdrs -> (epsilon)
requestHdrs -> headerField crlf requestHdrs
requestWithHeaders -> requestLine requestHdrs crlf

The start nonterminal is requestWithHeaders. The terminals are:

crlf, onespace, httpname, slash, digit, colon, optspace
httptoken, httpfield, period, uri, foldstart

...so every name that is lowercase only is terminal, and if there are uppercase characters in the middle, it's nonterminal.

Now, if I start using the stack [(endOfFile), requestWithHeaders], the maximum stack size is ever going to be 9 according to my tests. So, this grammar appears to have a maximum stack size.

The question is: how to prove the maximum stack size? I'm looking for an algorithm that terminates and gives me the answer 9 for this grammar. The algorithm need not terminate for a grammar that doesn't have a maximum stack size, so infinite recursion and infinite loops are permitted if the maximum stack size doesn't exist. (I can always limit the amount of CPU time given to the algorithm.)

I already have the code to calculate first-sets and follow-sets, and the code to generate the parser table, and the code to execute the parser using the parser table, so I'm not looking for advice for standard LL(1) parser implementation. I have already tested my parser with valid and invalid HTTP examples, and everything seems to work just fine.

The reason I'd like to determine this maximum stack size is that I want to avoid dynamic memory allocation in the parser. There is no need to allocate memory dynamically for cases where there is an upper bound for the stack size.

OK.  So you have a pushdown automaton, and out of all reachable stack configurations, you want to know the stack depth (length) of the longest such configuration.

I have two answers: a simple, practical answer that might suffice for your specific situation but doesn't scale, and a general answer that will apply more broadly.

Simple answer

Enumerate all possible stack configurations. This should be easy.  Just think of this as a giant graph, with one vertex per reachable stack configuration, and an edge from each such stack configuration to every other configuration that is reachable in a single step.  Now use any graph exploration algorithm, such as DFS, to explore the graph.  Out of all the configurations you visit, keep track of which one had the largest stack depth.

You have 5 nonterminals.  If the maximum stack depth is $9$, there will be at most $5^9$ reachable stack configurations, i.e., about 2 million of them.  It's easy to explore all such configurations and store them all in a simple data structure.

Of course this would not scale to larger cases, as the complexity is exponential.

General solution

The set of reachable stack configurations of a pushdown automaton is regular.  Therefore, you can build a DFA that concisely represents all such reachable stack configurations.  This DFA is not too large (linear in the size of the PDA, I think) and can be built efficiently (in quadratic or cubic time, I think).  Then, you can check whether the DFA has any cycles and the length of the longest path in the DFA, and that will tell you the stack depth of the deepest reachable stack configuration.

This will give you an efficient, polynomial-time algorithm that scales even to large, non-trivial grammars.  The cost is that it takes more work to understand the algorithms and implement them correctly, so I'd try the simple solution above first, and only fall back to this if necessary.


Table-Driven Agent Program I have two questions regarding a paragraph about table-driven agent programs from Modern Approach to Artificial Intelligence 3rd Edition.

"Let $\mathbb{P}$ be the set of possible percepts and let T be the lifetime of the agent (the total number of percepts it will receive). The lookup table will contain $\sum\limits_{t=1}^T |\mathbb{P}|^t$ entries. Consider the automated taxi: the visual input from a single camera comes in at a rate of roughly 27 megabytes per second (30 frames per second, 640 x 480 pixels with 24 bits of color information). This gives a lookup table with over $10^{250,000,000,000}$ entries for an hour's driving."

Can someone please show me the step-by-step derivation of the total number of entries based on the given information to arrive at a value over $10^{250,000,000,000}$? I did my math in the following way, but clearly there is something wrong:

$\mathbb{P} = 2^{640x480x24}$, since per frame there are 24x640x480 bits, and each frame is a percept. (I'm not entirely sure that my claim that a frame is a percept is accurate.)

Then, the total number of entries (S) for an hour is as follows:

S = $\sum\limits_{t=1}^{T=3600x30} (2^{640x480x24})^{t}$.

That series can be converted into the following closed form:

S = $\frac{\mathbb{P}^{T+1} - \mathbb{P}}{\mathbb{P} - 1}$.

If I plug in $2^{640x480x24}$ for $\mathbb{P}$, I end up with essentially $10^{240,000,000,000}$ and NOT over $10^{250,000,000,000}$. What am I doing wrong?

"The daunting size of these tables (the number of atoms in the observable universe is less than $10^{80}$) means that (a)...(d) even if the environment is simple enough to yield a feasible table size, the designer still has no guidance about how to fill in the table entries." I'm not exactly sure what guidance the designer needs. I'm assuming that the agent function already exists. In that case, all the designer needs to do in constructing their table entries is look up the corresponding action with each percept sequence.

I thank everyone in advance for taking the time to read this and help me out =)!

You are asking two questions. The answer to your first question is very simple – the authors used a figure of speech when they wrote over $10^{250,000,000,000}$. What they meant was roughly $10^{250,000,000,000}$. In any case, the exact number isn't important – it is just supposed to be an impressively large number rather than an exact estimate. For this reason I didn't bother to check your calculation. It is possible that your calculation is right, and the authors either got it wrong or preferred writing a round number rather than a more pedantic one; but it doesn't really matter.

As to your second question, probably the authors meant what they wrote – even when the table is small, it's not clear what its contents should be! For example, consider a speech recognition program. It is possible to convert the high dimensional raw input into a low dimensional representation using a vocoder. However, it is still difficult to parse what the person is saying, for many reasons. (This is just a guess as to what they meant; you aren't supplying enough context.)

If you want to understand the authors' comments mentioned in your second question better, I suggest you keep reading the book. The authors probably offer solutions to these problems, and these solutions will highlight the problems themselves.


Relationship between RAM size and 32-bit vs 64-bit word size I know that x86 supports only 4GB of RAM, and that switching to x64 greatly increases the size of RAM you can use, but I don't understand why.  Why is the maximum supported ram size related to whether the processor is 32-bit or 64-bit?

x86 is a 32-bit processor.  Memory addresses for x86 are 32 bits.  Each byte has a different address, so a 32-bit address means that you can only address up to $2^{32}$ bytes of memory.  $2^{32}$ bytes is 4GB.  That's why 32-bit processors are limited to 4GB of memory (per application).  In particular, each application can use only 4GB of memory.  (Technically, due to the way paging works, you can have more than 4GB of physical memory, but each application will still be limited to 4GB of physical memory.)

In contrast, a 64-bit processor can use 64-bit memory addresses, which allows addressing a huge amount of memory.  This has freed computers up to have more memory: they are no longer limited to 4GB of addressable memory.  (Technically, x86_64 has 48-bit addresses -- the high 16 bits of the 64-bit address basically can't be used -- but $2^{48}$ bytes of memory is still a humongous amount of memory, about 256 TB of memory.  That's more than anyone is likely to want to buy for now.)


Problem with understanding Multi-party security circuit for secure stable matching I am reading the following paper:
MPCircuits: Optimized Circuit Generation for Secure Multi-Party Computation

Paper Link

I have following question:

We have two groups shown in the circuit. Why we call it a multi-party circuit?

Paper provides a comparison of its multi-part technique with the old 2 part based technique:

  In secure stable matching, the match list is computed while keeping
  the  preference lists private to their respective owners. This problem
  has  been studied in the recent literature [21], [22] where the secure
  stable matching problem is reduced to a two-party secure computation
  scenario. Each individual XOR shares her preference list and sends it
  to two non-colluding servers who perform the secure computation.
  However, stable matching is inherently a multi-party problem and the
  assumption of two non-colluding servers may not be feasible in
  practice. To the best of our knowledge, we provide the first solution
  for multi-party secure stable matching.

The attached figure shows only how to input the preference list of group#1 and group#2. How can we perform n*n computation using the figure?
 Somebody please guide me. Zulfi.

Stable matching involves finding a matching between two groups of people (group 1, say males, and group 2, say females).  Those are the groups that is referring to.


Do subqueries add expressive power to SQL queries? Does SQL  need subqueries?

Imagine a sufficiently generalized implementation of the structured query language for relation databases. Since the structure of the canonical SQL SELECT statement is actually pretty important for this to make sense, I don't appeal directly to relational algebra, but you could frame this in those terms by making appropriate restrictions on the form of expressions.

An SQL SELECT query generally consists of a projection (the SELECT part) some number of JOIN operations (the JOIN part), some number of SELECTION  operations (in SQL, the WHERE clauses), and then set-wise operations (UNION, EXCEPT, INTERSECT, etc.), followed by another SQL SELECT query.

Tables being joined can be the computed results of expressions; in other words, we can have a statement such as:

SELECT t1.name, t2.address
  FROM table1 AS t1
  JOIN (SELECT id, address
          FROM table2 AS t3
         WHERE t3.id = t1.id) AS t2
 WHERE t1.salary > 50,000;

We will refer to the use of a computed table as part of an SQL query as a subquery. In the example above, the second (indented) SELECT is a subquery.

Can all SQL queries be written in such a way as to not use subqueries? The example above can:

SELECT t1.name, t2.address
  FROM table1 AS t1
  JOIN table2 AS t2
    ON t1.id = t2.id
 WHERE t1.salary > 50,000;

This example is somewhat spurious, or trivial, but one can imagine instances where considerably more effort might be required to recover an equivalent expression. In other words, is it the case that for every SQL query $q$ with subqueries, there exists a query $q'$ without subqueries such that $q$ and $q'$ are guaranteed to produce the same results for the same underlying tables? Let us limit SQL queries to the following form:

SELECT <attribute>,
      ...,
      <attribute>
 FROM <a table, not a subquery>
 JOIN <a table, not a subquery>
  ...
 JOIN <a table, not a subquery>
WHERE <condition>
  AND <condition>
  ...
  AND <condition>

UNION
 -or-
EXCEPT
 -or-
<similar>

SELECT ...

And so on. I think left and right outer joins don't add much, but if I am mistaken, please feel free to point that out... in any event, they are fair game as well. As far as set operations go, I guess any of them are fine... union, difference, symmetric difference, intersection, etc... anything that is helpful. Are there any known forms to which all SQL queries can be reduced? Do any of these eliminate subqueries? Or are there some instances where no equivalent, subquery-free query exists? References are appreciated... or a demonstration (by proof) that they are or aren't required would be fantastic. Thanks, and sorry if this is a celebrated (or trivial) result of which I am painfully ignorant.

To translate your statement into the relational algebra, I think it asks:

  Can we rewrite $\sigma_A(A)\bowtie \sigma_B(B)$ as $\sigma_A(\sigma_B(A\bowtie B))$?

(Where $\sigma$ is select and $\bowtie$ is join.)

The answer is "Yes," and it's a standard query optimization. To be honest, I'm not sure how to prove this in a non-question-begging manner - it's just a property of selection and join. You can argue inductively to add however many layers of nested queries you want.

Additionally, you might ask:

  Can every sequence of joins be written as $A\bowtie B\bowtie C\bowtie\dots$ [As opposed to, say, $(A\bowtie B)\bowtie(C\bowtie D)$]?

Again the answer is yes, because join is associative. Similar statements can be made about projection as well.

One notable type of "subquery" which I think cannot be "flattened out" is with. One way to see this is to note that if you have a with statement then you can have a recursive function, which cannot be written without using subqueries.

So to sum up: in the specific case you mentioned, no, SQL does not need subqueries, and you can prove it inductively. In general though, there are features which require subqueries.