Myhill-Nerode and closure properties It is well known that regular languages are characterized by the Myhill-Nerode equivalence. For language $L$ over $\Sigma^*$ define the equivalence $x\sim_L y$ over $\Sigma^*$ iff for all $z\in\Sigma^*$ we have $xz\in L \iff yz\in L$. Then $L$ is regular iff $\sim_L$ is of finite index, i.e., has a finite number of equivalence classes.

I know that the relation can be used to show that some languages are not regular, by indicating infinitely many strings that are not equivalent.

My question: can we easily use Myhill-Nerode to show closure properties of regular languages? Or should we use the "syntactic congruence" of languages?

As an example for prefix it is easy, as $x\sim_L y$ implies $x\sim_{\mbox{pref}(L)} y$.  But how do we handle suffix, concatenation, star, mirror?

I do closure under boolean operations with the MyHill-Nerode characterisation. Never saw it done that way. A right congruence $\sim$ saturates a language $L$ if
$$
 u \sim v \Rightarrow ( u \in L \leftrightarrow v \in L )
$$
or equivalently iff $L$ is an union of congruence classes. We use:

Theorem: (MyHill-Nerode) A language is regular if and only if there is a right-congruence of finite index that saturates $L$.

Now suppose we have regular languages $L_1, L_2 \subseteq X^{\ast}$, and denote $\sim_{L_1}, \sim_{L_2}$ some right congruences of finite index saturating them. Then
$$
 u \sim v :\Leftrightarrow u \sim_{L_1} v \land u \sim_{L_2} v
$$
is a right congruence (the intersection of both), and it refines both. Furthermore we have
$$
 [u]_{\sim} = [u]_{\sim_{L_1}} \cap [u]_{\sim_{L_2}}.
$$
Hence we have a finite number of equivalence classes. Also this gives that the intersection of equivalence classes $[u]_{\sim_{L_1}}$ and $[v]_{\sim_{L_2}}$ is either empty, or it has a common element $w$ and hence equals the equivalence class $[w]_{\sim}$. This gives that $L_1 \cap L_2$ is either empty or could be written as the union of equivalence class for $\sim$. By the above theorem $L_1 \cap L_2$ is regular.

For $L_1 \cup L_2$ it is an union of equivalence classes for $\sim_1$ and $\sim_2$, which are themselve unions of equivalence classes for $\sim$, hence it is also regular. And for complementation, this follows as the equivalence classes partition $X^{\ast}$, hence a right congruence working for $L_1$ works also for $X^{\ast} \setminus L_1$. $\square$

Additional comments: In your question you also mentioned the canonical Nerode right congruence
$$
 u \equiv_L v :\Leftrightarrow (\forall w \in X^{\ast} : uw \in L \leftrightarrow vw \in L)
$$
with $L \subseteq X^{\ast}$. This is the coarsest right-congruence saturating $L$. Now maybe it might be natural to ask if we can construct the Nerode right congruence of $L_1 \cap L_2$ or $L_1 \cup L_2$ easily out of the ones for $L_1, L_2$, or if the resulting intersection congruence arises as some Nerode right congruence. Maybe we can find such simple formulas like
$$
 u \equiv_{L_1\cap L_2} v \Leftrightarrow u \equiv_{L_1} v \land u \equiv_{L_2} v.
$$
But the above does not hold. And to my knowledge there does not exists any simple relation. For example consider $L_1 = (aa)^{\ast}$ and $L_2 = a(aa)^+$, then we have
$$
 L_1 \cap L_2 = \emptyset, \qquad
 L_1 \cup L_2 = X^{\ast} \setminus \{a\}.
$$
Now $\equiv_{L_1} \cap \equiv_{L_2}$ has at least four congruence classes, as it refines $\equiv_{L_2}$ which has exactly four congruence classes. But $\emptyset$ has precisely one class, and $X^{\ast} \setminus \{a\}$ has three (could all be easily seen by using minimal complete automata).

EDIT (2019.08.18).
The mirror and suffix operation are related to the left congruence
$$
 u \equiv^L v \Leftrightarrow \forall w \in X^* : wu \in L \leftrightarrow wv \in L.
$$
If $\equiv^L$ has finite index, similar as for the prefix-operation and the right-congruence, $\equiv^{\operatorname{suffix}(L)}$ has finite index. And
$u \equiv_L v$ iff $\operatorname{mirror}(u) \equiv^{\operatorname{mirror}(L)} \operatorname{mirror}(v)$; and as the mirror operation is a bijection on $X^*$ the last equation gives that $\equiv^{\operatorname{mirror}(L)}$ has finite index iff $\equiv_L$ has finite index (note that the left congruence has the same index as the right congruence for the mirrored words, but in general a right congruence for $\operatorname{mirror}(L)$ might have exponential many more classes as is shown by standard contructions from automata theory).

So these operations are handled if we can show that both congruences have finite index at the same time or not. For this lets look at the syntactic congruence
$$
 u \equiv_{S(L)} v \Leftrightarrow \forall x,y \in X^* : xuy \in L \Leftrightarrow xvy \in L.
$$
This congruence refines both congruences above, hence if it is finite, both congruence above are also finite. It is $u \equiv_{S(L)} v$ iff for all $w \in X^*$ we have $[wu]_{\equiv_L} = [wv]_{\equiv_L}$, hence we have a well-defined and injective map from the $\equiv_{S(L)}$-equivalence classes to the transformations on $\{ [w]_{\equiv_L} : w \in X^* \}$, and if the latter is a finite set, the set of those transformations is finite too, which implies that  $\equiv_{S(L)}$ is of finite index. So in total we have that $\equiv^L$ has finite index if $\equiv_L$ has finite index, the reverse is implied similar.


what is the difference between an adapter and a controller? 1- why do have a USB controller but a display adapter ?

2- I have heard the terms network adapter and network controller being used, is there a differance between those ?

The distinction between the two[adapter and controller] is mainly one of packaging. Controllers are chip sets in the device itself or on the system’s main printed circuit board (often called the motherboard). An adapter is a card that plugs into a slot on the motherboard.Regardless, the purpose of each is to transfer information back and forth between the I/O bus and an I/O device.

Ref: Computer Systems: A Programmer's Perspective, 3rd Edition.


Shortest walk that covers $k$ nodes I have the following problem, I would like to know an efficient algorithm to solve it.

Suppose I have a weighted graph $G$ and a set of vertices $K$, I want to find a walk which starts at a vertex $s$ and visits at least once every vertex of $K$ such that the distance is minimized.

There is no constraint on repeated nodes or edges in the walk found and is not guaranteed that the graph does not contain cycles. Some people have suggested me that it maybe NP-Hard due to a reduction from TSP, but there is no restriction of visit vertices exactly once, and is well known that TSP have that.

There is a simple reduction from Hamiltonian path. Suppose we are given a graph $G$ on $n$ vertices, and want to know whether it contains a Hamiltonian path. Adjoin a new vertex $s$ and connect it to all other vertices. The new graph $G'$ contains a walk of length (at most) $n$ starting at $s$ and covering all vertices if and only if the original graph $G$ contains a Hamiltonian path.


Does throughput includes CPU idle time also? I have 3 processes P1,P2,P3 having gantt chart as follows =>

Now, CPU remains idle in 0 - 2 sec and 44 - 47 seconds as I/O is taking place.

Does, this affect throughput as 3 processes can be completed in total 47 sec .

Hence, throughput = 3 / 47 .

Is this correct or am i missing something ?

You are correct!

According to the defenition Throughput (in case of scheduling in OS) is :

  Number of processes that can be completed in a unit of time.

The process can use both the CPU or the I/O operations. So the I/O time and idle times and CPU time are calculated in throughput.

Note: CPU idle time is not calculated when you want to have the Utilization of the CPU. So in your case CPU Utilization is 42/47.


What machine learning training algorithm to use for this kind of string dataset? I am working on a project where I have to train the following data-set using machine learning algorithm. One of my friend suggested decision tree, but I have never seen a situation where independent variable has more than 100 values in decision tree. I need help for choosing algorithm. Dataset is custom made and small. I am confused, since there are 100+ songs.

Dataset looks like this. Song is to be predicted. Every activity etc. comes from a predefined set of possibilities.

PS: It's not class assignment question. I made this database. I am also noob in ML.

You want to perform supervised learning, i.e., you have set of training examples (in this case, a set of 4-vectors with a label that corresponds to one of the 100 songs). So in particular, you want to do classification: given a 4-vector, predict a song. It might feel silly to call the songs a "category", but when you look past the naming in this particular case it should make sense: given an "activity vector", what is the song out of the 100 possible songs that will be chosen?

A fair starting point is scikit-learn's flowchart for choosing an estimator. Assuming the vector entries come from a predefined set of possibilities, you can simply map the strings to integers. For example, replace "walking" by 0, driving by "1", or replace "nothing" by 0, reading by "1", and so on. So for concreteness, your training data might be a file, where each line is something like "{0,1,0,8},47" meaning that activity 0, mob act 1, session 0, and mood 8 corresponds to song 47.

Now, assuming you have less than 100k samples, a good starting point is a linear support vector machine as per the flowchart. Depending on your results, the flowchart guides you towards other choices.


Can Homotopy Type Theory be used to derive more efficient algorithms on more efficient data representations from less efficient ones? I've read here that in HoTT, compilers could swap out less efficient representations of data for more efficient ones and I'm wondering whether my interpretation of that statement is correct.

Say we have two different ways of representing the natural numbers, unary (zero and successor) and binary. Here is a function that checks evenness on the former representation:

even : UnaryNat -> Bool
even zero = true
even (succ zero) = false
even (succ (succ n)) = even n

If we then have an isomorphism between the unary and binary representations, we trivially get an evenness function for the binary representation "for free", simply by converting a given binary natural number to a unary one, applying the even function, and converting the result back to the binary representation. Obviously, this is not very efficient, and we also don't need HoTT for this.

A better way to check whether a binary natural number is even would be to check if its least significant digit is a zero. My question is: Could we derive this more efficient algorithm for binary natural numbers from our definition of evenness for unary natural numbers using HoTT? If so, would this also be possible for other data types? I haven't studied any HoTT yet and since its appears to be a pretty complex subject I would like to find out whether it's as exciting as I think it is. Thanks!

You ask if we could derive a more efficent way to compute even? Yes, we could of course. The point however is that compilers could not.

Having a compiler automatically perform very fancy optimization techniques is a hard problem. In fact, if you ask for too much the problem may become undecidable, and for almost all interesting cases at least extremely hard. Even just asking whether two simple types are isomorphic quickly leads to open research questions.

What we have gained from HoTT is not a magic wand, but rather a formalism that provides a very good and structured way of thinking and reasoning about isomorphism, equivalence and equality in general. One can think easily enough about "small scale" notion of equivalence, for example when we focus just on one particular data structure, such as a dictionary, but it's a whole other matter to be able to talk about all notions of equivalence at the same time.

In your particular case it is easy to see what it would mean to have an equivalence between two implementations of natural numbers. But how about equivalence of large software components? Or equivalence of implementations of partial differential equation solvers? How do we even being to think about it? HoTT has an answer.


Which flow algorithm on a graph is used when the capacity is a rational number? Does ford fulkerson only use whole numbers? I tried to understand this but without success

Thank you

Since all steps of the algorithm merely involve addition, you can compute the least common multiple $m$ of the denominators of all weights involved, and creating $G'$ from $G$ by multiplying all weights by $m$.

Then all weights are integers and you can run Ford-Fulkerson. You can divide the results from it by $m$ again to get back your rationals.


Why is the blank symbol not considered part of the input alphabet of a Turing machine? Definitions of Turing machines are always explicit about the blank symbol not being part of the input alphabet.

I wonder what goes wrong when you would make it part of the input alphabet, because effectively the blank symbol already seems to be part of the input.

To explain that 'seems' in the last sentence, consider the following.

In the default setup, an infinite number of blank symbols appear on the right of the input. When the tape head moves over the first blank symbol, computation can just continue, as it doesn't need to be an accept or reject state.

Now suppose the computation would subsequently write symbols from the input alphabet to the right of that first blank symbol, then return to the leftmost position while also returning to the start state. It would then 'start over' with a different tape. Effectively, it now starts with a different input, where there are input symbols to the right of the blank that weren't there before. The input seems to effectively include the blank symbol. The further behavior of the machine could now also be different: after encountering the blank again, it will now encounter different symbols to the right.

Supposing this scenario is indeed possible, why wouldn't you consider the blank symbol part of the input alphabet and why wouldn't you allow including it as part of the 'initial' input?

Perhaps it is just a way to define the input such that it isn't always infinite?

The main reason is that it allows the machine to detect the end of its input: it's (the character before) the first blank. If you allowed blanks in the input, the machine could never know whether it might find more input by scanning farther to the right. Of course, you could solve that by having a special "end of input" character but then you have to insist that that can't appear in the input, so you've just shifted the problem one level deeper.

It also makes the initial conditions much easier to specify: the input is the non-blank section of the initial tape, which must be finite and contiguous. And if you want a blank character to be a part of the input alphabet, you can always add an extra character (call it "space" or something) and have the machine behave however you want when it sees it.


Simulating a combinatorial network I have various Boolean functions in the sum of products format. I "convert" these via combinatorial logic synthesis into a combinatorial network as an And-Inverter Graph - therefore this network only consists of 2-input, 1-output And-Gates and inverters. Every sum of products function is therefore "responsible" for a certain single output. The network is a multi-input and multi-output network, in- and outputs are Boolean (0 or 1). This network is also parsed as file, so it can be read from.

I know, that such a network can be proven to be correct, but I want to simulate this combinatorial network with certain inputs. My problem is, that I only find ways to simulate a sequential network - nothing for combinatorial networks. SAT-provers might be helpful, but because of the nature of this network and its functions, I already know the functions are satisfiable. I need to know, what output will be generated using certain inputs.

Is there any way to simulate and test a combinatorial network with certain inputs and save the outputs? I know there a SAT-provers out there, but I don't think I can really use those, as I need specific outputs and the Inputs have to be in a specific order. Logic Simulation might be the way to go, as the network is derived from Boolean functions, but I didn't find a way to simulate this network via anything.

Short Example: Network is some sort of adder, 4 inputs, 5 outputs. I then go through the inputs (0000, 0001, 0010, ...) and save the outputs of the network. I can't compare the outputs to a tables of "expected" outputs, because I don't know what the outputs will be (I only know them for certain test cases - the network probably won't be as easy as an adder).

Is there any way to simulate a network like this?

Yes.  Simulation is straightforward and doesn't require any special ideas: it can be done directly, by just executing the circuit one gate at a time.

The algorithm to simulate a combinational circuit is completely straightforward.  Given a combinational circuit $C$ and an input $x$, it is easy to compute the output $y=C(x)$, simply by simulating each gate, one gate at a time.  Each gate in the combinational circuit is either an AND gate or an inverter.  Both can be implemented in software.  So, to simulate such a circuit, you just iterate through the gates in topologically sorted order, compute the effect of each gate, and store the value of its output wire.  This is a trivial, linear-time algorithm.  There's no need for SAT solvers or anything fancy like that.

Of course, when you compute the output of the circuit on some input, it's straightforward to save the output anywhere you like.  If you only want to test the circuit on certain inputs, just do that.  If you want to compare the output of the circuit to the known-correct output, you can do that: it's just an equality test.

Alternatively: A combinational circuit is a special case of a sequential circuit.  A sequential circuit is allowed to have both combinational logic and memory (e.g., registers).  A combinational circuit is the special case where you have no memory (e.g., no registers).  So, in principle any method for sequential circuit simulation already provides you a way to simulate combinational circuits.


Finding context free grammar for this language? I needed help finding the context free grammar of this string

$$
10^{n}10^{n}1
$$

So far an idea I have is
$$
S\rightarrow 1S1S1\mid 0S \mid \varepsilon
$$

Any assistance you can provide would be greatly appreciated!

When looking for CFGs for an expression like yours, it is often handy to work from the inside out, especially whan you need to match symbols. Think of your expression as $1(0^n10^n)1$. The interior part, within the parentheses, consists of a $1$ surrounded by an equal number of zeros on each side. We could generate this by the production $T\rightarrow 0T0$, since repeated use of this production would result in derivations like
$$
T\Rightarrow 0T0\Rightarrow 00T00\Rightarrow 000T000
$$
and so on. In other words, we could have $T\stackrel{*}{\Rightarrow} 0^nT0^n$, where the star over the arrow means "eventually results in". Now all you have to do is get the $1$ in the middle. That's easy: just add the production $T\rightarrow 1$. In sum, you can get the part in parentheses by the productions
$$
T\rightarrow 0T0\mid 1
$$
Now that you have the middle part, just add the external $1$s to a start variable production $S\rightarrow 1T1$, giving the full grammar
$$\begin{align}
S&\rightarrow 1T1\\
T&\rightarrow 0T0\mid 1
\end{align}$$

Your attempt was a good start, since you did generate the correct number of $1$s, but there was no guarantee that the two $S$ variables in $S\rightarrow1S1S1$ would generate the matching $0$s you need.


How is (0|1|...|n) handled as a DFA? How is n-times regex alternation operation, e.g. (0|1|...|n), handled in a DFA (MYT algorithm)?

Here are the rules for the MYT also (Converting Regular Expressions to NFAs
):
https://swtch.com/~rsc/regexp/regexp1.html

The article shows how to get a FA for the regexp 0 + 1: make a FA, $M_0$, for 0, make a FA, $M_1$, for 1, make a new start state state, $q_0$, and link it to the original start states of $M_0$ and $M_1$ with $\epsilon$-moves.

Then recognize that the regexp 0 + 1 + 2 is (0 + 1) + 2, so do the construction again, using the FA for 0 + 1 and the FA for 2. Rinse and repeat.


Automated lip-reading: inferring what someone is saying, based upon video of them speaking Some humans can lip-read fairly well: by watching someone who is speaking, they can tell what the speaker is saying (even without hearing the speech).

Has there been any work on building computer software to lip-read?  In other words, given a video of someone speaking, is it possible to build software to infer what the person is saying (with access only to the video stream, without audio)?  Has there been any research on this problem, or even deployed systems?

Background and motivation: In the US, certain laws may forbid recording audio without consent.  However, there is generally no prohibition on recording video without consent of the people being recorded.  (That's why you see surveillance cameras all over the place, and why they record only video but never audio.)  I am curious whether technology has advanced enough that, solely from video, it might be possible for automated methods to tell what people are saying -- or whether that might become feasible in the near-future.  And, apart from the privacy implications, such a technology might be pretty useful.

There appears to be some work in that area. See for example this paper and the references therein. There are also demonstrations of implemented systems on youtube, see for example this video


Find the duplicates in a list of floating point numbers I receive a list of real numbers ( float ) between $0$ and $1$.  The list has length $N+1$ and I need to find two numbers on the list which are $\le \frac{1}{N}$ apart.  Here is an example test case:

[ 0.        ,  0.31662479,  0.63324958,  0.94987437,  0.26649916,
  0.58312395,  0.89974874,  0.21637353,  0.53299832,  0.84962311,
  0.1662479 ,  0.48287269,  0.79949748,  0.11612227,  0.43274706,
  0.74937186,  0.06599665]

One possibility I came up with is to multiply by $N=17$ and to take the integer part:

[ 0,  5, 10, 16,  4,  9, 15,  3,  9, 14,  2,  8, 13,  1,  7, 12,  1]

Then I have to find the location of two numbers in this list which are identical.

I would appreciate any solution to this problem with or without the intermediate multiplication step.  Or does this problem have a particular name in the field of algorithms?

Sorting

The simplest algorithm is to sort your floats, then compare adjacent entries.  This will let you find all pairs that are $\le \frac1N$ apart in $O(N \lg N)$ time.

Hashing

It's also possible to come up with a linear-time algorithm, i.e., to check whether there is any nearby pair of floats and if so find at least, in $O(N)$ time.

Let $M=\lfloor N/2 \rfloor$.  Build a list of integers by replacing each float $x$ with $\lfloor Mx \rfloor$, then find all duplicates in the resulting list of integers.  Finding duplicates in a list of integers can be done in expected linear time by hashing and looking for a pair with the same hash.  For each duplicate integer, check whether it corresponds to a pair of floats that differ by $\le \frac1N$.

Then, do it again: build a second list of integers by replacing each float $x$ with $\lfloor Mx + 0.5 \rfloor$, then find all duplicates in this list and check each to see whether it corresponds to a pair of floats that differ by $\le \frac1N$.

It's possible to show that if there exists a pair of floats that differ by $\le \frac1N$, then this procedure will find at least one such pair; and if there aren't any such pair, then this procedure will discover that fact.  Moreover, with suitable choice of the hash function, this can be made to run in expected linear time.  In fact, if you replace the hashing with counting sort, this runs in deterministic linear time.

In practice

In practice, my advice is to simply sort and then compare adjacent entries.  It will be easier to implement, less fiddly (you don't have to deal with corner cases), obviously correct, and probably more than fast enough in practice.


In the Traveling Salesperson Problem, is the shortest tour the same regardless of the start/return city? How do you prove it? This is the form of the problem where you start at a city, visit every other city, and return to the start city. Since you "return" to every city in the completed cycle, it seems intuitive that the cycle would be the same regardless of the starting city.

The optimal tour visits all vertices so it's still a tour regardless of where you start. The length of the tour is the sum of the lengths of its edges. Addition is commutative and associative so it doesn't matter what order you do the addition.


Running Time Analysis of a Simple Binary Search Algorithm I'm stuck with the following problem by Skiena (The Algorithm Design Manual, p. 106):

  Problem: Give an efficient algorithm to determine whether two sets (of
  size $m$ and $n$, respectively) are disjoint. Analyze the worst-case
  complexity in terms of $m$ and $n$, considering the case where $m$ is
  substantially smaller than $n$.

  Solution: First sort the big set – The big set can be sorted in
  $O(n\log n)$ time. We can now do a binary search with each of the m
  elements in the second, looking to see if it exists in the big set.
  The total time will be $O((n + m)\log n)$.

My question: Why is the running time $O((n + m)\log n)$? I would have to perform m binary searches in total (one binary search for every element in $m$) - as one binary search has a running time of $O(\log n)$, I would have to perform $m \cdot \log n$ operations in the worst case. How does this - if at all - translate into $O((n + m)\log n)$?

Sorting the big set takes time $O(n\log n)$. You perform $m$ binary searches, each taking $O(\log n)$, for a total of $O(m\log n)$ time spent on binary search. The total running time of the algorithm is thus
$$
O(n\log n + m\log n) = O((n + m)\log n) = O(n\log n),
$$
assuming $m \leq n$.

Note that it is even better to sort the smaller list, since then the running time improves to $O(n\log m)$.


concurrency and hardware I've a couple of questions that I need answers for. What I am looking for here is the outline of the answers. Not necessarily the exact complete answer. I can do that.
The question is that common operating systems provide support for concurrency through processes and threads.

There are differences between processes and threads and that well documented and easily understood. The issue here is What support does the hardware need to provide for processes and threads?
The initial guess that came to my mind was that it is related to process communication and synchronization. However, these concepts are parts from another question which gets me to think that they are not the right answer. I am aware of the hyper-threading which is a hardware approach for concurrency. Is it ?!

The other question is that Operating systems and programming languages offer various means for communication and synchronization between processes and threads. What are the most
common ones? What support does the hardware need to provide and, in particular, what instructions does a processor need to offer for communication and synchronization?

I know it is a long question but again, I don't seem to figure out the outline for the specific hardware support for (concurrent process and threads, as well as communication and synchronization).

Your help is highly appropriated

Preemptive multithreading is usually implemented by the operating system using timer interrupts.  Everything else can be done in software.  Even the timer interrupts aren't strictly necessary: in cooperative multithreading (what they had in Windows 3.1 and earlier and MacOS prior to MacOS X) the operating system would perform the thread switch whenever a thread did a system call (e.g. a file read or write.)

A process has an address space with one or more threads running in it.  Address spaces typically require hardware support for page tables.

There is no hardware support required for synchronization or communication.  Multiple threads in the same process communicate through the address space they share.  Threads within the same process typically synchronize using mutexes and condition variables.  Mutexes and condition variables can be implemented with load and store instructions.  (For the most part.  There are some processors that don't have sequentially consistent memory hardware, and for those the processor also needs to implement some kind of memory barrier instructions.)  When a thread needs to wait for a long time it will put itself to sleep by calling into the operating system.

Threads in different processes typically communicate through one of the abstractions implemented by the operating system (pipes, files, sockets).


Quantum lambda calculus Classically, there are 3 popular ways to think about computation: Turing machine, circuits, and lambda-calculus (I use this as a catch all for most functional views). All 3 have been fruitful ways to think about different types of problems, and different fields use different formulation for this reason.
When I work with quantum computing, however, I only ever think about the circuit model. Originally, QC was defined in terms of quantum Turing machines but as far as I understand, this definition (although equivalent to quantum circuits if both are formulated carefully) has not been nearly as fruitful. The 3rd formulation (in terms of lambda-calculus or similar functional settings) I am completely unfamiliar with. Hence my questions:

What are useful definitions of quantum lambda-calculus (or other functional paradigms)?

What subfields of QIP gain deeper insight from using this formulation instead of the circuit model?

Notes
I am aware that I am ignoring many other popular formalisms like cellular automata, RAM-models, etc. I exclude these mostly because I don't have experience with thinking in terms of these models classically, let alone quantumly.
I am also aware that there are popular alternatives in the quantum setting, such as measurement-based, topological, and adiabatic. I do not discuss them because I am not familiar with the classical counterparts.

here is a half-baked answer:
I know that Ugo Dal Lago at University of Bologna has been studying quantum lambda calculus. You may want to check his publications and perhaps this one in particular:

Quantum implicit computational complexity by U. Dal Lago, A. Masini, M. Zorzi.

I am saying it's a half-baked answer, because I haven't had chance to read any of his works.


How to get the shortest simple path in a directed Graph with an additional constraint that it needs to use two arcs in the said path I have a directed graph that has positive weights (but there are reverse arcs) and I am trying to find the shortest path between a given source, s and a given sink, t but the path should also contain two given arcs in a sequence. Say we are given arcs a1, a2, we want to find a simple shortest path that goes from s to tail of a1 and from head of a1 to tail of a2 and then from head of a2 to the sink t. I was wondering if there is any elegant algorithm or even a mixed integer programming approach to solve this problem.

I am currently planning to modify Dijkstras algorithm to forbid certain nodes that have been previously added to the path.

Edit: I want the whole path from $s$ to $t$ to be simple.

Let arc $a1$ be $(u_1, v_1)$ and $a2$ be $(u_2, v_2)$. As you mentioned in your question, you want to find a simple shortest path that:

Goes from source $s$ to $u_1$
From $v_1$ to $u_2$
From $v_2$ to the sink $t$.

As you DAG has only positive weights, I think you should find the shortest paths for all three cases (using Dijkstra or any other algorithm) and join them together to get the shortest path from $s$ to $t$ satisfying the given constraints.

EDIT: As the question is for Simple Path, I will refer you to this: http://math.mit.edu/~goemans/18438S12/lec22.pdf.

I am quoting a few important points here:

  We first note that the arc-disjoint path problem, and the vertex-disjoint path problem in a directed graph are equivalent - i.e. we can give a polynomial-time reduction in either direction.
  Undirected Edge Disjoint Paths. In the case of fixed k (i.e. there are k source-sink pairs), there is a polynomial-time algorithm to decide if there are edge-disjoint paths connecting each $s_i$,$t_i$ pair. This result follows from the Graph Minor Project of Robertson and Seymour (1995), and is very involved.
  Yet for super-constant k, the undirected edge-disjoint paths problem is NP-complete. 22-1
  Directed Arc Disjoint Paths. Even for $k = 2$ it is NP-complete to determine if there are arc-disjoint paths P1, P2 connecting s1, t1 and s2, t2. In fact, we can even choose s1 = t2 and s2 = t1 and this problem still remains NP-complete.


Hash function - uniformity / strong universality I am currently learning how randomised Hashing works.
So, you have a class (aka family) $H$ of hash functions, each of which maps the universe $U$ to the hash table $N$.

That class is called "strongly universal" or "pairwise independent" if $\forall x,y \in U, x \neq y: \forall z_1,z_2 \in N: \Pr\limits_{h \in H}[h(x) = z_1 \land h(y) = z_2] \leq \frac{1}{|N|^2}$. In words: pick any two elements from the universe and two from the hash table. If you pick a hash function from the hash class at random, the probability that these two elements are mapped to each other by $h$ is less or equal than $\frac{1}{|N|^2}$.

Now, what is confusing me is that, since $x$, $y$, $z_1$ and $z_2$ are all completely independent, it looks to me like you could just "remove" one pair from the equation and still get the same result. That would be $\forall x \in U: \forall z \in N: \Pr\limits_{h \in H}[h(x) = z] \leq \frac{1}{|N|}$. This, however, is called "uniformity" of a hash class.

Could someone explain to me why these two attributes are different from one anoter?

Arnab provided the answer. The family $\mathcal{H} = \{h_i : i \in N\}$, where $h_i(x) = i$ for all $x \in U$, is uniform but not pairwise independent. Similarly you can come up with families which are pairwise but not $3$-wise independent, and so on.

To give a simple example, let $X,Y$ be two independent uniformly random coin tosses. Each of the possibilities $(H,H),(H,T),(T,H),(T,H)$ has the same probability. Now let $X'$ be a uniformly random coin toss, and let $Y' = X'$. Now it is not true that each of the four possibilities of $(X',Y')$ has the same probability, but each of $X',Y'$ by itself is a uniformly random coin toss.


Expected value of the distance between nodes in a binary tree If there are 16 leaves in a full binary tree and two nodes $a$ and $b$ chosen at random, then what is the expected value of the distance between $a$ and $b$ in T?

My question here is, how do I correctly approach this question?

(Also tell me how to develop numerical skill in algorithm?)

Let's name the nodes $\mathit{node0}$ through $\mathit{node15}$. (with the implication that that's the order of the nodes)

I would approach this problem first by saying "if $a$ is $\mathit{node0}$, then what's the expected value of the distance between $a$ and $b$?" Then I'd ask the question "what if $a$ is $\mathit{node1}$?", etc. Presumably along the way there would be patterns and symmetries I could make use of so I wouldn't need to do a long calculation 16 times.

So let's take that first question: "if $a$ is $\mathit{node0}$, then what's the expected value of the distance between $a$ and $b$?"

First off, the distance between $\mathit{node0}$ and $\mathit{node0}$ is $0$.
To $\mathit{node1}$, the distance is $2$.
To nodes $\mathit{node2}$ or $\mathit{node3}$, the distance is $4$. To the four nodes $\mathit{node4}$ through $\mathit{node7}$, the distance is $6$. To the remaining eight nodes the distance is $8$.

So the expected distance when $a$ is $\mathit{node0}$ is $(0 + 2 + 2*4 + 4*6 + 8*8)/16 = 6.125$.

Now figure out the expected distance when $a$ is $\mathit{node1}$, and then other nodes. (there is an obvious pattern - prove it)

Then average over those results to find the answer.

Often, you will find a shorter or more elegant solution to a problem as you are working on it. This is normal, and should not be taken as a sign that your initial approach was wrong or that you should have seen the more elegant approach without trying your initial approach first, any more than a writer should expect to write an essay without first writing some notes or a rough draft.

Unfortunately, though writers are often trained in the idea of rough drafts and revisions, solutions to math or computer science problems are usually only presented in their final form without much indication of the bumbling around and blind corners that really went into discovering the elegant explanation.


Can pseudo random number generator generate all possible sequences? Suppose I have a random number generator G that takes in a seed s from the set of integers. Suppose we have a sequence of numbers Q where |Q| = k. Does there exist a seed s such that G(s) produces the sequence Q, for any Q with any length? This is an existence question; does it exist or not, the process of finding a random number generator is irrelevant. The code for G is finite as is the seed s.

My intuition is that no, moreover, it's impossible to construct such a G with these properties. Unfortunately I can't justify my intuition.

If you are considering a pseudorandom generator that can work with seeds of any length, then the answer is "It depends". It depends on the pseudorandom generator. There are pseudorandom generators for which the answer is yes (e.g., $G(x)=x$, or any bijective $G$), and pseudorandom generators for which the answer is no (e.g., $G(x) = G'(\text{SHA256}(x))$, where $G'$ is a pseudorandom generator that accepts fixed-length seeds, is almost certainly such an example).

In practice, pseudorandom generators usually have a fixed-length seed.  In that case, if the length of the output is longer than the length of the seed, then there exists an output that isn't produced by any seed (of that length).  This follows from the pigeonhole principle.

In practice this almost certainly doesn't matter.  Usually what matters is whether the output of the pseudorandom generator passes statistical tests, or whether it is indistinguishable from true-random bits.


Can the solution to a POMDP be found using linear programming? It is known that Markov decision processes (MDPs) can be solved using linear programming (see page 24 of Carlos Guestrin's PhD dissertation). The linear program is:

$$min_{V(x)} \sum_x \alpha(x)V(x)\\
\text{subject to: } V(x) \ge R(x,a) + \gamma\sum_{x'}P(x'|x,a)V(x')\text{ for all }x\in X, a\in A$$

where $V(x)$ is the value of starting at state $x$ (note that $V(x)$ is the decision variable), parameters $\alpha(x)>0$ for all $x$ which are termed state relevance weights and are typically normalized, that is $\sum_x\alpha(x)=1$ (the solution of the above LP is actually, surprisingly, independent of the exact choice of $\alpha$), $R(x,a)$ is the reward obtained in state $x$ when action $a$ is taken, and $P(x'|x,a)$ is the probability that transition to state $x'$ when we take action $a$ in state $x$.

Question: does anyone know of a similar linear programming formulation for solving partially observable Markov decision processes (POMDPs)?

What is known about the complexity of finding optimal policies for POMDPs indicates that solution by Linear Programming is not possible in the general case.
When the decision horizon is bounded (finite), finding optimal POMDP policies is PSPACE-hard (Papadimitriou and Tsitsiklis, 1987).
When the decision horizon is infinite and we are using e.g. the geometrically discounted rewards, finding optimal POMDP policies is unsolvable (Madani, Hanks, Condon 1999).
Linear Programming is solvable in polynomial time, and (efficient) reductions from the above PSPACE-hard and unsolvable problems to Linear Programming therefore are not believed to exist and do not exist, respectively.
Solution of POMDPs in sufficiently simple special cases is possible with LP, of course (like MDPs, which are fully observable POMDPs).


Translation of diagnosis problem to SAT I have the following diagnosis problem:
h(A): z1 = not(in1)
h(D): z2 = not(in2)
h(B): z3 = z1 or z2
h(C): out1 = not(z3)
h(E): out2 = not(z3)

This is an image of the system:

I have an observation where I know that:
in1 = false
in2 = false
out1 = true
out2 = true

I want to check if {B} is a diagnosis of the system, meaning that I assume that A,D,C,E are valid, while I don't assume the same about B.
This I want to turn into a sat problem. So first I map each variable in my system to a literal:
in1: 1
in2: 2
z1 (the output of A): 3
z2 (the output of D): 4
z3 (the output of B): 5
out1: 6
out2: 7

So to check if {B} is a diagnosis of the system (meaning that if I remove the assumption about {B} the system will be OK) I create a CNF like so:

not(1) AND not(2) AND 6 AND 7 - this represents my observations, the variables whose value I know for sure.

Now I want to add a representation for my constraints. For example, I know that 6 = not(5), but I don't know the value of 5 (because I can't assume the validity of component B).
My question is how do I add this knowledge to my CNF representation? If I add "not(5)" to my CNF then I assume the output of B is always false, and this isn't correct.

Thank you very much.

In order to express $x = \lnot y$ in CNF form, you add the clauses
$$
x \lor y, \lnot x \lor \lnot y.
$$
In order to express $x = y \lor z$ in CNF form, you add the clauses
$$
\lnot y \lor x, \lnot z \lor x, \lnot x \lor y \lor z.
$$
In order to express $x = y \land z$ in CNF form, you add the clauses
$$
\lnot x \lor y, \lnot x \lor z, \lnot y \lor \lnot z \lor x.
$$


Solving the Knapsack problem in $O(v^*n^2)$, where $v^*$ is the maximum value of all $n$ items For my study I am supposed to develop an dynamic programming algorithm which solves the following simplification of the Knapsack problem in $O(v^*n^2)$ time ($v^*$ is the maximum value of all elements):

Let there be given $n$ elements $1,...,n$, a maximum weight $W$ as well as a weight & value function:
$w: \{1,...,n\}\to \mathbb{N}$
$v: \{1,...,n\}\to \mathbb{N}$
We then define $v^* = \max(v(1),...,v(n))$

The goal is to find a subset $M\subseteq \{1,...,n\}$ so that $\sum_{x\in M} w(x)\le W$ and so that $\sum_{x\in M} v(x)$ is maximal.
(I.e. we want to pack the subset of items that have the highest summed up value while not using up more weight than $W$)

I've been trying for quite some time, but I can't seem to come up with any idea or reduction rule that makes use of $v^*$.

Since this is a homework assignment, I'm looking for hints, not answers.

To be precise: The regular dynamic programming algorithm that solves the regular Knapsack problem can be used on this simplification as well (it might even be that the version given here is the standard version. The sources I've looked through so far don't say whether $w,v$ map to $\mathbb{R}$ or $\mathbb{N}$),
and find the optimal solution in $O(n\cdot W)$ time (see e.g. Wikipedia).

The algorithm variant I'm looking for however is independent of $W$, and instead uses the maximum value $v^*$ of any of the items.

So, after eventually giving up on developing a different algorithm I looked back at the original solution, i.e. the one you can find e.g. on Wikipedia under 0/1 Knapsack problem.

The idea is to look closely at which fields of the table the algorithm builds are actually necessary, and which are not.


Understanding a few intricacies related to two naive algorithms to compute the convex hull of a set of points I already understood how the well-known algorithms like Graham's scan, Quickhull, etc. work, but I have difficulties in understanding 2 naive algorithms to compute the convex hull:

  Let $S= \{p_1, \dots , p_n \}$ a set of points and $CH(S)$ the convex hull of $S$.

The first problem and corresponding algorithm are as follows.

  Find the smallest subset $R \subset S$ for $CH(R) = CH(S)$. Since there are $2^n$ subsets, the complexity is $\mathcal{O}(2^n)$.

Pseudocode version:

foreach (s in S.subsets)
    if (CH(R) == CH(S))
        return R

Since we don't know $CH(S)$, and indeed it's our goal to compute $CH(S)$, how can we check if $CH(R) = CH(S)$?

The second problem is as follows.

  Let $p,q,r,s \in S$. $s \in CH(S)$, if $s \not\in triangle(p,q,r)$

And here is the algorithm:

Shouldn't the first part of the sentence (of the problem) be

  Let $p,q,r \in CH(S)$ and $s \in S$.

?

However, even in this case, we don't know what $CH(S)$ is.

My counterexample why this algorithm wouldn't work:

At the start, we check the $triangle(1, 2, 3)$, and see that $4$ is not in the triangle, and mark $4$ as not an element of the convex hull, but $4$ should be part of the CH!

A1) You're right, the algorithm description sounds kind of weird. A naive algorithm that takes exponential time would rather be something like

foreach (R in S.subsets)
  if (R.isConvexHull(S))
    return R

However, the method for checking whether R is a convex hull needs $n$ time, so we obtain a runtime of $n2^n$.

A2)
Your premise is missing some quantifiers. I think, what you wanted to say is

"$\forall s, $ if $\forall p,q,r \in S, s \not \in \triangle(p,q,r),$ then $s$ is on the convex hull."

Furthermore, go through your example again. You understood it wrong. If you check triangle (1,2,3), you see that 4 is not in the triangle. Hence, 4 might still be on the convex hull (but it doesn't have to). On the contrary, if you check the triangle (4,3,2), you see that 1 is on the interior. Therefore, 1 is definitely not on the convex hull.

This still does not give you a convex hull algorithm though, since the points still have to be sorted by the end. However, this is no problem, since the rest of the algorithm already needs $\mathcal{O}(n^4)$ time.


Which is the fastest method for calculating exact square root of a integer of 200-500 digit number? I wanted to know is there any algorithm / function / process through which I can calculate square root of a very large integer number. I wants to know current state of the research in this field.

No approximate methods please.

It seems a bit surprising that you did not find the Wikipedia article on integer square root where the Newton's algorithm is described in detail.

Here is the implementation in Python:

def integer_sqrt(n):
    """Compute the integer square root of n, or None if n is not a perfect square."""
    x = n // 2
    while True:
        y = (x + n // x) // 2
        if abs(x - y) < 2: break
        x = y
    return (x if x * x == n else None)

This takes about 0.018 seconds for a 1000 digit number on my MacBook Air. It's not clear why you're asking for the particular range between 200 and 500 digits, but I think you should be able to go on from here, especially if you take the time to read the Wikipedia page.

You may also be interested in the Rosetta Code integer roots page, where you can find fast implementations of integer root algorithms in many languages.

By the way, I just googled "integer square root" to find all of this, except I wrote the Python code.


what are the key advantages of pipelining I was trying to look my book computer architecture and design, but I can not find the answer for this question.
what are-the key-advantages of pipelining?

I Googled your question and found this (and this):

  Consider the modern way of making cars - on an assembly line. Here, there is an orderly flow of parts down a conveyor belt, and the parts are processed by different stations (also called segments of the assembly line). Each segment does one thing, over and over. The segments are coordinated to exploit the sequentiality inherent in the automobile assembly process. The work gets done more smoothly (because of the orderly flow of input parts and output results), more efficiently (because each assembler at each segment of the pipeline does his or her task at what one hopes is maximum efficiency), and more reliably because there is greater consistency in one task being done repetitively (provided the assembly line is designed correctly).

To put it in a simple way: Suppose you build a car in 10 steps $(s_1, s_2, \dots, s_{10})$. Suppose also that a single person can complete these 10 steps in 2 hours and a single step in 12 minutes. Let's also say that you have only 1 workplace for each step, so 2 people can't be working on the same step for 2 different cars. You'd have two ways to produce cars:

Put a single person that builds a car every 2 hours and uses all 10 workplaces.
Put a person per workplace (10 people in total) where each person completes a single step in 12 minutes and have a car every 12 minutes. The exception in this case is the first car which would take 2 hours to be completed, but from the second car and forward you'd have a car every 12 minutes.

The second way is the equivalent of pipelining.


Group time series events into minimal amount of buckets I'm trying to efficiently compute events in a time series by grouping them into buckets. My goal is to have as few buckets as possible. The constraint is that events within one bucket are all within a 30 minute time window.
To get more concrete, let's assume I've got these events:

time
event

15:15
1

16:58
2

17:13
3

17:21
4

A naive approach to group those events into 30 minute intervals would result in these 3 buckets
bucket 1: 15:00-15:30 – event 1
bucket 2: 16:30-17:00 – event 2
bucket 3: 17:00-17:30 – event 3,4

A better solution with fewer buckets is possible though:
bucket 1: 15:00-15:30 – event 1
bucket 2: 16:58-17:28 – event 2,3,4

What kind of algorithm do I need to look for to efficiently find the fewest amount of buckets for this kind of data?
I'd prefer a fast solution (i.e less than $O(n^2)$) over an optimal one.

The first event at time $t_0$ needs to be in a bucket. We can safely choose the bucket $[t_0, t_0+30]$, as there is nothing to gain by making it start earlier. We then move on to the next event starting at $t>t_0+30$ (earlier events fall into the bucket we chose). We once again choose the latest bucket containing that event. It is not hard to prove that repeating this strategy until all events are covered is optimal (you can do it by induction).
This procedure runs in $O(n)$ time if your events are sorted, $O(n\log(n))$ if you need to sort them first.


Is it possible to define branches which, once taken once, will become the default forever? Assuming I have a very simple branching:

switch on var:
  1 => branch1
  2 => branch2
  default => branch3

And I wish to implement a program that will forever take "branch2" when entering this sequence of instructions once branch2 is taken.

This is quite easy to do by adding an additional variable and setting it when branch2 is entered, however, this will keep the overhead of having to execute the control statement, I'm wondering if there is a way to remove that overhead or diminish it.

I'd be interested in knowing if:

a) This sort of optimization exists in theory ?

b) This sort of optimization is implemented languages which run in controlled environments (e.g. can use jitc) ?

c) This sort of optimization is implemented in statically compiled languages which don't need a VM/RE/etc ? (e.g. C, C++, Rust, D, Go) ?\

Edit:

Just to clarify, what I'm asking is if its possible that, once branch-x is taken once, for the instructions executed by the cpu to become:

//Code
//Instructions of branch x
//Code

rather than what we had before which was:

//Code
//Control Statement
//Code

That is in order to "skip" the overhead of having to select branch x to being with, not to optimize how that selection is done.

Update

Based on your comment,

  I'm not concerned so much about switch statement being inefficient as I am by the fact that the switch statement exists at all.

, I think that I understand the question better now.  And the answer is that you want currying to be applied on the first execution.

As a quick explanation of currying, consider a mathematical function
$$f\left(x,y,z\right)=x+y+z,$$
but you know that $x=y=z=1$, such that this could be reduced down to
$$f\left(\right)=3.$$
You want this, except in your case you want to reduce a switch function down to a single one of its branches.

This is entirely possible - you basically just need to recompile the code for that function.  Or, if you're working in an interpreted language (e.g., JavaScript), you can simply define the switch function as its branch to replace it.

In practice, you won't need to worry about it too much in typical cases because:

Most switch statements aren't executed enough to be computationally significant.
When switch statements are executed enough to be computationally significant, but continue to resolve to the same branch each time (as you're asking about), the CPU will tend to use branch prediction to optimize it away automatically.

Example:  StackOverflow: "Why is it faster to process a sorted array than an unsorted array?" is about a dramatic example of branch prediction at work.  The tl;dr there is that sorting a list caused branches to tend to evaluate the same way over time (as you're interested in), resulting in a dramatic speedup.

Still, if the switch statement's proving to be a major bottleneck or you just want to do this anyway for fun (which is a very under-valued rationale - where would we be today if people just didn't do stuff for the heck of it?!), then you have a few options:

Split up the method that calls the switch statement into several variants, each of which does a different branch.

Perform this split just high enough to be outside of the critical section.
In effect, this will be like having pre-compiled (and optimized!) versions of the code for each of the possibilities.
For a jargon description, you'd be hoisting the switch nodal point outside of the performance-critical code region.

Actually curry-and-recompile the method at runtime.

Depending on your platform, this can have some technical barriers.
When you recompile, you have to figure out what part of the program to recompile.  If you do the entire thing, then it could take a while, etc..  But if you do only the switch statement, then optimizations around that area in the code will become prohibited, plus your program will need an extra function-call step to call the switch statement and its ultimate reduction.
As with Option (1), the optimal choice here is probably to recompile the critical section, as opposed to just the switch statement or the entire program.

Specific answers

  a) This sort of optimization exists in theory ?

Sure, you're talking about splaying, such as implemented in a splay tree.

Obviously you can't implement this sort of optimization in rigid control structures like a switch statement in C/C++, so it'll take making your own implementation of something like a a splay tree that has methods as terminal nodes.

According to your description, you may want the reorganization process to stop after order's been changed once.  If so, that's a modification you can add into the splay tree's logic.  You can even instruct it to recompile itself in a more rigid, switch-like structure once the structure's determined and the splay logic's no longer needed.

  b) This sort of optimization is implemented languages which run in controlled environments (e.g. can use jitc) ?

Perhaps in some.  It's an implementation detail, so it may be implemented in some implementations but not others.

  c) This sort of optimization is implemented in statically compiled languages which don't need a VM/RE/etc ? (e.g. C, C++, Rust, D, Go) ?

Yeah, definitely!  You need to statically compile the methods, but you can have a splay tree that resolves method pointers, then run those.

Comments

Just in case there was any confusion, switch statements don't normally need to check cases one-by-one.

For example, consider:

switch (x)
{
    case 0:    foo_0();    break;
    case 1:    foo_1();    break;
    case 2:    foo_2();    break;
    case 3:    foo_3();    break;
}

I'd expect a good compiler to implement this more like:

function[] switchBranches = { foo_0, foo_1, foo_2, foo_3 };
var selectedBranch = switchBranches[x];
selectedBranch();

than as:

if      (x == 0) { foo_0(); }
else if (x == 1) { foo_1(); }
else if (x == 2) { foo_2(); }
else if (x == 3) { foo_3(); }

So if you're doing something like this, you don't really need to worry about the compiler reordering the switch statement's cases since it's already a constant-time lookup.

In more general cases, where a deterministic index isn't practical, dictionary-lookup logic can be applied.


How a file is determined If I have the integer ""1234" stored in a file, the size of the file when I use the command "ls -l" or "wc -c" is 5. If I have "12345" the size of the file is 6. Basically the number of bytes in a file = (number of individual digits) + 1. Now, I am assuming the "+1" comes from the space it takes to create the name of the file. But why is the rest of the byte count equal to the number of individual characters? Does the file system read the file character by character even we "write an integer" to the file? Elaboration on this would be very helpful.

The +1 is for the newline character.

The byte count equals the number of characters, in this case, because each character takes exactly one byte.  That need not be true in general (see, e.g., UTF-8), but it is for the example you listed.

You didn't write an integer to the file.  You wrote a string -- a sequence of characters, namely the character 1, then the character 2, then 3, then 4, then a newline.  Files don't store integers or other types.  They store a sequence of bytes.  Each character is converted to one or more bytes using an encoding, and then the sequence of bytes is written.


Intersection and partial quantity decidability I'm still insecure in the section decidability (no proof needed, I want to divine it):

X is decidable and Y is undecidable. Is the intersection of X and Y decidable or undecidable?

X is decidable and Y is a partial quantity of X. Is Y decidable, too or not?

Thanks!

For your first question, the answer is that $X\cap Y$ will not necessarily be decidable. Let $Y$ be an undecidable language over an alphabet $\Sigma$ and let $X=\Sigma^*$. Then obviously $X$ will be decidable and $X\cap Y=Y$ will be undecidable. On the other hand, the intersection may be decidable, as we could show by letting $X=\emptyset$.

For your second question, I assume that by "$Y$ is a partial quantity of $X$" you mean that $Y$ is a subset of $X$ (i.e., $Y\subseteq X$). Then we can do a similar construction, letting $X=\Sigma^*$, and $Y$ be undecidable, so again, $Y$ may or may not be decidable.

It's worth mentioning that this latter result frequently trips up students. Very few properties of languages are closed under subset/superset: there's no guarantee that a subset of a regular language will be regular, for example.


Self-balancing BST supporting in-order-sequential multi-insertions / multi-deletions in logn+klogk time? Given a self-balancing binary search tree of size $n$, I want to perform the following operations:

InsertInOrderSequentialBatch an ordered sequence of $k$ values (specialized $k \in \{2, 3, 4\}$ or generalized $k \in N $) which are guaranteed to be sequential in an in-order tree traversal immediately after insertion.

For example, insert $[310, 320, 330, 340]$ into a balanced tree containing $[100, 200, 500]$.

Future insertions might still be between the inserted nodes' values.

DeleteRange all of $k$ nodes (likewise specialized or generalized) between 2 values in the BST.

For both operations, I want the tree to remain balanced.
With a Red-Black or AVL tree, I can achieve both operations through a sequence of $k$ insertions/deletions in $\mathcal{O}(k \log n)$, but wonder if a data structure (e.g. AVL/RB tree variant) could achieve $\mathcal{O}(\log n + k \log k)$ time for a real-world performance gain (e.g. traverse tree for insertion point, insert balanced tree into insertion point, perform one auto-balance pass)?
My needs are less theoretical and more in terms of wall-time & memory pressure for an implementation of Fortune's Algorithm - an algorithm with high constant-time multipliers is unfortunately not useful. My insertion sequence is biased & frequently multimodal (modes not known prior) with long streaks of insertions/deletions within modes. My tree size is anywhere from 100 to 3000 nodes.

This can be solved with split and join operations, both achievable in $\mathcal{O}(\log n)$ for Red-Black and AVL trees.
For Red-Black Trees this is doable either leveraging finger trees or via extending a regular Red-Black Tree as in Ron Wein's "Efficient Implementation of Red-Black Trees with Split and Catenate Operations" implemented in CGAL with criticisms mentioned in https://stackoverflow.com/questions/29029894/red-black-tree-split-concatenate-in-logn-time (Tarjan might have a better paper).
For AVL trees this is doable according to Ramzi Fadel and Kim Vagn Jakobsen's "Data structures and algorithms in a two-level memory".
InsertInOrderSequentialBatch is expressable as a split followed by 2 joins. DeleteRange is 2 splits followed by 1 join.


Weaker, but similar conditions to Turing completeness? A model of computation is called Turing complete if it can simulate any Turing machine.

This rules out for example a combinational logic circuit.

However, there is a sense in which combinational logic circuits can solve all problems that Turing machines can: while it is not the case that we can find for Turing machine $T$ a circuit that computes the same function $\{0,1\}^*\to\{0,1\}$ as $T$, it is nevertheless the case that we can find for each $n$, a circuit that computes the same function $\{0,1\}^n\to\{0,1\}$ as T does for inputs of size $n$.

Is there a term for whether a model of computation can compute the same functions as arbitrary Turing machines in this less restrictive sense?

The automaton as represented by a combinational logic circuit (CLC) is called combinational logic. Its model of computation is given an input, a CLC is used to compute the output. The name of that model of computation can also be called combinational logic. (This is similar to Turing machine, which is a kind of computing machine and also the name of the model of computation associate to it.)

The question has been answered. However, you might suspect there is no actual information in the answer so far. You may ask further, what is exactly that model of computation? How to understand it?

Firstly let us be clear, a combinational logic is the digital logic where the output is a pure function of the present input only. This is in contrast to sequential logic, in which the output depends not only on the present input but also on the history of the input and which can be used to build finite automatons.

Define a Turing machine (TM) as bounded-computing if there is a natural number $n$ such that it always halts before $n$ transitions. Define bounded computation as the following model of computation: given an input, a bounded-computing TM is used to compute the output.

A finite language is a language in which the number of words is finite. What are the languages that are accepted by the bounded-computing TMs? The answer is finite languages.

What is the computation done by a CLC?  For any given $n$ and $m$, and a function $f:\{0,1\}^n\to\{0,1\}^m$, there is a combinational logic circuit (CLC) that outputs $f(s)$ given $s\in\{0,1\}^n$ as input. That is all a CLC can do. Note that the input are limited to strings of same length, which is, however, not a limitation of its computing capability since a CLC can pad shorter inputs to longer inputs of the same longer length. Another apparent limitation is that the input can only be words made up from two symbols, 0 and 1. That is not an actual limitation, either, since we can encode any finitely many symbols by two symbols. For example, the $i^{\text{th}}$ symbol can be encoded as $011\cdots1$ where the number of $1$s is $i$.

As it might have become intuitively clear by now, the computation by a CLC and computation by a bounded-computing TM are weakly computational equivalent. (Weak computational equivalence of two models of computation means the set of functions computed by one of them is "the same" as the set of functions computed by the other. Strong computational equivalence means there exists a simulation between the two How to show two models of computation are equivalent?). The detail of a demonstration of the weak computational equivalence is not shown here. However, the ideas are pretty simple. Now we know that combinational logic is computational equivalent to bounding computing. Hopefully, that provides a bit of insight into what is combinational logic as a model of computation.

There is a model of computation called combinatory logic, which is weakly computational equivalent to Turing machine but is not relevant here.


Arrangement of numbers in a grid I have a $n \times m$ matrix $M$ and a permutation of sequence $P$ of numbers from $1$ to $n$.

I have to fill the matrix using numbers $1$ to $n \times m$ in such a way that for each row $i$, the function $f(i) > 0.5$ where:

$f(i)$ is the probability that a number chosen randomly from row $i$ will be greater than a number chosen randomly from row $P[i]$. ($i$'s corresponding row according to permutation.)

For an example, let $n=3$,$m=3$,$P=[3, 1, 2]$ and $M=$

2 6 7
3 4 8
1 5 9

According to the given permutation, you will have to compare the number chosen from 1st row with 3rd row and similarly.

In the given matrix number are arranged in such a way that $f(1) = f(2) = f(3) = 5/9$.
Observe that there are 5 pairs in the Cartesian product $\{2,6,7\}\times\{1,5,9\}$ which the first element is larger than the second.

My question is how to construct such a matrix provided $n,m,P$ as input?

Here are some ideas for you to start thinking.

First of all, the problem isn't always solvable. For example, if $P$ contains a fixed point or a cycle of length 2, there is no solution (why?).

More generally, For each $m,k$, either there is a $k \ldots m$ solution for a cycle of length $k$, or there isn't. Let $L_m$ be the set of $k$ such that a solution exists (so $1,2 \not\in L_m$ for all $m$, and $3 \in L_3$). Then for given $m,P$, there is a solution iff the sizes of all cycles in $P$ lie in $L_m$ (why?).

It remains to determine $L_m$. Let us know if you get stuck doing that. You can start with small $m$ such as $1,2,3$.


Is the set of all Context free languages a Context sensitive Language? ( can we build a LBA that decides whether a given language is CFL or not?) What i mean is that can we code each CFL ( the same way we code each turing machine in the Universal Turing Machine ) and build a Linear bounded Automata in such a way that for each input ( which is a code of a particular CFL) decides whether this is a context free language ( accept ) or not?

I hope my question makes sense or maybe I'm confused, because i know that set of all regular expressions(regular languages) is a Context sensitive language because we can make a context sensitive grammar for it so i was wondering what can we say about the set of all context free languages?

If you consider a grammar $(N, \Sigma, P, S)$ you could actually give a regular expression for the production rules $P$, which pretty much determine the whole grammar:
$$r = S \to (\bar{N} + \bar{\Sigma})^\ast (| (\bar{N} + \bar{\Sigma})^\ast)^\ast (, \bar{N} \to (\bar{N} + \bar{\Sigma})^\ast (| (\bar{N} + \bar{\Sigma})^\ast)^\ast)^\ast$$
over the alphabet $N \cup \Sigma \cup \{,, |, \to\}$, where we use the $\bar{N}, \bar{\Sigma}$ as shortcut for $\sum_{A \in N} A$ and $\sum_{a \in \Sigma} a$.

So you could pass the grammar (the "code" of the cfl) to a finite automaton to check whether it is a context-free-grammar.

Basically, you just have to check whether there is only one single non-terminal in front of a $\to$. There is no nesting in contex-free grammars in contrast to regular expressions.


Is there a canonical definition of “pure” function? StackOverflow pointed me here, so the question might be a bit in a layman's terms.

Wikipedia defines pure functions as

  In computer programming, a function may be described as a pure
  function if both these statements about the function hold:

  The function always evaluates the same result value given the same
  argument value(s). The function result value cannot depend on any
  hidden information or state that may change as program execution
  proceeds or between different executions of the program, nor can it
  depend on any external input from I/O devices.
  Evaluation of the result does not cause any semantically observable side effect or
  output, such as mutation of mutable objects or output to I/O devices.

However it does not seem to cite any sources -- so it is hard to say whether this is an accepted definition, or who defined it this way.

When I look at what the languages do when they include a syntax/annotation for "pure" functions, there are quite a few different approaches:

In D the only limitation is non-mutation of global state. "Pure" functions can mutate its arguments.
In GCC there are two types of "pure": pure (no side-effects, but can read global state) and const (stricly pure as per wikipedia definition).
In C#, it is defined as "does not make any visible state changes" (whatever that is).
Haskell follows the Wikipedia definition.

So my question is: is there a canonical definition of pure function?
And if there is, what is its source?

As noted in this paper Imperative Functional Programming, (1993) by Peyton-Jones and Wadler (among the group of researchers that created Haskell):

  We focus on purely-functional solutions, which rule out side effects,
  for two reasons. Firstly, the absence of side effects permits
  unrestricted use of equational reasoning and program transformation...

the focus is on absence of side-effects to enable program transformations (i.e compiler optimisations).

What are side-effects? This paper in turn points to Integrating functional and imperative programming (1986) by Gifford and Lucassen, which mentions four types of effect classes: Pure, Function, Observer and Procedure. So, the term "pure function" derives from this paper.

  a PURE is referentially transparent: it does not cause side-effects,
  its value is not affected by side-effects, and it returns the same
  value each time it is evaluated.

Note, however, that Peyton-Jones and Wadler mentioned shortcomings in this approach. Worth noticing, they say, is the programming language Clean that uses linear types to introduce side-effects in a safe manner (i.e. safe for the compiler). Basically, it threads the World as a variable in all I/O related functions, including the main entry point.

With that, it is possible to have a pure functional language interacting with the world and having side-effects (I/O, the OS, the Windowing system, etc), contradicting partially your wikipedia definition. One can in fact say that Haskell has Clean as one of its influencers; although it departs from linear types and uses another type-level construct (monads) to guarantee linearity, i.e. a single-reference at all times.


Hardness of approximating Minimum Cardinality Exact Cover The Minimum Cardinality Exact Cover (MCEC) problem is just like set cover, but the output sets must be disjoint.

Formally, given a collection of subsets $S$ of a finite set $U$, the problem asks for a subcollection $S'$ of $S$ of minimum cardinality such that the union of $S'$ is $U$, and $S_1 \cap S_2 = \emptyset$ for every distinct $S_1, S_2 \in S'$.

We may assume that for each $u \in U$' there is a set $S_u = \{u\}$ in $S$.  This ensures that there exists an exact cover of cardinality at most $|U|$.

I'd like to know if MCEC is as hard to approximate as set cover, i.e. cannot be approximated to within a $\log |U|$ factor.
I can show that MCEC has no constant factor approximation, reducing from $k$-Set-Cover for any constant $k$ by adding every subset of a set present in the set cover input.  But having the same inapproximability as set cover would be stronger.

Suppose that we are given an instance of EXACT 3-COVER (in which every set contains 3 elements) with $m$ sets on $n$ elements; EXACT 3-COVER is known to be NP-complete. Create a new instance in which each element is replicated $t$ times, each of the original $m$ sets contains each copy of each element, and additionally all $tn$ singletons are available. When the original EXACT 3-COVER instance is a YES instance, the new instance can be exactly covered using at most $m$ sets. When the original EXACT 3-COVER is a NO instance, every exact cover of the new instance requires at least $t$ sets (since every disjoint union of the original sets misses at least one original element, and so requires $t$ singletons in the new instance).

Now let us choose $t = mn^\theta$, for some constant $\theta$. The new instance contains $N = mn^{1+\theta} \leq n^{4+\theta}$ elements, and has a gap of $n^\theta \geq N^{\theta/(4+\theta)}$ between the YES and NO instances. As $\theta \to \infty$, the ratio $\theta/(4+\theta)$ approaches $1$. We conclude that your problem is NP-hard to approximate to within $n^{1-\epsilon}$ for any $\epsilon > 0$. In contrast, there is a trivial $n$-approximation algorithm, which just takes all the singletons.


How to get the upper, lower and average bound of a given algorithm? How to get upper, lower, average bound of  given algorithm? What should be the first step I should do? I search on the internet and only give me the definition of those 3. For example if take the algorithm of nlog(n)+2 then how do we find the lower and upper bound of this? What would be the first step?

When we talk of best case, worst case, and average case, it is in the context of algorithms whose running time depends on the input and not just on its length. If the algorithm always runs in time $n\log n + 2$, then the best case, worst case, and average case are all the same.

For a non-trivial example, consider quicksort. Quicksort always runs in time $O(n^2)$, and there is a sequence of arrays, one of each length, on which quicksort runs in time $\Theta(n^2)$. Therefore the worst case running time of quicksort is $\Theta(n^2)$. The best case running time varies according to the implementation – it can be $\Theta(n\log n)$ or $\Theta(n)$.

What about average case? Whenever we talk about average case, we need to introduce a distribution, according to which the average is taken. For sorting, the standard distribution is a random permutation of $1,\ldots,n$. The average case running time of quicksort, with respect to this distribution, is $\Theta(n\log n)$.

In other words, even though there are some arrays which are "difficult" or "bad" for quicksort, causing it to have quadratic running time, on "most" arrays it behaves much better, having a linearithmic running time. The running time depends not only on the length of the input array, but also on its order. This causes the discrepancy between worst case and average case for quicksort, and for many other (though not all) sorting algorithms.


Computationally and memory efficient algorithm for a relatively simple problem Given a list of non-overlapping ranges and values, i.e. [(0, 5, 0.5), (10, 15, 1.1), ...], and a list of potentially overlapping ranges (bins), i.e. [(0, 10), (5, 15), (0, 5), ...], find the average, min, max, standard deviation of the bins.
For example, the answer for averages would be [0.25, 0.55, 0.5, ...]. Assume there is a implicit range (5, 10, 0) in the first list.
The max range is from 1 to 109. The number of bins ranges from 1 $\le$ n $\ge$ 1010.
What is a memory and computationally efficient way of solving this problem?
Edit: The first list of non-overlapping ranges would create a list: [0.5, 0.5, 0.5, 0.5, 0.5, 0, 0, 0, 0, 0, 1.1, 1.1, 1.1, 1.1, 1.1, ...]. A pair in the second list would specify the indices of the range to find a statistic. The average for the first pair, (0, 10), would be (0.5 * 5 + 0 * 5) / 10 = 0.25.
This is an actual problem in bioinformatics, and an algorithm already exists here, but I was wondering if there was a potentially better one.

I don't know what algorithm they use so I don't know whether this will be better, but there is an efficient algorithm for your problem, by using a tree.  Form the list of all endpoints of all ranges and bins, and sort it.  This partitions the real line into non-overlapping intervals, where each bin is a union of intervals that don't overlap.
Put those endpoints into a binary search tree.  Each internal node in the binary tree represents a union of those intervals.  You can store, in each tree, the min, max, sum, and sum of squares of all values in that interval, filling these in bottom-up.  Note that given these statistics for the two children of a node, it is easy to compute these statistics for the node itself in $O(1)$ time.
This yields an $O(n \log n)$ time algorithm, where $n$ counts the number of ranges + number of bins. It takes $O(n \log n)$ time to sort the endpoints, then $O(n)$ time to build the binary search tree, then $O(n)$ time to fill in each node bottom-up.
You might also enjoy reading about interval trees and segment trees, if you do a lot of computation on ranges/intervals.


Linear codes : why has the parity check matrix dimensions $(n-k)*k$? I am studying Quantum error correction that is based on some aspects on classical error correction.

I am reading some very basics around linear error correcting codes.

I consider a linear code [n,k]: thus it encodes k bits of information into n bits.

My question: I don't understand why the parity check matrix has $n-k$ lines.

What I understand from the topic.

If I call $x$ the column vector of the information bits I want to encode in the n-bits, I define $G$ the generator matrix such that:

$$ y = G x $$

Where $y$ is my encoded information.

The $H$ matrix is built such that its kernel is the code space. Thus, its kernel must be composed of the column vectors of $G$ as the code space is spanned by the column vectors of $G$.

All this means that the line vectors of $H$ must be orthogonal to the column vectors of $G$.

But why do we have to take $n-k$ lines in $H$, why not $n$ lines, or $2$ lines ? I guess it is a way to ensure us that the Kernel of $H$ is exactly the code space but I don't understand why this number of lines ensure this.

You can have as many rows in $H$ as you like, but they will be linearly dependent after you reach $n-k$ independent rows.  You can apply the rank-nullity theorem.  If you like, think of the rank of $H$ as the number of pivots you get, when you row reduce.  It is the same number you get when you column reduce.  Now for $H$ is a $s\times n$-matrix with kernel of dimension $k$.  That means by the rank-nullity theorem that $\mathrm{rank}~H+k=n$.  So $\mathrm{rank}~H=n-k$ but rank is just the number of pivots (either from row or column reducing).  Said another way, $s\geq n-k$ and if $s>n-k$ then after row reducing you get just $n-k$ nonzero rows.  So the most compact $H$ is $(n-k)\times k$.

Usually one thinks of generator and parity check matrices as having been row/column reduced with 0 rows serving no purpose so omitted.  That forces your dimensions. But yes in principal you could repeat yourself, it just wouldn't help or be what anyone expects.  But no, you can't choose just 2 that will make for a larger kernel in general.


Prove that the set of recursive languages is infinite I know that set of all deciders is countable. I am wondering whether it is infinite.In other words can we prove that the set of recursive languages is infinite ?

Edit : The above question has small mistake as pointed out in one of the comments .. Since every recursive language has infinitely many deciders .. the two questions are indeed not equivalent . For people who are wondering why there are infintely many deciders , take a decider D and keep on adding some useless states, transitions, tape symbols so that you get new decider with a larger description than D and since you can continue this process indefinitely , there exists infinitely many deciders for a recursive language.


Are all data structures in the von Neumann architecture based on the array, or array-like? I am an old Pythonista now learning C and how various data structures and types are implemented, such as binary trees and hash tables. Learning about the latter, leads me understand that the hash function servers the purpose of computing from the key the index in the array where the value is stored. I have also learned that trees may be stored as arrays. Given that arrays are said to be efficient (for lookup, if not insert/delete) due to the way they match memory addressing in the von Neumann architecture, is it generally the case that all other structures are basically "supersets" or "super-structures" of the array?

After all, the array is nothing more than a contiguous collection of memory "cells", so we can think of an int as a single cell array. And we can think of a struct as an array where elements are not necessarily of the same type. I struggle to think how any other data structure could be constructed in any other way, but I guess it's best that I ask here to be sure.

EDIT: Just to be perfectly clear and correct, I do understand that a memory cell and a data element are not necessarily the same thing, an element may occupy more than one memory cell. The distinction between the two is a minor detail that shouldn't detract from the question.

Your question is a bit vague, but it seems that you're missing one mechanism: dynamic memory allocation. Some data structures such as linked lists are heavily based on dynamic memory allocation, and so although linked lists are very similar to arrays in function, they are implemented very differently.

Dynamic memory allocation is treated as a primitive in C. System libraries are supposed to implement the malloc() and free() primitives, with the support of the operating system. While eventually memory is accessed (in the CPU level) as one long array (perhaps some of it implemented as virtual memory), this is all hidden under the hood as far as the C programmer is considered (unless they choose to tinker with it).


Prove foldl fusion law I have proven the foldr Fusion Law as follows:

Given f is strict, f a = b and f (g x y) = h x (f y) for all x and y, than

f.foldr g a = foldr h b

Case []:

(f . foldr g a) [] = foldr h b [] -- Remove . notation
f (foldr g a [])   = foldr h b [] -- definition foldr
f (foldr g a [])   = b            -- definition foldr
f a                = b            -- This is a given, so stop

Case (x:xs):

(f . foldr g a) (x:xs) = foldr h b (x:xs)       -- remove . notation
f (foldr g a (x:xs))   = foldr h b (x:xs)       -- definition foldr
f (g x (foldr g a xs)) = h x (foldr h b xs)     -- inductive hypothesis
f (g x (foldr g a xs)) = h x (f (foldr g a xs)) -- introduce y
                 say y = foldr g a xs
f (g x y)              = h x (f y)              -- This is a given, so stop

Now, I would also like to prove the Fusion Law for foldl. This goes like this:

Given f is strict, f a = b and f (g x y) = h (f x) y for all x and y, than

f.foldl g a = foldl h b

However, I don't seem to be able to use the same trick as in the proof for foldr. How can I prove the foldl Fusion Law?

Let me try to answer your question, I may be mistaken, so check it out first:

Let's first state the definition of foldl:

foldl :: (a -> b -> a) -> a -> [b] -> a
foldl h b x = case x of
                []     -> b
                (x:xs) -> foldl h (h b x) xs

Now, we aim to prove that, given f:: A -> B, g:: A -> C -> A, h:: B -> C -> B, a:: A b:: B, such that:

f a = b
f (g x y) = h (f x) y, for all x, y
f is strict

Then:

f . foldl g a = foldl h b :: [C] -> B

We are going to prove it by induction on the length of the list:

Case 0:

f.foldl g a []   = foldl h b []
f (foldl g a []) = foldl h b []   -- Definition of .
f a              = b              -- Definition of foldl
True                              -- given

Case n => n+1:

let x:xs be a list of length n+1, then xs has length n, the property holds for xs. Let's check it's true for x:xs:

f (foldl g a (x:xs))   = foldl h b (x:xs)
f (foldl g (g a x) xs) = foldl h (h b x) xs  -- Definition of foldl

Now, let's take f' = f, g' = g, a' = g a x, h' = h, b' = h b x

Clearly, f' is strict, also, f' a' = b':

f' a'     = b'
f (g a x) = h b x  -- Opening the '
h (f a) x = h b x  -- Hypothesis
h b x     = h b x  -- Hypothesis

Now, let's check that f' (g' z y) = h' (f' z) y works for any y, z (I changed the x for a z, because we have a fixed x, the head of the list):

f' (g' z y) = h' (f' z) y
f (g z y)   = h (f z) y   -- Opening the '
                          -- OK: hypothesis

Now, since the predicate works for lists of length n, and xs has that length, and also f', g', h', a', b' make the premises true, we have that, for any list of size n, in particular xs:

f' . foldl g' a' xs      = foldl h' b' xs
f  . foldl g  (g a x) xs = foldl h (h b x) xs  -- Opening the '
f (foldl g (g a x) xs)   = foldl h (h b x) xs  -- What we were trying to reach


Assignment based on ranked preference Assume that there are n students, who have to be evenly assigned to m groups. For every student, a preference ranking of of the m groups is given.

I partially order assignment by pointwise preference, i.e. one is better or equal to another if for every student, the assigned group is ranked higher or equal.

What algorithm can I use find “locally optimal” solutions, i.e. assignments where there are no strictly better solutions?

I assume there will be multiple locally optimal solutions. Is there a sensible way to order them without giving the students an incentive to be dishonest in their ranking, i.e. without encouraging strategic voting? If so, can that be solved?

And finally: What are the right terms to search for research that solves this and related problems?

The terms you can use to search the literature are stable marriage and  the assignment problem.

As far as discouraging strategic voting, one relevant term might be strategy-proof.  This might also be relevant to the general area of mechanism design.  My vague recollection is that discouraging strategic voting in stable-marriage-like problems is a hard problem, but I don't know if I'm remembering that right.

For instance, consider stable marriage.  The traditional algorithm gives a matching that is male-optimal and female-pessimal (every male gets the best possible mate he possibly could have received in any stable matching; and every female gets the worst possible mate she could have received in any stable matching).  Now suppose the females all get together and collude.  In a world of perfect information, they can compute what the female-optimal matching would be, and then change their reported preferences to ensure that the female-optimal matching will be selected.

In fact, collusion is not necessary -- the same result happens if each female individually acts in their own self-interest, without any cooperation or conspiracy.  Assume again a world of perfect information, where everyone's true preferences are known (to the females, at least).  Then each female can compute the best possible mate she could hope for, i.e., the best mate out of all possible matches in all possible stable matchings; she can then change her reported preferences to list that male as her first preference.  If the men use their true preferences and each woman uses this procedure to select her preferences strategically, and then we run the traditional algorithm, we end up with the female-optimal (and male-pessimal) matching.  Each woman has an incentive to behave in this way, and no collusion is necessary (assuming perfect information).


Returning random integer from interval based on last result and a seed Suppose we have an interval of integers [a, b]. I would like to have a function that returns random members from within the interval, without repetitions. Once that all members within the interval are explored, the function would start to return the same first random sequence again, in the same order.
Example: a=1, b=5
3, 1, 4, 5, 2, 3, 1, 4, 5, 2, 3, 1, 4, 5, 2, ...

This would be easy to achieve by shuffling an array of all elements between a and b, and repeating it once the array is finished. However, this would take too much memory space, and this is not suitable for my case (I might have millions of elements).
Instead, the function I'd like to have would be more or less like this:
f(a, b, n, seed) -> n+1

Where:
a - start of interval
b - end of interval
n - last element returned from list
seed - self-explanatory
n+1 - next random element from list, calculated by using the seed and the last element returned (n)

The trick is knowing some way to get a non-repeated number from the interval based only on the element returned before and the seed. In the end, it would behave like a circular list randomized at its initialization, but without using memory space.

I suggest you pick a random permutation on the range $[a,b]$, i.e., a bijective function $\pi:[a,b]\to [a,b]$.  Then, maintain a counter $i$ that starts at $i=a$; at each step, output $\pi(i)$ and then increment $i$ (wrapping around so that $b+1$ becomes $a$).
There are standard methods for generating such a random permutation in the cryptography literature: look up format-preserving encryption.  The seed is the cryptographic key.  You will be able to compute $\pi(i)$ in $O(1)$ time and $O(1)$ space, so this should be very efficient and avoid the need for a lot of storage.
If you insist that the next output should be a function of the previous output, you can let $g(i)=i+1$ (except that $g(b)=a$), then let $f(i)=\pi^{-1}(g(\pi(i))$, where $\pi$ is a random permutation chosen as above.   This will then give you a random cycle that iterates through the elements of $[a,b]$ in a random order.  The outputs are the sequence $f(a),f(f(a)),f(f(f(a))),\dots$.


Given the regular set $S = a^*ba^*ba^*$, is the set $S'$ of all first thirds of strings in S (with length divisible by 3) regular? I have no idea how to approach this problem, could I get at least a hint on how to go about proving/disproving this?

I've tried the pumping lemma but I don't think it applies here. I've also tried reasoning about closure properties, but I think my reasoning is faulty. My thought process so far is a string (with length divisible by 3) that is in L can be denoted as a regular expression. As such, the machine M for L can be broken down into M1, M2 and M3, each a machine for handling the first, middle and last thirds of the string. M2 would therefore be the machine corresponding to J, so J is regular.

The first step is figuring out the language of first thirds of $S$. Let us denote this language by $L$. A good starting point is to consider the language $P$ of prefixes of $S$, since clearly $L \subseteq P$. The language $P$ is easy to find: it is
$$
a^*ba^*ba^* + a^*ba^* + a^*.
$$
With some work, you can show that $L$ and $P$ are rather close to each other, and so $L$ is regular. Details left to you.

More generally, if $S$ is any regular language, then the language $L$ of all first thirds of words in $S$ is always regular. The easiest proof of this is via NFAs. You can take it as a challenge, or look up material on the very similar operation of taking the first half of all words in a regular language.


Solve a recurrence by drawing the recursion tree? I'm studying for an entrance exam and I have sample questions. One of the questions is this

  Prove that recurrence $T(n) = T(n/5) + T(4n/5)+n/2$
  has a solution $T(n) = \omega(n \log n)$.

  Solve by drawing the recursion tree.

This is what I drew on my paper:

root:  n/2 => (4n/5)/2

           => (n/5)/2

right sub tree:  (4n/5)/2 => (16n/25)/2

                          => (4n/25)/2

left sub tree:   (n/5)/2  => (4n/25)/2

                          => (n/25)/2

From what I saw online when I was searching for a solution to this question I noticed people were drawing the trees and saying Big O something as an answer. I'm wondering how do they determine that Big O notation is the correct answer for this question or if my tree is correct?

Use the Akra-Bazzi method. In terms of the notation there you have:
$$
\begin{align*}
g(x) &= \frac{x}{2} = O(x^c) \\
a_i  &> 0 \quad \forall i \\
0 &< b_i < 1 \quad \forall i \\
\end{align*}
$$
The requisites check out (and the somehow implied differences $h_i(x)$  due to truncation if the divisions don't come out exact also check out). So we need the $p$ for which:
$$
\left( \frac{1}{5} \right)^p + \left( \frac{4}{5} \right)^p = 1
$$
which is seen to be $p = 1$. Plugging into the equation:
$$
T(x) = \Theta \left( x^p \left( 1 + \int_1^x \frac{g(u) d u}{u^{p + 1}} \right) \right)
     = \Theta (x (1 + \frac{1}{2} \ln x))
     = \Theta (x \ln x)
$$


What does the $^*$ operator do in the theory of parsing? I'm currently reading through Aho's "Theory of parsing, translation and compiling" on my own and I got a bit confused about the closure operator on language $L$ with alphabet $\Sigma$ ($L^*$). The book defines it recursively as follows:

\begin{align*}
1)\ L^0&=\{e\}\\
2)\ L^n&=LL^{n-1}\quad \text{for } n\ge1\\
3)\ L^*&=\bigcup_{n\ge0}{L^n}
\end{align*}

What sort of set does this operation define? It seemed to me that it defines something like "the set of all possible concatenations of strings of language $L$". There wasn't an actual example in the chapter, I can't figure it out.

It does exactly what you describe: $L^*$ contains all possible finite concatenations of words in L, including the empty word. This operator is known as the Kleene star, it is fundamental in the theory of regular languages and more generally of grammars.


Are all databases reducible to this ultimate abstract database design? I've designed a few databases in my time, and on more than one occasion the drive to abstract common elements from specific tables has led me to create generic top-level tables which contain those common elements.  For example:

Table      Column         Column

Hamburgers Item           Topping
           Cheeseburger   Tomatoes
           Mushroomburger Swiss

Could be "simplified" ("normalized") as:

Table      Column         Column

FoodTypes  ID             Name
           1              Hamburger
           2              Topping

Food       Item           TypeID
           Cheeseburger   1
           Mushroomburger 1
           Tomatoes       2
           Swiss          2

Recently I've gone over the deep end with this approach, abstracting and re-abstracting a fairly complex database design until I was left with something both very simple and yet completely un-resembling of the actual data being stored.

This has led me to the conclusion that all databases could be "summarized" in a single monstrous table called "Entries" with columns:

ID       Type     Value1     Value2

For example:

ID       Type     Value1     Value2
4321     Item
8746     Descrip  4321       Food
5673     Item
9876     Descrip  5673       Hamburger
0341     Item
1234     Descrip  0341       Lettuce
5478     Relation 5673       0341
2381     Descrip  5478       Topping
2244     Relation 5673       4321
2160     Descrip  2244       Class
4436     Relation 0341       4321
7547     Descrip  4436       Class

Here, using these 4 columns in 1 table, I have created two objects sharing a common superclass, given them an attribute, and defined not only a relationship between them but the class of that relationship as well.  We could now say "Lettuce is a Topping of Hamburger, both of which are Foods".

There would of course be a set of rules for this system, but that is beyond the scope of this question.

My question is, is this not logically the case?  If so (or if there is a different, "correct" answer), what is this in relation to real databases?  Does such a system exist, or should it not?

I'm not sure if I've gone far enough in my analysis, and I feel like I'm on the verge of some insight which is profoundly obvious to mathematicians and computer scientists (like "yes, all relational data can be described in terms of binary operands like F[a, b]).

This insight was made at least as far back as 1886, by Alfred Kempe.  In fact, he observed that any set of relationships (not just those that are already relations) can be captured as a binary relation.  At the time this seems to have come as a shock to Charles Sanders Peirce, who had built his relation algebra on the idea that any relation can be captured by means of ternary relations, and who up to this time apparently believed this to be the best possible.  Kempe used graphs to illustrate his notion, while Peirce used edge-labelled graphs.  In a long and admiring review Peirce revised his theories to accommodate binary relations as a possible foundation, and distinguished the two approaches:

  Mr. Kempe's conception depends upon considering the diagram purely in its self-contained relations, the idea of its representing anything being altogether left out of view; while my doctrine depends upon considering how the diagram is to be connected with nature.

In terms of modern database representations, RDF corresponds to Peirce's ternary relations, while key-value stores correspond to Kempe's graphs.  As Raphael pointed out in a comment, these are essentially the ideas behind graph databases.

As an aside, the arguments about binary/ternary/quaternary/quinternary/... tuples being the "best" foundation for data representation still rage on in the W3C semantic web working groups.  I believe that the original insight of the relational model was that for efficiency, one should use relations of the right arity; relationships that are naturally represented as tuples should not be transmogrified into more complicated data structures just for reasons of purity.  However, this argument also goes the other way: relationships where different instances naturally have different arities should not be shoehorned into a rigid relational schema just to preserve the purity of the data model.

A. B. Kempe, A Memoir on the Theory of Mathematical Form, Philosophical Transactions of the Royal Society of London 177, 1886, 1–70.
C. S. Peirce, The Critic of Arguments (1892 essay), in Collected Papers of Charles Sanders Peirce, Vol. III, Harvard University Press, 1933, 250–265.