If L = {xy | |x| = |y|, x=y} is not Context Free, then what about L = {xy | |x| = |y|, x!=y}? I know that, when x = y, then it's not Context Free. This is because, the first letter of y cannot be matched with first letter of x, which is at the bottom of the stack.
But, a link of Show that { xy ∣ |x| = |y|, x ≠ y } is context-free claims that, when x!=y, then it's Context Free. But, how can the letters of x and y be matched on stack? Say x=abbb y=bbbb. How can we say first letters don't match?

Not necessarily restricting ourselves to determinism, will it be even possible by the Context-free Language class (Non-deterministic & Deterministic Pushdown Automata), as a whole, to generate L = {xy | |x| = |y|, x!=y}?

There is a big difference between $\{ xy ∣ |x|  =  |y|, x = y \}$ and $\{ xy ∣ |x|  =  |y|, x \ne y \}$. In the first one, we need every symbol in $x$ to be the same as the corresponding symbol in $y$. For inequality, it suffices that at least one symbol in x be different from the corresponding symbol in $y$. The two cases are not symmetrical.

Checking that the first symbol is the same is not difficult. That can easily be achieved with a context-free grammar; we just need a word consisting of some symbol followed by a word with that same symbol in the centre:

$$\begin{align}S&\to a A\mid b B\\A&\to a \mid a A a \mid a A b \mid b A a \mid b A b\\B&\to b \mid a B a \mid a B b \mid b B a \mid b B b \\ \end{align}$$

That doesn't help us with checking that all symbols in the first half are the same as the corresponding symbols in the second half. But it does give us a way to check if some symbol in the first half is the same as the corresponding symbol in the second half:

$$\begin{align}S&\to A A\mid B B\\A&\to a \mid a A a \mid a A b \mid b A a \mid b A b\\B&\to b \mid a B a \mid a B b \mid b B a \mid b B b\\  \end{align}$$

And clearly it can easily be modified to check whether the corresponding symbols differ, giving the grammar in @Raphael's answer, linked in your question:

$$\begin{align}S&\to A B\mid B A\\A&\to a \mid a A a \mid a A b \mid b A a \mid b A b\\B&\to b \mid a B a \mid a B b \mid b B a \mid b B b\\  \end{align}$$


additive hash function Do functions with the following properties exists for x being arbitrary stream of bytes:

op(f(x1), f(x2))=f(x1+x2) and op(f(x1), f(x2))!=f(x2+x1) given that x1!=x2 where plus denotes concatenation and op is an easily computable operation
f(x) is fixed length of about 160-512 bytes
f does not need to be hard to revert, but should be useful at finding transmission errors or duplicates.

Could you provide any names/articles/pointers?

Try the CRC hash; it has this property.  You can also look at Merkle tree hashing.

See also https://crypto.stackexchange.com/q/24622/351, Which fingerprinting/hashing algorithms support compounding?, https://crypto.stackexchange.com/q/6497/351.


Minimum number of swaps in sorting sequence Given an array of N integer elements (not necessarily distinct), what is the minimum number of swaps (not necessarily adjacent) needed to sort the array?

I've been struggling with this problem for a few months now. I know that the elements are distinct, the answer is the number of cycles in the permutation obtained after normalizing the values and that if the swaps are adjacent bubble sort obtains the optimum number of swaps, but nothing about this one. This question asks the same, but the answers only consider distinct elements.

My approach to the problem is graph theoretical, considering a graph with a node for each element value, drawing an oriented edge from $a$ to $b$ whenever a value $a$ lies at a position where $b$ should lie in the sorted array ($a \neq b$, so no loops), the answer being the maximal (partition with most equivalence classes) partition of the edges into simple cycles (a generalization of the solution for arrays with distinct elements).

Does this problem have a known name? Any references? Any polynomial solution or complexity class ownership (P, NP, graph isomorphism equivalence etc)?

This problem is known as "sorting strings by interchanges". Amir et al [1] proved that the problem is NP-complete and admits a 1.5-approximation. They also obtain other results for transforming two strings into one another (which is not equivalent to the sorting problem) and using several other cost functions for each transformation.

[1]: Amihood Amir, Tzvika Hartman, Oren Kapah, Avivit Levy, Ely Porat:
On the Cost of Interchange Rearrangement in Strings. SIAM J. Comput. 39(4): 1444-1461 (2009) -- https://epubs.siam.org/doi/10.1137/080712969


Why is $FOLLOW$ not necessary for $LL(1)$ grammars with no $\epsilon$ transitions? I'm aware of how $FIRST$ and $FOLLOW$ sets are used to construct a parsing table for $LL(1)$ grammars.

However, I've encountered this statement from my notes:

  With $\epsilon$ productions in the grammar, we may have to look
  beyond the current non-terminal to what can come after it

In my opinion, this suggests that $FOLLOW$ is not necessary for $LL(1)$ grammars that have no $\epsilon$ transition. Am I wrong? And if I'm not, why is this the case?

Thanks

That's correct for $LL(1)$: if there are no $\epsilon$ productions, the $LL$ parser-generation algorithm will never consult $FOLLOW$, because it only does that if it finds $\epsilon$ in the $FIRST$ set for the first non-terminal in the right-hand side of a production. (So it might not need the $FOLLOW$ sets even if there are some $\epsilon$ productions, provided that none of those productions occur at the beginning of a right-hand side.)

The observation doesn't generalise well to other values of $k$. You'll need $FOLLOW_k(\alpha)$ if any production can derive a string whose length is less than $k$.


Slicing clusters of non-black pixels from an image into separate images The backstory

I have spectrograms of certain repeating sounds. The background of the spectrograms are black and could easily be made transparent if that would help. The sounds are easily distinct from the background. As shown below, each sound is a series of connected pixels of various colors.

What I want to do

I would like to separate each of the sounds into separate images or slices. That is, from the above example I would like to isolate the sounds into something like the following example.

If you are familiar with Unity 3D, they do something similar with their "Sprite Slicer" that creates a rectangle around objects on a transparent image.

My attempt of an algorithm

Select non-black pixel
For each neighboring pixel
  If pixel is black
    Try each non-visited neighboring pixel again, traveling a maximum of three pixels away ( a sort of threshold )
  If pixel is non-black
    Add to a list of significant pixels and travel to neighboring pixels
Mark selected pixels as visited and select a new non-black pixel

This would result in a list of lists containing pixels where each list is the extracted sound or cluster of pixels that could be compiled into images.

My concerns

I know this has been done before and is called something, but for the life of me I cannot find the words to describe it (hence the poor title).

My algorithm feels non-standard and potentially slow and poorly written. It should work, but it's not it.

Questions

What is this called, how can I find more about it?

How do I succeed in extracting the sub-images as shown by the example?

It seems that you're just trying to find the connected components of a graph. In this case, the vertices are the non-black pixels and there's an edge between two pixels if they're at distance at most $d$, for some appropriate choice of $d$ and some appropriate metric (Euclidean distance, Manhattan distance, whatever works best).

(Note that, in terms of implementation, you don't need to construct an explicit data structure for the graph; you can calculate whether there's an edge between any two vertices whenever you need to.)


Is my interpretation correct? I am trying to implement the algorithm described in the paper A quantum-inspired classical algorithm for
recommendation systems.

This is the algorithm:

These are the necessary definitions for mathematical notations used in the algorithm to understand the algorithm.

  The distribution is defined as, for a nonzero vector $x \in R^n$, we
  denote by  $\mathrm{D}_x$ the distribution over [1, ..., n] whose
  probability density function is $$\mathrm{D}_x(i) =\frac{x^{2}_{i}}{\lVert{x}\rVert ^2} $$.

  If a matrix $A \in R^{m \times n}$, and let $A_i$  refer to the $i$th
  row of $A$. Let $\tilde{A} \in R^m$ be a vector whose $i$th entry is
  $\lVert A_i \rVert$.

  $[p] denotes [1, 2, ... p]$

  $s \sim _u [p]$ denotes pulling an $s$ uniformly at random.

I am having a problem understanding the Let the resulting p x p submatrix ... step of the algorithm. According to the algorithm the rows of the submatrix are sampled from a distribution $\mathrm{D}_{\tilde{A}}$ and the columns of the submatrix are sampled from a distribution $\mathcal{F}$.

I can't understand how can we form a submatrix with both rows and
colums given ? I think we just need either rows or columns. Can someone clarify
this to me, please ?
And I also don't understand the definition of $\mathcal{F}$.
According to definition of $\mathcal{D}_x$, $x$ has to be a vector
then how can we choose a column from $D_ \tilde{A_{i_s}}$.

Given a matrix $A$, you can form another matrix by taking only some of the rows and columns of $A$, possibly repeated. For example, suppose that $A$ is the following matrix:
$$
\begin{bmatrix}
1 & 2 & 3 \\
4 & 5 & 6 \\
7 & 8 & 9
\end{bmatrix}
$$
If we take only rows 1,2 and columns 1,3, then we get the matrix
$$
\begin{bmatrix}
1 & 3 \\
4 & 6
\end{bmatrix}
$$

For your second question, $\mathcal{D}_x$ is a distribution on column indices. You don't choose a column directly – you only choose an index. This corresponds to 1,3 in the example above.


Lines intersections with a point in 1D I have an array of lines in 1D represented by coordination and weight, it can be only positive weight. I want to find all the lines that intersect a point in a given range.

Is there any efficient way of doing it?

If you store all of the intervals in a segment tree, then the operation "find all intervals that contain the point $x$" is known as a stabbing query.  Building a segment tree from $n$ intervals takes $O(n \lg n)$ time, but once it is built, you can answer a stabbing query in $O(\lg n + k)$ time, where $k$ is the number of intervals that intersect the point $x$ (i.e., the length of the output of the operation).

In comparison, a linear scan (as described in G. Bach's answer) requires no preprocessing but takes $O(n)$ time to answer each stabbing query.  Thus, if you plan to make many stabbing queries on the same set of intervals, it may be faster to build a segment tree in advance, as each stabbing query can then be answered much faster.

See also interval trees, which have similar properties.


why are deterministic PDAs not closed under concatenation? I can understand that they are not closed under concatenation because without non determinism, PDA cannot decide whether to loop in the first PDA or jump to the next one.
But can someone prove this with an example. Also prove that the resulting language cannot be accepted by DPDA

Pick the languages:

$L_1 = \{a^ib^jc^k | i \neq j \}$ and $L_2 = \{a^ib^jc^k | j \neq k\}$; both are DCFL and $L_3 = 0L_1 \cup L_2$ is DCFL, too.

$L_0 = 0^*$ is DCFL (regular)

But $L_{conc} = L_0 \cdot L_3 = 0^* L_3$ is not DCFL.

Proof: Suppose that $L_{conc}$ (which is the concatenation of two DCFLs) is DCFL.

If we intersect $L_{conc}$ with the regular language $0a^*b^*c^*$, we should get a DCFL language:

$L_{conc} \cap \{0a^*b^*c^*\}$ = $0L_1 \cup 0L_2$. suppose $0L_1 \cup 0L_2$ is a DCFL, so $L_1 \cup L_2$ should be a DCFL, too but:

$L_1 \cup L_2 = \overline{\overline{L_1} \cap \overline{L_2}} = \overline{\{a^ib^ic^i\}}$ which is not DCFL $\Rightarrow$ contradiction.


Are there repositories of automatically generated (spam) webpages? I'm interested to see if I can use machine learning/network analysis methods to automatically detect automatically generated (spam) webpages.  I'm particularly interested in webpages that look structurally like a non-spam website, but on closer inspection are total rubbish.

If I want to test a method, I'd need some way of accessing (or generating) these webpages.

  Question: Where can I access automatically generated (spam) webpages?

Here's a sample of the kind of webpage I'm thinking about:

Image source

Question: Where can I access automatically generated (spam) webpages?

You could use:

a parody generator program.

They're usually based on Markov chains (e.g. SubredditSimulator) or context-free grammars (e.g. the well known SCIGen... according to the authors "with Markov chains you might get something syntactically correct, but it is likely to be boring"!).

Also a cut-up technique could be enough.
a (web spam) dataset. The WEBSPAM-UK2007 collection is one of the largest and cleanest (and it's open). A description of the dataset can be found in A Reference Collection for Web Spam (the paper describes WEBSPAM-UK2006 but it's still valid).

You should check if it's too broad: the collections includes many different web spam aspects as possible (pages that are only advertising, pages with unrelated links, pages that automatically redirect...) and you seems only interested in pages that contain machine generated content.
the spam messages in the email: email spammers often include URLs in their spam messages. Following those links you can store the HTML content. You should add a few heuristics to identify some false positives (e.g. exclude Alexa's Top 500 list and use SiteAdvisor's rating system to compile a whitelist).

This is the method used to create another well known dataset: Webb Spam Corpus (the original corpus was collected by Steve Webb). Further details are contained in Introducing the Webb Spam Corpus: Using Email Spam to Identify Web Spam Automatically (Steve Webb, Jamesa Caverlee, Calton Pu).


Efficiently locating the maximum value in interval over large amounts of data points I have a set of $n$ two-dimensional data points $(x_i,y_i)$.  I want to efficiently answer the following query: Given an arbitrary interval of $x$-values, find the highest and lowest points within that interval.  In other words, for this query we are given an interval $[\ell,u]$, and we want to find the point $(x_i,y_i)$ such that $x_i \in [\ell,u]$ and $y_i$ is maximal (or minimal).

What data structure would be appropriate for this task?  I'm interested in both the static case (where the set of points doesn't change) and the dynamic case (where we also want to be able to insert and/or delete points from the set).

This can be solved with a balanced binary tree.  Each such query can be answered in $O(\lg n)$ time.

Build a balanced binary tree, where each leaf holds a point, and the tree is keyed on the $x$-coordinate of the points (so the leaves contain the points, sorted from left to right).  Augment the tree, so that in each node $t$ of the tree, you store a pointer to the highest and lowest of all the points within the subtree rooted at $t$.

Now we are given an interval $[\ell,u]$, and asked for the highest point whose $x$-coordinate is within that interval.  It turns out that any such interval can be expressed as a union of $O(\lg n)$ subtree.  In other words, you can find nodes $t_1,t_2,\dots,t_k$ such that (1) every leaf that is a descendant of some $t_i$ has an $x$-coordinate in the interval $[\ell,u]$, (2) every leaf whose $x$-coordinate is in the interval $[\ell,u]$ is the descendant of one of these $t_i$'s, and (3) $k = O(\lg n)$.  Recall that the augmentation tells you what is the highest leaf under each $t_i$.  So, to answer the query, take the highest of all those: that will be the highest leaf whose $x$-coordinate is within $[\ell,u]$.  Since we only need to examine $O(\lg n)$ nodes, the running time is $O(\lg n)$.

How do you find those $k$ nodes?  That's described here: Delete a consecutive range of leaves from a binary tree.  You can verify that you can find those $k$ nodes explicitly in $O(\lg n)$ time, given $\ell$ and $u$.

Conveniently, this data structure works both for the static case (where the set of points doesn't change) as well as the dynamic case (where we want to insert and delete points).  You can insert and delete points in $O(\lg n)$ time: in particular, you can update the augmented information within those time bounds (you just have to touch each node on the path to the root from the inserted/deleted node).


topological sort equivalence For a given acyclic graph $G$, a topological sort is an ordering $v_1, \dots, v_n$ of the vertices such that the arrows in the graph are all directed forward under that ordering.

Question: can all topological orders of a graph $G$ be obtained from a single ordering by iteratively swapping two vertices that are not connected by an edge?

Motivation. In a certain context I am trying to prove that all topological sorts of an acyclic graph are in fact "equivalent". I want to do this by comparing $v_1, \dots, v, v', \dots v_n$ and $v_1, \dots, v', v, \dots v_n$ where there is no edge between $v,v'$.

Let $\tau_1: x_1, x_2, \dots, x_n$ and $\tau_2: y_1, y_2, \dots, y_n$ be two topological orderings of the vertices of graph $G$. Our aim is to show that $\tau_1$ can be transformed into $\tau_2$ by a sequence of swaps, each changing the position of two vertices in the sequence, not connected to each other by an edge of $G$.

Starting from the beginning compare the vertices $x_i$ and $y_i$ and select the first pair that differs. For notational convenience we assume $x_1 \neq y_1$. As $y_1$ must occurs in $\tau_1$ we can find $x_j=y_1$, $j>1$. Thus vertices $x_1, \dots, x_{j-1}$ are all before $x_j=y_1$ in ordering $\tau_1$, but all after $y_1=x_j$ in ordering $\tau_2$. This implies there is no edge in $G$ (in either direction) from $x_j$ to each of $x_1, \dots, x_{j-1}$. Thus we can "legally" swap $x_j$ with each of $x_1, \dots, x_{j-1}$ to get it to the first position. We obtain $\tau'_1: x_j, x_1, \dots, x_{j-1}, x_{j+1}, \dots, x_n$ which has the same first element as $\tau_2$.

Iterate, or invoke induction.

(Thanks for your suggestions and support.)


Calculating Size of parts of tree cut by an edge in a tree Suppose that there are $n$ nodes, and that edge $e$ of weight $w_e$ cuts the tree into parts of size $k_e,n-k_e$. Then the average distance is
$$
 \sum_e w_e k_e (n-k_e).
$$
For example :
n=6,k=6 list=[1,2,3,4,5,6]

                    Node--------> 1
                                   \(1)<-----------Weight
                                    \
                                     3
                                (3) / \(2)
                                   /   \
                                  4     2
                             (4) / \ (5)
                                /   \
                               5     6

in this case we get
$$
\ (1 \cdot 1 \cdot 5 + 2 \cdot 1 \cdot 5 + 3 \cdot 3 \cdot 3 + 4 \cdot 1 \cdot 5 + 5 \cdot 1 \cdot 5) ={87}
$$

I'm storing the tree using adjacency lists.

1 approach might be to calculate size of elements of the list of the vertex connected by that edge recursively. For eg here if I cut $3-4$ I go the list of $4$ that contains $5,6$ then for every element in $4$ I go their list and calculate size of them and the vertex in it i.e go to list $5$ and $6$ and calculate size of their list. But I think this might be wrong or too long.

Now how do I find out the value of $k_e$ in the tree in a better and fast way?

You can use dynamic programming in its version for trees. Choose a root arbitrarily, and calculate recursively the number of vertices in the subtree rooted at each node. This should give you enough information to calculate $k_e$ for each edge $e$. The total running time should be $O(n)$.

I'm leaving the rest of the details for you to ponder.


Running time question If I have two kinds of LinkedList $A$ and $B$.

$A$ is a move to front one which means:
>>> lst1 = 1, 2, 3, 4, 5, 6, 7, 8, 9
>>> lst1.contain(7)
True
>>> lst1.to_list
7, 1, 2, 3, 4, 5, 6, 8, 9
$B$ is a swap list, which means:
>>> lst2 = 1, 2, 3, 4, 5, 6, 7, 8, 9
>>> lst2.contain(7)
True
>>> lst2.to_list
1, 2, 3, 4, 5, 7, 6, 8, 9

I want to find a searching sequence such that the running time of $B$ is faster than $A$. I mean the Theta of them would be different. The length of lst1 and lst2 are both $n$. We search $m$ times and can search different elements for different times.

The move-to-front heuristic is 4-competitive in the model where swapping adjacent elements costs one unit. This means that if the optimal strategy has cost $N$, then move-to-front has cost at most $4N$. In particular, if a swap list has cost $N$ on some searching sequence, then move-to-front will have cost at most $4N$.
See for example MIT OpenCourseWare or Princeton Slides.


Can an independent set (of vertices) be a vertex cover as well? I wanted to clarify if this is possible, so I thought about a possible vertex cover that can also serve as an independent set:

So, to clarify, am I right to say that the nodes in red are both (i) a vertex cover, and (ii) an independent set?

Edit: I was confused by the theorem that states "If G = (V,E) is a graph, then S is an independent set <-> V-S is a vertex cover." So I thought that a vertex cover and an independent set are mutually exclusive.

If something satisfies the definition of $X$ and the definition of $Y$, then it is both an $X$ and a $Y$.

Although it's true that, whenever $S$ is independent, $V\setminus S$ is a vertex cover, it's possible for both $S$ and $V\setminus S$ to be independent: this happens when $S$ is one side of a bipartite graph, as is the case in the example in the question.


What is the difference between a microoperation, microinstruction and control word? I've seen a few lectures interchangeably use the two words (microinstruction and microoperation). I've found a source that explains the difference between a microoperation and microinstruction, but I have not been able to associate the two to a control word. Books I have referred to have provided definitions of each, but no explanation about the relation amongst the three.

Edit: Could I also get a few examples to help differentiate the three ?

In traditional horizontal microcode,

a micro-operation is the most basic operation achievable by a processor;
a micro-instruction is a set of micro-operations which are executable simultaneously;
control words are the bit patterns used to encode the micro-instructions.

Micro-operation is also used in current pipelined processors where an instruction is decomposed in a few (included zero) micro-operations or even a few instructions merged in one micro-operation which are then processed independently.

Control word is a far more general term and can refer to any bit patterns used to control any circuit.  Its use for the encoding of micro-instructions come from the fact that horizontal micro-code is usually lightly encoded if at all, and thus fields in the encoding control directly parts of the processor.  From there it went to be used for the encoding of any kind of micro-instructions.  BTW, the area where the micro-program is stored is often called the control store.


Question about bigram model I am trying to build a bigram letter model.

I obtain a sequence of words in a form of ['hello','I','am','Johnny'].

Firstly, I lower all the words to obtain : ['hello','i','am','johnny'].

I am capable of building a bigram letter model, but I have read somewhere that you should provide some kind of empty strings / padding to the model.

Does anybody know why do you have to provide padding to the input data to build a proper language model? And how to use padding on this sample input to build letter model?

I was thinking about making a space in front of every word, but I am not convinced that this is the right solution - other options that I am considering are adding padding at the end of every sentence or after each sequence of 2 characters as this is a bigram letter model.

The padding is there since the distribution of letters at the beginning and end of words is very different from their distribution inside words. To capture that, separate words with spaces and add trailing spaces on both sides: ' hello i am johnny '.


Efficiently computing minimal elements over partially ordered sets I have a list of sets that I would like to sort into a partial order based on the subset relation.

In fact, I do not require the complete ordering, only the minimal elements.

If I am not mistaken, each minimal elements should define one separate component  of the respective graph - and this component should be a meet-semilattice.

What would be the most convenient space and time efficient way to solve this problem? Perhaps there is a way that does not require to build the entire graph? Perhaps there is a known algorithm under a better terminology than what I have naively described above?

I am aware that the time and space requirements are underspecified above, but I would be happy about any suggestions, whether they are proven to be optimal or not...

Background: I am currently building an entire graph database that holds all  the edges between the sets and then look for the nodes that have no generalizations, but this is quite complicated, slow and requires a lot of (disk) space. The list mentioned above contains roughly 100 million sets.

One approach is to sort the sets by increasing size, then repeatedly perform the following: take the first set in the list, output it, and remove from the list all supersets of it.  This will output all of the minimal sets.  The running time is $O(nk)$ set comparisons plus $O(n \log n)$ steps for sorting, where $n$ is the number of sets you have and $k$ is the number of minimal elements.  Or, to put it another way, if each set contains $m$ elements, the running time will be approximately $O(n(k+\log n)m)$ basic steps.

Why sort by size?  This is an optimization.  The smallest set is guaranteed to be minimal (there is none of smaller cardinality in the list, so none of its subsets can be in the list), so size is a useful trick to identify a set that must surely be minimal.

Without sorting by size, the worst-case running time is likely to end up as $O(n^2)$ set comparisons (or $O(n^2 m)$ basic steps), which is worse when $k \ll n$.

Here is an optimized version of that algorithm.  Let $M$ be a data structure that stores a set of sets, as a trie: for instance, the set $\{1,3,6,7\}$ corresponds to the word $1367$ and is stored in the trie accordingly.  Initially, $M$ is empty.  Repeat the following: take the next set $S$ from the list; check whether any set in $M$ is a subset of $S$; if not, insert $S$ into $M$; finally delete $S$ from the list (or advance your pointer to the next element in the list).  The "check..." operation can be performed fairly efficiently using a recursive traversal of the trie.  At the end, once you've gone through the entire list, output $M$.

The worst-case running time of the optimized algorithm remains the same.  In practice the running time might be improved significantly, perhaps to as fast as $O(nm)$ basic steps in some cases if you are lucky (but don't count on it).  You can try both and see which works better in practice on the kind of workloads you are dealing with.


Is it possible to give a guarantee about the accuracy of the local time? Assuming there is no attack/bug and I use NTP: Are there any formal guarantees about the accuracy of the local time? Can there be any over the network?

Even if the communication is going directly between the time server (stratum-1) and the client, I have no idea if the devices / protocols on OSI layer 1-4 have time guarantees.

Maybe something like the following can be guaranteed: With a probability of 99% the currently set local time is off by less than 20ms.

(I've added the "cryptography" tag as certificates are also only valid for a given time - in this case it would be important to have a guarantee even with a possible attacker)

What I found

  Clock synchronization at the 10 millisecond level over long distance wide-area networks (WANs) (2000 km), and at the 1 millisecond level for local-area networks (LANs), is routinely achieved.

Source: Cisco, Network Time Protocol: Best Practices White Paper. 2008.

No.  No guarantee is possible.  The network latency could have arbitrarily high variance, in which case NTP might be arbitrarily inaccurate.


Why precondition strengtening is sound in Hoare logic I have problem with understanding why precondition strengthening is sound rule in Hoare logic. The rule is:

$$
{P \implies Q, \{Q\} C \{X\} } \over {\{P\} C \{X\}}
$$

I really do not understand why precondition in consequence goes in reverse direction that implication works (modus ponens).

I can understand why post-condition weakening works because it follows modus ponens rule but I am no able to understand precondition strengthening.

The triple $\{Q\}C\{X\}$ states that if $Q$ holds, then after executing $C$, the condition $X$ holds. Now suppose that $\{Q\}C\{X\}$ and that $P \Longrightarrow Q$. We will prove that $\{P\}C\{X\}$. Indeed, suppose that $P$ holds. Since $P \Longrightarrow Q$, also $Q$ holds. Hence if we execute $C$, then $X$ will hold. Altogether, we see that $\{P\}C\{X\}$ is valid.

An example can also be helpful. If we know that $\{x=1\}x\gets x+1\{x=2\}$ then we certainly know that $\{x=y=1\}x\gets x+1\{x=2\}$.


Ideas on how to approach the construction of a probability-heavy algorithm Definitions

Assume we have a Shopping List $L$ which is a list of pairs of Items and Quantities: $L = [(i_1, Q_1), (i_2, Q_2), (i_3, Q_3) ...$

We also have a Stock List $S$ which is a list of pairs of Containers and Prices: $S = [(C_1, p_1),(C_2, p_2), (C_3,p_3)...]$

Each container is a list of 3-tuples of Items, Quantities, and Probabilities: $C_n = \left[\left(t_1,q_1,\frac{a_1}{b_1}\right), \left(t_2,q_2,\frac{a_2}{b_2}\right), \left(t_3,q_3,\frac{a_3}{b_3}\right)...\right]$

Purchasing a container for a given price gives you a chance of getting each item within it. The chance is equal to each item's probability. The probabilities are independent of each other (two items with a probability of 1/2 are treated as two coin flips, it isn't "one or the other"), and their quantities are absolute. If we had $C_1 = \left[\right(x, 2, \frac{1}{2}\left)\right]$, then there is a one-in-two chance of getting two $x$s, and no chance of getting only a single $x$.

The Goal

I'm trying to come up with some algorithm which has the ultimate goal of satisfying a given shopping list from some stock list. Due to the random nature of the problem, it is impossible to construct a definite chain of purchases to make. Thus, I was thinking that foo(L, S) should return the best next purchase -- the container to buy which satisfies the most items in the shopping list for the lowest price. Purchasing this container can affect the shopping list in a variety of ways, so upon purchasing, the list will be run through the algorithm again and again until it is empty.

My Attempts

If I could construct a function which outputs some "instantaneous value" of each container, I could then calculate and sort each container by this value and purchase the one highest-valued one.

This value of a container would be its benefit minus its cost. Calculating the cost of containers which contain only one needed item is simple enough, but I'm stumped on containers with multiple items. Consider this example:

$L = [(x, 1), (y, 1)]$

$S = \left[\\
\left(\left[\left(x, 1, \frac{1}{2}\right)\right], 10\right),\\
\left(\left[\left(y, 1, \frac{1}{2}\right)\right], 10\right),\\
\left(\left[\left(x, 1, \frac{1}{3}\right),\left(y, 1, \frac{1}{3}\right)\right], 20\right)\\
\right]$

(The first container costs \$10 and has a 1/2 chance of giving an $x$. The second container costs \$10 and has a 1/2 chance of giving a $y$. The third container costs \$20 and has a 1/3 chance of giving an $x$, and a 1/3 chance of giving a $y$.)

The cost of getting an $x$ from the first container is \$20. This would satisfy one out of two of our list's requested items. If our strategy for satisfying the list was to brute-force the first container, then the second, the total cost of the list would be \$40.

What gives me trouble is that third choice. There is a 1/9 chance of spending only \$20 and getting both of our $x$ and $y$ in one move. There is a 4/9 chance of spending \$20 and getting either our $x$ or $y$ -- we could then get the remaining one for \$20 and be done for \$40. Finally, there is another 4/9 chance of getting nothing.

I suspect that the best path in this case is to buy the third container until at least either an $x$ or $y$ is obtained, then buy the remaining one from the first or second container. (Edit: A simulation shows that solely buying containers 1 and 2 leads to an average cost of \$40 to satisfy the list, as expected, but buying the third container then one or two leads to an average cost of \$52 to satisfy the list. Besides simulating, I'm unsure of how to derive that 52)

Any ideas on how to approach this?

One plausible approach would be to use integer linear programming.  The following won't be optimal, but it might be decent.

We could try to find quantities $x_1,x_2,\dots$ for the containers, so that if we buy that many containers, the expected number of each item is at least the desired quantity.  This leads to an integer linear program, with one inequality per item

$$\sum_i x_i q_{i,j} p'_{i,j} \ge Q_j$$

where $q_{i,j}$ is the number of item $j$ in container $i$, and $p'_{i,j}$ is the corresponding probability.  Then, we want to minimize $\sum_i x_i p_i$, the total price of these containers, where $p_i$ is the price of the $i$th container.  You could use an off-the-shelf ILP solver to solve for the $x_i$'s, or as a heuristic, use a linear programming solver and ignore that the $x_i$'s need to be integers.

Then, you could randomly sample a container, with container $i$ sampled with weight proportional to $x_i$.  This is a heuristic, but it might help identify which container you most want to buy, so it might work well enough in practice.

You shouldn't expect any efficient algorithm that gives the optimal solution; this problem is NP-hard, by reduction from the knapsack problem.


How do I prove that SAT in coNP implies NP=coNP? Is it true that if SAT is in coNP then its also coNP-complete (because it is NP-complete)?

If SAT is in coNP then since coSAT is coNP-complete, SAT can be reduced to coSAT in polytime. The same reduction also reduces coSAT to SAT. Since coSAT is coNP-complete, every problem in coNP can be reduced in polytime to coSAT, and so to SAT. This shows that SAT is coNP-complete.


Are regular expressions a*a and aa* equivalent? Let $\Sigma = \{a, b\}$ an alphabet. Are the regular expressions $a^*a$ and $aa^*$ over $\Sigma$ equivalent? Even though concatenation is not commutative, in this case it seems like the statement is correct, but I am not sure.

Yes, they're equivalent. Informally, it's clear that "any number of $a$s followed by one more" is the same thing as "a $a$ followed by any number more." However, there was a request in the comments for something more formal so here goes...

If $R$ and $S$ are regular expressions, then the concatenation $RS$ matches any string $w=w_1\dots w_\ell$ (where the $w_i$ are the individual characters) such that, for some $d$, $w_1\dots w_d$ matches $R$ and $w_{d+1}\dots w_\ell$ matches $S$. Here, $d=0$ and $d=\ell$ mean that we've split $w$ into $\varepsilon$ and $w$ and vice-versa.

So, consider $R=a^*$ and $S=a$. Then $RS$ matches any string $w=w_1\dots w_\ell$ such that, for some $d$, $w_1\dots w_d$ matches $a^*$ and $w_{d+1}\dots w_\ell$ matches $a$. We must have $d=\ell-1$ and $w_\ell=a$ because only the string $a$ matches $a$, and it has length $1$.  And we must have $w_1=\dots=w_{\ell-1}=a$ because that is the only length-$(\ell-1)$ string that matches $a^*$. So $w=a^{\ell}$ for some $\ell\geq 1$.

Considering $R=a$ and $S=a^*$, an almost identical argument shows that any string that matches $aa^*$ must also be $a^{\ell}$ for some $\ell\geq 1$, so the two regular expressions do indeed match the same language.

At an intermediate level of formality, you can argue that $a^*$ matches any string $a^\ell$ for $\ell\geq 0$, and $a$ matches the single string $a=a^1$.  So $a^*a$ matches any string $a^\ell a$ for $\ell\geq 0$, i.e., any string $a^{\ell+1}$ for $\ell\geq 0$, i.e., any string $a^\ell$ for $\ell>0$.  Similarly, $aa^*$ matches any string $aa^\ell=a^{1+\ell}$ for $\ell\geq 0$, i.e., $a^\ell$ for $\ell>0$.


How solve this recurrence: T(n) = 2t(n-1) - t(n-2) +5n +7 I am trying to solve the recurrence: T(n) = 2t(n-1) - t(n-2) +5n +7 but without success.

And from here I don't know how to continue?

According to your recurrence equation  2t(n-1) futher breakdown like 2[2t((n-1)-1)+t((n-1)-2)+5(n-1)+7] and for solution of this equation explore
recurrence equation solution


Coloring a graph with odd number of vertices with $k$ (which is close to $\Delta$) colors in linear time We have an undirected simple connected graph with odd number of vertices. We also know the number $k$ which is actually the closest odd number greater than or equal to $\Delta$. (So if $\Delta$ is even, $k = \Delta +1$ else $k=\Delta$.) i.e $k$ is the least odd number that is greater than or equal to degrees of all vertices.

We want to find a linear time algorithm that colors the graph with $k$ colors.

I am very new to graph coloring algorithms. I know that a greedy algorithm is actually linear time and can color the graph with $\Delta +1$. But I can't guarantee I can color it with $k= \Delta$ when $\Delta$ is odd.
Also, we probably should use all the information the question gives us. i.e using odd number of vertices somehow, but greedy algorithm don't use this extra information.

How can I solve this?

Brooks' theorem states that every connected graph $G$ with maximum degree $\Delta$ can be colored (in linear time) using at most $\Delta + 1$ colors. In fact, the graphs that require $\Delta + 1$ colors are precisely complete graphs and odd cycles.

You state that we have a connected graph $G$ with an odd number of vertices and we want to color $G$ with $k$ colors, where $k = \Delta + 1$ when $\Delta$ is even and $k = \Delta$ otherwise. Let's break this down into cases:

$G$ is complete (i.e., $G$ is $K_n$ for $n = 3,5,7,\ldots$). By definition, $\Delta = n-1$ and since $n$ is odd, we have that $\Delta$ is even. Thus, we can color $G$ with $k = \Delta+1$ colors.
$G$ is a cycle (i.e., $G$ is $C_n$ for $n = 3,5,7,\ldots$). Clearly, for any non-trivial cycle we have that $\Delta = 2$ which is even. Again, we can color $G$ with $k = \Delta+1$ colors.
$G$ is not complete nor a cycle. By Brooks' theorem, we have that $\chi(G) \leq \Delta \leq k$, so we are done.


Run-time of Hungarian algorithm - matrix formulation There are many different explanations of the Hungarian algorithm. My favorite explanation is the one based on matrices, for example here, since it is very intuitive and easy to carry out in a spreadsheet.

The problem is, I could not understand the argument of why this algorithm, in its matrix formalism, is polynomial in $n$. In particular, in the above presentation, I got stuck trying to prove that Step 5 (page 13) is executed $O(n)$ times, or more generally, $O(poly(n))$ times.

In step 5, we subtract a number $x$ from each uncovered row, and then add the same $x$ to each covered column. Since in this step, the size of the covering is less than $n$, there are more uncovered rows than covered columns, so we subtract $x$ more times than we add $x$. Hence, the sum of all elements in the matrix strictly decreases each time. Since the sum always remains positive, the algorithm must eventually end.

However, I could not understand why it must end after $O(poly(n))$ iterations.

What am I missing in the above argument?


Space complexity of boolean circuit evaluation I am given a boolean circuit of depth $D \ge \log n$ where $n$ is the input size.
Given an input, I need to find an algorithm that evaluates the circuit in space $O(D)$.

Now, assuming the fan in of each vertex is at most 2, I can set 2 bits for each vertex, one for the value of the vertex, and the other for which of his sons I am currently evaluating. Where I am stuck is that I am not given any information on the fan out of each vertex, So I can't just set a value to know which parent to go back to when I finish evaluating a sub circuit.

I would like some help understanding the catch here.

thanks.

This general question is captured by the concept of graph pebbling. Orient the edges of the circuit so that they point away from the leaves and toward the root. A pebbling of the graph is a series of moves, in the course of which pebbles are added to and removed from vertices (at most one pebble per vertex!), according to the following rules:

A pebble can always be removed.
A node $v$ can be pebbled (we can add a pebble to it) if all nodes $w$ such that there is an edge $w \to v$ are pebbled.

The goal is to pebble the root, and what we want to minimize is the maximum number of pebbles on the board. This minimum is called the pebbling number of the circuit.

If a circuit has pebbling number $p$, then it can be evaluated using roughly $p$ bits of memory. The idea is that pebbling a node corresponds to computing the its value, which is possible since all of its children are pebbled as well.

All of the above concerns the case in which the circuit is given ahead of time, and the goal is to construct a strategy to evaluate it on an unknown input. However, the same general approach can also be used to solve your problem, using the fact that the pebbling number of the complete binary tree of depth $D$ is $O(D)$. For more on pebbling, see Nordström's survey.

Finally, let me mention that the circuit evaluation problem is $\mathsf{P}$-complete. This means that assuming $\mathsf{L} \neq \mathsf{P}$, it is not possible to evaluate arbitrary circuit in logarithmic space. In contrast, the formula evaluation problem is in $\mathsf{ALOGTIME}$ (i.e., uniform $\mathsf{NC^1}$), and so in $\mathsf{L}$. This is due to important work of Buss.


Prove $\forall c \in \mathbb{N} \, \exists x,y \in \Sigma^* \, [K(xy) > K(x) + K(y) + c]$ I am trying to prove a theorem (title) given in a starred problem in Sipser's book. I have absolutely no idea how I would go about showing it, and after trying a few different approaches came here looking for a hint. I don't want a full answer, but would really appreciate a few words to point me in the right direction. This is not a homework exercise.

A paper of Day gives the following hint: Show that for every $c$, every long enough string $z$ contains a prefix $x$ with $K(x) < |x| - c$.

He also gives a hint to the hint: Use the fact that a machine for computing $x$ can use both the given program $\pi$ and its length $|\pi|$, which gives it an extra $\log|\pi|$ bits of information.


If L is regular, so is L2 (proof using closure properties) I've got a question that asks me to explain how if a language L is regular, then so is:

$M=\{s \in \{a, b\}^* |\ \exists\ t \in L\ such\ that\ |s|_a = |t|_a\}$

I believe I would have to get M into the form: $M=\{a^i |\ i\geq0\}$ since we know that any equation of that form is regular, but I'm not quite sure how to go about that using closure properties.

Here are several possible ways of proving that if $L$ is regular then so is $M$.

Method 1

Show first that the language
$K = \{ a^r : |s|_a=r \text{ for some } s \in M \}$.
You can obtain $K$ from $L$ by deleting all letters other than $a$. Then show that $M$ is regular by "undeleting" all letters other than $a$.

Method 2

Construct an NFA for $M$ directly, given an NFA for $L$. At each step, the new NFA accepts non-$a$ letters gratuitously, both in the input and in its simulation of the NFA for $L$. It also reads $a$, but then must also simulate an $a$ transition on the NFA for $L$. Finally, it accepts whenever it can get the NFA for $L$ to be at an accepting state.

Method 3

Parikh's theorem shows that $K$ (defined in Method 1) is eventually periodic. That is, for some integers $m,p$ and sets $A \subseteq \{0,\ldots,m\}$, $B \subseteq \{0,\ldots,r-1\}$ we have
$$
K = \{ a^i : i \in A \} \cup \{ a^{m+rj+i} : j \geq 0, i \in B \}.
$$
Given this, we can construct a DFA for $M$ directly (exercise).


What is the best algorithm to match a student's schedule with a tutor's schedule? I am building an application (RoR framework) that can help to match a tutor and a student based on their subjects, budgets, locations and freetime. I have done the first three parts(subjects, budgets, locations). Now, I am getting stuck at the most difficult one which is freetime matching.

The student's sample freetime:

Monday: 7AM-8:30AM
Wednesday: 6AM-8AM
Friday: 9AM-10:30AM

Now I want to match this student with a list of tutors who have the freetime that can match with the student's freetime. In addition, each session between a student and a tutor must be 90 minutes.

For example, the following is the tutor's freetime:

Monday: 6AM-9AM => matches because both the student and tutor can start their session at 7AM, and when the session ends at 8:30AM, it is still in the range of the student's freetime and tutor's freetime.
Tuesday: 7AM-10AM => doesn't match, of course.
Wednesday: 7AM-9AM => doesn't match because both of them can start their session at 7AM, but when the session ends 8:30AM, the student's time is already over.
Friday: 10AM-11:30AM => matches, like the case in Monday.
=> Conclusion: this tutor doesn't match with the student since he just matches 2 out of 3 days with the student (Monday and Friday)

I tried to use Hash data structure to solve the problem.

student_freetime = { monday: { start_time: 7, end_time: 8.5 }, wednesday: { start_time: 6, end_time: 8 }, friday: { start_time: 9, end_time: 10.5 } }

tutor_freetime = { monday: { start_time: 6, end_time: 9 }, tuesday: { start_time: 7, end_time: 10 }, wednesday: { start_time: 7, end_time: 9 }, friday: { start_time: 10, end_time: 11.5 } }

However, I think this is a bad solution since I need to use loop and if many times.

Therefore, I have been searching for the best solution for this problem, and found some suggestions on using the Hopcroft–Karp algorithm on stackoverflow. However, I've never implemented graph related algorithm before, so I am not sure the Hopcroft–Karp algorithm is the best choice in my case. As I understand, to implement Hopcroft–Karp algorithm  first I need to create to have 2 sets of data. In this case, I think the first set would be the student's freetime in a particular day, and the second set would be the tutor's freetime in the same day. But at this step, I am wondering how can I match their time by using Hopcroft–Karp algorithm  as I pointed out above, their freetime can be different and still match as long as it satisfies the session's limit time (90 minutes).
I would be appreciated if anybody could give me some suggestions here or point me to the right resources/similar problems.

This sounds like an instance of the assignment problem (see also our tag).  You can also view it as a bipartite matching problem.  There are standard algorithms for these problems; I suggest you use one of them.  Hopcroft-Karp is one of those standard algorithms.  I suggest that you either look for an existing implementation of one of those algorithms, or study them and implement themselves.

Expressing this as a network flow algorithm or as an instance of linear programming might provide extra flexibility to deal with additional constraints.

The specifics of how to express your problem as an instance of these problems will depend on the specific constraints you want to impose (e.g., is there a limit on the number of students you want to assign each tutor to?  is it ok to limit things to a set of non-overlapping 90-minute time slots?), which you haven't specified in the question, so it's hard for us to say much more.

I suggest you try applying one of those approaches to your specific problem, study one of the standard algorithms, and if you get stuck understanding some specific aspect of the problem, ask a new question where you ask about that specific difficulty.


Why NP is not closed under Turing reduction The notion of polynomial time Turing reductions (Cook reductions) is an abstraction of a very intuitive concept: efficiently solving a problem by using another algorithm as a subroutine.

For example, by stating "$A$ is polynomial time Turing reduced to $B$", we indicate that we can solve the problem $A$ in a polynomial number of steps by making use of an algorithm which can solve the problem $B$.

Then if $B$ is in $\mathsf{NP}$, why not $A$?

The reason that $A$ is not defined as in NP is that we use a finer notion for NP-completeness, which is mapping (Karp) reductions.

Intuitively, in a Karp reduction, we not only want the problem $A$ to be solvable using an oracle for $B$, but we also require that this oracle is only used once, and only as the very last operation.

Why this notion and not Turing reductions? First - it works well, and it provides a finer distinction in complexity classes (more on that in a bit). Second, it captures the intuition that if you could solve $B$, then given input for $A$ you can convert it to input for $B$, rather than just use $B$ in some complex and clever manner.  So in a way, it makes "very little use" of $B$. This is all philosophical, of course.

In practice, the main benefit of Karp reduction is that it differentiates $coNP$ from $NP$. Indeed, you can show a Turing reduction from $SAT$ to $\overline{SAT}$ (just call the oracle and flip the answer). So you cannot have the notion of coNP-complete v.s. NP-complete if you use Turing reductions.

You can read the discussion here for a more elaborate answer.


When is a regexp is not a Regular Expression? Since I'm studying for my formal languages college course, I stumbled upon these fascinating posts (One Two) which describe how to find a prime number using a regexp. As I said, a regexp, not a regular expression.
Since a regular expression can match strings computed by a Finite State Automata and finding a prime number can't be done by a FSA, the regexp shown in the blog post is not entirely a regular expression since it does backtracking to match the string.

Since I've never really used any regular expression, now, my question:

How can I immediately recognize a regexp from a "true" regular expression just by looking at it?

Definitions: By regular expression, I refer to the notion as defined in formal languages.  By regexp, I mean the notion supported by modern programming languages; the regexp syntax often contains additional features, such as backreferences.  Regexps as seen in programming languages are strictly more powerful than formal languages style regular expressions.

tl;dr backrefs.

As soon as there is a \1 (or any number that isn't used to escape unicode) in the regexp it is not a regular expression.

Backrefs allows you to match (a+)b\1 which matches n times a followed by b followed by n times a for any n>1. This is not a regular language (it's the poster child of a non regular language).

It is necessary and nearly sufficient that the backref references a group that contains a regexp that matches an arbitrarily long string or that it contains a * or +. The only exception (that I found) of a regexp of the form (A)B\1 where A is a finite language (could be replaced by a enumeration of all words that accepts them). You can convert it to word1+Bword1|word2+Bword2 etc. because A is finite.

Look-around groups don't remove the regularness of the regexp. A(?=B)C is the cross-section of regexes AB.* and AC and the cross-section of 2 regular languages is regular. Negative lookahead is similar except using the complement of B.* (complements of regular languages being regular). Lookbehind is exactly the same as well A(?<=B)C is the cross-section of AC and .*BC.


Number of combinations without given pairs Given a set of elements {e1, e2, ... en}, a set of pairs of these elements (each element may be present in several pairs) and a number k.
I need to count how many combinations of size k exist which not include any pair?
For example: if there only one pair {e1, e2} result in number of all combinations without elements e1 and e2. It may be counted in constant time: $$C^k_n - C^{k-2}_{n-2}$$
This task can be solved with the naive algorithm on python:
def combinations_without_pairs(elements, pairs, k):
    def iterable_len(iterable):
        return sum(1 for _ in iterable)

    def not_include_pairs(combination):
        for pair in pairs:
            if pair[0] in combination and pair[1] in combination:
                return False
        return True

    return iterable_len(filter(not_include_pairs, itertools.combinations(elements, k)))

But this algorithm is ineffective: it requires iterating over each element combination and each pair.
Is there any way to solve this problem with better complexity? At least reduce the impact of a big count of elements and pairs?
I want to find an algorithm with the lowest time complexity.

Don't expect an efficient algorithm.  This is the problem of counting the number of independent sets in an undirected graph.  This problem is #P-complete [1,2], so there is unlikely to be any effective algorithm that works for arbitrary graphs.
See https://cstheory.stackexchange.com/q/10700/5038 for techniques you could use.
[1] The complexity of counting cuts and of computing the probability that a graph is connected, J. Scott Provan and Michael O. Ball, SIAM J. Computing, 12:4.
[2] The complexity of counting in sparse, regular, and planar graphs, Salil P. Vadhan, SIAM J. Computing, 31:2(398--427).


Implementing an efficent priority queue using only stacks Is it possible to implement an efficient priority queue (as efficient as a heap) only using the stack data structure?

The usual efficiency for a priority queue which is implemented using a heap is :

get min - $O(1)$
extract min - $O(\log n)$
add - $O(\log n)$

Would it be possible to do something with the same complexity using only stacks?

I want to implement A* (which uses a priority queue to prioritize nodes) as a pathfinding algorithm inside Minecraft, but Minecraft doesn't allow random access, and the most efficent dynamic structure that can be implemented in it is a stack.

Unfortunately, it's not possible.  The order you extract items from the stack depends only on the order they're pushed, regardless of the values in those items; a priority queue needs items to be removed in an order that depends on the value of the items.


Secretary Problem with 2 positions - Maximizing the difference Synopsis

Imagine the secretary problem, except the goal is to hire two secretaries with the greatest possible difference between the two.

The Problem

I'm not particularly comfortable with this type of math so below are the modified constraints. The original constraints are from Wikipedia's page on the secretary problem.

There are 2 positions to fill
There are n applicants for the positions any applicant may fill any position, and the value of n is known.
NOTE: It is fine to put one person in both positions, but wouldn't be the optimal solution unless n = 1.
The applicants, if seen altogether, can be ranked from best to worst unambiguously.
The applicants are interviewed sequentially in random order, with each order being equally likely.
Immediately after an interview, the interviewed applicant is either accepted or rejected, and the decision is irrevocable.
The decision to accept or reject an applicant can be based only on the relative ranks of the applicants interviewed so far.
The objective of the general solution is to have the highest probability of selecting a pair with the greatest difference read (The best and the worst). This is the same as maximizing the expected payoff, with payoff defined to be one for the best applicant/worst applicant pair and zero otherwise.

For Context

I realized that at work that many of the problems I'm working on at the moment are normally treated as a single optimization problem. However in reality they are pair values, and since the goal is often to maximize the distance between choosing two values over a given number of days it seems to be very close to the secretary problem. I'm not comfortable enough yet with the math to solve this myself. My intuition is that this problem is equal to having two instances of the stopping problem however I'm not sure if this is mathematically equal.

Research

I've found papers on the Secretary Problem for TradeOffs, IE. The secretary's are evaluated on two rankings, and Random Walk, IE. dependent variables, while trying to answer this question. I have not managed to find anything directly related to this variant of the problem.

Answers

Thank you for reading my problem. Any insight into solving this problem is appreciated!

One trivial algorithm for the problem is exactly the same as the usual algorithm: observe $n/e$ of the applicants, then pick the first (if any) secretaries who are better than, or worse than, all applicants seen so far. This succeeds with probability roughly $1/e^2$. Answers to a question on math.se which includes your question claim that this algorithm (which is proposed in the answers) is obviously optimal.

To see that the success probability is roughly $1/e^2$, we follow the analysis in Wikipedia. We will analyze a more general algorithm, in which $n/e$ is replaced by $pn$, and then will show that the best choice for $p$ is roughly $1/e$. Let $q_{ij}$ be the success probability given that the $i$th secretary is the best one and the $j$th secretary is the worst one. If $i,j > pn$ then $q_{ij}$ is the probability that:

$i$ is the best secretary.
$j$ is the worst secretary.
Among the first $i-1$ secretaries, the best is one of the first $pn$.
Among the first $j-1$ secretaries, the worst is one of the first $pn$.

Calculation shows that
$$
q_{ij} = \begin{cases}
\frac{pn(pn-1)}{n(n-1)(i-1)(j-2)} & i < j, \\
\frac{pn(pn-1)}{n(n-1)(i-2)(j-1)} & i > j.
\end{cases}
$$
The overall success probability is thus at least
$$
\sum_{i=pn+1}^n \sum_{\substack{j=pn+1\\j \neq i}}^n \frac{pn(pn-1)}{n(n-1)(i-1)(j-1)} \approx p^2 \left(\int_{pn}^n \frac{dx}{x}\right)^2 = \left(p\log\frac{1}{p}\right)^2.
$$
This is just the square of the usual formula, so it is maximized at $p = 1/e$, for which the success probability is roughly $1/e^2$.


Confusion related to calculating time complexity I have some confusion related to calculating the time complexity of this algorithm

opt(i)
   for j=i:n
      a = f(i,j) + opt(j+1)
   end

How is the running time of this algorithm $O(n^2)$?

Let $T(i)$ be the running time of opt(i) then we have
$$ T(i)= \sum_{k=i}^n T(k+1).$$
You have not specified a recursion anchor, but I guess it is something like $T(n+1)=1$. Write down the series $T(n),T(n-1),T(n-2),\dots$ and you get the impression that $T(i)=2^{n-i}$. This guess can be proven by induction, since assuming that $T(i)=2^{n-i}$, we have
$$ T(i-1)= \sum_{k=i-1}^n T(k+1)= T(i)+\sum_{k=i}^n T(k+1)= 2 T(i) = 2^{n-(i-1)} .$$

Thus, $T(0)= 2^n$ and therefore it is not in $O(n^2)$.

PS I assumed that in the recursion the value of opt is never stored and will always be recomputed.


Maximum set of equalities, subject to some inequalities I have $n$ variables $x_1,\dots,x_n$.  I'm given a set $E$ of equalities (each of the form $x_i=x_j$ for some $i,j$) and a set $I$ of inequalities (each of the form $x_i \ne x_j$ for some $i,j$).  I want to find a maximum-size subset $E' \subseteq E$ such that $E'$ is compatible with $I$, i.e., such that there is an assignment to the $n$ variables that satisfies every inequality in $I$ and every equality in $E'$.

Is there an efficient algorithm for this?

I can see that the greedy algorithm (try adding equalities to $E'$ as long as doesn't imply the negation of some inequality) doesn't yield an optimal solution.  I have no idea what other approaches to try.

Equivalently, the problem can be formulated in graph-theoretic terms.  I'm given an undirected graph $G=(V,E)$ and a set $I \subseteq V \times V$.  I want to find a maximum-cardinality subset $E' \subseteq E$ of edges, such that when I decompose the graph $G'=(V,E')$ into connected components, $v,w$ are in different connected components for all $(v,w) \in I$.

Using your graph theoretic formulation, this problem can be restated as the multi-cut problem.

  Given a graph $G = (V, E)$ and a set of pairs $(s_i, t_i) \in I$ find a  set of edges $E' \subseteq E$ such that there is no path $s_i \leadsto t_i$ in the resulting graph $G' = (V, E \setminus E')$ for each $i$.

Since each inequality is unweighted you need to find a minimum size multi-cut.

This problem is NP-hard in general however there exist reasonable approximation algorithms that solve an LP. However a simple strategy might be to just take the union of each $(s_i, t_i)$ cut.


Shortest path from starting cell to all cells in the grid I found an algorithm for finding the shortest path on grid between selected cell, to all cells on the grid, with $O(KN)$ where $K$ is the number of neighbor cells and $N$ is the number of cells.

How ever if that's true than it's better than A*, Floyd–Warshall and many others. So I probably mistaking some thing. Can you point me what.

Here is a pseudo code for my algorithm, the idea is to calculate simultaneously to all the directions.

The algorithm starts with the call to filter method

class MapFilter
{
    declare cellsMap, array of numbers with two dimensions, that represent a grid
    declare stack, a stack of MapFilter
    declare count of type number
    read input to map, array of Cells with two dimensions, that represent a grid
    read input to x ,y those are coordinates of starting node

    function filter(){
        initialize cellsMap with empty grid, all values are 0
        set count = 1
        set cellsMap[x][y] = 1;
        execute();
        while(stack is not empty){
            read length of the stack to length
            iterate over i from 0 to length{
                remove first element from stack and store it in mapFilter, instance of MapFilter
                mapFilter.execute()
            }
        }
    }

    function execute()
    {
        populate(x + 1, y);
        populate(x - 1, y);
        populate(x, y + 1);
        populate(x, y - 1);
    }

    function populate(x, y)
    {
        // Testing if the x,y cell is blocked by some way
        if( not isInMapRange(x,y) or
            cellsMap[x][y] not empty or{
            return;
        }

        set cellsMap[x][y] to count;
        addTask(x,y);
    }

    function isInMapRange(x,y){
        return x < cellsMap.length &&
            x >= 0 &&
            y < cellsMap[0].length &&
            y >= 0;
    }

    function addTask(x, y)
    {
        initialize mapFilter;

        set mapFilter.map = this.map
        set mapFilter.cellsMap = this.cellsMap
        set mapFilter.count = this.count + 1
        set mapFilter.x = x
        set mapFilter.y = y
        add mapFilter to stack
    }
}

You have an unweighted, undirected graph with $N$ vertices, and where each vertex has degree $K$.  Then the problem of computing shortest paths can be solved in $O(KN)$ time using simple breadth-first search.

Why is this faster than Floyd-Warshall etc.?  Because Floyd-Warshall has to handle weighted graphs.  In your case you have an unweighted graph: every edge has weight 1 (the length of a path is just the number of edges in it).  There are faster algorithms for computing shortest paths in unweighted graphs than in weighted graphs; unsurprisingly, the problem is harder if you have a weighted graph.  If you have an unweighted graph, you don't need the fancier algorithms, like Floyd-Warshall; breadth-first search is enough.


Which of the following statements are true for the given special cases of the Traveling Salesman Problem? I'm taking the Algorithms: Design and Analysis II class, one of the questions asks:

  Which of the following statements is true?

  Consider a TSP instance in which every edge cost is either 1 or 2. Then an optimal tour can be computed in polynomial time.
  Consider a TSP instance in which every edge cost is negative. The dynamic programming algorithm covered in the video lectures might not
  correctly compute the optimal (i.e., minimum sum of edge lengths) tour
  of this instance.
  Consider a TSP instance in which every edge cost is negative. Deleting a vertex and all of its incident edges cannot increase the
  cost of the optimal (i.e., minimum sum of edge lengths) tour.
  Consider a TSP instance in which every edge cost is the Euclidean distance between two points in the place (just like in Programming
  Assignment #5). Deleting a vertex and all of its incident edges cannot
  increase the cost of the optimal (i.e., minimum sum of edge lengths)
  tour.

I argue as follows:

The DP algorithm doesn't make any assumptions on the edge costs, so option 2 is incorrect.

If all edge weights are negative, then deleting a vertex and all of its incident edges can certainly increase the minimum sum because in effect, that edge weight is now added to the previous minimum. Thus, option 3 is incorrect.

Take the optimal tour in the original instance. Now, instead of visiting the deleted vertex v, skip straight from v's predecessor to its successor on the tour. Because Euclidean distance satisfies the "Triangle Inequality", this shortcut only decreases the overall distance traveled. The best tour can of course only be better. Thus, option 4 is correct.

However, I'm not able to find any significance for TSP problems with unit edge costs. Is option 1 merely a trick, or is there more to it?

Statement 1 is false (assuming P $\neq$ NP) because any instance $G$ of the NP-complete Hamiltonian Cycle problem can be reduced to an instance of the TSP in which every edge cost is either 1 or 2.

Why? Define a TSP instance on a complete graph $K_n$, with edge cost 1 whenever the corresponding edge is also in the original graph $G$, and edge cost 2 otherwise. Now a TSP tour of cost $\le n$ exists in the complete graph if and only if $G$ has an Hamiltonian cycle.


Late and Early Bisimulation This is a follow up to my earlier questions on coinduction and bisimulation.

A relation  $R \subseteq S \times S$ on the states of an LTS is a bisimulation iff $\forall (p,q)\in R,$
$$
\begin{array}{l}
   \text{ if } p \stackrel\alpha\rightarrow p'
   \text{ then } \exists q', \;
   q \stackrel\alpha\rightarrow q' \text{ and } (p',q')\in R
\text{ and } \\
\text{ if } q \stackrel\alpha\rightarrow q'
   \text{ then } \exists p', \;
   p \stackrel\alpha\rightarrow p' \text{ and } (p',q')\in R.
\end{array}
$$

This is a very powerful and very natural notion, after you come to appreciate it. But it's not the only notion of bisimulation. In special circumstances, such as in the context of the $\pi$-calculus, other notions such as open, branching, weak, barbed, late and early bisimulation exist, though I do not fully appreciate the differences. But for this question, I want to limit focus just two notions.

  What are late and early bisimulation and why would I use one of these notions instead of standard bisimulation?

Late and early only make sense when building the LTS. The notion of bisimulation stays the same.

However there are several notion of bisimilarities in the π-calculus for example. These are related to how new names are handled. It happens in the π-calculus because it is a name-passing process calculus. There is no such thing in CCS where names cannot be sent.

Usually, the notion of barbed equivalence or congruence is more unanimous. Then you have to prove the equivalence with the late/early/open bisimilarity to give it some credit.

To be quick about it, early transitions are that way:
$$
a(x).P \stackrel{a(b)}{\longrightarrow} P[b/x]
\qquad
\begin{array}{c}
P \stackrel{a(b)}{\longrightarrow} P'
\quad
Q \stackrel{\overline ab}{\longrightarrow} Q'
\\ \hline
P\mid Q → P' \mid Q'
\end{array}
$$

and late are like this:
$$
a(x).P \stackrel{a(x)}{\longrightarrow} P
\qquad
\begin{array}{c}
P \stackrel{a(x)}{\longrightarrow} P'
\quad
Q \stackrel{\overline ab}{\longrightarrow} Q'
\\ \hline
P\mid Q → P'[b/x] \mid Q'
\end{array}
$$

You see the difference is subtle and is just about where the substitution is done. My preference go to the late one because when I reason about processes, I just remember that the $x$ in the transition $a(x)$ is bound. Also the late bisimilarity is the strongest one (beside the open one which is really not the same) and the processes that are early but not late bisimilar are kind of weird, so you don't lose much.


Auto-generating a class hierarchy/inheritance tree from a data set of objects with properties What is an algorithm that will take as an input a flat list of objects with a varying degree of overlapping properties:

thing1 (instance of "Mammal", but we don't know this now)
  -eatsFood
  -reproduces
  -hasMilk

thing2 (instance of "Emu", but we don't know this now)
  -eatsFood
  -reproduces
  -laysEggs
  -hasFeathers
  -doesNotFly

thing3 (instance of "Eagle", but we don't know this now)
  -eatsFood
  -reproduces
  -laysEggs
  -hasFeathers
  -flies

thing4 (another instance of "Eagle", we just know it has the same "shape" as thing 3)
  -eatsFood
  -reproduces
  -laysEggs
  -hasFeathers
  -flies

thing5 (instance of "BaldEagle", but we don't know this now)
  -eatsFood
  -reproduces
  -laysEggs
  -hasFeathers
  -flies
  -hasWhiteHead

And return as an output a hierarchical class structure/inheritance tree/taxonomy like the following?

Notes:

The algorithm is able to identify a hierarchical structure in the
objects' properties, including abstract classes that are not explicitly present as objects in our data set.  For example, there are no instances of "Bird" or "Animal" in our object data set, however the algorithm is able to identify that "Eagle" and "Emu" both inherit from a common parent class (the abstract class "Bird") and that both the "Bird" and "Mammal" classes inherit from a common parent class (the abstract class "Animal").
The algorithm doesn't know or care about the class names ("Animal", "Mammal", "Bird", "Emu", "Eagle", "Bald Eagle").  We generate those ourselves based on the properties of the classes the algorithm has generated.  I just put them here to aid the example, but they're not part of the algorithm.
The list of an object's properties in the data set will not necessarily be "in order" like they are here.  Don't assume any order to the properties in the raw data.

It looks like your problem can be solved by transitive reduction followed by some post-processing.

Build a directed graph, with one vertex per "object shape".  Draw an edge $u \to v$ if $u$ contains all of the fields of $v$ (possibly plus some more).  This should form a dag.  Now compute the transitive reduction of this dag.  The result should be a tree (or forest of trees).

This almost gives you the desired solution.  The one thing it doesn't do is invent new abstract base classes that weren't already present in the input.  So, we can do some post-processing to create them.  First, if the result has more than one tree, we'll create a new root (an abstract base class) that is a parent of all of those trees.  The result is a (directed) tree.

Examine each node that has more than two children.  This is the only place where we need to create new abstract base classes.  Let $S$ denote the set of children.  Now you have some choices about how you want to form a hierarchy based for $S$; there are multiple possibilities that are all consistent with the input data, and the question doesn't specify any criteria for choosing among them.  So, I'll have you let you decide on how you want to select among them.

What's the running time?  Constructing the graph and computing the transitive reduction can be done in $O(n^3)$ time, where $n$ is the number of different object shapes present in the input.   (In fact, given the structure of the input, in this particular case it can actually be done in $O(n^2)$ time, but maybe that isn't important, since I suspect in practice $n$ might be fairly small.)  The post-processing can also be done in $O(n^3)$ time (probably less if you care).  So the overall running time is at most $O(n^3)$.

Of course, we can de-duplicate the shapes in the input before doing any processing: there is no need to keep more than one object of any particular shape.  So, the running time depends only on $n$, the number of distinct shapes in the input, not on the number of objects in the input.  It's easy to do the de-duplication in linear time using a hash table.


Confusion related to this algorithm about finding the orientation given 3 points I have a confusion related to an algorithm for finding the orientation given three points, i.e., determining whether one line is clockwise or counter-clockwise of another.

Let's say the points are $P_1=(x_1,y_1)$, $P_2=(x_2,y_2)$, $P_3(x_3,y_3)$. The algorithm says

Let the slope of line $P_1P_2$ be $m_1$ and slope of $P_2P_3$ be $m_2$.
If $m_2 > m_1$, the orientation is counterclockwise and if $m_1 > m_2$ it is clockwise.

However lets say the points are $(0,0)$, $(4,4)$ and $(2,4)$. This give $m_1=1$, $m_2=0$. The orientation is counter clockwise but $m_2 < m_1$. So I am wondering if there is any issue with the algorithm.

Any suggestions?

The orientation of three points in the plane is classically done with a determinant. In the linked article the approach is done on a polygon thus they use a 3x3 determinant. For only three points, i.e., a triangle, a 2x2 determinat is sufficient.

Let $p_1=(x_1,y_1), p_2=(x_2,y_2)$, and $p_3=(x_3,y_3)$ be three points in the plane. Then we compute the orientation vectors at $p_1$, that is $p_{1,2}=p_2-p_1$ and $p_{1,3}=p_3-p_1$. Now we use the determinant to find the orientation: $$\mathrm{det}\begin{bmatrix}x_2-x_1&y_2-y_1\\x_3-x_1&y_3-y_1\end{bmatrix}=(x_2-x_1)(y_3-y_1)-(y_2-y_1)(x_3-x_1).$$

If the result is smaller than zero then $(p_1,p_2,p_3)$ are in counter-clockwise order, if larger than zero in clockwise order, and if zero then they are collinear.


Common parse tree for several formulas I have a large (~1k) number of boolean formulas like:

f1(x) = p1 AND p2
f2(x) = (p1 AND p2) OR p3
f3(x) = p4 OR !p5

The argument x is a set, and the predicates (the p's) assert that a certain condition is met on the set (typically, that x contains a certain value).

For every input, I have to evaluate all the formulas.

As an example, given a chair, f1 would say: the chair is red and the chair has a head rest, f2 would say f1 OR the chair was built before 1980 and so forth.

Some predicates invalidate the formulas statistically sooner than others in my data set; one of them would be, for example, the chair was built before 1900 (not many very old chairs are found).

If I scan all the formulas, find the pieces of them that are equal, like in this example, the first part of f1 and f2, is there a way to build a common parse tree that lets me use this information to make evaluating all the formulas faster?

This is the circuit minimization / logic optimization problem.   You have a circuit with some number of inputs (one per predicate p1, .., pn; or based on the representation of x)  and ~ 1k outputs (one per formula f1, .., fm).  Now the goal is to construct another equivalent circuit that computes the same output, as efficiently as possible.  That's a circuit minimization problem.  The problem is hard in general, but there are some heuristics and tools that may be effective in many situations (e.g., Espresso, Quine-McClusky, BDDs, and more).  I suggest reading about that subject and trying out one of those tools or techniques.


Find successor element in heap Does finding the successor of an element in a heap take $O(\log n)$?
An heap is not a binary search tree, so couldn't an element's successor be found in $O(n)$ time?

Suppose you have a min heap $H$, and you want to find successor one of the leaf node that its successor is maximum value, so you need to scan all leaves in tree, in addition we know that number of leaves in $H$ is $O(n)$. So you need read $O(n)$ nodes.


If a Language is Non-Recognizable then what about its complement? Is the complement of a Non-Recognizable language

Recognizable
Non-Recognizable
May be Recognizable, May be Non-recognizable. I.e cant comment.

A mathematical proof would be of great help since im unable to think of any way to prove this.

I did some research on this and found below examples. Im specifying complement using a "!"

!A(TM) is a non-recognizable language while A(TM) is a recognizable language.
EQ(TM) is a non-recognizable language and !EQ(TM) is also non-recognizable language

The above two would mean that we simply cant comment on the Recognizability of the complement of non-recognizable language. But I feel that there should be some way to prove (or disprove) this.

Assuming that you can prove statement 1 and 2 above, you have just presented a proof. You're trying to show that there exists a language which is non-recognizable such that its complement is recognizable. You then prove that $!A(TM)$ has this property. Then you want to show that there exists a non-recognizable language whose complement is also non-recognizable and then you show that $EQ(TM)$ has this property.

The point is that to prove that you can't comment, you need only to show that both possibilities are possible ie. that examples of each exist.


Why is Steiner Tree trivially in NP? I'm learning about NP-completeness, and many reduction proofs start off by stating that a problem is triviallyin  NP. But I can't seem to wrap my head around this.

Why is this so?

What is normally meant in cases like this is

  there is a simple, obvious algorithm which demonstrates that the problem is in $\mathcal{NP}$,

with an implicit

  but we don't have enough space, can't be bothered, or don't want to bore the reader by including it.

Whether it really is trivial is a trickier thing (but often it really is).

Before returning to the Steiner Tree problem, recall the two common definitions of $\mathcal{NP}$ membership:

A problem is in $\mathcal{NP}$ if, given the input and a solution, we can check that the solution is correct in deterministic polynomial time, or
given the input, we can compute the solution in non-deterministic polynomial time.

So for the Steiner Tree problem (remember we only concern ourselves with the decision versions), they are saying that at least one of the following is true:

Given a graph, a set of required points, a value $k$ and a tree (the alleged solution), we can easily check that the tree is a Steiner tree of value at most $k$, or
Given a graph, a set of required points and a value $k$, we can easily compute a Steiner tree of value at most $k$ if we can make some really good guesses.

Hopefully in this case both of these should be more obviously true. In the first case, we need only check that the tree1 contains the required points, and the total weight of the tree is at most $k$. In the second, we can use the magic of non-determinism to guess which edges are in the tree, then check that it's okay as in the first case.

The only further requirement is that these procedures be computable in polynomial time, but in both cases we at most need to look at each edge of the graph and each vertex of the graph once(-ish) (if we have sensible data structures to store the graph and tree), so even without being too precise, we can see that they can both be done in polynomial time.

Footnotes.

As A. Schulz notes in the comments, there is an additional issue of ensuring that the witness (the solution handed to us) has an encoded length bounded by a polynomial in the size of the original input. This may be easy to see, but as A. Schulz also notes, if we're talking about the Geometric Steiner Tree problem, then we might have to make an additional argument about how we encode the geometry of the tree - not necessarily too complicated, but still important. If we're talking about the Steiner Tree Problem in Graphs, then it's more straightforward (as we don't have to worry about the geometry), and perhaps something you can gloss over. Nonetheless it is important to be careful :).


What happens when many interrupt requests happen at the same time? My initial guess is that you would have to queue the lower priority one, but what happens when for example 5 or many more requests happen at the same time? Are all these requests put in a queue or are they lost forever?

In most cases, interrupt requests are processed, in priority order. Typically this does not involve a queue, but instead, lower priority interrupts continue to be asserted until such time as they can be processed.

A typical example would be the interrupt controller in a PC. This traditionally has a number of inputs, each assigned a priority. The peripheral signals its request. This remains until the processor clears the interrupting condition.


O(1) access into an array-like data structure with numerical ranges for keys Preface: It's been a long time since I've been in school, and my terminology is probably all wrong. Apologies...

Summary: I have a data structure with probability ranges assigned to the elements, and I want to "roll the dice" and get the element at that spot. I'm wondering if there's a (good) way to do this in O(1) time?

Assume I've got a data structure like this, where the indices/keys represent ranges, and the values are what I want:

a = {
  [0..0.3) -> "foo",
  [0.3..0.4) -> "bar",
  [0.4..0.9) -> "baz",
  [0.9..1.0] -> "qux"
}

I want to retrieve a value from that array using a randomly generated number between 0 and 1. So, using that previous example, I do something like:

a[0.2] == "foo"
a[0.3] == "bar"
a[0.5565] == "baz"
a[0.8] == "baz"
...and so forth

I think I could store the data in a tree structure where I could walk to the correct element in O(log(n)) time, but I'm wondering if there's a clever way to do it in O(1) time.

I'm also curious if there is a specific name for this kind of data structure. It seems like someone would have played with this at some point.

As background, I'm toying with creating a Markov generator, and that requires storing the frequencies for all the words/token pairs. I'm guessing this is a solved problem already, and there are probably better solutions than what I'm proposing, but it seemed like an interesting problem and now I'm curious about the index-by-range problem all by itself, independent of the Markov aspect.

Perhaps what you're looking for is a Direct-adress Table

You can set up the keys as the ranges you've provided. Since the set of keys is quite small (4 intervals), a Direct-adress Table is a simple solution to your problem. It has the advantage of retrieving data in O(1)

The keys would hold a pointer to the data you want to retrieve.

For example, you can set a variable key1 as the interval [0..0.3).
We generate a random number x, and get 0.1.
Since 0.1 meets the conditions of the first key ( x >= 0 and x < 0.3), we can retrieve the data stored in key1 in O(1) time.

If you want more information about a Direct-adress Table or O(1) operations on dictionaries, I recommend Introduction to Algorithms, 3rd Edition, Chapter 11


Allocation of many students to many schools based on capacity Say I have a set of schools coordinates (S). I also have a set of neighborhoods centroid coordinates (N).

I know how many kids are in each neighborhood, and they are categorized as either primary, middle or high school. So, in other words,

N = [(locationN1, primary:3, middle:10, high:4), (locationN2, primary:10, middle:17, high:7), ...]

I know how many spots are available in each school, the format being:

S = [(locationS1, primary:20, middle:5, high:2), (locationS2, primary:12, middle:7, high:8), ...]

My goal is to match as many students as possible to a school within a certain radius. It is possible (extremely likely) that in my calculations, some students will be school-less.

What I want: identify which neighborhood have school-less children and how many.

My current plan:

List all the pairings and corresponding distances between schools and neighborhood, within a given radius
Order by distance from lowest to highest
Give priority based on distance
Loop over the neighborhood in order of appearance (each neighborhood can appear several times linked to a given school within defined radius)
Fill corresponding school with children from neighborhood
Remove taken spots from the school capacity
Move to the next neighborhood-school pairing, ...

As an example:

Say you obtain the following ordering:

Order = [(neighborhood_2, school_7, distance1), (neighborhood_5, school_2, distance2), (neighborhood_2, school_2, distance3), (neighborhood_2, school_3, distance4) ...]

Then, school_7 receives children from neighborhood_2. Not all children from neighborhood_2 can be taken in at school_7.

Then, school_2 receives students from neighborhood_5. Now, assume that school_2 is full for middle school capacity.

Then, neighborhood_2 still has students to dispatch, and so tries to send them to school_2. Primary and high school, no problem, they are now all dispatched. But middle school is full.

Then we move on to the next pairing, and school_3 gets the remaining middle school students from neighborhood_2. Note that if distance4 had been higher than the limit radius, these middle school students would have been classified as school-less since no other pairings are available.

Additionally, if neighborhood_4 is oit of the limit radius for any school, all its children are considered school-less.

1) Is my algorithm correct?

2) What is the name of this exact problem? I've come across many to many point matching, capacitated allocation problems, or the "validation" part of facility location problem, but not this particular variant for some reason (likely poor searching skills)

3) How can I make this efficient, or is it pretty reasonable this way? (efficiency is not my primary concern, but easy fixes are welcome)

4) Do I have other options besides distance sorting? Technically, in my case, distance doesn't matter much to give priority, it's more of a random (or should I say fair) allocation based on for example time of received application (unknown data). So my method will show likely 100% allocation for a neighborhood very close to a school amd a bunch of school-less kids in farrher neighborhoods, yet that may not be (is not) true in real life.

This can be expressed as the problem of finding a maximum matching in a bipartite graph: each kid is one left-vertex, each slot in a school is a right-vertex, and there is an edge between two vertices if they can be matched.

In your case, you can solve it more efficiently using max flow.  I'll let work out the details.


Generating a Context Free Grammar(CFG) from a Language I would really appreciate if anyone could tell me how to generate CFG from this language. I am trying to learn the procedure of generating CFGs from CFLs and I am able to solve easier problems.. but I am really stuck on this one, I just can't get it how can I generate at two different positions at the same time.

L = {0^i 1^j 0^k | i + j >= 2k }

You can construct the grammar using the following nonterminals:

$S$ is the initial nonterminal. We will include a production $S \to 00S0$ to capture the inequality $i+j \geq 2k$ being satisfied just using $i$.
$T$ will similarly be a nonterminal that will include a production $T \to 11T0$ which captures the inequality $i+j \geq 2k$ being satisfied just using $j$. We also add a termination production $T \to \epsilon$.
The production $S \to T$ will allow us to mix both kinds of ways to satisfy the inequality $i+j \geq 2k$. However, there are two problems:

We need to allow $i+j > 2k$.
We need to allow the case $i+j = 2k$ in which $i,j$ are both odd, i.e., at some point the inequality $i+j \geq 2k$ is satisfied by increasing $k$ by 1, and compensating by increasing both $i$ and $j$ by 1.

To handle the second problem, we will add a production $S \to 01T0$.
To handle the first problem for $i$, we will add the production $T \to 1T$, and to handle it for $j$, we will add the production $S \to 0S$.

In total, we obtain the following grammar:

$$
\begin{align*}
& S \to 0S \mid 00S0 \mid 01T0 \mid T \\
& T \to 1T \mid 11T0 \mid \epsilon
\end{align*}
$$

You can prove by induction the following statements:

$T \Rightarrow^* xTy$ iff $x = 1^j$, $y = 0^k$, and $j \geq 2k$.

As a conclusion, $T \Rightarrow^* w$ if $w = 1^j0^k$, where $j \geq 2k$.

$S \Rightarrow^* xSy$ iff $x = 0^i$, $y = 0^k$, and $i \geq 2k$.

As a conclusion, $S \Rightarrow^* xTy$ if either $x = 0^i$, $y = 0^k$, and $i \geq 2k$, or $x = 0^i1$, $y = 0^k$, and $i+1 \geq 2k$.
As a conclusion from (1), $S \Rightarrow^* w$ if $w = 0^i 1^j 0^k$, where $i+j \geq 2k$.


What does $(\log n) \cdot (\log n)$ simplify to in Big O notation? Does it simplify to $O(\log n)$ or $O(\log^2 n)$ or something else entirely? I am a bit stuck on this one.

As $\log(n) \times \log(n) = \log^2(n)$, you can say $\log(n) \times \log(n) = O(\log^2(n))$.Moreover, as $\lim_{n\to\infty}\frac{\log(n)}{\log^2(n)} = 0$, you can't write $\log(n) \times \log(n) = O(\log(n))$, but you can write $\log(n) \times \log(n) = \omega(\log(n))$.


Why can't one use the Cook-Levin theorem to show that TQBF is PSPACE-complete? I have been reading Michael Sipser's Introduction to the Theory of Computation, and I have stumbled upon a paragraph in Chapter 8 (Theorem 8.9 on page 339 of the 3rd international edition) that I simply do not understand.
For context, TQBF is the language of all first-order logical formulas in prenex normal form that are true given a universe/domain.
A language $B$ is PSPACE-complete if

$B$ is in PSPACE, and
every $A$ in PSPACE is polynomial time reducible to $B$.

The following paragraph from the book tells us that it is a bad idea to use Cook-Levin theorem for the purpose of showing that a language $A$ in PSPACE is polynomial time reducible to TQBF. The paragraph reads:

As a first attempt at this construction, let's try to imitate the proof of the Cook-Levin theorem, Theorem 7.37. We can construct a formula $\phi$ that simulates $M$ on input $w$ by expressing the requirements for the accepting tableau. A tableau for $M$ on input $w$ has width $O(n^k)$, the space used by $M$, but its height is exponential in $n^k$ because $M$ can run for exponential time. Thus, if we were to represent the tableau with a formula directly, we would end up with a formula of exponential size. However, a polynomial time reduction cannot produce an exponential-size result, so this attempt fails to show that $A$ is polynomial time reducible to TQBF.

This last sentence I don't get. Why cannot a polynomial time reduction produce an exponential size result? Doesn't any reductions using Cook-Levin from an NP language result in an exponential-size result? Is it that it doesn't work in this particular situation, or is this a general thing?
My guess is that it has to do with the assumed space complexities of $A$ or TQBF, however I still don't see it. One of the conditions for TQBF's PSPACE-completeness is to show that any PSPACE language is polynomial time reducible to TQBF. Any talk about space shouldn't really belong.
Maybe it's my sheer interpretation of the sentence?

If you want to write $N$ words of output, it takes at least $N$ steps of computation to do that.  So, if you need to produce an exponential-sized output, you'll need to spend exponential time to do it.  For that reason, a polynomial-time reduction cannot produce an exponential-sized output when run on a polynomial-sized input.


Proving worst-case running time is in $\Omega(n^2)$ I was given the following method to argue that an algorithm $A$ has a worst-case running time of $\Omega(n^2)$:

  We need to argue that there exists an input $x$ of size $n$, the
  running time of $A$ with input $x$, i.e., $t(x)$, is at least
  $cn^2$, where $x>0$ is a constant.

If you find a single input of size $n$ that gives A a running time of exactly, $n^2$, then couldn't there still exist a different one that is less than $n^2$, since we're only specifying one input and not all inputs?  I'm having difficulty understanding the logic.

The worst-case running time of an algorithm $A$ is a function $T(n)$ which accepts an input length and outputs the maximum running time of algorithm $A$ on an input of length $n$:

$$ T(n) = \max_{|x|=n} \mathrm{runtime}(A,x). $$

Therefore to prove that $T(n) \geq S(n)$, it suffices to show that for each $n$ there is an input $x_n$ of size $n$ such that $\mathrm{runtime}(A,x_n) \geq S(n)$. The fact that there exist other inputs on which $A$ performs better is completely immaterial, since the worst-case running time depends on the worst input.


3SUM problem solution on the basis of cubic function and a line? The 3SUM problem formulation: in a given set of n real numbers find 3 elements that sum to specified value S.

I am trying to understand mathematical solution of the 3SUM problem based on a polynomial of 3 degree. I found some information about 3SUM problem as a special case of geometrical problems. It says:

  There are m points on a plane and it is required to check if some
  3 points are located on on the same straight line.   So, there is a
  straight line function: $y = ax + b$ and a curve: $ y = f(x) = x^3 -
Sx^2 $ Intersection of the above two equations is roots of the
  following equation: $x^3 - Sx^2 - ax - b = 0  $

  So, set of points $(a_1 , f(a_1)), ..., (a_m , f(a_m))$ contains 3
  points $(a_x , f(a_x)), (a_y , f(a_y)), (a_z , f(a_z))$ on the samle
  straight line if and only if $a_x + a_y + a_z = S$

I can't fully percieve the relation between 3SUM problem and the above geometrical problem.
AFAIK, in the equation: $x^3 - Sx^2 - ax - b = 0  $ variable $a$  represents set of points $(a_1 , f(a_1)), ..., (a_m , f(a_m))$ and probably all real numbers in which I search for some 3 numbers that sum to S. So 3 numbers $a_x + a_y + a_z$ sum to S if all of them are on the same line. But what x, y, z represent here? What is $a_z$ or $a_y$? And what is coefficient before $x^3$ equal to? How do I define b?

Can someone clarify relation between 3SUM problem and the above geometric problem?

Consider the problem of finding whether the list $a_1,\ldots,a_n$ contains $d$ points summing to $S$. We assume that these points are all distinct.

Let us suppose that the $d$ points $a_{i_1},\ldots,a_{i_d}$ do sum to $S$. All of these points are roots of the polynomial
$$
(x-a_{i_1})(x-a_{i_2})\cdots(x-a_{i_d}) = x^d - Sx^{d-1} - P_{d-2}(x),
$$
where $P_{d-2}$ is a polynomial of degree at most $d-2$; the point is that we know that the coefficient of $x^{d-1}$ is $-S$, since (in this case) it equals the negative sum of the roots.

In view of this, we are motivated to consider the points $p_i = (a_i, a_i^d - Sa_i^{d-1})$. If $a_{i_1},\ldots,a_{i_d}$ sum to $d$ then the points $p_{i_1},\ldots,p_{i_d}$ all lie on the polynomial $y = P_{d-2}(x)$ of degree at most $d-2$ (we have seen that above).

Conversely, suppose that there exist $d$ points $p_{j_1},\ldots,p_{j_d}$ which all lie on a polynomial $y = Q_{d-2}(x)$ of degree at most $d-2$. This means that these points satisfy
$$
a_{j_t}^d - Sa_{j_t}^{d-1} = Q_{d-2}(a_j), \text{ for $j=1,\ldots,d$}.
$$
Stated differently, the values $a_{j_1},\ldots,a_{j_d}$ are all roots of the polynomial
$$
Q = x^d - Sx^{d-1} - Q_{d-2}(x).
$$
Since $a_{j_1},\ldots,a_{j_d}$ are all distinct (by assumption) and a polynomial of degree $d$ has at most $d$ roots, we conclude that $a_{j_1},\ldots,a_{j_d}$ are all the roots of $Q$, which means that
$$
Q = (x - a_{j_1}) (x - a_{j_2}) \cdots (x - a_{j_d}),
$$
implying that $S = a_{j_1} + \cdots + a_{j_d}$, as before.

Summarizing, the $d$ values $a_{i_1},\ldots,a_{i_d}$ sum to $S$ if and only if the points $p_{i_1},\ldots,p_{i_d}$ lie on a polynomial of degree at most $d-2$. Stated differently, there are $d$ values summing to $S$ if and only if there are $d$ points lying on a polynomial of degree at most $d-2$.

This criterion should be contrasted with the fact that every $d$ points lie on some polynomial of degree at most $d-1$.


Exponential Space Complexity equality Consider $$ \bigcup_{c \in \mathbb{N}} \mathsf{DSPACE}(2^{c (\log{n})^2}) \quad  \overset{?}{=} \quad \bigcup_{c \in \mathbb{N}} \mathsf{DSPACE} ( n^{c \log{n}})$$

My lecture notes say that this is an equality, can someone point me to the theorem (or explain) why this is ?

I've observed that one power of the logarithm in the exponent disappeared but I couldnt find a theorem resembling any of the above.

Suppose first that $\log n$ stands for base 2 logarithm. In this case, since $n = 2^{\log n}$, we have
$$
2^{c\log^2 n} = (2^{\log n})^{c\log n} = n^{c \log n},
$$
from which your identity immediately follows.

If $\log n$ uses some other base, we still get the same result, because both sides of the identity are insensitive to the base of the logarithm. This is because different logarithms differ by a constant factor, and this constant factor can be swallowed by the union over $c$. Details left to you.