Given graph G and vertices v and w can you non-deterministically walk the "least Hamiltonian path" from v to w, if it exists? My understanding of non-deterministic algorithms is that they're "as lucky as you want".

...you can think of the algorithm as being able to make a guess at any point it wants, and a space alien magically guarantees it will always make the right/lucky guess.

For example, if you choose two vertices v and w, if there's a vw path, then you can non-deterministically walk a vw path, luckily correctly guessing the vertices to walk in a vw path. Given this is true of paths in general, I wonder if the same can be done for Hamiltonian paths. I would think so, but I'm not sure.
Therefore, my first question is: if you can non-deterministically walk a vw path, can you non-deterministically walk a Hamiltonian path from v to w, if a Hamiltonian path exists? If you can non-deterministically walk a Hamiltonian path, I wonder if the same can be done for an additional constraint, what I'm calling a "least Hamiltonian path." I would think so, but I'm not sure.
Define the least Hamiltonian path from v to w to be the Hamiltonian path such that the second vertex is the smallest it can be, then the third vertex is the smallest it can be, the fourth is the smallest, etc. Assume vertices are integers. For example, if we consider K5 the graph with vertices {1,2,3,4,5} and all possible edges, then the least Hamiltonian path for (v,w) = (2,3) is 21453. If you were at vertex 2, the next least vertex would be 1. Then, the next least vertex would 4. etc.
Therefore, my actual question is: Given graph G and vertices v and w can you non-deterministically walk the least Hamiltonian path from v to w, if it exists?
Motivation: If so, then perhaps there's a space-efficient algorithm for non-deterministically walking a Hamiltonian path: You can keep a counter for vertices v and w, and go through each pair of vertices such that v<w, checking for the existence of a least Hamiltonian path. To ensure all vertices in G are reached, keep a counter for the number of vertices walked (this should equal N if there are N vertices). Also, ensure that each vertex in the path is unique. The least Hamiltonian path from v to w will be unique, therefore it can be walked multiple times (each time you walk through it, starting at v, you'll non-deterministically guess the next least vertex in the least Hamiltonian path). You could use two counters to ensure no vertices are repeated - one for the vertex you're checking to see if it's unique (loop through the vertices in the least Hamiltonian path), and another counter for a second pass through the least Hamiltonian path. Ensure the second counter encounters the value of the first counter exactly once (use a boolean flag to keep track of this).

No.  There has to be a way to verify that your choices led to a correct choice, in polynomial time (with an ordinary deterministic computer).  Given a particular Hamiltonian path, there's no way to verify it is the least Hamiltonian path (in polynomial time).
The "space alien" stuff is just intuition, but if you want to know what it means in a precise way, you need to go to the formal mathematical definition.  My favorite definition of NP is the verifier-based definition.  With that definition, there is no obvious way to pick a short certificate that a polynomial-time (deterministic) algorithm can use to verify that a proposed solution to the problem is correct.


Fast hashing: combination of different techniques to identify changes in a file? I want to create a fast way to detect whether a file might or might not be the same. For almost 100% sureness I would use an existing hash algorithm, e.g. SHA256.
However, the files are expected to be huge video files with several GB, so calculating the SHA256 hash could take some time, especially over the network.

Therefore I want to combine different other techniques:

file size: if the file size has changed, the content has changed (sure)
head / tail hash
random hash

The latter 2 are part of my question:

My guess would be that in the header there are things like:

frame rates (e.g. Videos)
resolution (e.g. Videos, Images)
(file) length (e.g. in frames, pixels etc.)
last change date (e.g. Word documents, not specifically Videos)

Why I consider checking the tail is:

MP3 has the tag information there
EXIF adds custom data at the end if I'm right

Random hashes would select e.g. 126 regions at random positions in the file with a specific length, e.g. 64 kB and create a hash for them. Of course I remember the offsets for later comparison.
All in all I would use (1+126+1)*64 kB of data for my hash, so I need to read only 8 MB instead of several GB to get the hash.

Maybe it's more a Math question now, but: how likely is it to detect a change using the combination of file size, head, tail and random data to generate this quick hash sum?

I assume that the files are always legal files. There's no benefit in manipulating single bytes. The user would use a normal video editing tool to change the files.

UPDATE:
I unaccepted this answer which came from Crypto.StackExchange. I agree that my proposal is not cryptographic and not intended to be secure. I also agree that CRCing a file is fast, but in my case I really need a hash - I'll explain why:

My application is expected to save bookmarks in videos. My database is expected to save the video hash and the bookmarks.
Users sometimes move or rename files. My program will notice that a file does no longer exist, but will not delete the bookmarks from the database. Instead, when the same video is (accidentally) played again, I want to recognize that it's (probably) the same file.
Users are expected to save files on network drives (NAS) and stream videos. Those are dumb storages. I cannot install a server component. And they might be quite slow, so I really don't want the full hash. Calculating a full hash on a 3 GB file takes at least 5 minutes @ 10 MB/s, no matter how fast the hashing algorithm is.
If the user has edited the file, I somehow hope that the hash won't match any more, because otherwise I would display wrong bookmarks.

I'd be ok with a ~80% chance of having the correct bookmarks. How many hash pieces should I put together and where in the file would that be?

There are two sides to your coin:

if you want to do it secure, you will need to use a cryptographically secure hash like SHA256 (crypto-hashes are meant to be fast, but tend to be a bit slow due to security constraints),
things like CRCs are definitely quicker, but will never be able to offer the same kind of security (especially when we’re talking about .

Option 1: CRCs — Doing it quickly at the price of security:

If you're just after the detection of changes, go for a checksum instead of a hash. That's what checksums were made for: quickly detecting changes in a file or data-stream. But keep in mind that CRC was designed to prevent transmission errors, not malicious action!

Practically, CRC32 is the most obvious candidate (but even an additive CRC8 would do the job if you only want to detect if something has changed and don't expect anything else than that from the CRC.)

Option 2: Beyond CRCs — Doing it rather quickly while enhancing change-detection:

Other valid options (looking at @poncho's comment) are indeed to simply check the last-mod timestamp.

Or, you combine both (to prevent bottlenecks), using something like this pseudo-code shows:

if(LastMod != knownLastMod) { CreateNewCRCandCompare(FileName, knownCRC) };

But does this offer any real security? No. Same goes for your…

  Why I consider checking the tail is:
   - MP3 has the tag information there
   - EXIF adds custom data at the end if I'm right

Again, it depends on how much security you expect. You have to realize that an adversary will surely manipulate the file to keep (or copy-and-paste) any old ID3 and EXIF data… as anyone (with appropriate RW file-access rights) can modify that. Same goes for the Last-Modification timestamp, frame rates, resolution, last change date, and even the  (file) length. Depending on that “additional”  and “modifiable” data — which can be modified and removed by anyone with enough file-access rights — would introduce a security flaw.

But you do expect security, don't you? After all, that's the reason why you're thinking about all this in the first place. Well, then there is not way around using crypto-secure hashes…

Option 3: Cryptographically Secure Hashes — Doing it securely at the price of speed:

If you expect real security, you will have to rely on hashing; to be more precise: cryptographically secure hashing (using a hash which is not known to produce collisions). It takes time (a few microsecs per MB) but it's worth it.

My 2 (personal) cents:

Try to live with the fact that hashing costs time and hash the whole files with a cryptographically secure hash. Because, when stuff starts hitting the fan… you're better off being slow, instead of being sorry.

EDIT based on your EDIT…

If cryptographic security isn’t your main focus, you could look at MD5 or SHA1. Both MD5 and SHA1 are “cryptographically broken” because collisions have been detected… yet for the change-detection purposes you describe (especially after your EDIT), the likely-ness of hitting such a collision should be minimal enough.

Looking at everything again (including your EDIT), I personally would most probably use MD5, because it offers a usable collision resistance (for change-detection purposes) while still being fast enough to completely hash multi-gigabyte files.

If that still doesn’t satisfy you in a “speed” sense or if your hardware resources are really that limited, you have to try to balance collision-resistance/change-detection with speed. Meaning…

Take the individual timestamp, the individual filename, and hash the header (length depends on media type and used file format) as well as a good chunk from the middle and a good chunk of the tail (= file end). Combine those 5 and you should be able to roughly filter out most

  I'd be ok with a ~80% chance of having the correct bookmarks. How many hash pieces should I put together and where in the file would that be?

That’s more of a personal opinion, as it depends on a whole truckload of details (media type, file format, available resources, expected change-detection ratio, file similarity, etc.) so will have to balance that out yourself depending on your personal expectations, your implementations, and local results due to hardware and/or software bottlenecks.

Let me try to provide you with some guidance nevertheless:

If hashing the complete file isn’t an option for whatever reasons, I would – at least – take: the header (and maybe a few KBs more), a good chunk from the middle (at least the size of the “header & co.” part), and a good chunk from the file end (again, at least the size of the “header & co.” part).

The more resources you can invest (or are willing to invest), the more chunks you can take and/or the bigger those chunks can be. If you think your resources/feel/whatever still offers room for more, increase the size of the chunks you hash and/or increase the number of chunks you hash.

Increasing the number of chunks is easy: as all you need to do is to take care of an equal distribution (by dividing the filesize accordingly, resulting in same-size chunks you extract from equally-spaced parts over the whole file-length).

And if you’re asking yourself “Why equally distributed and not random chunk-positions?”, let me simply note that picking random chunk positions might practically render your change-detection efforts void since it incorporates the risk of skipping some important parts media where you would normally detect the chances you are aiming to detect. Choosing an equal distribution is – simply said – more neutral.


Boolean expression to logic gates Hello I need help with xy xor z, do I do the logic AND first or the XOR, no parenthesis. Thank You

Usually, an operator that's written implicitly by just putting the operands next to each other (e.g., "$xy$" for $x\land y$ in logic or $x\times y$ in arithmetic) has precedence over binary operators that are written out explicitly (e.g., $\lor$ or $\oplus$ in logic, or $+$ in arithmetic). Indeed, any author who uses a different convention to that needs a good stern talking to.  But note that it is only a convention.

So the expression in the question means $(xy)\oplus z$, unless the person who wrote it hates us. This view is reinforced by the fact that logical and is multiplication modulo 2, and xor is addition modulo 2 and we'd expect multiplication to have precedence over addition.


Prove that every regular subset of $a^nb^n$ is finite How to prove that every regular subset of $L=\{a^nb^n \mid n\ge0 \}$ is finite?
I know that every finite language is regular, and it's not true that every regular language is finite.
I also know that $a^n b^n$ is non-regular language.
I can find examples of finite regular subsets of $L$, for example $\{\epsilon, ab, aabb\}$, but how do I prove that all regular subsets of $T$ are finite?

This is a simple application of the pumping lemma. Suppose that $L'$ is an infinite subset of $L$. Given $p$, since $L'$ is infinite, there exists some $n \geq p$ such that $w = a^nb^n \in L'$. Let $w = xyz$ be a decomposition of $w$ such that $|xy| \leq p$ and $y \neq \epsilon$. Then $y = a^t$ for some $t \neq 0$, and so $xy^0z = a^{n-t}b^n \notin L'$. Therefore $L'$ is not regular.
One might be tempted to think that this argument generalizes to every $L$ whose non-regularity can be proved using the pumping lemma. However, this is incorrect, as the example of $L \cup c^*$ shows.
This raises the following intriguing question:

For which infinite languages $L$ is it the case that all regular subsets of $L$ are finite?


Target-Value Search (& II) [previously appearing in cstheory, it was closed there and introduced here instead]

Given an edge-weighted graph $G=(V,E)$ the problem of finding the shortest path is known to be in P ---and indeed a simple approach would be Dijkstra's algorithm which can solve this problem in $O(V^2)$. A similar problem is to find the maximum path in $G$ from a source node to a target node and this can be solved with Integer Programming so that, as far as I know, this is not known to be in P.

Now, the problem of finding a path in $G$ such that it deviates the minimum from a given target value (typically larger than the optimal distance but less than the maximum distance that separates the source and target nodes) has been conjectured to be in EXPTIME (see section "Conventions" of A depth-first approach to target-value search in the proceedings of SoCS 2009). In particular, this paper addresses this particular problem for  directed acyclic graphs (DAGs). A previous work is Heuristic Search for Target-Value Path Problem. There is event a US Patent of this algorithm US 2011/0004625.

I've been searching for related problems in other fields of Computer Science and Mathematics and strikingly, I have found none though this problem is clearly relevant in practice ---there are tons of opportunities to look for a specific target value instead of the minimum or the maximum path.

Do you know related problems to this or additional bibliographical references to this problem? Any information on this problem including studies of their complexity would be very welcome

Note: as already pointed out by Jeffe in cstheory, proving this problem to be in EXPTIME is trivial and the authors probably meant EXPTIME-complete.

What follows is taken from Tsuyoshi Ito's comment.

In the case of DAG, all paths can be enumerated in polynomial space and therefore the problem cannot be EXPTIME-complete unless PSPACE=EXPTIME. The natural decision version (given a DAG G, its vertices s and t, and numbers x and y, decide whether there is a path from s to t whose length is between x and y) is in NP.


Induced subgraph problem in trees Let $~G~$ be unweighted unordered tree. I have some number of pairs of this tree's vertices $~(u_1, v_1), \dots, (u_n, v_n)$. I need to construct a smallest subgraph of original tree such that for each pair $~(u_i, v_i)~$ there is path connecting this pair of vertices. "Smallest" in the sense that the number of edges being used is the least possible.

Does this problem have some special name? Can anyone offer efficient algorithm to deal with it?

First, notice that, in trees, the path between any pair of vertices is unique. This means that the sub-forest you want is the union of these paths.

To find them, do the following:

Pick any vertex to be the root of the tree.  Orient all the edges towards the root and store the distance from the root at each vertex.
To process a pair $(u_i,v_i)$ start a walk towards the root from the element of the pair that is farther from it.  (Break ties arbitrarily.)  As you walk, mark edges.  If the walk reaches the other item of the pair, stop.  Otherwise do the same thing from the other item of the pair.
Once all the pairs are processed, output the marked edges.

This is correct, since either $u_i$ and $v_i$ are on a path towards the root or the path between them goes through the root.  It's also too slow, since we may end up walking over the same edge multiple times, so we end up with $O(n^2)$ running time.

To speed this up, we can just use a union-find data structure.  The edges are partitioned into classes labeled by the lowest vertex they can reach by a path of marked edges.  Now when we walk, we can skip upwards every time we encounter a marked edge, at the same time merging any classes that we need to.

With this scheme, marked edges are encountered at most twice, so get a total of $O(\alpha(n)n)$, where $\alpha$ is the inverse Ackermann function.


Context free grammar for $bin(n)bin(n+1)^R$ It is pretty hard for me to understand, how binary representation of number may be context free. This language $L=\{bin(n)bin(n+1)^R : n \geq 0\}$ is context free.

Here, at 1.b, is a PDA which describes this language, so it is context free. I've tried to construct a context free grammar for this one, but I have no idea when to even start. How can I express a CFG binary representation of a number? I would be very glad for any suggestions.

Here is one solution:
$$
\begin{align*}
&S \to 01 \mid 1A1 \mid 1B1 \\
&A \to 1A0 \mid 0 \\
&B \to 1B1 \mid 0B0 \mid 0C1 \\
&C \to 1C0 \mid \epsilon
\end{align*}
$$

Explanation:

$A$ generates $1^n 0^{n+1}$, and so $1A1$ generates $1^{n+1} 0^{n+1}1$, which handles numbers whose binary expansion is $1^{n+1}$.
$C$ generates $1^n 0^n$, and so $0C1$ generates $01^n 0^n1$.
$B$ generates $w01^n0^n1w^R$, and so $1B1$ generates $1w01^n0^n1w^R1$, which handles numbers whose binary expansion is $1w01^n$.
Finally, $01$ handles $0$.


The Interleaved Transition System for 2 Independent and Concurrent Transition Systems This question is about Model Checking for Software Formal Verification
How do you model the joint behavior of 2 independent and concurrent transition systems?

Specifically, given the two independent and concurrent Transition Systems below; TS1 and TS2 (left to right).

A tutor proposed that the resulting Interleaving Transition System ITS is

I understand how all the shown states and transitions of this ITS were gotten, however, why is there no transition from state (l1,q1) to (l3,q2)--as would be expected if both TS1 and TS2 transitioned on action a?

By definition, the interleaving operator is not synchronized, so any transition in $TS1\ |||\ TS2$ corresponds to a transition in a single component while the other one remains in whatever state it is.

More generally, in process algebras like CSP, the parallel composition operator $||$ can be parameterized with a set of symbols on which to synchronize - for example, you could consider $TS1\ |[\{a\}]|\ TS2$, which has the same states and $b$-transitions as $TS1\ |||\ TS2$, but only two (synchronized) $a$-transitions $(l_1,q_1)\to(l_3,q_2)$ and $(l_2,q_1)\to(l_1,q_2)$. In particular, $|||$ is the special case $|[\emptyset]|$.

The point is that (together with additional operations like hiding) this allows you to represent a far greater variety of models of interaction.


Monte Carlo Tree Search in connect 5 tree design I'm trying to create a mcts ai for connect 5 algorithm. However, I'm confused on designing the tree. Here is a quick description of the algorithm:

The initial state, S0 is the board state where the AI places the stone, or in other words, the AI's turn. Is it correct that each node should be the AI's turn, not the humans?

In the expansion phase, you need to "create child nodes". In my game, the child nodes would each be a place where an AI can make a move. However, if I want to select the next avaliable AI move, I need to know where the enemy, or the human places the stone before the next avaliable AI move. I improvised by making it 2-layered: for every avaliable human moves, add every avaliable AI moves after the human plays. Is this the correct way to do it?

This is my current tree structure in an
Example: Each state has info of where black and white "stones"are placed.
the AI plays white, and Human plays black. Black plays first. state S0 would be the first move of the game.

                S0(black stones:[(2,2)],white stones:[])
                        /                            \
                       /                              \
                      /                                \
S1(black stones:[(2,2)],white stones:[(1,1)])        S2(black stones:[(2,2)],white stones:[(1,2)]
    |                                                       |
S3(black stones:[(2,2),(2,1)],white stones:[(1,1)])  S4(black stones:[(2,2),(2,3)],white stones:[(1,2)]

In you implementation you need to separate the game rules from the mcts search algorithm. Mcts does not need an evaluation like minimax. When calling random playouts all you need to do is keep making legal moves till the game ends and mark the playout with an outcome of win/loss.

your game rules need functions like
legal_moves, make_move, undo_move, is_game_over, winnerIs and maintain a states that represent the position

your mcts needs
mcts, ucb_sample, expand, random_playout, backpropogation

for states you need
position {visits, value or total/count}


Constructing PDA for $a^{2n} b^{3n}$ So I have been given the task of creating an PDA that recognises the language

$\{a^{2n} b^{3n} \mid n = 0,1,2,\dots\}$.

Am I right in thinking that it needs to have at least 3 times number of $b$'s than $a$'s?

So for example:
$aabbb$ would be accepted
$aaabb$ would NOT be accepted
However, how do I show that using JFlap because I am unfamiliar with the software?

The following pushdown automaton should do the trick. I publish this only because the existing answer can be improved upon. (Note, I am using $e$ to denote $\epsilon$- (or $\lambda$-) transitions.

The idea is that the left-hand part counts the number of $a$'s (modulo 2).
Each time it has seen two $a$'s, it pushes $3$ $b$'s onto the stack. Nondeterministically, the machine can change to the right-hand state. It then matches a $b$ from the string fro each $b$ on the stack.


Delete a node with 2 children in a binary search tree Recently in class we learned how to delete a node from a binary search tree. Since in a binary search tree, each node can have at most 2 nodes, there are 3 cases of deletion.

Case 1: The node is a leaf node. In that case you can simply delete the pointer to that node and free up the memory for that.

Case 2: The node has one child. In that case, you can connect the parent and child of that node and delete the pointer to and from the node you want to delete.

Case 3: The node has 2 children. Here is where I'm having a bit of a problem. Let's assume we have the following example.

I want to delete the node "4". To do this, I go to the largest integer node on its right side, i.e. "5" and swap their values. So 4 becomes 5 and 5 becomes 5. The I can simply delete the node "5" and I'll be done. Is this approach correct or am I missing anything?

Your approach works in your example, but not in general. For example, if the node with key 5 also has a left child with key 4.5, it will not be correct because the resulting tree is not a binary search tree anymore.

You have to replace the node to be deleted (4) not with its right child (5), but with its successor in the key ordering, which is the least-valued node in its right sub-tree (in your example, that is indeed 5, but in my example it would be 4.5, not 5).


Maximum value a variable can hold without documentation Suppose we work with some particular programming language (like C++) on some particular computer. Furthermore, we want to know which values are minimum and maximum for some particular numeric data type of this language. We can't use any specific tools of our language (like numeric_limits), and have no access to language or system documentation. Specifically, we don't know the lengths of our words. Is there an effective and rather precise way to find out the min/max we want to know?

We can certainly write some loop starting with zero and adding one at each step and wait for an overflow. But it is certainly not an effective way. We can write some loop and check some condition like $\log(\exp(n)) \stackrel{?}{=} n$, but I'm not sure whether this will answer our question.

The first step should be

count = 0
while (x*2 > x)
  x = x*2
  count++

to find the largest power of 2 that can fit into the variable. Note that doing +1 instead of *2 is not only much slower but also fails for floating point numbers (the gaps between large consecutive floating point numbers are bigger than 1). The above procedure should work for both numbers that roll over and numbers that reach infinity.

Once you have a rough estimate, you may perform a binary search in the range from estimate, to 2*estimate to find an exact bound.


Disproving using the definition of O Formally show that $0.1n + 10\sqrt{n}$ is not $O(\sqrt{n})$ using the definition of $O$ only.

I cannot find much on how to solve a problem like this, nor do i know how. Am I supposed to show some contradiction by trying to prove it is $O(\sqrt{n})$? Any help on how to answer this would be appreciated.

This is about measures of complexity, so we're interested in asymptotic behavior as $n \to +\infty$, and we assume that all the functions take only non-negative values ($\forall n, f(n) \ge 0$).

Here is one possible definition of big O (your definition might vary in details):

  Let $f(n),g(n)$ be two real-valued functions such that $f(n),g(n) > 0$ for all $n$. We say that $f(n) = O(g(n))$ if there exists an integer $N$ and a real $C > 0$ such that for all $n \geq N$, $f(n) \leq Cg(n)$.

Using the rules of logic, we get a definition of the negation of big O:

  Let $f(n),g(n)$ be two real-valued functions such that $f(n),g(n) > 0$ for all $n$. We say that $f(n)$ is not big $O(g(n))$ if for every integer $N$ and real $C > 0$ there exists $n \geq N$ such that $f(n) > Cg(n)$.

This is what you should prove. For each integer $N$ and real $C > 0$ you should find $n \geq N$ such that $0.1n + 10\sqrt{n} > C\sqrt{n}$.


Connection between KMP prefix function and string matching automaton Let $A_P = (Q,\Sigma,\delta,0,\{m\})$ the string matching automaton for pattern $P \in \Sigma^m$, that is

$Q = \{0,1,\dots,m\}$
$\delta(q,a) = \sigma_P(P_{0,q}\cdot a)$ for all $q\in Q$ and $a\in \Sigma$

with $\sigma_P(w)$ the length of the longest prefix of $P$ that is a Suffix of $w$, that is

$\qquad \displaystyle \sigma_P(w) = \max \left\{k \in \mathbb{N}_0 \mid P_{0,k} \sqsupset w \right\}$.

Now, let $\pi$ the prefix function from the Knuth-Morris-Pratt algorithm, that is

$\qquad \displaystyle \pi_P(q)= \max \{k \mid k < q \wedge P_{0,k} \sqsupset P_{0,q}\}$.

As it turns out, one can use $\pi_P$ to compute $\delta$ quickly; the central observation is:

  Assume above notions and $a \in \Sigma$. For $q \in \{0,\dots,m\}$ with $q = m$ or $P_{q+1} \neq a$, it holds that

  $\qquad \displaystyle \delta(q,a) = \delta(\pi_P(q),a)$

But how can I prove this?

For reference, this is how you compute $\pi_P$:

m ← length[P ]
π[0] ← 0
k ← 0
for q ← 1 to m − 1 do
  while k > 0 and P [k + 1] =6 P [q] do
    k ← π[k]
    if P [k + 1] = P [q] then
       k ← k + 1
    end if
    π[q] ← k
 end while
end for

return π

First of all, note that by definition

$\delta(q,a) = \sigma_P(P_{0,q}\cdot a) =: s_1$ and
$\delta(\pi_P(q),a) = \sigma_P(P_{0,\pi_P(q)}\cdot a) =: s_2$.

Let us investigate $s_1$ and $s_2$ in a sketch:

[source]

Now assume $s_2 > s_1$; this contradicts the maximal choice of $s_1$ directly. If we assume $s_1 > s_2$ we contradict the fact that both $s_2$ and $\pi_P(q)$ are chosen maximally, in particular because $\pi_P(q) \geq s_1 - 1$. As both cases cases lead to contradictions $s_1=s_2$ holds, q.e.d.

As requested, a more elaborate version of the proof:

Now we have to show $s_1=s_2$; we do this by showing that the opposite leads to contradictions.

Assume $s_2 > s_1$. Note that $P_{0,s_2} \sqsupset P_{0,q}\cdot a$ because $P_{0,s_2} \sqsupset P_{0,\pi_P(q)}\cdot a$ and $P_{0,\pi_P(q)} \sqsupset P_{0,q}$ by definition of $s_2$. Therefore, $P_{0,s_2}$ -- a prefix of $P$ and a suffix of $P_{0,q}\cdot a$ -- is longer than $P_{0,s_1}$, which is by definition of $s_1$ the longest prefix of $P$ that is a suffix of $P_{0,q}\cdot a$. This is a contradiction.

Before we continue with the other case, let us see that $\pi_P(q) \geq s_1 - 1$. Observe that because $P_{0,s_1} \sqsupset P_{0,q}\cdot a$, we have $P_{0,s-1} \sqsupset P_{0,q}$. Assuming that $\pi_P(q) < s_1 - 1$ immediately contradicts the maximal choice of $\pi_P(q)$ ($s_1 - 1$ is in the set $\pi_P(q)$ is chosen from).

Assume $s_1 > s_2$. We have just shown $|P_{0,\pi_P(q)}\cdot a| \geq s_1$, and remember that $P_{0,\pi_P(q)}\cdot a \sqsupset P_{0,q} \cdot a$. Therefore, $s_1 > s_2$ contradicts the maximal choice of $s_2$ ($s_1$ is in the set $s_2$ is chosen from).

As neither $s_1 > s_2$ nor $s_2 > s_1$ can hold, we have proven that $s_1 = s_2$, q.e.d.


Is Weighted Averages the Best Method to Aggregate Information? I'm working on a recommendation system. My system uses user's past rating data, to predict future ratings.

I designed mathematical methods for generating recommendation algorithms that allows me to generate an unlimited number of recommendation algorithms (given a large enough set of relevant ratings).

I intend to aggregate the results from all this algorithms to compute a final expected rating of the user. So I thought of taking the weighted averages of the expected ratings of each algorithm to use to calculate a final expected rating.

Basically I either:
1. Assign weights based on the amount of information (ratings collected).
2. Assign weights based on the accuracy of the algorithm used.

The algorithms arrive at their answer via different means, and it is possible that two may give the same answer, but they may take into account different information and/or use different inferential techniques on that information.

So if an accuracy of 1 means there's no deviation between the algorithm's expected ratings, and the user's actual ratings, and an accuracy of 0 means there's maximum deviation between an algorithm's expected ratings and user's actual ratings, we may get $\{Al_1, Al_2, Al_3\}$ with accuracies of $(0.9, 0.85, 0.92)$.

I have a minimum information and/or accuracy threshold that I would use to filter the algorithms to assign weights to (I have not yet figured out what this threshold would be, and as it may vary on a per user basis, I want to leave determining the threshold to an ML system.

My question is this:

  Is weighted averages the Best methods for me to aggregate the data provided by my various algorithms/infer from it?
  If not, what other methods are more apt for the problem at hand?

A weighted average might or might not be the best method.  This will depend on (a) the nature of the algorithms, and (b) what objective function you are trying to minimize.

Let me give you a sample set of assumptions.  Suppose we treat the predictions from the recommendation algorithms as independent random variables (e.g., because each recommendation algorithm was trained independently).  Also,  suppose we wish to minimize the variance of the final prediction.  In other words, our loss function is the $L_2$ loss: if our prediction was $Y$, and the correct value was $\tilde{Y}$, then the loss (penalty) is $(Y-\tilde{Y})^2$.

Then in this case we can find the optimal set of weights.  In particular, in this case, if we restrict ourselves to linear combinations, the optimal set of weights is inversely proportional to the variance of each estimator.  Suppose $X_1,\dots,X_n$ are the predictions from our $n$ recommendation algorithms.  Suppose that we have measured the accuracy of each recommendation algorithm by measuring its $L_2$ loss on a validation set; in other words, we know the variance $\text{Var}(X_i)$ for each $i$.  Here $\text{Var}(X_i)$ is a measure of the accuracy of the $i$th recommendation algorithm: the larger the variance, the larger the expected $L_2$ loss, and thus the less accurate the prediction is.  Then the optimal linear weighting is to select a final prediction $Y$ by

$$Y = c_1 X_1 + \dots + c_n X_n,$$

where we choose the weights

$$c_i = {a_i \over a_1 + \dots + a_n}$$

where

$$a_i = {1 \over \text{Var}(X_i)}.$$

Is a linear combination optimal (as opposed to other, nonlinear methods of combining the predictions)?  In this situation, if we additionally know that the errors made by each recommendation algorithm have a Gaussian distribution, then yes, a linear combination is optimal.  If the errors have a different distribution, then some other combination might be better.

As you can see, this will depend on the loss function we select, and on other assumptions.  That said, in practice, a linear combination (i.e., a weighted average) is often a reasonable choice.

There's lots written about this sort of thing in the statistics literature.  For instance, the above discussion is just a restatement of the fact that the average is the optimal estimator of the mean of a Gaussian distribution (i.e., it minimizes the mean squared error).  See, e.g., https://en.wikipedia.org/wiki/Estimator, https://en.wikipedia.org/wiki/Mean_squared_error, https://stats.stackexchange.com/q/81571/2921, https://stats.stackexchange.com/q/97765/2921, https://stats.stackexchange.com/q/48864/2921, https://math.stackexchange.com/q/9032/14578.


Operating System code suffers more cache misses than user code I was going through the text of the book Computer Architecture: A Quantitative Approach. It has a section in Chapter 5 where it discusses the fact that OS code undergoes more cache misses as compared to user code. Here is the text:

  Although the user code executes more instructions, the behavior of the operating
  system can cause more cache misses than the user processes for two reasons
  beyond larger code size and lack of locality. First, the kernel initializes all pages
  before allocating them to a user, which significantly increases the compulsory
  component of the kernel’s miss rate. Second, the kernel actually shares data and
  thus has a nontrivial coherence miss rate. In contrast, user processes cause coherence
  misses only when the process is scheduled on a different processor, and this
  component of the miss rate is small. This is a major difference between a multiprogrammed
  workload and one like the OLTP workload.

What is the first argument trying to explain?
My doubt is that although the kernel has to initialize the pages for allocation to a user, it(the kernel) is not required to retrieve data from those pages into cache. That is the user code's responsibility. Hence, the argument seems confusing.

There's cache misses when you access a page for the first time, then you get hits. Since the kernel initialises the page, it gets all the cache misses. Then it passes the page to the user code, which gets cache hits.

The same misses would happen in user code if the kernel didn't initialise the page.


Achieving better than the theoretical False Positive Rate for Bloom Filters I implemented a standard Bloom Filter in C++, and tested it on different sizes, with varying values of the ratio ${c = n/m}$ where ${n}$ is the size of the filter, and ${m}$ is the number of elements inserted.

For a Bloom Filter, I created ${k}$ Hash functions, and set the value in the filter for each Hash Index returned. Here's a graph of the results I obtained from my tests:

The problem from the graph is clear, I am getting False Positive rates that are better than the Theoretical value. The theoretical value is based on the assumption that each Hash Index is equally likely, which is:

$
Pr(H(a) = 1)^k = 1 - Pr(H(a) = 0)\\
               = (1 - (1 - 1/n)^{km})^{k}\\
               = (1 - e^{-k/c})^{k}
$

Using $k = c \ln(2)$

$
Pr(H(a) = 1)^{k} = (1 - e^{-\ln(2)})^{k}\\
                 = (1/2)^{c \ln(2)}\\
                 = 0.6185^{c}
$

All my tests are based on the optimal value of $k = c \ln(2)$, and the theoretical line is a plot of $0.6185^{c}$. My concern is that my False Positive rates are consistently better than the theoretical. Does this mean that my implementation is incorrect, or is it a likely possibility given the large sizes of the Bloom Filters and the efficiency of the hashing algorithm?

I appreciate any guidance on this.

Your question includes the equation

$$
(1 - (1 - 1/n)^{km})^{k} = (1 - e^{-k/c})^{k}
$$

But that is not actually an equation; it is only an approximation.


Big theta of function with multiple types of n I have the following function:

$\displaystyle\frac{n \cdot 7^n+\frac{8}{n!}}{(n+7) \cdot 7^n}=\Theta(1)$

I don't how they come to this. What is the proper way to analyse a function to theta notation?

You can calculate the limit of the function for $n\to\infty$:
\begin{align}
\lim_{n\to\infty}\frac{n\cdot7^n+\frac{8}{n!}}{(n+7)\cdot7^n}&=\lim_{n\to\infty}\frac{n\cdot7^n}{(n+7)\cdot7^n}+\lim_{n\to\infty}\frac{\frac{8}{n!}}{(n+7)\cdot7^n}\\
&=\lim_{n\to\infty}\frac{n}{n+7}+\lim_{n\to\infty}\frac{8}{(n+7)\cdot7^n\cdot n!}\\
&=1 + 0\\
&=\Theta(1)
\end{align}


How is the R-Tree's MBR size determined? Changes to MBR? The R-Tree creates 'rectangles' to index 2D data. How is their size calculated exactly? What happens to the performance by changing this parameter i.e. the size of this rectangle/MBR? Number of overlaps, area covered change but can this speed up some kind of queries or build a smaller index?

First of all, let us have some background. There are variants of Guttman's r-tree that have different splitting heuristics (e.g. Sellis' r+-tree, which involves inserting an item multiple times into a tree; and Beckmann's r*-tree, which takes into account area, margin, overlap). Also, there are variants that are more suitable for higher dimensions (e.g. Berchtold's x-tree, which uses split history and supernodes). You can improve any of the above structures using bulk loading, which can guarantee zero overlap between rectangles at the same level.

Rectangles used typically are minimum bounding rectangles (MBR's) that may fit your data well (if you are using orthonormal rectangles as with data mining), or may have to be used as approximations (if you are trying to detect intersections between polytopes).

You can find MBR's, which are possibly described using upper-left point and lower-right point, by taking extreme value pairs for each dimension.

Note also that points are degenerate rectangles and that we can form MBR's for collections of MBR's.

For example, if we had $P$ = $\{(1, 0), (2, 1), (3, 2), (4, 3)\}$, and right is large $x$ and up is large $y$, an MBR for these points could be $(p_\text{upper-left}, p_\text{lower-right})$ = $((1, 3), (4, 0))$.

There have been attempts to quantify how much time a query on an r-tree takes, but intuitively what is happening is that we may spend more than $O(k \cdot \log(n))$ time for $k$ matches, even though depth is $O(\log(n))$, because we could go down many branches without reaching a match. If you are interested, there are certain operations one could perform on an r-tree that take more time but have clean running time asymptotic values if you include a "look-ahead" query at each node we visit. In the end, however, with a regular r-tree and with regular queries, loosening the MBR's leads to diminished performance.


find all paths from source to destinations and then calculate the path with minimum cost I am trying to solve one problem. Please refer complete problem statement before proceeding.

You are given a road network, with N cities and M bi-directional
roads. Each road has some positive amount of tax associated to
it,meaning if there is a road connecting cities A and B with tax C,
you will need to pay C rupees to the government every time when you
use this road.
but you have a wildcard which can be used at most K times and when you
use wildcard while using a road, you do not need to pay tax associated
with the road.
You are planning to visit one city this weekend, due to limited budged
you want to estimate minimum passible cost from you home-city to every
other city, so that you can choose the destination according to the
budget, your home-city is a city numbered with 1.

For solving above problem I am Following this approach. Step 1) Calculate all the path between vertices u,v. Step 2) For a Path p=[i-j-k-l] do following
   for(int i=0;i<k;i++){
           int weight=findEdgeWithMaxWeight(p);
     cost of path p=cost of path-weight;
    }

I am repeating this step2 for all the paths for u,v and at last I am choosing the path with minimum weight. As my answer.
Consider following diagram to visualize my approach.

But problem with above approach is that I am have to calulate all the path between u,v to get the answer. Is there any way to get the optimal path with out calculating all the paths?
Edit: Hope Problem is bit clearer now.

One way to solve this is a Dijkstra variant with the following DP-Relaxation:
The distance array will be 2-dimensional array for which $Dist[i][j]$ is the shortest path from the source to the city $i$ using $j$ wildcards.
When processing a vertex $i$, for an incident edge $e\{i, j\}$ with cost $c$ we update as following:(for all values of k)
$Dist[j][k] = min(Dist[j][k], Dist[i][k] + C)$
$Dist[j][k] = min(Dist[j][k], Dist[i][k-1])$
The correctness follows from the fact that we are trying all placements of the wildcards and keeping the so-far-optimal.
The runtime is the usual Dijkstra runtime multiplied by the $K$ factor in the relaxation i.e. $O((e+n\log(n))k)$ using Fibonacci Heaps.


Find any of the 3 largest among $n$ elements I have two questions. Both are about finding any of the 3 largest among $n$ elements.

How to show that $n-3$ comparisons suffice to find any of the $3$ largest among $n$ given numbers $(n \geq 4)$?
How to show that $n-3$ comparisons are necessary to find any of the $3$ largest among $n$ given numbers $(n \geq 6)$?

My Idea: I have tried to solve 1. using a heap but could not derive any such bound.

The place where I found this question gave one hint which said to analyze the number of connected components in a comparison graph.

I shall appreciate if anyone can throw some light on a comparison graph.

I don't know what do you mean by comparison graph. However, here is my solution for question 1.

Suppose you have a list of $m$ elements, and you want to find the largest element. You can do this with $m-1$ comparisons.

Do you know how to proceed?

    You can simply ignore the first two elements in your list. This gives you a new list $L'$ of $n'=n-2$ elements, You can determine the largest element of $L'$ with $n'-1=n-3$ comparisons. This element is one of the three largest.


conversion of this grammar to CNF My task is to convert the following grammar to CNF: $S \to SS \mid (S) \mid \lambda$

after removing lambda productions: $S\to SS,  S\to (S),  S\to(), S\to S$

after removing unit productions: $S\to SS, S\to (S), S\to()$

I got upto this point. Do not know how this grammar will be in CNF coz I am not sure if using () makes the grammar illegal. Need help how to proceed and make this grammar in CNF?

Yes, the grammar you noww have is still illegal. For CFG you can only have two types of productions $A\to BC$ and $A\to a$ where $A,B,C$ are nonterminals (variables) and $a$ terminal.

It is best to add additional variables that introduce the brackets $A\to ($ and $B\to )$.
Now you can use $S\to AB$ instead of your production $S\to ()$.

Finally, try to get rid of $S\to (S)$. It is too long and contains both terminals and nonterminals on the right side.


Size of Propositional Formula I am study this lecture The Complexity of Propositional Proofs. Here there is a term size of propositional formula (page 2),

  Every tautology $\tau$ on $n$ variables has an $F$-proof in which thera are at most $2^{O(n)}$ formulas, each of which has size polynomial in the size of $\tau$

but here doesn't define that term. I have googled this term and I have found something similar length of propositional formula, which is defined as

  The function $L(P)$ giving the length of a formula is defined by
  structural induction as follows:

$L(p_i) = 1$, for all atomic formulas $p_i$
$L(P ∧ Q)$ = 1 + $L(P ) + L(Q)$,
$L(P ∨ Q) = 1 + L(P ) + L(Q)$,
$L(¬P) = 1 + L(P)$.

My question is: Is the length and size of a formula the same?

There are two possible ways of defining what the length or size of the formula is:

According to the size of a reasonable (and fixed!) binary encoding.
According to the size of a reasonable (and fixed!) encoding over an infinite alphabet which includes symbols for all possible variables.

The definition you mention, for example, is what you get if you apply the second type of definition with respect to the prefix or postfix encoding of a formula.

Note that these two "approaches" don't by themselves defined a concrete measure of size. In cases where it matters, a concrete definition will appear, for example the one you quote. In many cases, however, the exact definition makes no difference since all definitions are "polynomially related", that is, the size of a formula varies at most polynomially between the different definitions. Your quote, for example, cares only about the size of the formulas being polynomial, and so an exact definition isn't important.

In other places, however, it is mentioned that some formula has size $O(n)$. Here the exact encoding still doesn't matter, but there is a real difference between the two options mentioned above. Consider for example the formula $x_1 \lor \cdots \lor x_n$. Under the second option, such a formula has size $\Theta(n)$. However, any reasonable binary encoding of this formula will have size $\Theta(n\log n)$, since storing the indices also takes space. From the author's statement it follows that he uses a definition of the second kind.


Linearity of Expectation I'm taking a course on Coursera about approximation algorithms for fun and one of the modules uses probability to analyze the cost of a linear program with randomized rounding solution to the set cover problem.

One of the problem set questions is a basic probability question and is as follows:

You ask ten of your friends to give you one dollar (coin) each so that you can buy your favourite pizza.

When you reach the pizza place you realize that it's closed. So you return the coins to your friends by giving each of them a random coin.

1) How likely is that each of them gets the coin they put back?

2) How many of them will get in expectation the coin they put back? (Try to prove this elegantly using techniques discussed in the course)Define the random variables you use.

3) Now suppose that you take one coin to buy a coffee somewhere else. You redistribute the others dollar coins giving each of your friends one coin chosen uniformly at random. How many of your friends will get in expectation the coin they put back?

I've solved the first two parts and I'm thinking for the third part that I should define a random variable Xi that represents whether or not persion i get the coin back that she put in and E[Xi] is the probability that she gets it back.

The probability that she gets it back is 9 / 10 * 1 / 10 = 9 / 100. There's a 9 / 10 chance that her coin was not the coin that I bought coffee with and a 1 / 10 chance that she picks her coin or is left out as there are 9 coins for 10 remaining people.

Taking X as the number of folks that get their coins back I have

E[X] = sum(E[Xi]) over all persons E[X] = 90 / 100 = .9 people are expected to get their coin back.

Is my reasoning sound here? If not, can somebody show me the error of my ways?

Thanks so much,

Stead

Your approach looks good. Let's just write it clearly. Let's look at $E[X_1]$.

With probability $1/10$ the first coin was used to buy the coffee, thus the value is $X_1=0$.

With probability $9/10$ we are back in the situation of part II (we can add a new "Gold" coin - the party that gets this coin will not get his dollar back), so the expectation of this case is just like in Part II.

Adding both cases (with the appropriate weight) should solve your question, for $X_1$, and by the linearity of expectations, and since all parties are symmetric, the answer is $10 E[X_1]$.


LR(1) - Items, Look Ahead I am having diffuculties understanding the principle of lookahead in LR(1) - items. How do I compute the lookahead sets ?

Say for an example that I have the following grammar:

S -> AB
A -> aAb | b
B -> d

Then the first state will look like this:

S -> .AB , {look ahead}
A -> .aAb, {look ahead}
A -> .b, {look ahead}

I now what look aheads are, but I don't know how to compute them. I have googled for answers but there isn't any webpage that explains this in a simple manner.

Thanks in advance

There are two ways that lookaheads 'come into being'. The first is that the start production $S' \rightarrow S$ has lookahead $\$$ in the initial state of the $LR(1)$ automaton. Hence, $S' \rightarrow \bullet S, \$$ is an item in the initial state.

Pendantry note: we therefore accept in the state containing the item $S' \rightarrow S \bullet, \$$ on lookahead $\$$ and we pad any input with $\$$.

The rest of the lookaheads are computed from lookaheads which we have already computed. If we have in some state an item $A \rightarrow \alpha \bullet X \beta, l$ (so $l$ is the lookahead and $X$ is a nonterminal) and another production $B \rightarrow \gamma$, then for every $a \in \mathsf{FIRST}(X \beta l)$ we add in the completion step for that state the item $B \rightarrow \bullet \gamma, a$.

In other words, the lookahead is some terminal that can appear as the first terminal in a string derived from $X \beta l$. As $l$ is a terminal and appears at the end of $X \beta l$, this means that $X \beta l$ does not derive the empty string (so we don't need $\mathsf{FOLLOW}$). Also note that we only ever derive items and therefore new lookaheads from items that already have lookaheads, so there is no problem there.

The precise definition of $\mathsf{FIRST}$ is: $\mathsf{FIRST}(a \alpha) = \{a\}$ if $a$ is a terminal, $\mathsf{FIRST}(A \alpha) = \mathsf{FIRST}(A)$ if $A$ is a nonterminal and $A$ does not derive the empty string, and $\mathsf{FIRST}(A \alpha) = \mathsf{FIRST}(A) \bigcup \mathsf{FIRST}(\alpha)$ if it does. $\mathsf{FIRST}(A)$ is the well-known relation denoting the first terminals in the strings derivable from $A$ (which is also used in $LL(1)$).


Landau Notation: Why is O(f) (not) the set all g < c*f? I am somewhat confused here about the Landau notations. Let's say we are dealing with function from $\mathbb{N}$ to $\mathbb{R}$. Then we can define $\mathcal{O}(f) = \left\{ g : \mathbb{N} \to \mathbb{R} | \exists c > 0 \text{ such that } g \leqslant cf\right\}$. Ok, so every function $g$ that is asymptotically smaller than $f$ is in this set. So if we have an algorithm $A$ that runs at most exactly $n^2+10$ steps, then
$g1 : \mathbb{N} \to \mathbb{R} \text{ with } n \mapsto n^2 \in \mathcal{O}(A)$.
But also
$g2 : \mathbb{N} \to \mathbb{R} \text{ with } n \mapsto n \in \mathcal{O}(A)$
or even
$g3 : \mathbb{N} \to \mathbb{R} \text{ with } n \mapsto 0 \in \mathcal{O}(A)$
satiesfy the condition to be elements of $\mathcal{O}(A)$. So, why would normally only $g1$ be the function of which one would say $g1 = \mathcal{O}(A)$ ?
I understand the $=$-sign is formally incorrect and just a convention, but if $g2$ and $g3$ also are in $\mathcal{O}(A)$ why define $\mathcal{O}$ this way, if $g1$ is the only function we care about to describe the asymptotic complexity of $A$?
Edit
So, I see I had misunderstood the idea a little. So far I thought $\mathcal{O}$ would take an algorithm and return how long it runs asymptotically. So, what $\mathcal{O}$ actually does is the following>:
If we have an algorithm $A$ saying that
$$\forall c > 0. \forall x \in domain(A).\lim_{n\to\infty} T(A(x)) \leqslant cn$$ would be the same as $$T(A) \in \mathcal{O}(n)$$
Is that correct?? Something looks still wrong about that.
($T$ being the function that returns the number of steps the computation required.)

There are at least three fundamental misunderstandings, here.

$O(\cdot)$ only makes statements about large enough inputs to the function. It's not that there exists some $c$ such that $g\leq c\,f$ for all $n$, but just for all large enough $n$.
The argument of $O(\cdot)$ is a (mathematical) function. If $A$ is an algorithm, it makes no sense to write $O(A)$: it doesn't type-check. In particular, for an algorithm $A$, we don't talk about "the order of $A$". Rather, $O(\cdot)$ is a way of comparing mathematical functions: $O(f)$ is the set of all mathematical functions $g$ such that $g(n)\leq c\,f(n)$ for some $c$ and all large enough $n$.
$O(f)$ is the set of all mathematical functions $g$ such that $g(n)\leq c\,f(n)$ for some $c$ and all large enough $n$. So it's simply not true that, in your example, $g_1$ would be the only function you'd describe as being $O(n^2+10)$.

$O(\cdot)$ is defined that way because it's useful to do so: it's a way of comparing functions and it doesn't care what you use those functions for. ($O(\cdot)$ doesn't care about complexity theory, just as the meter doesn't care about Mount Everest.) So, when we say that the running time of an algorithm is, say, $O(n^2)$, we just mean that, for large enough inputs, it's no worse than some constant times $n^2$. Often, we say it that way because we don't know anything more precise.  In the same vein, I'm pretty sure that you have less than a million dollars in the bank but It would be hard for me to find out how much less.

In cases where we do know something more precise, we might use $\Theta(\cdot)$, or we might use separate $O(\cdot)$ and $\Omega(\cdot)$ bounds.  For example, we might say that the running time of some algorithm is $\Theta(n\log n)$, meaning that there are constants $c_1$ and $c_2$ such that, for all large enough $n$, the running time is between $c_1n\log n$ and $c_2n\log n$.  For some other algorithm, we might only be able to prove that its running time is $O(n^3)$ and $\Omega(n^2)$, meaning that there are constants $c_1$ and $c_2$ such that, for large enough $n$, the running time is between $c_2n^2$ and $c_1n^3$.


Is the halting problem pointless? Some programs run quickly, some programs run slowly, and some spend all eternity whirring and whizzing without ever halting. The halting problem uses a thought experiment to prove that there cannot exist a program which can itself examine any arbitrary program and tell the user whether the program being examined will halt.
However, the thought experiment involves programs that were, frankly, designed to act in a way no sane programmer would ever want. Programs that are intentionally designed to halt without producing any useful output, programs that are designed to run indefinitely without halting. As addressed in the answers to the question Is there a subset of programs that avoid the halting problem, the halting problem doesn't apply to all programs. In the extreme case, the following programs would be trivial to analyze:
// Program 1:

while true {}

// Program 2:

print("I really can't tell with this one")

Rather, the halting problem merely indicates that there will always be some programs that can't be analyzed for halting. Those that can be analyzed fall into a certain class of programs that is reasonably well-researched and well-understood, and seems to align quite neatly with the class of useful programs. As for the original proof, while the logic holds, the programs used therein are poor indicators of code a human would actually write, and beg a certain question:
Is it possible that the halting problem only applies to useless programs?

The point of the halting program IMO is not to show that you can't check whether an arbitrary program can halt--that's not a very interesting fact on its own. The point of the halting program, is to use "reduction", to go on and prove that a (very large number of) procedures you might like to have a tool do are also impossible in general:

Deciding whether two programs are the same (including, whether a program always outputs "true"). This is true even for even many simple definitions of "program".
Deciding whether a mathematical fact is true or false
Determining the longest time a program could run
Checking whether a particular line of code like an error condition, is possible to reach

Of course, much like NP-complete problems, it may still be worthwhile to work on heuristic versions or special cases. But knowing that it's impossible in general, saves us a lot of time trying to come up with a perfect version--after all, we usually want a perfect version if we can get one. And knowing that a problem is impossible in general, is a good hint that it may be hard in specific cases you're likely to run into (checking if two programs are identical for example, is actually really hard in practice).
I think it's fairly reasonable to assume that for any program a human would write, the answer is "yes, it halts"--otherwise it's a bug! So the class of "programs a human would write on purpose" is not really that interesting to look at.
A more interesting question is, "what sorts of things in real programming, lead to problems analyzing whether the program halts?". For example:

Almost all opcodes (ex. addition) complete
Bounded loops complete (if the inner loop completes)
Function calls with no recursion complete (if the body of each function does)
Arbitrary while loops are hard to analyze
Global variables may be hard to analyze
Recursive function calls are hard to analyze

It's quite possible to invent a language (Charity, Epigram, and LOOP are academic/niche langauges, but you can also just imagine making a list of all these features and banning them from Java) where all programs halt. The challenge then becomes, can you express what you want to do in this language?
Edit: For an example of a practical program that is hard to analyze, here is bubble sort in python:
swapped = True
while swapped:
    swapped = False
    for i in range(0, len(list)-1):
        if list[i] > list[i+i]:
            list[i], list[i+i] = list[i+1], list[i]
            swapped = True

As a human, we can tell that this program halts for all inputs. It's much harder to get a computer to realize the same thing.


data carried during TCP control flow I am learning about TCP control flow and came across a question about how much data is carried by the 4th segment. The answer is supposed to be 1200 (2230 - 1030) but I don't quite understand why.

By definition, I know that the acknowledgement number is telling the other side what is next expected from it. Thus 5 is the server acknowledging everything up to 2230 and telling the client that the server is expecting 2230 next, while 3 is the client acknowledging everything up to 3848 and telling the server that it next expects 3848. But I still don't understand why we're considering segment 5 and segment 2? If it's only "expecting" then how do we know how much data is being carried?

The data that will be carried in the 4th segment is 1200 why?we can know it by simpley look at the sequence number of the 6th packet -a packet's sequence number is in simple words:"im sending data from this certain number"
if we take a look at the 3th packet we can see that it was sent from the client to the server with a sequence number of 1030 and we can see in the 6th packet that the sequence number of it is 2230 which means a total 2230-1030=1200 of data was sent from the clinet to server in the 4th packet


Minimum Bounding Quadrilateral In an image processing project (using opencv with python), I am trying to detect as precisely as possible the location of a rectangular object in a photograph. My final goal is to output the 4 corners of the object.

For example, an image could look like this:

In the first stage I am able to detect an approximate boundary for the image, like so:

Now, I have the above red convex polygon.

Next, I would like to compute the Minimum Area Bounding Quadrilateral, and this is where I'm stuck.

My question is, given a convex polygon, what is an efficient algorithm to find a minimum area bounding quadrilateral?

Thanks!

The fitting of a minimum area quadrilateral to a set of points is an uneasy problem, and I believe that simpler approaches are good enough.

Notice that the corners are rounded and cannot be used as such. So you'd better fit straight edges and intersect them to obtain the quadrilateral.

One approach is by the Hough transform. To make it maximally efficient, I would recommend to process four tight areas or interest around the edges of the axis-aligned bounding box. This will make processing much faster, avoid false positives and avoid any ambiguity on the correspondences.

You can also sample points on the four sides and fit a straight line by total-least squares, or by some robust line fitting method.

If you want to make sure that the fitted lines don't cross the shape at all, you can handle the four sides independently and consider a partition of the plane in the four quadrants delimited by the diagonals (even if they are approximate). In every quadrant, you will find the minimum area triangle formed by the line against an edge of the convex hull. Just try every edge of the convex hull in turn.

[Technically, it is possible that the minimum is achieved with a line through some vertex of the convex hull, with an intermediate angle, i.e. not in the direction of a hull side. We should also check if the area function is always unimodal in terms of the line angle. IMO these refined considerations can come later.]


new language accepted by FA when new transitions are added to a FA? found this question online and I am trying to solve this question. I have solved this question but I think I might be missing some cases. Could someone verify if my answers are correct?
Let N = (Σ ∪ {λ}, Q, δ, q0, {qf }) be a λ − NFA and let L = L(N) be the language accepted by N. For N assume q0 has no incoming transitions and qf has no outgoing transitions. For each of the following FAs that are modifications of N describe the language accepted by each in terms of L.
(a) A λ-transition is added from qf to q0.
(b) Add a λ-transition from q0 to every state reachable from q0 along a path with labels that may be λ or symbols from Σ.
(c) Add a λ-transition to qf from every state that reach qf along some path.
(d) The FA where both (b) and (c) are done.

a) L+
b) For this one I have defined a function suff, this takes all the valid strings in the original Language and generates new stings from them. For example, if L = {112,12} where alphabet is {1,2}
Then, suff(L) means suff(112) + suff(12)
where suff(112) = {112,12,2}, keeps chopping off the first symbol until u get empty string
Similarly, suff(12) = {12,2}
So, the final answer would be suff(L) + the empty string. (Is this correct?)
C) for this one, I defined pre which is similar to suff but chops off the last symbol.
pre(123) = {123,12,1}
pre(112) = {112,11,1}

So, the final ans is pre(L) +  empty string
d) I need help with this one..

Your answers to (a), (b), and (c) seem correct to me. Here's something to think about for (d).
Hint for (d): Let's say $s = s_1s_2...s_k \in L$, and on input $s$ the original transition function follows the path $P = q_0, q_1... q_f$. Let $q_{s_i}$ denote the state $q_i$ closest to $q_f$ in $P$ after only reading up to $s_i$ in the original NFA. What are the strings can I generate by doing the following in the NFA defined by (d)? $\lambda$-transition from $q_0$ to $q_{s_i}$, follow $P$ up to $q_{s_j}$ (for any $1 < i < j < k$), and then $\lambda$-transition to $q_f$ and accept.


Can you suggest a topic for a Bachelor Thesis in Mathematics that is related to Machine Learning? Context
I am a final year Bachelor of Mathematics student and next semester I will write my Bachelor thesis.
My interests are in Machine Learning (ML) and I will do a master in ML next year. More specific sub-fields I like are

Deep Learning
Computer Vision
Natural Language Processing
Reinforcement Learning

And my interests outside of ML and mathematics include

Self-driving cars (e.g. Tesla)
Rocket and space exploration

more vaguely, I find tech interesting as a whole.
Question
I am looking for a thesis which would bring me as close as possible to the field of ML. Do you have topic recommendations ?
BUT my Bachelor is in Mathematics therefore I shall not write a thesis in Computer Science as it would not be accepted by my study director.
Some thoughts
I know some people who were in my case. One of them for instance discovered and proved some convergence results in the context of Gradient Descent. Maybe this will inspire you with your answers.
Thanks in advance!

PS: This is a duplicate of my original question on the Math Stack Exchange but I thought that people on the Computer Science Stack Exchange could bring a different point of view.

I would like to make two points clear as a researcher:

Mathematics is a very broad discipline. When you're on bachelor level it is still appropriate to call it "Mathematics" but already in Masters, you'll need to specialize! Youll have to choose a branch and then you won't be "a mathematician" you'll be Statistician, a topologist, graph theorist, category theorist etc. This being said you need to ask yourself which branch you're most interested in? This leads to the next point:

The fact that you're interested in Machine Learning already narrows it down to  Probability & Statistics, Linear Algebra, Multivariate Calculus. And here I would say that any topic that falls within these categories will help you later along the road.

Bachelor Thesis is a piece of scientific work that's why it is called "Bachelor". You are supposed to do research and produce new knowledge regardless of how small or significant it will be. This forum cant do it for you.
Pick something YOU are interested in from Probability & Statistics, Linear Algebra or Multivariate Calculus and explore the topic. Once you start you'll inevitably get questions that need addressing. If you get stuck pick a classic problem (for example Knight's tour) and systematically break it down.


Tight Bound of the Insertion Sort I'm asking this question because I was confused by some of the articles in the internet.

I already know that the asymptotic lower and upper bounds of insertion sort is $\Omega(n)$ and $O(n^2)$.

Therefore according to my understanding of the $\Theta$ notation, we cannot make a statement about the $\Theta$ for all cases.

So is it $\Theta$ undefined for the insertion sort?

Or is it $\Theta(n^2)$?

So is $\Theta$ undefined for insertion sort?

This question contains a category error. It's like saying, "I know that Donald Trump has a height of at least 5 and at most 7. So are numbers undefined for Donald Trump?

$\Theta$ is notation for expressing the growth rate of mathematical functions. "Insertion sort" is not a mathematical function, so if you want to talk about $\Theta$ and insertion sort in the same sentence, you need to say what property of insertion sort you're measuring with a mathematical function that you wish to describe with $\Theta$.

We measure the resource usage of algorithms in terms of the length of the input, which is usually denoted $n$.  You've proposed a function which is the number of execution steps of insertion sort on some input. However, this is a function of the input itself, not of its length. Some inputs of length $n$ will take roughly $n$ steps to sort (I'm using "roughly" to hide constant factors), and some inputs of length $n$ will take roughly $n^2$ steps. So you can't write this as a function of $n$ at all – the number of steps required isn't just a function of the length of the input but, rather, it's a function of the whole input.  Because the thing you're trying to measure isn't a function of the length of the input, you can't directly measure it using $\Theta$ at all.

So we need to come up with a function that does just depend on the length of the input. Two natural functions are the best-case and worst-case number of execution steps. We know that, for an input of length $n$, the best case is that insertion sort finds that the input is already sorted, and in this case, it takes a linear number of steps.  No more, no less, so we're entitled to say that the best-case running time of the algorithm is $\Theta(n)$. Similarly, we're entitled to say that the worst-case running time is $\Theta(n^2)$.

If the best and worst case was (asymptotically) the same (up to constant factors), then the running time would actually just be a function of the length of the input, so it would make sense to say that the running time was, e.g., $\Theta(n\log n)$. However, unless the running time really is a function of $n$, this is an abuse of notation. In the case or insertion sort, where the best and worst case running times are different, we can abuse notation a little harder and say the running time is $\Omega(n)$ and $O(n^2)$. This says that, for any (sufficiently large) input, the running time will be somewhere between $n$ and $n^2$ steps (up to constant factors) but, again, there is no actual function of $n$ that is "the running time." It would be more formal to say that the running time $T(x)$ for an input $x$ satisfies $c|x|\leq T(x)\leq c'|x|^2$ for large enough $|x|$ and some constants $c$ and $c'$.


Meaning of $a\lor b \to b' \lor c'$ So I have done part a) but I have no clue what I am supposed to do for part b), I have been trying for days to wrap my head around and even asked my fellow course mates, none of which seem to know themselves.

The way I understand it they give me automaton of

  a->b->c

But what do they mean about the next state a',b',c' automaton for which is not displayed.

If the current state is one of $a,b$, then the following state is one of $b,c$.


Solving systems of linear equations over semirings So I have come across an issue where it would be very nice to solve systems of linear equations over semirings but I have no clue how to do that. Over a field I would use Gaussian elimination but I'm at a loss of how to find solution spaces to even rings much less semirings. In fact I'm not 100% sure this is decidable. The problem demands that I be able to do this for a wide class of semirings (preferably all) and not just 1 specific kind.

Are systems of linear semiring equations decidable? If so what algorithms are known to compute solutions for them?

I don't think there's any general algorithm that works for arbitrary semirings.  The requirement to be a semiring doesn't give us a lot to work with.
However, if you have a closed semiring, then there are algorithms for solving systems of linear equations over the semiring.
Closed semirings
A closed semiring is a semiring with a closure operator, denoted $*$, which satisfies the equation
$$a^* = 1 + a \times a^* = 1 + a^* \times a.$$
A closed semiring is also known as a star semiring.
The intuition is that $a^*$ is intended to be the sum of the infinite series
$$1 + a + a^2 + a^3 + \dots$$
For instance, the regular languages form a closed semiring under union and concatenation; the $*$ operator is the Kleene star.  The real numbers form a closed semiring under addition and multiplication; the $*$ operator is $a^* = 1/(1-a)$.
Systems of linear equations over a closed semiring
Now, if you have that kind of structure, then there is an analog of Gaussian elimination.  In particular, if you have a linear system of equations
$$Ax+b = x$$
where $x$ is a vector of variables over the closed semiring, $b$ is a vector of constants, and $A$ is a matrix of constants, then this has the solution
$$x = A^* b.$$
The closure operator on matrices takes a bit of work to define, but it can be computed efficiently using an analog of Gaussian elimination.
For a careful development of the theory, I recommend the following papers:
Stephen Dolan.  Fun with Semirings: A functional pearl on the abuse of linear algebra.  International Conference on Functional Programming, ICFP '13.
Daniel J. Lehmann.  Algebraic structures for transitive closure.  Theoretical Computer Science, vol 4 pp.59--76, 1977.


a lower bound for the maximum fraction of matchings not containing an edge I am trying to prove the following statement (from book, page 317):

Let $G(A,B,E)$ be a bipartite graph, where $A$ and $B$ are the two disjoint sets of vertices s.t. $|A|=|B|=n$. Let the number of matchings of size $k\le n$, be $m_k$. If $|E|>k$ then there exists an edge $e$, such that $\frac{m_{ne}}{m_k} \ge \frac{1}{n}$, where $m_{ne}$ is the number of matchings of size $k$, that do not include/contain edge $e$.

The book gives a hint to use pigeonhole principle. But I am only able to get a weaker result.
Each matching of size $k$, contributes towards a matching of size $k$ not containing an edge, for $|E|-k$ edges. Thus as there are in total $m_k$ matchings, it can be seen as distributing $(|E|-k)m_k$
balls in $|E|$ bins. Thus by pigeonhole principle there is a bin (an edge) with at least $\frac{(|E|-k)\cdot m_k}{|E|}$ matchings which do not contain it. That is there is an edge $e$ such that
$$m_{ne} \ge \frac{(|E|-k)\cdot m_k}{|E|}$$
$$\frac{m_{ne}}{m_k} \ge \frac{|E|-k}{|E|} \ge \frac{1}{|E|} \ge \frac{1}{n^2}$$
How can I prove that the lower bound is at least $\frac{1}{n}$ for some edge ?

Your approach has been working well all along, only to miss the promising transformation at the last step.
Instead of
$$\frac{|E|-k}{|E|} \ge \frac{1}{|E|} \ge \frac{1}{n^2},$$
we can proceed as
$$\frac{|E|-k}{|E|} =1 - \frac{k}{|E|} \ge1- \frac k{k+1}=\frac1{k+1}.$$
Since $k\le n$, i.e., $\dfrac1{k+1}\ge\dfrac1{n+1}$,  we are not far from the goal $\dfrac1n$.
It takes a bit more effort to reach the goal. I will leave it to you to complete.

Here is a slightly easier proof. It shows, except possibly for graphs where all edges are separated, we can increase $1/n$ to $1/2$.
Consider whether there are incident edges in $G$.

There are incident edges. Say, edge $e_1$ and $e_2$ are incident. Every matching (of size $k$) can contain at most one of them. So either at least 1/2 of the matching of size $k$ does not contain $e_1$ or  at least 1/2 of the matching of size $k$ does not contain $e_2$. Note that $$1/2\ge 1/n.$$
There are no incident edges. Then there are at most $n$ edges. Since each matching does not contain at least one of the $|E|$ edges, we have , if $e$ is the edge that is absent from the most matchings of size $k$,$$\frac{m_{ne}}{m_k}\ge \frac{1}{|E|} \ge \frac{1}{n}.$$

$\checkmark$


Undecidability of the following language So we can prove that the language say $A = \{ \langle M,w \rangle \mid \text{M is TM that accepts } w^R \text{ whenever it accepts } w \}$ is undecidable by assuming it is decidable and use that to construct a $TM$ deciding $A_{TM}$. So by contradiction $A$ is undecidable. But what if the language was $\{ \langle M,w \rangle \mid \text{M accepts } w \text{ but on input } w^R \text{halts and rejects} \}$?

I was thinking to prove that it's r.e, we can construct a Turing recognizer, say $K$, which recognizes this language by simulating $M$ on $w$ and do whatever $M$ does. But how does the machine know what's $w$ and $w^R$? Non determinism maybe? Or am I looking at it the wrong way?

And to prove that it's undecidable would we use the same approach as that for $A$?

You can construct a recognizer that simply simulates M on w and then simulates M on $w^R$. This will halt in finite time for all  that are in A (by definition), and then you can accept if the first simulation accepted and the second rejected. That suffices for the language being recognisable (recursively enumerable).

I'm not sure what you mean by "how does the machine know what's $w$ and $w^R$ ?" w is part of the input  pair, and w^R is easily generated from it. The way you've defined the language A, you don't have to worry about guessing which is the one that M should accept and which is the one it should reject. But if the language was  such that either M accepts w and rejects in finite time w^R or M rejects w in finite time and accepts w^R, then it's still easy. You do the same thing and accept if exactly one of the two simulations accepts, without caring which one.

I don't actually know a "standard" proof that $A$ is undecidable. But to prove your new language undecidable, I'd make a decider for A_TM that on input  produces M' that rejects all other input than w and behaves as M on w. M' definitely rejects $w^R$ in finite time, so  will be accepted by the decider for your language iff M accepts w. I imagine to prove $A$ undecidable you do the same thing but make M' accept all other strings, so it definitely accepts $w^R$ and accepts w iff the hypothetical $A$ decider accepts.


Generating all equal-sized set partitions Minor disclaimer: This is my first question here, so I hope it is the
right place to put it.

Question: Is there an algorithm to exhaustively generate all set
partitions of equal size? That is, I want to list all possible ways to
divide a set of $N$ elements into $K$ parts where each part has the same
size $\frac{N}{K}$. At best, I want to generate all of these partitions
sequentially without generating any duplicates. There are many
algorithms to list all divisions of a set into $K$ parts that however do
not impose a size constraint on the parts. But I have not found anything
on generating set partitions of equal size.

I assume that the elements in the set are labeled using labels $1, ...,
K$. For $K = 2$ groups, I can exhaustively list all partitions by
sequentially generating all permutations of the group labels in
lexicographic order and stop as soon as the first element is $2$ [that
is assuming I started with the initial partition $(1, 1, 1, ...., 2, 2,
2)$]. However, for $K > 3$ generating permutations of the labels does
work anymore without generating duplicate partitions.

Suppose $N=\{0,\dots,N-1\}$.
There are $\binom{N-1}{K-1}$ choices for which elements are equivalent to 0. For each choice of these there are $\binom{N-K-1}{K-1}$ choices for which elements are equivalent to the smallest number not equivalent to 0. And then $\binom{N-2K-1}{K-1}$ for which elements are equivalent to the smallest number not equivalent to any number chosen so far.
Continuing to iterate this way, we get through all the $\prod_{a=0}^{N/K-1}\binom{N-aK-1}{K-1}$ balanced partitions.


Why does the following Backus-Naur form reflect the following syntax diagram? The definition of the variable

< number>::=< digit > | < digit >< number >

where < digit >  is defined as

< digit > ::= 1|2|3|4|5

Apparently reflects the following syntax diagram

Please explain why this is the case. I am particularly confused with the clause after the vertical OR line (i.e. < digit >< number >) and whether it has something to do with the fact that number can consist of many digits.

< number>::=< digit > | < digit >< number > means that a number is either just a digit, or a digit followed by a number. So 1 is a number (just a single digit), and 12 is also a number (a single digit, followed by a number that consists of just the single digit '2'). Similarly 123 is a number that consists of a single digit '1' and a number (that itself consists of a single digit '2' followed by a number (that consists of the single digit '3')).


Constructing a reduction between two languages about pairs of Turing machines I'm curious about a potential relation between the following two languages.

$L_1 := \{\langle M_1, M_2 \rangle : L(M_1) \cap L(M_2) \ne \emptyset \}$.

$L_2  := \{\langle M_1, M_2 \rangle : L(M_1) \ne L(M_2) \}$.

  Is it true that $L_2$ mapping reduces to $L_1$?

I've had many failed attempts to construct a reduction and would appreciate any help.

Here are three hints.

Show that $L_2$ is not computably enumerable.
Show that $L_1$ is computably enumerable.
If $L_2$ mapping reduces to $L_1$, what does it imply?


Approximation factor preserving reduction The definition of approximation factor preserving reduction from the book by Vijay V. Vazirani, page 365:

Let $\Pi_1$ and $\Pi_2$ be two minimization problems, an approximation factor preserving
reduction from $\Pi_1$ to $\Pi_2$ consists of two polynomial-time algorithms, $f$ and
$g$, such that:

for any instance $I_1$ of $\Pi_1$, $I_2 = f(I_1)$ is an instance of $\Pi_2$ such that $OPT_{\Pi_2}(I_2) \leq OPT_{\Pi_1}(I_1)$.
for any solution $t$ of $I_2$ (constructed above), $s = g(I_1, t)$ is a solution of $I_1$ such that: $obj_{\Pi_1}(I_1, s) \leq obj_{\Pi_2}(I_2, t)$.

It is clear that this reduction preserves the approximation factor.
QUESTION: Since any solution of $I_2$ shall have an objective value no less than that the objective value of the corresponding solution of $I_1$, if the solution $t$ to $I_2$ is optimal, that is, $obj_{\Pi_2}(I_2, t) = OPT_{\Pi_2}(I_2)$, doesn't this imply that equality should always be satisfied on the first condition? In other words, $OPT_{\Pi_2}(I_2)$ can never be less than $OPT_{\Pi_1}(I_1)$, or else, some solution of $I_1$ will have an objective value less than its optimal (which yields a contradiction for a minimization problem).
I understand that we are mainly interested in optimization problems that are NP-hard, however, in this reduction, we did not specify that the solution of $I_2$ should not be optimal.
In this book, the author gives several such reductions between different problems, however, none of those reductions were built upon the strict equality of the first condition.

That looks right.  The only exception I can think of is problems where there isn't an optimal solution, but just a sequence of ever-better solutions converging to, but never attaining, some optimum.  Though actually, even then, if the optima weren't the same, it should be possible to find some solution in between the optima, which would arrive at a contradiction.  So it seems what you say should still hold, unless I'm also missing something.


Why is finding minimum number of comparisons to sort $n$ elements so difficult? In The Art of Computer Programming 2nd Ed, Vol 3, Section 5.3.1 then discuss a function $S(n)$ which is define as:

  $S(n)$ : The minimum number of comparisons that suffice to sort $n$ elements.

Further, the book regards $\lceil \lg n! \rceil$ as the information theoretic lower bound for $S(n)$.

Using merge insertion they also upper bound the number of comparisons by $F(n)$ where

$$F(n) = \sum_{k = 1}^{n} \lceil \lg \tfrac{3}{4} k \rceil$$

So you can get the bound $\lceil \lg n! \rceil \leq S(n) \leq F(n)$, and for any values $n$ where $\lceil \lg n! \rceil = F(n)$ you can find the exact value of $S(n)$.

My questions are:

Why does $S(n)$ not always match the information theoretic lower bound $\lceil \lg n! \rceil$? It seems like if this is all the bits of information we should need, that this is all the comparisons we would need. Why do they differ?
Why is $S(n)$ so difficult to compute? It's discussed in the book some but the reasons are still unclear to me. Do you have to brute force and create every possible decision tree for a given $n$ and determine the longest path? Is there not a more efficient way? It seems that $S(n)$ has only been exactly computed for $n \leq 22$ (See A036604 here).

Let's say the size of the array is such that there are $2^{k-1} < x ≤ 2^k$ possible permutations, so the theoretical lower bound to sort this array is k comparisons.

Any comparison divides the set of possible permutations in two subsets, consistent with each outcome of the comparison. You'd first need a comparison that splits the set of all possible permutations into two subsets, each of size at most $2^{k-1}$. And each subset you need to split into two subsets of size at most $2^{k-2}$ etc. If these subsets don't have the same size, then after j comparisons the size of the largest subset could exceed $2^{k-j}$, and you lost.


A TSP to HamCycle Reduction I'm referring to the decision version of both $TSP$ and $HamCycle$. The first is, given a graph $G=(V,E)$, a weight function  $w:E\rightarrow \mathbb R^+$ and an integer $k$, is there a simple cycle with weight $\leq k$ which passes, once, through every vertex? (The weight of the cycle is the sum of the weights of the edges). The second problem is finding a Hamiltoninan Cycle (a cycle that passes through every vertex only once).

I know both are $NPC$. I am interested in finding reduction between both these problems. The first reduction $HamCycle \leq TSP$ is quite easy: for every edge in the original graph you give a weight $0$ and for every pair of vertices who did not have an edge you give a weight of $1$. Then you ask whether the agent can travel with sum of path $\leq 0$. The correctness of this follows pretty quickly.

However, my question if for the reduction the other way around: $TSP\leq HamCycle$. I could not come up with an idea for such. I am aware that since both are $NPC$ there exists a reduction through Cook-Levin Theorem and $SAT$, but I am wondering if there is a direct reduction $TSP\leq HamCycle$?

By direct reduction, do you then mean a reduction that does not leave the graph-world and go back again? (that might be a very vague formulation, sorry). I do not think such a reduction exists. Of cause proving that it does not exist is not a simple matter, but at least I have not been able to find or think of one myself. But here's a couple of thoughts about why such a direct reduction is unlikely:

TSP is run on a fully connected graph with $n$ nodes and $n^2$ edges while HamCycle is run on a graph with $n$ nodes and $m < n^2$ edges (otherwise it would be trivial).
A solution to TSP must pass all nodes and contain no cycles and therefore must contain exactly $n$ edges. We could run HamCycle each on all possible paths of length $n$, starting from the one with the lowest edge-sum and continuing until we reach one that contains a Hamiltonian Cycle, but as there are ${{n^2}\choose{n}} = O(n^{2n})$ such possible paths, this would mean running HamCycle an exponential number of times. I can not see how you can avoid this.

You have most likely thought about this already, so this is mostly to say that you are not the only one who are not able to come up with such a reduction and I suspect that this may be because a reduction either has to be quite complicated or has to leave the graph-world somehow and go back again. Of cause there might exists a reduction that does leave the graph-world but is still simpler than going all the way through SAT, but I do not know of any such reduction.

I'm quite interested to see if anyone has a better answer to this.


Dynamic programming problem our uni is closed because of the COVID-19 and I'm trying to homelearn dynamic programming.

In our algorithms book, there is the following problem: (an example problem for dynamic programming)

  A driver has 3 cars. He wants to use all of the 3 cars, but want to
  use the least gas. Each car has a different engine, so it will consume
  different amounts of gas to get to each destination. What is the least amount of gas
  we can consume while still using each car? After he switches cars, he
  can't go back to the previous car.

  Input description:

  First is a number $n$, which is the number of destinations that he
  wants to reach.  Then there are 3 lines, each is the gas consumed
  while trying to reach each destination (line 1 is car 1, line 2 is car
  2, etc..)

  Example input:

  7

  2 4 1 5 1 1 2

  3 3 2 5 3 2 2

  1 1 5 4 3 3 3

  Example output:

  12 (third car (2 destinations), first car (4 destinations), second car (1 destination).)

However, I can't figure out how to start, as I'm still learning DP. Could you please help me or give me any hints?

I think it's a great good example problem, because other problems are very similar so if I master this one, I should be able to solve other problems.

Thanks!

Let $g(i,j)$ be the gas consumed when travelling to destination $i$ with car $j$.

Guess the optimal order $\langle c_1, c_2, c_3 \rangle$ of cars (there are only $3! = 6$ possible permutations).

Define $OPT[i,j]$ as the minimum amount of gas needed for reaching the first $i$ destinations using cars $c_1, \dots, c_j$ in this order, with the constraint that each car must be used at least once. If no feasible solution exists then $OPT[i,j] = + \infty$.

According to the above definition, you have $$OPT[1,j] = \begin{cases}
g(1, c_1) & \mbox{if } j=1 \\
+\infty & \mbox{if } j>1
\end{cases}$$.

and, for $i=2, \dots, n$:

$$OPT[i,j] = g(i,c_j)+
\begin{cases}
OPT[i-1, j] & \mbox{if } j=1 \\
\min\{ OPT[i-1, j], OPT[i-1, j-1] \} & \mbox{if } j>1
\end{cases}.$$

The solution to your problem is $OPT[n,3]$, which can be computed in $O(n)$ time using dynamic programming.


Does this DFA have a solution? I am trying to create a DFA that can recognize strings with alphabet $\{a,b,c\}$ where $a$ and $c$ appear even number of times and where $b$ appears odd number of times.

I am wondering that this may only be expressed with other methods such as Turing machine or context-free languages.

You might find it fun to think of the solution.

This is doable with a DFA. Hint: We need to keep track of three things simulataneously:

The parity of a's (have we seen an odd or even number of a's so far?)
The parity of b's
The parity of c's

So there are 8 possibilities for what we've seen so far:

Even number of a's, even number of b's, even number of c's.
Odd number of a's, even number of b's, even number of c's.
Even number of a's, odd number of b's, even number of c's.
...

Does that help?


How can I check that the language of one context-free grammar is a subset of a second context-free grammar? Could you explain me, how can I check, that the language of first context-free grammar (G1) is a subset of the language of second context-free grammar (G2).

G1 and G2 are two LL(1) grammars with identical alphabets:

{a, b, c, d, f}

Production rules are look like:

A -> αB

or

A -> α

and α is a non-epsilon string (of terminal symbols).

Context-free grammar G1:

S1 -> aK
K -> bC|cE
C -> cB|d
E -> bA|f
A -> abC
B -> acE

Context free grammar G2 :

S2 -> aX
X -> bZ|cY
Z -> cV|d
Y -> bU|f
V -> aQ
U -> aP
Q -> cY
P -> bZ

Automatic way is preferred.

  In additional, how can I check that the languages of two arbitrary
  context-free grammars are equal.

Here you have a couple of salient points. Firstly, the grammars are right linear (strictly $G_{1}$ needs some small changes, but they're trivial). This means that the two languages are regular. Given this fact, there's an automated way of determining whether $L(G_{1}) \subseteq L(G_{2})$ or not.

In this case however, things are fairly simple, and we can show a simple mapping between the non-terminals, with only the transitions $A \to abC$ and $B \to acE$ causing a small amount of trouble. If you draw out the finite automata though, you should be able to see the mapping. Doing so, it should be fairly clear that $S_{1}$ maps to $S_{2}$ (obviously), $K$ to $X$, $C$ to $Z$ and $E$ to $Y$. $A$ maps to the pair $U,P$. $U \to aP \to abZ$, and $Z$ already maps to $E$, so you can see the rule is essentially the same in both grammars, just split in $G_{2}$ into an intermediate step. The same observation applies to $B$ and $V,Q$.

Note that in general, we need the fact that $L(G_{1})$ and $L(G_{2})$ are regular, deciding containment for context free languages is undecidable.


Longest path in a cyclic, directed and weighted graph I am looking for the longest simple path in a directed, cyclic and weighted graph with positive and negative weights.

In my research so far I have found out that you need to generate -G from graph G and then run a shortest path algorithm on it to find the longest path in G. Of course this won't work if -G contains negative cycles. But that's excatly what I need to do. Consider following graph (which I created quickly in paint..):

The red letters are just there for identification. The red numbers are the value of the vertex and the blue numbers are the edge weights.
The edge weights are generated with the following formula:

$$ Weight = \frac{destination}{source} $$

I am looking for the longest path from A to F - but the longest simple path. That means that a vertex must not be visited more than once. By simply looking at it I can see that it is A - B - E - F. But if I tried to generate -G and then run the Bellman-Ford algorithm on it it would fail because there would be negative cycles like B - E - D - B.

I am aware that it is not possible if you look for paths in which a vertex can be visited more than once. But if you look for simple paths only, is it still not possible?

Longest Path is NP-hard; the reduction from Hamiltonian Path is almost trivial.

That means that we do not know any algorithm with even polynomial running-time. You have to compromise.

Of course, the problem is easier for special classes of graphs, for instance both undirected and directed acyclic graphs.


Complements of Linear Bounded Automata? Would switching the accept and reject states of an LBA A create a new LBA we'll say A' in which the language of A' is the complement of the language of A? I believe the answer is yes just by working out an example...but I'm not sure on a solid proof...nor am I sure if the fact that I am working with an LBA vs a regular turing machine makes a difference in this case.

It depends whether the automaton is deterministic or not. If it is deterministic, then the answer should be yes, just as in the case of DFAs, and you can mimic the proof for DFAs. If it is non-deterministic, then the answer should be no, just as in the case of NFAs; in fact NFAs are a special case of non-deterministic LBAs, and the NFA counterexample can be adapted to the LBA setting.

(The set of languages accepted by non-deterministic LBAs is closed under complementation, but the proof is not quite as straightforward; it is known as the Immerman--Szelepcsényi theorem.)