Greedy proof: Correctness versus optimality I am really confused after surveying a bunch of material online about correctness versus optimality proof for greedy algorithms. Some website even uses both correctness and optimal in the same sentence!

From my best unconfirmed understanding, the optimal proof uses "greedy stay ahead" where I need to show that greedy algorithm constructs a solution set that is no worse than the optimal set

The correctness proof utilizes the swapping argument to show that any difference between output set A and optimal set OPT can be eliminated by swapping the items in the optimal set.

Can someone clarify if I must only use the "greedy stay ahead" proof method for the optimal proof and not the correctness proof? And must I use the swapping argument (with contradiction) to show that swapping items in the optimal set?

Greedy stay ahead: http://www.cs.cornell.edu/Courses/cs482/2007sp/ahead.pdf

Swapping: http://www.cs.oberlin.edu/~asharp/cs280/handouts/greedy_exchange.pdf (Note that author states that this proves correctness and ends with prove optimality)

Instance where swapping was used to prove optimality, greedy stay ahead used to prove correctness: http://test.scripts.psu.edu/users/d/j/djh300/cmpsc465/notes-4985903869437/notes-5z-unit-5-filled-in.pdf

You can use whatever proof method you want. Proofs aren't even limited to existing patterns such as "greedy stay ahead" and "swapping". Indeed, in some cases, such as the greedy algorithm for maximizing a submodular function over a uniform matroid, the proof consists of adding together a bunch of inequalities expressing the fact that the random choice was (greedily) optimal.

Usually the proof that a greedy algorithm works compares itself against an optimal solution, though when proving approximation guarantees, it could be enough to compare the greedy solution to the theoretical maximum (a case in point is the derandomized version of the random 3SAT algorithm).

Also, I suspect that "correctness" and "optimality" mean the same thing.


Do Higher Order Functions provide more power to Functional Programming? I've asked a similar question on cstheory.SE.

According to this answer on Stackoverflow there is an algorithm that on a non-lazy pure functional programming language has an $\Omega(n \log n)$ complexity, while the same algorithm in imperative programming is $\Omega(n)$. Adding lazyness to the FP language would make the algorithm $\Omega(n)$.

Is there any equivalent relationship comparing a FP language with and without Higher Order Functions? Is it still Turing Complete? If it is, does the lack of Higher Order on FP makes the language less "powerful" or efficient?

In a functional programming language that is powerful enough (for example, with data types to implement closures) you can eliminate all uses of higher order by the transformation of defunctionalization. Since this method is used to compile this kind of language, you can reasonably assume that this does not affect performances and that in this setting higher order does not make the language any less powerful. However it does affect how to write code.

However if the language is not powerful enough, then yes, higher order does provide expressive power. Consider the lambda-calculus: without any higher-order function, it really can't do anything, mostly because the most basic data types (integers, booleans) are implemented using functions.

In conclusion, it really depends on the language.

Above is my answer. Below, a comment about a usual assumption on imperative languages.

  about an algorithm that on a non-lazy functional programming language has an $\Omega(n \log n)$ complexity, while the same algorithm in imperative programming is $\Omega(n)$. Adding lazyness to the FP language would make the algorithm $\Omega(n)$.

I would like to see this reference. The usual assumption is that an access to a array of length $n$ in a RAM is in time $O(1)$ and the equivalent in pure FP is in in time $O(\log n)$. That is not entirely true: the access time in a RAM is in $O(\log m)$ where $m$ is the size of the memory. Of course, $m≥n$. In practice accessing an element of an array is much faster. A reason would be that $m$ is bounded but... so is $n$!

EDIT: thank you for the link (the link for the paper about laziness is not available, here is another one). As posted in the comments and above in my answer, the model of RAM is a little unfair to pure FP by providing $O(1)$-time look-ups even when the size of one address is not bounded. I am yet to understand how the lazy trick works but I think it is important to note that this is only for this particular problem.


Is it possible to eliminate the unit rules in this? S -> aA | bC | CC | a | b | C
A -> B
B -> S
C -> A | S

It looks like its going to loop so it would be endless replacing the unit rule....

You can always eliminate unit rules. In fact, every context-free grammar can be massaged to one in Chomsky normal form, and there are several algorithms doing that. Their treatment of unit rules is more subtle than what you suggest.


Caroll's paradox => Rice theorem? To me (but I might be wrong) Rice's theorem asserts that it's not possible to formalise the demonstration of a non-trivial property of a recursively enumerable language within the same given language. The modus ponens being the basis for demonstrating, Rice therefore says in substance that you will necessarily need a metalanguage to define it.

What I call Carroll's paradox is referred in Wikipedia under What the Tortoise Said to Achilles.

Wikipedia explains the following:

  The Wittgensteinian philosopher Peter Winch discussed the paradox in The Idea
  of a Social Science and its Relation to Philosophy (1958), where he argued that the paradox showed that "the actual process of drawing an inference, which is after all at the heart of logic, is something which cannot be represented as a logical formula ... Learning to infer is not just a matter of being taught about explicit logical relations between propositions; it is learning to do something" (p. 57). Winch goes on to suggest that the moral of the dialogue is a particular case of a general lesson, to the effect that the proper application of rules governing a form of human activity cannot itself be summed up with a set of further rules, and so that "a form of human activity can never be summed up in a set of explicit precepts" (p. 53).

In other words, Carroll's paradox shows that it's not formally possible to prove a property of a language purely with propositions of this language. You will need to admit a rule (or a principle) that "the modus ponens means X" with X using everyday words. I.e. you will need a meta language.

I will concede that it is a philosophical way to ask the question. But Carroll's paradox can be described in a formal (mathematical) way (done here).

Hence am I mistaken in principle to say that Caroll's paradox implies Rice's theorem?

Well, any true statement implies every other true statement, so in that vacuous sense, I suppose one implies the other.

But no, I wouldn't say that Carroll's paradox implies Rice's theorem in any interesting or meaningful way.  Carroll's Paradox is an explanation of why we need modus ponens as an inference rule in propositional logic and can't replace it with a finite list of axioms.  It's nothing fancier than that.  As such, it refers to what is true in a logical theory.  It refers to what inference rules or axioms we need.

Rice's theorem is different.  It talks about what is decidable, not what is true.   It talks about what can be computed on a Turing machine, not about the inference rules or axioms we need.

Rice's theorem doesn't say "it's not possible to formalise the demonstration of a non-trivial property of a recursively enumerable language within the same given language".  It has nothing to do with "within the same given language" (it's not even clear what that would mean; a language is a subset of $\{0,1\}^*$ and doesn't demonstrate anything), but rather with that can be computed with a Turing machine.  Rice's theorem talks about what a Turing machine can decide.

Rice's theorem doesn't say "you will necessarily need a metalanguage to define modus ponens".  (I don't even know what a metalanguage would mean in this context.)  It has nothing to do with what you can define.  Rather, it has to do with what a Turing machine can decide.

In general, I warn you against trying to reason about mathematical statements using English language and analogies.  That is notoriously error-prone.  Rice's theorem is a mathematical statement with a precise mathematical meaning.  At a suitable level of imprecision and vagueness, I suspect everything can seem similar and connected -- but when you look at the specifics, the situation often becomes richer and more interesting than that.


Analyzing Twitter Relationships I'm not even sure if this is the right StackExchange to post this, but it seems like sentiment analysis would go here.

What would be the best approach to determine if two people on Twitter are actually friends?

I think that the first criteria would be that they are following each other. This would eliminate all of the celebrities, companies, etc. that a person follows.

The second criteria could be physical proximity to one another. If two people tweet from the same general areas, then there's probably a higher chance that they actually know each other.

After that, I'm not sure what criteria I should look for. Would sentiment analysis of their tweets to each other be a viable option? With that friendly sentiment could indicate that they actually know each other.

My metric of choice would be the communication by direct message. However, this metric is hard to come by since measuring it requires the user's consent.

I do not think that using similar hashtags or terms has any say over friendship. People tend to adjust to the language they read and do not require personal bonding to do so.

I think mentions are a good way to identify friends and foes alike. A good way would probably be to see whether mentions beget a reply. Users tend to 'reward' pleasant and useful mentions with replies. However, the semantics of these messages are very important and only quantified analysis may not be enough.

Since I cannot comment yet, I would like to reply to the suggestion of using machine learning. I do not think that machine learning can effectively identify friends, even if one manages to get 'sufficient' data. Using Twitter is a rather creative process and generally not uniform across social circles.


RSA Encryption & Anonymity Considering plain RSA encryption, assume we have B who wants to send 10 messages to either A1 or A2. The recipients' public key, namely the exponent e1, e2 and prime product n1, n2 for A1/A2 respectively, is publicly known.

When B sends out, he will either encrypt his messages via $c_i = (m_i)^{e_1} mod (n_1)$ or $c_i = (m_i)^{e_2} mod (n_2)$

Let's assume eavesdropper E gets hold of the 10 encrypted messages $c_i$. Given that she knows e1, e2, n1, n2 - while she can't figure out the messages m themselves, can she figure out whether B sent the messages to A1 or A2, and if so, how?

I'll just expand one of the attacks mentioned in D.W.'s comment; this attack seems the most relevant to your question, but other attacks may exist according to the parameters you actually use.

Ideally, an encryption can be viewed as a permutation $\pi_i$ (determined by $e_i$), that maps $\{0,\ldots,n-1\}$ to itself. If you don't know the two permutations and you don't know the messages $m_i$, there is no way to tell if you used the permutation $\pi_1$ or $\pi_2$ by only seeing a small number of (image only) samples.

Under certain assumptions, RSA is a good encryption. This means you cannot decrypt a codeword $c$ and find $m$ such that $m^e=c \mod n$, even if you know $e$. Of course, information-theoretically, knowing $e$ gives you all the information you need to find $m$ from $c$–it fully specifies the permutation. But for a computationally-bounded Eve, we assume this is impossible.

However, if $n_1 \ne n_2$, Eve gets a certain advantage in distinguishing ecryptions in the two settings. By definition, $c_1 \in \{0,\ldots, n_1-1\}$ while $c_2 \in \{0, \ldots, n_2-1\}$. So if $n_1$ is very different from $n_2$ (say, $n_2>n_1$), and Eve is lucky to see $c_i \in \{n_1, \ldots, n_2-1\}$, she knows that this message was encrypted using $(e_2,n_2)$. Assuming RSA is close to a random permutation, then this has probability of about $1/(n_2-n_1)$ per sample.


Finding constrained random time intervals with a constrain also on their sum I'm searching to devise an algorithm that finds a set of n time intervals with a random duration between min and max. On top of that, the total duration is also given (tot).

For example:

  n = 15

  min = 30 s

  max = 90 s

  tot = 15 minutes

means:
"Find 15 time intervals, each of a duration between 30 and 90 seconds, which, when summed together, produce a total time interval of 15 minutes"

To check whether there is a solution to the problem I would just make sure that
min * n <= tot <= max * n.

To make sure that the total duration is equal to tot I would apply a found ratio to all the time intervals.

However, how to make sure that the min and max constrains are met even after the ratio is applied? Am I on the right track?

Let’s consider general parameters $n$, $\min$, $\max$, with $0<\min<\max$ and $tot=1$ (you can transform your problem to this form simply by considering 15 minutes as the measure unit for time). What you are trying to do is to sample from the intersection of the following two set:

the set $S=\left\{(x_i)_{i=1}^{n}|\Sigma_{i=1}^{n}x_i=tot=1\right\}$, the canonical n-dimensional simplex, and
the set $C=\left\{(x_i)_{i=1}^{n}|\forall i\, x_i \in [\min,\max]\right\}=[\min,\max]^n$ which is a n-dimensional hypercube in the first octant.

To see the shape of this set let’s fix $n=3$, so we now are in a $3$-dimensional space and the hypercube is an actual cube. The cube depends on the parameters $\min$ and $\max$. If you keep the radius $R=\frac{\min-\max}{2}$ constant and change the mid-point $m=\frac{\min +\max}{2}$ of the interval $[\min,\max]$ you are translating the cube with direction $\left(1,1,1\right)$. Instead if you change radius $R$ but keep the mid-point $m$ constant you get are expansion (the edge of) the cube.

The intersection of the simplex and the cube is a hexagon, whose regularity depends on the value of $R$. Moreover, it may happen that the hexagon collapses to a triangle, or to a point or to the emptyset (in these two cases you can sample only one point or none at all, so the problem is trivially solved). So, if we know how to compute the vertices of the hexagon, the problem reduces to a sampling from a hexagon.

To compute the vertices notice that they lie only on those edges of the cube such that one end-point lies “above” the simplex and the other “below”. So you could search all the couple of adjacent vertices of the cube such that one end-point satisfy the constraint $x+y+z\geq1$ and the other satisfy the constraint $x+y+z\leq1$. For all these couples $\left(e_1,e_2\right)$ you can parametrize the segment $e_1e_2$ in the form $Le_1+(1-L)e_2$ for all $L$ in $\left[0,1\right]$ and then find that particular $L$ such that the point on the segment lies on the simplex, i.e. find L such that $x_L +y_L + z_L=1$ where $(x_L,y_L,z_L)= Le_1+(1-L)e_2$.

Once you have computed the six vertices of the hexagon you should be able to decide if it is really a hexagon -if all vertices are distinct- or a triangle -if there are only three distinct vertices- or something trivial.

To sample from a triangle you can, for example, find a transformation $\varphi$ from the canonical simplex to the triangle, sample from the simplex (for example as in cs.stackexchange.com/q/3227/755 as suggested by D.W.) and then transform the sample using $\varphi$. To ensure uniformity you should sample uniformly in the simplex and normalize $\varphi$ with the norm of the determinant $d$ of its jacobian matrix (when $d\neq 0$), i.e. use the transformation $\psi =\begin{cases}\varphi & \text{if }  d=0\\\frac{\varphi}{d} &\text{if } d\neq 0   \end{cases}$.

To sample from a hexagon you can divide the hexagon in six triangles drawing the edges from the vertices to an inner point of the hexagon (for example $\left(\frac{1}{3},\frac{1}{3},\frac{1}{3}\right)$; infact, this point is a possible sample if and only if there is at least one sample), choose randomly one of them, and then sample from that triangle. In this case to get uniformity, on top of sampling uniformly from triangles, you should choose the triangles using a probability distribution $\left(p_i\right)_1^6$ of the form $p_i =\frac{\text{area of the }i\text{-th triangle}}{\text{area of the hexagon}}$ (with this choiche you cover also the case of a collapsed hexagon). However, I suppose there are much more refined methods to sample from a triangle or from a hexagon.

Generalizing to grater values of $n$, instead of a hexagon divided in six triangles, you should get a $n-1$ dimensional convex surface whose vertices can be computed as above. This surface can be divided in some $n-1$ dimensional simplicial polytopes. So you select randomly one of these polytopes accordingly to their volume, find a transformation from the $n-1$ canonical simplex to this polytope and use it to transform a sample from the $n-1$ dimensional simplex.


Example of reduction such that it is not many-one reduction while it is not turing reduction I am reviewing things I learned, and I can't suddenly come up with an example of reduction that is not many-one, but Turing reduction. Can anyone present such an example?

A simple example would be a reduction from e.g. $SAT$ to it's complement $\overline{SAT}$, which works as follows: given a formula $\varphi$, you can decide whether $\varphi$ is satisfiable by deciding whether $\varphi\in \overline{SAT}$, and then negating the answer. This is a Turing reduction, since you use an oracle for $\overline{SAT}$ to solve $SAT$.

A similar example can be constructed for HALT and it's complement, if you want decidability, rather than complexity.


How to define enumeration of the set of finite state machines? I want to write a function that takes N (maximum number of states) as a parameter, enumerates all possible finite state machines up to N states, and returns random FSM with a probability in proportion to the number of states (fewer states more probable). Alphabet = {0,1}
Can you please suggest how to implement this enumeration, encoding / decoding.
Something similar to how in Kolmogorov complexity there is an enumeration for Turing machine programs.

One simple encoding is to represent each of the $N$ states by a partial function $f_n:\{0,1\} \rightarrow \{1, \dots, N\}$. Input $x$ in state $n$ will cause a transisition to state $f_n(x)$ if $f_n(x)$ exists and an error condition if not. You can assume that the initial state is always state $1$.
For $N$ states there are $(N+1)^2$ such partial functions (because either $0$ or $1$ or both may fail to have an image), so there are $(N+1)^{2N}$ encodings. However, some of the encodings will represent FSMs that are isomorphic (because they represent the "same" FSM with a re-labelling of states).
For example, for $2$ states there are $9$ partial functions from $\{0,1\}$ to $\{1,2\}$ and each state can be represented by one of these partial functions, so there are $9^2=81$ representations of FSMs. The $2$ state FSM which stays in the same state on input $0$ and changes to the opposite state on input $1$ is represented by the two functions
$f_1(0)=1 \quad f_1(1)=2\\
f_2(0)=2 \quad f_2(1)=1$


Algorithm to compose identity from a set of permutations Given a subset P of all the possible permutations of a fixed set of elements, is there a non-exponential or optimized algorithm for computing the smallest composition of P that yields the identity permutation?

Assuming that "smallest composition" means smallest number of permutations used in the composition, then the NP-complete Pancake Flipping Problem is a special case of your problem.


Girth of Undirected Graph with Positive Integer Weights Let $G = (V, E)$ be an undirected graph without self loops and with edge weights $w: E \to \mathbb{N}$. The girth $g(G)$ of $G$ is defined as the length of the shortest cycle in $G$, i.e.

$g(G) := \min\left\{ n \in \mathbb{N} \mid \exists \text{ cycle }(e_1, e_2, \dots, e_k) \text{ in $G$ satisfying } n = \sum_{i = 1}^k w(e_i) \right\}$.

GOAL. Determine $g(G)$ algorithmically and as efficient as possible in terms of time complexity. Note that it's not necessary to find corresponding cycle, length is sufficient.

I present my thoughts on this problem as following. If the graph is unweight, i.e. $w(v) = 1$ for all $v \in V$, we may start a breadth-first search traversal keeping track of the depth of each vertex. Once we detect an edge which leads to an already visited vertex $v$, a cycle is found. The length of the cycle is the difference of the current depth and the depth of $v$. BFS from each vertex and taking minimum should do the job, time complexity is $\mathcal{O}(|V| \times (|V| + |E|))$.

How to deal with edge weights? It seems natural to modify Dijkstra, but I do not see how, because the cycle with least edges may be different from the cycle of minimum weight, the shortest cycle. Is there still a way to use Dijkstra in order to solve this problem?

Can we adapt an all-pairs shortest path algorithm? I would appreciate a solution based on Floyd-Warshall, because of it's simplicity (if there is no faster algorithm). One may assume the graph to be dense, i.e. $|E| = \mathcal{O}(|V|^2)$, so the above solution is $\mathcal{O}(|V|^3)$.

Use an all-pairs shortest-paths algorithm to find the distance from each vertex to each other vertex, call it $d(u,v)$.  Now find the minimum value of $d(v,v)$ over all vertices $v$.  That is the length of the shortest cycle.

Why does this work?  Suppose the shortest cycle from $v$ to $v$ has length $\ell$.  Obviously we will have $d(v,v) \le \ell$ (since we have a path from $v$ to $v$ of length $\ell$, the shortest such path is at most $\ell$).  Conversely, we know there is a path of length $d(v,v)$ from $v$ to $v$; since it goes from $v$ to $v$, this is a cycle; so the length $\ell$ of the shortest cycle must satisfy $\ell \le d(v,v)$.  We have proven both $d(v,v) \le \ell$ and $\ell \le d(v,v)$, so it follows that $\ell = d(v,v)$.


How to enumerate minimal covers of a set I have a set $S$ and a set $P = \{P_{1},...,P_{n}\}$ with $\bigcup P_{i} = S$. I want to find all the inclusion-minimal subsets of $P$ that are covers of $S$.

What is the best algorithm for enumerating all the inclusion-minimal covers of $S$ contained in a set $P$ and what is its running time?

Additional information : The algorithm must work in the general case. $|S|$ and $n$ can be anything.
I need to enumerate the exact set of all the inclusion-minimal covers of $S$ contained in $P$. Obviously, it is possible to find the first one in polynomial time by just removing elements of $P$. The second one could be found easily by using the same method starting with the different $P\setminus \{P_{i}\}$ with $P_{i}$ an element of the first cover.

I don't really hope for a polynomial delay algorithm but I would be really happy with an incremental polynomial delay, if such a thing exists.

The problem is equivalent to translating a monotone conjunctive normal form Boolean formula to a monotone disjunctive normal form Boolean formula (also called "monotone dualization" in the literature).

Let us for example take $P = \{\{x,z\}, \{x,a\}, \{y,z \}, \{y,c\}\}$. We can translate $P$ to the following boolean formula: $ \psi = (x \vee z) \wedge (x \vee a) \wedge (y \vee z) \wedge (y \vee c)$ and ask for a valuation of the variables that makes the formula valid, but has as few as possible variables set to true as possible.

If we translate $\psi$ to disjunctive normal form, we obtain:
$$\psi' = (x \wedge y) \vee (x \wedge z \wedge c) \wedge (z \wedge a \wedge c)$$
It is now easy to list all ''minimal'' solutions to $\psi \equiv \psi'$.

The paper "Computational aspects of monotone dualization: A brief survey" by Thomas Eitera, Kazuhisa Makinob, and Georg Gottlob contains a nice survey on existing literature to the topic, including algorithms and complexity results.


Why do you reason about the minimum number of nodes of an AVL tree of height h to argue the height is $\log n$ of an AVL tree? Recall the standard argument for showing an AVL free is of size $\log n$:

  Let $n_h = $ be the minimum number of nodes of an AVL tree of height
  $h$. Then we have:

  $$ n_{h} \geq 1 + n_{h-1} + n_{h-2} \implies n_h > 2n_{h-2}$$ $$ n_h > 2^{\frac{h}{2} } \implies h < 2 \log n_h $$

  so the height of the tree is $O( \log n)$.

I understand the recurrence but I just don't understand why we argue about:

  be the minimum number of nodes of an AVL tree of height $h$

maybe my intuition is wrong but I thought that we'd want to argue about as many nodes as we can fit in a tree of height $h$ and show that it still balanced and show its $\log n$. Why is that reasoning incorrect?

First of all AVL trees are binary trees so you can't argue as many nodes as we can fit in a tree of height h because the maximum nodes you can fit in a AVL tree with h is 2h+2h-1+...+20. Also the minimum number of nodes on an AVL tree with h is 1+2h-1+2h-2+..+20.

be careful for the first 1 at minimum number rather than 2h. If that plus one node would not exists, the AVL tree would be simply of height h-1, and we don't want that.

So you have to define n as be the minimum number of nodes of an AVL tree of height h. Because your algorithm has at least that much of nodes to traverse , and you do the analyze with that assumption


Algorithm to find slope of line with a modulus Say I have some data which represents a single line, and I want to determine its approximate slope. This data has a known minimum and maximum on the y-axis. When the line crosses the maximum, it re-emerges at the minimum, or vice versa, so there appear to be many parallel lines in the data. Clearly, the feasibility of this is dependent on the sampling rate and the amount of noise in the data. Also, a slope too steep will put the apparent parallel lines too close to each other such that they'd become impossible to distinguish. So, we'll assume that the sampling rate, noise, and slope are all within reasonable limits. Is there a particularly elegant way to approach this problem?

As I understand it, the best way should just be to take the known maximum - minimum as your change in y, and the period length as the change in x (assuming the function you've described is periodic, with its domain as ℝ), and their ratio is the slope.  Since you're dealing with discrete points, you'd just need enough data to estimate the shape of two periods to solve for the period length, but more is obviously better.


Which would be better for programming using Homotopy type theory Agda or Idris I'm looking to model data inputs for an artificially intelligent system, which is affected by its internal parts and has feedback loops. I'd like to model it mathematically, using category theory or homotopy type theory.
Is Agda or Idris the best choice for such modelling?

Agda is definitely the better choice if you're doing Homotopy Type Theory.

Idris has several features that are specifically incompatible with HoTT. Specifically, you can use dependent pattern matching to prove Uniqueness of Identity Proofs (UIP), which, when combined with Univalence, allows you to prove False. There's also a type-case feature which you can use to directly prove False from univalence.
Agda has some features that are specifically designed to enable HoTT. Namely, it has a --without-K option, which ensures that you can't prove UIP or the related Axiom K. There's also a whole language extension for Cubical Type Theory, which uses a special notion of equality gives computational meaning to univalence.

Relevant reading:
Introduction to Univalent Foundations in Agda
Pattern Matching without K
Proof-relevant Unification in Agda
Cubical Agda Paper
Cubical Agda documentation
Cubical Agda tutorial


Approximation algorithm question, clustering on n points So the algorithm I thought of, is to iterate through the n points, centering a ball at each point, and keeping track of the point where we centered that encapsulated the most points. Then remove the encapsulated points from this max ball we found, then iterate through all the points again. Continue until there are no longer any points not encapsulated. Return all the centers we found.

I'm not sure if this algorithm is correct. O(1) approximation algorithm is in terms of O( $\frac{\Delta_{ours}}{\Delta}$). The requirement is a polynomial algorithm, which I believe mine is in the order of $n^{2}$.

I'm also not sure how to prove the correctness of an approximation algorithm either.

There's an even simpler algorithm, the greedy algorithm. This algorithm iterates through the points in some order. Initially the set of centers is empty. When point $p$ is reached, if $p$ is within distance $2\Delta$ of one of the selected centers, then we do nothing. Otherwise, we add $p$ to the set of centers. Naive implementation of this algorithm runs in time $O(kn)$, which is polynomial.

Why does this work? Suppose that balls at radius $\Delta$ centered at the points $p_{i_1},\ldots,p_{i_k}$ cover the entire set, and suppose that the algorithm above has selected points $p_{j_1},\ldots,p_{j_k}$. We have to show that every point in the set is within distance $2\Delta$ of these points.

For a point $p$, let $c(p)$ denote the point among $p_{i_1},\ldots,p_{i_k}$ which is closest to $p$.
I claim that $c(p_{j_a}) \neq c(p_{j_b})$ for $a \neq b$. Indeed, by construction $\|p_{j_a}-p_{j_b}\| > 2\Delta$. But if $c(p_{j_a}) = c(p_{j_b}) = q$, then $\|p_{j_a}-p_{j_b}\| \leq \|p_{j_a}-q\| + \|q-p_{j_b}\| \leq 2\Delta$.

Renumber the points so that $c(p_{j_a}) = p_{i_a}$, and consider an arbitrary point $p$ in the set. Suppose that $c(p) = p_{i_a}$. Then $\|p-p_{j_a}\| \leq \|p-p_{i_a}\| + \|p_{i_a}-p_{j_a}\| \leq 2\Delta$.


Algorithm challenge: build a pile of 'n' cubes whose total volume adds up to 'm' I'm working on solving an algorithm problem defined as follows (important parts in bold):

  Your task is to construct a building which will be a pile of n cubes. The cube at the bottom will have a volume of n^3, the cube above will have volume of (n-1)^3 and so on until the top which will have a volume of 1^3.

  You are given the total volume m of the building. Being given m can you find the number n of cubes you will have to build?

  The parameter of the function findNb will be an integer m and you have to return the integer n such as n^3 + (n-1)^3 + ... + 1^3 = m if such a n exists or -1 if there is no such n.

Okay, so here's how I've been approaching the problem from a theoretical standpoint:

The summation 1^3 + 2^3 + ... + n^3 is equal to [n(n+1)/2]^2 = m.
Taking the square root of both sides yields |n(n+1)/2| = sqrt(m). We can disregard the absolute value sign because n will always be positive. So n(n+1)/2 = sqrt(m).
Therefore, n(n+1) = 2*sqrt(m). This problem is essentially asking us to find two consecutive numbers, n and n+1, such that their product is equal to 2*sqrt(m).

My code

def find_nb(m):
    target = 2*math.sqrt(m)
    for n in range(1, int(math.sqrt(target))+1):
        if n*(n+1) == target:
            return n
    return -1

Here, I've defined target to be 2*sqrt(m). I'm looping from n=1 to n=sqrt(target) (inclusive) because there is no point in going beyond the square root of the target when trying to find two numbers, n and n+1, whose product equals the target.

The issue...

This code runs into floating-point precision issues that are fairly consistent across all tests that failed. Here are some screenshots of tests that failed:

Notice that in all of these cases, the value I end up returning is 1 less than the value I stopped looping at. This is quite odd, and I'm not sure what could be causing this behavior.

If you compute the values using a good calculator, you'll find that it is indeed an issue of floating-point imprecision. I'm not sure how to deal with that. My code fails for 33/69 test cases.

Alternative approach

In yet another attempt, I tried doing the most straightforward solution possible: looping from n=1 to n=m and calculating [n(n+1)/2]^2 for each iteration, then comparing this to m. And, unsurprisingly, that solution is not accepted because it takes too long to execute for very large values of m!

So I tried looping from n=1 to n=sqrt(m) to at least simplify the range of values I'm working with. But clearly, the exponentiation, division, and multiplication add up in terms of complexity, and thus this revised approach also results in an execution timeout.

Question

How am I supposed to solve this problem? Is it possible to solve this problem without introducing floating-point errors and without the algorithm taking an unreasonable amount of time for large input values?

Here is a Python function that is about as simple as possible and as fast as possible, assuming the input is valid.

def find_nb(m):
    return int(math.sqrt(2 * (math.sqrt(1.0 * m))))

If the input can be invalid, such as 10252519345963644753026 in the question, and the function should return None accordingly, the Python program can be the following.

def find_nb(m):
    # Use float since math.sqrt is wrong for big integers.
    target = int(math.sqrt(2 * (math.sqrt( 1.0 * m))))
    # or target = int(1.4142135623730951 * m ** 0.25)

    if (target * (target + 1) // 2) * (target * (target + 1) // 2) == m:
        return target
    else:
        return None

What is happening? According to Daniel Castle's comment, for $m\ge1$,

$$ n=\frac{-1+\sqrt{1+8\sqrt{m}}}{2}=\frac{-1}2+\sqrt{\frac14+2\sqrt{m}} $$
It can be checked easily that  $$ n + 0.4 < \sqrt{2\sqrt m} < n + 0.5$$

That means, $n = \lfloor \sqrt{2\sqrt m} \rfloor$ with plenty of room to prevent an error.


Find the smallest summed distances by uniquely pairing elements of one set to elements of another set As input I have two sets of points in RN, typically for large N, for example N=40. Supose both sets have m elements:

S = s1 ... sm

T = t1 ... tm

Semantically both sets are equal, but due to noise (of whatever kind) on the R^N points, elements which should be semantically the same still have a distance larger than 0.

What I want to find is m tuples (si, tj) such that the sum of distance(si, tj) is minimized and such that sk and tk exactly occur once in the set of tuples for k=1...m. Basically (i,j) have to be chosen as towers on a chessboard which can not hit each other while minimizing the summed distances.

In other words, I want to find an onto one-one map between S and T which 'is sort of an identity map, but robust to noise'. We assume that the distance measure is a good indication of how similar elements are.

Basically I need to find a permutation of 1...N, and hence I think this problem is either NP-hard or NP-complete, since it 'feels' quite similar to the TSP; however I have not been able to rewrite the TSP problem to a subset of my problem here.

Is this problem realistically solvable for large N? Is there a name for this problem? What would be a feasible solution? Is there another criteria which might be better than the summed distances?

I thought of a greedy approach, let D be a matrix of the distances, dij = distance(si, tj).

T = {}
while D is not empty:
    (i,j) = argmin-(i,j) dij
    append (i,j) to T
    set row i and column j to infinity.

This does not result in the optimal solution, but finds a solution. Would this be my best bet? Should I use simulated annealing, or is it overkill?

PS: from my point of view, this is just a minor problem in a bigger ML problem, however, I am very much interested in the CS background of it.

This is the problem of finding the maximum matching in a weighted bipartite graph.  There are efficient algorithms that solve this problem in polynomial time.

Basically, you have a complete bipartite graph with $2m$ vertices.  $S$ forms one set of vertices; $T$ forms the other set of vertices.  For each $i,j$, create an edge from $s_i$ to $t_j$ whose weight is equal to $-d(s_i,t_j)$, the negation of the distance between $s_i$ and $t_j$.

Now, you want to find a matching whose weight is as large as possible.  This corresponds to a set of pairs $(s_i,t_j)$ whose total distance is as small as possible.  From there, you can use existing algorithms on this graph to find the maximum-weight matching.


Semantic similarity in text Is there a relatively simple way of telling if two pieces of text are semantically similar?

Some assumptions that are valid:

It is all english
I have a list of all the important nouns

Are there any strategies that I should pursue? Looking for something that is relatively computationally cheap, though something that could be scaled to improve accuracy at the expense of computational power would be a bonus.

Note:

Assume that there are not enough posts for some type of probabilistic analysis, but some type of NN might be feasible (I think, just don't know enough about it).

Here's a simple technique.

Train an LDA using something like MALLET over your collection of texts. For each pair of documents you want to compare, obtain the topic distributions and compute the Hellinger distance between them.

Things you can tweak include term weighting, the LDA hyperparameters, and the metric for comparing distributions. Term weighting would obviate both the need for a list of important words, and the restriction to only English.


Determine if the sequence of numbers is a post order traversal of a binary tree The question is: given a sequence of numbers, find an algorithm that determines if the sequence of numbers is in post order traversal of a binary search trees.

Up to now, I have understood the following:

In the post order traversal of the binary tree it follows Left, Right, Root. So the Left value has to be less than the Right value.
The last element of the sequence is the root, assuming the sequence was in the post order traversal.

I do not know how to progress further with this. Also, is there a way to create a Divide and Conquer algorithm for this?

Probably you consider binary search trees, otherwise the exercise is a little useless.

You already concluded that your input has postorder: post-left-subtree, post-right-subtree, root.
Now the value of the root determines which values belong left, and which values belong right. So you are right: this is divide and conquer. Split the numbers according to the subtrees, and repeat for each of the two subtrees.

If a split of the input does not have the form post-left-subtree < root < post-right-subtree, you know what to conclude from that.

An example. The sequence is 1, 5, 9, 7, 3, 13, 17, 15, 11.
So the root is 11. And we can split the sequence accordingly into left and right subtrees: 1, 5, 9, 7, 3 < 11 < 13, 17, 15. Continue with the left and right subsequences.

Another sequence is 1, 5, 13, 9, 7, 3, 17, 15, 11. No split 'at' 11 possible.


Hitting Set Problem with non-minimal Greedy Algorithm The Hitting Set Problem is defined as having a universal set $\mathfrak{U}$, and nonempty sets $S_i \subseteq \mathfrak{U}$ for $1 \leq i \leq n$, and finding a set $\mathcal{H} \subset \mathfrak{U}$ such that $|\mathcal{H} \cap S_i| \geq 1$ for all $1 \leq i \leq n$.

We may ask for the minimal cardinality of $\mathcal{H}$, that is, what is the least number of elements needed to "Hit" every $S_i$?

Further, we may use a greedy algorithm to ensure we find a hitting set. In this greedy algorithm, we set $\mathcal{H} = \emptyset$, and while we still have sets $S_i$ that have not been hit, we add to $\mathcal{H}$ an element whom appears in the most $S_i$ that have not been hit, breaking ties arbitrarily if there are any.

My question is: What is an example of a Universe set $\mathfrak{U}$ and subsets $S_i$, where $1 \leq i \leq n$ for some $n \in \mathbb{N}$, such that the greedy algorithm above does not find a minimal Hitting Set $\mathcal{H} \subset \mathfrak{U}$?

For a longer (and probably clearer) description, and more info on the Hitting Set problem, see http://theory.stanford.edu/~virgi/cs267/lecture5.pdf, or Prove that Hitting Set is NP-Complete.

The greedy algorithm always finds a minimal set (inclusion-wise). However, it does not necessarily find a minimum one.

So what does minimal and minimum mean, you might ask. Minimal set in a family of sets (say the set of all hitting sets), is a set that is not a superset of any other set in the family. That means, a minimal hitting set is a hitting set where if you exclude any element from it becomes a non-hitting set. On the other hand, a minimum hitting set is a hitting set of the smallest size. Even though a minimum hitting set might not be unique, all minimum hitting sets are minimal but minimal hitting sets do not have to be minimum.

An example, where the greedy algorithm does not yield a minimum hitting set is

$$U = \{1, 2, 3, 4, 5\}\\
\mathcal{F} = \{
\{1, 2, 3\}, \{1, 3, 4\}, \{1, 4, 5\}, \{1, 2, 5\}, \{2, 3\}, \{4, 5\}
\},$$
where $U$ is the universe and $\mathcal{F}$ is the family of sets to be hit. A minimum solution is hence $\{2, 4\}$. Any solution including $1$ is not minimum, since the set must hit $\{2, 3\}$ and $\{4, 5\}$ using at least one element of each resulting in a solution of size at least 3. However, the greedy algorithm includes $1$ in the first step and hence can not yield a minimum solution.


How pictures and videos are usually loaded in Memory? Lets assume I'm talking about Jpeg and Mp4 and a general video player(not sure if different ones load it differently, if they do please tell)

So do video players (process) usually load the entire Jpeg or Mp4 including metadata into its own memory space right? like lets say we have a 1920x1080  picture with 10 bytes of metadata, does the picture viewer's process loads this into its own heap or maybe stack?  and does it read it sequentially in order to display it?

I'm asking this because i want to know what stops criminals to for example inject some part of a video or picture with malware, lets say 10 malicious instructions are hidden in that file in a frame of a video or part of a picture, what stops the operating system with no good anti virus from executing these malicious instructions?

Just having malicious instructions loaded into memory is not a problem in itself.  Instructions (code) is just binary, so it might be stored in the data segment.

Where it becomes a problem is if something causes that code to be executed.  It's not clear why a video player would jump to data inside an image.  If it had a security vulnerability, that could happen, but if it has a vulnerability, almost by definition bad things could happen, so that's not really saying much.


Two definitions of balanced binary trees I have seen two definitions of balanced binary trees, which look different to me.

A binary tree is balanced if for each node it holds that the number of inner nodes in the left subtree and the number of inner nodes in the right subtree differ by at most 1.
A binary tree is balanced if for any two leaves the difference of the depth is at most 1.

Does every tree that satisfies def. 1 also satisfy def. 2? What about the other way round?

Definition 1. is also known as weight-balancedness¹ and definition 2. as height-balancedness.

Height-balancedness does not imply weight-balancedness; examples are both AVL- and Red-Black-Trees. See here and here for proofs, respectively.

Weight-balancedness does imply height-balancedness, though. This can be proven by showing the following stronger fact by induction (over height): a weight-balanced tree is complete on all levels but the deepest². The essential argument in the inductive step is that the subtrees can't have a height difference of more than one because -- both having the claimed property by induction hypothesis -- they would then not be weight-balanced.

The article gives a different, more general definition.
In other words, such a tree of height $k$ without the leaves at level $k$ is a perfect tree of height $k-1$.


Why are functional programs considered slower than procedural counterparts asymptotically, if the opposite appears true? I've read and been told way too many times that functional algorithms and data structures have an obligatory O(log(N)) slowdown in respect to their procedural (for-loop/array-based) counterparts. But, after thinking about it, I don't see how that could be true. Mind this for loop

int arbitrary_sum(int* arr, int size, int n){
    int sum = 0;
    for (int i=0; i<n; ++i)
         sum += arr[(int)(random()*size)];
    return sum;
}

That sums N random elements of an array. You'd saiy this is O(N), but that is taking in account array indexing is O(1), which can't be true. For simplicity, assume memory cells are stored linearly. Since that chip must occupy a linear amount of space, and since a signal requires a linear amount of time to travel given space, then it is obvious an indexing operation takes at least O(S) time to complete. That is the time a signal takes to go from the CPU to the memory cell and come back. This means that the complexity of a for-loop is O(N*S), where N is the number of interactions and S is the size of the state that is visible on that for-loop. This way, the textbook int sum(int* array, int size) function, for example, can't be O(N) - it is, actually, O(N^2), for any reasonable implementation of for, as far as physical laws apply. Using layers of caches we are able to shrink the initial S factor and amend this effects, but that has a runtime cost and doesn't change the asymptotics. Now, lets look at the functional counterpart. The most obvious way to sum a container of numbers functionally is folding over a list. For simplicity, lets examine the sum of 0 to 4 using church lists:

((λc.(λn.(c 0 (c 1 (c 2 (c 3 (c 4 n))))))) + 0)

We can optimally evaluate a λ program is using an interaction net, so, lets encode that program as one:

Now, let me propose a new model of computer. Instead of separating the CPU and the memory, we instead store a simplistic computing unit together with each memory cell, each one capable of sending/receiving signals and processing local reductions. On this system, we can reduce the ((λ ...list...) +) abstraction by sending parallel signals from the topmost λ node to each corresponding application. We can also reduce the outermost abstraction by sending 0 to the last application of the list. All that takes no more than 2 runs through the list, and the result is:

From here on, it is clear that the rest of the computation will take a linear amount of time to complete. After all, each redex is local, and the redexes are reduced one by one, producing the result from the tail of the list up to its head.

Under this point of view, it seems to me that functional programs are actually asymptotically faster than imperative counterparts, so, why is the opposite considered the truth?

Without fully answering your question, I would like to answer it at
least partially by remarking that computation cost can be evaluated
only with respect to an abstract model of computation.

If you want to use two different models, for two different programs,
than you have to determine the complexity of reducing each model to
the other, in order to have a meaningful comparison.

Another point is that physics does not well qualify as a computation
model for several reasons:

it is not clear enough what physics allows and does not allow regarding of computation, computation speed, storage, etc.
computation models are defined with various assumptions about unit
operations and their costs, and about infinity and asymptotics,
which are not meant to be a reflection of reality, but only an
approximation of reality intended to facilitate the analysis of
some phenomena, whether abstract or physical.

This is why Turing machines are more appropriate than finite
automata theory to analyse the behavior of devices with very large,
though still finite memory. For example, the powerset construction
of DFA may exist in theory when the memory is finite, however big,
but may also quickly exceed the capacity of our limited universe,
thus hardly making any sense.

Considering your first example about the "physical" time cost of
executing a for loop on an array of size $n$. If we are to do
asymptotic physics, we have to do it right, or at least as right as
current knowledge in physics will allow. Due to universe expansion,
the part of the universe that we can ever hope to access is bounded by
a radius of some $z$ zillion light-years (corresponding to a distance
at which the expansion speed relative to us equals the speed of
light), so that nothing relevant to us can be further away.

You can see that as good news: distances being bounded, access is
asymptotically in constant time, so that the classically accepted cost
analysis does hold, despite your remarks.

Of course, since you still want to have arbitrarily large memory, you
have to assume that this finite sphere can hold infinitely many bits
of information ... which I fear physicists cannot really tell. But
let's be optimistic.

Another way to do away with your remark is to consider that the access
time is small enough that it will not really impact the computing
time, unless you have specific reasons to think otherwise.

Some high speed computer do have to be programmed taking into account
physical distances, in particular to memory. But why should functional
program be exempted from such physical limitations. How much
computational capacity do you store with each cell?  Instead of the
$+$ operator, can you pass any arbitrarily complex fuction as
parameter and still have it reduced locally in each memory cell.

Or to put it differently, what prevents an imperative program from
taking advantage of an architecture that has computing power in each
memory cell. This is remindful of various specialized architectures,
such as vector processors.


Splay trees: why are depths of nodes on the access path halved? The original paper describing splay trees Self-Adjusting Binary Search Trees by Sleator and Tarjan claims that:

  Splaying not only moves x to the root, but roughly halves the depth of every node along the access path.

What is the intuition for this claim? The paper includes some figures (splaying in a tree of all zig-zigs or all zig-zags) and while I can see at a high level that splaying helps other parts of the tree, it's not really clear to me where the halving comes from?

Nobody has answered this question yet, and I can give some hints how to solve it.
I would much rather post this as a comment, but I can't since I don't have enough reputation.
So here is a link to the original paper: https://www.cs.cmu.edu/~sleator/papers/self-adjusting.pdf
The basic idea is looking at zig-zig and zig-zag (zig only happens once when the parent of x is the root!):

Notice that if a node was in the search path before x was pushed to that position, it is now either in A or in B.
Notice that all nodes in A and B have at least 1 depth less than before the zig-zig operation

Notice that if a node was in the search path before x was pushed to that position, it is now either in B or in C.
Notice that all nodes in B and C have at least 1 depth less than before the zig-zag operation

Now just think about how many zig-zig and zig-zag operations there are for a node with depth d in the search path.


Simple question on the phrasing on a PBS Infinite Series video What does she mean by finding the 6 qubit quantum state $|010001\rangle$ from a sphere of dimension $2^6$.

Here is the link: https://www.youtube.com/watch?v=IrbJYsep45E
at time 8:47.

The state of an $n$-qubit system is a superposition of the $2^n$ pure states
$$
\sum_{x \in \{0,1\}^n} \alpha_x \left| x \right\rangle,
$$
where the $\alpha_x$ are complex numbers satisfying $\sum_x |\alpha_x|^2 = 1$. The $2^n$-dimensional (complex) sphere is just
$$
\{ (\alpha_{0\dots0},\ldots,\alpha_{1\dots1}) \in \mathbb{C}^{2^n} : \sum_x |\alpha_x|^2 = 1 \}.
$$
I'm not sure what "finding" $\left|010001\right\rangle$ on the sphere means, though.


How is an OS page stored in a k-way set-associative cache? I have been reading about set-associative caches. As far as I have read, in case of n-way set-associative cache each way stores, a block (let's say 16 bytes) and therefore each set will be of size 16n bytes. But what if I have to load a whole page into the cache. Since the size of a page is much larger than a block, how is that distributed over the cache?
Another question is what would be the distribution in case of a shared NUCA cache design? Assume that a single tile has a private L1 cache and shared L2 cache.

There are few things to be cleared first.

Lets assume a away set associative cache with bwide cache-lines and c number of cache lines. In this configuration, size of the cache is a X b X c. Number of bits needed to represent the number of cachelines, is called index bits. (ex: 1024 cachelines will need 10 bits). When we need to load data, the index bits of the memory address tells us in which cache line this data will be stored. Since our cache is away, there are a number of cachelines, all indexed by this index bits, this data can be stored. If there are empty lines, we will use them, otherwise we have to replace and entry and store the newly fetched data.

Now coming back to your original question,

Think of "loading the page to cache" as reading the entire page in cacheline quantities. Assuming all the cache entries are invalid, first n reads will be stored in the first entry in each block of cachelines, the second n reads will be stored in the second entry in each block.

In a 2-way set assoc cache with 4 cachelines, this is how it would look like.

cacheline 1 set0 - addr 0
cacheline 1 set1 - addr 4
cacheline 2 set0 - addr 1
cacheline 2 set1 - addr 5
cacheline 3 set0 - addr 2
cacheline 3 set1 - addr 5
cacheline 4 set0 - addr 3
cacheline 4 set1 - addr 7


The recursive solution to the all-pairs shortest-paths of Floyd-Warshall algorithm In the Floyd-Warshall algorithm we have:

Let $d_{ij}^{(k)}$ be the weight of a shortest path from vertex $i$ to $j$ for which all intermediate vertices are in the set $\{1, 2, \cdots, k\}$ then

\begin{align*}
&d_{ij}^{(k)}= \begin{cases}
w_{ij} & \text{ if } k = 0 \\
\min\{d_{ij}^{(k-1)}, d_{ik}^{(k-1)} + d_{kj}^{(k-1)}\} & \text{ if } k > 0
\end{cases}\\
\end{align*}

In fact it considers whether $k$ is an intermediate vertex in the shortest path from $i$ to $j$ or not. If $k$ is an intermediate it selects $d_{ik}^{(k-1)} + d_{kj}^{(k-1)}$ becuase it decomposes the shortest path to  $i \stackrel{p_1}{\leadsto} k \stackrel{p_2}{\leadsto} j$  otherwise $d_{ij}^{(k-1)}$ since $k$ is not an intermediate vertex so it has no effect on the shortest path.

My problem is, For a given shortest path between $i$ and $j$, $k$ is an intermediate vertex or not and its existence is deduced from the structure of the graph not our decision. so we have no freedom to select or not to select the $k$, because if $k$ is an intermediate vertex so we must choose $d_{ik}^{(k-1)} + d_{kj}^{(k-1)}$ and if not we must choose $d_{ij}^{(k-1)}$. But when in formula it takes $\min$ between two numbers, it sounds like that it has option to select any of them while based on the structure of the graph there is no option for us. I believe the formula must be

\begin{align*}
&d_{ij}^{(k)}= \begin{cases}
w_{ij} & \text{ if } k = 0 \\
d_{ij}^{(k-1)} & \text{ if } k > 0 \text{ and } k \notin \text{ intermediate}(p)\\
d_{ik}^{(k-1)} + d_{kj}^{(k-1)} & \text{ if } k > 0 \text{ and } k \in \text{ intermediate}(p)
\end{cases}\\
\end{align*}

In fact the algorithm determines whether the vertex $k$ is "intermediate" on the path from $i$ to $j$.  If indeed $d_{ik}^{(k-1)} + d_{kj}^{(k-1)} < d_{ij}^{(k-1)} $ during the computation we know that (up to the first $k$ vertices) the vertex $k$ is needed to obtain a shorter path between $i$ and $j$.

So, in my opinion, the algorithm takes into account the structure of the graph!


Can a safe state in Banker's Algorithm cause deadlock eventually? I know that unsafe state does not always mean deadlock. That is a situation that banker's algorithm does not detect deadlock accurately. I am just wondering if there is any example of a safe state that deadlocks?

No deadlock as long as you keep running the Banker's algorithm.

By definition, a state is considered safe if it is possible for all processes to finish executing, which means there is no deadlock.

In order to avoid triviality, the question should be asking whether a safe state might change into deadlock. Assume the system is in a safe state (or the system is safe in short) initially. If you are able to run the Banker's algorithm, then

each time a request for resources is raised, the system will

either reject the request so the state  will not change, meaning the system is still safe of course.
or it will grant the request after it have been verified that after the requesting process has obtained those resources the system will still be safe, meaning the system is still safe.

each time some resources is returned, the system will obviously still be safe.

So, you can see that almost by definition and design, a safe state never goes into deadlock under the Banker's algorithm.

A more interesting question might be whether the system guarantees to make progress. The answer is yes, too. For any process, it is assumed that maximum number of instances of each resource type may not exceed the total number of resources in the system. It is also assumed that when a process gets all its requested resources it must return them in a finite amount of time. Suppose at some point of time, no process is able to run yet because of its lack of resources. Since the system is safe, resources will be allocated upon requests continuously until one of process is able to get all the resources it needs, meaning that process will start to run and progress will be made. After some finite amount of time, that process, having made some progress, must return all its requested resources to the system. Now the system is sort of back to square one but with progress made.

For a more rigorous analysis, you can check Selected Writings on Computing: A Personal Perspective
, Springer-Verlag, 1982, by the algorithm's designer Edsger W. Dijkstra.


Minimum Distance Spanning Tree Dijkstra I would like to construct a Minimum Distance Spanning Tree (Dijkstra) for the graph below:

MDST: {(a,c), (c,h), (c,f), (a,d), (h,g), (a,b), (d,e), (h,j), (h,i), (j,k), (e,m), (i,l)}

Is my understanding correct? The total cost would be 49 (sum of the distance from the root for each node).

Like other have pointed out, it seems you are confused by the difference between a minimum spanning tree, and a shortest path tree.

A minimum spanning tree, is a tree such that it spans all vertices, and the sum of all edges is as minimum as possible.

A shortest path tree, is a rooted tree such that the distance between the root, and any other vertex is as minimum as possible. (That doesn't necessary mean that the sum of its edges has to be minimum as possible).


Vertices reachable from negative-weight cycles in Bellman-Ford TLDR: I want to know if there's a simple way to fill in distances for all vertices reachable from negative weight cycles (not just ones on the cycle itself) once Bellman-Ford has found a negative-weight cycle.
The Bellman-Ford algorithm finds single-source shortest distances $d$ for a graph of $|V|$ vertices by making $|V|-1$ passes through all $|E|$ edges with weights $w$, and then checking each edge $u \rightarrow v$, with weight $w(u,v)$, for negative-weight cycles. If $v.d > u.d + w(u,v)$, then we know that there exists a negative weight cycle consisting of some path from $v$ to $u$, then the edge $(u,v)$. It's straightforward to find every vertex on that cycle and set all their $d$ to $-\infty$.
However, this also must mean that any vertices reachable from but not on this cycle must also have $d = -\infty$. One way to update all their distances is to collapse each cycle to a vertex and then perform DFS from each such "cycle vertex", setting $x.d = -\infty$ for every reachable vertex $x$.
I'm wondering if there's a faster way to update all the distances, involving perhaps a smaller modification to Bellman-Ford?

You don't need to perform DFS separately from each such vertex.  Instead, add a new fake vertex $s_0$, with an edge from $s_0$ to each vertex in a negative cycle; use DFS to find all vertices reachable from $s_0$; and set their distances to $-\infty$.  This needs only a single DFS, rather than many DFS's.  It is simple and fast; there is no hope for something that is asymptotically faster, as it takes linear time, and in the worst case, you might need to visit all vertices, taking linear time in the worst case.


Average height of a BST with n Nodes I have to find the maximum, minimum, and average height of a BST with n nodes. After doing some researching I found that the maximum height is $n-1$ and the minimum height is $\log_2(n+1)-1$. My question is how do I get the average height of a BST with n nodes?

Ok, so we need to get a bit mathematical here. Let's first define the following quantities

$X_n$ height of a tree composed of $n$ nodes.
$Y_n = 2^{X_n}$ is referred to as the exponential height.

One of the BST's properties is that the left subtree must contain key values less than the root. Also, the right subtree contains key values greater than the root. This property is recursive so it applies to any node. Having said that, pick any node at random, call it the $i^{th}$ node, then, the left subtree has $i-1$ elements and the right subtree has $n-i$ elements. Therefore,
$$Y_n = 2 \max (Y_{i-1},Y_{n-i})$$
Assuming all nodes are picked with equal probability, so picking a node $i$ has the following probability $$Pr(i) = \frac{1}{n} \quad \forall i=1\ldots n$$
Now, let us find the expected value of $Y_n$
\begin{align}
 E(Y_n) &= E[2 \max (Y_{i-1},Y_{n-i})]\\
 &=
 2 \sum\limits_{i=1}^n Pr(i)E[\max (Y_{i-1},Y_{n-i})] \\
 &=
 \frac{2}{n} \sum\limits_{i=1}^n E[\max (Y_{i-1},Y_{n-i})] \\
 &\leq
\frac{2}{n} \sum\limits_{i=1}^n
E(Y_{i-1}) +
\frac{2}{n} \sum\limits_{i=1}^n E(Y_{n-i})  \\
&=
\frac{2}{n} \sum\limits_{i=0}^{n-1}
E(Y_{i}) +
\frac{2}{n} \sum\limits_{i=0}^{n-1} E(Y_i)  \\
&=
\frac{4}{n} \sum\limits_{i=0}^{n-1}
E(Y_i)
\end{align}

Now, by induction, you can actually prove
\begin{equation}
 E(Y_n)
 \leq
 \frac{1}{4}
 C_{n+3}^3
\end{equation}
Remember that we have
\begin{equation}
 2^{X_n} = Y_n
\end{equation}
or
\begin{equation}
 E(2^{X_n}) = E(Y_n)
\end{equation}
Using Jensen's inequality, we can say that
\begin{equation}
 2^{E(X_n)}\leq  E(Y_n)
\end{equation}
But
\begin{equation}
 E(Y_n)
 \leq
 \frac{1}{4}
 C_{n+3}^3
\end{equation}
So
\begin{equation}
 2^{E(X_n)}\leq  E(Y_n)
 \leq
 \frac{1}{4}
 C_{n+3}^3
\end{equation}
And note that
\begin{equation}
 C_{n+3}^3
 =
 \frac{(n+3)!}{3!n!}
 =
 \frac{(n+3)(n+2)(n+1)}{6}
 \sim
 O(n^3)
\end{equation}
So
\begin{equation}
 2^{E(X_n)} \leq O(n^3)
\end{equation}
Take log on both sides,
\begin{equation}
 E(X_n) \leq O(\log n^3) = O(3 \log n) = O(\log n)
\end{equation}
Therefore, the average BST height is of order $O(\log n)$, which is what you'd expect out of Binary stuff, right ?


Why do floating point values have infinity? Why do floating point values have infinity instead of just a higher exponent?

Because sometimes there just isn't an exponent high enough.

First of all, there is no way to effectively represent all real numbers in a reasonable computational model: it is sufficient to observe that the set of configurations of e.g. a Turing Machine is countably infinite, and the set of real numbers is uncountably infinite. Floating point numbers, are ultimately an approximation of what the "actual" computation would be; models for exact real computation exist but as we said before they necessarily "miss" some numbers.

INF and NaN are part of the IEEE standard for rather practical reasons, namely to give meaning to computations that should fail, for a reason or another, and handle such cases in a safe way. We could, as you are basically suggesting, take a floating point model that is finite but unbounded, dynamically adding more space as we need it. As others have already commented, this kind of generalization is actually missing the point: the strength of floating point computations is that they can be performed very efficiently on hardware, and a dynamic solution would be infeasibly more complex.

But even assuming such a model, we aren't really addressing the core of the issue. Let's say that at a certain point we ask the machine to perform the computation $\log(0)$. Mathematically, it doesn't make any sense, because $\log$ isn't defined on $0$. If we didn't have a special value like -INF to return, we would have to abort the computation (or have the program diverge, or terminate in some kind of error state). You might think that such a thing is reasonable: after all, if we had the machine compute $\log(0)$ the program must be wrong in a way or another.

But it gets worse. In any floating point model, there is a smallest positive number that we can distinguish from zero, let that number be $\varepsilon$. Now, we ask the machine to compute $\delta = e^{-10}\varepsilon$ and then $\log(\delta)$. Observe that all those operations are mathematically legit, for instance we can easily see that $\log(\delta) = \log(\varepsilon)-10$. However $\delta < \varepsilon$, which means that our model literally cannot tell $\delta$ and $0$ apart, by definition of $\varepsilon$. It is much less reasonable to make the entire program fail, now.

Special values like NaN and INF manage to at least salvage the "logical" aspect of the computation, correctly handling equality/inequality checking and the sign, if applicable (i.e. +INF is greater than everything else, NAN is not equal to NAN and so on).


Finding partition with maximum number of edges between sets Given a graph (say in adjacency list form), is there an algorithm to find a partition of vertices such that the number of edges between the two sets of the partition is the maximum possible?

For example, for the following set of edges of a graph with vertex set $\{1, 2, 3, 4, 5, 6\}$:
$\{(1, 2), (2, 3), (3, 1), (4, 5) , (5, 6), (6, 4)\}$, one possible "maximum" partition is $\{\{1, 3, 4, 6\}, \{2, 5\}\}$ with $4$ edges between the sets $\{1, 3, 4, 6\}$ and $\{2, 5\}$.

If your question really is "is there an algorithm", the answer is obviously yes: just try every possible partition and choose the one maximizing the number of edges with endpoints in different parts.

Otherwise, it's unlikely that there is a polynomial-time algorithm. Indeed, this problem is known as maximum cut and it is well-known to be NP-hard.


Eliminate left recursion from grammar Consider the following grammar:

$$
    A\to Ba|Aa|c \\
    B\to Bb|Ab|d
$$

How do I convert this grammar to be LL(1) by eliminating direct and indirect left recursion?

I have tried applying the rule which converts $A \to A\alpha|\beta$ to $A \to \beta A'$ and $A' \to \alpha A'$:

For $A \to Ba|Aa|c$, $\beta = Ba|c$ and $\alpha = a$.
For $B \to Bb|Ab|d$, $\beta = Ab|d$ and $\alpha = b$.

In this way I eliminate direct recursion from each one, but then when I try to substitute A or B with its product and eliminate indirect left recursion, the parsing table finds collisions so the grammar is not LL(1). Any ideas?

Mutual recusive definitions are tricky to eliminate. You'll have to work with the unwieldy expanded form of one of the rules. Here, let's expand $B$
\begin{align*}
B &\to Bb \mid Ab \mid d \\
& \to (Bb \mid Ab \mid d)b \mid Ab \mid d \\
&\to ((Bb \mid Ab \mid d)b \mid Ab \mid d)b\mid Ab \mid d \\
& \to ~\cdots \\
&\to (d \mid Ab) \mid (db \mid Abb) \mid (dbb \mid Abbb) \mid \cdots \\
&\to (d \mid Ab)b^*
\end{align*}
In general, $B \to B(x_0 \mid x_1 \mid \dots) \mid (y_0 \mid y_1 \mid \dots)$ will have an expanded form of $B \to y\cdot x^*$. Things get even more complicated if $B \to z B x \mid y$ and $z$ is nullable. But let's not worry about that just yet, instead, let's turn our attention back to $B$.

Now, notice that I have used the term $b^*$, this is actually just the nonterminal $b^* \to \epsilon \mid b b^*$; this is a standard trick that many "extended" BNF based parsers use as well.

Finally, we can inline $B$ into $A$ to get
\begin{align*}
A &\to Ba \mid Aa \mid c \\
&\to db^* a \mid Abb^*a \mid Aa \mid c \\
&\to (c \mid db^*a)(bb^*a \mid a)^*
\end{align*}

where once again $(bb^*a \mid a)^* \to \epsilon \mid (bb^*a \mid a)(bb^*a \mid a)^*$.

Now, if all you need is $A$, then this is already fine and dandy. However, if you need to expose $B$ as a public method as well, then you'll notice that there is a slight hitch: $\text{follow}((bb^*a \mid a)^*) = \text{follow}(A) = b$, since $B \to Abb*$. But since $\text{first}((bb^*a \mid a)^*)$ also contains $b$, then we can't decide whether we should shift to $\epsilon$ or $bb^*a$ when we encounter a $b$. You might try to inline $A$, so that
$$
B \to (d \mid (c \mid db^*a)(bb^*a \mid a)^*b)b^*
$$
but you still have the same problem. Now you can reason that $(bb^*a \mid a)^*bb^* = b^*(ab^*)^*$, but this is not very generalizable, and it breaks down fast when your language takes a step out of its regular territory. Instead, you'll want to start from the beginning. Expand $A$ first, and inline into $B$.


Determine the worst-case complexity that allow you to conclude that a given array with n elements is not sorted Determine the worst-case complexity (in number of comparisons of two array elements) that allow you to conclude that a given array with n elements is not sorted.

I sort of have a general idea of what is going on. Suppose I have two element array, then make one comparison between these two elements.

If I have three elements, then i compare the 0th index element with 1st index element, sort it, and then compare 2nd index element with whatever is now the 1st element after sorting. Hence, I obtain 2 total comparisons.

Going on this pattern, I believe I will make n-1 comparisons which becomes my worst-case complexity. But of course, this is not a proof. How can I make this mathematically rigorous? Am I on right track?

The minimum number of comparisons to tell whether an $n$-element array is sorted is indeed $n - 1$.
However, we don't have to sort the array to arrive to a conclusion.

Here is how to check an array $a$ in $n - 1$ comparisons.
Compare $a_0$ to $a_1$, compare $a_1$ to $a_2$, ..., compare $a_{n-2}$ to $a_{n-1}$.
If all comparisons result in "less or equal" outcome, the array is sorted.
If any comparison results in "greater" outcome, the array is not sorted.
Here, "sorted" means "the elements follow in non-decreasing order from left to right".

The harder thing is to prove that less comparisons won't be enough.
Sure, if we just followed the above checks but dropped the last one, we won't know whether $a_{n-2} \le a_{n-1}$ holds, so the array is sorted if it does but is not sorted if it doesn't.
But what if we compared some other $n - 2$ pairs?

One way to prove it is to establish and maintain some global characteristic of our knowledge about comparison results.
Namely, consider a graph where vertices are array indices: $0$, $1$, $2$, $\ldots$, $n-1$.
The edges of the graph will be the comparisons we make.

As we add our edges, let us track such global characteristic: the number of connected components in the graph.
Initially, it is $n$, same as the number of vertices.
Each edge either lies inside some component, or connects two different components, so the number of components drops by at most $1$ with each edge added.

In the end, after $n - 2$ edges, we will have at least $2$ connected components.
Let all comparisons for vertices $i < j$ so far result in $a_i \le a_j$, so that the result is still unknown.
Consider any vertex $u$ from one of them and any vertex $v$ from another, such that $u < v$.
If $a_u < a_v$, our array may still be sorted.
If $a_u > a_v$, it is not sorted.

Either of the above does not contradict any prior information about the array, so both are possible, which concludes our proof.
If that's unconvincing, we can construct the example arrays.
For the first case, simply let $a_i = i$, which is clearly a sorted array.
For the second case, let $a_i = i$ for all elements of the $v$'s connected component, and let $a_i = i + n$ for all other indices.
We can check that both arrays are consistent with our $n - 2$ comparisons, and for two vertices $u < v$, $a_u < a_v$ in the first case and $a_u > a_v$ in the second case.


In this implementation of Hoare-partitioning Quicksort, why are additional checks for $i \leq j$ needed? I am looking at the following implementation of Quicksort that uses Hoare partition scheme (two approaching indices $i$ and $j$ starting from either end of the array).

I am having trouble seeing why in the inner while-loops, the condition $i \leq j$ is needed in addition to checking $M[i] \leq p$ (or $M[i] > p$).

What I've tried:

I tried running through several examples with equal elements, ordered elements etc.
I have compared this implementation to the ones given in CLRS Introduction to Algorithms in hope for hints.

What I've found out so far:

In the implementation given here, the Hoare partitioning scheme is used. However, the pseudocode given in the Wikipedia article does not seem to do this additional check.
There is a potential problem in the given implementation that if all elements in $M[l+1..r]$ are les than $p$, the first while loop would not terminate when not checking for $i \leq j$. However, that does not explain the necessity of checking $i \leq j$ in the second inner while loop.

I don't expect a complete answer but I would be very thankful if someone could point me in the right direction.

I am having trouble seeing why in the inner while-loops, the condition $i\le j$ is needed in addition to checking $M[i]\le p$ (or $M[i]\gt p$).  The pseudocode given in the Wikipedia article does not seem to do this additional check. There is a potential problem in the given implementation that if all elements in $M[l+1..r]$ are less than $p$, the first while loop would not terminate when not checking for $i≤j$. However, that does not explain the necessity of checking $i≤j$ in the second inner while loop.

As you suspected, it is not needed to check the condition $i≤j$ in the second inner while loop.

One usual way to prove that condition is not needed is by analyzing all possible cases and establishing various invariants as well as employing the powerful tool of mathematical induction, which will probably convince anyone who can follow through the proof with enough patience. Although I have done that below, it is actually not convincing to myself because of the subtlety in the
Hoare's quicksort as shown in Hoare's quicksort is deceptively simple, the devil in selecting element at index hi as pivot, a slight modification of Hoare's partitioning, what happens if both indexes land on the pivot. Even if I have checked my proof tens of times, it might still miss a corner case or two. As shown/implied by many answers at why is writing down mathematical proofs more fault-tolerant than writing computer code?, a traditional mathematical proof for a moderate computer program is probably far from fully satisfactory or fully correct in general. It is more like how we can understand/believe the program is correct in a high level.

Instead, I have written a program that tests the implementation of Hoare's quicksort with that condition removed.

Here is the testing program.

That program tests the sorting algorithm against every permutation of every possible way $n$ competitors can rank in a competition, allowing for the possibility of ties, up to a certain number of competitors.

What are all possible ways $n$ competitors can rank in a competition? Here is an example for $n=3$. There are four different sorted ranks, [1, 1, 1], [1, 2, 2], [1, 1, 2] and [1, 2, 3]. If a comparison sorting algorithm can sort all permutations of each of those four arrays, which counts to 13, it will sort any array of size 3 correctly. By the way, the number of ways $n$ competitors can rank in a competition is the Fubini numbers.

If a simple sorting algorithm like the current one does not work, it should fail for an array whose size is smaller than 8. For extra insurance, I have run that program against arrays size up to 11. These testing proves that condition is not needed.

A brief mathematical proof

Since many people would prefer a traditional proof, here is a sketch of a mathematical proof of the correctness of the implementation either with or without that additional check.

Let us assume l < r. Throughout the method, M is a constant reference to the array while l and r are constant indices. The pivot p = M[l] is constant, too. All we need to prove is that at the end of outer while loop, M[l] is the pivot, followed by elements not bigger than the pivot up to index j inclusively or no elements if l >= j, followed by all other elements, which are bigger than the pivot. (Then by mathematical induction on r - l, we can prove easily that the method does sort the subarray of M from indice r to l inclusively.)

We can establish the following invariant at the end of each iteration of the outer while loop.

Elements from l + 1 to the smaller of i and j are not bigger than the pivot
Elements from j + 1 to r are bigger than the pivot.

The first inner loop, while ( i <= j && M[i] <= p) { i = i + 1; } will find the smallest index i such that i <= j && M[i] > p or  i == j+1.
The second inner loop, either while (M[j] > p) { j = j - 1; } or while (i <= j && M[j] > p) { j = j - 1; } will find the largest $j$ such that M[j] <= p.

Why is the condition i <= j not necessary? Let us elaborate as here is the crux of current question.

There are two cases at the start of this loop depending on the result of above inner loop.

i <= j && M[i] > p.  As we are looking for an element that is not larger than the pivot going from index j to smaller indices, the latest time we will succeed must before current i. That is, i <= j will always be satisfied throughout the loop. That is, the condition i <= j is not necessary.
i == j+1. The first inner loop must have missed the above case, since j is smaller than j + 1. That means M[j] > p was not satisfied. So at the start of current loop, we have both i > j and M[j] <= p. Using either version of the second inner while loop, we will break the loop right away.

if (i < j) { swap(M, i, j);}. This swap extends both the left hand side of elements that is not bigger than the pivot and the right hand side of elements that is bigger than the pivot.

To tell the truth, I used program to double check various invariants and propositions in the mathematical proof.

Many further questions can be raised, which go much beyond the scope of the current question.

How to improve the performance of the testing problem?
How to reduce the number of test cases needed for a specific size?
Is there a way to determine rigorously an upper bound of the size of the array that need to be tested to prove the correctness of a sorting algorithm given its description?


Help in geometrically understanding "Linear Decision Trees" In the words of (http://www.cs.utah.edu/~suresh/5962/lectures/17.pdf, section 17.2), "Each $f(x)$ can be interpreted as deﬁning a hyperplane in $R^n$. Thus, tracing a path through the tree computes the intersection of the half-planes deﬁned by the nodes touched by the path."

I fail to visualize how path tracing is done? I would be glad to see it explained through the presentation of the path in a 2-dimensional space.

I do understand that $x_1,x_2,...,x_n$ is a point in the $R^n$ dimensional space. But I don't get how Figure 17.1 in (http://www.cs.utah.edu/~suresh/5962/lectures/17.pdf) helped in proving the lower bounds of Element Uniqueness as $\Omega(n\log n)$. I also don't get the implication of $\#F$ being connected components; why can't they simply be called solutions?

Unfortunately, reading online resources did not help me much understand the aforementioned concepts.

Thank you in advance.

At each point in the linear decision tree, we branch according to whether $f(x) > 0$, $f(x) = 0$ or $f(x) < 0$, where $f$ is some linear functional. That means that the values of $x$ reaching some leaf are exactly those values satisfying some system of linear equations and inequalities
$$
\begin{align*}
&f_1(x) = f_2(x) = \dots = f_a(x) = 0, \\
&g_1(x), g_2(x), \dots, g_b(x) > 0, \\
&h_1(x), h_2(x), \dots, h_c(x) < 0.
\end{align*}
$$
Here $f_i,g_i,h_i$ are conditions encountered along the way. (In fact we can get rid of the $h$s, but this doesn't matter.) Each of these conditions — $f_i(x) = 0$, $g_j(x) > 0$ or $h_k(0) < 0$ — is convex, so their intersection is convex. This means that the set of all points getting to that leaf is convex, and in particular, either empty or connected.

In order to get a lower bound for element distinctness (for example), we show that the set $\{x : \text{all components of $x$ are distinct}\}$ has many (in fact $n!$) connected components. If we take one vector each from all the connected components, then all these vectors must land at different leaves (why?), so there must be many leaves, hence the tree must be deep.


proving program equivalence I understand that the general problem of program equivalence is undecidable, but I'm wondering what approaches exist to tackle the problem? I am familiar with Hoare-style verification, but are there any other frameworks for proving program equivalence?

One general approach to the problem is to prove program equivalence by showing the programs have the same semantics. Hoare-style verification, as you say, is one option categorized as axiomatic semantics. Have a look at this article which describes most of the semantic approaches out there, including denotational semantics and operational semantics.


Approximation rate for Greedy Set Cover algorithm (RESOLVED) Set Cover: Consider a set of points X and Si a subset of X. The goal is to get the minimum number of subsets Si such as all points in X are covered. An example is shown by figure bellow. In this case, optimal solution should be OPT = {S3, S4, S5}.

Greedy Algorithm:

greedy(X, F = {S1, S2, ...})
     G_OPT = {}
     U = X
     while U = empty set
          Pick s in F with greatest coverage in U
          G_OPT = G_OPT + s
          U = U - s
     return G_OPT

Goal: To find approximation rate of greedy set cover algorithm above.

What I have so far: Let t be the size of optimal soltion, $t = |OPT|$.

At the beginning of step k + 1, the number of uncovered items in X is given by $|U_{k+1}| = |U_{k}| -$ # of newly covered items;
By pigeonhole principle, # of newly covered items $\leq \frac{|Uk|}{t}$ and then $|U_{k+1}| \leq |U_{k}| - \frac{|U_{k}|}{t} = |Uk|(1 - \frac{1}{t})$;
Taking the Taylor's Series of $\exp(-\frac{1}{t})$, one can easily see that $exp(-\frac{1}{t}) \geq (1 - \frac{1}{t})$;
So, $|U_{k+1}| <= |U_{k}| \times exp(-\frac{1}{t})$;
$|U_{0}| = |X| = n$ (none item is covered at step 0);
Taking $|U_{1}| = n \times exp(-\frac{1}{t})$, gives $|U_{2}| = |U_{1}| \times exp(-\frac{1}{t}) = n \times exp(-\frac{2}{t})$, $|U_{3}| = |U_{2}| \times exp(-\frac{1}{t}) = n \times exp(-\frac{3}{t})$ so on and so forth. Therefore, $|U_{k}| = n \times exp(-\frac{k}{t})$;
Lets say there is no item uncovered at k-th step. So, $|U_{k}| = 0$ and $n \times exp(-\frac{k}{t}) < 1$ (otherwise, there could be a remaining uncovered item in $U_{k}$, and this would be a contradiction of $|U_{k}| = 0)$;
It is possible to get $\frac{k}{t} > ln(n)$ by taking log over the previous inequality.

The expected answer is $\frac{k}{t} \leq ln(n) + 1$. I have seen some lecture videos and lecture notes on the internet that give raise to the same results as I described above. However, they are all vague while getting from $\frac{k}{t} > ln(n)$ to $\frac{k}{t} \leq ln(n) + 1$.

All I can see about k, t and n is:

$k \geq t$
$t \leq n$

Does anyone know the "trick"?

I have figured out the answer.

The trick is not really coming from $\frac{k}{t} > ln(n)$ to $\frac{k}{t} \leq ln(n) + 1$ directly. Lets take 1 step back.

Lets say there is no item uncovered at k-th step. So, $|U_{k}| = 0$ and $n \times exp(-\frac{k}{t}) < 1$ (otherwise, there could be a remaining uncovered item in $U_{k}$, and this would be a contradiction of $|U_{k}| = 0)$;

The step above can be rewritten as:

Lets say there is no item uncovered at k-th step. So, $|U_{k}| = 0$ and we are done. We are interested in how much steps we can take before that happens. So, find the upper bound of k such as $|U_{k}| \geq 1$;
$|U_{k}| \geq 1 \Leftrightarrow n \times exp(-\frac{k}{k}) \geq 1$. This results in $k \leq \frac{ln(n)}{t}$. So, $k = \frac{ln(n)}{t}$ is our upper bound for iterations. If $k = \frac{ln(n)}{t}$, $|U_{k}| = 1$. It's almost done. There is only 1 last item to cover and, consequently, 1 last round to run.
Therefore, $k \leq \frac{ln(n)}{t} + 1$ in order to get $|U_{k}| = 0$. It's easy to see that $\frac{k}{t} \leq ln(n) + \frac{1}{t}$.

One can still get a cleaner solution and say $\frac{k}{t} \leq ln(n) + 1$ since $t \geq 1$.

k is the number of steps taking to get G_OPT. At each step, G_OPT increases by 1. Then, $|G\_OPT| = k$. We defined $t = |OPT|$. We end up with

Approx. rate $= \frac{|G\_OPT|}{|OPT|} \leq ln(n) + 1$


Does the OS create its own bootstrapped stack frame when running a program? I've been doing nand2tetris exercises and I'm quite interested in how compilation actually works. In nand2tetris when creating the VM language I had to create a "bootstrap" which called the main method of the program.

In other languages such as C, Java or even interpreted languages like PHP, does the OS/interpreter/VM automatically create its own first frame on the stack, and then invokes the main method of the program as a new second stack frame?

I'm trying to think about how initial arguments are passed to a program, and how programs are able to return values. Does each OS have a standard way of creating this initial stack frame which all languages adhere to? When I run a program from command prompt and pass it arguments, what is actually creating that initial stack frame that pushes these arguments onto the stack and that invokes my main method?

I have no idea how each system operates, and do not inquire since I
usually do not need to know. However it seems rather easy to make an
educated guess, based on whatever experience I have. There are
many variants that exist. For example a program is often
byte code to be interpreted by a virtual machine. It is all very flexible.

Usually, the program will have its own run time environment, for which
some inital space can be allocated at the
bottom of the stack, or anywhere else, since it will not have to move
while the program executes, and also because it will exist in only one
copy for a run of the program (it is not called recursively). But
bottom of stack is probably simpler. Whether you want to consider that
space as a frame or not is probably not very important. However, it
may be simpler for the compiler/interpreter to maintain a structural
consistency with frames at least for that part which may be visible to or
accessed by the rest of the program, so that access is always done consistently.

This is set up by code inserted by the compiler in the compiled code (or linked to it), and is supposed to respect some
standards of communication with the OS (operating system) it is
intended for, so that data can be passed by the OS to the application,
and returned from the application to the OS.

Such standards are usually OS dependant, and must be conformed to by
the language compiler. The standard may simply imply agreement on the
location were the information to be passed is stored, and possibly
ways of specifying its size, upon call to or return from the program.

The stack of frame policy is needed for recursion, and it is possible only as long as you do not have
functions (called also methods, sub-program, procedure ...) that can
return functions as result. The first important recursive  language with that
property was Algol 60, and the stack of frames was invented for the
implementation of Algol 60.

The stack of frame was invented to implement recursion. However it is
useful even for allocating space to non-recursive function, as it is a
convenient, simple, fast and easy way to allocate storage for the
function only for the exact duration of that function execution.

Note that the stack policy no longer work as simply if functions can
have functions as result. Then frames may have to be allocated on a
heap (managed with a garbage collector) or occasionally transfered
from the stack to the heap.

The OS does not create an initial frame, whether on stack or anywhere
else. There must be a separation of responsibility. Some languages (at least older ones) do not even use frames, while others do use frames, but not organized as a stack. The role of the OS
is to allocate some space for the program to run, to place the data
to be passed to the program in some predetermined place in that space,
and then to pass control to the program code (if compiled), or to the
interpreter of the program (if interpreted)  with a reference to the
program as additional argument.

The code of the application program will then organize the allocated
space, initialize what has to be, possibly move data passed by the OS
in a more convenient location, etc, and then start with the code that
is specific to the application, what you call main method or main
program, thus creating its frame on the stack. This is usually done by a standard piece of code included by
the compiler with proper parameters.

In the case of interpreted code, the program that is actually called
is the interpreter, and the address of the program to be excuted is
passed to it as additional data. The interpreter will organize the
space, and reserve some for its own needs. Then it will start
interpreting your main method/program, thus creating the stack frame
for it.

But, as I said, there are many variants.
Does this answer your question? or did I miss a point?


Can I couple non-terminals in context-free grammars? If I had productions like so...

$S \rightarrow A1B$

$A \rightarrow \epsilon$

$A \rightarrow 0$

$B \rightarrow \epsilon$

$B \rightarrow 1$

If I only want strings $\{\epsilon1\epsilon, 011\}$, am I allowed to choose when both $A$ and $B$ become $\epsilon$? Or will I get resulting strings such as $\epsilon11$ and $01\epsilon$? (I know the $\epsilon$'s disappear, but I just left them in to avoid confusion.)

If I get the unwanted strings, then how would you force both $A$ and $B$ to be $\epsilon$ only when you need them to be, while still having $A$ and $B$ result in different terminals?

In your case, the desired language is finite, so you can just go

$\qquad\displaystyle S \to 1 \mid 011$.

If you had recursion, say

$\qquad\displaystyle S \to ASB \mid 1$

as starting rule, you can not force "matching" $A$ and $B$ to behave in sync.
There are more powerful types of grammars that can do that, but that's beyond
the power of context-free.


Whats an elegant way to tour a hypercube, in distance order: Consider the unit hypercube in $\mathbb{R}^n$ with all non-negative coordinates, and one point anchored at $0^n$.

I've been working on a problem where I want to generate the (exponentially many) corners of this cube (as a list of 0's and 1's) but I want to generate them in "distance" order. That is starting from a corner (0,0,0...) I will generate a sequence of points $p_0, p_1 ... $ with the property that the distance of each point $p_k$ from the origin $p_0$ is either constant or increasing. (Naturally this means (1,1,...) will be the very last point in the sequence) and you can visualize this as "snaking around the cube".

To be more explicit in $\mathbb{R}^3$, a sample list I could generate would be:

$$\begin{pmatrix} 0,0,0 \\\ 1,0,0 \\\ 0,1,0 \\\ 0,0,1 \\\ 1,1,0 \\\ 1,0,1 \\\ 1,1,0 \\\ 1,1,1  \end{pmatrix}  $$

This is not the ONLY solution. For any two entries $e_i$, $e_j$ if the number of "1"'s in the entries is equal, then a new list could be generated by "swapping" the entries in the original list.

My Work So Far:

A very inefficient solution:

I could generate the list of all binary numbers from $0$ to $2^{n} - 1$ with $n$ digits and then attempt to sort them by assigning an "magnitude" function that simply counts the number of "1's". This is very expensive especially given the exponential size of the data set and moreover cannot be done in a "batch" or online manner.

A slightly better solution:

For a positive integer $n$ and dimension $d$ define the following

Generator($n$, $d$)

if $n == 0$ then we return a vector of $d$ 0's.

If $n > 0$ then we consider the partially formed lists L_1 = $(1)$, L_2= $(0,1)$ , L_3 = $(0,0,1)$ ... $(0,0,0...1)$

Then we calculate Generator($n-1$, $d-r$) where r ranges from 1 to the length of L_max, and for each r we append to it the prefix list L_r.

Then calling Generator(0,n), Generator(1,n) ... Generator(n,n), as if it were one continuous list would yield our distance order tour of the cube.

For all $k=1, \dots, n$, you can easily generate all bit strings of length $n$ with exactly $k$ bits set.

The lexicographically smallest bit string has the $k$ ones in the $k$ least significant bits. If you interpret this string string as an integer, and it fits in a constant number of words, you can use bit tricks to find the next string in a constant number of operations.

See the section "Compute the lexicographically next bit permutation" here, and this answer for an explanation.


Why Linear bounded automata requires Nondeterministic Turing machine ? Why not Deterministic Turing machine? Going through the topic of LBA, i.e., Linear bounded automata. I found that LBA requires the NTM with some constraints on tape. I found the same information from different sources. But I did not get why all the sources mentioned that it needs a NTM. I am not getting why I need a NTM for LBA? We also know that any NTM can be converted to DTM. Therefore, I can take a DTM and put those tape constraints for building a LBA. I think that with a tape constraints DTM would be converted to LBA! Please make me correct and kindly tell me why I need an NTM for an LBA?

The conversion from nondeterministic Turing machine to deterministic Turing machines doesn't conserve space. The best known construction, known as Savitch's theorem, converts a nondeterministic Turing machine using space $s(n)$ to a deterministic one using space $O(s(n)^2)$, and this is suspected to be tight in general; see for example this question on cstheory.
Linear-bounded automata correspond to a class of grammars, context-sensitive grammars, in the following strong sense: a language can be described by a context-sensitive grammar iff it is accepted by some linear-bounded automaton. We only know how to prove this result if the linear-bounded automata are allowed to be nondeterministic. Indeed, assuming that $\mathsf{DSPACE}(n) \neq \mathsf{NSPACE}(n)$ (a conjecture which is much weaker than the tightness of Savitch's theorem), there exists a context-sensitive language which cannot be decided by a deterministic linear-bounded automaton.