Can a DFA have an unreachable state? I am trying to prove or disprove the following statement:

  If $A = (\Sigma, Q, \delta, q_0, F)$ is a complete DFA where $F \neq \emptyset$ then $L(A) \neq \emptyset$

So my initial thinking is to find a counter example. If say we were to construct a DFA with one accepting state, and that state is never reached then the proposition is false.

For instance :

Assume we have the following automaton

So my question is , are we allowed to have such a state in a DFA ?

You are indeed allowed to have unreachable states in DFAs (or NFAs, or various other automata models).

You may wonder what is the point of having them, given that they are unreachable and have no effect on the language.

Well, automata are typically not designed by hand. Rather, they are usually obtained algorithmically by translation from other types of specifications, models, etc.

These translation algorithms often don't guarantee that there are no unreachable states, and very often there are many unreachable states.
For example, take the subset construction, that transforms an NFA to an equivalent DFA. There are typically many unreachable states in the naive construction (although it can be optimized to construct only the reachable states).

However, there are other constructions that are much more involved (e.g., the translation of Linear Temporal Logic to Nondeterministic Buechi automata).

In fact, one of the most fundamental algorithms on automata is that of emptiness -- check whether the language is empty. To do so, we look for a reachable accepting state. If automata only had reachable states, we would only have to check whether there are accepting states, but this is not enough.

Finally, I'll remark that this algorithm is often symbolic, in that you don't run it on an explicit automaton, but on a symbolic representation. For example, you can check emptiness of a DFA constructed by determinizing an NFA without actually contstructing the whole thing.


Alignment of RGBD with a thermal camera I have a thermal camera that I would like to overlay, automatically, to the output of a RGB-D camera (e.g. Kinect).

I have retrieved the intrinsic and extrinsics parameters of both cameras.

My objective is to calculate the disparity map between the two. That is, to map the matrix resulting from the depth image to the thermal image, in order to estimate the distance of each point in the thermal image.
From an intuitive standpoint, I should be able to align them because I have depth information in this case.

A solution that comes to my mind, it is as follows:

Step 1: for each pixel of the depthmap, estimate its corresponding 3D point. Let's call it Depth_3D.
Step 2: transform Depth_3D in Ther_3D. That is, given the 3D position of the point of the depth camera, find the 3D position of the same 3D point (object in the real world), but respect to the thermal camera. The relative position and orientation of the two cameras is known.

Problem: to perform step 2, I need the 3D rotation matrix (let's call it R3D) and 3D translation vector (let's call it T3D) to be able to map from the depth camera to the thermal camera, in the real world.

Step 3: Finally, using the intrinsic parameters of the thermal camera, project each Ther_3D into the thermal image.
Step 4: assign the depth to the obtained pixel, so that, at the end of the loop, the depth map of the thermal image is complete.

My doubt is about how to calculate R3D and T3D (please see step 2) using their relative position and orientation.
Other solutions are welcome of course.

Thanks in advance.

Step 2 is just a change of coordinate system from one camera's coordinate system to the other camera's coordinate system.  It's easy to do, using a "change of basis".

The extrinsic parameters of the depth camera tell you how to transform from the depth camera's coordinate system to the world coordinate system (a transform between two 3D coordinate systems).  The extrinsic parameters of the thermal camera tell you how to transform from the 3D world coordinate system to the thermal camera's coordinate system.  If you combine these two transformations, you have a way to transform from Depth_3D to Ther_3D.

So if you have the extrinsic parameters, you should already know how to do this.

See, e.g., https://en.wikipedia.org/wiki/Pinhole_camera_model and https://en.wikipedia.org/wiki/Camera_matrix and https://en.wikipedia.org/wiki/Camera_resectioning, or any textbook that describes camera intrinsic and extrinsic parameters.


Distinction between 2 languages.One is regular the other is not whenever it needs to be determined if langage is regular or not, I use the notion that it is impossible for a machine to "remember" an infinte states.

given 2 languages:$L_1=\{(01)^{n}(10)^{n}|n \in \mathbb{N}\}$

$L_2=\{(01)^{n}0(10)^{n} |n \in \mathbb{N}\}$

The only difference between $L_1$ and $L_2$ is the $0$ in the middle.
$L_1$ is non-regular but $L_2$ is .

In the appendix page in the workbook it's written that:the intuition used in L1 is that I need to remeber an infinite states, and then using the "Pumping Lemma" they disproved that it is regular. It also says that L2 is regular and it is possible to build a DFA for the language.

I am not looking for answers for how to solve this, just why this notion of "machine have to remember an infinite states" is not applicable to $L_2$ because it seems that in $L_2$ the machine needs to remember how many times $01$ appeared then after $0$ machine needs to repeat the same number of time for $10$.

I also use this webpage:https://www.geeksforgeeks.org/how-to-identify-if-a-language-is-regular-or-not/

A bit over year ago I asked about the statemnets written there and they told it is not fully reliable(theorem no. 5 : "concatenation of pattern(regular) and a non-pattern(not regular) is also not a regular language.")

Why language is not regular

Before trying to draw a DFA or disaproving using pumping lemma I use these theorems, but as it seems it maybe unreliable.

The questios are: why L1 is regular and L2 is not(I understand that one can be described via dfa and the other is not, just why L2 is not supposed to remember an infinite states).

and if the link for "geeks for geeks" can be used, to help to decide if language  is regular or not?(I know that the only way to determine is by building dfa or pumping lemma=> these are the only 2 ways I've so far as a student studied,but before wasting time in the exam for building "DFA" for non regular language I need some sort of "hunch" as to choosing to disaprove by pumping lemma or building a DFA).

This is one of those trap questions where $L_2$ can actually be written in a different way that makes it obvious that it is a regular language. See if you can figure out what $L_2$ is "really doing", and the answer will become obvious.

Solution:

   $L_2 = 0(1010)^*$


Is there a way to access hard drives while computer sleeps? Is there any way at all possible or possible with hardware (aside from a NAS) to access hard drives while the computer is in a low power mode such as sleep (aside from WOL)?

For example, can I log into a networked drive located on the computer and spin it up to access data without the computer coming out of low power mode?

Sure.  It all depends on the architecture of the machine.  For instance, if there is a co-processor that is awake and responds to the network requests by accessing the hard drive, that would be one way to accomplish it.

If you're asking about a specific product or technology, that is off-topic here.  But conceptually, you can certainly build a computer that has this capability.  Whether any individual computer does have that capability is a question about that specific product or technology.


Clarification on Tabu Search I need some help in understanding the 'Tabu Search' Algorithm. (Wikipedia)

I miss a simple explanation to Tabu Search. Anyway, I'm trying to refer to available resources and build an understanding.

This is what I'm trying to 'digest':

Tabu Search is an improvement over the Hill Climbing algorithm (Ref-1).
The problem with Hill Climbing is that it does not guarantee about reaching the global optimum, because it only searches on a subset of the whole solution space. It will find the local optimum.
To get rid of this issue, Tabu Search maintains a 'Tabu List' of previously visited states that cannot be revisited (Ref-2).
If the tabu list is too large, the oldest candidate solution is removed and it’s no
longer tabu to reconsider (Ref-3).

My questions are,

How does Tabu Search cure the problem of getting stuck in a local
optimum? Does it increase the search-space?
What is the need of maintaining a list (i.e. Tabu List)? Why not
just remember the optimum solution found so far?
When the Tabu List is too large, the oldest candidate will be
removed. What if this oldest candidate is the global optimum?

If anyone could explain Tabu Search algorithm using an example, I'm sure these questions would be automatically answered.

References:

(Ref-1) Hill Climbing, Wikipedia Article (link)
(Ref-2) Russell, Stuart Jonathan, et al. Artificial intelligence: a modern approach. Vol. 74. Englewood Cliffs: Prentice hall, 1995. (WorldCat)
(Ref-3) Luke, Sean. "Essentials of Metaheuristics.". (pdf)

How does Tabu Search cure the problem of getting stuck in a local optimum? Does it increase the search-space?

First, the search method does not affect the size of the search space; it depends only on the problem and it simply contains all possible states. Tabu search (TS) does what local search methods often do: when you get stuck, you allow a non-improving move in the hopes of getting unstuck. TS, in particular, maintains a tabu list. When we do a non-improving move, the tabu list ensures we never move to a previously visited state.

  What is the need of maintaining a list (i.e. Tabu List)? Why not just remember the optimum solution found so far?

As explained, the need of maintaining a list is guiding the search in an "intelligent" way. If you just remembered one state (perhaps that is the best solution found so far), you would be getting out of a local optimum in a "blind way". That is, it is possible you would simply trace your steps back, and then walk into the same local optimum again!

  When the Tabu List is too large, the oldest candidate will be removed. What if this oldest candidate is the global optimum?

If the global optimum is not in tabu list, then it is possible you will find it later. In short, the tabu list (as the name implies) contains all states you for some reason do not want to backtrack to.


Filling a matrix with the sum of conditional values I have $P$ vectors of size $N$ with elements in $\{0,1\}$. Each vector $v$ has a value $\alpha_v$.

I would like to Fill a square matrix $M$ of size $N\times N$ in the following way:

$$\forall i,j \in \{1,2,...,N\}~ M_{i,j} = \sum_{\text{vectors}~v : v_i  v_j =1} \alpha_v$$

Is it possible to fill the matrix $M$ in time complexity better than $O(P\cdot N^2)$?

Assuming that each vector has at most $Q$ elements equal to $1$, is it possible to do better than $O(P\cdot(N+Q^2))$ ?

Let $V$ be the $N\times P$ matrix whose columns are the vectors $v$, and let $D$ be the $P\times P$ diagonal matrix with elements $D_{vv} = \alpha_v$. Then you want to compute $VDV^T$. Computing $U = DV^T$ takes time $NP$, and it remains to compute $VU$. When $P < N^{0.3029}$, for every $\epsilon > 0$ there is an (impractical) algorithm to compute this product in time $O_\epsilon(N^{2+\epsilon})$. See Le Gall, who improved on an earlier result of Coppersmith.


in order of binary search tree This is what I got for the in-order of the bst but it's wrong because I'm answering some questions about some successors of some of the letters and I got them wrong. so I'm wondering where in this in-order i've gone wrong?

d, b, m, h, i, e, a, j, k, f, g, c

(Sorry if these questions aren't allowed here, please let me know where I can ask it if not!)

Remember that an in-order traversal lists the elements from left-to-right, descending the tree: Left, Root, and Right. This means that starting from the root (a), we will traverse the whole left branch, then print a, and finally traverse the right branch.

You started off correct; however, your mistake was that you put m beforee h. It is an easy mistake to make so you have to be careful. The m node is the right node of h so the traversal for that subtree will be h, m. The same goes for i and e in your traveral---they should be flipped.

The correct answer for this in-order traversal is d b h m e i a j f k c g.


How to check for ambiguous grammar if you don't know the string Let's say I have a CFG grammar $G$ which describes some rules for language generation. How can you tell that grammar can generate ambiguous results for a string if you don't know that string? I know how to check for ambiguity when you're given a particular string but what about the cases when it's not? Is there any algorithm to do this?

You cannot tell that a context-free grammar is ambiguous, since the problem is undecidable. This can be proved by a straightforward reduction from the Post correspondence problem, for example. What this means is that there is no algorithm that, given a context-free grammar, decides whether it is ambiguous or not.


exists (u,v) edge with positive capacity and there is not path from $s$ to $u$. and $(u,v)$ is with full capacity in some maximal flow Given a network flow and there exists (u,v) edge with positive capacity and there is not path from $s$ to $u$. and $(u,v)$ is with full capacity in some maximal flow.

I've had this questions with true or false and I thought it was false but apparently it is true.
Can someone please explain me how this is possible?

Since you just have to satisfy the conservation of flow property and capacity property. You can consider the following example:
$V = \{s,t,u,v\}$ and $E = \{(s,t), (u,s), (u,v), (v,u)\}$ with each edge of capacity 1.
You can send a flow of 1 via $(u,v)$, $(v,u)$, and $(s,t)$. It follows all properties of a valid flow. It does not have a path from $s$ to $u$. Also, the flow via $(u,v)$ is at its full capacity.


How to "properly" handle incorrect values in a random walk? I'm performing a simple one dimensional walk to create sample interest rates. Whilst I know there are lots of options for encouraging values to oscillate around a mean etc. I'm yet to find a simple "proper" way to handle truly random processes going out of bounds. Whilst you could simply turn it in the other direction, is there some sort of commonly accepted way of making asymptotically less and less likely to get closer to the boundary the closer you get to it?

A random walk $(X_i)$ can't become negative if there are no positive-probability transitions to negative values. One condition that causes it to stay finite with probability $1$ is that, for all large enough $n$, $\mathbb{E}(X_{i+1}|X_i=n)<n$.


Proving a Language is Irregular using Myhill-Nerode I'm trying to prove that the language: \begin{equation*}
L = \{ w \in \{ 0, 1 \}^* : w  \text{ contains more 0's than 1's} \}
\end{equation*} is irregular using the Myhill-Nerode theorem. I've been through all the basic examples in the book, and thought I understood them, but I'm having trouble with this one.

So far, I've been thinking about letting $ x_i = 1^i 0^i $ and $x_j = 1^{j+1} 0^{j-1}$, then if I let $ w_{ij} = 0$, only $x_iw_{ij} \in L$. That seems to be sufficient, but it seems weak compared to some of the other examples.

Am I on the right track here? I would really appreciate any hints/suggestions.

You need to come up with an infinite number of pairwise inequivalent strings. Try $x_i = 0^i$ for all $i \geq 0$.


What is the computation model of Prolog? Several computation models have representative programming language counterparts, as, according to this answer, Snobol for rewriting systems, APL for combinators, Lisp/Scheme for lambda calculus, and off course the family of imperative languages for TMs (or more precisely RAMs). It seems to me that Prolog should also be a paradigmatic language for some model. Is this assumption true? If so, what is the name of that model?

I think the computation model of Prolog is the SLDNF resolution of Horn clauses.

Prolog is actually very procedural. Kowalski 1974: "The interpretation of predicate logic as a programming language is based upon the interpretation of implications [...] as procedure declarations [...]" (emphasis mine)

https://www.doc.ic.ac.uk/~rak/papers/IFIP%2074.pdf

(However, lambda calculus, theorem provers, and Turing machines are term rewriting systems indeed. What is a computational model then, if everything is a term rewriting system?)


Bound on space for selection algorithm? There is a well known worst case $O(n)$ selection algorithm to find the $k$'th largest element in an array of integers.  It uses a median-of-medians approach to find a good enough pivot, partitions the input array in place and then recursively continues in it's search for the $k$'th largest element.

What if we weren't allowed to touch the input array, how much extra space would be needed in order to find the $k$'th largest element in $O(n)$ time?  Could we find the $k$'th largest element in $O(1)$ extra space and still keep the runtime $O(n)$?  For example, finding the maximum or minimum element takes $O(n)$ time and $O(1)$ space.

Intuitively, I cannot imagine that we could do better than $O(n)$ space but is there a proof of this?

Can someone point to a reference or come up with an argument why the $\lfloor n/2 \rfloor$'th element would require $O(n)$ space to be found in $O(n)$ time?

It is an open problem if you can do selection with $O(n)$ time and $O(1)$ extra memory cells without changing the input (see here). But you can come pretty close to this.

Munro and Raman proposed an algorithm for selection that runs in $O(n^{1+\varepsilon})$ time while using only $O(1/\varepsilon)$ extra storage (cells). This algorithm leaves the input unchanged. You can pick any small $\varepsilon>0$.

At its core, Munro and Raman's algorithm works as the classical $O(n)$ algorithm: It maintains a left and right bound (called filter), which are two elements with known rank. The requested element is contained between the two filters (rank-wise). By picking a good pivot element $p$ we can check all numbers against the filters and $p$. This makes it possible to update the filters and decreases the number of elements left to check (rank-wise). We repeat until we have found the request element.

What is different to the classical algorithm is the choice of $p$. Let $A(k)$ be the algorithm that solves selection for $\varepsilon=1/k$.  The algorithm $A(k)$  divides the array in equally-sized blocks and identifies a block where many elements are, whose ranks are in between the filters (existence by pigeon-hole principle). This block will then be scanned for a good pivot element with help of the algorithm $A(k-1)$. The recursion anchor is the trivial $A(1)$ algorithm. The right block size (and doing the math) gives you running time and space requirements as stated above.

Btw, the algorithms you are looking for, were recently named constant-work-space algorithms.

I am not aware of any lower bound.


Equivalene of big O definitions (Limit Definition $\Longleftrightarrow$ Quantifier Definition) I need to proof, that both definitions of the Big 0 notation are equiavlent, but I am not sure if my proof works both ways of the equivalence.
Definitions:
Let f,g be functions.

$f(n)\in \mathcal{O}(g)\Longleftrightarrow \exists c>0\exists n_0 \forall n\geq n_0 :f(n)\leq cg(n)$
$f(n)\in \mathcal{O}(g)\Longleftrightarrow \limsup\limits_{n\to\infty}\frac{f(n)}{g(n)}<\infty$

My proof:
$f(n)\in \mathcal{O}(g)\Longleftrightarrow \limsup\limits_{n\to\infty}\frac{f(n)}{g(n)}<\infty$
$\Longleftrightarrow \exists c>0 : \limsup\limits_{n\to\infty}\frac{f(n)}{g(n)}\leq c$
$\Longleftrightarrow \exists c>0\exists n_0 \forall n\geq n_0 : \frac{f(n)}{g(n)}\leq c$
$\Longleftrightarrow \exists c>0 \exists n_0 \forall n\geq n_0 : \frac{f(n)}{cg(n)}\leq 1$
$\Longleftrightarrow \exists c>0 \exists n_0 \forall n\geq n_0 :f(n)\leq cg(n)$
$\Longleftrightarrow f(n)\in \mathcal{O}(g)$
I would like to know, if the conversion is correct or if I made any mistakes.
Thanks in advance!

This 2 definitions, of course, are not equivalent, when $g$ have $0$ subseuquence i.e. when $\exists n_k \in \mathbb{N}, n_{k+1}>n_k , k\in \mathbb{N}$ such that $g(n_k)=0$. In this case, assuming, that $\frac{0}{0}$ have no sense as well as $\frac{a}{0}, a \ne 0$, then $\frac{f(n_k)}{g(n_k)}$ is not defined, while definition with quantifiers have no problem.
This is why, imho, first should be taken as base definition and second considered only in appropriate situations and why I count your question important.
If such subsequence does not exist, then your proof is correct.


What does 'buffering' mean? I read the lecture 4 of CS162 (UC Berkeley: https://inst.eecs.berkeley.edu/~cs162/sp17/static/lectures/4.pdf), but I got little bit confused about the meaning of the keyword "buffered" they used when mentioning the following informations:

  Kernel buffered reads

  Kernel buffered writes

  Data buffered automatically by C-library functions

What does each of 'buffering' and 'buffered' mean?

When reading from a source, often a program wants to read data a few bytes at a time. For instance, the program can ask the OS for the next 4 bytes from a file, so to read the next 32-bit integer. Then, it can repeat the operation again and again, until all the integers have been read.

However, that is rather inefficient. First, disk (or even SSD) reads are done in hardware using large chunks, only, like 512 or more bytes. Reading that much only for 4 bytes is a waste of band. Second, switching between user mode and kernel mode has its cost, and it would be better if any such switch would transfer a non-trivial amount of data.

For that reason, reading is usually done in large chunks, using a "buffer". Basically, the OS reads a large-ish portion of the file (say, a few KBs), and keeps this in a kernel-space array (the "buffer"). This is done in one large chunk so to optimize disk/SSD access. After this, when the program asks for the next bytes, the OS does not need to involve the hardware, and can return data from the buffer.

Context switches are similarly optimized. The C library also commonly reads a large chunk form the OS, using a user-space buffer, using only one system call (= one switch). In this way, when the application program asks for the next (say) 4 bytes, the C library can copy from the buffer without making system calls.

When the buffer becomes empty, the C library starts asking again to the OS, and the OS starts asking again to the hardware.

Buffered writing is similar, but in the other direction, converting many small writes to fewer big ones, so to improve performance. This is done by the C library and the OS/kernel.


How do you check if two algorithms return the same result for any input? How do you check if two algorithms (say, Merge sort and Naïve sort) return the same result for any input, when the set of all inputs is infinite?

Update: Thank you Ben for describing how this is impossible to do algorithmically in the general case. Dave's answer is a great summary of both algorithmic and manual (subject to human wit and metaphor) methods that don't always work, but are quite effective.

In contrast to what the nay-sayers say, there are many effective techniques for doing this.

Bisimulation is one approach. See for example, Gordon's paper on Coinduction and Functional Programming.
Another approach is to use operational theories of program equivalence, such as the work of Pitts.
A third approach is to verify that both programs satisfy the same functional specification. There are thousands of papers on this approach.
A fourth approach is to show that one program can be rewritten into the other using sound program transformations.

Of course none of these methods is complete due undecidability, but volumes and volumes of work has been produced to address the problem.


Why is the throughput (performance) of the Aloha protocol ≈ 0.18? I've read in a few places (like here that the throughput - that is, the amount of good useful messages relative to capacity - of the ALOHA protocol for networks is roughly 0.18%.

But its not clear how we arrived at that number.

Can someone explain it?

This number is reached first by assuming that messages will be produced and sent according to a Poisson process.

$$P[(N(t + \tau) - N(t)) = x]  = \frac{{e^{ - \lambda\tau } (\lambda\tau) ^x }}{{x!}}$$

This means, that the probability of $x$ messages arriving for the given interval $[t, t+\tau]$ where $\lambda$ messages are expected to arrive, is equal to right side of the equation. In other words, if we are expecting 10 messages to arrive per hour, the chances of 6 messages arriving in an hour is roughly 6.3%.

Now, messages sent by ALOHA need to be alone in order to make it to all other the nodes undisturbed. In other words, no other nodes can be sending messages at the moment we want our message to be sent and must stay silent until our message is completely sent.

This means we want to find: $$P(exactly\space1\space\space message\space arriving) * P(exactly\space0\space\space messages\space arriving\space in\space next\space t)$$

The odds of exactly one message arriving is

$$P[(N(t + 1) - N(t)) = 1]  = \frac{{e^{ - \lambda\tau } (\lambda\tau) ^ 1 }}{{1!}}  = \lambda\tau e^{ - \lambda\tau} = \lambda e^{ - \lambda}$$

The odds of 0 messages arriving for $t$ is:

$$P[(N(t + 1) - N(t)) = 0]  = \frac{{e^{ - \lambda\tau } (\lambda\tau) ^ 0 }}{{0!}}  = e^{ - \lambda\tau} = e^{ - \lambda}$$

and together they make

$$\lambda e^{ - \lambda} \times e^{ - \lambda} = \lambda e^{ -2 \lambda}$$.

This function tells us the throughput of the Aloha for all values of $\lambda$. So which $\lambda$ offers the highest throughput? To find out, we take the derivative of $\lambda e^{ -2 \lambda}$ and get:

$$ e^{ -2 \lambda} - 2\lambda e^{  -2 \lambda}$$
set to 0 and solve for $\lambda$ and we get

$$\lambda = \frac{1}{2}$$

This means that in order to have the highest throughput (i.e. be most efficient) we should have an expected rate of incoming messages to be $\frac{1}{2}$ per timeslot.

And after all that, what is the maximum throughput that we get when we have an expected rate of $\frac{1}{2}$? Simply, plug it into our equation  $\lambda e^{ -2 \lambda}$ and we get:

$$\frac{1}{2} e^{ -1} = 0.18393.... $$


Why is automated theorem proving impossible? As far I know, in general case there is no Turing machine which could get any theorem on its input and produce its proof on its output.

Why is it so?

We have to be carful here. I think you mean that a program given a formula could not, in general, produce a proof of it or its negation. I can write a program that, given a theorem, will produce it's proof as long as the set of proofs is recursively enumerable. This is not possible in general because of Godel's incompleteness theorem (well that was the first case we knew of). If everything that was true could be proved then we could write a program that enumerated all the proofs until it found the proof of the formula or its negation. However this is not the case as the incompleteness theorem points out. While Godel was the first to prove this was the case the halting problem gives us a nice simple proof that some things are not provable.

The argument goes like this:

Say you have a sound and complete logic for proving the termination of computer programs. The rules of the logic make the proofs recursively enumerable as well. If the logic wasn't sound we wouldn't have to worry about proving anything because false things are already provable; everything falls apart. If it wasn't complete (generally the case) then there would be a true thing that wasn't provable and thus neither you nor the computer could ever prove it. If The proofs were not recursively enumerable then there would be a proof that the program couldn't check to be valid or even reach and thus it couldn't prove the corresponding formula. Now consider the following program:

Given a program called pgrm
foreach p in set of proofs //remember, proofs are recursively enumerable
  if p is a proof that pgrm halts
    output that pgrm halts
  if p is a proof that pgrm loops
    output that pgrm loops

This program would solve the halting program however so one of our 3 assumptions must be wrong. In practice we work with what we think are sound systems of logic and we work with recursively enumerable sets of proofs as well.


Type of undecidability in Rice Theorem Rice theorem says every non-trivial property of languages of Turing machines is undecidable.  As David Richerby said in here :

  Undecidable means not decidable. Undecidable problems may or may not be semi-decidable.

I would like to know how to find out Rice Theorem leads to semi-decidability or non-semi-decidability?

As an example Rice Theorem is applicable to this r.e. language

  $A = \{x | \phi_x$ is defined for at least one input$ \}$

and also this non-r.e. language as well:

$\psi_p = x^2$

There is no algorithm to determine $\psi_p$ has that property at all while for $A$ we can simply run the program forever an see whether it accepts one input or not. I would like to know using Rice Theorem is there any way to determine this difference?

Rice's Theorem just says it's undecidable. Some undecidable languages are semi-decidable; some (almost all, in fact) of them aren't.


Dijkstra with bitwise OR of edge costs Given a graph $G$ where loops and multiple edges are allowed.
A path {$e_1, e_2, ..., e_k$} (a sequence of edges) has a cost
$$ cost = e_1 | e_2 |...|e_k$$
where $|$ is the bitwise OR.

Assume for all edges in $G$, $e_i \ge 0$.

Now, the triangle inequality is satisfied, for this definition of cost. Meaning, as the path size increases, the path cost can never decrease.

So theoretically, to find the shortest between two vertices, Dijkstra's algorithm should give the right answer?

I'm not sure if you can adapt Dijkstra specifically in any way to this problem, but there's a different efficient solution that's actually easier to come up with.

Because bitwise operators treat bits independently, you can try to fix each bit in your answer, iteratively, from highest to lowest. The first question is "can I not have the highest bit set to 1 in my answer?". If after removing all edges with the highest bit set to 1 from the graph, the source and destination are still connected, the answer is yes, you throw away all those edges for good and proceed with the next bit. If the answer is no, you put the removed edges back, because they might come in handy, and again proceed with the next bit.

Running time is $O(Elog MaxCost)$.


Algorithm(s) for creating balanced 5-a-side teams? I play 5-a-side soccer twice a week. 10 people play each game out of a pool of about 30 people who are giving the opportunity to play as it's first come first serve. Some people play more often than others.

The best matches are the ones where the score stays even throughout the game because they are the most competitive. Our rules are as following: first team to score 5 goals gets 1 point then the goals count resets.

The problem is figuring out how to pick balanced teams. I am going to program a script to log teams and scores over time and I am wondering what algorithm(s) can I use to generate the teams based on this history keeping in mind that we wont always have the same 10 players but we might have the same 8 players, etc?

This is a modelling question.  One plausible model might be as follows.  Each player as a strength, which is a real number.  The strength of a team is the sum of the strengths of the players on the team.  If team A plays team B, then team A will win with probability $f(s_A - s_B)$, where $f$ is the logistic function, $s_A$ is the strength of team A, and $s_B$ is the strength of team B.

This is an example of a possible model.  It might or might not be a good model.  But if we assume this model is correct, then it is possible to infer the approximate strength of each player, given the outcomes of a bunch of matches.  If $s$ is a vector that describes the strengths of all players, define $L(s)$ to be the likelihood of this vector.  In particular, $L(s)$ is formed by computing the product of the likelihood for each match that was played.  To compute the likelihood of a match between $A$ and $B$, you use $s$ to calculate the probability $p$ that A wins (assuming $s$ is the correct strength); if A actually won, the likelihood of that outcome is $p$, otherwise it is $1-p$.  (I assume there are no ties.)  For any particular $s$, you can calculate the likelihood of each match outcome like this, multiply them together, and get $L(s)$.  Now, to find the "best fit", you find the vector $s$ that maximizes $L(s)$.  This is known as a maximum-likelihood method.

How do you find the vector $s$ that maximizes $L(s)$?  Basically, you use some mathematical optimization method, like gradient descent.

If you assume this model is correct, another procedure to find the strengths of the players would be to use logistic regression.  However, ultimately this will end up being equivalent to what I articulated above.

Of course, you might find that the model I outlined is not a good model.  In that case, your task is to find a better probabilistic model that describes the probability that team A will beat team B, as a function of the strengths of the players.  Then, you can use the techniques sketched above to infer the strengths of each player.

Finally, once you have the strength of each player, the probabilistic model will let you evaluate different ways of assigning people to teams and figure out which one is most balanced (where the probability of winning for team A is as close to one-half as possible).

This approach assumes you only take into account who won, but not the score.  It would be possible to consider more sophisticated probabilistic models that also try to describe the distribution of scores as a function of the strengths of the players, but this will be more complex.  I suggest you stay simple for now.

You could also look at the Elo rating system and research whether there's any way to generalize it to apply to your setting, where each team has multiple players and you want to rate the strength of each individual player.


What are positive and negative circles in weighted digraph? I am going through Warshall and Floyd algorithms and I read that Floyd's algorithm does not hold if a graph has negative circle. I have not been able to fully figure out what  negative circle means. Therefore, I would like to know  more about positive and negative circles.

A circle is a path in the graph ($v\to u_1 \to u_2 \to \cdots \to v$) starting from some node $v$, that goes back to node $v$, thus "closing a circle".

The "value" of a circle, is the sum of the weights of the edges in the circle. If they sum to a negative value -- the circle is "negative"; otherwise, it is "positive".


LTL Model of (infinitely often p) ∧ ( infinitely often q) ∧ (¬ Eventually (p ∧ q))? Can anyone give a model (pi) of the ltl formula above?

Hint: Take $p$ to mean even number, $q = \neg p$ meaning odd number.

Can you come up with a model where you have infinitely often $p$ and infinitely often $q$ but never both at the same time?


Lower bound on space of DFS keeping the running time linear $\mathsf{DFS(G, u) \text{}}$, $G = (V,E)$

Input : A Directed graph $G$ and a source vertex $u$.

Find  : Is $v$ reachable from  vertex $u$ for all $v \in V$ ?

Model of computation : Word RAM , one can represent a vector $A[1,\cdots ,n]$ of elements from a finite alphabet $\Sigma$ using $n \lg |\Sigma| + O(\lg^2 n)$ bits, such that any element of vector can be read or written in constant time.

$\mathsf{DFS \text{}}$ (Depth first search) takes $O(m + n)$ time and $O(n\log n)$ bits of space . Other known results for DFS is $O((m + n ) \log n)$ time and space  $O(n)$ bits ( see this paper) (please note that DFS in this paper have defined as two phase process 1) Forward phase 2) Backtack phase )

It is a open question that $\mathsf{DFS \text{}}$ can be done in $O(m + n)$ time and $O(n)$ bits of space. (see this paper)

How to prove the lower bound that for $\mathsf{DFS \text{}}$ if we want to keep the runtime $O(m + n)$, we cannot do better than $O(n)$ in terms of space ?

Thanks in advance.

The questions as stated seems to be beyond reach. Without the time constraint, a superlogarithmic space lower bound on your question would imply that $\mathsf{L} \neq \mathsf{NL}$, a famous conjecture in complexity theory.

What you are looking for is known as a time-space tradeoff, and these are not known for the RAM model, though similar results are known for restricted models such as the cell-probe model and comparison-based algorithms with memory (modeled as branching programs).

Time-space tradeoffs for reachability have been studied under the JAG model and its variants, which is a pebbling-based model. The best known time-space tradeoff, due to Edmonds and Poon, implies that polynomial time requires space roughly $\Omega(n/2^{O(\sqrt{\log n}})$, and this has been achieved by Barnes et al. in their paper A sublinear space, polynomial time algorithm for directed $s$-$t$ reachability. (The work of Edmonds and Poon is cited by Barnes et al.)


What is the official name of a specific type of combination algorithm Say that I have the following set of variables:

[A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z]

The values represent a list of variables from a dataset.  Each variable has a certain level of correlation with the target variable $.  The correlation increases or decreases depending on the sort of combination you use against your target $.  For example, BCJX might have a higher correlation with $ than OQTVW.  I'm going to test each possible combination against the training algorithm and output it all, with their accuracy score, in a concise CSV file.  But I don't know the name of the algorithm that might combine these variables in every possible way.

In other words, I want to find the combination with the highest correlation value and the smallest dimension.

You are probably looking for subsets of a set. If a set has $n$ elements, it has $2^n$ subsets when counting also the empty set (there is a clear correspondence to all bit strings of length $n$). So if in your case $n=26$, there are about 67 million subsets of variables to check which might be unfeasible.


Are modern programming languages context-free? Which language class are today's modern programming languages like Java, JavaScript, and Python in?
It appears (?) they are not context-free and not regular languages.
Are these programming languages context-sensitive or decidable languages? I am very confused!
I know that context-free is more powerful than regular languages and that context-sensitive is more powerful than context-free.
Are modern programming languages both context-free and context-sensitive?

Practically no programming language, modern or ancient, is truly context-free, regardless of what people will tell you. But it hardly matters. Every programming language can be parsed; otherwise, it wouldn't be very useful. So all the deviations from context freeness have been dealt with.
What people usually mean when they tell you that programming languages are context-free because somewhere in the documentation there's a context-free grammar, is that the set of well-formed programs (that is, the "language" in the sense of formal language theory) is a subset of a context-free grammar, conditioned by a set of constraints written in the rest of the language documentation. That's mostly how programs are parsed: a context-free grammar is used, which recognises all valid and some invalid programs, and then the resulting parse tree is traversed to apply the constraints.
To justify describing the language as "context-free", there's a tendency to say that these constraints are "semantic" (and therefore not part of the language syntax). [Note 1] But that's not a very meaningful use of the word "semantic", since rules like "every variable must be declared" (which is common, if by no means universal) is certainly syntactic in the sense that you can easily apply it without knowing anything about the meaning of the various language constructs. All it requires is verifying that a symbol used in some scope also appears in a declaration in an enclosing scope. However, the "also appears" part makes this rule context-sensitive.
That rule is somewhat similar to the constraints mentioned in this post about Javascript (linked to from one of your comments to your question): that neither a Javascript object definition nor a function parameter list can define the same identifier twice, another rule which is both clearly context-sensitive and clearly syntactic.
In addition, many languages require non-context-free transformations prior to the parse; these transformations are as much part of the grammar of the language as anything else. For example:

Layout sensitive block syntax, as in Python, Haskell and many data description languages. (Context-sensitive because parsing requires that all whitespace prefixes in a block be the same length.)

Macros, as in Rust, C-family languages, Scheme and Lisp, and a vast number of others. Also, template expansion, at least in the way that it is done in C++.

User-definable operators with user-definable precedences, as in Haskell, Swift and Scala. (Scala doesn't really have user-definable precedence, but I think it is still context-sensitive. I might be wrong, though.)

None of this in any way diminishes the value of context-free parsing, neither in practical nor theoretical terms. Most parsers are and will continue to be fundamentally based on some context-free algorithm. Despite a lot of trying, no-one yet has come up with a grammar formalism which is both more powerful than context-free grammars and associated with an algorithm for transforming a grammar into a parser without adding hand-written code. (To be clear: the goal I refer to is a formalism which is more powerful than context-free grammars, so that it can handle constraints like "variables must be declared before they are used" and the other features mentioned above, but without being so powerful that it is Turing complete and therefore undecidable.)
Notes

Excluding rules which cannot be implemented in a context-free grammar in order to say that the language is context-free strikes me as a most peculiar way to define context-freeness. Of course, if you remove all context-sensitive aspects of a language, you end up with a context-free superset, but it's no longer the same language.


What is an unrestricted production? I was reading an article at

What does "context" in "context-free grammar" refer to?

The production

zA -> xy

is described as being an "unrestricted" production. In what way is it "unrestricted"?

I even visited https://en.wikipedia.org/wiki/Unrestricted_grammar

which talks about unrestricted grammar as the one that is comprised of productions which have no restriction on LHS or RHS. On this note, I assume that an unrestricted production is the one with no restriction on LHS or RHS.

What restrictions are being talked about and how is the production free from such restrictions?

A single rule can not be "unrestricted".

The whole set of rules is $(T \cup N)^+ \to (T \cup N)^*$. So the class of unrestricted grammars may use any rule from this set.

Restricted classes of grammars are only allowed to use a strict subset of all rles, e.g.

right-regular grammars are restricted to $N \to T^*N^{\{0,1\}}$, and
context-free grammars to $N \to (T \cup N)^*$.

By going through the Chomsky hierarchy, you will note that the rule

$\qquad zA \to xy$

is not admitted in any but the type-0 grammars; try to see why it's not a "context-sensitive rule". That does not mean it is only ever allowed in the unrestricted class -- just that it's not in any on this list. There are many more classes.


How are the 1s and 0s derived by the minimax algorithm for the game called "nim"? I'm having trouble figuring out why the 1s and 0s are where they are in this game tree for the game Nim:

There is a statement in the book that explains the numbers but it's still not clear to me,

In implementing minimax, we label each level in the search space according to whose
move it is at that point in the game, MIN or MAX.

In the example, MIN is
allowed to move first. Each leaf node is given a value of 1 or 0, depending on whether it is
a  win  for  MAX  or  for  MIN.  Minimax  propagates  these  values  up  the  graph  through
successive parent nodes according to the rule:

If the parent state is a MAX node, give it the maximum value among its children.
If the parent is a MIN node, give it the minimum value of its children.

If I was to draw the tree by hand how would I know where to put the 1s and 0s?

The graph contains all positions reachable from the initial position. The values are determined as follows:

A leaf (a node with no children) is labeled 0 if it is MAX's turn to play, and 1 if it is MIN's turn to play.
A non-leaf belonging to MAX gets the maximum of the labels of its children.
A non-leaf belonging to MIN gets the minimum of the labels of its children.

Hopefully you can now read the book and understand why we're doing the computation in this way.


Horn clause to Prolog At the needs of my HW at uni I need to transform some Horn clauses to Prolog but I cannot figure out how to do it. I found out some guides but they describe how to do it with only one fact. So can you give me a brief example on how to do it?

Eg John is beautiful and rich

we can transform it at: not (Beautiful(John)) ^ not(Rich(John)) which is a Horn clause right? So how this can be translated it Prolog?

another example Everyone loves somebody.
Horn clause: $\forall X \exists Y Loves(X,Y)$ how can this be implemented in Prolog?

Thx in advance

A horn clause is a disjunction with at most one positive literal, e.g.

\begin{align}
\lnot X_1 \lor \lnot X_2 \lor \ldots \lor \lnot X_n \lor Y
\end{align}

The implication $X \rightarrow Y$ can be written as disjunction $\lnot X \lor Y$ (proof by truth table). If $X = \lnot X_1 \lor \lnot X_2 \lor \ldots \lor \lnot X_n $, then $\lnot X$ is equivalent to $X_1 \land X_2 \land \ldots \land X_n$ (De Morgan's law). Therefore, the above clause is logically equivalent to

\begin{align}
(X_1 \land X_2 \land \ldots X_n) \rightarrow Y
\end{align}

A Prolog program basically is a (large) list of horn clauses. A Prolog clause (called rule) is of the form
head :- tail.,
which in logic notation is $head \leftarrow tail$. Therfore, any horn clause

\begin{align}
\lnot X_1 \lor \lnot X_2 \lor \ldots \lor \lnot X_n \lor Y
\end{align}

is written in Prolog notation as Y :- X1, X2, X3, ..., Xn.

A horn clause containing no positive literal , e.g. $\lnot X_1 \lor \lnot X_2 \lor \ldots \lor \lnot X_n$ can be rewritten as $(X_1 \land X_2 \land \ldots X_n) \rightarrow \bot$, which is :- X1, X2, X3, ..., Xn. in Prolog notation.

Regarding your examples:

"John is beautiful and rich", is a CNF, and each clause contains at most one positive literal, hence it can be written in Prolog as beautiful(john). and rich(john).
$\forall X \ \exists Y \ \operatorname{Loves}(X,Y)$

That nested extential quantifier can be eleminated by Skolemization, which is introducing a new function for the extential quantifier inside the universal quantifier: $\forall X \ \operatorname{Loves}(X,p(x))$, which in Prolog notation is loves(X,p(X)).


Runtime complexity of a brute force factoring algorithm? (in terms of bits) Let N be an n bit number. A brute force algorithm factors N by trying to divide N by all of the numbers between 2 and sqrt(N). Given that dividng two n bit integers takes O(n^2) time, what is the asymptotic running time for the brute force factoring algorithm?

It is $(\lfloor \sqrt{N} \rfloor-1) \cdot O(n^2) = O(\sqrt{N} \log^2 N) = O(2^{\frac{n}{2}} n^2)$ in the worst case: for each of the $O(\sqrt{N})$ choices of the dividend you perform a division of two numbers of at most $n$ bits.

(When you factor $N$ you might repeat some of the divisions, but these can be safely ignored since there can be at most $n$ repeated divisions, for a total complexity of $O(n^3) = o(2^{\frac{n}{2}} n^2)$.)

Notice that this is the best bound we can get for your question under reasonable hypotheses.
Indeed, if the complexity of dividing two n-bit numbers is also $\Omega(n^2)$ and you apply the brute-force algorithm on a prime $N$:

$$
\sum_{i=2}^{\lfloor \sqrt{N} \rfloor} T(\log N, \log i)
\ge \sum_{i=\lceil \sqrt{N}/2 \rceil}^{\lfloor \sqrt{N} \rfloor} T\left(\frac{1}{2}\log N - 1, \frac{1}{2}\log N - 1\right) = \Omega(\sqrt N) \cdot \Omega(\log^2 N) = \Omega(\sqrt{N} \log^2 N),
$$

where $T(i,j)$ is the time it takes to divide a $i$-bit integer by a $j$-bit integer and I am assuming that $T(i,j)$ is non-decreasing w.r.t. $i$ and $j$.


Is it possible to go from code to circuit? I am wondering if it is possible to have a program that interprets programming code and is capable of turning that code into an optimized circuit. Is this possible, and if so, does it exist?

Yes, it is certainly possible.
There are compilers that will compile from code to circuits.  Classic examples would be VHDL or AHDL compilers, but you can certainly do this for any other language, to the extent that you have an upper bound on the running time of the program or that you have an upper bound on the memory use of the program and are willing to have a circuit that contains stateful elements.
In fact, you can walk down to Fry's and buy something that basically has the form you asked for: it's called a computer.  That's more or less what a computer does: it takes code written in a programming language and executes it efficiently, using an optimized circuit.  The circuit is fixed (it is the gates in the processor) and part of its input is data that depends upon the program you are executing (which is stored in the RAM of the computer).  However, you could consider this a larger circuit where part of it is hardcoded (i.e., the program part of the input is hardcoded); then you can view a computer running a program as a big circuit with part that is universal and identical for all programs (the gates of the processor) and part that depends on the program (the hardcoded input), and this immediately gives a mapping from programs to circuits.  The mapping is implemented by a compiler.


Given arbitrary integers of $K$ and $M$, can deciding $2^K$ + $M$ is a prime be in $P$? Given arbitrary integers of $K$ and $M$, is $2^K$ + $M$ a prime?
K = int(input('enter exponent K: '))
M = int(input('enter integer for M: '))

if AKS.Primality(2**K + M) == True:
    OUTPUT 'yes'
else:
    OUTPUT 'no'

I am not knowledgeable enough in number theory or any other field of mathematics to know the answer to this question.
Question
Is there a polynomial-time algorithm for this decision problem?

Assuming you mean "polynomial in the size of the binary representation of K and M", then it is extremely unlikely, but proving that it is impossible will also be very difficult.
There are polynomial time algorithms for checking primality, but they would be applied to a number whose size is K, which is a lot bigger than checking a number whose size is the same as the size of K.


If I have sources and sinks of a DAG can I find the minimum number of edges to be added to make it Strongly Connected? I am trying to create an algorithm in linear time where if given a directed acyclic graph I can add edges to make it strongly connected components.

I believe I have an algorithm to identify sources and sinks in the input list of edges in form

1 2
2 5
3 1
etc

And I know that the minimum number of edges to be added in order to create connected components is equal to MAX(sources,sinks).

My question is, is there a way to come up with where I should add edges so that I can have the minimum number and still be linear complexity?

Here is an example of what I'm after.

Given this input edges:

1 3
1 4
2 3
2 4
5 7
5 8
6 8
6 9

Output these edges to be added:

3 1
4 5
7 6
8 1
9 2

Assuming there are no isolated vertices in the graph you only need to add $max(|\mbox{sources}|,|\mbox{sinks}|)$ edges to make it strongly connected.

Let $T = \lbrace t_1,\ldots,t_n\rbrace$ be the sinks and $\lbrace s_1,\ldots,s_m \rbrace$ be the sources of the DAG. Assume that $n \le m$ (the other case is similar). Consider a bipartite graph $G(T,S)$ between the two sets defined as follows: $G(T,S)$ has an edge $(t_i, s_j)$ if and only if $t_i$ can be reached from $s_j$.

Let $M$ be a maximal matching in $G(T,S)$. Without loss of generality assume that $M$ consists of $k$ edges: $\lbrace (t_1, s_1), (t_2, s_2), \ldots, (t_k, s_k) \rbrace$. In the original DAG $G$, add directed-edges $\lbrace (t_1\rightarrow s_2), (t_2\rightarrow s_3), \ldots, (t_{k-1}\rightarrow s_k),(t_k\rightarrow s_1)\rbrace$. It's easy to see that by adding these edges, the vertices induced by $M$ are strongly connected in $G$.

Now consider the remaining vertices in $G(T,S)$. Because $M$ is maximal, each vertex in $S-M$ (resp. $T-M$) should be connected to a vertex in $T$ (resp. $S-M$). So we pair up the remaining vertices arbitrarily, say $\lbrace (t_{k+1}, s_{k+1}), \ldots, (t_n, s_n)\rbrace$ and add the corresponding directed edges in $G$. For each remaining source vertex source $s_i$ ($i$ belongs to $\lbrace n+1,\ldots, m\rbrace$ we add the edge $(t_1\rightarrow s_i)$ in $G$. Thus the total number of edges added is $max(|\mbox{sources}|,|\mbox{sinks}|)$.


A general algorithm for greedy algorithms I have been refreshing on greedy algorithms as an algorithm design technique. I have read many sources for an explanation of what a greedy algorithm is, because I would like to put together a general greedy algorithm.

When reading these sources, I have gathered all of the important concepts to try to come up with this general algorithm for the greedy selection technique. By "general" I mean that it summarizes the behavior
 of the technique for all possible problem for who this technique would yield a correct solution.

I would like some input on it. Here is take 1:

Let $f$ be a function from $S$ to any set. The following algorithm tries to perform greedy choices per each search iteration of element of $S$, in order to try come up with the best possible point for $f$ over $S$ given a set of constraints $C$:

Select p0 from S;
i := 1;
Let P be a set of already chosen points from S to be initialized to {}
Let F be the set of values of f for each element of P to be initialize to {};
while S != {}:
    Make a greedy choice for p_i based on p_{i - 1};
    if f(p_i) is feasible based on constraints from C and has improved:
        p_{i - 1} := p_i;
    Add f_i := f(p_i) to F;
    Remove p_{i - 1} from S and save it in P;
 return P, F;

My specific question is: How far is this first take from being a correct generalization of the greedy selection technique for algorithmic design?

This should be fun :)

There is no such thing as the correct generalization of the greedy selection technique, because it's an informal technique. That said, there has been some effort at modeling the greedy heuristic, with a view toward understanding its limitations. This study has been initiated by Borodin, Nielsen and Rackoff, (Incremental) priority algorithms, and continued mostly by Borodin and his coauthors.

Before discussing the work of Borodin et al., let me briefly mention the subject of matroids and greedoids. They answer the following question:

  Consider the greedy algorithm for maximizing a linear objective subject to constraints. For which constraint structure does this algorithm produce optimal results?

We can think of the constraints as a set system, any member of which is a feasible solution. For hereditary set systems (any subset of a feasible set is feasible), the greedy algorithm produces an optimal result if and only if the constraints form a matroid. Greedoids answer a more refined question.

Back to Borodin's priority algorithms. The exact definition of a priority algorithm depends on the context, but here is a general flavor. There is some iterative procedure for constructing a solution for a given instance. The instance consists of a set of objects (think scheduling algorithms). At each step of the procedure, the algorithm chooses an ordering of all objects, and the best available object according to the ordering is added to the solution set. All objects incompatible with this object are thrown out, and the following iteration is executed. The process stop when the set of available objects becomes empty.

What I described above is the adaptive priority model. In the fixed priority model, the ordering is chosen once and for all rather than at each step. In both models, the algorithm is not allowed to look at the set of available objects (that would be cheating).

The situation for graph algorithms is somewhat more complicated, see for example Borodin, Boyar and Larsen, Priority algorithms for graph optimization problems, and there are several models which are more realistic than the model considered above. There are several other variants of priority algorithms which can be explored through the relevant work of Borodin and others.


Domain and range of recursive functions are recursively enumerable I want to show the following two propositions:

The domain of a recursive function is recursively enumerable.
The range of a recursive function is recursively enumerable.

I have thought the following in order to prove the first proposition.

Suppose that we have a recursive function $f$. Then we know that there is an algorithm $A$ that computes $f$.
So if $m \in dom(f)$ then we know that the algorithm $A$ with input $m$ terminates, giving output "yes".
Since $m$ is arbitrary, we deduce that the domain of a recursive function is recursively enumerable.

Is my idea right? If so, can't we also deduce from that that the domain of a recursive function is recursive since the algorithm always terminates for the elements of the domain?

Can you give me a hint how we can show the second proposition?

The first proof looks ok. (Actually, it depends on the definition you use for RE. Some authors define RE iff it's the domain of a recursive function, making the exercise trivial.)

For the second, here's a hint. Given $x$ you want to check whether $f(0)=x$ or $f(1)=x$ or ... If all of these are false, we can diverge (we must diverge, actually), but if any of these is true, we must halt. We can not proceed with a simple infinite iteration, since $f(1)$ might diverge and $f(2)$ might return $x$, and if so we need to detect that and halt anyway.

So, we need to evaluate in parallel all these programs, so that even if one of them diverges does not stop the evaluation of the others.

Think of a fair scheduler among infinitely many processes. Think about running a program for only a given number of steps. Think about doves and their tails. ;-)


Differences between ALLTM and INF The definitions of ALLTM and INF are as follows:

$$\mathrm{ALLTM} = \{ \langle M \rangle \mid \text{ TM $M$ such that $L(M) = \Sigma^*$}    \}. $$

$$\mathrm{INF} = \{ \langle M \rangle \mid \text{TM $M$ such that $L(M)$ is infinite}    \}. $$

In one of the proofs of undecidability of INF, they reduce $A_{TM}$ to INF as follows:

  Given $\langle M,w \rangle$, construct $M'$ :
  "On input $x$, simulate $M$ on $w$. If $M$  accepts w, then Accept". Clearly,  $M$ accepts $w$ when $L(M) = \Sigma^*$. "

Here, the proof for INF proof used the definition of ALLTM to show that the reduction is valid.

Can we use INF and ALLTM interchangeably? If not, what are some crucial differences in these sets?

The two sets are clearly different – there are Turing machines whose language is infinite but doesn't consist of everything. However, both languages belong to the same Turing degree, that is, each of them can be reduced to the other (computably).

Given an instance $M$ of ALLTM, construct a Turing machine $M'$ which on input $x$ runs $M$ on all inputs $y \leq x$ (in some arbitrary computable ordering of all strings). Then $M$ is total (i.e., halts on all inputs) iff $M'$ halts on infinitely many inputs.

Given an instance $M$ of INF, construct a Turing machine $M'$ which on input $x$ runs $M$ in parallel on all inputs $y \geq x$, and halts once one of the runs halts. Then $M$ halts on infinitely many inputs iff $M'$ is total.

(In fact, both ALLTM and INF are $\Pi_2$-complete.)


Is this data structure a hypertree or they are just isomorphic trees? I have a data structure described as following:

- It's a collection of trees.
- Each tree has the same structure.
- Each tree has information of diferent nature.

A example of this data structure:

    4 - - - - - - - 'a' - - - - - - - 3.5
   / \              / \               / \
  3   1           'f' 'y'           1.0 3.1
     / \              / \               / \
    4   7           'e' 'f'           2.3 7.7

If you see, ignoring the contents of each tree, each of them is just the same tree (the same hierarchy, the same structure). The first contains natural numbers, the second one, characters, and the third one, floating numbers.

The idea of this data structure is that diferent classes (in a C++ program for example) explore diferent "layers" of this tree, in order to each class uses only the information this class needs, ignoring the remaining information. In other words, each class sees only one tree.

Does this data structure match with a hypertree or can it be reformulated/adapted to a hypertree? Or just they are isomorphic trees put together is a same data structure?

You can describe what's going on here with the notion of a functor, extending things which you would do naturally with three different types (ints, chars, and floats) to trees over these types.

What you have is in effect only a single tree, e.g.
$$
T = \left\{\mspace{45mu}\begin{array}{c@{}c@{}c}
& (4,a\mspace{-18mu}&,3.5) \\
&/&\backslash \\
&\mspace{-60mu}(3,f,1.0) & (1,y\mspace{-36mu}&,3.1) \\
& &  /&\backslash \\
& &\mspace{-60mu}(4,e,2.3) & (7,f,7.7)\mspace{-60mu}
\end{array}\mspace{50mu}\right\}
$$
and mappings from this tree over tuples, to the trees which are visible by the classes,
$$
A = \left\{\mspace{-10mu}\begin{array}{c}
4 \\
\;/ \;\;\backslash &  \\
\;3 \quad 1 \\
\;~ \quad\; / \;\; \backslash \\
\;~ \quad\;4 \quad7
\end{array}\mspace{-10mu}\right\},
\qquad
B = \left\{\mspace{-10mu}\begin{array}{c}
a \\
\;/ \;\backslash &  \\
\,f \quad y \\
\,~ \quad\; / \;\; \backslash \\
\,~ \quad\;e \quad f
\end{array}\mspace{-10mu}\right\},
\qquad
C = \left\{\mspace{-20mu}\begin{array}{c}
3.5 \\
\,/ \;\;\backslash &  \\
\;1.0 \quad 3.1 \\
\;~ \quad\;\;\;\; / \;\; \backslash \\
\;~ \quad\;\;\;\; 2.3 \quad 7.7
\end{array}\mspace{-10mu}\right\}.
$$
The mappings which carry $T \mapsto A$, $T \mapsto B$, and $T \mapsto C$ can be desribed in terms of the projectors
$$\begin{align*}
\pi_1 \;\;:\;\; \text{int} \times \text{char} \times \text{float} &\to\;\; \text{int} \;, \\
\pi_2 \;\;:\;\; \text{int} \times \text{char} \times \text{float} &\to\;\; \text{char} \;, \\
\pi_3 \;\;:\;\; \text{int} \times \text{char} \times \text{float} &\to\;\; \text{float}
 \;.
\end{align*}$$
Each of these "projector" maps $\pi_j$ can be extended to a mapping on trees, using the tree functor which carries all functions $f: A \to B$ to functions on trees, $\text{Tree}(f) : \text{Tree}(A) \to \text{Tree}(B)$ in the obvious way, preserving the tree structure for any given tree, and applying the function $f$ to each node in the tree. Thus
$$\begin{align*}
A &= \Bigl[\text{Tree}(\pi_1)\Bigr](T), \\
B &= \Bigl[\text{Tree}(\pi_2)\Bigr](T), \\
C &= \Bigl[\text{Tree}(\pi_3)\Bigr](T).
\end{align*}$$
So these trees are just the images of $T$ under projection maps in the natural way; they aren't meaningfully independent of one another, and what the classes do which can only access one of these trees is that they can only access information about $T$ through these projections.


How to prove that the Myhill-Nerode equivalence classes for L are the same as for its complement? Given language $L$, I want to show that its Myhill-Nerode equivalence classes are the same as for its complement $\overline{L}$.

I am thinking of constructing a DFA $M$ for the Language $L$ so the DFA for the language of its complement will be just changing the final states to non final states but the states will be same. So the classes do remain same? How do I put this in a more formal way?

Note that the Myhill-Nerode equivalences are also defined for non-regular languages, so constructing a finite state automaton will not help.

What is the definition of such a class? $x \sim_L y$ iff $xz\in L$ whenever $yz\in L$ (for any string $z$). How does that change when we consider the complement of $L$? We use basic logic: $P\Leftrightarrow Q $ iff $\lnot P\Leftrightarrow \lnot Q $.

$x \sim_L y$
iff  $xz\in L$ whenever $yz\in L$ (for any string $z$)
iff  (not $xz\in L$) whenever (not $yz\in L$) (for any string $z$)
iff  $xz\in \bar L$ whenever $yz\in \bar L$ (for any string $z$)
iff  $x \sim_{\bar L} y$.


Randomized Algorithms Probability I'm taking a grad level randomized algorithms course in the fall. The professor is known for being very detail oriented and mathematically rigorous, so I will be required to have an in-depth understanding of probability. What would be a good probability book to learn from that would be intuitive, but also have some mathematical rigor to it?

What textbooks does the course recommend? I like "Probability and Computing" by Mitzenmacher and Upfal and "Randomized Algorithms" by Motwani and Raghavan. They introduce the necessary theory from an algorithms viewpoint. I also recommend a book on inequalities, as bounding things is quite essential to the analysis of randomized algorithms. At the very least this cheat sheet.


Would time travel be useful for optimization? Let's say we have circuitry that can send pieces of data to the past state of the program through literal time travel. Said time travel takes 1-5 clock cycles (I cannot assume the nature of time travel so I am giving slight lee-way) and sends one byte to some byte in the past programs memory along with a check bit to some other location so that the time travel can be detected. The general purpose would be for the program to basically run once and then essentially bootstrap paradoxing the original calculation, thereby in essence only taking the amount of time it took to send the data back to the program's past state.

Would it actually be realistic for a user level  or utility program to use this as a fast/cheap way to optimize a program? My guess is that it is only good for extremely complex calculations such as prime number searches, framebuffer generations for 3D graphics, etc. but I cannot be entirely sure.

Assuming this were in the C language, the syntax for code to be bootstrapped would look like this (in case one wishes to write examples of cases they find contradictory)

bootstrap (<checkbit to see if time travel has occurred>)
{
    <code to process and create the original data>

    send: <list of addresses to be sent back separated by commas>
    to: <list of addresses of where the data should be sent to separated by commas>
}

Assume energy/radiation/side effects of time travel are irrelevant. This assumes that it is literally as easy to time travel as it is to run an adding circuit. Also, assume that people have worked out all the "bugs" from the system. The circuit works correctly without fail.

I apologize if this is the wrong stack exchange site. I wish to speak scientifically regarding this in a real theoretical sense and this seemed like the more theoretical CS stack exchange site.

Yes.  If time travel were possible, it would be a huge win for optimization and computation: it would enable us to solve computational problems that today seem very hard to solve with existing computers.

To formalize this, we must first agree on a model of physics that allows time travel and that describes what happens when you try.  There are various plausible ways to do that.  Under one plausible set of assumptions about the physics, the set of problems you can solve in polynomial time using time travel is all of PSPACE.  (If you're not familiar with it, PSPACE is the set of problems solvable by classical no-time-travel computers in  any amount of running time you want, subject only the restriction that the space usage must be polynomial.)  For instance, every problem in NP could be solved in polynomial time if time travel were possible.

For instance, there are problems that today seem to require exponential time to solve (with classical no-time-travel computers), but could be solved in polynomial time if time travel were possible.

To learn more about this subject, I suggest you take a look at Scott Aaronson's lecture notes: http://www.scottaaronson.com/democritus/lec19.html


Improve Markov Chain results Apologies for another Markov Chain question but this one is best given its own question to avoid confusion. I am using a Markov Chain to get the 10 best search results from the union of 3 different search engines. The top 10 results are taken from each engine to form a set of 30 results.

The chain starts at State x, a uniform distribution of set S = {1,2,3,...30}. If the current state is page P, select page Q uniformly from the union of the results from each search engine. If the rank of Q < rank of P in 2 of the 3 engines that rank both P and Q, move to Q. Else, remain at P.

This results in a number of pairwise comparisons being carried out. result2 is compared with result1 and a count is made of each time result2 ranks better than 1. The results are sorted by the results of the pairwise comparisons, with the lowest score ranked first. e.g.

Engine Rankings:                       Pairwise Comparison:
         eng1   eng2   eng3                    result1  result2  result3  result4  result5
result1   1      2      2              result1    0        1        0        0        1
result2   4      3      1              result2    2        0        1        2        2
result3   2      4      5              result3    3        2        0        1        2
result4   5      5      3              result4    3        1        2        0        1
result5   3      1      4              result5    2        1        1        2        0

The problem with this example is, if we add the total of each row in the pairwise comparison, we get {2,7,8,7,7}, leaving 3 different results with the same score. I'm wondering if there is a method to further sort these results in order to refine the results so that I'm not left with a number of results that have the same score? I've seen Keminization but I can't see how this would apply? Can someone please give me some guidance?

Let $\mathcal{S}$ be the state space of your Markov chain, and assume that we start at some state $i \in \mathcal{S}$. Let $\mathcal{Y}_i$ be the set of states (pages) that are ranked lower than $i$ by two of the three engines. According to your description, the probability of transition to state $j$ can be defined as follows:

\begin{equation}
P_{ij} =
 \begin{cases}
  1 - \frac{|\mathcal{Y}_i|}{|\mathcal{S}|} & \text{if } j = i, \\
  \frac{1}{|\mathcal{S}|} & \text{if } j \in \mathcal{Y}_i, \\
  0 & \text{Otherwise}
 \end{cases}
\end{equation}

If I have understood your question correctly, this Markov chain does not always produce credible results due to the following issues. First, your chain allows repetitive comparisons. In other words, it is likely that a state $i$ is compared against some state $j$ multiple times. This, of course, does not make trouble as long as your chain is irreducible. However, in some cases, you will not get the correct result. For example, consider the following scenario.

Imagine for some state $i \in \mathcal{S}$, no state (page) can be found that is ranked lower than $i$ by two other engines, that is $\mathcal{Y}_i = \varnothing$. Therefore, $P_{ii} = 1$ making $i$ an absorbing state. In this case, your chain will be trapped in state $i$ in finite time, and from then on, it will only compare state $i$ against other states repeatedly. If chain is trapped in such a state and you let it run for a long enough time, then your results would clearly be wrong. Similar problem occurs if your chain contains recurrent sub-classes.

Assuming that no such states exist, then you would have an irreducible chain. In that case, if you let the chain run for sufficiently long time, the counting process would result in a good approximation of correct rankings (according to your algorithm).

P.S. This answer is just based on my understanding of your problem and may not be 100% correct.


Relational algebra statement for a query For the following schema

Country ("countryID", cName)
CoffeeShop ("shopID", sName, countryID, city)
Product ("productID", size)
Serves ("shopID", "productID")
ProductNames ("productID", "countryID", pName)

where attributes in quotation marks are primary keys, I must write a relational algebra statement for the following query:

List names of products that have same names in all countries they are served.

The thing that made me stuck on this problem is the fact that the product must not necessarily be served in all countries, but rather have the same name in all countries it is served. Without comparing for an initial value, I couldn't get a solution that makes more sense and that is possible to be written as a relational algebra statement.

Hint: A product has the same names in all countries if for every two countries, it has the same name in both countries.


Relevance of memory reads while calculating the time complexity of an algorithm Can there be a genuine algorithm in which number of memory reads far outnumber the
no. of operations performed? For example, number of memory reads scale with n^2, while no. of operations scale with only n, where n is the input size.

If yes, then how will one decide the time complexity in such a case? Will it be n^2 or only n?

For a memory read to be relevant to the algorithm, the information read in must be processed in some way.
If the information is never compared or used as input to any operator, it will not affect the algorithm and thus was unnecessary to read in the first place.
If there were an operator that could accept a variable number of inputs, a number that could grow without bounds, then and only then could you have the number of memory reads far outnumber the number of operations in the way you describe.  For instance, if "sum" were a single atomic operation accepting any number of inputs, then you could have such an algorithm.
However, a model of computation where a single operation could utilize an unlimited number of inputs is not very interesting nor very useful for algorithmic analysis.  It would essentially just push all the hard work to a lower level of abstraction.  So you won't find such a model in any CS literature.

A paragraph from an MIT Open CourseWare PDF about communication networks as in Graph Theory makes a related point (related to what I said about just pushing the hard/interesting work to a different level of abstraction) in discussion of switch sizes:

One way to reduce the diameter of a network (and hence the latency needed to route packets) is to use larger switches. For example, in the complete binary tree, most of the switches have three incoming edges and three outgoing edges, which makes them $3 \times 3$ switches. If we had $4 \times 4$ switches, then we could construct a complete ternary tree with an even smaller diameter. In principle, we could even connect up all the inputs and outputs via a single monster $N \times N$ switch, as shown in Figure 6.9. In this case, the “network” would consist of a single switch and the latency would be $2$.
This isn’t very productive, however, since we’ve just concealed the original network design problem inside this abstract monster switch. Eventually, we’ll have to design the internals of the monster switch using simpler components, and then we’re right back where we started. So the challenge in designing a communication network is figuring out how to get the functionality of an $N \times N$ switch using fixed size, elementary devices, like $3 \times 3$ switches.


Where Can I Find DFA Practice? Where can I find a web site or book where I can practice drawing DFAs from a language like " {w| w has at least three a’s and at least two b’s} ". It will be important to have access to the answer so as to check myself. I need the practice.

Well you have a little problem between your hands. The problem is that creating a DFA that generates some language $L$ have more than one solution. In fact if $L$ is regular then it have infinite solutions. If you are searching a book with answers it may not be usefull because your answer can be correct even though it is different from the one in the book.

There is some methods to prove the correctness of a DFA using proof by induction but it is fairly difficult. If you are having problems generating DFA I wouldn't reccommend to try proving the correctness until you are more experienced into this topic.

My teacher told me that the best you can do to be sure that your DFA is correct(when you skipping the proof of correctness) is do it in a sistematic way and understandable for anyone that reads it.


Is the runtime complexity of sorting $O(n\log n)$ or $O(n\log^2 n)$? Suppose we want to sort an array that contains $n$ different integers in the range $[1,2n]$. It is known that this requires $\Theta(n\log n)$ comparisons. But comparing integers which might be as large as $n$ might requires time $\Theta(\log n)$ since we have to compare them bitwise. So, apparently the runtime complexity of sorting is $\Theta(n\log^2 n)$. Is this correct? If so, why is it taught that the complexity of sorting is $\Theta(n\log n)$? Is there a better algorithm for sorting which runs in time $\Theta(n\log n)$?

EDIT: I understand that the question depends on the computational model. In fact, I just found an interesting unanswered question that specifically asks about the runtime complexity of sorting on a Turing machine. Originally, I had in mind a realistic computer, only with unlimited memory. In such a computer, we can represent arbitrarily large integers (as sequences of bytes). We are given an array that contains $n$ different integers, each of which is between $1$ and $2n$. We measure the clock-time it takes to sort this array, as a function of $n$. What function will we see?

Algorithms are usually analyzed using the random access machine model. In this model, arithmetic operations on machine words take time $O(1)$. A machine word contains $O(\log n)$ bits, where $n$ is some natural parameter, say the length of the input (in machine words!).

Given this definition, comparison-based sorting algorithms run in time $O(n\log n)$ as long as the arguments fit in a constant number of machine words.

Sorting algorithms probably take more than $n\log^2 n$ time on a Turing machine, since Turing machines have no random access. Turing machines are not so interesting, however, for analyzing the running time of algorithms, except for special circumstances such as proving results on the Turing machine model itself.

In your particular case, you can actually sort the array in $O(n)$ using counting sort. The $\Omega(n\log n)$ lower bound only holds for some models such as the comparison model.


What does $\log^{O(1)}n$ mean? What does $\log^{O(1)}n$ mean?

I am aware of big-O notation, but this notation makes no sense to me.
I can't find anything about it either, because there is no way a search engine interprets this correctly.

For a bit of context, the sentence where I found it reads "[...] we call a function [efficient] if it uses $O(\log n)$ space and at most time $\log^{O(1)}n$ per item."

You need to ignore for a moment the strong feeling that the "$O$" is in the wrong place and plough on with the definition regardless.  $f(n) = \log^{O(1)}n$ means that there exist constants $k$ and $n_0$ such that, for all $n\geq n_0$, $f(n) \leq \log^{k\cdot 1}n = \log^k n$.

Note that $\log^k n$ means $(\log n)^k$.  Functions of the form $\log^{O(1)}n$ are often called polylogarithmic and you might hear people say, "$f$ is polylog $n$."

You'll notice that it's easy to prove that $2n=O(n)$, since $2n\leq k n$ for all $n\geq 0$, where $k=2$.  You might be wondering if $2\log n = \log^{O(1)}n$. The answer is yes since, for large enough $n$, $\log n\geq 2$, so $2\log n \leq \log^2n$ for large enough $n$.

On a related note, you'll often see polynomials written as $n^{O(1)}$: same idea.


Approximation algorithm to visit all nodes in an undirected, weighted, complete graph, with shortest sum of edge weights I'm looking for an algorithm that gives a smallest value of 'travel cost' within the following constraints:

a complete, connected, weighted graph,
vertices are defined in 3d euclidean space,
relatively low number of vertices (less than 500)
no limits on how many times a node may be visited
a fixed starting vertex
no requirement for which vertex to end at.

I've looked at minimum spanning tree algorithms, but those could create sub-optimal result, because they optimize for lowest summed edge weight.

I'm suspecting this may be a variant of the traveling salesman problem and thus NP-hard. For our use case however, a good approximation will be good enough.

Suppose $G$ is a weighted graph, and $T_{OPT}$ is the optimal route you seek.

For clarity: $T_{OPT}$ is a path that connects all vertices, such that for any other path $P$ that connects all vertices, it holds that $w(T_{OPT}) \leq w(P)$.

Denote $M$ for the MST of $G$. Since $T_{OPT}$ is a subgraph of $G$ that connects all its vertices, we can say:

$w(M) \leq w(T_{OPT})$ - by definition of MST.

Denote $M^*$ An euler tour of $M$. Since $M^*$ visits each edge of $M$ exactly twice, it holds that:

$w(M^*) = 2w(M)$
$M^*$ is some path that visits all vertices of $G$, hence a path that solves your problem (although we cannot say $w(M^*) = w(T_{OPT})$)

Following from 1. 2. and 3. we get:

$$w(M) \leq w(T_{OPT})$$
$$2w(M) \leq 2w(T_{OPT})$$
And, since $w(M^*) = 2w(M)$
$$w(M^*) \leq 2w(T_{OPT})$$


Convoy effect in priority scheduling and SJF (Non preemptive) In books, I have read that FCFS suffers from convoy effect. I think that even SJF and priority(both preemptive and non preemptive) can suffer from convoy effect.

In SJF, if a process with large burst time arrives first then no other process can preempt it causing convoy effect.

In preemptive and non preemptive priority, if all processes arrive at time 0 and if a high priority process has very large burst time, it can lead to convoy effect as no other process can preempt this process because they all have lesser priority.

Am I correct?

Cant comment but here is some clarification. Using the preemptive sjf, a process with a smaller burst can remove a process with a bigger burst that is currently occupying the cpu, this eliminates the convoy effect but can create a starvation effect whereby shorter procesess keep cutting off long and old processes. A priority based sheduling is efficient if it keeps in account how long a process has been waiting in the wait-queue and also its cpu-burst, a good example is the HRRN method, where the priority of a process is calculated taking in account the afore mentioned criterias. So if the priority


Fine-grained complexity of 3-CNF formula evaluation It's well known that 3-SAT is in NP, which means that one can evaluate a 3-CNF formula in polynomial time. However, I was wondering what the tightest upper bound is for formula verification, expressed in big-O notation or some other way.

My best guess is that 3-CNF formulas can be verified in linear time in the number of clauses. Each clause has two disjunctions and up to three negations, which should each require one step to evaluate. If you count replacing a literal with its assigned value as a step, that gives you at most 8 steps per clause. Then, once all the clauses are evaluated, you should need [# of clauses] - 1 steps to compute all the conjunctions between them. So with $x$ clauses, that's at most $8x + x - 1 = 9x - 1$ steps total, which is $O(x)$.

Obviously, if I'm wrong about that, please let me know, and if there are even better time bounds (either theoretical or practical), I would love to hear about those as well.

Yes, you are correct.  Your analysis is fine.  It takes linear time.

It's also easy to see that it's not possible to do better than linear time: any algorithm will have to read the entire input (in the worst case), which itself takes linear time.


Comparing sets of vectors If $u,v \in \mathbb{R}^d$ are two $d$-dimensional vectors, say that $u\le v$ if $u_i \le v_i$ for all $i=1,\dots,d$.  In other words, comparisons on vectors will be pointwise.

Let $S,T$ be two subsets of $\mathbb{N}^d$ of size $m$.  Is there an efficient way to test whether there exists $s\in S, t \in T$ such that $s\le t$?  The naive algorithm does $m^2$ comparisons between vectors; is there a more efficient algorithm?

If $d=1$, this is very easy: we simply find the smallest element in $S$ and the largest element in $T$, which can be done with $O(m)$ comparisons.  But already when $d=2$, it seems much harder.  Any ideas?

In the case $d=2$, it is possible in $O(n \log n)$ time. First, sort the input elements on their first component. Then, use a recursive divide&conquer strategy: if a pair of comparable elements exist, then either:

Both elements are contained in the first half of the list
Both elements are contained in the second half of the list
A pair can be formed by taking on element from the first half and one from the second half

Cases 1 and 2 can be solved by recursion. Case 3 can be solved by finding the element from the first half with the lowest second component and finding the element with the highest second component from the right list.

It is possible to implement the divide&conquer strategy in $O(n)$ time so the time complexity is dominated by presorting the list, taking $O(n \log n)$ time.

When going to $d=3$, a similar strategy might be possible, but the third case is harder: given two sets of 2-dimensional vectors $A,B$ it requires finding $a\in A,b\in B$ such that $a\leq b$.

Edit: the following paper may be relevant, it computes for each vector how many vectors are ranked lower in less than quadratic time. http://www.cs.uiuc.edu/class/fa05/cs473ug/hw/p214-bentley.pdf


Optimized resource allocation problem I am from ECE background and trying to solve channel allocation problem. Let's assume I have three users and three available channels. I would like to allocate channel among them in such a way that average BER would be minimum.
For example, consider BER matrix for each user for each frequency allocation
\begin{bmatrix} User/frequency & User1 & User2 &  User3 \\ f1 &0.01 & 0.05 & 0.3\\f2 & 0.12 & 0.045 & 0.02 \\ f3 &0.02 & 0.01 & 0.01 \end{bmatrix}

Now, I would like to allocate channels f1--> User1, f2--> User3 and f3-->User2, which gives least average BER (Sum of each users BER/no of users).
(Note: Same frequency can't allocated to different users.)

Brute force is obliviously one solution, but I am trying to find optimized solution.

This is just the assignment problem: you need to find a maximum-weight matching between the users and frequencies.  The Hungarian algorithm solves this in time $O(n^3)$.


A string that takes a DFA from any state to a given state? EDIT: as templatetypedef commented, this problem is to find out if a DFA has a synchronizing word (a.k.a. "reset sequence").

Given a finite state set $Q$, a finite alphabet $\Sigma$, and a transition function $\delta : Q \times \Sigma \rightarrow Q$, I want to find out if there is a state $q_f \in Q$ and a string $s \in \Sigma^*$ such that for every state $q_0 \in Q$ (including $q_f$), the DFA $\left( Q, \Sigma, \delta, q_0, \left\{ q_f \right\} \right)$ accepts $s$. ($q_0$ is the initial state; $q_f$ is the only accepting state.)

In other words, if you think of a string as a list of directions for navigating the DFA, I want to find out if there is a list of directions that takes you to the same state no matter where you started. (Knowing the existence is enough; I do not need to know the state or the string itself.)

I have tried this algorithm:

Reverse the transitions in $\delta$ to form an NFA.
Convert the NFA into a DFA where each state corresponds to a subset of the NFA's states.
For each state $q \in Q$, search the new DFA for a path from $\left\{ q \right\}$ to $Q$. (I just do a depth first search.)
Iff one of these searches is successful, then the answer to the question is "yes".

This algorithm is correct, but it runs in exponential time and space, and it takes too long to complete. (My input DFAs have tens of states.) Note that I do not actually construct a DFA from the NFA -- instead, I perform the search on the NFA and I remember which subsets of its states I have visited.

Is there a way to improve my algorithm? Are there other algorithms to solve this problem? (Or at least, algorithms that would be useful?) Are there any properties of automata and regular languages that I can take advantage of?

It turns out that there exists a string that takes all states to the same state iff for each pair of states, there exists a string that takes both states to the same state.

Using this fact, I had success with the following algorithm:

Generate a new DFA from the Cartesian product of the old DFA with itself. (The new DFA contains $\left(a,b\right) \overset{x}{\rightarrow} \left(c,d\right)$ iff the old DFA contains $a \overset{x}{\rightarrow} c$ and $b \overset{x}{\rightarrow} d$, where $x$ is an input symbol and $a$, $b$, $c$, and $d$ are states.)
For each state $\left(a,b\right), a \neq b$ in the new DFA, search for a path from $\left(a,b\right)$ to a state of the form $\left(c,c\right)$. (If found, then that means there is a string that takes the old DFA from $a$ to $c$ and from $b$ to $c$.)
There is a reset sequence for the old DFA iff every search in the above step yields such a path.

More info:

https://www.ics.uci.edu/~eppstein/pubs/Epp-SJC-90.pdf


Looking for a succinct dynamic sorted dictionary I was digging through research articles to find a data structure that solves the dynamic sorted dictionary problem (representing any subset $S$ of a universe $U = \{0, \ldots, u\}$ with member/predecessor/successor queries), but sadly I was able to find none. I did find succinct solutions to the following problems:

Dynamic non-sorted dictionary
Dynamic indexable bitvector (which is no good if the universe, say $[2^{64} - 1]$ is too big to store), not to mention storing a simple set, $\{u\}$ uses up the maximum amount of space
Static indexable dictionaries

Dynamic succinct sorted/indexable dictionaries, however, do not seem to exist. (I do not actually need indexable dictionaries, just sorted ones with predecessor/successor queries, but it looks like this isn't really any easier to solve, either.)

What are some viable succinct data structures for solving this problem? Time bounds are not too important as long as they're not overly large (like $O(|U|)$). If there's no such data structure (yet), what is the second best option? Exponential search trees? Dynamic fusion trees? Multiple underlying data structures based on sparseness? (I prefer data structures with worst-time operation guarantees to those with amortized ones.)

If you can tolerate $O(\sqrt{n})$ time complexity, I'd go for bi-parental heaps by Munro and Suwanda. This seems like an elegant implementation that should have $O(\sqrt{n})$ memory overhead in practice.

If your sets are too large for that, I'd try this data structure by Frederickson. You'll need a Hashed Array Tree to make it work with malloc.

Theoretically, a solution with $O(\log n)$ time per operation is possible. See this extended abstract by Franceshini and Grossi, and my bachelor's thesis that goes into greater detail and fixes some of the bugs.

Note that, apart from the bi-parental heap, I am not aware of any implementations. The asymptotically optimal solution probably has excessive multiplicative constants and I still need to complete it (which shall be my master's thesis).


Arden's Lemma in case $X_{i}=AX_{i}$? Arden's lemma is applied in cases where we have an equation that looks like this: $$ X_{i}=AX_{i} + B, $$ with the condition that $\epsilon \notin A$.

But if I have such situation: $$X_{i}=AX_{i},$$ so there's no B, or simply talking we have $B= \varnothing $, thus by the Lemma, we have $$X_{i}=A^{*}\cdot\varnothing$$ which equals to $$X_{i}=\varnothing.$$

Is my reasoning correct?

What we have with

$\qquad X = AX + B$

is, quite literally, a recurrence of languages expressed in terms of the symbolic method. $B$ represents the base case of the recurrence. Arden's Lemma just tells you that the smallest fixpoint of this recurrence (read as an inductive definition) is $A^*B$.

Now, if you drop the base case and only have

$\qquad X = AX$,

there are no finite words that can be constructed in this way. Now, the "recurrence" may make sense read as a coinductive definition (that is the solution would be an $X$ containing infinite strings) but not as an inductive one. Hence, the empty set is the only one that solves the equation.


Naive Bayes' Classification and Using the Entire Vocabulary in the Denominator I am working through the NLP notes for Naive Bayes' classification here: https://web.stanford.edu/~jurafsky/slp3/6.pdf

Below $c$ is the class of the observation and $w_i$ is the $i$th word of a text document.

In developing the maximum likelihood estimate for the conditional probability of the feature (word) $w_i$ given class $c$ the following expression is given for the conditional probability:

$$\hat{P}(w_i \mid c) = \frac{count(w_i,c)}{\sum_{w\in V} count(w,c)}$$

It is mentioned that $V$ consists of the union of all the word types in all classes, not just the words in one class $c$. The importance of this fact is stressed later on when add-one (Laplace) smoothing is used to avoid probability estimates that equal 0.

It is mentioned that:

It is crucial that the vocabulary $V$ consists of the union of all the word types in all of the classes, not just the words in one class $c$ (try to convince yourself that this is true).

I have thought for awhile on this aside given in the text, but it does not seem to make much sense. To me, wouldn't $count(w,c)$ always equal $0$ for any $w$ which is not contained in a document of class $c$? Why sum over all words in the vocabulary if they will just equal $0$?

If you're using Laplace smoothing, you'll replace the count with a "pseudocount", and that won't be zero.  So, it does make a difference.


algorithm for checking satisfiability In order to prove that SAT is in NP, I need to come up with a polynomial time verfier (an algorithm). The Cooks Levin Theorem uses a non-deterministic Turing machine but that's not what I am looking for.
The idea of the algorithm could be that we put in the values and calculate the answer. Then, we check whether the answer is 1 or not. However, I am unable to understand how I could write a psuedocode for the 'putting in values' part and then show that it's polynomial for sure.
if x = 1:
 accept
else:
 reject

This could be in O(1). But what about the remaining part?

Here is how I would do it:
Algo: Verifier for DNF-SAT problem given as array of closures and a possible mapping of literals to booleans
Input:
Array of closures: [$C_1$,$C_2$,...,$C_m$]
where $C_j \subseteq \{x_1,...,x_n,\neg x_1, ... \neg x_n\}$
(Certificate) Array $M$ where $M_i$ is the boolean value of literal $x_i$
Output: true or false
for $i = 1$ to $m$:
  value = true
  for literal in $C_i$:
    if literal == $x_i$:
      value = value or $M[i]$:
    else if literal == $\neg x_i$:
      value = value or (not $M[i]$)
  if not value:
    return false
return true

Note: the math notation is indented and commonly used in pseudocode sadly cs stackexchange doesn't support it


How to check if DFA is actually a correct model of the intended system? Suppose I have modeled a deterministic finite automaton of my system. How can I check if the traces generated by this system, actually represent the model I had in mind?

For example, say I have DFA A which models a vending machine. To ensure I did not model any wrong transitions, is coming up with  (safety/liveness) specifications and performing verification the only method I can follow to ensure my model is correct? Many thanks.

If you want a guarantee, then yes, verification is the only approach.  That's pretty much the definition of what verification means.

If you want a heuristic check, there are a number of testing methods based on synthesizing test cases (perhaps based on the DFA) and then checking that the vending machine's actual behavior on those test cases matches your DFA's.


Efficient data structure handling insert(number) and find(sum) returning pair a,b such that a + b = sum There are two operations as follows:

insert(num): insert num into the data structure.
find(sum): return a pair(a, b) such that a + b = sum, if no such pair exists return -1

How such data structure could be designed, possibly with find $\in o(N)$ and insert $\in o(\log N)$ operations?

It's unlikely that a data structure exists that supports both $insert(\cdot)$ and $find(\cdot)$ queries in $o(n/\log^2 n)$ time, since if it did, then we could use it to solve the 3SUM problem in $o(n^2/\log^2 n)$ time, beating the best known algorithm for this problem, which takes $O(n^2 (\log \log n)^{O(1)}/\log^2 n)$ time.

In 3SUM, we are asked to find 3 distinct elements that sum to zero in a list of distinct integers $x_1, \dots, x_n$.  We can reduce this problem to your problem as follows:

For each $i$ from 1 to $n$:

Call $find(-x_i)$.  If this succeeds, with return value $(x_a, x_b)$, then $x_a, x_b, x_i$ are all distinct and sum to zero: return TRUE.
Call $insert(x_i)$.

Return FALSE.